Riepilogo Tecnico: Weisfeiler–Leman è Incompleto su Grafi a Spettro Semplice, quindi Canonizzateli

Enunciato del Problema

Le Reti Neurali su Grafi (GNN) sono ampiamente utilizzate per l'apprendimento su dati strutturati a grafo, ma la loro potenza espressiva è spesso limitata dalla gerarchia di Weisfeiler–Leman (WL). È un risultato noto che il test WL a $k$ dimensioni ($k$-WL) non può distinguere tutti i grafi non isomorfi. Tuttavia, una specifica classe di grafi—quelli con uno spettro semplice (dove la matrice di adiacenza ha autovalori distinti)—ammette un test di isomorfismo in tempo cubico. Nonostante questa trattabilità teorica, rimaneva una questione aperta se la gerarchia WL, che limita superiormente l'espressività di molte GNN, potesse distinguere tutti i grafi a spettro semplice.

Inoltre, mentre le codifiche posizionali spettrali (ad esempio, autovettori del Laplaciano) sono comunemente integrate nelle GNN per migliorare l'espressività, esse soffrono di ambiguità intrinseche: ambiguità di segno per gli spettri semplici e ambiguità di base per autovalori ripetuti. I metodi esistenti per risolvere queste ambiguità (come SignNet, MAP e OAP) sono dimostrabilmente incompleti sui grafi a spettro semplice, fallendo nel distinguere certe coppie non isomorfe. Questa incompletezza limita la capacità delle GNN spettrali di raggiungere l'approssimazione universale su questa classe di grafi.

Metodologia

1. Dimostrazione dell'Incompletezza di WL sugli Spettri Semplici

Gli autori stabiliscono innanzitutto che l'intera gerarchia WL è incompleta sui grafi a spettro semplice.

• Costruzione: Utilizzano la costruzione di Cai–Fürer–Immerman (CFI), che genera coppie di grafi non isomorfi indistinguibili dal $k$-WL.
• Codifica: Poiché i grafi CFI standard non possiedono uno spettro semplice, gli autori introducono un nuovo meccanismo di codifica integrale. Mappano i pattern di adiacenza CFI in una matrice ortogonale $\tilde{X}$ composta da interi.
• Formazione di Multigrafi: Utilizzando questa matrice ortogonale e una matrice diagonale di autovalori interi distinti, costruiscono una coppia di multigrafi simmetrici ($A_{G,0}$ e $A_{G,1}$) con spettri semplici.
• Risultato: Dimostrano che questi multigrafi a spettro semplice costruiti rimangono indistinguibili dal test $k$-WL, dimostrando che nessun livello della gerarchia WL può risolvere il problema dell'isomorfismo per questa classe, nonostante il problema sia risolvibile in tempo cubico.

2. PRiSM: Una Canonizzazione Completa

Per affrontare i limiti dei metodi spettrali esistenti, gli autori propongono PRiSM (Partition, Refine, Solve, Match), una procedura di canonizzazione dimostrabilmente completa per le decomposizioni spettrali di grafi a spettro semplice.

• Input: Una matrice ortonormale per colonne $U$ di autovettori.
• Gruppo di Ambiguità: La procedura gestisce il gruppo di ambiguità $S_n \times \{-1, 1\}^k$ (permutazioni e inversioni di segno).
• Quattro Fasi:
  1. Partizione: I vertici sono raggruppati in base alle loro firme invarianti rispetto al segno (valori assoluti delle voci degli autovettori).
  2. Raffinamento: Viene applicata una variante spettrale della procedura di raffinamento dei colori WL alla partizione. Questo raffina iterativamente le classi di vertici utilizzando il multinsieme delle caratteristiche degli archi definite dai prodotti elemento per elemento delle voci degli autovettori ($U_v \odot U_u$) fino a quando la partizione non si stabilizza.
  3. Risoluzione: La partizione stabile definisce un sistema di equazioni lineari sul campo $\mathbb{Z}_2$. Il sistema impone che ogni classe di partizione contenga almeno una riga con voci non negative. Risolvere questo sistema determina i segni canonici unici per gli autovettori (a meno di automorfismi del grafo).
  4. Corrispondenza: Una volta fissati i segni, le righe vengono ordinate lessicograficamente per risolvere l'ambiguità di permutazione, producendo una matrice canonica unica.
