Technische Samenvatting: Neurale Message Passing op Structurele Interactiegrafen voor Volledig-Inductieve Graph Neural Networks

1. Probleemstelling

De ontwikkeling van Graph Foundation Models (GFMs) staat voor een centraal obstakel: input-heterogeniteit. In tegenstelling tot natuurlijke taal, waar een gedeelde token-vocabulaire modellen in staat stelt om elke tekst te coderen, komen grafen voor met unieke node-feature-ruimtes die verschillen in dimensionaliteit, coördinatensemantiek en labelsets. Bij consequent kan een model dat getraind is op de ene graaf, de andere graaf niet "lezen".

Bestaande benaderingen pakken delen van deze uitdaging aan, maar slagen er niet in deze te verenigen:

• Node Classificatie GFMs: Methoden zoals GraphAny gaan om met willekeurige feature- en labelruimtes, maar zijn uitsluitend ontworpen voor node classificatie en missen mechanismen voor link voorspelling of relationele redenering.
• Knowledge Graph Foundation Models (KGFMs): Modellen zoals ULTRA bereiken zero-shot transfer op kennisgrafen door een "relatie-graaf" te construeren over discrete relatietypes. Dit proces is echter fundamenteel discreet; het veronderstelt een eindige vocabulaire van relaties en mist mechanismen voor continue node- of edge-features.

De kernuitdaging is het ontwerpen van een volledig-inductief graafmodel dat gelijktijdig generaliseert over drie assen: ongeziene grafenstructuren, ongeziene feature-ruimtes (willekeurige dimensionaliteit en semantiek) en ongeziene labelruimtes.

2. Methodologie: Het Sigil-framework

De auteurs stellen Sigil (Structural Interaction Graphs for Inductive Learning) voor, een framework dat elke attributieve graaf naar een verenigde, gefixeerde dimensionele representatieruimte mapt. De kerninnovatie is de Structural Interaction Graph (SIG).

2.1 Constructie van de Structural Interaction Graph (SIG)

Gegeven een input-graaf $G=(V, E)$ met node-features $X \in \mathbb{R}^{n \times d}$, "lift" Sigil de graaf van het node-domein naar het feature-dimensiedomein.

1. Multi-Order Propagatie: Features worden gepropageerd over toenemende buurtordes $k$ (van $0$ tot $K$) met behulp van niet-geparameteriseerde propagatie: $X^{(k)} = A^k X$.
2. Interactie-operatoren: Voor elke orde $k$ wordt een interactie-operator $g$ (bijv. subtractie of elementgewijze vermenigvuldiging) toegepast op de features van aangrenzende nodes om edge-features te creëren.
3. Rol-aggregatie: Deze edge-features worden geaggregeerd terug naar de nodes, gescheiden per rol (head/tail voor gerichte grafen), wat samenvattende matrices $\bar{X}^{(k)}_h$ en $\bar{X}^{(k)}_t$ creëert. Deze matrices karakteriseren hoe feature-waarden zich manifesteren over lokale buurten.
4. Gram-matrix Constructie: De uitlijning tussen feature-dimensies wordt gevangen door het berekenen van Gram-matrices (inwendige producten) van deze samenvattende vectoren: $\bar{A}^{(k)} = (\bar{X}^{(k)})^\top \bar{X}^{(k)}$.
5. De SIG: De resulterende matrices $\bar{A}^{(k)}$ vormen een Structural Interaction Graph $G_{struct}$. In deze graaf zijn:
   • Nodes de input feature-dimensies $[d]$.
   • Edges zijn gewogen en getypeerd, waarbij ze coderen hoe paren van features uitlijnen over verschillende orden van connectiviteit.
   • Voor gerichte grafen levert de constructie vier slices per orde op (head-head, tail-tail, head-tail, tail-head), wat directionele interacties vastlegt.

2.2 Representaties Leren via Relational Message Passing

Zodra de SIG is geconstrueerd, opereert een Relational Message Passing Network (RMPNN) op deze:

• Embedding: De RMPNN embed de elke feature-dimensie $f \in [d]$ in een gefixeerde verborgen ruimte $d_h$.
• Transformatie: De geleerde feature-embeddings $\Theta^{(T)} \in \mathbb{R}^{d \times d_h}$ worden gebruikt om de originele node-features van elke graaf te transformeren naar een verenigde representatie: $H = X \Theta^{(T)}$.
• Inductieve Eigenschap: Omdat de RMPNN-parameters alleen opereren op de gefixeerde verborgen breedte $d_h$ en nooit op de input-dimensie $d$, kan één getraind Sigil-model grafen met willekeurige feature-dimensionaliteiten verwerken.

2.3 Downstream Taken

• Link Voorspelling: De verenigde node-representaties worden gevoed aan expressieve link voorspellings GNN's (bijv. NBFNet) om zero-shot inferentie uit te voeren.
• Node Classificatie: De verenigde representaties dienen als input voor een downstream decoder (bijv. een lichtgewicht MLP of een analytische oplossing in gesloten vorm) om labels te voorspellen.

3. Belangrijkste Bijdragen en Theoretische Eigenschappen

3.1 Strikte Generalisatie van KGFMs

