Sintesi Tecnica: Comprendere i Codifiche Posizionali Troncate per le Graph Neural Networks

Definizione del Problema

Le Graph Neural Networks (GNN), in particolare le Message Passing Neural Networks (MPNN), sono fondamentalmente limitate nella capacità di catturare informazioni strutturali globali, un vincolo formalizzato dalla loro equivalenza al test 1-Weisfeiler-Lehman (1-WL). Per superare questo limite, i Graph Transformer (GT) e le GNN potenziate utilizzano le Codifiche Posizionali (PE) per iniettare informazioni strutturali. Due famiglie dominanti di PE sono le codifiche spettrali (derivate dagli spazi eigenspaziali del Laplaciano) e le codifiche basate su cammini (walk-based, derivate dalle potenze della matrice di adiacenza).

Teoricamente, le versioni complete di queste codifiche (utilizzando $\Omega(n)$ autovettori o potenze di matrici) sono equivalenti in termini di potere espressivo, ponendosi tra i test 1-WL e 3-WL. Tuttavia, il calcolo di queste codifiche complete richiede una complessità temporale e spaziale di $O(n^3)$, il che è proibitivo per applicazioni nel mondo reale. Di conseguenza, i professionisti si affidano a varianti troncate (ad esempio, i primi $k$ autovettori o le prime $k$ potenze della matrice di adiacenza). Le proprietà teoriche, il potere espressivo e i punti di forza comparativi di queste PE troncate rimangono ampiamente inesplorati, creando un divario tra le garanzie teoriche e l'implementazione pratica.

Metodologia

Gli autori avviano uno studio sistematico delle PE troncate attraverso sia l'analisi teorica che la validazione empirica.

Framework Teorico

Il documento utilizza la gerarchia WL e le sue varianti per caratterizzare il potere espressivo di diverse PE:

• Test $\psi$-WL: Una variante del test WL in cui i colori dei nodi vengono aggiornati utilizzando una codifica posizionale relativa (RPE) $\psi$.
• Test Sparse-$\psi$-WL: Un'estensione per le MPNN in cui $\psi$ viene utilizzato come feature degli archi.
• Famiglie Chiave Analizzate:
  1. Proiezioni dello Spazio Eigenspaziale Troncate ($k$-EP-WL): Utilizzando le prime $k$ proiezioni dello spazio eigenspaziale del Laplaciano.
  2. Codifiche di Cammino Troncate ($k$-Walk-WL): Utilizzando le prime $k$ potenze della matrice di adiacenza.
  3. Resistenza Effettiva (Resistance-WL): Una specifica distanza spettrale (distanza 1-armonica).
  4. Distanze $k$-armoniche: Una generalizzazione della resistenza effettiva definita come $H_k(u, v) = \sqrt{(1_u - 1_v)^T (L^+)^k (1_u - 1_v)}$.

Gli autori costruiscono coppie di grafi specifiche (ad esempio, prodotti di grafi path e grafi completi, o cicli rispetto a unioni disgiunte di cicli) per dimostrare la separabilità o l'indistinguibilità sotto diverse PE troncate e test WL.

Valutazione Empirica

Gli esperimenti sono stati condotti su tre benchmark:

1. BREC: Un dataset progettato per misurare la "espressività realizzata" delle GNN testando la loro capacità di distinguere grafi non isomorfi che vanno da indistinguibili per 1-WL a 4-WL.
2. ZINC-12k: Un benchmark di regressione di grafi per la solubilità molecolare, utilizzato per testare l'ipotesi che mescolare le PE troncate migliori le prestazioni.
3. ogbg-molhiv: Un benchmark di classificazione binaria per l'inibizione dell'HIV.

Gli autori hanno valutato architetture Graphormer-GD e MPNN (GINE) utilizzando varie combinazioni di PE troncate, incluse singole famiglie e miscele di codifiche spettrali, di cammino e $k$-armoniche.

Contributi Chiave e Risultati

1. Divergenza del Potere Espressivo nelle Forme Troncate

Il documento dimostra che, sebbene le codifiche spettrali e di cammino complete siano equivalenti, le loro forme troncate sono fondamentalmente diverse:

• Spettrale Troncata vs 1-WL: Gli autori mostrano che le proiezioni dello spazio eigenspaziale troncate ($k$-EP-WL) possono essere più deboli del test 1-WL. Nello specifico, esistono coppie di grafi distinguibili dal 1-WL ma indistinguibili dal $k$-EP-WL per $k \in \Omega(n)$ (Teorema 4.1).
• Cammino Troncato vs Spettrale: Al contrario, esistono coppie di grafi distinguibili da una singola proiezione dello spazio eigenspaziale (1-EP-WL) ma indistinguibili da codifiche di cammino di dimensione $\Omega(n)$ (Teorema 4.2).
• Implicazione: Nessuna singola famiglia di PE troncate è strettamente superiore; esse catturano aspetti strutturali differenti e possono essere incomparabili con la gerarchia WL standard.

2. Limitazioni della Resistenza Effettiva

Il documento analizza la Resistenza Effettiva (distanza 1-armonica) e scopre che è una PE più debole rispetto alle proiezioni dello spazio eigenspaziale complete o alle codifiche di cammino su grafi pesati.

• Teorema 4.3: Esistono grafi pesati indistinguibili dal Resistance-WL ma distinguibili dall'Adjacency-WL (e quindi dal 1-WL su grafi non pesati).
• Corollario 4.1: Il Resistance-WL non codifica l'intero spettro del grafo, smentendo una precedente congettura.

3. Le Distanze $k$-armoniche come Ponte

Gli autori introducono le distanze $k$-armoniche come un ponte naturale tra le codifiche polinomiali e quelle spettrali.

• Completezza: La concatenazione di $\Theta(n)$ distanze $k$-armoniche produce una codifica equivalente in potenza alle codifiche spettrali o di cammino complete (Teorema 4.6).
• Potere Differenziale: Anche all'interno della famiglia $k-armonica$, le codifiche a dimensione fissa differiscono. Ad esempio, la distanza biarmonica (2-armonica) può distinguere determinate coppie di alberi in un numero costante di iterazioni, mentre la resistenza effettiva (1-armonica) ne richiede $O(n)$ (Teorema 4.7).
• Robustezza: Tuttavia, se una distanza $k$-armonica distingue una coppia di grafi, la maggior parte delle altre distanze $k$-armoniche le distinguerà comunque (Teorema 4.8).

4. Risultati Empirici: Il Potere della Miscelazione

• Risultati BREC: Le distanze $k$-armoniche hanno ottenuto risultati competitivi con le codifiche a canale singolo e basso overhead, spesso eguagliando il limite teorico per grafi compresi tra 1-WL e 3-WL.
• Risultati ZINC: Il risultato più significativo è che mescolare le PE di diverse famiglie (ad esempio, combinando cammini troncati e $k$-armoniche) supera qualsiasi singola famiglia. Una miscela di cammini troncati e $k$-armoniche ha raggiunto il Mean Absolute Error (MAE) più basso su ZINC-12k, superando i baseline a singola famiglia.
• Efficienza: Il documento nota che le distanze $k$-armoniche possono essere approssimate in $O(mk \cdot \text{poly}(\log n))$ tempo utilizzando solver Laplaciani veloci e proiezioni di Johnson-Lindenstrauss, evitando il costo di $O(n^3)$ del calcolo esatto.

Significato e Rivendicazioni

Il documento sostiene di avviare lo studio teorico delle codifiche posizionali troncate, spostando la prospettiva dal vederle semplicemente come approssimazioni di codifiche complete al vederle come uno spazio di progettazione distinto con proprietà espressive uniche.

• Intuizione Teorica: Il lavoro dimostra che la troncatura altera fondamentalmente le informazioni catturate dalle PE, rendendole incomparabili con la gerarchia WL standard in casi specifici.
• Guida Pratica: Gli autori propongono una regola empirica: mescolare le PE di diverse famiglie quando si utilizzano codifiche troncate. Questo approccio cattura indizi strutturali complementari controllando al contempo i costi computazionali.
• Ambito Modesto: Gli autori riconoscono che, sebbene l'isomorfismo dei grafi sia un proxy fondato, i compiti del mondo reale coinvolgono segnali a valle (centralità, motivi) che potrebbero non allinearsi strettamente con i test di isomorfismo. Pertanto, il contributo primario è stabilire una base teorica e un punto di partenza per uno studio empirico sistematico, piuttosto che rivendicare una soluzione universale per tutti i compiti di apprendimento sui grafi.