🤖 machine learning

Understanding Truncated Positional Encodings for Graph Neural Networks

Dit artikel onderzoekt de theoretische en empirische implicaties van het gebruik van afgekapte positionele encodings in graph neural networks, waarbij wordt onthuld dat een dergelijke afkapting de expressieve kracht van verschillende encoding-families fundamenteel verandert — waardoor spectrale varianten niet sterker zijn dan de 1-WL test — en aantoont dat het combineren van meerdere afgekapte encodings beter presteert dan het gebruik van een enkele familie op echte datasets.

Oorspronkelijke auteurs: James Flora, Mitchell Black, Weng-Keen Wong, Amir Nayyeri

Gepubliceerd 2026-06-12

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: James Flora, Mitchell Black, Weng-Keen Wong, Amir Nayyeri

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een robot probeert te leren de lay-out van een stad te begrijpen. De robot is een Graph Neural Network (GNN), en de stad is een graaf bestaande uit kruispunten (nodes) en straten (edges).

Om een goed werk te leveren, heeft de robot meer nodig dan alleen een lijst van welke straten met elkaar verbonden zijn. Het heeft Positional Encodings (PE's) nodig. Denk aan PE's als een "kaart" of een "kompas" dat de robot vertelt waar elk kruispunt zich bevindt ten opzichte van elk ander kruispunt. Zonder deze kaart is de robot als een persoon die door een stad loopt met de ogen dicht, die alleen weet wie er direct naast hem staat, maar geen idee heeft of hij zich in het centrum van de stad bevindt of vastzit in een doodlopend steegje.

Het Probleem: De "Perfecte" Kaart is Te Zwaar

Er zijn twee belangrijke manieren om deze perfecte kaart te maken:

De Spectrale Kaart: Deze gebruikt complexe wiskunde (eigenwaarden en eigenvectoren) om de "vibraties" of de globale vorm van de stad te zien.
De Walk Map: Deze telt hoeveel manieren er zijn om van het ene punt naar het andere te lopen in 1 stap, 2 stappen, 3 stappen, enzovoort.

Wiskundig gezien, als je de volledige kaart gebruikt (alle stappen, alle vibraties), zijn deze twee methoden even krachtig. Ze kunnen bijna elke twee verschillende stadsindelingen van elkaar onderscheiden.

Echter, er is een addertje onder het gras: Het maken van deze "volledige" kaart voor een grote stad kost een enorme hoeveelheid computerkracht en geheugen (specifiek, het wordt exponentieel moeilijker naarmate de stad groeit). Het is alsof je probeert een bibliotheek met elke mogelijke kaart van de wereld in je rugzak te dragen. Het is te zwaar om in het echte leven te gebruiken.

Daarom gebruiken ingenieurs Truncated Positional Encodings. In plaats van de hele bibliotheek, nemen ze gewoon de eerste paar hoofdstukken.

Truncated Spectral: Alleen de eerste paar "vibraties" (eigenvectoren).
Truncated Walk: Alleen de eerste paar wandelstappen (machten van de adjacency matrix).

De grote vraag die het paper stelt, is: Als we het einde van deze kaarten afknippen, werken ze dan nog steeds op dezelfde manier?

De Grote Ontdekking: "Snijden" Verandert Alles

De auteurs ontdekten een verrassend antwoord: Nee, ze werken niet meer op dezelfde manier.

Wanneer je de volledige kaart hebt, zijn de Spectral- en Walk-methoden tweelingen. Maar wanneer je ze truncateert (afknipt), worden ze heel verschillende broers en zussen met verschillende sterktes en zwaktes.

De "Truncated Spectral" Valstrik: Soms maakt het gebruik van slechts de eerste paar vibraties de robot zelfs slechter in het begrijpen van de stad dan wanneer hij helemaal geen kaart zou hebben! In sommige gevallen is een getrunceerde spectrale kaart zo zwak dat hij zelfs het verschil niet kan zien tussen twee steden die een zeer eenvoudige "buur-controle" (een test genaamd de 1-WL test) gemakkelijk kan onderscheiden.
De "Truncated Walk" Valstrik: Omgekeerd zijn er stadsindelingen die een getrunceerde walk-kaart (die slechts een paar stappen telt) volledig mist, maar die een getrunceerde spectrale kaart onmiddellijk oppikt.

De Analogie: Stel je voor dat je een persoon probeert te identificeren.

De Volledige Spectrale Kaart is als het kennen van hun volledige DNA en levensgeschiedenis.
De Getrunceerde Spectrale Kaart is als het alleen kennen van hun lengte.
De Getrunceerde Walk Map is als het alleen weten van hoeveel stappen het duurt om van hun huis naar de supermarkt te lopen.

Als je alleen hun lengte kent (Truncated Spectral), kun je twee mensen van dezelfde lengte misschien met elkaar verwarren. Als je alleen de loopafstand kent (Truncated Walk), kun je twee mensen die even ver van de winkel wonen misschien met elkaar verwarren. Maar als je beide gebruikt, krijg je een veel beter beeld.

De Nieuwe Held: "Harmonische Afstanden"

Het paper introduceert een nieuwe familie van kaarten genaamd k-harmonische afstanden.

Denk aan Effective Resistance (een type 1-harmonische afstand) als het meten van hoe "verbonden" twee punten zijn, zoals de hoeveelheid elektriciteit die tussen hen door stroomt.
Het paper laat zien dat Biharmonic distance (2-harmonische) iets anders meet: hoe "centraal" of belangrijk een straat is voor de hele stad.

De auteurs bewijzen dat hoewel deze nieuwe kaarten krachtig zijn, ze ook hun grenzen hebben. Als je alleen de "weerstand"-kaart gebruikt, mis je misschien details die de "biharmonische" kaart wel vangt, en vice versa. Echter, als je genoeg van deze harmonische kaarten gebruikt, kun je de kracht van de volledige, zware kaarten recreëren.

Het Praktische Advies: "Mix en Match"

Omdat geen enkele enkele "cut" kaart perfect is, suggereren de auteurs een eenvoudige vuistregel voor ingenieurs: Vertrouw niet op slechts één type getrunceerde kaart.

In plaats daarvan: meng ze samen.

Combineer een paar stappen van de "Walk"-kaart.
Combineer een paar "vibraties" van de "Spectral"-kaart.
Voeg een "Harmonic" afstand of twee toe.

Het Experiment:
De auteurs hebben dit getest op real-world datasets (zoals het voorspellen van chemische eigenschappen van moleculen).

Het gebruik van slechts één type getrunceerde kaart was oké.
Het gebruik van een mengsel van verschillende soorten getrunceerde kaarten was aanzienlijk beter.

Het is als het navigeren door een stad: tegelijkertijd een kompas (Spectral), een stappenteller (Walk) en een maatstaf voor verkeersstroom (Harmonic) hebben, is veel beter dan vertrouwen op slechts één van hen.

Samenvatting

Volledige kaarten zijn te zwaar voor gebruik in de echte wereld, dus gebruiken we "getrunceerde" (afgeknipt) versies.
Het afknippen verbreekt de gelijkheid: Getrunceerde Spectral- en Walk-kaarten zijn niet langer gelijk; ze hebben verschillende blinde vlekken.
Sommige snedes zijn slechter dan geen kaart hebben: In sommige gevallen is een getrunceerde spectrale kaart zwakker dan een zeer basale test.
De Oplossing: Kies niet één soort. Meng verschillende soorten getrunceerde kaarten om de beste prestaties te behalen zonder de zware computationele kosten.

Technische Samenvatting: Begrip van Gekantelde Positionele Encodings voor Graph Neural Networks

Probleemstelling

Graph Neural Networks (GNN's), met name Message Passing Neural Networks (MPNN's), zijn fundamenteel beperkt in hun vermogen om globale structurele informatie te vatten, een beperking die wordt geformaliseerd door hun equivalentie aan de 1-Weisfeiler-Lehman (1-WL) test. Om dit te overwinnen, maken Graph Transformers (GT's) en verbeterde GNN's gebruik van Positionele Encodings (PE's) om structurele informatie te injecteren. Twee dominante families van PE's zijn spectrale encodings (afgeleid van de Laplaciaanse eigenruimten) en walk-gebaseerde encodings (afgeleid van machten van de adjacency matrix).

Theoretisch zijn volledige versies van deze encodings (gebruikmakend van $\Omega(n)$ eigenvectoren of matrixmachten) equivalent in expressieve kracht, liggend tussen de 1-WL en 3-WL tests. Echter, het berekenen van deze volledige encodings vereist een $O(n^3)$ tijd- en ruimtecomplexiteit, wat prohibitief is voor real-world toepassingen. Bijgevolg vertrouwen beoefenaars op gekantelde varianten (bijv. de eerste $k$ eigenvectoren of de eerste $k$ machten van de adjacency matrix). De theoretische eigenschappen, de expressieve kracht en de vergelijkende sterktes van deze gekantelde PE's blijven grotendeels onverkend, wat een kloof creëert tussen theoretische garanties en praktische implementatie.

Methodologie

De auteurs initiëren een systematische studie naar gekantelde PE's door middel van zowel theoretische analyse als empirische validatie.

Theoretisch Kader

Het artikel maakt gebruik van de WL-hiërarchie en varianten daarvan om de expressieve kracht van verschillende PE's te karakteriseren:

$\psi$ -WL Test: Een variant van de WL-test waarbij node-kleuren worden bijgewerkt met behulp van een relatieve positionele encoding (RPE) $\psi$ .
Sparse- $\psi$ -WL Test: Een uitbreiding voor MPNN's waarbij $\psi$ wordt gebruikt als edge-features.
Geanalyseerde Kernfamilies:
1. Gekantelde Eigenschapsruimte Projecties ( $k$ -EP-WL): Gebruikmakend van de eerste $k$ eigenspace projecties van de Laplaciaan.
2. Gekantelde Walk Encodings ( $k$ -Walk-WL): Gebruikmakend van de eerste $k$ machten van de adjacency matrix.
3. Effectieve Weerstand (Resistance-WL): Een specifieke spectrale afstand (1-harmonische afstand).
4. $k$ -Harmonische Afstanden: Een generalisatie van effectieve weerstand gedefinieerd als $H_k(u, v) = \sqrt{(1_u - 1_v)^T (L^+)^k (1_u - 1_v)}$ .

De auteurs construeren specifieke graafparen (bijv. producten van pad-grafen en complete grafen, of cycli versus disjuncte unies van cycli) om scheidbaarheid of ononderscheidbaarheid te bewijzen onder verschillende gekantelde PE's en WL-tests.

Empirische Evaluatie

Experimenten werden uitgevoerd op drie benchmarks:

BREC: Een dataset ontworpen om de "gerealiseerde expressiviteit" van GNN's te meten door hun vermogen te testen om niet-isomorfe grafen te onderscheiden die variëren van 1-WL tot 4-WL ononderscheidbaar.
ZINC-12k: Een graph regression benchmark voor moleculaire oplosbaarheid, gebruikt om de hypothese te testen dat het mengen van gekantelde PE's de prestaties verbetert.
ogbg-molhiv: Een binaire classificatie benchmark voor HIV-inhibitie.

De auteurs evalueerden Graphormer-GD architecturen en MPNN's (GINE) met behulp van diverse combinaties van gekantelde PE's, inclusief enkele families en mengsels van spectrale, walk en $k$ -harmonische encodings.

Belangrijkste Bijdragen en Resultaten

1. Divergentie van Expressieve Kracht in Gekantelde Vormen

Het artikel bewijst dat hoewel volledige spectrale en walk encodings equivalent zijn, hun gekantelde vormen fundamenteel verschillend zijn:

Gekantelde Spectrale vs. 1-WL: De auteurs tonen aan dat gekantelde eigenspace projecties ( $k$ -EP-WL) zwakker kunnen zijn dan de 1-WL test. Specifiek bestaan er graafparen die onderscheidbaar zijn door 1-WL maar ononderscheidbaar door $k$ -EP-WL voor $k \in \Omega(n)$ (Theorem 4.1).
Gekantelde Walk vs. Spectrale: Omgekeerd bestaan er graafparen die onderscheidbaar zijn door een enkele eigenspace projectie (1-EP-WL) maar ononderscheidbaar door $\Omega(n)$ -grootte walk encodings (Theorem 4.2).
Implicatie: Geen enkele gekantelde PE-familie is strikt superieur; ze vatten verschillende structurele aspecten samen en kunnen onvergelijkbaar zijn met de standaard WL-hiërarchie.

2. Beperkingen van Effectieve Weerstand

Het artikel analyseert Effectieve Weerstand (1-harmonische afstand) en stelt vast dat dit een zwakkere PE is dan volledige eigenspace projecties of walk encodings op gewogen grafen.

Theorem 4.3: Er bestaan gewogen grafen die ononderscheidbaar zijn door Resistance-WL maar onderscheidbaar door Adjacency-WL (en dus 1-WL op ongewogen grafen).
Corollary 4.1: Resistance-WL codeert niet het volledige spectrum van de graaf, wat een eerdere conjectuur weerlegt.

3. $k$ -Harmonische Afstanden als Brug

De auteurs introduceren $k$ -harmonische afstanden als een natuurlijke brug tussen spectrale en polynomiale encodings.

Volledigheid: Het concateneren van $\Theta(n)$ $k$ -harmonische afstanden levert een encoding op die equivalent is in kracht aan volledige spectrale of walk encodings (Theorem 4.6).
Differentieel Vermogen: Zelfs binnen de $k$ -harmonische familie verschillen vaste grootte encodings. Bijvoorbeeld, de biharmonische afstand (2-harmonische) kan bepaalde boom-paren onderscheiden in een constant aantal iteraties, terwijl effectieve weerstand (1-harmonische) $O(n)$ iteraties vereist (Theorem 4.7).
Robuustheid: Echter, als één $k$ -harmonische afstand een paar grafen onderscheidt, zullen de meeste andere $k$ -harmonische afstanden hen ook onderscheiden (Theorem 4.8).

4. Empirische Bevindingen: De Kracht van Mengen

BREC Resultaten: $k$ -harmonische afstanden behaalden competitieve resultaten met single-channel, lage-overhead encodings, en matchten vaak de theoretische bovengrens voor grafen tussen 1-WL en 3-WL.
ZINC Resultaten: De meest significante bevinding is dat het mengen van PE's uit verschillende families (bijv. het combineren van gekantelde walks en $k$ -harmonics) beter presteert dan elke enkele familie. Een mengsel van gekantelde walks en $k$ -harmonics behaalde de laagste Mean Absolute Error (MAE) op ZINC-12k, waarmee de single-family baselines werd overtroffen.
Efficiëntie: Het artikel merkt op dat $k$ -harmonische afstanden kunnen worden benaderd in $O(mk \cdot \text{poly}(\log n))$ tijd met behulp van snelle Laplaciaanse solvers en Johnson-Lindenstrauss projecties, waardoor de $O(n^3)$ kosten van exacte berekening worden vermeden.

Betekenis en Claims

Het artikel claimt de theoretische studie van gekantelde positionele encodings te hebben geïnitieerd, waarbij het perspectief verschuift van het louter beschouwen van hen als benaderingen van volledige encodings naar het zien van hen als een distincte ontwerpplek met unieke expressieve eigenschappen.

Theoretisch Inzicht: Het werk demonstreert dat de kanteling de gevangen informatie fundamenteel verandert, waardoor ze in specifieke gevallen onvergelijkbaar zijn met de standaard WL-hiërarchie.
Praktische Richtlijn: De auteurs stellen een vuistregel voor: meng PE's van verschillende families wanneer gekantelde encodings worden gebruikt. Deze aanpak vangt complementaire structurele signalen op terwijl de computationele kosten onder controle worden gehouden.
Bescheiden Omvang: De auteurs erkennen dat hoewel graaf-isomorfisme een geprincipeerd proxy is, real-world taken betrokken bij downstream-signalen (centraliteit, motieven) die mogelijk niet strikt overeenkomen met isomorphism testing. Daarom is de primaire bijdrage het vestigen van een theoretische basis en een startpunt voor een systematische empirische studie, in plaats van het claimen van een universele oplossing voor alle graph learning taken.