Manifold GCN: Diffusion-based Convolutional Neural Network for Manifold-valued Graphs

Sintesi Tecnica: Manifold GCN

Definizione del Problema

Le Reti Neurali a Grafo (GNN) sono diventate uno standard per l'analisi di dati strutturati a grafo, eppure la stragrande maggioranza di esse si basa su spazi di caratteristiche euclidei. Tuttavia, molte applicazioni del mondo reale coinvolgono dati che risiedono su varietà riemanniane non piatte, come sfere, il gruppo speciale ortogonale $SO(3)$, spazi di matrici simmetriche definite positive (SPD), varietà di Stiefel e varietà di Grassmann. Le architetture GNN esistenti progettate per caratteristiche con valori su varietà sono tipicamente limitate a tipi specifici di varietà (ad esempio, spazi a curvatura costante o matrici SPD) e non riescono a gestire varietà riemanniane generiche. Inoltre, la maggior parte dei modelli esistenti non sfrutta le regolarità geometriche (isometrie) dello spazio delle caratteristiche, portando a prestazioni subottimali a causa della mancanza di equivarianza e di un aumento della necessità di dati di addestramento per apprendere tali simmetrie.

Metodologia

Gli autori propongono una nuova architettura GNN, Manifold GCN, progettata per operare su grafi con caratteristiche in varietà riemanniane arbitrarie, a condizione che le geodetiche possano essere approssimate efficientemente. L'architettura consiste in due layer primari che sono equivarianti sia sotto permutazioni dei nodi che sotto le isometrie della varietà delle caratteristiche:

1. Manifold Diffusion Layer (Layer di Diffusione su Varietà)

Questo layer discretizza un'equazione di diffusione su grafo con valori in varietà.

• Meccanismo: Risolve l'equazione di diffusione $\frac{\partial}{\partial t} f(v, t) = -\Delta f(v, t)$ utilizzando uno schema di Eulero esplicito. Il Laplaciano del grafo $\Delta$ è definito utilizzando la mappa logaritmo riemanniana per aggregare le caratteristiche dai nodi vicini.
• Nonlinearità: Per prevenire il collasso della profondità (depth collapse) e mantenere l'equivarianza, gli autori introducono una nuova funzione di attivazione $\sigma_p^\theta$ equivariante rispetto alle isometrie che agisce sui vettori tangenti. Questa funzione scala i vettori tangenti in base alla loro norma utilizzando una funzione sigmoide.
• Operazione: Il layer esegue $\ell$ passi di diffusione "con attivazione non lineare", aggregando le informazioni su vicinati di $\ell$-hop. Mappa le caratteristiche di input $f$ in nuove caratteristiche tramite la mappa esponenziale: $step_{t,\theta}(f)(v) = \exp_{f(v)}(-t \sigma_{f(v)}^\theta(\Delta f(v)))$.
• Equivarianza: Il layer è dimostrato essere equivariante sotto permutazioni dei nodi e trasformazioni isometriche della varietà delle caratteristiche.

2. Tangent Multilayer Perceptron (tMLP)

Questo layer agisce come una "convoluzione 1x1" per trasformare le caratteristiche dei nodi e alterare la larghezza della rete, generalizzando il classico MLP alle varietà.

• Meccanismo: Mappa le caratteristiche dei nodi verso uno spazio tangente di riferimento (ad esempio, lo spazio tangente in una caratteristica selezionata o nella media di Fréchet).
• Trasformazione: Apprende combinazioni lineari per definire le direzioni nello spazio tangente. Successivamente, applica un'attivazione scalare non lineare (ad esempio, ReLU) alla proiezione delle caratteristiche su queste direzioni.
• Output: I vettori tangenti trasformati vengono mappati nuovamente sulla varietà tramite la mappa esponenziale.
• Equivarianza: Come il layer di diffusione, il tMLP è equivariante sotto permutazioni dei nodi e isometrie della varietà.

Architettura della Rete

La rete completa combina questi layer in una sequenza: $Diff \to tMLP \to \dots \to Diff \to tMLP$. Per i compiti di classificazione, l'output viene passato attraverso un layer invariante rispetto alla varietà (calcolando le distanze dalle medie pesate), seguito da un pooling globale (max/mean) e un MLP finale. Gli autori raccomandano inoltre di normalizzare i pesi degli archi per garantire passi di diffusione stabili.

