GraphProp: Training the Graph Foundation Models using Graph Properties

Dit paper introduceert GraphProp, een tweefasige methode voor het trainen van graf-foundationmodellen die zich richt op structurele generalisatie door graf-invarianten te voorspellen en deze te gebruiken als positie-encoding, waardoor de modellen superieure prestaties leveren bij graf-classificatie, vooral in scenario's zonder knooppuntattributen.

De kern

Stel je voor dat je een meester-architect bent die gebouwen van over de hele wereld moet begrijpen en classificeren. Je hebt te maken met alles: van kleine houten hutjes in een dorp tot gigantische glazen wolkenkrabbers in een moderne stad.

Het probleem is dat elk type gebouw zijn eigen speciale "taal" heeft. De houten hutten hebben informatie over hun houtsoort en dakbedekking (dit zijn de knooppunten of node features). De wolkenkrabbers hebben informatie over hun glas en staal. Als je probeert een model te bouwen dat alle gebouwen begrijpt, raakt je vaak de draad kwijt omdat de materialen (de data) zo verschillend zijn.

Dit is precies het probleem waar GraphProp voor oplost. Het is een nieuwe manier om slimme computermodellen (zogenoemde "Graph Foundation Models") te trainen om elk type grafiek of netwerk te begrijpen, ongeacht waar het vandaan komt.

Hier is hoe het werkt, in drie simpele stappen:

1. De Grote Ontdekking: De "Vorm" is belangrijker dan de "Stof"

De onderzoekers merkten iets belangrijks op. Als je een brug bekijkt en een spinnenweb, zijn de materialen totaal anders (staal versus zijde). Maar als je kijkt naar de structuur (hoeveel draden er kruisen, hoe de bochten lopen), zijn er verrassende overeenkomsten.

• De oude aanpak: Modellen probeerden vooral de "materialen" (de tekstuele beschrijvingen van de knopen) te vertalen naar één gemeenschappelijke taal. Dit werkte goed als de materialen op elkaar leken, maar faalde als ze totaal verschillend waren.
• De GraphProp-inzicht: De vorm van het gebouw (de structuur) bevat universele regels die voor elk gebouw gelden, of het nu een brug, een sociale netwerk of een molecuul is. Denk aan het aantal verbindingen, de lengte van de langste weg, of hoe stevig het geheel is. Deze regels zijn als de "wiskunde van de vorm" en zijn overal hetzelfde.

2. Stap 1: De "Structuur-leraar" (De eerste training)

GraphProp begint met het trainen van een speciaal model dat alleen naar de blauwdrukken kijkt, zonder naar de materialen te kijken.

• Hoe werkt het? Het model krijgt een blauwdruk van een gebouw en moet raden: "Hoeveel draden zijn er nodig om dit te stabiliseren?" of "Wat is de langste route door dit gebouw?".
• De truc: Het model leert niet door te lezen wat er op de muren staat, maar door de wiskundige eigenschappen van de vorm te voorspellen. Dit noemen ze "grafische invarianten".
• Het resultaat: Het model wordt een expert in het begrijpen van de vorm van een netwerk. Het leert dat een brug en een spinnenweb, ondanks hun verschillende materialen, dezelfde wiskundige principes volgen. Dit maakt het model heel goed in het herkennen van structuren, zelfs als het nooit eerder zo'n type gebouw heeft gezien.

3. Stap 2: De "Alles-kunner" (De tweede training)

Nu hebben we een model dat de vorm perfect begrijpt. Maar we willen ook weten wat voor materiaal er gebruikt is (bijvoorbeeld: is het een giftig molecuul of een vriendelijk sociaal netwerk?).

