Random Wavelet Features for Graph Kernel Machines

Titolo: Caratteristiche d'onda casuali per macchine a kernel su grafi (Versione estesa)

1. Il Problema

Le macchine a kernel sono algoritmi potenti per l'apprendimento non lineare, ma la loro applicazione diretta ai grafi presenta sfide significative:

• Costo Computazionale: I kernel su grafi, che misurano la similarità tra nodi (spesso definiti come funzioni del Laplaciano del grafo $L$), richiedono il calcolo e l'archiviazione di una matrice kernel $N \times N$. Il costo per calcolare questa matrice è tipicamente $O(N^3)$, rendendo i metodi esistenti proibitivi per reti su larga scala.
• Limitazioni delle Metodi Esistenti: Esistono approcci basati su "random features" (come le Random Walks) che approssimano i kernel, ma mostrano una convergenza lenta per kernel spettralmente localizzati (cioè kernel che catturano interazioni globali o a lungo raggio nel dominio spaziale, ma sono concentrati su poche frequenze basse nel dominio spettrale).

2. Metodologia Proposta

Gli autori propongono un nuovo metodo di embedding nodale spettrale randomizzato basato sulla Elaborazione del Segnale su Grafo (GSP) e sulla Trasformata Wavelet su Grafo (GWT). L'obiettivo è costruire una mappa di feature $\Phi$ tale che il prodotto scalare tra le embedding di due nodi approssimi un kernel grafico specifico $\Gamma = h(L)$, dove $h$ è una funzione nota (es. diffusione, random walk).

L'algoritmo si articola in due fasi principali (Algoritmo 1):

Fase 1: Range Finding (Individuazione dello Spazio)

• L'obiettivo è stimare lo spazio generato dai primi $K$ autovettori del Laplaciano ($V_{:K}$), che corrispondono alle armoniche più "lisce" del grafo.
• Invece di calcolare la decomposizione spettrale completa (ED), si filtrano $K+r$ segnali casuali (Gaussiani) attraverso un'approssimazione polinomiale di un filtro passa-basso ideale $\chi_K$.
• Si utilizza una approssimazione polinomiale di Chebyshev (o Jackson-Chebyshev) per simulare il filtro, evitando la necessità di conoscere a priori tutti gli autovalori.
• Si stima l'autovalore di taglio $\lambda_K$ tramite un algoritmo di dicotomia che conta gli autovalori in un intervallo, utilizzando anch'esso filtri polinomiali su segnali casuali.
• I segnali filtrati vengono ortogonalizzati (Gram-Schmidt) per ottenere una base $Q$ che approssima lo span di $V_{:K}$.

Fase 2: Approssimazione del Kernel

• Una volta ottenuta la base $Q$, si costruisce l'embedding dei nodi $\Phi$ applicando la radice quadrata del filtro del kernel desiderato ($h^{1/2}$) ai segnali nella base $Q$.
• Anche questo filtro viene approssimato tramite un polinomio $p_h$.
• L'embedding finale è dato da $\Phi = (p_h(L)Q)^\top$.
• Il kernel approssimato è dato da $\tilde{\Gamma} = \Phi^\top \Phi$, che è una matrice di rango $K$ (o $K+r$).

Oversampling:
Il metodo adotta una strategia di oversampling (aggiunta di $r$ vettori casuali oltre ai $K$ target), mutuata dalla SVD Randomizzata (RSVD), per mitigare gli errori introdotti dall'approssimazione polinomiale e dall'ortogonalizzazione, garantendo che lo spazio stimato sia allineato correttamente con gli autovettori dominanti.

3. Contributi Chiave

1. Nuova Costruzione Spettrale Randomizzata: Introduzione di un metodo che utilizza la trasformata wavelet su grafo su segnali casuali per approssimare kernel grafici generici basati su $L$.
2. Superiorità per Kernel Localizzati Spettralmente: Dimostrazione teorica ed empirica che il metodo è particolarmente efficace per kernel con banda spettrale stretta (es. processi di diffusione), dove i metodi basati su camminate casuali (spaziali) falliscono nel catturare le dipendenze a lungo raggio.
3. Analisi degli Errori: Fornitura di limiti teorici rigorosi sull'errore di approssimazione, separando l'errore dovuto all'approssimazione polinomiale del filtro ($E_P$) e l'errore dovuto alla stima dello spazio (Range Finding, $E_R$).
4. Efficienza Computazionale: Il metodo evita la decomposizione spettrale completa ($O(N^3)$), riducendo la complessità temporale a $O(MEK + NK^2)$ e lo spazio a $O(NK)$, dove $M$ è il grado del polinomio e $E$ il numero di archi.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su grafi sintetici (Swiss-Roll e Community) con 5.000 nodi, confrontando il metodo proposto con le Graph Random Features (g-GRFs) esistenti.

• Accuratezza su Kernel a Banda Stretta: Il metodo proposto supera significativamente le g-GRFs per kernel con forte localizzazione spettrale (es. kernel di diffusione con $\sigma$ alto). Le g-GRFs, basate su camminate casuali, faticano a catturare le interazioni globali tipiche di questi kernel.
• Influenza del Rango Target ($K$):
  • Sul grafo Swiss-Roll (autovalori distribuiti uniformemente), il metodo raggiunge un errore vicino all'approssimazione ottimale di rango $K$ fino a $K \approx 1000$.
  • Sul grafo Community (autovalori raggruppati in cluster), le prestazioni degradano quando $K$ supera la struttura dei cluster, a causa della difficoltà nel distinguere autovalori molto vicini con filtri polinomiali non perfettamente netti.
• Complessità e Scalabilità:
  • I tempi di esecuzione confermano la complessità teorica: il tempo cresce linearmente con il numero di nodi $N$ (per $K$ fissato) e linearmente con $K$ (per $N$ fissato).
  • Per grafi grandi, il metodo è drasticamente più veloce della decomposizione spettrale completa, rendendo fattibile l'apprendimento basato su kernel su reti su larga scala.

5. Significato e Impatto

Questo lavoro colma un divario importante nell'apprendimento su grafi:

• Scalabilità: Permette di utilizzare macchine a kernel su grafi di grandi dimensioni, un compito precedentemente limitato dalla complessità cubica.
• Principio Teorico: Offre una giustificazione teorica solida per l'uso di feature randomizzate nello spazio spettrale dei grafi, collegando l'apprendimento su grafi alla SVD randomizzata e all'analisi numerica classica.
• Versatilità: Il metodo è flessibile e può essere adattato a qualsiasi kernel definito come funzione del Laplaciano, offrendo un'alternativa superiore per compiti che richiedono la cattura di strutture globali e proprietà geometriche del grafo, come la classificazione di nodi o la ricostruzione di segnali.

In sintesi, gli autori dimostrano che l'uso di wavelet randomizzate fornisce un compromesso ottimale tra accuratezza (specialmente per kernel spettrali) ed efficienza computazionale, aprendo la strada a nuove applicazioni di apprendimento profondo su grafi su larga scala.