Acyclic Graph Pattern Counting under Local Differential Privacy

1. Il Problema

Il conteggio dei pattern nei grafi è fondamentale per l'analisi delle reti (es. rilevamento di frodi, caratterizzazione di comunità), ma la pubblicazione diretta di questi risultati comporta gravi rischi per la privacy.
Il lavoro si concentra sul Local Differential Privacy (LDP), un modello decentralizzato in cui ogni nodo del grafo privatizza i propri dati localmente prima di inviarli a un analizzatore, senza la necessità di un curatore fidato che veda i dati grezzi.

Sfide principali identificate:

• Limitazione degli approcci esistenti: Le soluzioni LDP attuali sono spesso "ad hoc" e funzionano solo per pattern semplici e localizzati come stelle (stars) e triangoli. Non esiste una soluzione generale per pattern aciclici arbitrari.
• Costruzione del pattern distribuita: In un ambiente LDP, aggregare informazioni distribuite su più nodi per costruire un pattern complesso è difficile senza violare la privacy.
• Eliminazione della duplicazione dei nodi: Per contare un pattern aciclico (es. un percorso o un albero), tutti i nodi nell'istanza del pattern devono essere distinti. Nei pattern semplici (come le stelle), un nodo può verificare la non-duplicazione localmente. Nei pattern aciclici generali, che possono coinvolgere nodi distanti, nessun singolo nodo ha una visione globale per rilevare e prevenire la duplicazione.
• Inefficienza dei metodi basati su RR: L'approccio diretto basato sulla Randomized Response (RR), dove ogni nodo invia la lista dei vicini rumorosa, porta a un errore additivo di ordine $O(N^k)$ (dove $N$ è il numero di nodi e $k$ il numero di archi nel pattern), rendendolo inutilizzabile per grafi reali.

2. Metodologia

Gli autori propongono il primo meccanismo generale per il conteggio di pattern aciclici arbitrari sotto edge-LDP, affrontando le sfide attraverso tre componenti chiave:

A. Conteggio Ricorsivo dei Sottopattern (Walk Counting)

Per superare la necessità di aggregazione globale, il metodo utilizza un approccio ricorsivo basato sul conteggio dei walk (percorsi che possono ripetere nodi).

• Meccanismo Multi-round: Invece di pubblicare liste di vicini, i nodi collaborano in $k-1$ round.
• Logica: In ogni round $\ell$, un nodo aggrega i conteggi dei walk di lunghezza $\ell-1$ provenienti dai suoi vicini, aggiunge rumore di Laplace e pubblica il risultato.
• Ottimizzazione: Si riduce il numero di round da $k$ a $k-1$ e si sposta il calcolo del massimo globale (necessario per calibrare il rumore) sull'analizzatore, riducendo il costo computazionale per nodo da $O(N)$ a $O(d(G))$ (grado massimo).

B. Tecnica di "Random Marking" (Per i Percorsi e Pattern Aciclici)

Per trasformare il conteggio dei walk (che ammettono nodi ripetuti) in quello di path o pattern aciclici (nodi distinti), si introduce una tecnica ispirata al color-coding:

• Assegnazione di Marche: Ogni nodo $v_i$ campiona casualmente un "marchio" $r_i$ da $\{0, 1, \dots, k\}$.
• Vincolo di Posizione: Un nodo può partecipare al conteggio di un pattern solo se si trova nella posizione specifica definita dal suo marchio. Ad esempio, un nodo con marchio 0 può essere solo l'inizio del percorso.
• Effetto: Questo vincolo proattivo impedisce la duplicazione dei nodi all'interno di un'istanza del pattern. Poiché i marchi sono indipendenti, un pattern valido viene contato solo se tutti i suoi nodi ricevono i marchi corretti in sequenza.
• Correzione del Bias: Il risultato finale viene ridimensionato moltiplicando per $(k+1)^{k+1}$ per compensare la probabilità di campionamento, garantendo uno stimatore non distorto (unbiased).

