Graph Neural Networks (GCN) verständlich erklärt

Ein Lieferdienst weiß nur von wenigen Kunden, ob sie in der Innenstadt oder in der Vorstadt wohnen. Für alle anderen fragt ein Rechenverfahren die Nachbarn. Diese Seite erklärt, wann das hilft und wann es schadet.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Kunden, von denen man fast nichts weiß

Ein Lieferdienst beliefert Kunden in einem großen Gebiet. Jeder Kunde gehört zu einem Gebietstyp: Innenstadt, Vorstadt, Land oder Gewerbegebiet. Jeder Gebietstyp bildet eine zusammenhängende Fläche auf der Karte. In der Innenstadt ist Parken schwer, auf dem Land sind die Wege weit.

Den Gebietstyp kennt der Dienst nur von wenigen Kunden. Von allen anderen hat er vier Messwerte aus den Fahrten: Stopps je Stunde, Dauer der Parksuche, Ladegewicht und Enge des Zeitfensters für die Lieferung. Diese Werte schwanken von Kunde zu Kunde zufällig. Ein Kunde in der Innenstadt kann deshalb einmal aussehen wie ein Kunde auf dem Land.

Aus den Messwerten soll man den Gebietstyp der übrigen Kunden erraten. Schaut man nur auf den einzelnen Kunden, kann der Zufall in die Irre führen.

Der Trick: erst die Nachbarn befragen

Kunden, die nah beieinander wohnen, liegen meist im selben Gebietstyp, denn jeder Gebietstyp ist eine zusammenhängende Fläche. Also hilft ein Blick auf die Nachbarn. Dazu zeichnet man eine Karte mit einem Punkt je Kunde und Linien zwischen jedem Kunden und seinen nächsten Nachbarn. Eine solche Karte aus Punkten und Linien heißt Graph. Eine Linie ist stimmig, wenn beide Kunden denselben Gebietstyp haben.

Das Verfahren mischt nun die Messwerte jedes Kunden unter die seiner Nachbarn. Das Bild dazu sind Thermometer. Ein einzelnes Thermometer kann falsch anzeigen. Hängen fünf nebeneinander, gleichen sich ihre Zufallsfehler aus, weil mal eines zu hoch und mal eines zu tief liegt. Alle messen dieselbe Raumtemperatur, so wie Nachbarn meist denselben Gebietstyp teilen. Beim Mischen bleibt, was die Nachbarn teilen, und der Zufall jedes Einzelnen zählt weniger.

Das Mischen läuft in Schichten. Eine Schicht ist eine Fragerunde bei den direkten Nachbarn, die nächste bringt auch die Nachbarn der Nachbarn ein. Danach muss es aus den gemischten Werten auf den Gebietstyp schließen. Dafür probiert es an den bekannten Kunden Rechenregeln aus, bis sie möglichst oft den richtigen Gebietstyp ergeben, und schätzt damit die übrigen Kunden (Fachwort: neuronales Netz). Das ganze Verfahren heißt Graph Convolutional Network, kurz GCN.

Wie viel das Mischen bringt, zeigt ein Vergleich. Dasselbe Verfahren läuft ein zweites Mal ohne Linien. Es sieht dann nur den einzelnen Kunden und heißt hier Vergleichsverfahren. Jeder Unterschied zwischen beiden Läufen stammt also von den Nachbarn.

Rechenbild und Programm zum Ausprobieren

Alle Kunden, Messwerte und Linien dieser Seite sind erzeugt. Sie stammen aus einem vereinfachten Rechenbild (Fachwort: Modell) eines Liefergebiets, nicht aus der Wirklichkeit. Die Aussagen unten gelten für dieses Rechenbild.

Zu dieser Seite gehört ein Programm zum Ausprobieren, die Demo. Sie erreichen es über den ersten Knopf unten, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie die Demo nicht.

Was das Rechenbild zeigt

Ein Beispielgebiet hat 200 Kunden in drei Gebietstypen. Jeder Kunde ist mit seinen fünf nächsten Nachbarn verbunden. Gemessen wird, wie viele unbekannte Kunden das Verfahren richtig einordnet.

