🤖 machine learning

Differentially Private Relational Learning with Entity-level Privacy Guarantees

Cet article propose un cadre fondé sur des principes pour l'apprentissage relationnel à confidentialité différentielle qui répond aux défis de la haute sensibilité des entités et de l'échantillonnage couplé en introduisant un écrêtage de gradient adaptatif et des analyses d'amplification de la confidentialité étendues, atteignant ainsi des garanties formelles de confidentialité au niveau de l'entité avec une utilité forte.

Auteurs originaux : Yinan Huang, Haoteng Yin, Eli Chien, Rongzhe Wei, Pan Li

Publié 2026-02-04

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Yinan Huang, Haoteng Yin, Eli Chien, Rongzhe Wei, Pan Li

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 que vous essayez d'apprendre à un ordinateur à comprendre comment les gens sont connectés — comme pour déterminer qui est ami avec qui, ou quels produits sont souvent achetés ensemble. C'est ce qu'on appelle l'apprentissage relationnel. L'ordinateur apprend en observant une immense carte de connexions (un graphe) où des points représentent des personnes (des entités) et des lignes représentent leurs relations.

Le problème ? Ces cartes contiennent souvent des secrets sensibles. Peut-être que la carte montre qui a consulté quel médecin, ou qui a acheté quel médicament. Si vous entraînez simplement un ordinateur sur ces données, il pourrait accidentellement « mémoriser » ces secrets et les divulguer plus tard.

Pour empêcher cela, les scientifiques utilisent un bouclier appelé Confidentialité Différentielle (Differential Privacy - DP). Voyez la DP comme une « machine à bruit » qui ajoute de la statique au processus d'apprentissage de l'ordinateur, rendant impossible de savoir si une personne spécifique figurait dans les données d'entraînement ou non.

Cependant, les auteurs de cet article ont découvert que la manière standard d'utiliser ce bouclier de confidentialité (appelée DP-SGD) échoue lorsqu'elle est appliquée à ces cartes de connexions. Voici pourquoi, et comment ils l'ont résolu, en utilisant des analogies simples :

Les deux grands problèmes

1. Le problème de « l'une personne, plusieurs rôles » (Sensibilité élevée)
Dans les données normales, une personne n'est généralement qu'un seul point de donnée. Mais dans une carte de connexions, une personne peut être impliquée dans des dizaines de relations.

L'analogie : Imaginez un professeur corrigeant une classe. Dans une classe normale, si un élève part, le professeur perd seulement un devoir. Mais dans cette classe relationnelle, si un élève part, il emporte avec lui tous ses projets de groupe, ses évaluations par les pairs et ses partenaires d'étude. Soudain, la feuille de notes du professeur change radicalement parce qu'une personne manque à l'appel.
Le risque : Parce qu'une personne affecte de nombreuses parties du calcul, le « bruit » nécessaire pour la masquer doit être énorme, ce qui ruine la capacité de l'ordinateur à apprendre des choses utiles.

2. Le problème de la « danse en deux étapes » (Échantillonnage couplé)
Pour enseigner à l'ordinateur, nous ne lui montrons pas toute la carte d'un coup. Nous lui montrons de petits morceaux (mini-batches). Pour créer un morceau, nous choisissons d'abord des connexions réelles (échantillons positifs), puis nous inventons des connexions fictives (échantillons négatifs) pour lui apprendre ce qu'il ne doit pas attendre.

L'analogie : Imaginez que vous créez une playlist. D'abord, vous choisissez 5 chansons que vous aimez vraiment. Ensuite, pour rendre la playlist intéressante, vous choisissez 5 chansons aléatoires que vous n'aimez pas pour les comparer aux 5 premières.
Le risque : La deuxième étape (choisir les chansons que l'on « n'aime pas ») dépend entièrement de la première étape. Si vous changez les 5 premières chansons, les 5 suivantes changent aussi. La mathématique de la confidentialité standard suppose que ces étapes sont indépendantes, comme si l'on choisissait deux playlists distinctes. Parce qu'elles sont liées, l'ancienne mathématique de la confidentialité ne fonctionne plus, et nous ne savons pas à quel point les données sont réellement sécurisées.

