Riepilogo Tecnico: Rete Neurale a Grafo a Spettro Completo: Espressiva e Scalabile

Enunciato del Problema

Le Reti Neurali a Grafo (GNN) spettrali standard parametrizzano la propagazione sul grafo come filtraggio Laplaciano. Sebbene sia stabilito che le GNN spettrali possono approssimare universalmente i segnali sui nodi, la loro potenza espressiva nel distinguere grafi non isomorfi è strettamente limitata dal test di Weisfeiler–Lehman 1-dimensionale (1-WL). Questa limitazione riflette la loro incapacità di approssimare universalmente segnali di ordine superiore. Inoltre, le GNN spettrali classiche si affidano a filtri spettrali diagonali (funzioni di singoli autovalori), il che ne limita la capacità di modellare interazioni complesse, in particolare nei grafi eterofili dove i nodi adiacenti possiedono spesso etichette diverse. Gli approcci esistenti per superare il 1-WL coinvolgono tipicamente l'innalzamento del passaggio di messaggi a domini di ordine superiore (ad esempio, coppie di nodi) nel dominio spaziale, ma è mancato un corrispondente framework spettrale scalabile.

Metodologia

Gli autori propongono FSPECGNN (Full-Spectrum Graph Neural Network), una generalizzazione del secondo ordine delle GNN spettrali classiche. La metodologia si fonda su due avanzamenti teorici fondamentali:

1. Innalzamento del Dominio del Segnale: Invece di filtrare i segnali sui nodi $x \in \mathbb{R}^V$, FSPECGNN opera su segnali su coppie di nodi $\varepsilon \in \mathbb{R}^{V \times V}$. Questo innalza il segnale dal dominio dei nodi al dominio delle coppie di nodi.
2. Filtraggio Spettrale Bivariato: Il filtraggio spettrale classico applica una funzione univariata $g(\lambda)$ agli autovalori. FSPECGNN estende questo concetto a un filtro bivariato $g(\lambda_i, \lambda_j)$ su coppie di autovalori.
   • La convoluzione a spettro completo è definita come:
     $$G_\lambda *_{\mathcal{G}} \varepsilon = \sum_{i,j} g(\lambda_i, \lambda_j) u_i u_i^\top \varepsilon u_j u_j^\top$$
     dove $L = U\Lambda U^\top$ è la decomposizione spettrale del Laplaciano del grafo.
   • Questa formulazione generalizza le GNN spettrali classiche, che si dimostrano essere un caso speciale diagonale di FSPECGNN (recuperato limitando il filtro alla diagonale $g(\lambda_i, \lambda_i)$).

Implementazione Scalabile:
Il calcolo diretto nel dominio delle coppie di nodi ($n^2 \times n^2$) è intrattabile per grafi di grandi dimensioni. Per affrontare questo problema, gli autori propongono un'implementazione scalabile utilizzando la decomposizione tensoriale a rango basso:

• Il filtro polinomiale bivariato è approssimato da una somma di polinomi univariati separabili: $P(L \otimes I, I \otimes L) \approx \sum_{r=1}^S f_r(L) \otimes h_r(L)$.
• Utilizzando la proprietà $(A \otimes B)\text{vec}(\varepsilon) = \text{vec}(B\varepsilon A^\top)$, la convoluzione è calcolata come $h(L) \varepsilon f(L)^\top$, evitando la costruzione esplicita dell'operatore di dimensione $n^2$.
• Il segnale iniziale su coppie di nodi $\varepsilon$ è costruito tramite una combinazione apprendibile dell'identità e di un livello GAT ($I + \alpha \text{GAT}$), inducendo un mixing fuori diagonale dipendente dalle caratteristiche.

Contributi Chiave

