Fractal Graph Contrastive Learning

Riepilogo Tecnico: Fractal Graph Contrastive Learning (FractalGCL)

Enunciato del Problema
L'Apprendimento Contrastivo su Grafi (GCL) si basa sulla generazione di aumentazioni di grafi semanticamente coerenti per creare coppie positive per l'apprendimento auto-supervisionato. Tuttavia, i metodi esistenti utilizzano prevalentemente perturbazioni locali (ad esempio, cancellazione casuale di nodi/archi, mascheramento degli attributi) o vincoli topologici fissi. Gli autori sostengono che questi approcci offrono un controllo limitato sulla coerenza strutturale globale, spesso fallendo nel garantire che le visualizzazioni aumentate conservino le proprietà globali intrinseche del grafo originale. Questa mancanza di un meccanismo principiato per imporre la similarità globale crea un collo di bottiglia nell'apprendimento di rappresentazioni di grafi di alta qualità, in particolare per grafi che presentano strutture complesse e multi-scala.

Metodologia
Il documento propone FractalGCL, un framework fondato sulla geometria frattale per affrontare la sfida della coerenza globale. La metodologia è composta da tre componenti fondamentali:

1. Aumentazione Basata sulla Rinormalizzazione:
   Invece di perturbazioni locali casuali, FractalGCL genera visualizzazioni positive tramite rinormalizzazione del grafo. Questo processo comporta la partizione dei vertici del grafo in "scatole" (supervertici) disgiunte e connesse, basate su un vincolo di raggio. Ogni scatola viene collassata in un singolo supervertice, e gli archi vengono formati tra i supervertici se esisteva un arco tra i loro vertici costituenti nel grafo originale.

   • Base Teorica: Gli autori invocano il Teorema 3.2, affermando che la rinormalizzazione limitata preserva la dimensione di conteggio delle scatole (dimensione frattale) nel limite del diametro infinito. Ciò garantisce che la visualizzazione aumentata $R(G)$ mantenga una similarità strutturale con il grafo originale $G$ a una scala grossolana.
   • Costruzione dell'Input: La visualizzazione aumentata immessa nel codificatore è l'unione disgiunta $A(G) = G \sqcup R(G)$, permettendo al modello di elaborare simultaneamente strutture locali a grana fine e strutture rinormalizzate a grana grossa.

2. Funzione di Perdita Contrastiva Consapevole della Dimensione Frattale:
   Il framework introduce una nuova funzione di perdita che penalizza esplicitamente le discrepanze nella dimensione di conteggio delle scatole a scala finita tra il grafo di riferimento e la sua visualizzazione aumentata.

   • La perdita modifica i logit contrastivi standard aggiungendo un termine proporzionale a $|\hat{d}_{B}(G_i) - \hat{d}_{B}(R(G_i))|$, dove $\hat{d}_{B}$ è la dimensione della scatola stimata.
   • Coppie Positive: Il punteggio di similarità viene penalizzato se la visualizzazione rinormalizzata devia significativamente in dimensione dal riferimento, scoraggiando aumentazioni inaffidabili.
   • Coppie Negative: La forza di repulsione tra le coppie negative viene ripesata in base alla discrepanza di conteggio delle scatole tra il riferimento e la visualizzazione rinormalizzata del campione negativo. I grafi con geometrie a scala finita significativamente diverse ricevono una repulsione più forte.

3. Surrogato Gaussiano per l'Efficienza:
   Calcolare la dimensione di conteggio delle scatole per ogni grafo rinormalizzato è computazionalmente costoso ($O(|V|^3)$ negli scenari nel caso peggiore). Per rendere il metodo pratico, gli autori derivano un surrogato gaussiano controllato dal diametro.

   • Dimostrano (Proposizione 3.5) che la discrepanza di rinormalizzazione $\Delta(G) = \hat{d}_{B}(G) - \hat{d}_{B}(R(G))$ può essere approssimata da una distribuzione gaussiana $N(0, \sigma^2)$ controllata dal diametro del grafo e dall'incertezza di regressione.
   • Questo surrogato evita ripetute regressioni di conteggio delle scatole durante l'addestramento, riducendo il tempo di esecuzione di circa il 61%.
   • Fallback Sicuro: Un meccanismo di gating disabilita la correzione frattale (impostando il peso $\alpha=0$) se il diametro del grafo è piccolo ($\le 9$) o se l'adattamento del conteggio delle scatole è debole ($R^2 < 0.9$), assicurando che il modello ricada sul comportamento GCL standard quando le ipotesi frattali non sono valide.

Contributi Chiave

• Geometria Frattale nel GCL: Il documento è tra i primi a introdurre una prospettiva frattale matematicamente rigorosa nell'apprendimento di rappresentazioni di grafi, dimostrando che le proprietà strutturali globali e senza scala sono un segnale potente per l'apprendimento contrastivo.
• Architettura Guidata dalla Teoria: L'integrazione di aumentazioni basate sulla rinormalizzazione e di una funzione di perdita consapevole della dimensione fornisce un'alternativa principizzata alle perturbazioni locali euristico.
• Implementazione Efficiente: La derivazione del surrogato gaussiano trasforma un metodo teoricamente solido ma computazionalmente proibitivo in uno strumento pratico, ottenendo un significativo aumento di velocità senza sacrificare le prestazioni.
• Meccanismo di Robustezza: Il fallback a livello di obiettivo garantisce che il metodo non degradi le prestazioni su grafi privi di una chiara scala frattale o troppo piccoli per una stima affidabile della dimensione.

Risultati Sperimentali
Gli autori valutano FractalGCL attraverso tre contesti distinti:

1. Pre-addestramento Congelato (MalNet-Tiny): FractalGCL funge da strumento efficace di pre-addestramento congelato. Quando combinato con classificatori a valle (ad esempio, SAGE, JK-SAGE), migliora l'accuratezza rispetto ai baseline, con il guadagno più grande di 1,20 punti percentuali sul modello SAGE-small.
2. Benchmark Standard (TUDataset): Su cinque dataset (NCI1, MUTAG, PROTEINS, D&D, REDDIT-M5K), FractalGCL raggiunge la più alta accuratezza media (76,93%), superando il metodo successivo migliore (GradGCL) di 1,29 punti percentuali. Si classifica primo su tutti e cinque i dataset individuali. Il margine di prestazioni è notevolmente più ampio sul dataset D&D, che presenta caratteristiche frattali forti.
3. Applicazione nel Mondo Reale (Traffico Urbano): Valutato su compiti di classificazione della sicurezza del traffico utilizzando reti stradali di Chicago, San Francisco e New York, FractalGCL raggiunge un'accuratezza media del 61,76%, superando il baseline successivo migliore di 4,51 punti percentuali.

Significato e Affermazioni
Il documento afferma che FractalGCL dimostra che la coerenza strutturale globale, formalizzata attraverso la geometria frattale, è un fattore critico ma spesso trascurato nell'apprendimento di rappresentazioni di grafi. Spostandosi oltre le perturbazioni locali per imporre l'autosimilarità multi-scala, il metodo migliora la qualità degli embedding appresi.

Gli autori notano modestamente che l'efficacia del metodo dipende dalla presenza di una struttura frattale significativa a scala finita. Riconoscono che per grafi con una scala frattale debole o diametri molto piccoli, la correzione frattale può essere meno informativa, motivo per cui il meccanismo di fallback proposto è essenziale. Il lavoro posiziona la geometria frattale non solo come una curiosità teorica, ma come un prior pratico e scalabile per la progettazione di obiettivi di apprendimento contrastivo su grafi robusti.