Active Learning on Adversarially Corrupted Graphs

Sintesi Tecnica: Apprendimento Attivo su Grafi Corrotti Adversarialmente

Formulazione del Problema
Il documento affronta il problema dell'apprendimento attivo su grafi la cui struttura sottostante è stata manomessa da un avversario. Il setting prevede un grafo iniziale "ground-truth" $G^* = (V^*, E^*)$ e un insieme di vertici corrotti (maliziosi) $I$. Un avversario con un budget $b$ costruisce un grafo finale $G$ attraverso tre passaggi:

1. Creazione di un sottografo arbitrario su un insieme di nuovi vertici $I$ (dove $|I| \le |V^*|$).
2. Connessione di al massimo $b$ vertici da $V^*$ all'insieme $I$. Questo definisce il potere dell'avversario: la dimensione della frontiera di $I$ in $G$ è limitata da $b$ (ovvero, $|\partial_G(I)| \le b$).
3. Aggiunta arbitraria di archi all'interno di $G^*$.

L'algoritmo riceve il grafo risultante $G$ e ha accesso a un oracolo di etichettatura $O_{G,I}$, che rivela se un vertice interrogato appartiene a $I$. L'obiettivo è ottenere il recupero debole (weak recovery): identificare un sottoinsieme $\hat{I}$ tale che la differenza simmetrica $|\hat{I} \triangle I| \le \gamma |V(G)|$ con alta probabilità, utilizzando un numero minimo di query di etichettatura. La sfida risiede nel fatto che $G^*$ e il sottografo corrotto $G[I]$ possono essere arbitrari e l'avversario può manipolare significativamente la struttura del grafo, purché il numero di connessioni con il grafo originale rimanga limitato.

Metodologia
La soluzione proposta si basa sulla proprietà strutturale dell'espansione dei vertici e su un framework algoritmico ricorsivo.

1. Intuizione Strutturale: L'intuizione centrale è che se l'insieme di vertici corrotti $I$ possiede un'espansione dei vertici significativamente inferiore rispetto alle parti "buone" del grafo $G^*$, esso può essere isolato. Nello specifico, gli autori definiscono una condizione in cui $I$ è "scarsamente espansivo" rispetto al resto del grafo. Se $I$ soddisfa una specifica condizione di gap di espansione, qualsiasi insieme $S$ con un confine piccolo e una dimensione comparabile a $I$ deve essere fortemente correlato con $I$.

2. Nucleo Algoritmico (Sum-of-Squares): Per trovare un tale insieme $S$, gli autori adattano gli algoritmi Sum-of-Squares (SoS), nello specifico modificando la rilassazione semidefinite (SDP) per l'espansione dei vertici proposta da Feige et al. (2005).

   • Gli algoritmi standard di espansione dei vertici spesso falliscono nel garantire la dimensione dell'insieme restituito o forniscono fattori di approssimazione troppo deboli per questo specifico setting avversariale.
   • Gli autori introducono un nuovo algoritmo di arrotondamento (rounding) per la rilassazione SoS di grado 4. Questo arrotondamento assicura che l'insieme in uscita $S$ soddisfi i vincoli di cardinalità (specificamente, $|S| = \Theta(|I|)$) mantenendo al contempo un confine piccolo.
   • Questo adattamento permette all'algoritmo di trovare un insieme $S$ che approssima l'espansione minima dei vertici soggetta a vincoli di dimensione, un risultato di interesse indipendente (Teorema 4).

3. Raffinamento Ricorsivo: L'algoritmo opera iterativamente:

   • Utilizza la procedura basata su SoS per trovare un insieme $S$ che sia altamente correlato con i restanti vertici corrotti.
   • Interroga l'oracolo su un piccolo campione casuale di $S$ e del suo complemento per determinare quale insieme contenga la maggioranza dei nodi corrotti.
   • L'insieme identificato viene rimosso dal grafo, e il processo si ripete sul grafo residuo.
   • Gli autori dimostrano che le proprietà strutturali (specificamente l'espansione dei vertici del grafo ground-truth rimanente) sono preservate sufficientemente attraverso queste iterazioni, permettendo all'algoritmo di continuare a recuperare i nodi corrotti fino a quando una frazione elevata non viene identificata.

Risultati Chiave
Il contributo principale è il Teorema 3, che stabilisce la complessità delle query per il recupero debole. L'algoritmo ottiene il recupero debole $(\gamma, \delta, q, b)$ se:

• Il budget di query $q$ scala come $\tilde{O}\left(\frac{1}{\gamma} (\log \frac{1}{\delta} + b\sqrt{\log n})\right)$.
• Il budget dell'avversario $b$ è limitato dall'espansione dei vertici del grafo ground-truth $G^*$: $b \le O\left(\frac{\gamma^6}{\log^3(1/\gamma)\sqrt{\log n}} \cdot \partial_{\eta n}(G^*)\right)$, dove $\partial_{\eta n}(G^*)$ è il minimo confine di sottoinsiemi di dimensione almeno $\eta n$.

Essenzialmente, il numero di query richieste è lineare nel budget dell'avversario $b$ e inversamente proporzionale alla precisione desiderata $\gamma$, a condizione che il budget dell'avversario sia piccolo rispetto alla connettività del grafo (espansione dei vertici).

Inoltre, il Teorema 4 presenta un risultato ausiliario: un algoritmo polinomiale randomizzato che trova un insieme con piccola espansione dei vertici e dimensione entro un intervallo bilanciato $[m, n-m]$, raggiungendo un fattore di approssimazione di $O(\sqrt{\log n})$ per certi parametri. Questo migliora o integra i limiti esistenti per i problemi di espansione di piccoli insiemi (small-set expansion).

Significatività e Rivendicazioni
Il documento sostiene di essere il primo a dimostrare che l'espansione dei vertici è una misura fondamentale che determina la complessità delle query degli algoritmi di apprendimento attivo robusti ad attacchi avversariali strutturali.

• Novità: A differenza dei lavori precedenti sugli attacchi Sybil o sul graph poisoning, che spesso assumono che il grafo "buono" sia un espansore o limitano il numero di archi aggiunti, questo modello permette strutture interne arbitrarie sia nei sottografi buoni che in quelli cattivi, limitando solo la dimensione del confine.
• Fondamento Teorico: Il lavoro fornisce un collegamento teorico tra la connettività del grafo (espansione dei verti) e la fattibilità del rilevamento dei nodi corrotti. Dimostra che anche se il grafo ground-truth non è un espansore globale, il recupero debole è possibile purché il budget dell'avversario sia piccolo rispetto all'espansione di sottoinsiemi sufficientemente grandi.
• Contributo Algoritmico: Il documento introduce un algoritmo in tempo polinomiale per trovare insiemi con piccola espansione dei vertici sotto vincoli di cardinalità, un problema noto per essere computazionalmente difficile, sfruttando e adattando le tecniche Sum-of-Squares.

Gli autori mantengono un tono modesto, notando che i loro risultati dipendono da specifici gap di espansione e che la complessità delle query degrada al diminuire della precisione $\gamma$ o all'aumentare del budget dell'avversario. Non pretendono di risolvere il problema per tutte le possibili strutture di grafo o budget avversariali arbitrari, ma stabiliscono un preciso compromesso tra costo delle query, accuratezza e proprietà strutturali del grafo di input.