Het papier bewijst dat Sigil een strikte generalisatie is van bestaande Knowledge Graph Foundation Models (zoals ULTRA).

• Theorema 1: Wanneer de input-features one-hot indicatoren van discrete relaties zijn, herstelt de SIG-constructie exact de relatie-graaf die door KGFMs wordt gebruikt.
• Extensie: In tegenstelling tot KGFMs accepteert Sigil continue features. De Gram-matrices worden continue feature-uitlijningsmatrices in plaats van integer co-occurrence counts. Bovendien codeert de multi-order propagatie van Sigil hogere-orde interacties tussen features die KGFMs (beperkt tot single-hop motieven) missen.

3.2 Symmetrie en Equivariantie

Sigil voldoet aan de symmetrieën die vereist zijn voor volledig-inductieve generalisatie:

• Node Permutatie Equivariantie: De output node-representaties zijn equivariant aan permutaties van de input-nodes.
• Feature Permutatie Invariantie: De verenigde representatie is invariant aan de ordening of identiteit van de input feature-dimensies. Dit stelt het model in staat om grafen te lezen met feature-ruimtes die het nog nooit heeft gezien.
• Label Permutatie Equivariantie: Wanneer gekoppeld aan een equivariente decoder, respecteert het model permutaties van labels.

4. Experimentele Resultaten

De auteurs evalueren Sigil over drie regimes, waarbij gebruik wordt gemaakt van een enkel model dat vooraf is getraind op de Cora dataset (voor link voorspelling en node classificatie) of een mix van kennisgrafen (voor KG redenering).

4.1 Link Voorspelling (Continue Features)

Geëvalueerd op 11 benchmarks (7 attributieve, 4 niet-attributieve).

• Attributieve Grafen: Sigil-lp is de sterkste volledig-inductieve methode op elke dataset, waarbij het baselines zoals UniLP en TFMLinker overtreft. Opvallend genoeg presteert het aanzienlijk beter dan UniLP op datasets zoals CiteSeer en AmazonPhotos, wat aantoont dat het benutten van feature-ruimtes via SIG superieur is aan het verwerpen ervan.
• Niet-Attributieve Grafen: Sigil-lp blijft competitief, staat op de tweede plaats onder de volledig-inductieve methoden en vertoont een hoge stabiliteit.
• Efficiëntie: Sigil-lp voltooit inferentie binnen minuten, terwijl in-context baselines zoals UniLP tijdbudgetten van meer dan 24 uur overschrijden.

4.2 Knowledge Graph Reasoning

Geëvalueerd op de ULTRA benchmark (inductieve settings met ongeziene entiteiten en relaties).

• Reproductie: Sigil(0) (orde 0 SIG) reproduceert de prestaties van ULTRA binnen een kleine marge (bijv. het exact matchen van MRR op pretraining grafen).
• Expressiviteit: Hogere-orde SIG's (Sigil(1), Sigil(2)) vertonen variabele prestaties afhankelijk van de dataset, wat suggereert dat hoewel hogere-orde interacties expressiviteit toevoegen, ze de prestaties niet uniform verbeteren over alle taken.

4.3 Node Classificatie

Geëvalueerd op 26 benchmarks met variërende feature-dimensies en klassenaantallen.

• Prestaties: Sigil-nc is competitief en staat op de eerste of tweede plaats op 10 van de 26 datasets. Het blijft achter bij gespecialiseerde modellen zoals RGVT en TAG (die geoptimaliseerd zijn voor specifieke taken), maar presteert beter dan GraphAny en TS-MEAN.
• Analyse: De auteurs schrijven het prestatieverschil toe aan de "kosten van unificatie": het comprimeren van willekeurige feature-ruimtes naar een gefixeerde dimensie $d_h$ maakt de originele coördinaten ontoegankelijk voor de decoder, wat meer supervisie vereist. De resultaten bevestigen echter dat leren op SIG's een geldige aanpak is voor node classificatie foundation models.

5. Betekenis en Claims

Het artikel claimt dat Sigil verschillende voorheen gescheiden regimes in het ontwerp van graph foundation models verenigt:

1. Unificatie: Het overbrugt de kloof tussen node-classificatie GFMs (die willekeurige features afhandelen) en KGFMs (die relationele redenering afhanden), en biedt een enkele mechanisme voor beide.
2. Transfereerbaarheid: Het demonstreert dat een enkel model, getraind op één graaf, sterke zero-shot prestaties kan leveren op grafen met geheel andere feature-ruimtes en structuren.
3. Generalisatie: Door de relatie-graaf te formaliseren als een discrete instantie van een Structural Interaction Graph, biedt dit werk een theoretische basis voor het uitbreiden van relationele redenering naar continue input-ruimtes.

De auteurs concluderen dat transfereerbaarheid, relationele redenering en edge-level taken kunnen voortkomen uit een enkel mechanisme (SIG-constructie en message passing), in plaats van dat er aparte ontwerpen nodig zijn voor verschillende typen grafen. Toekomstig werk wordt gesuggereerd in het verfijnen van architecturen voor het leren op SIG's en het bestuderen van hun expressieve kracht.