Riassunto Tecnico: CoRe-GNN: Passaggio di Messaggi Multilivello su Grafi Coarsened

Problematica

L'addestramento di Graph Neural Networks (GNN) su grafi di grandi dimensioni è fondamentalmente limitato dal costo di memoria richiesto per memorizzare le rappresentazioni intermedie dei nodi attraverso i livelli. Nelle architetture standard di passaggio di messaggi, la rappresentazione di un nodo al livello $l$ dipende dal suo vicinato a $l$-hop. Per grafi di grandi dimensioni, questo vicinato cresce esponenzialmente con la profondità, portando a colli di bottiglia della memoria che saturano la memoria GPU sia durante l'addestramento che durante l'inferenza.

Gli approcci scalabili esistenti rientrano generalmente in due categorie, entrambe affette da limitazioni complementari:

1. Coarsening del Grafo (Raggruppamento): Metodi come Coarsen-GNN mappano i nodi originali in "supernodi" per creare un grafo più piccolo. Sebbene ciò permetta una propagazione efficiente e offra garanzie spettrali, impone che tutti i nodi all'interno di un supernodo condividano la stessa rappresentazione. Questa "uniformità" limita la discriminabilità per singolo nodo, particolarmente in contesti eterofili dove i nodi adiacenti possono avere etichette diverse.
2. Restrizione Basata su Cluster: Metodi come Cluster-GCN limitano il passaggio di messaggi solo alle connessioni intra-cluster, scartando gli archi inter-cluster. Ciò consente un batching efficiente trattando i cluster come sottografi indipendenti. Tuttavia, recidere le connessioni inter-cluster elimina le dipendenze a lungo raggio, degradando le prestazioni in compiti che richiedono l'aggregazione di informazioni su molti hop.

Entrambi gli approcci si basano su una decomposizione del grafo in gruppi di nodi, ma non riescono a bilanciare il compromesso tra la preservazione della struttura a lungo raggio e il mantenimento della discriminabilità locale del nodo.

Metodologia: CoRe-GNN

Gli autori propongono CoRe-GNN (Coarsen and Restore), un'architettura progettata per affrontare simultaneamente il limite di accuratezza del coarsening dei grafi e la cecità a lungo raggio di Cluster-GCN.

Formulazione Matriciale Unificata

Il documento stabilisce prima una prospettiva unificata sui GNN a grafo compresso, vedendoli come modifiche strutturate della matrice di propagazione standard $S$.

• Coarsen-GNN sostituisce $S$ con $\Pi S \Pi$, dove $\Pi = QP$ è un operatore a costanza di blocco che mappa i nodi ai supernodi e viceversa.
• Cluster-GCN sostituisce $S$ con $S_{intra}$, una matrice a blocchi diagonali che mantiene solo gli archi intra-cluster.

L'Architettura CoRe-GNN

CoRe-GNN esegue due propagazioni parallele ad ogni livello, accoppiando lo spazio coarsened (raffinato/aggregato) e lo spazio dei nodi originali:

1. Propagazione Inter-Cluster (Coarsened): Un termine $S_{inter}^c$ opera sul grafo coarsened (supernodi). Questo cattura in modo efficiente le informazioni strutturali a lungo raggio.
2. Propagazione Intra-Cluster (Locale): Un termine $S_{intra}$ opera sullo spazio dei nodi originali, preservando la discriminabilità per singolo nodo all'interno dei cluster.

La regola di aggiornamento per il livello $l$ è:
$$H^{(l)} = Q \sigma(S_{inter}^c P H^{(l-1)} \theta_c^{(l)}) + \sigma(S_{intra} H^{(l-1)} \theta^{(l)})$$
Qui, $P$ e $Q$ sono matrici di riduzione e lifting derivate dalla partizione del grafo. L'architettura mantiene due stati paralleli: $H_c^{(l)}$ nello spazio coarsened e $H^{(l)}$ nello spazio dei nodi originali. I pesi $\theta^{(l)}$ e $\theta_c^{(l)}$ sono indipendenti, permettendo alla rete di apprendere trasformazioni distinte per le interazioni locali e a lungo raggio.

Schema di Batching

Per scalare a grafi con milioni di nodi, CoRe-GNN introduce una strategia di batching naturale:

• Termine inter-cluster: Calcolato su tutti i $n$ supernodi (dove $n \ll N$) in ogni step, il che è computazionalmente economico.
• Termine intra-cluster: Calcolato solo per i cluster nel batch corrente $B$. Per i supernodi non inclusi nel batch, il termine intra-cluster è approssimato da un proxy di self-loop nello spazio coarsened durante l'addestramento.
  Questo approccio riduce la complessità della memoria a $O(K(n+b)d)$, indipendente dal numero totale di nodi $N$, consentendo l'addestramento su grafi che altrimenti eccederebbero la memoria GPU.

