🤖 machine learning

Understanding Truncated Positional Encodings for Graph Neural Networks

Diese Arbeit untersucht die theoretischen und empirischen Auswirkungen der Verwendung trunkierter Positionskodierungen in Graph Neural Networks und zeigt auf, dass eine solche Trunkierung die Ausdrucksstärke verschiedener Kodierungsfamilien grundlegend verändert – indem sie spektrale Varianten nicht stärker als den 1-WL-Test macht – und demonstriert, dass die Kombination mehrerer trunkierter Kodierungen auf realen Datensätzen besser abschneidet als die Verwendung einer einzelnen Familie.

Ursprüngliche Autoren: James Flora, Mitchell Black, Weng-Keen Wong, Amir Nayyeri

Veröffentlicht 2026-06-12

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: James Flora, Mitchell Black, Weng-Keen Wong, Amir Nayyeri

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, einem Roboter beizubringen, den Grundriss einer Stadt zu verstehen. Der Roboter ist ein Graph Neural Network (GNN), und die Stadt ist ein Graph, der aus Kreuzungen (Knoten) und Straßen (Kanten) besteht.

Um einen guten Job zu machen, benötigt der Roboter mehr als nur eine Liste darüber, welche Straßen miteinander verbunden sind. Er benötigt Positionskodierungen (Positional Encodings, PEs). Denken Sie an PEs als eine Art „Karte“ oder „Kompass“, der dem Roboter sagt, wo sich jede Kreuzung im Verhältnis zu allen anderen befindet. Ohne diese Karte ist der Roboter wie ein Mensch, der durch eine Stadt läuft, während er die Augen geschlossen hat – er weiß zwar, wer direkt neben ihm steht, hat aber keine Vorstellung davon, ob er sich in der Nähe des Stadtzentrums befindet oder in einer Sackgasse feststeckt.

Das Problem: Die „perfekte“ Karte ist zu schwerfällig

Es gibt zwei Hauptwege, um diese perfekte Karte zu erstellen:

Die Spektrale Karte: Diese nutzt komplexe Mathematik (Eigenwerte und Eigenvektoren), um die „Vibrationen“ oder die globale Form der Stadt zu erfassen.
Die Walk-Karte: Diese zählt, wie viele Wege man von einem Punkt zum anderen in 1 Schritt, 2 Schritten, 3 Schritten und so weiter gehen kann.

Mathematisch gesehen, wenn man die vollständige Karte verwendet (alle Schritte, alle Vibrationen), sind diese beiden Methoden gleichermaßen leistungsstark. Sie können fast jede zwei unterschiedlichen Stadtlayouts unterscheiden.

Es gibt jedoch einen Haken: Das Erstellen dieser „vollständigen“ Karte für eine große Stadt erfordert eine massive Menge an Rechenleistung und Speicherplatz (speziell wird es exponentiell schwieriger, je größer die Stadt wächst). Es ist, als würde man versuchen, eine Bibliothek mit jeder möglichen Weltkarte in seinem Rucksack zu tragen. Das ist für den realen Einsatz viel zu schwerfällig.

Deshalb verwenden Ingenieure Trunkierte Positionskodierungen (Truncated Positional Encodings). Anstatt die ganze Bibliothek zu nehmen, nimmt man nur die ersten paar Kapitel.

Trunkierte Spektrale Kodierung: Nur die ersten paar „Vibrationen“ (Eigenvektoren).
Trunkierte Walk-Kodierung: Nur die ersten paar Gehschritte (Potenzen der Adjazenzmatrix).

Die große Frage, die das Paper stellt, lautet: Wenn wir das Ende dieser Karten abschneiden, funktionieren sie dann noch auf die gleiche Weise?

Die große Entdeckung: Das „Schneiden“ verändert alles

Die Autoren fanden eine überraschende Antwort: Nein, sie funktionieren nicht mehr auf die gleiche Weise.

Wenn man die vollständige Karte hat, sind die spektralen und die Walk-Methoden wie Zwillinge. Aber wenn man sie trunkiert (abschneidet), werden sie zu sehr unterschiedlichen Geschwistern mit verschiedenen Stärken und Schwächen.

Die „Trunkierte Spektrale“ Falle: Manchmal führt die Verwendung der ersten paar Vibrationen dazu, dass der Roboter die Stadt sogar schlechter versteht, als wenn er gar keine Karte hätte! In einigen Fällen ist eine trunkierte spektrale Karte so schwach, dass sie nicht einmal den Unterschied zwischen zwei Städten erkennen kann, den ein sehr einfacher „Nachbarschafts-Check“ (ein sogenannter 1-WL-Test) problemlos feststellen würde.
Die „Trunkierte Walk“ Falle: Umgekehrt gibt es Stadtlayouts, die eine trunkierte Walk-Karte (die nur wenige Schritte zählt) völlig übersieht, die eine trunkierte spektrale Karte jedoch sofort erkennt.

