Sintesi Tecnica: Allineamento di Grafi per il Benchmarking di Reti Neurali su Grafi e Apprendimento di Codifiche Posizionali

Definizione del Problema

Le Reti Neurali su Grafi (GNN) sono ampiamente utilizzate in vari domini come la chimica, la scienza dei materiali e le reti sociali. Tuttavia, valutare la loro comprensione strutturale rimane una sfida. I benchmark esistenti spesso confondono le capacità strutturali con l'apprendimento di caratteristiche (feature learning) o si affidano a compiti di ottimizzazione combinatoria (es. SAT, TSP) che sono legati a specifiche topologie di problemi o modelli sintetici come il Modello a Blocchi Stocastici (SBM), limitandone la generalizzabilità. Inoltre, i metodi attuali faticano a fornire una metrica fine per confrontare i modelli all'interno della stessa classe di espressività (ad esempio, la classe 1-Weisfeiler-Lehman) o per quantificare l'espressività strutturale attraverso diverse topologie di grafi presenti nelle applicazioni reali.

Gli autori propongono di affrontare questo vuoto introducendo una metodologia di benchmarking basata sul Problema dell'Allineamento di Grafi (noto anche come Graph Matching). Questo compito consiste nell'allineare due grafi non etichettati per massimizzare il numero di archi sovrapposti, un problema di ottimizzazione combinatoria che generalizza l'isomorfismo di grafi.

Metodologia

1. Il Compito di Allineamento di Grafi

Il compito principale è definito come la ricerca di una permutazione $\pi^*$ tra due grafi $G$ e $\tilde{G}$ con $N$ vertici che massimizzi la sovrapposenza delle loro matrici di adiacenza:
$$\pi^* \in \arg \max_{\pi \in S_N} \sum_{i,j} A_{i,j} \tilde{A}_{\pi(i),\pi(j)}$$
Questo viene inquadrato come un compito di apprendimento auto-supervisionato. Gli autori impiegano un'architettura Siamese in cui una GNN elabora entrambi i grafi per produrre embedding dei nodi $X$ e $\tilde{X}$. Viene calcolata una matrice di similarità $\Sigma = X\tilde{X}^T$.

• Addestramento: Il modello minimizza la perdita di cross-entropy binaria tra la matrice di similarità predetta e l'allineamento reale (permutazione piantata).
• Valutazione: L'algoritmo di Hungarian risolve il Problema di Assegnazione Lineare su $\Sigma$ per estrarre la permutazione predetta. Le prestazioni sono misurate in termini di percentuale di nodi correttamente mappati.

2. Costruzione del Dataset

Per superare i limiti dei precedenti dataset sintetici (ad esempio, grafi di Erdős-Rényi), gli autori propongono un metodo per generare dataset di Allineamento di Grafi da qualsiasi dataset di grafi esistente (dataset base).

• Generazione di Grafi Correlati: Per un grafo base $G$, un grafo correlato $\tilde{G}$ viene generato aggiungendo e rimuovendo casualmente archi in base a un livello di rumore $\eta$.
• Soluzione Piantata: Poiché l'allineamento ottimale è noto (l'identità o una permutazione nota prima del rumore), la verità fondamentale (ground truth) è disponibile senza dover risolvere il problema NP-difficile.
• Scalabilità: Per grafi di grandi dimensioni (es. OGBN-Arxiv), viene utilizzato un algoritmo di campionamento tramite Ricerca in Ampiezza (BFS) per estrarre sottografi più piccoli che preservino la topologia locale, rendendoli compatibili con le Reti Neurali a Passaggio di Messaggi (MPNN).
• Controllo della Difficoltà: Variando il livello di rumore $\eta$ (dal 4% al 30%), gli autori creano una famiglia di dataset con difficoltà controllabile, permettendo una valutazione sfumata.

3. Apprendimento della Codifica Posizionale (GAPE)

Gli autori sfruttano gli embedding dei nodi appresi dal compito di Allineamento di Grafi come Codifiche Posizionali di Allineamento di Grafi (GAPE). Questi embedding sono destinati a servire come input strutturali per architetture Transformer, che mancano di un accesso intrinseco alla struttura del grafo.

Contributi Chiave

