Large-scale semi-supervised learning with online spectral graph sparsification

1. Enunciato del Problema

Il lavoro affronta la sfida dell'Apprendimento Semi-Supervisionato (SSL) in contesti su larga scala in cui:

• I dati etichettati sono scarsi e costosi: Ottenere etichette di alta qualità è difficile, mentre i dati non etichettati sono abbondanti.
• Struttura basata su grafi: La similarità dei dati è codificata in un grafo $G=(V, E)$, dove i nodi rappresentano i punti dati e gli archi rappresentano la similarità.
• Vincoli computazionali e di memoria: I metodi SSL tradizionali basati su grafi, come la Soluzione della Funzione Armonica (HFS), richiedono la risoluzione di un sistema lineare che coinvolge il Laplaciano del Grafo ($L_G$).
  • Per un grafo denso con $n$ nodi, i solver standard richiedono $O(n^3)$ tempo e $O(n^2)$ spazio.
  • Questo è non fattibile per $n$ grandi (ad esempio, milioni di nodi) e impedisce la memorizzazione dell'intera matrice di similarità in memoria.
• Obiettivo: Sviluppare un algoritmo che elabora un flusso di archi con $O(n \cdot \text{polylog}(n))$ di spazio e un costo computazionale ammortizzato di $O(\text{polylog}(n))$ per arco, senza memorizzare mai l'intero grafo.

2. Metodologia

Gli autori propongono Sparse-HFS, un algoritmo che combina Stable-HFS (una variante teoricamente fondata di HFS) con la Sparsificazione Spettrale Online dei Grafi.

A. Formulazione di Stable-HFS

L'HFS standard minimizza un problema di minimi quadrati regolarizzato ma soffre della singolarità della matrice Laplaciana. Gli autori adottano l'approccio Stable-HFS (Belkin et al., 2004), che restringe lo spazio delle ipotesi a funzioni ortogonali al vettore costante ($\langle f, \mathbf{1} \rangle = 0$).
La soluzione è formulata come:
$$\hat{f} = (\gamma l L_G + I_S)^+ y - \mu \mathbf{1}$$
Dove $I_S$ è una matrice identità che maschera i nodi non etichettati, e $\mu$ è un termine di correzione calcolato in forma chiusa per imporre il vincolo di ortogonalità.

B. Sparsificazione Spettrale Online

Per ridurre la complessità, gli autori non risolvono il sistema sul grafo completo $G$. Invece, mantengono un sparsificatore spettrale $H \subseteq G$.

• Definizione: Un grafo $H$ è uno sparsificatore spettrale $(1 \pm \epsilon)$ di $G$ se per tutti i vettori $x$:
  $$(1-\epsilon)x^T L_G x \leq x^T L_H x \leq (1+\epsilon)x^T L_G x$$
• Costruzione Incrementale (Algoritmo di Kelner-Levin):
  • L'algoritmo opera in un contesto semi-streaming. Riceve gli archi uno per uno.
  • Gli archi vengono accumulati in un buffer $A$ fino a raggiungere una dimensione di $O(n \log^2 n / \epsilon^2)$.
  • Il buffer viene quindi unito allo sparsificatore corrente $H$, e viene calcolato un nuovo sparsificatore.
  • Meccanismo Chiave: Gli archi vengono campionati in base alla loro Resistenza Effettiva ($R_e$). Calcolare $R_e$ esatta è costoso, quindi gli autori utilizzano solver lineari Simmetrici a Dominanza Diagonale (SDD) (Koutis et al., 2011) per approssimare $R_e$ in $O(n \cdot \text{polylog}(n))$ tempo.
  • Lo sparsificatore risultante $H$ possiede $O(n \cdot \text{polylog}(n))$ archi, permettendo la risoluzione efficiente del sistema Laplaciano.

C. L'Algoritmo Sparse-HFS