Die Analogie: Stellen Sie sich vor, Sie versuchen, eine Person zu identifizieren.

Die Vollständige Spektrale Karte ist wie das Wissen über ihre gesamte DNA und ihre Lebensgeschichte.
Die Trunkierte Spektrale Karte ist wie das Wissen nur über ihre Körpergröße.
Die Trunkierte Walk-Karte ist wie das Wissen, wie viele Schritte es braucht, um von ihrem Haus zum Supermarkt zu laufen.

Wenn man nur die Körpergröße kennt (Trunkierte Spektrale Karte), könnte man zwei Menschen gleicher Größe verwechseln. Wenn man nur die Gehdistanz kennt (Trunkierte Walk-Karte), könnte man zwei Personen verwechseln, die gleich weit vom Laden entfernt wohnen. Aber wenn man beides nutzt, bekommt man ein viel besseres Bild.

Der neue Held: „Harmonische Distanzen“

Das Paper führt eine neue Familie von Karten ein, die k-harmonische Distanzen genannt werden.

Denken Sie an den Effektiven Widerstand (eine Art 1-harmonische Distanz) als ein Maß dafür, wie „verbunden“ zwei Punkte sind, ähnlich wie viel Elektrizität zwischen ihnen fließt.
Das Paper zeigt, dass die Biharmonische Distanz (2-harmonisch) etwas anderes misst: wie „zentral“ oder wichtig eine Straße für die gesamte Stadt ist.

Die Autoren beweisen, dass diese neuen Karten zwar leistungsstark sind, aber auch Grenzen haben. Wenn man nur die „Widerstands“-Karte verwendet, übersieht man vielleicht Details, die die „biharmonische“ Karte erfasst, und umgekehrt. Wenn man jedoch genug dieser harmonischen Karten verwendet, kann man die Kraft der schweren, vollständigen Karten rekonstruieren.

Der praktische Rat: „Mix und Match“

Da keine einzelne Art von trunkierter Karte perfekt ist, schlagen die Autoren eine einfache Faustregel für Ingenieure vor: Verlassen Sie sich nicht nur auf eine Art von trunkierter Karte.

Stattdessen: Mischen Sie sie zusammen.

Kombinieren Sie ein paar Schritte der „Walk“-Karte.
Kombinieren Sie ein paar „Vibrationen“ der „Spektralen“ Karte.
Werfen Sie eine „Harmonische“ Distanz oder zwei mit hinein.

Das Experiment:
Die Autoren haben dies auf realen Datensätzen getestet (wie etwa die Vorhersage chemischer Eigenschaften von Molekülen).

Die Verwendung von nur einer Art von trunkierter Karte war okay.
Die Verwendung einer Mischung aus verschiedenen Arten von trunkierten Karten war signifikant besser.

Es ist wie die Navigation durch eine Stadt: Einen Kompass (Spektral), einen Schrittzähler (Walk) und ein Maß für den Verkehrsfluss (Harmonisch) gleichzeitig zu haben, ist viel besser, als sich nur auf eines davon zu verlassen.

Zusammenfassung

Volle Karten sind zu schwerfällig für den realen Einsatz, daher verwenden wir „trunkierte“ (abgeschnittene) Versionen.
Das Abschneiden bricht die Gleichheit: Trunkierte spektrale und Walk-Karten sind nicht mehr gleich; sie haben unterschiedliche blinde Flecken.
Manche Schnitte sind schlechter als gar keine Karte: In einigen Fällen ist eine trunkierte spektrale Karte schwächer als ein sehr einfacher Test.
Die Lösung: Wählen Sie nicht nur eines. Mischen Sie verschiedene Arten von trunkierten Karten, um die beste Leistung ohne die hohen Rechenkosten zu erzielen.

Technisches Resümee: Verständnis trunkierter Positionskodierungen für Graph Neural Networks

Problemstellung

Graph Neural Networks (GNNs), insbesondere Message Passing Neural Networks (MPNNs), sind fundamental in ihrer Fähigkeit eingeschränkt, globale strukturelle Informationen zu erfassen – eine Einschränkung, die durch ihre Äquivalenz zum 1-Weisfeiler-Lehman-Test (1-WL) formalisiert wird. Um dies zu überwinden, nutzen Graph Transformer (GTs) und verbesserte GNNs Positionskodierungen (Positional Encodings, PEs), um strukturelle Informationen zu injizieren. Es gibt zwei dominante Familien von PEs: Spektralkodierungen (abgeleitet aus den Eigenräumen der Laplace-Matrix) und gangbasierte Kodierungen (abgeleitet aus Potenzen der Adjazenzmatrix).

