🤖 machine learning

Neural Message Passing on Structural Interaction Graphs for Fully-Inductive Graph Neural Networks

Dieses Paper stellt SIGIL vor, ein voll induktives Framework, das die Input-Heterogenität in Graph-Foundation-Modellen überwindet, indem es beliebige attribuierte Graphen auf einen einheitlichen strukturellen Interaktionsgraphen abbildet, wodurch der Transfer gelernter Merkmalsrepräsentationen über diverse Graphen hinweg ermöglicht und bestehende Ansätze des Knowledge-Graph-Reasoning vereinheitlicht wird.

Ursprüngliche Autoren: Omer Yom Tov, Avigdor Gal

Veröffentlicht 2026-08-11

📖 3 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Omer Yom Tov, Avigdor Gal

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, die Welt zu verstehen. In der Welt des Textes haben wir ein riesiges Wörterbuch mit Wörtern, auf die sich alle geeinigt haben; sobald der Roboter lernt, was „Katze“ oder „laufen“ bedeutet, kann er ein neues Buch über Katzen oder das Laufen lesen, ohne eine neue Lektion zu benötigen. Aber in der Welt der Graphen – Netzwerke aus verbundenen Dingen wie Social-Media-Freunden, chemischen Molekülen oder Zitationsnetzwerken – gibt es kein universelles Wörterbuch. Jeder Graph bringt seine eigenen, einzigartigen „Merkmale“ mit (wie etwa die spezifischen Attribute einer Person oder eines Moleküls), die sich vom nächsten völlig unterscheiden können. Ein Modell, das darauf trainiert wurde, ein Netzwerk von Wissenschaftlern zu verstehen, könnte völlig verwirrt sein, wenn man ihm ein Netzwerk von Online-Shoppern überreicht, weil die „Wörter“ (Merkmale) nicht übereinstimmen. Dies macht es unglaublich schwierig, ein einziges, intelligentes „Fundamentmodell“ zu bauen, das von einem Netzwerktyp zum anderen springen kann, ohne jedes Mal von Grund auf neu trainiert werden zu müssen. Die große Frage, die sich Forscher stellen, lautet: Können wir einen universellen Übersetzer für diese chaotischen, unterschiedlichen Netzwerke bauen, der überall und für alles funktioniert, ohne für jeden einzelnen neuen Auftrag ein Wörterbuch zu benötigen?

Dieses Paper stellt einen cleveren neuen Rahmen namens Sigil (was für Structural Interaction Graphs for Inductive Learning steht) vor, um genau dieses Problem zu lösen. Betrachten Sie Sigil als einen Meisterkoch, dem es egal ist, welche Zutaten Sie ihm reichen (ob Äpfel, Karotten oder außerirdische Früchte). Anstatt zu versuchen, jede mögliche Zutat auswendig zu lernen, schaut Sigil darauf, wie die Zutaten miteinander interagieren. Es nimmt einen chaotischen, komplexen Netzwerk und hebt es auf eine neue, vereinfachte Ebene, einen sogenannten „Structural Interaction Graph“ (SIG). In dieser neuen Sichtweise sind die „Knoten“ nicht mehr die Menschen oder Moleküle; sie sind die Merkmale selbst (wie „Größe“, „Preis“ oder „Farbe“). Die Verbindungen in diesem neuen Graphen zeigen, wie diese Merkmale dazu neigen, basierend auf der ursprünglichen Vernetzung des Netzwerks, miteinander zu korrelieren oder zu kollidieren.

Indem Sigil ein spezielles Message-Passing-Spiel auf dieser Feature-Map durchführt, lernt es eine universelle Sprache für Merkmale. Es übersetzt jeden Graphen, egal wie seltsam oder unterschiedlich seine Merkmale sind, in ein standardisiertes, fest definiertes Format, das eine nachgeschaltete KI leicht verstehen kann. Das Paper zeigt, dass dies nicht nur ein neuer Trick ist, sondern eine vereinheitlichende Theorie. Wenn die Merkmale einfache „One-Hot“-Codes sind (wie diskrete Beziehungstypen in einem Wissensgraphen), stellt Sigil perfekt bestehende leistungsstarke Modelle wieder her. Aber wenn die Merkmale kontinuierliche Zahlen sind (wie reelle Sensordaten), geht Sigil dorthin, wo diese alten Modelle nicht hinkommen konnten. Die Autoren haben dies bei einer Vielzahl von Aufgaben getestet, einschließlich der Vorhersage fehlender Verbindungen in Netzwerken und der Klassifizierung von Knoten. Sie fanden heraus, dass ein einziges Sigil-Modell, das nur auf einem einzigen Graphen (wie dem Cora-Zitationsnetzwerk) trainiert wurde, auf völlig ungesehenen Graphen mit anderen Merkmalen erstaunlich gut abschneiden konnte und oft andere „voll induktive“ Modelle schlug, die versuchen zu generalisieren. Es ist, als würde man einem Schüler beibringen, ein Buch zu lesen, und er besteht dann eine Prüfung über ein Buch, das in einer völlig anderen Sprache geschrieben wurde, einfach weil er die zugrunde liegende Grammatik der Verbindung von Ideen gelernt hat, anstatt die Wörter auswendig zu lernen.

