Misclassification Rate and Privacy-Utility Trade-offs in Graph Convolutional Networks via Subsampling Stability

Riepilogo Tecnico: Tasso di Misclassificazione e Compromessi Privacy-Utilità nelle Reti Convoluzionali su Grafo tramite Stabilità da Campionamento

Enunciato del Problema
L'aumento dell'impiego delle Reti Convoluzionali su Grafo (GCN) per compiti come la classificazione dei nodi e il rilevamento di comunità solleva preoccupazioni significative in materia di privacy, poiché i dati grafo codificano spesso interazioni sensibili tra entità. Sebbene la Privacy Differenziale (DP) offra un quadro rigoroso per la protezione dei dati, le indagini teoriche sulla DP specificamente nel contesto delle GCN rimangono scarse. Gli approcci esistenti si concentrano spesso sull'alterazione degli input o sull'applicazione di DP-SGD, ma manca una fondazione teorica rigorosa per comprendere i limiti fondamentali della preservazione della privacy e per guidare la progettazione degli algoritmi nelle GCN. Questo lavoro colma tale lacuna analizzando i compromessi tra privacy e utilità nell'applicazione della DP alle GCN attraverso un meccanismo di stabilità da campionamento.

Metodologia
Gli autori propongono un framework denominato AsampGCN, che integra la privacy differenziale nelle GCN tramite campionamento a livello di arco e votazione a maggioranza. La metodologia procede come segue:

1. Campionamento a Livello di Arco: Dato un grafo in ingresso $G=(V, E)$, l'algoritmo genera $m$ sottografi indipendenti $\{G_1, \dots, G_m\}$. In ciascun sottografo, ogni arco viene mantenuto indipendentemente con una probabilità $p_s \in (0, 1]$.
2. Classificazione Base: Un classificatore GCN standard viene applicato a ciascun sottografo campionato $G_\ell$ per produrre un'etichettatura binaria dei nodi $\hat{y}(G_\ell)$.
3. Aggregazione: I $m$ vettori di etichetta risultanti vengono aggregati tramite votazione a maggioranza per produrre una stima di consenso $\bar{y}$.
4. Test di Stabilità (Framework PTR): Per soddisfare la privacy differenziale a livello di arco $(\epsilon, \delta)$, gli autori impiegano il framework Propose-Test-Release (PTR). Calcolano un punteggio di stabilità $\hat{d}$ basato sulle frequenze dei vettori di etichetta più comuni tra le $m$ uscite. Questo punteggio viene alterato con rumore Laplaciano. Se il punteggio alterato supera una soglia determinata da $\epsilon$ e $\delta$, viene rilasciato l'etichetta di consenso $\bar{y}$; altrimenti, l'algoritmo restituisce $\perp$ (fallimento), indicando una stabilità insufficiente.

Contributi Chiave
Il paper apporta tre contributi teorici principali:

1. Meccanismo di Stabilità da Campionamento: Introduce e analizza un meccanismo di stabilità da campionamento specificamente progettato per fornire garanzie di privacy differenziale per le GCN, un approccio innovativo in questo dominio.
2. Limiti del Tasso di Misclassificazione: Gli autori derivano un limite superiore esplicito per il tasso di misclassificazione del meccanismo proposto. Crucialmente, questo limite dipende direttamente dalla probabilità di campionamento $p_s$, dalla norma del Laplaciano del grafo e dal margine del classificatore.
3. Caratterizzazione Privacy-Utilità: Il lavoro stabilisce espressioni analitiche precise che definiscono gli intervalli fattibili di $p_s$. Dimostra che $p_s$ non può essere scelto arbitrariamente; deve rientrare in un intervallo specifico per soddisfare simultaneamente le garanzie di privacy e mantenere l'utilità.

Risultati Teorici
Il paper fornisce teoremi rigorosi che caratterizzano le prestazioni di AsampGCN:

• Limite per Singolo Grafo (Teorema 3): Per un singolo sottografo campionato, il tasso di misclassificazione è limitato da una funzione $f(p_s, \eta)$ che scala con la probabilità di campionamento. Il limite incorpora la costante di Lipschitz della funzione di attivazione, i coefficienti del filtro, la norma del Laplaciano del grafo $\|L\|_2$ e il margine minimo $\gamma_{min}$.
• Limite del Meccanismo (Teorema 4): Per l'intero meccanismo di stabilità da campionamento che coinvolge $m$ sottografi, il tasso di misclassificazione è limitato da $f(p_s, \eta)/4 + O(1/\sqrt{m})$. Questo risultato combina il limite per singolo grafo con la disuguaglianza di Hoeffding applicata allo schema di votazione a maggioranza.
• Caratterizzazione del Compromesso (Teorema 5): Il paper definisce un intervallo fattibile $(p_s^*, \frac{\epsilon}{32 \ln(1/\delta)})$ per la probabilità di campionamento.
  • Se $p_s$ è troppo grande, la condizione di stabilità richiesta dal meccanismo DP diventa difficile da soddisfare, portando a garanzie di privacy vacue (l'algoritmo restituisce frequentemente $\perp$).
  • Se $p_s$ è troppo piccola, l'estrazione di segnali informativi viene soppressa, causando un degrado significativo dell'accuratezza (alto tasso di misclassificazione).
  • Il limite inferiore $p_s^*$ è derivato da un'equazione quadratica che garantisce che il tasso di misclassificazione rimanga sufficientemente basso per assicurare l'utilità, mentre il limite superiore è dettato dai parametri di privacy.

Significato
Gli autori affermano che questo lavoro fornisce il primo framework teorico rigoroso per comprendere la stabilità da campionamento nelle GCN sotto privacy differenziale. Collegando esplicitamente la probabilità di campionamento sia ai tassi di misclassificazione che alle garanzie di privacy, i risultati offrono una guida principiale per la selezione dei parametri nell'apprendimento su grafo privato. Lo studio va oltre le osservazioni empiriche per stabilire limiti fondamentali, mostrando che il compromesso tra privacy e utilità nelle GCN è governato dal parametro di campionamento $p_s$, che deve essere calibrato con cura per evitare sia il fallimento della privacy che il collasso dell'utilità.