La solution : Un bouclier de confidentialité plus intelligent

Les auteurs ont construit une nouvelle version du bouclier de confidentialité spécifiquement pour ces cartes de connexions. Ils ont résolu les deux problèmes ci-dessus avec deux astuces ingénieuses :

1. Le « Coupeur d'Équité » (Écrêtage de gradient adaptatif)
Au lieu d'utiliser une règle universelle pour limiter l'influence d'une personne, ils ont rendu la règle dynamique.

La correction : Si une personne apparaît dans de nombreuses relations dans le morceau actuel, le système « baisse automatiquement le volume » de sa contribution plus que d'habitude. Si elle apparaît rarement, le volume reste normal.
Le résultat : Cela maintient la stabilité mathématique. Cela empêche une personne populaire de dominer le processus d'apprentissage, ce qui signifie que nous n'avons pas besoin d'ajouter autant de « bruit » pour la protéger. C'est comme un professeur qui sait que si un élève est dans 10 groupes, il ne compte que pour un seul élève pour la note finale, et non pour dix.

2. La « Danse strictement ordonnée » (Échantillonnage dépendant de la cardinalité)
Ils ont modifié la façon dont ils choisissent les connexions fictives (négatives) pour que les deux étapes de la danse ne soient que lâchement liées.

La correction : Au lieu de choisir les connexions fictives en fonction des connexions réelles choisies, ils choisissent d'abord un nombre fixe de personnes au hasard, puis ils les associent.
Le résultat : Cela rend les deux étapes mathématiquement prévisibles. Cela leur permet de prouver exactement la confidentialité préservée, même si les étapes sont liées. C'est comme dire : « Nous choisirons exactement 10 personnes au hasard pour la liste des "je n'aime pas", peu importe les 5 chansons que nous avons choisies pour la liste des "j'aime". »

Les résultats

L'équipe a testé cette nouvelle méthode sur des données du monde réel, plus précisément en affinant de grands modèles de langage (comme ceux qui alimentent les chatbots) pour comprendre les relations dans des réseaux d'articles scientifiques et de données d'achats en ligne.

Meilleure confidentialité : Ils ont prouvé mathématiquement que leur méthode offre des garanties solides qu'aucune donnée d'une personne individuelle ne peut être rétro-ingéniérée.
Meilleur apprentissage : Comme leur méthode n'avait pas besoin d'ajouter autant de « bruit » que les anciennes méthodes, l'ordinateur a beaucoup mieux appris. Il pouvait prédire les relations (comme « qui achètera ceci ensuite ») avec beaucoup plus de précision que les précédentes méthodes respectant la vie privée.

En résumé

Cet article traite de l'enseignement aux ordinateurs comment apprendre à partir de réseaux de relations complexes sans exposer les secrets des individus dans ce réseau. Les auteurs ont réalisé que les anciens outils de confidentialité étaient trop rudimentaires pour cette tâche, alors ils ont construit un outil sur mesure qui ajuste les règles de confidentialité en fonction de l'activité de chaque personne et de la façon dont les données sont échantillonnées. Le résultat est un système qui garde les secrets en sécurité tout en permettant à l'ordinateur d'apprendre efficacement.

Résumé Technique : Apprentissage Relationnel avec Confidentialité Différentielle et Garanties de Confidentialité au Niveau de l'Entité

1. Formulation du Problème