1. Espressività Teorica:

   • Approssimazione Universale: Gli autori dimostrano che FSPECGNN lineare può approssimare universalmente segnali su coppie di nodi unidimensionali (Teorema 3.4), estendendo l'universalità delle GNN spettrali dai nodi alle coppie di nodi.
   • Superiorità sul 1-WL: Il lavoro stabilisce che FSPECGNN può superare il limite superiore del 1-WL. Nello specifico, in condizioni di spettro semplice e coefficienti spettrali non nulli, FSPECGNN può raggiungere un'espressività equivalente a Local 2-GNN (un modello spaziale del secondo ordine), e potenzialmente superarlo con specifici polinomi bivariati (Teorema 3.8).

2. Apprendimento su Grafi Eterofili:

   • Gli autori analizzano la convoluzione ottimale per la separazione delle classi nei grafi eterofili. Dimostrano che l'operatore ottimale richiede componenti fuori diagonale nella base spettrale (Teorema 4.1) per sopprimere le connessioni inter-classe.
   • Viene dimostrata una limitazione fondamentale: le convoluzioni spettrali classiche (filtri diagonali) non possono realizzare questo operatore ottimale a meno che non degenerino in un multiplo scalare dell'identità (Teorema 4.2). FSPECGNN, permettendo interazioni spettrali fuori diagonale, può realizzare questo operatore ottimale.

3. Scalabilità:

   • L'approssimazione a rango basso proposta riduce la complessità computazionale a $O(Kmd)$, paragonabile alle GNN spettrali polinomiali esistenti, evitando al contempo il costo $O(n^3)$ della decomposizione spettrale e la memoria $O(n^4)$ delle operazioni esplicite su coppie di nodi.

Risultati Sperimentali

Il lavoro valuta FSPECGNN su tre compiti:

1. Classificazione di Nodi Eterofili:

   • Testato su otto dataset (ad esempio Texas, Wisconsin, Squirrel, Roman Empire).
   • Le varianti di FSPECGNN (utilizzando basi di Chebyshev, ChebNetII e Bernstein) hanno costantemente superato le linee di base spettrali all'avanguardia (ChebNet, GPRGNN, BernNet, ecc.).
   • Studi di ablazione hanno confermato che la rimozione delle interazioni fuori diagonale o del "in-filter" ha degradato significativamente le prestazioni, validando la necessità di modellare l'accoppiamento tra spazi degli autovettori.

2. Conteggio di Sottorestrutture (Validazione dell'Espressività):

   • Valutato su benchmark di omomorfismo e conteggio di cicli (corde).
   • FSPECGNN ha raggiunto prestazioni paragonabili a Local 2-GNN e Local 2-FGNN, confermando la previsione teorica che corrisponde all'espressività dei modelli spaziali del secondo ordine.
   • Ha superato sostanzialmente le GNN invarianti spettrali e le MPNN standard in questi compiti.

3. Efficienza:

   • FSPECGNN ha dimostrato un tempo di esecuzione significativamente inferiore (circa 5 volte più veloce) e un picco di memoria GPU inferiore rispetto alle linee di base spaziali del secondo ordine (Local 2-GNN, Local 2-FGNN, Subgraph GNN).

Significato e Affermazioni

Il lavoro afferma che FSPECGNN fornisce un corrispettivo spettrale fondato per le GNN spaziali di ordine superiore. Il suo significato principale risiede nel colmare il divario tra metodi spettrali ed espressività di ordine superiore:

• Dimostra che l'eterofilia è un fenomeno intrinsecamente del secondo ordine che richiede componenti spettrali fuori diagonale, che le GNN spettrali classiche mancano strutturalmente.
• Offre un'architettura scalabile che mantiene i benefici teorici della modellazione del secondo ordine (superare il 1-WL, approssimazione universale sulle coppie) senza i costi computazionali proibitivi dei metodi spaziali espliciti di ordine superiore.
• Il lavoro identifica una limitazione fondamentale dei filtri spettrali diagonali e propone un framework generalizzabile (estendibile all'$k$-esimo ordine) per superarla.