• Fünf bekannte Kunden je Gebietstyp: Das GCN ordnet 88 Prozent richtig ein, das Vergleichsverfahren 69 Prozent.
• Nur zwei bekannte Kunden je Gebietstyp, im selben Gebiet: Das GCN erreicht 81 Prozent, das Vergleichsverfahren 50 Prozent.

Einzelne Gebiete weichen stark voneinander ab. Das GCN war trotzdem in jedem von acht erzeugten Gebieten besser als das Vergleichsverfahren.

Wenn die Linien nicht stimmen

Der Trick gilt nur, wenn Nachbarn wirklich meist im selben Gebietstyp liegen. Stellen Sie sich vor, die Nachbarschaftsliste des Dienstes ist veraltet. Viele Linien verbinden dann Kunden, die gar nicht nebeneinander wohnen. Das ist, als mittelten Sie die Raumtemperatur aus Thermometern in fünf verschiedenen Häusern. Die Mischung passt zu keinem Haus.

Das GCN kann eine falsche Linie nicht erkennen. Wie stark ein Nachbar beim Mischen mitzählt, hängt nur von der Zahl der Nachbarn ab, nie davon, was er meldet. Es mischt eine falsche Linie also genauso ein wie eine stimmige.

Man ersetzt einen wachsenden Anteil der Linien durch zufällige. Im Mittel über zwölf erzeugte Gebiete wird das GCN dabei Schritt für Schritt schlechter. Das Vergleichsverfahren bleibt gleich, weil es die Linien nie benutzt. Zum Vergleich: Im Beispielgebiet waren 92 von 100 Linien stimmig. Der Wechsel liegt zwischen den Fällen, in denen nur noch 59 von 100 Linien stimmig sind und 49 von 100. Bei 59 liegt das GCN noch vorn, bei 49 liegt es hinten.

Kann man zu oft mischen?

Mischt man immer weiter, werden sich alle Kunden ähnlicher. Das Bild dazu: Wer Farben immer weiter verrührt, bekommt am Ende überall dieselbe Mischfarbe. Jeder Mischschritt zieht die Werte eines Kunden zu denen seiner Nachbarn. Fachleute nennen das Über-Glättung.

Zuerst hilft das Mischen aber. Die Messung mischt dafür nur und lernt nichts. Sie ordnet jeden Kunden dem Gebietstyp zu, dessen bekannte Kunden ihm im Durchschnitt am ähnlichsten sind. Die Zuordnung wird erst besser und dann schlechter: Unter den ausprobierten Schrittzahlen stimmt sie nach acht Mischschritten am häufigsten (92 Prozent), nach sehr vielen nur noch bei 78 Prozent. Zuerst dämpft das Mischen den Zufall, später verwischt es die Unterschiede zwischen den Gebietstypen.

Beim lernenden Netz zeigte die Messung keinen Einbruch. Mit einer bis acht Schichten blieb der Anteil richtiger Kunden ähnlich hoch. Das ist kein Widerspruch: Beim reinen Mischen gibt es keine Rechenregel, die etwas ausgleichen könnte. Das Netz kann seine Regel dagegen anpassen. Eine Vermutung ist, dass es so die Angleichung ausgleicht. Getrennt geprüft hat die Messung das nicht.

Häufige Missverständnisse

• „Wenn ich genug Kunden kenne, brauche ich die Nachbarn nicht.“ Doch. Mit mehr bekannten Kunden wurden beide Verfahren besser. Der Abstand blieb ähnlich groß (Mittel über zwölf Gebiete, zwei bis zwanzig bekannte Kunden je Gebietstyp). Ein bekannter Kunde macht die Werte der anderen nicht weniger zufällig. Das leistet nur das Mischen.
• „Die Nachbarn verraten ihren Gebietstyp.“ Nein. Die meisten Nachbarn sind selbst unbekannte Kunden, denn nur wenige Kunden sind bekannt. Das GCN reicht nur Messwerte weiter, nie einen Gebietstyp. Eine Linie sagt nur: Diese beiden Kunden liegen nah beieinander.

Woran Sie das im Alltag erkennen