Technisches Resümee: Neuronale Nachrichtenübertragung auf strukturellen Interaktionsgraphen für voll-induktive Graph-neuronale Netzwerke

1. Problemstellung

Die Entwicklung von Graph-Foundation-Modellen (GFMs) steht vor einem zentralen Hindernis: der Input-Heterogenität. Im Gegensatz zur natürlichen Sprache, in der ein gemeinsames Token-Vokabular Modellen erlaubt, jeglichen Text zu kodieren, kommen Graphen mit einzigartigen Knoten-Merkmalsräumen an, die sich in Dimensionalität, Koordinatensemantik und Label-Sätzen unterscheiden. Folglich kann ein Modell, das auf einem Graphen trainiert wurde, im Allgemeinen keinen anderen „lesen“.

Bestehende Ansätze adressieren Teile dieser Herausforderung, scheitern jedoch an deren Vereinigung:

Knotenklassifikations-GFMs: Methoden wie GraphAny handhaben beliebige Feature- und Labelräume, sind jedoch ausschließlich für die Knotenklassifikation konzipiert und verfügen über keine Mechanismen für Link-Vorhersage oder relationales Schließen.
Wissensgraph-Foundation-Modelle (KGFMs): Modelle wie ULTRA erreichen Zero-Shot-Transfer auf Wissensgraphen durch Konstruktion eines „Relationsgraphen“ über diskrete Relationstypen. Dieser Ansatz ist jedoch fundamental diskret; er setzt ein endliches Vokabular von Relationen voraus und besitzt keine Mechanismen für kontinuierliche Knoten- oder Kantenmerkmale.

Die Kernherausforderung besteht darin, ein voll-induktives Graphmodell zu entwerfen, das gleichzeitig über drei Achsen generalisiert: ungesehene Graphstrukturen, ungesehene Merkmalsräume (beliebige Dimensionalität und Semantik) sowie ungesehene Labelräume.

2. Methodik: Das Sigil-Framework

Die Autoren schlagen Sigil (Structural Interaction Graphs for Inductive Learning) vor, ein Framework, das jeden attributierten Graphen auf einen vereinheitlichten, festdimensionalen Repräsentationsraum abbildet. Die zentrale Innovation ist der Strukturelle Interaktionsgraph (SIG).

2.1 Konstruktion des Strukturellen Interaktionsgraphen (SIG)

Gegeben sei ein Eingabegraph $G=(V, E)$ mit Knotenmerkmalen $X \in \mathbb{R}^{n \times d}$ . Sigil „hebt“ den Graphen vom Knotenbereich in den Merkmalsdimensionsbereich an.