C. Generalizzazione ai Pattern Aciclici Arbitrari

Per pattern che non sono semplici percorsi lineari (es. alberi), il metodo:

1. Trasforma il pattern in una struttura ad albero con un ordinamento dei vertici (es. DFS).
2. Applica la ricorsione dal basso verso l'alto (dalle foglie alla radice), aggregando i conteggi dei sotto-alberi.
3. Integra la tecnica di random marking per garantire l'unicità dei nodi in ogni istanza dell'albero.

3. Contributi Chiave

1. Prima soluzione generale: Il primo meccanismo LDP in grado di contare qualsiasi pattern aciclico con $k$ archi, non limitato a stelle o triangoli.
2. Garanzie di Utilità Teoriche:
   • Per i walk a $k$ archi: Errore additivo $\tilde{O}(\sqrt{N} d(G)^{k-1})$.
   • Per i path e pattern aciclici a $k$ archi: Errore additivo $\tilde{O}(\sqrt{N} d(G)^k)$.
   • Questi limiti sono significativamente migliori rispetto all'approccio RR basato ($O(N^k)$).
3. Efficienza:
   • Comunicazione: Costo totale di $O(M + N)$ (dove $M$ è il numero di archi), un miglioramento drastico rispetto a $O(N^2)$ dei metodi basati su RR.
   • Computazione: Costo per nodo $O(d(G))$ e costo per analizzatore $O(N)$.
4. Meccanismo per le Stelle: Una variante ottimizzata a un singolo round per il conteggio delle stelle, che non richiede la fase di marking e raggiunge lo stato dell'arte (SOTA) per tale compito specifico.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su 6 dataset reali (es. Twitter, Enron, AstroPh) confrontando il metodo proposto con le tecniche basate su RR ([48]) e altre soluzioni specifiche ([4], [30]).

• Miglioramento dell'Utilità:
  • Per il conteggio di walk: Riduzione dell'errore fino a 110 volte.
  • Per il conteggio di path: Miglioramento dell'utilità fino a 2600 volte rispetto ai baselines.
  • Per pattern aciclici generali: Miglioramento fino a 46 volte.
• Riduzione dei Costi di Comunicazione:
  • Riduzione dei costi di comunicazione fino a 650 volte (da GB a MB).
• Precisione:
  • Per i walk, l'errore relativo è rimasto inferiore all'8% su tutti i dataset.
  • Per il conteggio delle stelle, l'errore relativo è stato mantenuto sotto lo 0,5%.
• Robustezza: L'errore del metodo proposto si stabilizza al crescere del budget privacy $\epsilon$ quando l'errore di campionamento (dovuto al random marking) diventa dominante, ma rimane comunque molto inferiore ai metodi concorrenti.

5. Significato e Impatto

Questo lavoro colma un divario teorico e pratico significativo nella privacy dei grafi decentralizzati.

• Generalità: Dimostra che è possibile contare pattern complessi e arbitrari in ambienti LDP senza sacrificare eccessivamente la privacy o l'efficienza, superando la limitazione dei metodi precedenti confinati a strutture locali.
• Scalabilità: La riduzione dei costi di comunicazione e computazione rende fattibile l'applicazione di queste tecniche su grafi reali di grandi dimensioni, dove i metodi precedenti erano impraticabili.
• Fondamento Futuro: La metodologia basata su ricorsione e marcatura casuale apre la strada a futuri sviluppi, come l'estensione a pattern ciclici (es. triangoli in contesti LDP più complessi) o l'adattamento al Node-LDP.

In sintesi, il paper presenta un framework robusto ed efficiente che trasforma il problema del conteggio di pattern aciclici in un'operazione fattibile e precisa sotto vincoli di privacy locale, offrendo miglioramenti di ordini di grandezza rispetto allo stato dell'arte.