• Sie kennen die Wahrheit nur für wenige Fälle und sollen viele einordnen, etwa den Musikgeschmack aus dem der Freunde. Das klappt nur, solange Freunde einander ähneln.
• Warnzeichen: Die Verbindungen sind alt oder zufällig entstanden, etwa ein Verteiler, in den jeder beliebig eingetragen wurde. Dann kann das Befragen der Umgebung das Urteil verschlechtern.

Wie ernst ist das Rechenbild zu nehmen?

Das Rechenbild kennt nur vier Messwerte je Kunde und zusammenhängende Gebietstypen. Ob ein echtes Liefergebiet so aufgebaut ist, zeigt es nicht.

Was Sie mitnehmen:

• Fragen Sie bei jeder Schätzung aus der Umgebung zuerst, ob die Umgebung meist dasselbe Muster teilt.
• Prüfen Sie die Verbindungsliste, bevor Sie dem Ergebnis trauen. Eine falsche Liste kann schlechter sein als gar keine.
• Vergleichen Sie fair: dieselbe Rechnung mit und ohne Nachbarn, damit klar ist, woher ein Unterschied kommt.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Gesucht ist die Klasse (der Gebietstyp) jedes Knotens eines Graphen, wenn sie nur für wenige Knoten bekannt ist (semi-überwachtes Lernen). Beschrieben sind ein Graph Convolutional Network (GCN) nach Kipf und Welling (2017), von Grund auf in numpy geschrieben, und seine Messung auf erzeugten Daten.

• Daten: \(n\) Kunden (Knoten) in einem Gebiet, Voreinstellung 200, einstellbar von 60 bis 400. Das Gebiet zerfällt in \(K\) räumlich zusammenhängende Gebietstypen (Voreinstellung 3, einstellbar von 2 bis 4): Der Typ eines Kunden ist das nächste von \(K\) verdeckten Zentren, die einen Mindestabstand haben. Jeder Kunde hat vier Merkmale \(x_i\) (Stopps je Stunde, Parksuche, Ladegewicht, Zeitfenster-Enge). Die Mittelwerte \(\mu_t\) der Typen sind zufällige Einheitsvektoren, das Merkmal ist Mittelwert plus Rauschen. Das Rauschen ist je Kunde und Merkmal unabhängig normalverteilt; der Rauschregler hat die Voreinstellung 1,5, und die Standardabweichung \(\sigma\) je Merkmal ist die Hälfte des Reglerwerts.
• Graph: symmetrische Kanten zu den \(k\) räumlich nächsten Kunden (Voreinstellung \(k = 5\)), \(d_i\) ist die Zahl der Nachbarn von Knoten \(i\). Der Regler „falsche Kanten“ ersetzt einen Anteil \(r\) der Kanten durch zufällige; die Kantenzahl bleibt, die Homophilie \(h\) (Anteil der Kanten zwischen Knoten desselben Typs) sinkt.
• Bekannte Etiketten: Je Gebietstyp sind \(c\) Kunden bekannt (Voreinstellung 5, in den Messreihen 2 bis 20), zusammen \(m\) Knoten. Alle übrigen sind unbekannt und dienen als Prüfmenge; ihre Genauigkeit wird nur angezeigt und nie zur Auswahl benutzt. Die unbekannten Knoten gehören zum Graphen und liefern ihre Merkmale; nur ihre Etiketten fehlen (transduktiv).
• Netz und Training: \(L\) Schichten (Voreinstellung 2, einstellbar von 1 bis 8), 16 verdeckte Einheiten, Glorot-Start (gleichverteilte Anfangsgewichte, Spannweite nach Schichtbreite), Softmax-Kreuzentropie auf den bekannten Knoten, Gewichtszerfall \(\lambda = 5 \cdot 10^{-4}\) auf allen Schichten, Adam (Gradientenverfahren mit angepasster Schrittweite je Gewicht) mit Lernrate 0,01, fest 200 Epochen. Es gibt kein Abstimmen an der Prüfmenge. Gemessen wird der Anteil richtig vorhergesagter unbekannter Knoten nach der letzten Epoche.
• Vergleichsnetz (MLP): dasselbe Netz mit \(\hat A = I\), also ohne Nachbarn, mit demselben Start und demselben Training.
• Beispielgebiet: 200 Kunden, 3 Gebietstypen, 5 bekannte Kunden je Typ, \(k = 5\) nächste Nachbarn je Kunde, Rauschregler 1,5, 2 Schichten, ein fest gewähltes Gebiet; die Prüfmenge hat 185 Kunden.
• Messreihen: Die Reihen mitteln über 12 erzeugte Gebiete (jedes mit eigener Zufallszahlenfolge) bei den Einstellungen des Beispielgebiets, soweit nicht anders genannt; die Streuung der Einzelgebiete zeigt eine Reihe über 8 Gebiete.

