🤖 machine learning

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

PriDyG est un cadre de préservation de la vie privée pour l'inférence de graphes dynamiques qui combine l'apprentissage structurel basé sur les GNN avec le raisonnement sémantique basé sur les LLM pour atteindre une confidentialité différentielle au niveau des arêtes avec un coût cumulatif constant, surpassant de manière significative les bases de référence existantes en termes d'utilité tout en atténuant l'accumulation de la perte de confidentialité.

Auteurs originaux : Yuyang Xia, Ruixuan Liu, Li Xiong

Publié 2026-08-06

📖 4 min de lecture☕ Lecture pause café

CC BY 4.0

Auteurs originaux : Yuyang Xia, Ruixuan Liu, Li Xiong

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez l'internet comme une carte géante de connexions en perpétuel changement. Certaines lignes sur cette carte sont des amitiés, d'autres sont des transactions financières, et certaines sont des consultations médicales secrètes. Cette carte est appelée un « graphe », et les ordinateurs l'utilisent pour faire des prédictions, comme deviner avec qui vous pourriez vouloir devenir ami ou quel produit vous achèterez ensuite. Mais voici le hic : si vous demandez à un ordinateur d'étudier cette carte de trop près, il pourrait accidentellement révéler ces lignes secrètes, exposant ainsi des relations privées. Pour empêcher cela, les scientifiques utilisent un bouclier mathématique appelé « Confidentialité Différentielle » (Differential Privacy). Imaginez cela comme l'ajout d'un peu de bruit statique à un signal radio ; cela rend le signal juste assez flou pour que personne ne puisse entendre un secret spécifique, mais assez clair pour comprendre toujours la musique générale.

Le problème devient plus complexe lorsque la carte ne cesse de changer. Dans le monde réel, de nouvelles amitiés se forment et de nouvelles transactions ont lieu chaque seconde. Si un ordinateur essaie de mettre à jour ses prédictions chaque fois qu'une nouvelle ligne est tracée, il doit examiner toute la carte encore et encore. Chaque fois qu'il regarde, le bouclier de confidentialité s'affaiblit un peu et le bruit devient un peu plus fort, jusqu'à ce que les prédictions deviennent des données inutiles. Cet article s'attaque à la grande question : comment pouvons-nous continuer à mettre à jour nos prédictions sur une carte changeante sans épuiser la confidentialité ou nous noyer dans le bruit ?

Les auteurs de cet article, Yuyang Xia, Ruixuan Liu et Li Xiong, proposent un nouveau système ingénieux appelé PriDyG. Au lieu d'essayer de forcer l'ordinateur à rescanner toute la carte désordonnée chaque fois qu'une nouvelle ligne apparaît, ils ont construit une équipe en deux parties. Une partie est un « détective structurel » (un Réseau de Neurones sur Graphe) qui observe les connexions, et l'autre est un « lecteur sémantique » (un Grand Modèle de Langage) qui lit les descriptions textuelles des personnes ou des articles concernés.

Voici comment leur tour de magie fonctionne. Le « détective structurel » est celui qui a besoin du bouclier de confidentialité car il observe les connexions secrètes. Habituellement, chaque fois que la carte change, ce détective doit réexaminer l'ensemble, ce qui consomme le budget de confidentialité et ajoute tellement de bruit qu'il finit par être confus. PriDyG change la donne en utilisant un système de « tampon » (buffer). Au lieu de relire toute la carte, le système regarde simplement les nouvelles lignes arrivées depuis la dernière vérification. Il calcule la différence et l'ajoute à la réponse précédente, comme lorsqu'on met à jour un tableau de score en ajoutant simplement les nouveaux points plutôt qu'en recomptant tout le match. Cela signifie que le coût de la confidentialité reste le même, peu importe le nombre de mises à jour de la carte.

Cependant, cette méthode de « différence » n'est pas parfaite ; elle manque certaines connexions complexes et à longue distance qu'un balayage complet capterait. C'est là que le second membre de l'équipe, le « lecteur sémantique », intervient. Ce lecteur ne regarde que les descriptions textuelles publiques (comme la biographie d'une personne ou la description d'un produit) et ignore totalement les connexions secrètes. Comme il ne touche pas aux données privées, il n'a besoin d'aucun budget de confidentialité ! Il agit comme un filet de sécurité. Lorsque le détective structurel devient trop flou ou incertain à cause du bruit, le système s'appuie davantage sur l'opinion du lecteur sémantique.