1. Nuovo Compito di Benchmarking: Introduzione del Problema dell'Allineamento di Grafi come benchmark per le GNN, che generalizza il test di Weisfeiler-Lehman e permette la valutazione attraverso diverse topologie (molecolari, sociali, casuali) senza modificare le strutture sottostanti dei grafi.
2. Framework di Generazione Dataset: Una metodologia completa per generare dataset di Allineamento di Grafi sia da dataset sintetici che reali, consentendo la creazione di dataset con diversi livelli di difficoltà.
3. Classifica Empirica delle Architetture: Un benchmark sistematico di MPNN ampiamente utilizzate (GCN, GIN, GatedGCN, GAT, GATv2) dimostra che i modelli anisotropi superano costantemente i modelli isotropi (come GCN e GIN) nell'analisi strutturale, anche su grafi omofilici.
4. Livello di Difficoltà Ottimale: Scoperta di un "livello di rumore ottimale" in cui il divario di prestazioni tra i modelli è massimizzato, fornendo classifiche statisticamente significative e robuste rispetto alle scelte degli iperparametri e ai seed casuali.
5. Codifiche Posizionali (GAPE): Dimostrazione che gli embedding appresi tramite l'Allineamento di Grafi fungono da codifiche posizionali efficaci per i Transformer, superando o eguagliando le codifiche spettrali e basate su random-walk in compiti di regressione molecolare.
6. Ricostruzione del Grafo: Evidenza che gli embedding GAPE comprimono efficacemente la struttura del grafo, permettendo la ricostruzione della matrice di adiacenza completa con un'accuratezza del ~98% utilizzando un semplice decoder.
7. Strumentazione Open-Source: Fornitura di un pacchetto Python per generare questi dataset e testare nuove architetture.

Risultati

• Prestazioni del Modello: Negli esperimenti su cinque dataset base (Erdős-Rényi, AQSOL, PCQM4Mv2, CoraFull, OGBN-Arxiv), le architetture anisotrope (GatedGCN, GAT, GATv2) hanno ottenuto un'accuratezza di allineamento superiore rispetto a quelle isotrope (GCN, GIN).
• Sensibilità al Rumore: Il divario di prestazioni tra i modelli era trascurabile a livelli di rumore molto bassi o molto alti. Il divario ha raggiunto il picco a un livello di rumore ottimale (es. $\eta \approx 15\%$ per i grafi molecolari), dove la significatività statistica era massima.
• Compiti Downstream: Quando utilizzati come codifiche posizionali per i Transformer nella regressione molecolare (AQSOL, PCQM4Mv2, ZINC), GAPE ha ottenuto un errore assoluto medio (MAE) allo stato dell'arte o competitivo rispetto alle codifiche Laplacian, Random Walk e altre codifiche spettrali. Nello specifico, GAPE+RWPE ha ottenuto i migliori risultati su AQSOL e PCQM4Mv2.
• Ricostruzione: Un autoencoder con un encoder GAPE congelato ha ottenuto un'accuratezza superiore al 98% nella ricostruzione della matrice di adiacenza, confermando che gli embedding catturano l'intera topologia del grafo.
• Correlazione: È stata osservata una forte correlazione negativa ($r < -0.90$) tra l'accuratezza dell'Allineamento di Grafi e l'errore di predizione delle proprietà molecolari nei compiti downstream, suggerendo che la capacità di allineamento strutturale sia un collo di bottiglia primario per tali compiti.

Significato e Rivendicazioni

Il paper sostiene di fornire un framework robusto e fine-grained per valutare l'espressività strutturale delle GNN, indipendentemente dalle specifiche caratteristiche di nodi o archi. Isolando la comprensione strutturale, il benchmark rivela che i modelli anisotropi offrono una rappresentazione della topologia del grafo più ricca rispetto ai modelli isotropi precedentemente stabiliti.

Inoltre, gli autori sostengono che il compito di Allineamento di Grafi non sia semplicemente un "puzzle", ma un obiettivo di pre-addestramento fondamentale. Il fatto che gli embedding appresi possano essere utilizzati per l'alta accuratezza della ricostruzione del grafo e migliorino significativamente le prestazioni dei Transformer nei compiti downstream suggerisce che il compito costringa il modello a imparare una compressione ad alta fedeltà della struttura del grafo. Ciò valida l'utilità del benchmark sia per il confronto tra architetture che per la generazione di rappresentazioni utili per applicazioni reali in chimica e scienza dei materiali.

Il lavoro conclude che il benchmark di Allineamento di Grafi offre un approccio flessibile e indipendente dal dominio per la valutazione delle GNN, capace di adattarsi alle specifiche caratteristiche topologiche di qualsiasi dominio applicativo target.