Graphentheorie für Machine Learning

Ein Graph modelliert Entitäten und die Beziehungen zwischen ihnen. Formal ist ein Graph G = (V, E), wobei V die Menge der Knoten und E die Menge der Kanten ist, die Knotenpaare verbinden. Viele reale Systeme lassen sich von Natur aus als Graphen darstellen.

Jeder Knoten repräsentiert eine Entität (einen Benutzer, ein Atom, eine Webseite). Jede Kante repräsentiert eine Beziehung (eine Freundschaft, eine chemische Bindung, einen Hyperlink). Maschinelles Lernen mit Graphen lernt aus dieser Verbindungsstruktur und nicht nur aus isolierten Stichproben.

Die Adjazenzmatrix A kodiert, welche Knoten verbunden sind. Für n Knoten ist A eine n-mal-n-Matrix; A[i][j] = 1, wenn eine Kante Knoten i und Knoten j verbindet, andernfalls 0.

Neben der Struktur verfügt jeder Knoten normalerweise über einen Feature-Vektor. Zusammengestellt bilden diese die Feature-Matrix X mit der Form (num_nodes, num_features). In einem sozialen Graphen könnte eine Zeile das Alter eines Benutzers, die Anzahl seiner Beiträge und das Alter seines Kontos enthalten.

Der Grad eines Knotens ist die Anzahl seiner Kanten. Die Gradmatrix D ist eine Diagonalmatrix, deren Diagonaleinträge jeweils dem Knotengrad entsprechen. Sie bildet die Grundlage des Graph-Laplacians.

Der Graph-Laplacian ist definiert als L = D - A. Er erfasst, wie stark sich Werte zwischen verbundenen Knoten unterscheiden, und ist grundlegend für die Spektraltheorie von Graphen sowie für viele GNN-Formulierungen.

Die Eigenwerte und Eigenvektoren des Laplacians geben Aufschluss über die globale Struktur: Zusammenhang, Cluster und Glattheit. Graph-Faltungen werden häufig aus dem Laplacian hergeleitet. Daher ist das Verständnis von L = D - A entscheidend für das Verständnis von GNNs.

In einem ungerichteten Graphen hat eine Kante keine Richtung (Freundschaft), daher ist A symmetrisch. In einem gerichteten Graphen zeigen Kanten in eine Richtung (etwa bei einem Follower oder einer Zitation), daher kann A asymmetrisch sein: A[i][j] kann sich von A[j][i] unterscheiden.

Kanten können Gewichte tragen, die Stärke oder Entfernung darstellen. Dann sind die Einträge der Adjazenzmatrix reelle Zahlen und nicht nur 0 oder 1. In einem Straßennetz könnten die Kanten nach Fahrzeit gewichtet werden, in einem Ähnlichkeitsgraphen nach der Kosinusähnlichkeit.

Bei großen dünn besetzten Graphen verschwendet die Adjazenzmatrix Speicher, da die meisten Einträge null sind. ML-Frameworks speichern Kanten stattdessen als Kantenliste (COO-Format): zwei Arrays, die Quelle und Ziel jeder Kante angeben. PyTorch Geometric bezeichnet diese als edge_index.

Graphen kommen überall vor:

• Sozial: Freundschaftsempfehlungen, Community-Erkennung
• Molekular: Vorhersage von Moleküleigenschaften (Atome = Knoten, Bindungen = Kanten)
• Wissensgraphen: Link Prediction über Entitäten und Beziehungen
• Web/Zitationen: Ranking und Klassifikation

Testen Sie Ihr Wissen über Graphentheorie.

Sie haben die Grundlagen der Graphentheorie für ML gelernt:

• Ein Graph ist G = (V, E) und besteht aus Knoten und Kanten
• Die Adjazenzmatrix A kodiert die Verbindungen; X enthält die Knoten-Features
• Der Graph-Laplacian ist L = D - A
• Graphen können gerichtet oder ungerichtet sowie gewichtet oder ungewichtet sein
• Die Anwendungen reichen von sozialen Graphen über Molekülgraphen bis hin zu Wissensgraphen