1. Inizializzare uno sparsificatore vuoto $H$.
2. Ricevere archi dal flusso.
3. Quando viene raggiunto la soglia di dimensione del buffer, aggiornare $H$ utilizzando la procedura di sparsificazione di Kelner-Levin.
4. Costruire il Laplaciano $L_H$ e risolvere il sistema lineare Stable-HFS su $H$ invece che su $G$.
5. Restituire la soluzione $\hat{f}$.

3. Contributi Chiave

1. Algoritmo Scalabile: Introduzione di Sparse-HFS, il primo metodo per risolvere problemi SSL su larga scala con $O(n \cdot \text{polylog}(n))$ di spazio e tempo ammortizzato $O(\text{polylog}(n))$ per arco. Evita la memorizzazione dell'intera matrice di similarità.
2. Garanzie Teoriche di Generalizzazione:
   • Gli autori derivano un limite sull'errore di generalizzazione $R(\hat{f})$ per l'approssimazione sparsa.
   • Utilizzando la Teoria della Stabilità Algoritmica, dimostrano che l'errore introdotto dalla sparsificazione (controllato da $\epsilon$) non degrada il tasso di convergenza.
   • Teorema 1: Mostra che per un $\epsilon$ fisso, l'algoritmo approssimato fornisce garanzie dello stesso ordine dello Stable-HFS esatto. Il termine di errore di approssimazione scala come $1/l^2$ (dove $l$ è il numero di nodi etichettati), il che significa che diventa trascurabile man mano che sono disponibili più etichette.
3. Gestione della Singolarità: L'integrazione del vincolo di stabilità (ortogonalità a $\mathbf{1}$) permette un'analisi teorica rigorosa nonostante l'uso di pseudoinverse e sparsificatori.

4. Risultati Sperimentali

Gli autori hanno valutato Sparse-HFS su un dataset sintetico ($R2$) con $n=12.100$ punti e due classi.

• Configurazione: Hanno costruito grafi k-NN con $k$ variabile (da 100 a 12.000), risultando in conteggi di archi fino a $1,38 \times 10^8$.
• Prestazioni:
  • Sia Sparse-HFS che Stable-HFS non sono riusciti a propagare efficacemente le etichette fino a quando $k > 4000$ (il punto in cui i cluster si connettono).
  • Una volta connessi, Sparse-HFS ha raggiunto una accuratezza comparabile a Stable-HFS, nonostante l'uso di un grafo sparsificato.
  • Efficienza: Al punto di accuratezza ottimale ($k=4500$), lo sparsificatore $H$ conteneva solo ~10% degli archi del grafo originale $G$, mantenendo tuttavia prestazioni simili.
• Conclusione: L'errore di approssimazione è sufficientemente piccolo tale che la massiccia riduzione di memoria e calcolo non impatta significativamente l'accuratezza finale di classificazione.

5. Significato e Lavori Futuri

• Significato: Questo lavoro colma il divario tra le garanzie teoriche SSL e il dispiegamento pratico su larga scala. Dimostra che la sparsificazione spettrale non è solo uno strumento per i solver lineari ma una strategia praticabile per gli algoritmi di apprendimento, abilitando l'SSL su grafi troppo grandi per entrare in memoria.
• Limitazioni: L'approccio corrente supporta solo flussi di solo inserimento. La gestione delle cancellazioni di archi (grafi dinamici) non è banale; i metodi di schizzo esistenti per la sparsificazione dinamica richiedono $O(n^2)$ tempo per calcolare la soluzione finale, il che viola i vincoli di efficienza del lavoro.
• Lavori Futuri: Estendere queste tecniche di sparsificazione a un contesto completamente dinamico (gestendo sia inserimenti che cancellazioni) mantenendo una complessità computazionale sub-quadratica è identificato come un problema aperto chiave.

In sintesi, il lavoro fornisce un quadro rigoroso per l'apprendimento semi-supervisionato su larga scala sfruttando la sparsificazione spettrale online, offrendo una soluzione che è sia computazionalmente efficiente che teoricamente fondata.