L'article montre que cette collaboration fonctionne incroyablement bien. Lors de tests sur quatre ensembles de données différents (incluant des réseaux sociaux et des catalogues de produits), PriDyG a réussi à maintenir la précision de ses prédictions même lorsque le graphe changeait des milliers de fois. Il a prouvé qu'en combinant une mise à jour structurelle respectant la confidentialité avec un lecteur de texte exempt de contraintes de confidentialité, on peut maintenir une haute précision sans que le coût de la confidentialité ne devienne incontrôlable. Les auteurs ont constaté que cette méthode est bien meilleure que les anciennes méthodes de préservation de la confidentialité, qui aboutissaient généralement à un ordinateur si bruyant qu'il ne pouvait plus faire de prédictions utiles après quelques mises à jour. Ils ont démontré que leur approche maintient le coût total de la confidentialité constant, quel que soit le nombre de mises à jour, tout en délivrant des résultats compétitifs par rapport aux systèmes qui n'utilisent aucune protection de la confidentialité.

Résumé technique : PriDyG

Formulation du problème

L'article traite du défi de l'inférence de graphes dynamiques avec confidentialité différentielle (DP) au niveau des arêtes (EDG). Dans les graphes dynamiques, où les arêtes arrivent de manière continue et où les modèles nécessitent des mises à jour fréquentes, les méthodes existives de préservation de la vie privée font face à deux défis critiques :

Compromis Utilité-Confidentialité (Défi 1) : L'imposition d'une DP au niveau des arêtes nécessite l'injection de bruit dans l'agrégation de voisinage, ce qui déforme les signaux structurels essentiels pour les réseaux de neurones sur graphes (GNN), entraînant une dégradation significative de la précision par rapport aux contreparties non privées.
Accumulation du budget de confidentialité (Défi 2) : Dans les contextes dynamiques, les mises à jour répétées du modèle déclenchent généralement une composition séquentielle des budgets de confidentialité. Si un mécanisme réexécute l'agrégation privée sur l'ensemble du graphe pour chaque mise à jour, le coût total de confidentialité croît linéairement ( $M \cdot \epsilon$ ) avec le nombre de mises à jour $M$ , devenant rapidement prohibitif. Alternativement, l'allocation d'un budget décroissant géométriquement aux mises à jour successives permet de maintenir le coût total borné, mais provoque une croissance exponentielle de l'échelle du bruit, rendant les modèles ultérieurs inutilisables.

Les auteurs définissent le problème EDG comme la conception d'un mécanisme qui répond à des requêtes de classification de nœuds et de prédiction de liens sur un graphe évolutif tout en satisfaisant la DP au niveau des arêtes sur l'ensemble de l'exécution et en maintenant une utilité élevée. Crucialement, le modèle de menace suppose que les attributs textuels des nœuds sont publics, tandis que seule l'existence des arêtes est protégée.

Méthodologie : PriDyG

Les auteurs proposent PriDyG, un cadre qui couple le raisonnement sémantique basé sur les LLM avec un apprentissage structurel DP-GNN dynamique. L'architecture opère via trois composantes :

1. Cadre collaboratif LLM-GNN

PriDyG exécute deux branches complémentaires :

Branche DP-GNN : Apprend des représentations structurelles sous DP au niveau des arêtes.
Branche LLM : Effectue une classification zero-shot ou un score de lien en utilisant uniquement les attributs textuels des nœuds. Puisque le texte des nœuds est public selon le modèle de menace, cette branche consomme zéro budget de confidentialité.
Fusion par porte de confiance (Confidence-Gated Fusion) : Le système fusionne dynamiquement les prédictions. Si la prédiction du GNN est confiante (marge élevée), elle est utilisée directement. Si elle est incertaine, le système fusionne la sortie du GNN avec la prédiction sémantique du LLM. Cela permet au système de s'appuyer sur l'ancre sémantique stable et sans coût de confidentialité du LLM à mesure que l'exactitude structurelle du GNN s'érode en raison de l'accumulation de bruit au fil du temps.

2. Agrégation multi-sauts privée incrémentale (PMA)

Pour résoudre le problème d'accumulation du budget, PriDyG introduit la PMA incrémentale, qui remplace l'approche consistant à réexécuter l'agrégation complète sur l'ensemble du graphe.

