Riepilogo Tecnico: Contrastive FUSE

Enunciato del Problema

Il documento affronta la sfida di apprendere rappresentazioni significative dei nodi in grafi dove le caratteristiche esplicite dei nodi sono assenti, inaffidabili o non trasferibili (grafi privi di caratteristiche o con caratteristiche sparse). A differenza dei metodi standard di embedding non supervisionato per grafi che si basano esclusivamente sulla struttura del grafo, o dei metodi di apprendimento contrastivo auto-supervisionato che dipendono da aumentazioni dei dati, questo lavoro si concentra su un contesto in cui la supervisione è disponibile solo sotto forma di vincoli parziali a coppie. Tali vincoli indicano se due nodi debbano essere simili (must-link) o dissimili (cannot-link), uno scenario comune in domini come la biologia computazionale (ad esempio, la previsione della letalità sintetica), i sistemi di raccomandazione (feedback implicito) e le reti sensibili alla privacy dove gli attributi dei nodi sono inaccessibili.

L'obiettivo è sviluppare un framework rapido e scalabile che apprenda embedding discriminativi dei nodi ottimizzando congiuntamente:

1. Coerenza Strutturale: Preservare la struttura globale delle comunità del grafo.
2. Coerenza a Coppie: Rispettare i vincoli a coppie con segno forniti (attrarre coppie simili, respingere coppie dissimili).

Metodologia: Contrastive FUSE

Gli autori propongono Contrastive FUSE, un framework unificato che integra l'apprendimento strutturale basato sulla modularità con la supervisione contrastiva attraverso una formulazione spettrale.

1. Funzione Obiettivo

L'obiettivo principale $J(S)$ combina un termine strutturale e un termine contrastivo:
$$J(S) = \text{Tr}(S^\top \tilde{B}S) - \lambda \text{Tr}(S^\top L_c S)$$

• Termine Strutturale (Modularità): Il primo termine massimizza la modularità, incoraggiando i nodi all'interno della stessa comunità ad avere embedding simili. Gli autori utilizzano una matrice di modularità modificata $\tilde{B} = A - \frac{d\mathbf{1}^\top}{2m}$, dove $A$ è la matrice di adiacenza, $d$ è il vettore dei gradi e $m$ è il numero totale di archi.
• Termine Contrastivo: Il secondo termine utilizza un Laplaciano contrastivo con segno e normalizzato ($L_c$) costruito dalla matrice di supervisione a coppie $Y$ (dove $Y_{ij} \in \{+1, -1, 0\}$). Questo termine agisce come regolarizzatore che avvicina le coppie positive e allontana le coppie negative nello spazio degli embedding, normalizzato per il grado contrastivo di ciascun nodo per evitare la dominanza di nodi fortemente vincolati.

2. Ottimizzazione Efficiente tramite Approssimazione del Gradiente

Un'innovazione chiave riguarda la gestione del gradiente della modularità. Il gradiente esatto dell'obiettivo di modularità comporta un termine di correzione grado-grado ($d(d^\top S)$), che è computazionalmente costoso e numericamente instabile per grafi grandi e densi.

• Approssimazione: Gli autori propongono un'approssimazione leggera sostituendo l'aggregazione dei gradi ponderati $d^\top S$ con la somma globale non ponderata $\mathbf{1}^\top S$.
• Giustificazione Teorica: Il documento dimostra (Teorema 2) che, sotto ipotesi lievi riguardanti la distribuzione degli embedding e la struttura dei gradi del grafo, la direzione di ascesa del gradiente approssimato proposto rimane strettamente allineata con il gradiente esatto (similarità del coseno limitata). Ciò consente significativi risparmi computazionali preservando il comportamento di ricerca della struttura tipico della modularità.

3. Algoritmo di Ottimizzazione

Il framework impiega l'ascesa del gradiente proiettata:

1. Calcolare il gradiente strutturale ($G_{mod} = \tilde{B}S$) e il gradiente contrastivo ($G_{con} = -L_c S$).
2. Combinare i gradienti: $G = G_{mod} + \lambda G_{con}$.
3. Aggiornare gli embedding: $\tilde{S} = S + \eta G$.
4. Proiezione: Imporre vincoli di norma unitaria tramite normalizzazione riga per riga ($S_i \leftarrow \tilde{S}_i / \|\tilde{S}_i\|_2$) per prevenire soluzioni di scalatura banali.
5. Classificazione a valle: Gli embedding appresi sono utilizzati come caratteristiche di input per un classificatore basato su GNN (GCN, GAT o GraphSAGE) seguito da un MLP per prevedere le relazioni a coppie.

Contributi Chiave

1. Nuova Formulazione Contrastiva: Introduce un metodo per l'apprendimento di rappresentazioni dei nodi sotto supervisione a coppie che integra direttamente i vincoli etichettati delle coppie di nodi nell'obiettivo di embedding senza richiedere caratteristiche dei nodi.
2. Laplaciano Contrastivo con Segno e Normalizzato: Propone un operatore Laplaciano specifico che potenzia l'apprendimento basato sulla modularità attirando simultaneamente coppie simili e respingendo coppie dissimili in modo normalizzato.
3. Schema di Ottimizzazione Scalabile: Sviluppa un'approssimazione computazionalmente efficiente del gradiente della modularità che riduce significativamente l'overhead mantenendo l'allineamento teorico con l'obiettivo esatto, consentendo l'addestramento su grafi con milioni di archi.

Risultati Sperimentali

Il metodo è stato valutato su un insieme diversificato di benchmark, inclusi reti di citazione (Cora, CiteSeer, PubMed), grafi di acquisto congiunto (Amazon Photo, WikiCS) e dataset OGB su larga scala (ArXiv, Products).

• Prestazioni: Contrastive FUSE ha ottenuto prestazioni competitive o superiori nella classificazione dei nodi a valle (Accuratezza e Macro-F1) rispetto a baseline state-of-the-art, inclusi metodi non supervisionati (DeepWalk, Node2Vec), metodi contrastivi auto-supervisionati (DGI, GRACE, SGCL) e metodi spettrali (COLES).
• Scalabilità ed Efficienza: Il framework ha dimostrato significativi guadagni nei tempi di esecuzione. Su dataset di scala media, è stato significativamente più veloce di baseline contrastive come GRACE e SGCL. Sul dataset OGBN-ArXiv su larga scala, è stato circa 13–14 volte più veloce dei metodi basati su random walk (DeepWalk, Node2Vec) mantenendo prestazioni competitive. Diverse altre baseline non sono riuscite a essere eseguite su ArXiv a causa di vincoli di memoria.
• Ablazione: La rimozione del termine contrastivo (impostando $\lambda=0$) ha portato a prestazioni costantemente inferiori, confermando la necessità della supervisione a coppie per apprendere rappresentazioni discriminative in contesti privi di caratteristiche.

Significato e Affermazioni

Il documento afferma che Contrastive FUSE colma efficacemente il divario tra il rilevamento di comunità strutturali e l'apprendimento supervisionato a coppie. Il suo significato principale risiede nell'offrire un'alternativa rapida e scalabile ai metodi di apprendimento contrastivo esistenti che tipicamente si affidano a encoder profondi costosi, estese aumentazioni dei dati o architetture di passaggio messaggi.

Accoppiando l'apprendimento strutturale ispirato alla modularità con la supervisione contrastiva, il framework consente un apprendimento efficiente degli embedding dei nodi in scenari in cui le caratteristiche dei nodi sono assenti ma le relazioni a coppie sono note. Gli autori sottolineano che questo approccio è particolarmente prezioso per grafi in evoluzione o specifici per il contesto in cui gli embedding devono essere ricalcolati in modo efficiente, e per domini come la bioinformatica e le reti sensibili alla privacy dove l'apprendimento basato solo sulla struttura è una necessità. Il metodo raggiunge un compromesso favorevole tra accuratezza predittiva ed efficienza computazionale, rendendolo adatto per applicazioni reali su larga scala.