Theoretisch sind vollständige Versionen dieser Kodierungen (unter Verwendung von $\Omega(n)$ Eigenvektoren oder Matrixpotenzen) in ihrer Ausdrucksstärke äquivalent und liegen zwischen dem 1-WL- und dem 3-WL-Test. Die Berechnung dieser vollständigen Kodierungen erfordert jedoch eine Zeit- und Platzkomplexität von $O(n^3)$ , was für reale Anwendungen prohibitiv ist. Infolgedessen verlassen sich Praktiker auf trunkierte Varianten (z. B. die ersten $k$ Eigenvektoren oder die ersten $k$ Potenzen der Adjazenzmatrix). Die theoretischen Eigenschaften, die Ausdrucksstärke und die vergleichenden Stärken dieser trunkierten PEs sind weitgehend ungeklärt, wodurch eine Lücke zwischen theoretischen Garantien und praktischer Implementierung entsteht.

Methodik

Die Autoren initiieren eine systematische Untersuchung trunkierter PEs durch sowohl theoretische Analyse als auch empirische Validierung.

Theoretischer Rahmen

Das Paper nutzt die WL-Hierarchie und deren Varianten, um die Ausdrucksstärke verschiedener PEs zu charakterisieren:

$\psi$ -WL-Test: Eine Variante des WL-Tests, bei dem Knotenfarben unter Verwendung einer relativen Positionskodierung (RPE) $\psi$ aktualisiert werden.
Sparse- $\psi$ -WL-Test: Eine Erweiterung für MPNNs, bei der $\psi$ als Edge-Feature verwendet wird.
Analysierte Schlüsselfamilien:
1. Trunkierte Eigenraumprojektionen ( $k$ -EP-WL): Verwendung der ersten $k$ Eigenraumprojektionen der Laplace-Matrix.
2. Trunkierte Gang-Kodierungen ( $k$ -Walk-WL): Verwendung der ersten $k$ Potenzen der Adjazenzmatrix.
3. Effektiver Widerstand (Resistance-WL): Eine spezifische spektrale Distanz (1-harmonische Distanz).
4. $k$ -harmonische Distanzen: Eine Verallgemeinerung des effektiven Widerstands, definiert als $H_k(u, v) = \sqrt{(1_u - 1_v)^T (L^+)^k (1_u - 1_v)}$ .

Die Autoren konstruieren spezifische Graphpaare (z. B. Produkte von Pfadgraphen und vollständigen Graphen oder Zyklen vs. disjunkte Vereinigungen von Zyklen), um die Separabilität oder Ununterscheidbarkeit unter verschiedenen trunkierten PEs und WL-Tests zu beweisen.

Empirische Evaluierung

Experimente wurden auf drei Benchmarks durchgeführt:

BREC: Ein Datensatz, der darauf ausgelegt ist, die "realisierte Ausdrucksstärke" von GNNs zu messen, indem die Fähigkeit getestet wird, nicht-isomorphe Graphen zu unterscheiden, die zwischen 1-WL und 4-WL ununterscheidbar sind.
ZINC-12k: Ein Graph-Regressions-Benchmark für molekulare Löslichkeit, der verwendet wird, um die Hypothese zu testen, dass das Mischen trunkierter PEs die Leistung verbessert.
ogbg-molhiv: Ein binärer Klassifikations-Benchmark für die HIV-Inhibition.

Die Autoren evaluierten Graphormer-GD-Architekturen und MPNNs (GINE) unter Verwendung verschiedener Kombinationen von trunkierten PEs, einschließlich einzelner Familien sowie Mischungen aus Spektral-, Gang- und $k$ -harmonischen Kodierungen.

Zentrale Beiträge und Ergebnisse

1. Divergenz der Ausdrucksstärke in trunkierten Formen

Das Paper beweist, dass vollständige Spektral- und Gang-Kodierungen zwar äquivalent sind, ihre trunkierten Formen jedoch fundamental verschieden sind:

Trunkierte Spektralkodierung vs. 1-WL: Die Autoren zeigen, dass trunkierte Eigenraumprojektionen ( $k$ -EP-WL) schwächer als der 1-WL-Test sein können. Konkret existieren Graphpaare, die durch 1-WL unterscheidbar, aber durch $k$ -EP-WL für $k \in \Omega(n)$ ununterscheidbar sind (Theorem 4.1).
Trunkierte Gang-Kodierung vs. Spektralkodierung: Umgekehrt existieren Graphpaare, die durch eine einzige Eigenraumprojektion (1-EP-WL) unterscheidbar, aber durch $\Omega(n)$ -große Gang-Kodierungen ununterscheidbar sind (Theorem 4.2).
Implikation: Keine einzelne Familie trunkierter PEs ist strikt überlegen; sie erfassen unterschiedliche strukturelle Aspekte und können mit der Standard-WL-Hierarchie nicht vergleichbar sein.