Multi-Order-Propagation: Merkmale werden über zunehmende Nachbarschaftsordnungen $k$ (von $0$ bis $K$ ) mittels nicht-parametrisierter Propagation propagiert: $X^{(k)} = A^k X$ .
Interaktionsoperatoren: Für jede Ordnung $k$ wird ein Interaktionsoperator $g$ (z. B. Subtraktion oder elementweise Multiplikation) auf die Merkmale benachbarter Knoten angewendet, um Kantenmerkmale zu erzeugen.
Rollen-Aggregation: Diese Kantenmerkmale werden zurück zu den Knoten aggregiert, getrennt nach Rollen (Head/Tail für gerichtete Graphen), wodurch Zusammenfassungsmatrizen $\bar{X}^{(k)}_h$ und $\bar{X}^{(k)}_t$ entstehen. Diese Matrizen charakterisieren, wie Merkmalswerte über lokale Nachbarschaften hinweg instanziieren.
Gram-Matrix-Konstruktion: Die Ausrichtung zwischen den Merkmalsdimensionen wird durch die Berechnung von Gram-Matrizen (Skalarprodukte) dieser Zusammenfassungsvektoren erfasst: $\bar{A}^{(k)} = (\bar{X}^{(k)})^\top \bar{X}^{(k)}$ .
Der SIG: Die resultierenden Matrizen $\bar{A}^{(k)}$ $\overset{ˉ}{A}^{(k)}$ bilden einen Strukturellen Interaktionsgraphen $G_{struct}$ $G_{s t r u c t}$ . In diesem Graphen:
- Sind die Knoten die Eingangs-Merkmalsdimensionen $[d]$ .
- Sind die Kanten gewichtet und typisiert, wobei sie kodieren, wie Paare von Merkmalen über verschiedene Ordnungen der Konnektivität hinweg korrelieren.
- Für gerichtete Graphen ergibt die Konstruktion pro Ordnung vier Slices (head-head, tail-tail, head-tail, tail-head), welche die gerichteten Interaktionen erfassen.

2.2 Lernen von Repräsentationen via Relationaler Nachrichtenübertragung

Sobald der SIG konstruiert ist, operiert ein Relationales Nachrichtenübertragungs-Netzwerk (RMPNN) auf ihm:

Embedding: Das RMPNN bettet jede Merkmalsdimension $f \in [d]$ in einen festen verborgenen Raum $d_h$ ein.
Transformation: Die gelernten Merkmals-Embeddings $\Theta^{(T)} \in \mathbb{R}^{d \times d_h}$ werden verwendet, um die ursprünglichen Knotenmerkmale jedes beliebigen Graphen in eine vereinheitlichte Repräsentation zu transformieren: $H = X \Theta^{(T)}$ .
Induktive Eigenschaft: Da die Parameter des RMPNN nur auf die feste verborgene Breite $d_h$ wirken und niemals auf die Eingangsdimension $d$ , kann ein einzelnes trainiertes Sigil-Modell Graphen mit beliebigen Merkmalsdimensionalitäten verarbeiten.

2.3 Downstream-Aufgaben

Link-Vorhersage: Die vereinheitlichten Knotenrepräsentationen werden in expressive Link-Vorhersage-GNNs (z. B. NBFNet) eingespeist, um Zero-Shot-Inferenz durchzuführen.
Knotenklassifikation: Die vereinheitlichten Repräsentationen dienen als Input für einen nachgeschalteten Decoder (z. B. ein leichtgewichtiges MLP oder eine geschlossene analytische Lösung), um Labels vorherzusagen.

3. Wichtige Beiträge und theoretische Eigenschaften

3.1 Strikte Generalisierung von KGFMs

Das Paper beweist, dass Sigil eine strikte Generalisierung bestehender Wissensgraph-Foundation-Modelle (wie ULTRA) darstellt.

Theorem 1: Wenn die Eingangsmerkmale One-Hot-Indikatoren diskreter Relationen sind, rekonstruiert die SIG-Konstruktion exakt den Relationsgraphen, der von KGFMs verwendet wird.
Erweiterung: Im Gegensatz zu KGFMs akzeptiert Sigil kontinuierliche Merkmale. Die Gram-Matrizen werden zu kontinuierlichen Merkmals-Ausrichtungsmatrizen statt zu ganzzahligen Ko-Okkurrenz-Zählungen. Zudem kodiert die Multi-Order-Propagation von Sigil höherwertige Interaktionen zwischen Merkmalen, die KGFMs (beschränkt auf Single-Hop-Motive) entgehen.

3.2 Symmetrie und Äquivarianz

Sigil erfüllt die Symmetrien, die für eine voll-induktive Generalisierung erforderlich sind:

Knoten-Permutations-Äquivarianz: Die resultierenden Knotenrepräsentationen sind äquivariant gegenüber Permutationen der Eingangsknoten.
Merkmals-Permutations-Invarianz: Die vereinheitlichte Repräsentation ist invariant gegenüber der Ordnung oder Identität der Eingangs-Merkmalsdimensionen. Dies ermöglicht es dem Modell, Graphen mit Merkmalsräumen zu lesen, die es noch nie gesehen hat.
Label-Permutations-Äquivarianz: In Kombination mit einem äquivarianten Decoder respektiert das Modell Label-Permutationen.