Die Formeln

Sei \(A\) die symmetrische 0/1-Nachbarschaftsmatrix und \(\tilde A = A + I\) die Matrix mit einer Schleife je Knoten. Mit \(\tilde D_{ii} = \sum_j \tilde A_{ij}\), also \(\tilde d_i = d_i + 1\), ist die Normierung

\[\hat A = \tilde D^{-1/2} \tilde A \tilde D^{-1/2}\]

Ein Nachbar \(j\) geht mit \(\hat A_{ij} = 1/\sqrt{\tilde d_i \tilde d_j}\) in die Mischung von Knoten \(i\) ein, der Knoten selbst mit \(1/\tilde d_i\). Das Gewicht hängt nur von den Graden ab, nie vom Inhalt des Nachbarn. Mit \(H^{(0)} = X\) (Zeilen \(x_i\)) und lernbaren Matrizen \(W^{(l)}\) mischt jede Schicht über den Graphen und rechnet dann um. Dabei sei \(Z^{(l)} = \hat A H^{(l-1)} W^{(l)}\) die Eingabe der Aktivierung. Für \(l < L\) gilt

\[H^{(l)} = \mathrm{ReLU}(\hat A H^{(l-1)} W^{(l)})\]

Die letzte Schicht hat keine ReLU; ihre Ausgabe \(Z^{(L)}\) sind die Logits, deren Zeile \(Z_i\) der Softmax auf Klassenwahrscheinlichkeiten abbildet. Nach \(L\) Schichten hängt die Ausgabe eines Knotens nur von Knoten im Abstand höchstens \(L\) ab, denn \(\hat A_{ij} \ne 0\) gilt nur für Nachbarn und für \(j = i\). Das Training minimiert über die \(m\) bekannten Knoten die Kreuzentropie plus Gewichtszerfall:

\[\mathcal L = -\frac1m \sum_{i \in \text{bekannt}} \log \mathrm{softmax}(Z_i)_{y_i} + \frac{\lambda}{2}\sum_l \lVert W^{(l)} \rVert_F^2\]

Mit der Fehlergröße \(\delta^{(L)} = (\mathrm{softmax}(Z^{(L)}) - Y)/m\) auf den bekannten Zeilen (\(Y\) ist die One-Hot-Matrix der Etiketten; auf den unbekannten Zeilen ist \(\delta^{(L)} = 0\)) lauten die Gradienten, rückwärts über die Schichten:

\[\partial\mathcal L/\partial W^{(l)} = (\hat A H^{(l-1)})^\top \delta^{(l)} + \lambda W^{(l)}\]

\[\delta^{(l-1)} = \hat A\,(\delta^{(l)} W^{(l)\top}) \odot \mathbb 1[Z^{(l-1)} > 0]\]

Dabei wird die Symmetrie von \(\hat A\) benutzt; \(\odot\) ist das elementweise Produkt, \(\mathbb 1[\cdot]\) die Indikatormatrix.

Herleitungen Schritt für Schritt

Die folgenden Herleitungen sind Rechnungen dieser Seite, keine Messungen der Demo. Gegenproben der Demo stehen in der Befundtabelle.

Eine Schicht am Pfad aus drei Knoten.