Inferenza Esatta: Mentre lo schema di batching per l'addestramento utilizza un'approssimazione, gli autori derivano un procedimento di inferenza esatta non banale che evita questo collo di bottiglia. In questa modalità, il termine inter-cluster è calcolato su tutti i supernodi sulla GPU, mentre il termine intra-cluster viene calcolato cluster per cluster, caricando i blocchi dalla CPU alla GPU su richiesta e scartandoli immediatamente. Ciò consente l'inferenza esatta su grafi molto grandi senza dover mantenere l'intero grafo computazionale attraverso i livelli.

Garanzie Teoriche

Gli autori dimostrano che CoRe-GNN eredita garanzie di approssimazione simili al coarsening dei grafi. Nello specifico, limitano l'errore tra il passaggio di messaggi sul grafo originale e CoRe-GNN utilizzando la costante di Restricted Spectral Approximation (RSA). Il limite teorico per CoRe-GNN dipende dalle proprietà del sottografo inter-cluster ($S_{inter}$), suggerendo che all'aumentare del rapporto di coarsening, i limiti di errore possono migliorare rispetto al coarsening standard.

Contributi Chiave

1. Prospettiva Unificata: Il documento fornisce una formulazione matriciale che mostra come il coarsening dei grafi e Cluster-GCN siano modifiche strutturate complementari della matrice di propagazione, chiarendo le rispettive limitazioni.
2. Architettura CoRe-GNN: Una nuova architettura che accoppia le propagazioni inter-cluster (coarsened) e intra-cluster (locali) in parallelo, mitigando la perdita di discriminabilità nel coarsening e la perdita di informazioni a lungo raggio nel clustering.
3. Batching Scalabile: Uno schema di batching naturale che permette a CoRe-GNN di addestrare su grafi con milioni di nodi, unito a una procedura di inferenza esatta che evita approssimazioni.
4. Analisi Teorica: Derivazione delle garanzie di propagazione per CoRe-GNN, mostrando che preserva segnali fluidi con costanti dipendenti dalla struttura inter-cluster.
5. Validazione Empirica: Valutazione completa su benchmark omofili, eterofili, su larga scala e a lungo raggio.

Risultati Sperimentali

Gli autori hanno valutato CoRe-GNN su un set diversificato di dataset, tra cui:

• Omofili: Cora, CiteSeer, PubMed.
• Eterofili: Chameleon, Squirrel, Amazon Ratings.
• Larga scala: ogbn-arxiv, Reddit, ogbn-products.
• Lungo raggio: Reti stradali di Parigi e Londra.

Risultati Principali:

• Prestazioni: CoRe-GNN supera costantemente i baseline Coarsen-GNN e Cluster-GCN in tutte le categorie.
• Compiti a Lungo Raggio: Sui dataset di Parigi e Londra, CoRe-GNN raggiunge l'accuratezza più elevata, dimostrando la sua capacità di catturare le dipendenze a lungo raggio che Cluster-GCN perde e la discriminabilità che il puro Coarsen-GNN manca.
• Eterofilia: Sui dataset eterofili (es. Squirrel), CoRe-GNN supera significativamente Coarsen-GNN, che fatica quando i nodi nello stesso supernodo hanno etichette diverse.
• Scalabilità: Su dataset su larga scala come Reddit e ogbn-products, il GCN standard e la versione non batched di CoRe-GNN vanno in esaurimento della memoria (OOM). La variante batched di CoRe-GNN riesce ad addestrare con successo e raggiunge un'accuratezza competitiva o superiore rispetto a Cluster-GCN.
• Ablazione: Gli esperimenti confermano che l'uso di pesi indipendenti per i due rami e l'uso della matrice di propagazione specifica per l'inter-cluster ($S_{inter}^c$) anziché la matrice coarsened completa produce prestazioni migliori.

Significato e Rivendicazioni

Il paper sostiene che CoRe-GNN unifica con successo i vantaggi del coarsening dei grafi e della restrizione basata su cluster. Eseguendo propagazioni parallele, supera i "fallimenti complementari" degli attuali metodi scalabili: la perdita di dettaglio a livello di nodo nel coarsening e la recisione delle dipendenze a lungo raggio nel clustering.

Gli autori sottolineano che CoRe-GNN fornisce un framework che:

1. Mantiene le garanzie spettrali per la propagazione di segnali fluidi.
2. Preserva la discriminabilità per singolo nodo in contesti eterofili.
3. Cattura le dipendenze a lungo raggio essenziali per compiti grafici complessi.
4. Scala a milioni di nodi tramite uno schema di batching efficiente in termini di memoria.

Il lavoro suggerisce che la decomposizione del grafo in gruppi non debba essere necessariamente un compromesso tra accuratezza e scalabilità; piuttosto, un approccio multilivello può raggiungere entrambi. Gli autori notano che il framework è attualmente limitato alle GNN con matrici di propagazione fisse (escludendo i meccanismi di attenzione) e che il lavoro futuro potrebbe esplorare estensioni alle connessioni residue e agli scenari di apprendimento federato asincrono.