2. Limitationen des effektiven Widerstands

Das Paper analysiert den effektiven Widerstand (1-harmonische Distanz) und stellt fest, dass dieser auf gewichteten Graphen eine schwächere PE als vollständige Eigenraum- oder Gang-Kodierungen ist.

Theorem 4.3: Es existieren gewichtete Graphe, die durch Resistance-WL ununterscheidbar, aber durch Adjacency-WL (und damit durch 1-WL auf ungewichteten Graphen) unterscheidbar sind.
Korollar 4.1: Resistance-WL kodiert nicht das gesamte Spektrum des Graphen, was eine frühere Vermutung widerlegt.

3. $k$ -harmonische Distanzen als Brücke

Die Autoren führen $k$ -harmonische Distanzen als natürliche Brücke zwischen Spektral- und Polynomial-Kodierungen ein.

Vollständigkeit: Die Konkatenierung von $\Theta(n)$ $k$ -harmonischen Distanzen ergibt eine Kodierung, die in ihrer Kraft äquivalent zu vollständigen Spektral- oder Gang-Kodierungen ist (Theorem 4.6).
Differenzielle Leistung: Selbst innerhalb der $k$ -harmonischen Familie unterscheiden sich fixierte Größen. Beispielsweise kann die biharmonische Distanz (2-harmonische Distanz) bestimmte Baum-Paare in einer konstanten Anzahl von Iterationen unterscheiden, während der effektive Widerstand (1-harmonische Distanz) $O(n)$ Iterationen benötigt (Theorem 4.7).
Robustheit: Wenn jedoch eine $k$ -harmonische Distanz ein Paar von Graphen unterscheidet, werden die meisten anderen $k$ -harmonischen Distanzen sie ebenfalls unterscheiden (Theorem 4.8).

4. Empirische Befunde: Die Kraft des Mischens

BREC-Ergebnisse: $k$ -harmonische Distanzen erzielten kompetitive Ergebnisse mit Single-Channel-Kodierungen mit geringem Overhead und erreichten oft das theoretische Limit für Graphen zwischen 1-WL und 3-WL.
ZINC-Ergebnisse: Die signifikanteste Erkenntnis ist, dass das Mischen von PEs aus verschiedenen Familien (z. B. die Kombination von trunkierten Gang-Kodierungen und $k$ -harmonischen Distanzen) die Leistung jeder einzelnen Familie übertrifft. Eine Mischung aus trunkierten Gang-Kodierungen und $k$ -harmonischen Distanzen erreichte den niedrigsten mittleren absoluten Fehler (MAE) auf ZINC-12k und übertraf damit die Single-Family-Baselines.
Effizienz: Das Paper stellt fest, dass $k$ -harmonische Distanzen in $O(mk \cdot \text{poly}(\log n))$ Zeit mithilfe schneller Laplacen-Solver und Johnson-Lindenstrauss-Projektionen approximiert werden können, wodurch die $O(n^3)$ -Kosten einer exakten Berechnung vermieden werden.

Bedeutung und Ansprüche

Das Paper beansprucht, die theoretische Untersuchung trunkierter Positionskodierungen initiiert zu haben, indem es die Perspektive verschiebt: Weg von der bloßen Betrachtung als Approximation vollständiger Kodierungen, hin zur Betrachtung als ein distinkter Designraum mit einzigartigen Ausdruckseigenschaften.

Theoretische Einsicht: Die Arbeit zeigt, dass die Trunkierung die erfassten Informationen fundamental verändert, was sie in spezifischen Fällen unvergleichbar mit der Standard-WL-Hierarchie macht.
Praktische Orientierung: Die Autoren schlagen eine Faustregel vor: Mischen Sie PEs aus verschiedenen Familien, wenn Sie trunkierte Kodierungen verwenden. Dieser Ansatz erfasst komplementäre strukturelle Hinweise bei gleichzeitiger Kontrolle der Rechenkosten.
Moderater Umfang: Die Autoren räumen ein, dass die Graph-Isomorphie zwar ein prinzipieller Stellvertreter ist, reale Aufgaben jedoch Downstream-Signale (Zentralität, Motive) beinhalten, die nicht strikt mit Isomorphie-Tests übereinstimmen müssen. Daher ist der primäre Beitrag die Etablierung einer theoretischen Grundlage und eines Ausgangspunkts für eine systematische empirische Untersuchung, nicht der Anspruch einer universellen Lösung für alle Aufgaben des Graph-Learnings.