🤖 machine learning

Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings

Dit artikel introduceert een nieuw zelfgesuperviseerd benchmarkframework voor Graph Neural Networks gebaseerd op het graafuitlijningsprobleem, waarbij wordt aangetoond dat taakmoeilijkheid effectief modelarchitecturen kan rangschikken en dat de resulterende geleerde positionele coderingen downstream graaftaken aanzienlijk verbeteren.

Oorspronkelijke auteurs: Adrien Lagesse, Marc Lelarge

Gepubliceerd 2026-06-24

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Adrien Lagesse, Marc Lelarge

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

Het Grote Idee: Een Nieuwe "Sportschool" voor AI

Stel je voor dat je wilt testen hoe sterk een nieuwe gewichtheffer is. Je zou hen niet zomaar een willekeurige doos laten tillen; je zou hen op een specifieke, verstelbare gewichthefmachine zetten waar je precies kunt controleren hoe zwaar de gewichten zijn.

Dit paper stelt een nieuwe "gewichthefmachine" voor voor Graph Neural Networks (GNN's). GNN's zijn een type AI die ontworpen zijn om data te begrijpen die eruitziet als een kaart van verbindingen (zoals sociale netwerken, chemische moleculen of wegenkaarten).

De auteurs stellen dat de huidige manieren om deze AI's te testen gebrekkig zijn, omdat ze de "vorm" van de kaart verwarren met de "labels" op de kaart (zoals kleuren of namen). Ze willen het vermogen van de AI om alleen de vorm te begrijpen, testen. Hiervoor hebben ze een benchmark gecreëerd gebaseerd op een puzzel genaamd Graph Alignment.

De Kernpuzzel: Het "Ghost Map" Spel

Denk aan het Graph Alignment Probleem als volgt:

Stel je voor dat je een gedetailleerde kaart van een stad hebt (Grafiek A).
Stel je nu een "ghost" versie van diezelfde stad voor (Grafiek B). Het heeft exact dezelfde straten en kruispunten, maar de straatnamen zijn door elkaar gehusseld en een paar straten zijn willekeurig verwijderd of er zijn nieuwe straten toegevoegd.
De Uitdaging: Jouw AI moet naar de Ghost Map kijken en ontdekken welk kruispunt op de Ghost Map overeenkomt met welk kruispunt op de Originele Kaart.

Als de AI erin slaagt om de twee kaarten met elkaar te matchen, bewijst dat de AI de structuur van de stad echt begrijpt, en niet alleen de namen op de borden.

Hoe Ze de Test Hebben Gebouwd

De onderzoekers hebben niet slechts één kaart gebruikt. Ze hebben een hele sportschool gebouwd met verschillende soorten terrein:

Synthetische Kaarten: Door de computer gegenereerde willekeurige steden.
Real-World Kaarten: Werkelijke data van sociale netwerken (zoals Twitter), chemische moleculen en wetenschappelijke artikelen.

Ze hebben ook een "moeilijkheidsschuifregelaar" toegevoegd (genaamd ruis of noise).

Lage Ruis: De Ghost Map is bijna identiek aan de Originele Kaart. De puzzel is makkelijk.
Hoge Ruis: De Ghost Map is erg rommelig, met veel ontbrekende of valse straten. De puzzel is erg moeilijk.

De Ontdekking: Ze ontdekten dat als de puzzel te makkelijk of te moeilijk is, alle AI's hetzelfde lijken (of ze krijgen het allemaal goed, of ze falen allemaal). Maar op een "Goldilocks"-niveau van moeilijkheid worden de verschillen tussen de slimste en de domste AI's heel duidelijk. Dit stelt onderzoekers in staat om de modellen nauwkeurig te rangschikken.

De Resultaten: Wie wint de Sportschool?

Toen ze de test uitvoerden, ontdekten ze enkele interessante zaken over hoe verschillende AI-architecturen werken:

Isotroop vs. Anisotroop: Denk aan "Isotrope" modellen als mensen die elke richting hetzelfde behandelen (zoals iemand die in een cirkel loopt). "Anisotrope" modellen zijn als mensen die aandacht besteden aan de specifie of specifieke richting waarin ze kijken.
De Winnaar: De "richting-bewuste" (Anisotrope) modellen versloegen consequent de "richting-blinde" (Isotrope) modellen. Dit suggereert dat het aandacht schenken aan de specifieke richting van verbindingen de AI helpt de kaart beter te begrijpen.

De Bonus: Leren "Lezen" van de Kaart

Het meest opwindende deel van het paper is wat er gebeurt nadat de AI de puzzel heeft opgelost.

Wanneer de AI leert om deze kaarten uit te lijnen, creëert het een speciale "identiteitskaart" (een embedding) voor elk afzonderlijk punt op de kaart. Deze identiteitskaarten bevatten een diep begrip van waar dat punt zich in de algehele structuur bevindt.

De auteurs lieten zien dat deze identiteitskaarten zo goed zijn dat ze kunnen worden gebruikt als Positional Encodings voor een ander type AI genaamd een Transformer (hetzelfde soort AI die chatbots en beeldgeneratoren aandrijft).

De Analogie: Meestal zijn Transformers als mensen die een boek kunnen lezen, maar niet weten waar de woorden op de pagina staan. Deze "identiteitskaarten" fungeren als een GPS voor de woorden, die de Transformer precies vertelt waar elk stukje data zich in de structuur bevindt.
Het Resultaat: Wanneer ze deze door AI gegenereerde identiteitskaarten gebruikten, werd de Transformer ongelooflijk goed in het voorspellen van chemische eigenschappen (zoals hoe goed een medicijn oplost) en kon hij zelfs de hele kaart met 98% nauwkeurigheid opnieuw tekenen.

Samenvatting

Kortom, dit paper zegt:

We hebben een betere manier nodig om te testen of Graph AI's daadwerkelijk vormen begrijpen, en niet alleen labels.
We hebben een "Ghost Map" puzzel (Graph Alignment) gecreëerd die ons toestaat de moeilijkheidsgraad aan te passen om te zien welke AI echt de slimste is.
We hebben ontdekt dat AI's die aandacht besteden aan richting het beste werken.
De "lessen" die deze AI's leren van de puzzel zijn zo krachtig dat ze kunnen worden gebruikt om andere AI's te leren hoe ze complexe structuren moeten begrijpen, wat leidt tot betere voorspellingen in de wetenschap en chemie.

De auteurs hebben ook een gratis toolkit uitgebracht, zodat iedereen deze "Ghost Map" puzzels kan bouwen en hun eigen AI-modellen kan testen.

Technische Samenvatting: Grafische Uitlijning voor het Benchmarking van Graph Neural Networks en het Leren van Positionele Encodings

Probleemstelling

Graph Neural Networks (GNN's) worden breed toegepast in domeinen zoals chemie, materiaalkunde en sociale netwerken. Het evalueren van hun structurele begrip blijft echter een uitdaging. Bestaande benchmarks verwarren vaak structurele capaciteiten met feature-leren of vertrouwen op combinatorische optimalisatietaken (bijv. SAT, TSP) die gebonden zijn aan specifieke topologieën of synthetische modellen zoals het Stochastic Block Model (SBM), wat de generaliseerbaarheid beperkt. Bov�ijnast worstelen huidige methoden ermee om een fijnmazige metriek te bieden om modellen binnen dezelfde expressiviteitsklasse (bijv. de 1-Weisfeiler-Lehman klasse) te vergelijken of om structurele expressiviteit over diverse grafische topologieën te kwantificeren die in real-world toepassingen worden gevonden.

De auteurs stellen voor dit gat te dichten door een benchmarking-methodologie te introduceren gebaseerd op het Grafische Uitlijningsprobleem (ook bekend als Graph Matching). Deze taak behelst het uitlijnen van twee ongelabelde grafen om het aantal overlappende randen te maximaliseren, een combinatorisch optimalisatieprobleem dat grafische isomorfie generaliseert.

Methodologie

1. De Grafische Uitlijningstaak

De kernopdracht wordt gedefinieerd als het vinden van een permutatie $\pi^*$ tussen twee grafen $G$ en $\tilde{G}$ met $N$ knopen die de overlap van hun adjacency matrices maximaliseert:
$\pi^* \in \arg \max_{\pi \in S_N} \sum_{i,j} A_{i,j} \tilde{A}_{\pi(i),\pi(j)}$
Dit wordt geformuleerd als een self-supervised learning taak. De auteurs maken gebruik van een Siamese architectuur waarbij een GNN beide grafen verwerkt om node embeddings $X$ en $\tilde{X}$ te produceren. Een gelijkenismatrix $\Sigma = X\tilde{X}^T$ wordt berekend.

Training: Het model minimaliseert de binary cross-entropy loss tussen de voorspelde gelijkenismatrix en de grondwaarheid (planted permutation).
Evaluatie: Het Hongarijaanse algoritme lost het Lineaire Toewijzingsprobleem op $\Sigma$ op om de voorspelde permutatie te extraheren. Prestaties worden gemeten aan de hand van het percentage correct toegewezen knopen.

2. Dataset Constructie

Om de beperkingen van eerdere synthetische datasets (bijv. Erdős-Rényi grafen alleen) te overwinnen, stellen de auteurs een methode voor om Grafische Uitlijningsdatasets te genereren van elke bestaande grafische dataset (base datasets).

Geërdeerde Grafische Generatie: Voor een base graaf $G$ wordt een gecorreleerde graaf $\tilde{G}$ gegenereerd door willekeurig randen toe te voegen en te verwijderen op basis van een ruisniveau $\eta$ .
Planted Solution: Aangezien de optimale uitlijning bekend is (de identiteit of een bekende permutatie vóór de ruis), is de grondwaarheid beschikbaar zonder het NP-harde probleem op te lossen.
Schaalbaarheid: Voor grote grafen (bijv. OGBN-Arxiv) wordt een Breadth-First Search (BFS) sampling algoritme gebruikt om kleinere subgrafen te extraheren die de lokale topologie behouden, waardoor ze compatibel zijn met Message-Passing Neural Networks (MPNN's).
Moeilijkheidsgraad Controle: Door het ruisniveau $\eta$ te variëren (van 4% tot 30%), creëren de auteurs een familie van datasets met controleerbare moeilijkheidsgraden, wat genuanceerde evaluatie mogelijk maakt.

3. Positionele Encoding Leren (GAPE)

De auteurs benutten de geleerde node embeddings uit de Grafische Uitlijningstaak als Graph Alignment Positional Encodings (GAPE). Deze embeddings zijn bedoeld om te dienen als structurele inputs voor Transformer-architecturen, die van nature geen toegang hebben tot de grafische structuur.

Belangrijkste Bijdragen

Nieuwe Benchmarking Taak: Introductie van het Grafische Uitlijningsprobleem als een benchmark voor GNN's, die de Weisfeiler-Lehman test generaliseert en evaluatie over diverse topologieën (moleculair, sociaal, random) mogelijk maakt zonder de onderliggende grafische structuren te wijzigen.
Dataset Generatie Framework: Een uitgebreide methodologie om Grafische Uitlijningsdatasets te generen van zowel synthetische als real-world base datasets, wat de creatie van datasets met variërende moeilijkheidsgraden mogelijk maakt.
Empirische Rangschikking van Architecturen: Een systematische benchmark van veelgebruikte MPNN's (GCN, GIN, GatedGCN, GAT, GATv2) die aantoont dat anisotrope modellen consequent beter presteren dan isotrope modellen (zoals GCN en GIN) bij structurele analyse, zelfs op homofiele grafen.
Optimale Moeilijkheidsgraad: De ontdekking dat er een "optimaal ruisniveau" bestaat waar het prestatieverschil tussen modellen wordt gemaximaliseerd, wat statistisch significante rangschikkingen oplevert die robuust zijn tegen hyperparameterkeuzes en willekeurige seeds.
Positionele Encodings (GAPE): Demonstratie dat embeddings geleerd via Grafische Uitlijning effectieve positionele encodings zijn voor Transformers, waarbij ze spectral en random-walk-gebaseerde encodings evenaren of overtreffen bij moleculaire regressietaken.
Grafische Reconstructie: Bewijs dat GAPE embeddings de grafische structuur effectief comprimeren, waardoor de volledere adjacency matrix gereconstrueerd kan worden met ~98% nauwkeurigheid met behulp van een eenvoudige decoder.
Open-Source Tooling: Voorzienheid van een Python-package om deze datasets te genereren en nieuwe architecturen te benchmarken.

Resultaten

Modelprestaties: In experimenten over vijf base datasets (Erdős-Rényi, AQSOL, PCQM4Mv2, CoraFull, OGBN-Arxiv) bereikten anisotrope architecturen (GatedGCN, GAT, GATv2) een hogere uitlijningsnauwkeurigheid dan isotrope architecturen (GCN, GIN).
Ruisgevoeligheid: Het prestatieverschil tussen modellen was verwaarloosbaar bij zeer lage of zeer hoge ruisniveaus. Het verschil piekte bij een optimaal ruisniveau (bijv. $\eta \approx 15\%$ voor moleculaire grafen), waar de statistische significantie het hoogst was.
Downstream Taken: Wanneer gebruikt als positionele encodings voor Transformers in moleculaire regressie (AQSOL, PCQM4Mv2), bereikte GAPE state-of-the-art of concurrerende Mean Absolute Error (MAE) vergeleken met Laplacian, Random Walk en andere spectrale encodings. Specifiek behaalde GAPE+RWPE de beste resultaten op AQSOL en PCQM4Mv2.
Reconstructie: Een autoencoder met een bevroren GAPE-encoder bereikte 98%+ nauwkeurigheid in het reconstrueren van de adjacency matrix, wat bevestigt dat de embeddings de volledige grafische topologie vastleggen.
Correlatie: Er werd een sterke negatieve correlatie ( $r < -0.90$ ) waargenomen tussen Grafische Uitlijning nauwkeurigheid en downstream moleculaire eigenschap voorspellingsfout, wat suggereert dat het vermogen tot structurele uitlijning een primaire bottleneck is voor deze taken.

Betekenis en Claims

Het artikel claimt een robuust, fijnmazig framework te bieden voor het evalueren van de structurele expressiviteit van GNN's, onafhankelijk van specifieke node- of edge-features. Door het structurele begrip te isoleren, onthult de benchmark dat anisotrope modellen een rijkere representatie van de grafische topologie bieden dan eerder vastgestelde isotrope modellen.

Verder betogen de auteurs dat de Grafische Uitlijningstaak niet louter een "puzzel" is, maar een fundamentele pre-training doelstelling. Het feit dat de geleerde embeddings kunnen worden gebruikt voor hoogwaardige grafische reconstructie en de prestaties van downstream Transformers aanzienlijk verbeteren, suggereert dat de taak het model dwingt om een hoogwaardige compressie van de grafische structuur te leren. Dit valideert de bruikbaarheid van de benchmark voor zowel het vergelijken van architecturen als het genereren van nuttige representaties voor real-world toepassingen in chemie en materiaalkunde.

Het werk concludeert dat de Grafische Uitlijning benchmark een flexibele, domein-agnostische benadering biedt voor GNN-evaluatie, die in staat is zich aan te passen aan de specifieke topologische kenmerken van elk doeltoepassingsdomein.