Technische Samenvatting: Plain Transformers zijn verrassend krachtige Link Predictors

Probleemstelling

Linkvoorspelling (link prediction) is een fundamentele taak in graph machine learning, maar de huidige state-of-the-art benaderingen kampen met aanzienlijke uitdagingen op het gebied van schaalbaarheid en generalisatie. Standaard Graph Neural Networks (GNN's), met name Message-Passing Neural Networks (MPNN's), worden beperkt door hun node-centrische aggregatie, die vaak faalt in het onderscheiden van structureel verschillende node-paren met symmetrische lokale buurten. Om dit te overwinnen, vertrouwen bestaande pipelines vaak op expliciete structurele heuristieken (bijv. gemeenschappelijke buren, afstandscodering), globale graafkenmerken, of leerbare per-node ID-embeddings. Deze benaderingen introduceren verschillende kritieke beperkingen:

1. Schaalbaarheid: Methoden die afhankelijk zijn van globale caches of volledige graaf-passes hebben moeite met web-schaal grafen en dynamische updates.
2. Deployment-beperkingen: ID-gebaseerde embeddings vereisen dure hertraining of herberekening wanneer nieuwe nodes worden toegevoegd, wat in strijd is met de behoefte aan efficiëntie met een vast budget voor mini-batches.
3. Overmatige afhankelijkheid van Priors: Veel modellen slagen door eenvoudige structurele signalen te exploiteren in plaats van generaliseerbare patronen te leren, en ze vereisen vaak complexe, handmatig ontworde structurele encodings (PE/SE) die de hardware-efficiëntie hinderen.