4. Experimentelle Ergebnisse

Die Autoren evaluieren Sigil über drei Regime hinweg, wobei ein einziges Modell auf dem Cora-Datensatz (für Link-Vorhersage und Knotenklassifikation) oder einer Mischung aus Wissensgraphen (für KG-Reasoning) vortrainiert wurde.

4.1 Link-Vorhersage (Kontinuierliche Merkmale)

Evaluierung auf 11 Benchmarks (7 attributiert, 4 nicht-attributiert).

Attributierte Graphen: Sigil-lp ist die stärkste voll-induktive Methode auf jedem Datensatz und übertrifft Baselines wie UniLP und TFMLinker. Bemerkenswert ist, dass es UniLP auf Datensätzen wie CiteSeer und AmazonPhotos signifikant übertrifft, was zeigt, dass die Nutzung von Merkmalsräumen via SIG überlegen ist gegenüber dem Verwerfen derselben.
Nicht-attributierte Graphen: Sigil-lp bleibt wettbewerbsfähig, belegt den zweiten Platz unter den voll-induktiven Methoden und zeigt eine hohe Stabilität.
Effizienz: Sigil-lp schließt die Inferenz in Minuten ab, während In-Context-Baselines wie UniLP Zeitbudgets von über 24 Stunden überschreiten.

4.2 Wissensgraph-Reasoning

Evaluierung auf dem ULTRA-Benchmark (induktive Settings mit ungesehenen Entitäten und Relationen).

Reproduktion: Sigil(0) (Order-0 SIG) reproduziert die Leistung von ULTRA innerhalb einer geringen Marge (z. B. exakte Übereinstimmung des MRR auf Pretraining-Graphen).
Expressivität: Höherwertige SIGs (Sigil(1), Sigil(2)) zeigen eine variable Leistung je nach Datensatz, was darauf hindeutet, dass höhere Interaktionen zwar die Expressivität erhöhen, aber nicht einheitlich die Leistung über alle Aufgaben hinweg verbessern.

4.3 Knotenklassifikation

Evaluierung auf 26 Benchmarks mit variierenden Merkmalsdimensionen und Klassenzahlen.

Leistung: Sigil-nc ist wettbewerbsfähig und belegt den ersten oder zweiten Platz bei 10 von 26 Datensätzen. Es fällt hinter spezialisierten Modellen wie RGVT und TAG (die für spezifische Aufgaben optimiert sind) zurück, übertrifft aber GraphAny und TS-MEAN.
Analyse: Die Autoren führen die Leistungslücke auf die „Kosten der Vereinheitlichung“ zurück: Die Komprimierung beliebiger Merkmalsräume in eine feste Dimension $d_h$ macht die ursprünglichen Koordinaten für den Decoder unzugänglich, was mehr Supervision erfordert. Dennoch bestätigen die Ergebnisse, dass das Lernen auf SIGs ein valider Ansatz für Knotenklassifikations-Foundation-Modelle ist.

5. Bedeutung und Behauptungen

Das Paper behauptet, dass Sigil mehrere zuvor getrennte Regime im Design von Graph-Foundation-Modellen vereinigt:

Vereinigung: Es schließt die Lücke zwischen Knotenklassifikations-GFMs (die beliebige Merkmale handhaben) und KGFMs (die relationales Schließen handhaben) und bietet einen einzigen Mechanismus für beide.
Transferierbarkeit: Es demonstriert, dass ein einziges Modell, das auf einem Graphen trainiert wurde, eine starke Zero-Shot-Leistung auf Graphen mit völlig unterschiedlichen Merkmalsräumen und Strukturen liefern kann.
Generalisierung: Durch die Formalisierung des Relationsgraphen als diskretes Instanz eines Strukturellen Interaktionsgraphen liefert die Arbeit ein theoretisches Fundament für die Erweiterung des relationalen Schließens auf kontinuierliche Eingangsräume.

Die Autoren kommen zu dem Schluss, dass Transferierbarkeit, relationales Schließen und Kanten-Level-Aufgaben aus einem einzigen Mechanismus (SIG-Konstruktion und Nachrichtenübertragung) entstehen können, anstatt separate Designs für verschiedene Graphentypen zu erfordern. Als zukünftige Arbeit wird die Verfeinerung von Architekturen zum Lernen auf SIGs sowie die Untersuchung ihrer Ausdrucksstärke vorgeschlagen.