Was ist der gewichtete Grad eines Knotens und wie beeinflusst er die Struktur von Graphen?

Der gewichtete Grad eines Knotens $i$ ist die Summe der Gewichtungen aller Kanten, die von diesem Knoten ausgehen. Formal lässt sich der gewichtete Grad als $\sum_{j=1}^{m} d_i = w_{ij}$ ausdrücken, wobei $w_{ij}$ die Gewichtung der Kante zwischen den Knoten $i$ und $j$ darstellt. Der Vektor der gewichteten Grade ist der Vektor $T_d = (d_1, d_2, \dots, d_m)$, der die Grade der Knoten als Einträge enthält. Die gewichtete Gradmatrix ist eine $m \times m$ Diagonalmatrix $D = \text{diag}(d_1, \dots, d_m)$, die die Grade der Knoten auf der Diagonalen abbildet.

In der Praxis sprechen wir häufig einfach von den "Graden" der Knoten und der Gradmatrix, ohne das Adjektiv „gewichtet“ zu verwenden. Für einen Digraphen gibt es eine äquivalente Definition des eingehenden Grads $\tilde{d}_i$, der die Kanten misst, die an Knoten $i$ enden. Dieser eingehende Grad ergibt sich, indem man in der Formel für den Grad $w_{ij}$ durch $w_{ji}$ ersetzt. Der Vektor der eingehenden Grade lautet dann $\tilde{d} = W^T1$. Bei einem ungerichteten Graphen, also einem Fall, bei dem $W = W^T$ symmetrisch ist, sind die Grade der Knoten identisch, das heißt, $\tilde{d} = d$.

In vielen praktischen Anwendungen von Graphen kommen zusätzliche Informationen zu den Knoten hinzu, die als Knotenmerkmale bezeichnet werden. Diese Merkmale können unterschiedliche Eigenschaften haben, abhängig davon, was die Knoten repräsentieren. Wenn die Knoten beispielsweise Bilder darstellen, könnten die Merkmale Pixelwerte der Bilder oder Informationen über deren Klassifikation oder Annotationen sein. Wenn die Knoten Websites darstellen, könnten die Merkmale den Typ der Website oder statistische Zusammenfassungen des Inhalts enthalten.

Ein „Walk“ in einem gewichteten Digraphen ist eine geordnete Liste von Kanten $\epsilon_1, \epsilon_2, \dots, \epsilon_k$, die benachbarte Knoten $m_1, m_2, \dots, m_{k+1}$ verbinden, wobei jede Kante $\epsilon_i = (m_i, m_{i+1})$ den Knoten $m_i$ mit dem Knoten $m_{i+1}$ verbindet und dabei eine positive Gewichtung $w_m > 0$ aufweist. In einem ungerichteten Graphen wird beim Walk keine Beachtung auf die Kantenrichtung gelegt. Ein „Trail“ ist ein Walk, bei dem keine Kanten wiederholt werden, also $\epsilon_i \neq \epsilon_j$ für $i \neq j$. Ein „Path“ ist ein Trail, bei dem auch keine Knoten wiederholt werden, also $m_i \neq m_j$ für $i \neq j$.

Ein „Circuit“ ist ein Trail, der zu seinem Ausgangspunkt zurückkehrt, also $m_{k+1} = m_1$. In einem solchen Circuit können Knoten zwar mehrfach besucht werden, aber jede Kante wird nur einmal durchlaufen. Bei gerichteten Graphen ist es wichtig, dass die Kanten in der richtigen Reihenfolge befahren werden, um einen validen Circuit zu bilden. Ein Circuit in einem ungerichteten Graphen hat hingegen keine Beachtung für die Kantenrichtung.

Schließlich wird häufig das Konzept eines „Indikatorvektors“ verwendet, um eine Teilmenge von Knoten $S \subset N$ zu repräsentieren. Der Indikatorvektor $1_S \in \mathbb{R}^m$ hat den Wert 1 an den Positionen der Knoten, die zu $S$ gehören, und den Wert 0 an allen anderen Positionen. Diese Vektoren sind in der Regel orthogonal, wenn sie verschiedene Teilmengen repräsentieren.