Hoewel Graph Transformers (GT's) een theoretisch alternatief bieden via all-to-all attention, brengen zij doorgaans aanzienlijke overhead met zich mee door complexe structurele encodings (bijv. spectrale signalen, random walks) die vaak onhaalbaar zijn voor link voorspellings-taken met strikte deployment-beperkingen.

Methodologie: PENCIL

De auteurs stellen PENCIL voor (Plain ENCoder for Inferring Links), een Transformer-gebaseerde link predictor ontworpen om te opereren zonder handmatig ontworde priors, node ID's of globale preprocessing. PENCIL maakt gebruik van een standaard, encoder-only BERT-stijl architectuur die is aangepast voor graph link voorspelling via een nieuw encoding-schema en architecturaal ontwerp.

1. Graph Encoding Schema

In plaats van de volledige graaf te verwerken, opereert PENCIL op fixed-budget, gesamplede lokale subgrafen gecentreerd rond een kandidaat-link $(v_{src}, v_{dst})$.

• Tokenisatie: Voor een kandidaat-paar krijgen de subgraaf-nodes indices toegewezen waarbij $v_{src}$ wordt vastgezet op index 0 en $v_{dst}$ op index 1. De overige nodes krijgen willekeurige indices toegewezen.
• Input Representatie: Elk token bestaat uit drie geconcateneerde componenten:
  1. Een one-hot identifier van de node binnen de gesamplede volgorde.
  2. De adjacency indicator rij van de node binnen de geëxtraheerde subgraaf (waardoor het model de adjacency matrix direct uit de input kan reconstrueren).
  3. Een role flag die context-nodes onderscheidt van task-nodes (endpoints).
• Task Tokens: Twee aanvullende task tokens worden toegevoegd, die de identifier en adjacency informatie van de endpoints kopiëren, maar de role flag omdraaien om aan te geven dat zij de query-targets zijn.

2. Architectuurontwerp

PENCIL maakt gebruik van een standaard Transformer encoder met bidirectionele self-attention, gekoppeld aan een specifiek residu-mechanisme:

• Input Projectie: De getokeniseerde input en optionele node features worden geprojecteerd naar een gedeelde verborgen dimensie. De auteurs maken gebruik van orthogonale initialisatie voor de projectiematrix om goed geconditioneerde initiële vectoren te garanderen.
• Adjacency Reconstructie: De subgraaf adjacency matrix $\tilde{A}$ wordt niet als aparte input geleverd, maar wordt gereconstrueerd door de adjacency indicator rijen uit de token encoding te snijden.
• Multiplicatieve Residu: Om structurele inductieve bias te injecteren zonder complexe encodings, voegt PENCIL een multiplicatieve residu-term toe aan de standaard Transformer output. Voor elke laag $k$:
  $$H^{(k)} = Z^{(k)} + P_k(\tilde{A}Z^{(k)})$$
  waarbij $Z^{(k)}$ de output is van de self-attention block en $P_k$ een leerbare projectie is. Dit stelt het model in staat om expliciete one-hop message passing uit te voeren over de gereconstrueerde adjacency matrix naast de dense self-attention.
• Predictie: De uiteindelijke representaties van de twee task tokens worden geconcateneerd en geprojecteerd naar een scalaire logit, getraind met binary cross-entropy loss.

Belangrijkste Bijdragen

1. Prestaties en Efficiëntie

PENCIL bereikt state-of-the-art prestaties op diverse benchmarks (inclusief OGB datasets zoals ogbl-ppa en ogbl-citation2) terwijl het aanzienlijk minder parameters gebruikt dan leidende ID-gebaseerde methoden (22× tot 146× minder). Het demonstreert superieure trainingsefficiëntie, waarbij het in 6.7× tot 40× minder epochs convergeert dan pure GNN-architecturen op grootschalige datasets. Opvallend genoeg behaalt het deze resultaten zonder node features op verschillende datasets, wat de aanname uitdaagt dat features universeel noodzakelijk zijn.

2. Theoretische Unificatie

Het paper biedt een formele theoretische analyse die PENCIL verbindt met gevestigde paradigma's:

• Heuristiek Herstel: De auteurs bewijzen dat PENCIL kan degenereren naar source-geconditioneerde MPNN's (zoals NBFNet) en, onder specifieke parametervestellingen, klassieke pad-gebaseerde heuristieken realiseert (Katz index, Personalized PageRank, Shortest Path Distance) en lokale heuristieken (Common Neighbors).
• Expressiviteit: Door middel van het $k_\phi$-$k_\rho$-$m$ framework tonen de auteurs aan dat PENCIL, wanneer uitgerust met lokale relationele pooling, niet minder expressief is dan SEAL (een subgraph-gebaseerde GNN) onder dezelfde sampling-beperkingen.
• Permutatie Invariantie: Hoewel de encoding randomized indices gebruikt, bewijzen de auteurs dat de resulterende predictor permutatie invariant is in distributie, wat voldoet aan de symmetrie-eisen van graph-taken.

3. Structurele Sufficiëntie

Experimentele resultaten wijzen erop dat op veel standaard benchmarks, structurele informatie alleen voldoende is voor hoge prestaties. Het paper demonstreert dat node features soms volatiliteit kunnen introduceren of slechts beperkte marginale winst bieden vergeleken met rijke structurele signalen die worden gevangen door het attention mechanisme van de Transformer.

Experimentele Resultaten

• Benchmarks: PENCIL werd geëvalueerd op Planetoid datasets (Cora, Citeseer, Pubmed) en OGB link voorspellings datasets (ogbl-citation2, ogbl-ppa, ogbl-ddi, ogbl-collab).
• Vergelijkingen: Het presteert beter dan heuristiek-geïnformeerde GNN's (bijv. NCN, Neo-GNN) en ID-gebaseerde methoden (bijv. MPLP+, Refined-GAE) in termen van nauwkeurigheid en stabiliteit (lagere variantie).
• Heuristiek Estimatie: In taken die vereisen dat pairwise heuristieken (bijv. Katz, PageRank) vanuit lokale subgrafen worden geschat, presteert PENCIL aanzienlijk beter dan standaard GNN's, wat zijn vermogen aantoont om lang-afstands structurele afhankelijkheden te vangen waar MPNN's moeite mee hebben door oversquashing.
• Diepte: In tegenstelling tot MPNN's, die vaak last hebben van prestatievermindering bij toenemende diepte, profiteert PENCIL van diepere architecturen, waarbij consistente verbeteringen in Hits@K metrieken worden getoond naarmate de diepte toeneemt.

Betekenis en Claims

Het paper claimt dat eenvoudige ontwerpkeuzes voldoende zijn om state-of-the-art link voorspellingscapaciteiten te bereiken, wat de heersende afhankelijkheid van complexe engineeringtechnieken, handmatig ontworde structurele encodings en enorme parametercounts uitdaagt.

• Paradigmaverschuiving: PENCIL demonstreert dat een "plain" Transformer, wanneer gecombineerd met een eenvoudige lokale subgraph sampling strategie en een multiplicatieve residu, rijkere structurele signalen kan extraheren dan standaard GNN's.
• Deployment Haalbaarheid: Door het elimineren van de noodzaak voor globale preprocessing, ID-embeddings of offline structurele encodings, biedt PENCIL een schaalbare, hardware-efficiënte oplossing die geschikt is voor real-world, grootschalige deployment scenario's.
• Theoretische Fundering: Het werk overbrugt de kloof tussen high-expressivity link voorspelling en praktische deployment, door de eerste systematische verklaring te bieden van hoe een vanilla bidirectionele Transformer effectief als link predictor kan fungeren zonder de sterke positionele encodings die typisch zijn voor Graph Transformers.

De auteurs concluderen dat vooruitgang in hardware en systemen voor het verwerken van grotere gesamplede subgrafen de praktische capaciteiten van dergelijke modellen direct kan uitbreiden, waardoor plain Transformers worden gepositioneerd als een legitiem en theoretisch onderbouwd paradigma voor graph machine learning.