• De combinatie: In deze tweede fase nemen we de kennis van de "Structuur-leraar" en gebruiken we die als een GPS-kaart (een soort positie-informatie) voor een tweede, groter model.
• Het proces: Dit tweede model krijgt nu zowel de GPS-kaart (de structuur) als de specifieke beschrijvingen van de materialen (de knoop-kenmerken). Omdat het model al weet hoe de vorm eruitziet, kan het de specifieke informatie veel beter plaatsen en begrijpen.
• Het voordeel: Zelfs als een gebouw geen beschrijving van zijn materialen heeft (bijvoorbeeld een oud, onbekend netwerk zonder data), kan het model het nog steeds goed classificeren op basis van de vorm die het in Stap 1 heeft geleerd.

Waarom is dit zo geweldig? (De Analogie)

Stel je voor dat je een detective bent die moorden moet oplossen in verschillende steden.

• De oude methoden probeerden alleen de getuigenverklaringen (de tekst) te vertalen. Als er in één stad geen getuigen waren, kon de detective niets doen.
• GraphProp leert eerst de patronen van de misdaad (de structuur). Het leert dat moorden vaak op dezelfde manier georganiseerd zijn, ongeacht de stad.
• Vervolgens gebruikt het die kennis om ook de specifieke details van de zaak (de getuigen) te analyseren.
• Het resultaat: Zelfs als er in een nieuwe stad geen getuigen zijn (geen knoop-kenmerken), kan de detective de dader nog steeds vinden omdat hij de patronen kent.

Samenvatting in één zin

GraphProp is een slimme methode die eerst leert om de "skeletstructuur" van netwerken te begrijpen via wiskundige regels, en die kennis vervolgens gebruikt om ook de "vlees en bloed" (de specifieke data) van elk type netwerk te doorgronden, zelfs als die data ontbreekt.

Dit maakt het model veel sterker, flexibeler en beter in staat om nieuwe, onbekende situaties aan te pakken dan eerdere modellen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "GraphProp: Training the Graph Foundation Models using Graph Properties", geschreven in het Nederlands.

Probleemstelling

De ontwikkeling van Graph Foundation Models (GFMs) stuit op een fundamenteel probleem: het vinden van consistente informatie die over verschillende domeinen (zoals chemische moleculen en sociale netwerken) heen werkt.

• Huidige beperkingen: Bestaande GFMs richten zich voornamelijk op het overdragen van knooppunt-kenmerken (node features) naar een uniforme representatieruimte. Echter, deze kenmerken zijn vaak sterk domeinspecifiek (bijv. chemische eigenschappen vs. gebruikersprofielen) en hebben weinig overlap tussen domeinen.
• Structuur vs. Kenmerken: Het paper stelt dat grafstructuren (de connectiviteit) meer consistente, domein-onafhankelijke informatie bevatten dan knooppunt-kenmerken of labels. Traditionele methoden die grafen omzetten naar tekst voor LLM's (Large Language Models) verliezen vaak essentiële structurele informatie of missen de capaciteit voor structurele generalisatie, vooral bij grafen zonder knooppunt-kenmerken.

Methodologie: GraphProp

GraphProp is een tweefasige trainingsmethode die de structurele generalisatie van GFMs verbetert door gebruik te maken van graftheorie-eigenschappen (graph invariants).

Fase 1: Training van een Structurele GFM

In deze fase wordt een model getraind puur op basis van de grafstructuur (adjacentiematrix), zonder gebruik te maken van knooppunt-kenmerken of labels.

• Doel: Het voorspellen van graf-invarianten. Dit zijn eigenschappen die alleen afhangen van de abstracte structuur van de graf en niet van de labeling of tekening (bijv. het Lovász-getal, het fractionele chromatische getal, de diameter, het Wiener-index).
• Implementatie:
  • Een Graph Transformer fungeert als de structurele GFM ($f$).
  • Als positie-encoding wordt een reversibele methode gebruikt ($B = U\Lambda^{1/2}$, gebaseerd op de Laplacian-matrix) om ervoor te zorgen dat alle informatie uit de adjacentiematrix behouden blijft.
  • Het model leert een regressor om een vector van $K$ verschillende graf-eigenschappen te voorspellen.