• Schritt 1: Knoten 0, 1, 2 bilden einen Pfad (0 – 1 – 2). Mit den Schleifen sind die Grade \(\tilde d = (2, 3, 2)\).
• Schritt 2: \(\hat A_{00} = 1/2\), \(\hat A_{01} = 1/\sqrt 6\), \(\hat A_{11} = 1/3\) und \(\hat A_{02} = 0\), weil 0 und 2 keine Nachbarn sind. Die Matrix ist symmetrisch.
• Schritt 3: Mit einem Merkmal je Knoten, \(x = (1, 2, 4)\), und \(W = 1\) ergibt sich die Ausgabe der Tabelle. Gerundet (Rechnung dieser Seite): Knoten 0 steigt von 1 um knapp ein Drittel, Knoten 1 liegt gut eine halbe Einheit über 2, Knoten 2 sinkt von 4 auf knapp unter 3. Der kleinste Wert steigt, der größte sinkt: Die Werte rücken zusammen.
• Schritt 4: Die Zeilensummen von \(\hat A\) sind nicht 1: Für Knoten 0 ist \(1/2 + 1/\sqrt 6\) kleiner als 1, für Knoten 1 ist \(2/\sqrt 6 + 1/3\) größer als 1. Die Mischung ist also eine gewichtete Summe, nur näherungsweise ein Mittelwert.

Knoten \(i\)	\(\tilde d_i\)	Eingabe \(x_i\)	Ausgabe \((\hat A x)_i\)
0	2	1	\(\tfrac12 \cdot 1 + \tfrac{1}{\sqrt 6} \cdot 2\)
1	3	2	\(\tfrac{1}{\sqrt 6} \cdot 1 + \tfrac13 \cdot 2 + \tfrac{1}{\sqrt 6} \cdot 4\)
2	2	4	\(\tfrac{1}{\sqrt 6} \cdot 2 + \tfrac12 \cdot 4\)

Warum Mischen das Rauschen dämpft. Annahmen: Das Merkmal von Knoten \(j\) ist \(x_j = \mu_{y_j} + \varepsilon_j\), die \(\varepsilon_j\) sind unabhängig mit Mittelwert 0 und Standardabweichung \(\sigma\) je Merkmal; alle Nachbarn von Knoten \(i\) haben denselben Typ \(t\).

• Schritt 1: Zeile \(i\) von \(\hat A X\) ist \(\sum_j \hat A_{ij} x_j = \big(\sum_j \hat A_{ij}\big)\mu_t + \sum_j \hat A_{ij}\varepsilon_j\): ein Signalanteil und ein Rauschanteil.
• Schritt 2: Wegen der Unabhängigkeit hat der Rauschanteil je Merkmal die Standardabweichung \(\sigma \sqrt{\sum_j \hat A_{ij}^2}\).
• Schritt 3: Das Verhältnis von Signal zu Rauschen wird mit \(\sum_j \hat A_{ij} \big/ \sqrt{\sum_j \hat A_{ij}^2}\) multipliziert. Nach der Cauchy-Schwarz-Ungleichung ist das höchstens \(\sqrt{\tilde d_i}\) und wird nur bei gleichen Gewichten erreicht. Der Gewinn aus dem Mischen ist also höchstens \(\sqrt{d_i + 1}\) und bei den ungleichen Gewichten des GCN kleiner. Im Graphen mit den \(k\) nächsten Nachbarn und ohne falsche Kanten ist \(d_i \ge k\), die Obergrenze also mindestens \(\sqrt{k + 1}\).
• Schritt 4: Ist nur ein Anteil \(h\) der Nachbarn vom eigenen Typ und der Rest gleichmäßig auf die \(K - 1\) anderen Typen verteilt (gleich große Typen, gleiche Gewichte), so schrumpft der Abstand der gemischten Signale zweier Typen um den Faktor \((Kh - 1)/(K - 1)\). Er ist 1 bei \(h = 1\) und 0 bei \(h = 1/K\). Bei vollständig zufälligen Kanten liegt \(h\) in dieser Näherung bei \(1/K\); gemessen sind 38 % bei 3 Typen (Mittel über 12 Gebiete), ein wenig mehr, weil die Typen verschieden groß sind (für ein zufälliges Paar ist die Trefferchance \(\sum_t \pi_t^2 \ge 1/K\) mit den Anteilen \(\pi_t\) der Typen).
• Folgerung: Rausch-Gewinn und Signalverlust wirken gegeneinander. Wo sie sich aufheben, sagt diese Rechnung nicht, denn Training, ungleiche Gewichte und das Eigengewicht des Knotens fehlen darin. Die Lage des Kipppunkts ist eine Messung, siehe Befunde.