L'article traite du défi consistant à entraîner des modèles d'apprentissage automatique sur des données relationnelles et structurées en réseau tout en fournissant des garanties formelles de confidentialité différentielle (DP) au niveau de l'entité (ou du nœud). Dans l'apprentissage relationnel, les modèles (tels que les encodeurs d'attributs de nœuds) sont entraînés pour prédire des relations (arêtes) entre des entités (nœuds) en utilisant des fonctions de perte contrastives.

La méthode DP-SGD (Stochastic Gradient Descent à Confidentialité Différentielle) standard, conçue pour des données non structurées et indépendantes, fait face à deux échecs critiques lorsqu'elle est appliquée directement à l'apprentissage relationnel :

Sensibilité Élevée : Dans les données de graphes, une seule entité (nœud) participe souvent à plusieurs relations. Par conséquent, la suppression ou la modification d'un seul nœud peut modifier de multiples tuples d'arêtes au sein d'un mini-lot (mini-batch), provoquant un changement significatif du gradient à travers de nombreux termes. Cela conduit à une sensibilité démesurée ou excessivement élevée, nécessitant une quantité prohibitive de bruit pour masquer la contribution de l'entité.
Échantillonnage Couplé : Les mini-lots d'apprentissage relationnel sont généralement construits via un processus à plusieurs étapes : d'abord l'échantillonnage d'arêtes positives (relations observées), puis la génération d'arêtes négatives (relations manquantes) conditionnées par les échantillons positifs. Cette interdépendance viole l'hypothèse standard du DP-SGD qui repose sur un échantillonnage indépendant en une seule étape, rendant les analyses classiques d'amplification de la confidentialité (qui reposent sur le sous-échantillonnage de jeux de données indépendants) inapplicables.

2. Méthodologie

Les auteurs proposent un cadre DP-SGD sur mesure qui intègre trois composantes clés pour surmonter ces défis :

A. Écrêtage de Gradient Adaptatif (FREQ-CLIP)
Pour traiter la sensibilité élevée, l'article introduit un schéma d'écrêtage de gradient adaptatif. Contrairement à l'écrêtage standard qui utilise un seuil fixe $C$ pour tous les échantillons, cette méthode ajuste dynamiquement le seuil d'écrêtage en fonction de la fréquence d'occurrence des nœuds dans un mini-lot.

Mécanisme : Pour chaque tuple d'arête $T_i$ , le seuil d'écrêtage est mis à l'échelle par la fréquence maximale de tout nœud apparaissant dans ce tuple (tant dans les arêtes positives que négatives).
Effet : Cela garantit que la sensibilité locale du gradient du mini-lot par rapport à la suppression d'un seul nœud est bornée par une constante, même si le nœud apparaît dans plusieurs relations. Plus précisément, cela borne la sensibilité par $(1 + |B^-(u^*)|) \cdot C$ , où $|B^-(u^*)|$ est le nombre de tuples d'arêtes où le nœud n'apparaît que dans les arêtes négatives.

B. Échantillonnage Couplé Dépendant de la Cardinalité
Pour gérer l'analyse de confidentialité de l'échantillonnage multi-étapes, les auteurs formalisent une sous-classe d'échantillonnage couplé où la dépendance entre les étapes provient uniquement des contraintes de taille d'échantillon (cardinalité), et non du contenu spécifique des échantillons.

Implémentation : Ils proposent une stratégie spécifique de sous-échantillonnage négatif (Algorithme 2 : Échantillonnage Négatif Sans Remise). Dans ce schéma, les arêtes négatives sont construites en associant des nœuds échantillonnés indépendamment de l'ensemble des nœuds avec les extrémités des arêtes positives échantillonnées.
Avantage : Cette conception garantit que l'étape d'échantillonnage négatif dépend uniquement du nombre d'arêtes positives échantillonnées, et non de leur identité spécifique. Ce découplage permet d'analyser le processus complexe à deux étapes comme un mécanisme d'échantillonnage dépendant de la cardinalité traitable.

C. Analyse d'Amplification de la Confidentialité
L'article dérive une borne d'amplification de la confidentialité rigoureuse pour ce cas spécifique d'échantillonnage couplé dépendant de la cardinalité.

Résultat : Ils prouvent que pour un jeu de données composite où la première étape est un échantillonnage de Poisson et la seconde est un échantillonnage sans remise (dépendant uniquement de la taille de la première), le coût de confidentialité peut être étroitement borné en utilisant la Confidentialité Différentielle de Rényi (RDP).
Intégration : En combinant l'écrêtage adaptatif (qui borne la sensibilité) avec la stratégie d'échantillonnage spécifique (qui permet la borne d'amplification), les auteurs fournissent une garantie $(\alpha, \epsilon(\alpha))$ -RDP prouvable pour l'ensemble du processus d'entraînement.

3. Contributions Clés

Analyse de Sensibilité et Écrêtage Adaptatif : Une analyse rigoureuse de la sensibilité du gradient dans l'apprentissage relationnel, menant à un algorithme d'écrêtage de gradient adaptatif basé sur la fréquence qui contrôle efficacement la sensibilité sans supposer de degrés de nœuds extrêmes.
Formalisation de l'Échantillonnage Couplé : L'extension de la théorie de l'amplification de la confidentialité à une sous-classe traitable d'échantillonnage couplé où les dépendances sont limitées aux tailles d'échantillons, fournissant les premières bornes d'amplification pour ce contexte.
Variante de DP-SGD Sur Mesure : Un algorithme complet (Algorithme 3) qui intègre la limitation du degré (degree capping), l'écrêtage adaptatif et l'échantillonnage dépendant de la cardinalité pour obtenir des garanties de confidentialité au niveau de l'entité.
Validation Empirique : Démonstration de l'efficacité de la méthode pour l'ajustement fin (fine-tuning) d'encodeurs de texte pré-entraînés (ex: BERT, Llama2) sur des réseaux attribués au texte pour la prédiction de relations zero-shot.

4. Résultats Expérimentaux

Les auteurs ont évalué leur méthode sur des jeux de données de réseaux attribués au texte (réseaux de citations MAG et réseaux d'achats conjoints Amazon) dans le but d'ajuster des encodeurs pour la prédiction de relations.

Bornes de Confidentialité : L'analyse numérique des bornes RDP dérivées (Éq. 3) montre que la méthode proposée atteint des bornes de confidentialité nettement plus serrées par rapport aux mécanismes gaussiens naïfs et au DP-SGD standard avec un écrêtage fixe.
Compromis Utilité-Confidentialité : Dans les tâches de prédiction de relations (mesurées par PREC@1 et MRR), la méthode proposée surpasse systématiquement :
- L'ajustement fin non privé (comme attendu, mais avec des garanties de confidentialité).
- Les modèles de base non ajustés.
- Le DP-SGD standard avec écrêtage de gradient fixe sous les mêmes budgets de confidentialité ( $\epsilon = 4$ et $\epsilon = 10$ ).
Études d'Ablation : Les expériences indiquent qu'augmenter le nombre d'échantillons négatifs par arête positive et le plafonnement du degré des nœuds améliore généralement l'utilité du modèle sous des contraintes de confidentialité fixes.

5. Signification et Revendications

L'article affirme fournir le premier cadre de principe pour l'apprentissage relationnel avec confidentialité différentielle au niveau de l'entité offrant des garanties formelles. Sa signification réside dans :

Combler le fossé : Il répond aux défis structurels spécifiques des données de graphes (sensibilité élevée et échantillonnage couplé) qui empêchent l'application directe du DP-SGD standard.
Rigueur Théorique : Il dépasse les applications heuristiques de la DP sur les graphes en fournissant une analyse de sensibilité rigoureuse et un nouveau théorème d'amplification de la confidentialité pour les processus d'échantillonnage dépendants.
Utilité Pratique : Il démontre qu'une confidentialité stricète au niveau de l'entité peut être maintenue sans perte catastrophique de performance du modèle, ce qui le rend viable pour des domaines sensibles comme la santé et la finance où les données relationnelles sont prédominantes.

Les auteurs soulignent que leur approche permet l'ajustement fin de modèles de fondation sur des données relationnelles tout en protégeant la confidentialité des entités individuelles, une capacité auparavant entravée par l'absence de mécanismes de confidentialité appropriés pour l'échantillonnage relationnel couplé.