• Data Augmentatie: Om het gebrek aan gelabelde data te overwinnen, gebruikt GraphProp ongelabelde data en synthetische grafen. Omdat de training gebaseerd is op het voorspellen van wiskundige invarianten (die berekend kunnen worden zonder labels), kunnen synthetische grafen effectief worden gebruikt.

Fase 2: Training van een Comprehensieve GFM

In deze tweede fase wordt de structurele GFM gebruikt om een volledig model te trainen dat ook domeinspecifieke informatie verwerkt.

• Positie-encoding: De structurele representaties ($Z$) die door de eerste fase zijn gegenereerd, worden gebruikt als positie-encoding.
• In-Context Learning: Deze structurele representaties worden gecombineerd met domeinspecifieke knooppunt-kenmerken (via Text-Attributed Graphs, TAG) en labels.
• Doel: Het model leert via in-context learning om zowel de universele structuur als de specifieke domein-kenmerken te integreren voor taken zoals graf-classificatie.

Belangrijkste Bijdragen

1. Nieuwe Training Paradigma: GraphProp is de eerste GFM die expliciet eerst een structurele GFM traint via het voorspellen van graf-eigenschappen, en deze vervolgens gebruikt om een comprehensieve GFM te bouwen. Dit zorgt voor zowel structurele als knooppunt-kenmerk generalisatie.
2. Theoretische Garantie: Het paper biedt theoretische bewijzen dat GraphProp een sterke graf-discriminatiecapaciteit heeft. Als twee grafen verschillend zijn, zullen hun voorspelde invarianten ook verschillend zijn, wat essentieel is voor graf-taken.
3. Overbrugging van Graftheorie en GFM: Door graftheorie-eigenschappen (zoals het fractionele chromatische getal) te gebruiken als supervisie, wordt de kloof tussen wiskundige graftheorie en modern deep learning overbrugd.
4. Oplossing voor Data Schaarste: De methode maakt het mogelijk om ongelabelde en synthetische grafen te gebruiken voor training, wat een groot probleem is bij het trainen van foundation modellen.

Resultaten

De auteurs hebben experimenten uitgevoerd op twee groepen datasets:

• G1: Datasets met knooppunt-kenmerken (bijv. PROTEINS, NCI1).
• G2: Datasets zonder knooppunt-kenmerken (bijv. COLLAB, IMDB-B, DD).

Kernbevindingen:

• Supervised Learning: GraphProp presteert significant beter dan state-of-the-art baselines (zoals OFA, BRIDGE, EdgePrompt+) in beide groepen.
  • In G2 (zonder knooppunt-kenmerken) is de prestatieverbetering het grootst. Bestaande modellen zoals OFA falen hier vaak omdat ze afhankelijk zijn van tekstuele beschrijvingen van knooppunten die niet bestaan. GraphProp kan hier echter de structuur direct benutten.
  • Op datasets zoals COLLAB, IMDB-B en DD toont GraphProp aanzienlijke verbeteringen in nauwkeurigheid (ACC).
• Few-Shot Learning: In scenario's met weinig trainingsdata (k-shot) overtreft GraphProp consistent andere methoden, wat aantoont dat het model beter generaliseert naar nieuwe, ongezichten domeinen.

Betekenis en Conclusie

GraphProp vertegenwoordigt een belangrijke stap voorwaarts in het veld van Graph Foundation Models. Het paper demonstreert dat grafstructuren een rijkere bron van domein-onafhankelijke informatie zijn dan knooppunt-kenmerken. Door de kracht van graftheorie-eigenschappen te benutten voor supervisie, creëert GraphProp een robuustere basis voor generalisatie. Dit maakt het mogelijk om effectieve foundation modellen te bouwen voor grafen, zelfs wanneer deze geen gedetailleerde knooppunt-kenmerken hebben, wat een veelvoorkomende beperking in bestaande methoden was.