Das MLP ist der Sonderfall \(\hat A = I\). Dann ist \(H^{(l)} = \mathrm{ReLU}(H^{(l-1)} W^{(l)})\), ein gewöhnliches Netz, das jeden Knoten für sich beurteilt. Gleicher Start und gleiches Training machen jeden Unterschied zum GCN zu einem Effekt von \(\hat A\).

Die Gradienten.

• Schritt 1: Die Ableitung der Kreuzentropie nach den Logits \(Z_i\) ist \(\mathrm{softmax}(Z_i) - Y_i\), geteilt durch \(m\); das ist \(\delta^{(L)}\).
• Schritt 2: Weil \(Z^{(l)}\) linear in \(W^{(l)}\) ist, folgt \((\hat A H^{(l-1)})^\top \delta^{(l)}\), dazu \(\lambda W^{(l)}\) aus dem Gewichtszerfall. Zur vorigen Schicht geht \(\delta^{(l)}\) über \(W^{(l)\top}\) und \(\hat A^\top = \hat A\) zurück, multipliziert mit der ReLU-Ableitung.

Über-Glättung.

• Schritt 1: \(\hat A\) ist symmetrisch. Es ist \(\hat A = I - \tilde L\) mit dem normierten Laplace-Operator \(\tilde L\) des Graphen mit Schleifen; dessen Eigenwerte liegen in \([0, 2)\), denn der Wert 2 tritt nur bei bipartiten Komponenten auf und Schleifen verhindern das. Also liegen die Eigenwerte von \(\hat A\) in \((-1, 1]\). Der Wert 1 gehört zum Eigenvektor \(\tilde D^{1/2}\mathbf 1\): \(\hat A \tilde D^{1/2}\mathbf 1 = \tilde D^{-1/2}\tilde A\mathbf 1 = \tilde D^{-1/2}\tilde d = \tilde D^{1/2}\mathbf 1\).
• Schritt 2: In einem zusammenhängenden Graphen haben alle anderen Eigenwerte einen Betrag kleiner als 1. Dann gilt \(\hat A^k X \to \tilde D^{1/2}\mathbf 1\,\mathbf 1^\top \tilde D^{1/2} X \big/ (\mathbf 1^\top \tilde D\,\mathbf 1)\) für \(k \to \infty\); bei mehreren Zusammenhangskomponenten gilt das je Komponente.
• Schritt 3: Zeile \(i\) des Grenzwerts ist \(\sqrt{\tilde d_i}\) mal ein Zeilenvektor, der für alle Knoten derselbe ist. Alle Knoten haben also dieselbe Richtung, sind aber nicht gleich. Die Streuung der Messreihe (Norm der um ihren Mittelwert verschobenen Merkmalszeilen, relativ zu der der Ausgangsmerkmale; 100 % = unverändert) geht darum nicht gegen 0, sondern gegen einen Rest von wenigen Prozent (am Beispielgebiet nachgerechnet, nicht Teil der Messreihe).
• Schritt 4: Der Abstand zum Grenzwert schrumpft wie \(|\lambda_2|^k\) mit dem größten Betrag \(\lambda_2\) unter den übrigen Eigenwerten. In einem räumlichen Graphen mit großen zusammenhängenden Flächen liegt er knapp unter 1 (am Beispielgebiet nachgerechnet), die Glättung ist also langsam. Deshalb ist die Streuung nach 128 Mischschritten noch deutlich über dem Grenzrest; wie viel davon Rest und wie viel noch nicht abgeklungener Anteil ist, trennt die Messreihe nicht.

Befunde

Genauigkeit ist der Anteil richtig vorhergesagter unbekannter Kunden nach der letzten Epoche. „Raten“ bedeutet, für alle unbekannten Kunden den Gebietstyp vorherzusagen, der in der Prüfmenge am häufigsten ist (ein Orakelwert, der die Prüfetiketten benutzt). Einzelwerte gehören zum Beispielgebiet, Mittelwerte zu den genannten Messreihen. Die „Streuung“ ist die in der Herleitung zur Über-Glättung definierte Kennzahl.