Mécanisme : Les nouvelles arêtes arrivées sont mises en tampon. Lorsqu'une commande de réentraînement est émise, l'algorithme calcule une agrégation "delta" basée uniquement sur les nouvelles arêtes et ajoute ce delta bruité aux agrégations mises en cache des étapes précédentes.
Garantie de confidentialité : Comme chaque arête est traitée exactement une fois (lorsqu'elle est extraite du tampon), le théorème de composition parallèle s'applique. Le coût total de confidentialité reste constant ( $\epsilon_{PMA}$ ), indépendant du nombre de mises à jour $M$ ou du calendrier de réentraînement.
Préservation du signal :
- Un saut (One-hop) : L'agrégation est exacte sur le signal (sans perte dans le cas non bruité).
- Multi-sauts (Multi-hop) : La méthode conserve au moins la moitié de tous les transferts d'informations à deux sauts. Elle omet les chemins "rétroactifs dans le temps" (où l'information circule des arêtes plus récentes vers les plus anciennes), mais cette erreur est structurée et bornée, contrairement à la dérive non bornée d'autres méthodes.
Accumulation de bruit : Bien que le budget de confidentialité soit constant, la variance du bruit croît linéairement ( $O(M)$ ) avec le nombre de mises à jour. Cependant, il s'agit d'une croissance polynomiale, contrastant nettement avec la croissance exponentielle du bruit requise par les bases de référence à budget décroissant géométriquement.

3. Adaptation de la prédiction de liens

Pour la prédiction de liens, le prédicteur par défaut utilise la similitude cosinus sur les représentations PMA privatisées. Pour calibrer les poids de fusion sans violer la DP au niveau des arêtes, les auteurs utilisent la Réponse Aléatoire (Randomized Response) sur un ensemble disjoint de paires de nœuds pour générer des étiquettes privatisées afin d'ajuster les paramètres de fusion ( $\alpha, \tau$ ).

Contributions clés

Cadre collaboratif LLM-GNN : Un pipeline unifié qui réduit l'écart entre confidentialité et utilité en compensant la perte d'utilité du GNN privatisé par le raisonnement sémantique du LLM sans coût de confidentialité.
Inférence dynamique à budget constant : La proposition de la PMA incrémentale, qui atteint un coût de confidentialité total de $O(1)$ pour un nombre arbitraire de mises à jour de modèle en exploitant la disjointement des lots d'arêtes, résolvant fondamentalement la tension du budget dans l'inférence de graphes dynamiques.
Évaluation complète : Expérimentations approfondies sur quatre jeux de données de référence (Cora, PubMed, ogbn-arxiv, ogbn-products) pour la classification de nœuds et la prédiction de liens.

Résultats

Les expériences démontrent que PriDyG :

Surpasse systématiquement les bases de référence à budget décroissant géométriquement sous le même budget de confidentialité total.
Réduit le coût de confidentialité cumulé jusqu'à trois ordres de grandeur par rapport aux approches de réentraînement par mise à jour, tout en maintenant une utilité compétitive.
Maintient une exactitude stable sur de longs flux d'insertion, alors que la branche GNN seule subit des chutes d'exactitude substantielles par rapport à l'entraînement statique en raison de l'accumulation de bruit.
Reste compétitif par rapport aux bases de référence non privées tout en fournissant des garanties formelles de DP au niveau des arêtes.

Signification et affirmations

L'article affirme que PriDyG est le premier travail à formuler et étudier l'inférence de graphes avec une DP au niveau des arêtes sur des graphes continuellement mis à jour, avec l'objectif spécifique de garantir que le coût de confidentialité ne croît pas avec le nombre de mises à jour.

Les auteurs soulignent que la collaboration LLM-GNN n'est pas seulement un gain d'exactitude générique mais est spécifiquement précieuse dans le régime dynamique. À mesure que la branche structurelle (GNN) s'affaiblit en raison de l'accumulation de bruit, le pipeline déplace naturellement sa dépendance vers l'ancre sémantique stable et sans coût de confidentialité du LLM. Cette conception permet des mises à jour de modèles fréquentes sans dégradation supplémentaire de la confidentialité, répondant ainsi à un goulot d'étranglement critique dans les applications de graphes dynamiques réels où les données évoluent continuellement.