Riepilogo Tecnico: Modello di Base per Grafi Centrato sulla Struttura tramite Basi Geometriche

1. Enunciato del Problema

I Modelli di Base per Grafi (GFMs) mirano ad apprendere rappresentazioni trasferibili attraverso domini di grafi diversificati. Tuttavia, gli approcci esistenti affrontano due limitazioni primarie:

1. Eterogeneità Strutturale: I grafi variano significativamente in topologia, scala e metriche indotte tra i diversi domini. A differenza del testo o delle immagini, i grafi sono oggetti relazionali definiti solo fino all'isomorfismo, privi di un riferimento geometrico condiviso.
2. Incompatibilità delle Caratteristiche: Gli spazi delle caratteristiche dei nodi differiscono spesso in dimensionalità e semantica tra i dataset. I GFMs attuali impongono tipicamente dimensioni fisse delle caratteristiche tramite proiezioni specifiche per dataset, padding o adattatori. Sebbene ciò allinei gli spazi delle caratteristiche, non riesce ad allineare le strutture sottostanti dei grafi, portando a rappresentazioni che riflettono scarsamente la similarità intrinseca dei grafi e limitando il trasferimento tra domini.

Le alternative esistenti, come la tokenizzazione dei grafi, impongono ordinamenti artificiali su strutture intrinsecamente non ordinate, violando l'invarianza permutazionale e fallendo nel catturare la geometria intrinseca del grafo.

2. Metodologia: SCGFM

Gli autori propongono i Modelli di Base per Grafi Centrati sulla Struttura (SCGFM), che trattano la topologia del grafo come la fonte primaria di conoscenza trasferibile. L'idea centrale è modellare i grafi come spazi di misura metrica (mm-spaces) e apprendere un sistema di coordinate strutturali condiviso.

2.1. Prospettiva Geometrica

SCGFM assume che i grafi del mondo reale risiedano all'interno di un sottoinsieme totalmente limitato dello spazio degli mm-spaces. Basandosi sul teorema di compattezza di Gromov, qualsiasi grafo può essere approssimato dalle sue distanze rispetto a un insieme finito di pattern geometrici canonici (basi).

2.2. Componenti Principali

Il framework consiste in due fasi: Pre-addestramento delle Basi Geometriche e Proiezione a Valle.

A. Basi Geometriche Apprendibili

SCGFM apprende un insieme finito di $K$ basi geometriche $\{B_k\}_{k=1}^K$. Ogni base $B_k$ è definita come uno spazio di misura metrica finito $( [M], d_k, \mu_k )$:

• Metrica ($d_k$): Rappresentata da una matrice simmetrica e vuota apprendibile $B_k \in [0, 1]^{M \times M}$, che parametrizza i pesi degli archi di una struttura di grafo canonica con $M$ nodi.
• Misura ($\mu_k$): Fissata a una distribuzione uniforme per garantire accoppiamenti ben definiti.

Queste basi collettivamente formano un sistema di coordinate strutturali condiviso.

B. Allineamento Strutturale tramite Gromov–Wasserstein (GW)

I grafi di input $G$ vengono allineati alle basi utilizzando le distanze di Gromov–Wasserstein (GW). Per garantire la scalabilità, il metodo impiega la Gromov–Wasserstein a Fette (SGW), che riduce la complessità computazionale da $O(N^3)$ a quasi lineare $O(N \log N)$ proiettando le strutture metriche su fette unidimensionali.

Per un grafo $G$, la discrepanza strutturale rispetto a ciascuna base $B_k$ è calcolata come $\delta_k = d_{GW}(G, B_k)$. Queste distanze vengono convertite in un vettore di coordinate strutturali $w$ (pesi) tramite una funzione softmax:
$$w_k = \frac{\exp(-\delta_k / \tau)}{\sum_j \exp(-\delta_j / \tau)}$$
Questo vettore $w$ funge da rappresentazione del grafo nello spazio geometrico condiviso.

C. Ricalibrazione delle Caratteristiche

Per affrontare l'incompatibilità delle caratteristiche senza assumere dimensioni fisse, SCGFM impiega un meccanismo di ricalibrazione delle caratteristiche consapevole della struttura:

1. Piano di Trasporto: Il piano di trasporto ottimale $T_{ik}$ ottenuto durante il calcolo GW mappa i nodi dal grafo di input alla base geometrica.
2. Proiezione: Le caratteristiche dei nodi vengono aggregate e proiettate sulle basi utilizzando $T_{ik}$, risultando in una matrice di caratteristiche unificata $H(G)$.
3. Unificazione: Questo processo unifica le rappresentazioni dei nodi ancorate alla struttura, rimanendo agnostico rispetto alla dimensionalità originale delle caratteristiche.

D. Obiettivi di Addestramento

L'obiettivo di pre-addestramento minimizza una somma pesata di tre perdite:

1. Perdita di Ricostruzione GW ($L_{gw}$): Minimizza la distanza tra il grafo di input e un surrogato lineare del baricentro GW (una combinazione pesata di basi).
2. Perdita di Ricostruzione Statistica ($L_{rec}$): Un decoder $f(\cdot)$ ricostruisce statistiche a livello di grafo (istogramma dei gradi, clustering, motivi) da $w$ per garantire la fedeltà strutturale.
3. Regolarizzazione della Diversità ($L_{div}$): Impone una separazione pairwise tra le basi per prevenire il collasso e garantire che esse coprano lo spazio strutturale.