Frage	Befund
Hilft der Graph? (Beispielgebiet)	GCN 88,1 % gegen MLP 68,6 % auf den 185 unbekannten Kunden. 92,4 % der 608 Kanten verbinden Kunden desselben Typs.
Wie stark streuen einzelne Gebiete? (8 Gebiete, übrige Einstellungen wie im Beispielgebiet)	GCN 63 bis 94 %, MLP 40 bis 69 %; der Graph gewinnt in jedem Gebiet. Das Beispielgebiet ist ein typisches, kein bestes Gebiet.
Wie wirkt die Zahl der bekannten Kunden? (Mittel über 12 Gebiete)	2 je Typ: GCN 82,7 % gegen MLP 52,0 %. 20 je Typ: 91,4 % gegen 60,7 %. Der Graph gewinnt bei jeder Etikettenzahl in allen 12 Gebieten, der Abstand bleibt bei etwa 30 Punkten. Im Beispielgebiet mit nur 2 bekannten Kunden je Typ (zusammen 6): 81,4 % gegen 50,0 %.
Verrauschte Merkmale, mehr Typen (Beispielgebiet mit je einer geänderten Einstellung; bei vier Typen zusätzlich dreihundert statt zweihundert Kunden im selben Gebiet)	Rauschregler 3,0: MLP 42,7 % (Raten 41,1 %), GCN 77,3 %. Vier Typen: MLP 32,1 %, schlechter als Raten (33,9 %), GCN 77,5 %.
Was, wenn die Nachbarn nicht stimmen? (Mittel über 12 Gebiete)	Mit wachsendem Anteil ersetzter Kanten sinkt die Homophilie von 91 % auf 38 % und das GCN von 87,9 % auf 46,2 %. Das MLP, das die Kanten nie sieht, bleibt bei 57,8 %. Kipppunkt zwischen Homophilie 59 % (GCN 65,5 %, gewinnt in 9 von 12 Gebieten) und 49 % (GCN 52,9 %, gewinnt in 4 von 12). Im Beispielgebiet mit überwiegend falschen Kanten (Homophilie 46,4 %): GCN 49,7 % gegen MLP 68,6 %; das GCN lernt nicht einmal alle 15 bekannten Etiketten (Trainingsgenauigkeit 80 %).
Reine Glättung ohne Lernen (Mittel über 12 Gebiete)	Nächster-Mittelpunkt-Genauigkeit auf \(\hat A^k X\), Mittelpunkte aus den bekannten Knoten: 62,4 % (\(k = 0\)), 85,6 % (1), 92,0 % (8), 78,0 % (128). Die Streuung der Merkmale schrumpft von 100 % auf 52,7 % (1) und 13,5 % (128).
Trainiertes Netz nach Tiefe (Mittel über 12 Gebiete, 1 bis 8 Schichten)	Kein Einbruch: 84,5 bis 88,7 % in allen Tiefen (1 Schicht 84,5 %, 2 Schichten 87,9 %), Standardfehler des Mittels bis 2,7 Punkte. Im Beispielgebiet 91,9 % mit 8 Schichten gegen 88,1 % mit 2.
Stimmt der Kern?	Gegenproben der Demo: Vorwärtsrechnung gleich einer expliziten Nachbarschleife (2 Schichten), Gradienten gleich zentralen Differenzen (1, 2, 3 Schichten, mit Gewichtszerfall), MLP gleich einem unabhängig geschriebenen MLP, erster Adam-Schritt bewegt jedes Gewicht mit von null verschiedenem Gradienten um die Lernrate, Verlust \(\log K\) bei Nullgewichten, größter Eigenwert 1.

Grenzen und was die Messung zeigt

Was sie belegt: der Vergleich GCN gegen MLP bei gleichem Netz, gleichem Training und gleicher Prüfmenge, getrennt für die genannten Einstellungen. Sie belegt auch die Richtung der Effekte: Der Graph hilft bei stimmigen Kanten in allen gemessenen Gebieten, schadet bei überwiegend falschen Kanten, und die reine Glättung lässt die Zuordnung erst besser und später schlechter werden.