Contributi Chiave

1. Supporto per Varietà Generiche: A differenza dei lavori precedenti limitati a specifiche varietà (ad esempio, iperboliche o SPD), questa architettura supporta caratteristiche provenienti da qualsiasi varietà riemanniana in cui le geodetiche siano computabili.
2. Layer Equivarianti: Gli autori sono i primi a sviluppare layer GNN per varietà generiche che esibiscono l'equivarianza sia sotto permutazioni dei nodi che sotto le isometrie dello spazio delle caratteristiche. Ciò fornisce un forte bias induttivo.
3. Nuova Attivazione: La proposta di una funzione di attivazione con valori in varietà ed equivariante rispetto alle isometrie che agisce sui vettori tangenti.
4. Strategie di Embedding Flessibili: L'equivarianza permette nuove strategie di design delle caratteristiche, come l'uso di embedding "one-hot" che vengono permutati tramite isometrie, cosa che precedentemente era incompatibile con le reti invarianti per permutazione.

Risultati Sperimentali

Gli autori hanno valutato Manifold GCN su due compiti di classificazione:

1. Classificazione di Grafi Sintetici

• Task: Classificare grafi generati dagli algoritmi di Erdős-Rényi, Barabási-Albert o Watts-Strogatz.
• Configurazione: Confronto con lo stato dell'arte delle GNN iperboliche (HGNN, H2H-GCN) utilizzando spazi di embedding iperbolici e SPD.
• Risultati:
  • Manifold GCN con un embedding "one-hot" ha superato i competitor in tutti i set di dati, particolarmente su dataset piccoli (ad esempio, 90–360 grafi).
  • Ha ottenuto questo risultato con significativamente meno parametri addestrabili (ad esempio, 1.970 contro 161.903 per HGNN).
  • Il metodo ha dimostrato che lo spazio SPD non è necessariamente superiore allo spazio iperbolico per questo specifico compito.

2. Classificazione della Malattia di Alzheimer (AD)

• Task: Classificare soggetti con AD rispetto a soggetti cognitivamente normali (CN) utilizzando mesh triangolari dell'ippocampo destro.
• Caratteristiche: Sono stati testati due tipi di caratteristiche: normali di superficie (varietà $S^2$) e coordinate differenziali (varietà $SO(3) \times SPD(3)$).
• Confronto: Confronto con DiffusionNet, MeshCNN e un baseline GNN euclideo.
• Risultati:
  • I modelli proposti hanno raggiunto l'accuratezza più elevata (75,3% per le normali, 76,9% per le coordinate differenziali) nonostante avessero il minor numero di parametri tra tutti i metodi testati.
  • Gli studi di ablazione hanno confermato che rimuovere i layer di diffusione, i tMLP o rompere l'equivarianza degradava significativamente le prestazioni.
  • I risultati evidenziano l'importanza di rispettare la geometria sottostante (ad esempio, la simmetria sferica per le normali) per il riconoscimento di pattern.

Significato e Rivendicazioni

Il paper afferma che Manifold GCN offre un paradigma unificante per l'apprendimento su grafi con dati con valori in varietà. La sua importanza primaria risiede in:

• Ampia Applicabilità: Estende le capacità delle GNN oltre le varietà a curvatura costante o SPD a varietà complesse come i gruppi di rotazione e gli spazi di forma.
• Efficienza dei Dati: Il bias induttivo dell'equivarianza permette alla rete di funzionare bene con dati di addestramento scarsi, un vantaggio critico in domini come l'imaging medico dove i dati sono limitati.
• Apprendimento di Rappresentazioni Geometriche: Sfruttando l'equivarianza rispetto alle isometrie, la rete può utilizzare strategie di embedding (come le codifiche one-hot) che prima erano inaccessibili ai modelli invarianti per permutazione, portando a una migliore separazione dei nodi embedded e a migliori prestazioni di classificazione.

Gli autori concludono che, sebbene il loro metodo superi le reti allo stato dell'arte specifiche per compito, il lavoro futuro dovrebbe esplorare schemi di diffusione implicita per affrontare l'over-squashing, l'uso di $p$-Laplaciani e l'integrazione di meccanismi di attenzione.