2.3. Rappresentazione a Valle

L'embedding finale del grafo $z(G)$ è una concatenazione di:

1. Coordinate strutturali $w$.
2. Statistiche ricostruite $f(w)$.
3. Caratteristiche proiettate $vec(H(G))$.

Questo embedding unificato viene utilizzato per compiti a valle (classificazione di nodi o grafi) tramite un encoder congelato e un classificatore leggero (ad esempio, Rete Prototipale).

3. Contributi Chiave

1. GFM Centrato sulla Struttura: Un framework innovativo che abilita il trasferimento tra dataset di grafi eterogenei senza architetture specifiche per dataset o pre-elaborazione delle caratteristiche, affidandosi invece a un sistema di coordinate geometrico condiviso.
2. Basi Geometriche e Spazio Latente: L'introduzione di basi geometriche apprendibili che inducono uno spazio latente allineato geometricamente. Gli autori dimostrano che le distanze in questo spazio correlano fortemente con la geometria intrinseca dei grafi GW.
3. Flessibilità delle Caratteristiche: Un meccanismo per unificare caratteristiche di nodi eterogenee attraverso l'allineamento strutturale, eliminando la necessità di dimensioni fisse delle caratteristiche o pre-elaborazione specifica per dominio.
4. Garanzie Teoriche: Dimostrazione che le coordinate strutturali apprese e le statistiche ricostruite sono continue di Lipschitz rispetto alla distanza GW, garantendo stabilità.

4. Risultati Sperimentali

Gli autori hanno valutato SCGFM su 12 dataset attraverso 5 domini (Molecole, Reti Sociali, Accademico, E-commerce, Sintetico) per la classificazione a livello di grafo e di nodo sotto un protocollo di apprendimento few-shot a 5 esempi.

• Prestazioni: SCGFM ha costantemente superato basi solide, inclusi GNN vanilla (GCN, GIN, GAT), metodi auto-supervisionati (GraphCL, GraphMAE) e GFMs esistenti (GCOPE, RiemannGFM, GIT).
  • Classificazione di Grafi: Ha raggiunto una precisione superiore sia intra-dominio che inter-dominio, in particolare sul dataset COLORS-3 dove le basi si sono degradate a livelli vicini al caso fortuito a causa di grandi spostamenti strutturali.
  • Classificazione di Nodi: Ha dimostrato un comportamento quasi indipendente dalla sorgente. Ad esempio, sul dataset Reddit, le prestazioni sono rimaste elevate (~84%) indipendentemente dal dominio di pre-addestramento, attribuito alla capacità del modello di proiettare caratteristiche semantiche ad alta dimensionalità in uno spazio dove la separabilità lineare è garantita (Teorema di Cover).
• Scalabilità: SCGFM si è scalato fluidamente a grafi con 5 milioni di nodi, mantenendo il consumo di picco di memoria più basso (~12 GB) tra tutti i metodi. I metodi concorrenti (GAT, GIT) hanno incontrato errori di memoria esaurita a scale inferiori.
• Studi di Ablazione:
  • Su dataset dominati dalle caratteristiche (ad es. Cora), le caratteristiche proiettate $vec(H)$ erano critiche; la loro rimozione ha causato un crollo catastrofico delle prestazioni.
  • Su dataset dominati dalla struttura (ad es. PROTEINS, MUTAG), le coordinate geometriche $w$ sono state i principali driver delle prestazioni.
  • Sia le perdite di ricostruzione che quelle di diversità sono state essenziali per un addestramento stabile attraverso tutte le modalità.
• Interpretabilità: Le visualizzazioni hanno mostrato che le basi apprese si sono specializzate in motivi geometrici distinti (ad es. cluster densi, pattern ad anello e coda) e si sono evolute da pattern non strutturati a primitive topologiche nette durante l'addestramento.
• Isometria: Le distanze euclidee nello spazio latente hanno mostrato una forte correlazione lineare ($\rho \approx 0.70$) con le vere distanze GW, confermando che l'embedding preserva la geometria intrinseca del grafo.

5. Significato e Affermazioni

Il documento afferma che SCGFM offre un'alternativa fondata alla tokenizzazione dei grafi e ai GFMs dipendenti dal dominio. Modellando i grafi come spazi di misura metrica e utilizzando le distanze GW, SCGFM disaccoppia con successo la topologia dalla semantica.

Gli autori sottolineano che il loro approccio:

• Generalizza in modo robusto attraverso domini disparati senza modifiche architetturali.
• Fornisce stabilità teorica attraverso garanzie di continuità di Lipschitz.
• Scala efficientemente a grafi massicci, superando i colli di bottiglia computazionali del calcolo GW esatto tramite l'approssimazione SGW.
• Si adatta alla modalità dei dati, sfruttando efficacemente segnali strutturali o semantici a seconda delle caratteristiche del dataset.

Il lavoro si posiziona come un passo verso un paradigma unificato e centrato sulla struttura per i modelli di base per grafi che supera le limitazioni degli approcci centrati sulle caratteristiche e basati su token.