🤖 machine learning

PriDyG: Privacy-preserving Dynamic Graph Inference with LLM-GNN Collaboration

[[PrivDyG è un framework per l'inferenza di grafi dinamici che preserva la privacy e combina l'apprendimento strutturale basato su GNN con il ragionamento semantico basato su LLM per ottenere la privacy differenziale a livello di edge con un costo cumulativo costante, superando significativamente i baseline esistenti in termini di utilità pur mitigando l'accumulo della perdita di privacy.]]

Autori originali: Yuyang Xia, Ruixuan Liu, Li Xiong

Pubblicato 2026-08-06

📖 4 min di lettura☕ Lettura da pausa caffè

CC BY 4.0

Autori originali: Yuyang Xia, Ruixuan Liu, Li Xiong

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina Internet come una mappa gigante e in continuo mutamento di connessioni. Alcune linee su questa mappa sono amicizie, altre sono scambi finanziari e altre ancora sono consultazioni mediche segrete. Questa mappa è chiamata un "grafo", e i computer la usano per fare previsioni, come indovinare chi potresti voler avere come amico o quale prodotto potresti acquistare successivamente. Ma ecco il problema: se chiedi a un computer di studiare questa mappa troppo da vicino, potrebbe accidentalmente rivelare quelle linee segrete, esponendo relazioni private. Per impedire ciò, gli scienziati usano uno scudo matematico chiamato "Differential Privacy" (Privacy Differenziale). Immaginalo come l'aggiunta di un po' di rumore statico a un segnale radio; rende il segnale abbastanza sfocato da non permettere a nessuno di sentire un segreto specifico, ma abbastanza chiaro da capire comunque la musica generale.

Il problema diventa più complicato quando la mappa continua a cambiare. Nel mondo reale, nuove amicizie si formano e nuove transazioni avvengono ogni secondo. Se un computer cerca di aggiornare le sue previsioni ogni volta che viene disegnata una nuova linea, deve esaminare l'intera mappa ancora e ancora. Ogni volta che guarda, lo scudo della privacy si indebolisce un po' e il rumore diventa un po' più forte, finché le previsioni non diventano spazzatura inutile. Questo articolo affronta la grande domanda: come possiamo continuare ad aggiornare le nostre previsioni su una mappa che cambia senza esaurire la privacy o annegare nel rumore?

Gli autori di questo articolo, Yuyang Xia, Ruixuan Liu e Li Xiong, propongono un nuovo e astuto sistema chiamato PriDyG. Invece di cercare di costringere il computer a scansionare nuovamente l'intera mappa disordinata ogni volta che appare una nuova linea, hanno costruito una squadra composta da due parti. Una parte è un "detective strutturale" (una Rete Neurale su Grafo) che osserva le connessioni, e l'altra è un "lettore semantico" (un Large Language Model) che legge le descrizioni testuali delle persone o degli oggetti coinvolti.

Ecco come funziona il loro trucco magico. Il "detective strutturale" è colui che ha bisogno dello scudo della privacy perché osserva le connessioni segrete. Di solito, ogni volta che la mappa cambia, questo detective deve riesaminare tutto l'insieme, il che consuma il budget della privacy e aggiunge così tanto rumore da confonderlo. PriDyG cambia le regole del gioco utilizzando un sistema a "buffer". Invece di rileggere l'intera mappa, il sistema guarda solo le nuove linee arrivate dall'ultimo controllo. Calcola la differenza e la aggiunge alla risposta precedente, come aggiornare un tabellone dei punteggi aggiungendo semplicemente i nuovi punti invece di ricontare l'intera partita. Ciò significa che il costo della privacy rimane lo stesso indipendentemente da quante volte la mappa si aggiorna.

Tuttavia, questo metodo della "differenza" non è perfetto; perde alcune connessioni complesse e a lunga distanza che una scansione completa riuscirebbe a cogliere. È qui che entra in gioco il secondo membro del team, il "lettore semantico". Questo lettore osserva solo le descrizioni testuali pubbliche (come la biografia di una persona o la descrizione di un prodotto) ed ignora completamente le connessioni segrete. Poiché non tocca i dati privati, non ha bisogno di alcun budget di privacy! Funziona come una rete di sicurezza. Quando il detective strutturale diventa troppo sfocato o incerto a causa del rumore, il sistema si affida maggiormente all'opinione del lettore semantico.

L'articolo dimostra che questa collaborazione funziona incredibilmente bene. Nei test su quattro diversi dataset (inclusi social network e cataloghi di prodotti), PriDyG è riuscito a mantenere accurate le sue previsioni anche quando il grafo cambiava migliaia di volte. Ha dimostrato che combinando un aggiornamento strutturale che preserva la privacy con un lettore testuale privo di rischi per la privacy, è possibile mantenere un'alta accuratezza senza che il costo della privacy sfugga al controllo. Gli autori hanno scoperto che questo metodo è molto migliore rispetto ai vecchi modi di cercare di risparmiare la privacy, che solitamente portavano il computer a diventare così rumoroso da non essere più in grado di fare previsioni utili dopo pochi aggiornamenti. Hanno dimostrato che il loro approccio mantiene il costo totale della privacy costante, indipendentemente da quanti aggiornamenti avvengono, fornendo comunque risultati competitivi con i sistemi che non utilizzano alcuna protezione della privacy.

Riepilogo Tecnico: PriDyG

Formulazione del Problema

Il documento affronta la sfida dell'Inferenza su Grafi Dinamici con Differentially Private (DP) a livello di arco (EDG). Nei grafi dinamici, dove gli archi arrivano continuamente e i modelli richiedono aggiornamenti frequenti, i metodi esistenti per la preservazione della privacy affrontano due sfide critiche:

Compromesso Utilità-Privacy (Sfida 1): Imporre la DP a livello di arco richiede l'iniezione di rumore nell'aggregazione dei vicini, il che distorce i segnali strutturali essenziali per le Graph Neural Networks (GNN), portando a un significativo degrado dell'accuratezza rispetto alle controparti non private.
Accumulo del Budget di Privacy (Sfida 2): Nelle impostazioni dinamiche, gli aggiornamenti ripetuti del modello tipicamente innescano la composizione sequenziale dei budget di privacy. Se un meccanismo riesegue l'aggregazione privata sull'intero grafo per ogni aggiornamento, il costo totale della privacy cresce linearmente ( $M \cdot \epsilon$ ) con il numero di aggiornamenti $M$ , diventando rapidamente proibitivo. Alternativamente, allocare un budget che decade geometricamente agli aggiornamenti successivi mantiene il costo totale limitato, ma causa una crescita esponenziale della scala del rumore, rendendo inutilizzabili i modelli successivi.

Gli autori definiscono il problema EDG come la progettazione di un meccanismo che risponda a query di classificazione dei nodi e predizione dei collegamenti su un grafo in evoluzione, soddisfacendo la DP a livello di arco durante l'intera esecuzione e mantenendo un'alta utilità. Fondamentalmente, il modello di minaccia assume che gli attributi testuali dei nodi siano pubblici, mentre solo l'esistenza degli archi è protetta.

Metodologia: PriDyG

Gli autori propongono PriDyG, un framework che accoppia il ragionamento semantico basato su LLM con l'apprendimento strutturale DP-GNN dinamico. L'architettura opera attraverso tre componenti principali:

1. Framework Collaborativo LLM-GNN

PriDyG esegue due rami complementari:

Ramo DP-GNN: Apprende rappresentazioni strutturali sotto la DP a livello di arco.
Ramo LLM: Esegue classificazione zero-shot o scoring dei collegamenti utilizzando solo gli attributi testuali dei nodi. Poiché il testo del nodo è pubblico secondo il modello di minaccia, questo ramo consuma zero budget di privacy.
Fusione con Gate di Confidenza: Il sistema fonde dinamicamente le predizioni. Se la predizione della GNN è sicura (margine elevato), viene utilizzata direttamente. Se incerta, il sistema fonde l'output della GNN con la predizione semantica dell'LLM. Ciò consente al sistema di fare affidamento sull'ancora LLM stabile e priva di privacy man mano che l'accuratezza strutturale della GNN erode a causa dell'accumulo di rumore nel tempo.

2. Aggregazione Multi-hop Privata Incrementale (PMA)

Per risolvere il problema dell'accumulo del budget, PriDyG introduce la PMA Incrementale, che sostituisce l'approccio di rieseguire l'aggregazione completa su tutto il grafo.

Meccanismo: I nuovi archi arrivati vengono bufferizzati. Quando viene emesso un comando di riaddestramento, l'algoritmo calcola un'aggregazione "delta" basata solo sui nuovi archi e aggiunge questa delta rumorosa alle aggregazioni memorizzate dai passaggi precedenti.
Garanzia di Privacy: Poiché ogni arco viene elaborato esattamente una volta (quando viene svuotato dal buffer), si applica il Teorema della Composizione Parallela. Il costo totale della privacy rimane costante ( $\epsilon_{PMA}$ ), indipendentemente dal numero di aggiornamenti $M$ o dalla pianificazione del riaddestramento.
Preservazione del Segnale:
- One-hop: L'aggregazione è un segnale esatto (senza perdite nel caso non rumoroso).
- Multi-hop: Il metodo mantiene almeno la metà di tutti i trasferimenti di informazione a due hop. Omette i percorsi "backward-in-time" (dove l'informazione fluisce dagli archi più recenti verso quelli più vecchi), ma questo errore è strutturato e limitato, a differenza del drift illimitato di altri metodi.
Accumulo del Rumore: Mentre il budget di privacy è costante, la varianza del rumore cresce linearmente ( $O(M)$ ) con il numero di aggiornamenti. Tuttavia, si tratta di una crescita polinomiale, che contrasta nettamente con la crescita esponenziale del rumore richiesta dalle baseline a budget che decade geometricamente.

3. Adattamento della Predizione dei Collegamenti

Per la predizione dei collegamenti, il predittore predefinito utilizza la similarità del coseno sulle rappresentazioni PMA privatizzate. Per calibrare i pesi di fusione senza violare la DP a livello di arco, gli autori utilizzano la Risposta Randomizzata su un set disgiunto di coppie di nodi per generare etichette privatizzate per la sintonizzazione dei parametri di fusione ( $\alpha, \tau$ ).

Contributi Chiave

Framework Collaborativo LLM-GNN: Una pipeline unificata che restringe il divario tra privacy e utilità compensando la perdita di utilità della GNN privatizzata con il ragionamento semantico dell'LLM privo di privacy.
Inferenza Dinamica a Budget Costante: La proposta della PMA Incrementale, che raggiunge un costo di privacy totale $O(1)$ sotto arbitrari aggiornamenti del modello sfruttando la disgiunzione dei batch di archi, risolvendo fondamentalmente la tensione del budget nell'inferenza su grafi dinamici.
Valutazione Esaustiva: Esperimenti estesi su quattro dataset benchmark (Cora, PubMed, ogbn-arxiv, ogbn-products) per la classificazione dei nodi e la predizione dei collegamenti.

Risultati

Gli esperimenti dimostrano che PriDyG:

Supera costantemente le baseline a budget che decade geometricamente sotto lo stesso budget di privacy totale.
Riduce il costo di privacy cumulativo fino a tre ordini di grandezza rispetto agli approcci di riaddestramento per aggiornamento, mantenendo un'utilità competitiva.
Mantiene un'accuratezza stabile su lunghi flussi di inserimento, mentre la sola branca GNN subisce cali di accuratezza sostanziali rispetto all'addestramento statico a causa dell'accumulo di rumore.
Rimane competitivo con le baseline non private fornendo al contempo garanzie formali di DP a livello di arco.

Significato e Rivendicazioni

Il documento afferma che PriDyG è il primo lavoro che formula e studia l'inferenza su grafi con DP a livello di arco su grafi continuamente aggiornati con l'obiettivo specifico di garantire che il costo della privacy non cresca con il numero di aggiornamenti.

Gli autori sottolineano che la collaborazione LLM-GNN non è semplicemente un potenziamento generico dell'accuratezza, ma è specificamente preziosa nel regime dinamico. Man mano che la branca strutturale (GNN) diventa più debole a causa dell'accumulo di rumore, la pipeline sposta naturalmente la dipendenza verso l'ancora LLM stabile e priva di privacy. Questo design consente aggiornamenti frequenti del modello senza ulteriore degradazione della privacy, affrontando un collo di bottiglia critico nelle applicazioni di grafi dinamici nel mondo reale dove i dati evolvono continuamente.