Wie lässt sich der Graph-Laplacian für die binäre spektrale Clusterung nutzen?

Die Diskussion über die Struktur der Eigenvektoren des Graph-Laplacians in Lemma 9.28 vermittelt wichtige Einsichten in die Funktionsweise von spektralen Methoden zur Clusterung. Insbesondere wird dort gezeigt, dass die höchsten Eigenvektoren des Graph-Laplacians besonders stark schwanken, was zu einer schnellen Wechselwirkung der Vorzeichen entlang der Kanten führt. Diese Erkenntnis ist von grundlegender Bedeutung, wenn man sich der Frage widmet, wie man Graphen in Cluster unterteilt.

Wenn wir uns ein einfaches Szenario vorstellen, bei dem der Grad $d_i = d$ für alle Knoten im Graph konstant ist, wird die einzige Stelle, an der eine Ungleichung im Beweis von Lemma 9.28 auftritt, die Schätzung in Gleichung (9.28). Angenommen, alle Einträge des Vektors $x$ haben den absoluten Wert 1, das heißt $x_i = \pm 1$ für alle $i$, dann gilt die Gleichung (9.28) genau dann, wenn $x_i = 1$ und $x_j = -1$ oder umgekehrt, was bedeutet, dass beide Seiten der Ungleichung den Wert 4 erreichen. Diese Erkenntnis wird noch deutlicher, wenn man bedenkt, dass diese Schätzung nur über Kanten im Graphen genutzt wird, da sie mit $w_{ij}$ im nächsten Schritt des Beweises multipliziert wird. Daraus folgt, dass die höchsten Eigenvektoren des Graph-Laplacians Vektoren sind, deren Einträge über den Graphen hinweg stark oszillieren, indem sie die Vorzeichen über möglichst viele Kanten hinweg ändern.

Ein Beispiel für eine konkrete Anwendung dieser Theorie ist die binäre spektrale Clusterung, bei der wir den Graph-Laplacian dazu verwenden, Knoten eines gewichteten Graphen in zwei Gruppen zu unterteilen. Ziel ist es, eine Partition des Graphen in zwei komplementäre Teilmengen $A \subset N$ und $A^c = N \setminus A$ zu finden, sodass möglichst wenige Kanten zwischen den beiden Teilmengen existieren. Dies lässt sich als Minimierung der sogenannten Graph-Cut-Energie formulieren, die in Gleichung (9.29) angegeben ist:

Dabei stellt die Graph-Cut-Energie die Summe der Kantengewichte dar, die durch das Schneiden der Kanten des Graphen zwischen den zwei Teilmengen entstehen. Die Idee, diese Energie zu minimieren, erscheint zunächst sinnvoll, da dies zu einer Trennung des Graphen führt, bei der nur wenige Kanten durchtrennt werden müssen. In der Praxis hat sich jedoch gezeigt, dass diese Methode suboptimale Clusterungen erzeugen kann, insbesondere in Fällen, in denen eine Teilmenge $A$ nur einen einzelnen ausreißenden Knoten enthält oder sogar die triviale Partition $A = \emptyset$ gewählt wird, was dann eine ungenaue Clusterung zur Folge hat.

Diese Normalisierung sorgt dafür, dass keine der beiden Teilmengen zu klein wird. Wenn eine der Mengen leer ist, wird die Average Cut-Energie unendlich, was darauf hinweist, dass eine triviale Partition vermieden wird. Darüber hinaus hat man die Möglichkeit, die so genannte Normalized Cut-Energie zu minimieren, die die Größe der Teilmengen auf eine andere Weise berücksichtigt und ebenfalls eine verbesserte Clusterung ermöglicht.

Ein weiteres nützliches Konzept, das hier in Betracht gezogen wird, ist der Zusammenhang zwischen der Durchschnitts-Cut-Energie und der Spektraltheorie des Graphen, speziell den Eigenwerten und Eigenvektoren des Graph-Laplacians. Durch die Spektralanalyse des Graphen wird es möglich, die Clusterstrukturen des Graphen zu extrahieren, ohne sich direkt mit den schwierigen Optimierungsproblemen auseinanderzusetzen.