• Estensione: Per grafi con autovalori ripetuti (spettro non semplice), PRiSM viene esteso euristica. Applica la procedura di base al blocco a spettro semplice ($m=1$) e utilizza la decomposizione QR e la selezione dei pivot per risolvere gli spazi propri di ordine superiore ($m > 1$).

3. Garanzie Teoriche

• Completezza: PRiSM è dimostrato essere una canonizzazione valida, il che significa che produce lo stesso output per grafi isomorfi e output diversi per grafi a spettro semplice non isomorfi.
• Approssimazione Universale: Componendo PRiSM con una rete di insiemi universale (ad esempio, DeepSets o Transformers), il modello risultante raggiunge l'approssimazione universale per qualsiasi funzione invariante rispetto all'isomorfismo su grafi a spettro semplice. Questo risolve il problema aperto di raggiungere la completezza per le GNN spettrali su questa classe.

Risultati Chiave

Risultati Teorici

• Teorema 1: Per ogni numero naturale $k$, esistono multigrafi a spettro semplice non isomorfi con $\Theta(k)$ nodi che non sono distinti dall'algoritmo $k$-WL. Ciò implica che tutte le famiglie di GNN allineate a $k$-WL (inclusi PPGN, $k$-GNN e Graph Transformers) sono incomplete sui grafi a spettro semplice.
• Teorema 2: PRiSM fornisce una canonizzazione valida per le decomposizioni spettrali a spettro semplice.
• Teorema 3: I modelli composti da PRiSM e reti di insiemi universali raggiungono l'approssimazione universale sui grafi a spettro semplice.

Performance Empiriche

Gli autori hanno valutato PRiSM su tre benchmark:

1. Benchmark di Espressività BREC: PRiSM ha superato le canonizzazioni concorrenti (MAP, OAP) nel distinguere coppie di grafi non isomorfi, in particolare nelle categorie Regular e Extension. Ha correttamente distinto 212/360 coppie rispetto a 199/360 per MAP/OAP.
2. Predizione di Proprietà Molecolari (ZINC, OGB-Mol): PRiSM ha raggiunto prestazioni all'avanguardia o pari alle migliori su compiti di regressione molecolare (ZINC) e classificazione (MOLTOX21, MOLPCBA) utilizzando sia backbones GatedGCN che PNA.
3. Backbones Transformer (OGB, Alchemy): Quando utilizzato come codifica posizionale per i Graph Transformers, PRiSM ha superato tutti i baseline (LPE, MAP, OAP) su tutti e quattro i dataset (MOLHIV, MOLCLINTOX, MOLBBBP, ALCHEMY). Gli autori attribuiscono questo fatto al fatto che PRiSM fornisce un ordinamento deterministico dei vertici oltre agli autovettori corretti per il segno, il che è cruciale per i meccanismi di attenzione dei Transformer.

Significato e Affermazioni

Il documento afferma di risolvere un divario fondamentale nella comprensione teorica dell'espressività delle GNN e dei metodi spettrali:

1. Incompletezza di WL: Dimostra definitivamente che la gerarchia WL, nonostante il suo potere crescente, non può distinguere tutti i grafi a spettro semplice, una classe in cui l'isomorfismo è teoricamente semplice.
2. Prima Canonizzazione Completa: PRiSM è presentato come la prima canonizzazione di segno dimostrabilmente completa per le decomposizioni spettrali a spettro semplice, superando i limiti di metodi precedenti come MAP e OAP che sono incompleti su questa classe.
3. Approssimazione Universale: Il lavoro stabilisce che le GNN spettrali possono raggiungere l'approssimazione universale su grafi a spettro semplice se accoppiate con una canonizzazione completa come PRiSM, giustificando l'uso di codifiche posizionali del Laplaciano canonizzate.
4. Utilità Pratica: Empiricamente, il metodo dimostra che la risoluzione completa delle ambiguità spettrali porta a miglioramenti tangibili nei compiti a valle, superando gli approcci esistenti invarianti al segno e di canonizzazione.

Gli autori notano dei limiti, specificamente che la garanzia di completezza si applica rigorosamente ai grafi a spettro semplice (o multigrafi costruiti nella dimostrazione) e che la procedura di canonizzazione è discontinua, una proprietà che sostengono sia matematicamente inevitabile per le canonizzazioni di segno complete. Lasciano inoltre l'estensione della dimostrazione di incompletezza ai grafi combinatori semplici (senza archi multipli) come lavoro futuro.