Riepilogo Tecnico: Un Strato Tikhonov Generalizzato per Reti Neurali su Grafi Interpretabili per Design

Enunciato del Problema

Le Reti Neurali su Grafi (GNN) hanno ottenuto successi significativi nei compiti di classificazione di grafi e nodi imparando ad aggregare le caratteristiche sulla topologia del grafo. Tuttavia, la loro interpretabilità rimane una sfida critica. A differenza delle reti neurali classiche, le GNN devono spiegare non solo come le caratteristiche di input vengono trasformate, ma anche come la topologia del grafo stessa viene sfruttata. I metodi di interpretabilità esistenti spesso si basano su approssimazioni post-hoc (ad esempio, GNNExplainer, salienza del gradiente) che mancano di garanzie di fedeltà, o su architetture a due moduli in cui un estrattore di spiegazioni è disaccoppiato dal classificatore, permettendo al classificatore di ignorare la spiegazione mentre minimizza la perdita. Inoltre, le GNN profonde soffrono di patologie come l'oversmoothing (collasso delle rappresentazioni dei nodi) e l'oversquashing (decadimento esponenziale della sensibilità a lungo raggio).

Metodologia

Gli autori propongono lo strato Tikhonov, uno strato di rete neurale su grafo progettato per essere interpretabile per costruzione. L'innovazione centrale risiede nel vincolare la matrice di propagazione del grafo $R$ a una specifica soluzione in forma chiusa derivata da un problema di regolarizzazione Tikhonov generalizzato su grafi.

L'Operatore di Propagazione

Per un grafo con laplaciano normalizzato $L$, l'output dello strato per le caratteristiche di input $X$ è dato da:
$$X^{(k+1)} = \sigma \left( R X^{(k)} W \right)$$
dove la matrice di propagazione $R$ è definita come:
$$R = (p(L) + Q)^{-1} Q$$
Qui:

• $L$ è il laplaciano normalizzato del grafo.
• $Q = \text{diag}(q_1, \dots, q_n)$ è una matrice diagonale apprendibile di punteggi di importanza dei nodi strettamente positivi.
• $p(\cdot)$ è un polinomio apprendibile che soddisfa $0 < p(\lambda) < 1$ per $\lambda \in [0, 2]$.
• $\sigma$ è una non-linearità punto a punto e $W$ è una matrice di pesi.

Interpretazione Variazionale

L'operatore $R$ è il minimizzatore unico in forma chiusa del problema Tikhonov generalizzato:
$$R x = \arg \min_{z \in \mathbb{R}^n} \sum_{i \in V} q_i (x_i - z_i)^2 + z^\top p(L) z$$
Questa formulazione scambia esplicitamente la fedeltà ai dati a livello di nodo (pesata da $q_i$) con la regolarizzazione guidata dalla topologia (governata da $p(L)$).

