Technische Samenvatting: Structure-Centric Graph Foundation Model via Geometric Bases

1. Probleemstelling

Graph Foundation Models (GFMs) streven naar het leren van overdraagbare representaties over diverse grafendomeinen. Echter, bestaande benaderingen ondervinden twee primaire beperkingen:

1. Structurele Heterogeniteit: Grafen variëren aanzienlijk in topologie, schaal en geïnduceerde metrieken tussen domeinen. In tegenstelling tot tekst of afbeeldingen zijn grafen relationele objecten die slechts tot op isomorfisme gedefinieerd zijn, en missen ze een gedeelde geometrische referentie.
2. Feature-Incompatibiliteit: De ruimten van knoopkenmerken verschillen vaak in dimensionaliteit en semantiek tussen datasets. Huidige GFMs dwingen doorgaans vaste feature-dimensies af via dataset-specifieke projecties, opvulling of adapters. Hoewel dit feature-ruimten uitlijnt, faalt het om de onderliggende grafstructuren uit te lijnen, wat leidt tot representaties die de intrinsieke grafgelijkenis slecht weerspiegelen en de overdracht tussen domeinen beperken.

Bestaande alternatieven, zoals graf-tokenisatie, leggen kunstmatige ordeningen op aan van nature ongeordende structuren, wat de permutatie-invariantie schendt en faalt in het vastleggen van de intrinsieke grafgeometrie.

2. Methodologie: SCGFM

De auteurs stellen Structure-Centric Graph Foundation Models (SCGFM) voor, die graf-topologie behandelen als de primaire bron van overdraagbare kennis. Het kerninzicht is om grafen te modelleren als metrische maatruimten (mm-ruimten) en een gedeeld structureel coördinatenstelsel te leren.

2.1. Geometrisch Perspectief

SCGFM neemt aan dat real-world grafen liggen binnen een totaal begrensde deelverzameling van de ruimte van mm-ruimten. Gebaseerd op de compactheidstelling van Gromov kan elke graaf worden benaderd door zijn afstanden tot een eindige set canonieke geometrische patronen (bases).

2.2. Kerncomponenten

Het kader bestaat uit twee fasen: Pre-training van Geometrische Bases en Projectie voor Downstream Taken.

A. Leerbare Geometrische Bases

SCGFM leert een eindige set van $K$ geometrische bases $\{B_k\}_{k=1}^K$. Elke base $B_k$ is gedefinieerd als een eindige mm-ruimte $( [M], d_k, \mu_k )$:

• Metriek ($d_k$): Gerepresenteerd door een leerbare, symmetrische, holle matrix $B_k \in [0, 1]^{M \times M}$, die de randgewichten parametrisert van een canonieke grafstructuur met $M$ knopen.
• Maat ($\mu_k$): Vastgesteld op een uniforme verdeling om goed gedefinieerde koppelingen te waarborgen.

Deze bases vormen collectief een gedeeld structureel coördinatenstelsel.

B. Structurele Uitlijning via Gromov–Wasserstein (GW)

Invoergraf $G$ worden uitgelijnd met de bases met behulp van Gromov–Wasserstein (GW) afstanden. Om schaalbaarheid te waarborgen, maakt de methode gebruik van Sliced Gromov–Wasserstein (SGW), wat de computationele complexiteit reduceert van $O(N^3)$ naar quasi-lineair $O(N \log N)$ door het projecteren van metrische structuren op 1D-schijven.

Voor een graaf $G$ wordt de structurele discrepantie met elke base $B_k$ berekend als $\delta_k = d_{GW}(G, B_k)$. Deze afstanden worden omgezet in een structureel coördinatenvector $w$ (gewichten) via een softmax-functie:
$$w_k = \frac{\exp(-\delta_k / \tau)}{\sum_j \exp(-\delta_j / \tau)}$$
Deze vector $w$ dient als de representatie van de graaf in de gedeelde geometrische ruimte.

C. Feature Hervercodering

Om feature-incompatibiliteit aan te pakken zonder vaste dimensies aan te nemen, hanteert SCGFM een structure-bewust feature-hercoderingsmechanisme:

1. Transportplan: Het optimale transportplan $T_{ik}$ verkregen tijdens GW-berekening, koppelt knopen van de invoergraaf aan de geometrische base.
2. Projectie: Knoopkenmerken worden geaggregeerd en geprojecteerd op de bases met behulp van $T_{ik}$, resulterend in een geünificeerde feature-matrix $H(G)$.
3. Unificatie: Dit proces unificeert knooprepresentaties die verankerd zijn in de structuur, en blijft agnostisch ten opzichte van de oorspronkelijke feature-dimensionaliteit.

D. Trainingsdoelen

Het pre-training-doel minimaliseert een gewogen som van drie verliezen:

1. GW-Reconstructieverlies ($L_{gw}$): Minimaliseert de afstand tussen de invoergraaf en een lineair surrogaat van het GW-barycentrum (een gewogen combinatie van bases).
2. Statistisch Reconstructieverlies ($L_{rec}$): Een decoder $f(\cdot)$ reconstrueert graf-niveau statistieken (graadhistogram, clustering, motieven) uit $w$ om structurele fideliteit te waarborgen.
3. Diversiteitsregularisatie ($L_{div}$): Dwingt paarsgewijze scheiding tussen bases af om ineenstorting te voorkomen en te waarborgen dat ze de structurele ruimte beslaan.