Was sie nicht belegt:

• Reale Netze. Die Daten sind erzeugt: vier Merkmale, Voronoi-Zonen, normalverteiltes Rauschen. Die Zahlen gelten für dieses Vehikel und die genannten Größen.
• Feine Unterschiede. 12 oder 8 Gebiete. Standardfehler des Mittels: bis 2,7 Punkte in der Tiefen-Reihe, beim GCN mit 2 bekannten Kunden je Typ gut 5 (Nachrechnung dieser Seite). Unterschiede von wenigen Punkten, etwa zwischen verschiedenen Tiefen, sind kein Befund. Der Kipppunkt ist nur auf einem groben Raster (Schritte von 20 Prozentpunkten beim Anteil ersetzter Kanten) eingegrenzt.
• Über-Glättung im Netz. Bis 8 Schichten zeigte das trainierte Netz keinen Einbruch. Warum, wurde nicht getrennt gemessen; die Vermutung ist, dass die gelernten Gewichte ausgleichen und der Graph räumlich glatt ist. Der Befund gilt für dieses Gebiet, diese Nachbarzahl und dieses feste Training, nicht für tiefere Netze oder andere Graphen.
• Fester Ablauf. Kein Dropout, kein Early Stopping, keine Validierungsknoten, keine Suche nach besseren Einstellungen: 200 Epochen für alle. Andere Abläufe können andere Abstände ergeben.
• Transduktiv. Der ganze Graph samt der Merkmale der unbekannten Knoten ist beim Training bekannt. Neue Knoten und sehr große Graphen (Stichproben der Nachbarschaft) wurden nicht gemessen.
• Gleich gewichtete Nachbarn. Das Gewicht kommt nur aus den Graden. Ob andere Verfahren falsche Kanten besser abfangen, misst diese Demo nicht (siehe Verweise).
• Mitteln und Reichweite. Dass Mitteln Nachbarschaften mit gleichem Durchschnitt nicht unterscheidet und dass die lokale Nachbarschaft für weit entfernte Information nicht genügt, wird nicht gemessen.

Erweiterungen und Verweise

Weitere Demos dieser Reihe greifen Annahmen des GCN auf; hier steht nur, was ihre Karten über sie sagen:

• Eigenes Gewicht und Stichprobe: GraphSAGE: ein Gewicht für den Kunden, eines für die Nachbarn: trennt das Gewicht des Kunden von dem seiner Nachbarn und zieht im Training nur eine Stichprobe der Nachbarn.
• Aufmerksamkeit: GAT: lernbare Aufmerksamkeit auf Nachbarn: lernt für jeden Nachbarn ein Gewicht aus den Merkmalen, statt alle gleich zu mitteln. GATv2: Aufmerksamkeit, die vom Fragenden abhängt: bewertet die Nachbarn für jeden Fragenden neu.
• Summe statt Mittel: GIN: Summe statt Mittel, Nachbarn zählen: summiert die Nachbarn und zählt so mit, wie viele es sind.
• Ganzes Netz: Graph Transformer: Aufmerksamkeit über das ganze Netz: achtet auf alle Kunden statt nur auf die Nachbarn.

Quellen

• Kipf, Welling (2017): Semi-supervised classification with graph convolutional networks. ICLR.
• Li, Han, Wu (2018): Deeper insights into graph convolutional networks for semi-supervised learning. AAAI (zur Über-Glättung).
• Quelltext, Messreihen und Gegenproben der Demo: github.com/sebastian-hanisch/gcn-demo.

Kipf und Welling (2017) sind als Literatur in der README der Demo genannt und für diese Seite nicht nachgeschlagen. Li, Han und Wu (2018) stehen nicht in der README und sind aus dem Gedächtnis genannt, nicht geprüft. Der Pfad aus drei Knoten (Zahlen aus der Handrechnung der Demo), die Rauschrechnung und die Grenzwertrechnung sind Rechnungen dieser Seite und keine Messungen.