• $q_i$ grande: Il nodo $i$ si affida pesantemente alle proprie caratteristiche; l'output $z_i$ rimane vicino a $x_i$.
• $q_i$ piccolo: Il nodo $i$ scarta le proprie caratteristiche a favore di una soluzione guidata dalla topologia del grafo (liscezza o proprietà spettrali specifiche definite da $p$).
• Forma di $p(\lambda)$: Determina la natura dell'influenza topologica. Un $p$ crescente penalizza le alte frequenze (favorendo l'omofilia/liscezza), mentre un $p$ decrescente penalizza le basse frequenze (favorendo l'eterofilia).

Architettura e Espressività

Per mantenere un'elevata espressività senza sacrificare l'interpretabilità, l'architettura impiega una separazione delle responsabilità:

1. La Rete Q: Una GNN dedicata, potenzialmente profonda (ad esempio, ChebNet o ARMA), che prende in input il grafo $(G, X)$ e restituisce i punteggi di importanza dei nodi $Q$. Questo componente gestisce l'apprendimento rappresentazionale complesso e adatta $q_i$ alle strutture e alle caratteristiche locali del grafo.
2. Lo Strato Tikhonov: Un singolo strato trasparente che applica la propagazione $R$. Non contiene non-linearità nascoste o passaggi complessi di passaggio messaggi; i suoi parametri sono i coefficienti polinomiali di $p$ e gli output della rete Q.
3. Testa (Head): Un'operazione di pooling globale seguita da un MLP per la previsione finale.

Il modello supporta estensioni multicanale in cui vengono utilizzate più reti Q e polinomi indipendenti, sebbene gli esperimenti si concentrino sul caso a canale singolo ($J=1$).

Dettagli di Implementazione

• Calcolo: Il calcolo di $(p(L) + Q)^{-1}QX$ comporta la risoluzione di sistemi lineari. Gli autori utilizzano il Gradiente Coniugato Precondizionato (PCG) con un precondizionatore diagonale (Jacobi) per evitare il costo $O(n^3)$ dell'inversione densa, raggiungendo una scalabilità $O(dTKm)$ dove $T$ è il numero di iterazioni.
• Differenziazione: Per evitare di memorizzare il grafo computazionale del solver, gli autori utilizzano la differenziazione implicita, richiedendo solo un'ulteriore risoluzione PCG nel passaggio all'indietro per calcolare i gradienti rispetto a $Q$ e $p$.
• Vincoli: Il polinomio $p(\lambda)$ è parametrizzato utilizzando polinomi di Bernstein con attivazioni sigmoide per imporre rigorosamente $0 < p(\lambda) < 1$. I punteggi $q_i$ sono mappati su valori strettamente positivi tramite una funzione di limitazione nello spazio logaritmico.

Contributi Chiave e Proprietà Teoriche

1. Interpretabilità Integrata: La coppia $\{ \{q_i\}_{i \in V}, p(\cdot) \}$ costituisce una spiegazione diretta e fedele. Un $q_i$ grande indica affidamento alle caratteristiche; un $q_i$ piccolo indica affidamento alla topologia. La forma di $p$ rivela il bias spettrale (omofilia, eterofilia, passa-banda).
2. Accoppiamento Strutturale: Gli autori dimostrano (Proposizione 3.6) che la mappa $Q \mapsto R$ è iniettiva. A differenza dei metodi post-hoc, cambiare la spiegazione ($Q$) cambia necessariamente l'operatore di propagazione ($R$), garantendo che la spiegazione sia fedele al calcolo.
3. Espressività: È dimostrato che lo strato è denso nello spazio dei filtri spettrali continui nel caso omogeneo. Con $Q$ eterogeneo, estende rigorosamente l'espressività oltre i filtri spettrali tradizionali rompendo la stazionarietà (Proposizione 3.3).
4. Mitigazione delle Patologie delle GNN:
   • Oversmoothing: Evitato utilizzando un singolo strato e l'invertibilità di $p(L) + Q$. Il collasso dei nodi si verifica solo se il modello guida deliberatamente tutti i $q_i \to 0$.
   • Oversquashing: Il tasso di decadimento della sensibilità a lungo raggio $|R_{ij}|$ è governato dal numero di condizione $\kappa$ del sistema, che dipende dalla $Q$ appresa. Il modello può imparare a ridurre $\kappa$ (abbassando specifici $q_i$) per aumentare la sensibilità a lungo raggio dove necessario, scambiando efficacemente la precisione locale con la portata globale.

Risultati Sperimentali

Il modello è stato valutato su benchmark sintetici e standard, dimostrando sia prestazioni che interpretabilità:

• Compiti Sintetici Controllati:
  • Colors-3: Il compito si basa esclusivamente sulle caratteristiche dei nodi. Il modello ha imparato $q_i$ grandi ovunque, ignorando efficacemente la topologia e comportandosi come un MLP, identificando correttamente che le caratteristiche guidano la previsione.
  • Distanza da Cliques: Un compito puramente strutturale. Il modello ha imparato $q_i$ piccoli per i nodi del percorso (affidandosi alla topologia per percepire la distanza) e $q_i$ grandi per i nodi della cliqua (ancore), raggiungendo il 100% di accuratezza.
  • Triangoli: Un compito strutturale per il rilevamento di triangoli. Il modello ha assegnato $q_i$ piccoli in generale ma $q_i$ più grandi ai vertici del triangolo, individuando il motivo senza supervisione.
• CSBM (Modello a Blocchi Stocastici Contestualizzato): Il modello ha tracciato con successo la soglia teorica di transizione di fase per il recupero. I valori di $q_i$ appresi sono transitati fluidamente da regimi dominati dalle caratteristiche ($q_i$ grandi) a regimi dominati dalla topologia ($q_i$ piccoli), identificando correttamente la fonte del segnale in regimi misti.
• ECHO-diam (Propagazione a Lungo Raggio): Su un compito di regressione del diametro del grafo, il modello ha raggiunto un Errore Assoluto Medio (MAE) di 1.17, superando le baseline GNN profonde (~1.6) e avvicinandosi alle prestazioni dei Transformer (1.05). La spiegazione ha rivelato che il modello ha assegnato $q_i$ grandi ai nodi periferici (punti finali) e $q_i$ piccoli ai nodi interni, utilizzando il contrasto tra punti finali ancorati e interno lisciato per stimare il diametro.

Significato e Affermazioni

Il paper afferma che lo strato Tikhonov offre un approccio innovativo all'interpretabilità delle GNN progettando lo strato per essere auto-spiegante invece di recuperare spiegazioni post-hoc.

• Fedeltà: La spiegazione è il modello stesso; non c'è sottografo disaccoppiato o approssimazione.
• Granularità: Fornisce una risposta continua e risolta spazialmente (valori di $q_i$ graduati) invece di una selezione binaria di sottografi.
• Prestazioni: Il modello corrisponde o supera le baseline opache (come GIN, GAT e Transformer) su vari compiti fornendo allo stesso tempo intuizioni su come viene risolto il compito (ad esempio, distinguendo tra ragionamento basato su caratteristiche e basato su topologia).
• Limitazioni: Gli autori riconoscono che alcune spiegazioni possono essere complesse da interpretare per gli esseri umani e che il costo computazionale del PCG può essere elevato per compiti che richiedono interazioni a lungo raggio (sebbene suggeriscano l'algebra lineare numerica casuale come direzione futura per l'approssimazione).

Il lavoro stabilisce che è possibile vincolare gli strati delle GNN a forme variazionali specifiche per ottenere interpretabilità senza sacrificare la capacità di apprendere filtri su grafi complessi e non stazionari.