2.3. Downstream Representatie

De uiteindelijke graf-embedding $z(G)$ is een concatenatie van:

1. Structurele coördinaten $w$.
2. Gereconstrueerde statistieken $f(w)$.
3. Geprojecteerde features $vec(H(G))$.

Deze geünificeerde embedding wordt gebruikt voor downstream taken (knopen- of grafclassificatie) via een bevroren encoder en een lichtgewicht classifier (bijv. Prototypical Network).

3. Belangrijkste Bijdragen

1. Structure-Centric GFM: Een nieuw kader dat overdracht mogelijk maakt over heterogene grafendatasets zonder dataset-specifieke architecturen of feature-preprocessing, en in plaats daarvan vertrouwt op een gedeeld geometrisch coördinatenstelsel.
2. Geometrische Bases & Latente Ruimte: De introductie van leerbare geometrische bases die een geometrie-uitgelijnde latente ruimte induceren. De auteurs tonen aan dat afstanden in deze ruimte sterk correleren met intrinsieke GW-grafgeometrie.
3. Feature-flexibiliteit: Een mechanisme om heterogene knoopkenmerken te unificeren door middel van structurele uitlijning, waardoor de noodzaak voor vaste feature-dimensies of domein-specifieke preprocessing wordt geëlimineerd.
4. Theoretische Waarborgen: Het bewijs dat de geleerde structurele coördinaten en gereconstrueerde statistieken Lipschitz-continu zijn met betrekking tot de GW-afstand, wat stabiliteit waarborgt.

4. Experimentele Resultaten

De auteurs evalueerden SCGFM op 12 datasets over 5 domeinen (Moleculen, Sociale Netwerken, Academisch, E-commerce, Synthetisch) voor zowel graf-niveau als knoop-niveau classificatie onder een 5-shot few-shot learning protocol.

• Prestaties: SCGFM presteerde consequent beter dan sterke baselines, waaronder vanilla GNN's (GCN, GIN, GAT), zelftoezichtende methoden (GraphCL, GraphMAE) en bestaande GFMs (GCOPE, RiemannGFM, GIT).
  • Grafclassificatie: Bereikte superieure in-domein en cross-domein nauwkeurigheid, met name op de COLORS-3 dataset waar baselines degradeerden tot bijna-chance-niveaus door grote structurele verschuivingen.
  • Knoopclassificatie: Toonde bijna bron-onafhankelijk gedrag. Bijvoorbeeld, op de Reddit dataset bleef de prestatie hoog (~84%) ongeacht het pre-training domein, toegeschreven aan het vermogen van het model om hoogdimensionale semantische features te projecteren in een ruimte waar lineaire scheidbaarheid gegarandeerd is (Cover's Theorem).
• Schaalbaarheid: SCGFM schaalde soepel naar grafen met 5 miljoen knopen, met behoud van het laagste piekgeheugengebruik (~12 GB) onder alle methoden. concurrerende methoden (GAT, GIT) ondervonden out-of-memory-fouten bij lagere schalen.
• Ablatiestudies:
  • Op feature-dominante datasets (bijv. Cora) waren de geprojecteerde features $vec(H)$ cruciaal; het verwijderen ervan veroorzaakte een catastrofale daling in prestaties.
  • Op structuur-dominante datasets (bijv. PROTEINS, MUTAG) waren de geometrische coördinaten $w$ de primaire drijfveren van prestaties.
  • Zowel reconstructie- als diversiteitsverliezen waren essentieel voor stabiele training over alle modaliteiten.
• Interpreteerbaarheid: Visualisaties toonden aan dat geleerde bases gespecialiseerd waren in distincte geometrische motieven (bijv. dichte clusters, ring-en-staart patronen) en evolueerden van ongeordende patronen naar scherpe topologische primitieven tijdens training.
• Isometrie: De latente Euclidische afstanden toonden een sterke lineaire correlatie ($\rho \approx 0,70$) met ware GW-afstanden, wat bevestigt dat de embedding de intrinsieke grafgeometrie behoudt.

5. Betekenis en Claims

Het artikel claimt dat SCGFM een principiële alternatief biedt voor graf-tokenisatie en domein-afhankelijke GFMs. Door grafen te modelleren als metrische maatruimten en GW-afstanden te benutten, slaagt SCGFM erin topologie te ontkoppelen van semantiek.

De auteurs benadrukken dat hun aanpak:

• Robuust generaliseert over uiteenlopende domeinen zonder architecturale aanpassingen.
• Theoretische stabiliteit biedt door middel van Lipschitz-continuïteitsgaranties.
• Efficiënt schaalt naar massale grafen, door de computationele knelpunten van exacte GW-berekening te overwinnen via de SGW-benadering.
• Zich aanpast aan datamodaliteit, effectief gebruikmakend van zowel structurele als semantische signalen afhankelijk van de datasetkarakteristieken.

Het werk positioneert zichzelf als een stap naar een unificerend, structure-gecentreerd paradigma voor graf foundation modellen dat de beperkingen van feature-gecentreerde en token-gebaseerde benaderingen overwint.