Birba, Zelma Aubin
(2026).
« Robustesse et protection de la vie privée pour l'apprentissage sur graphes distribués » Thèse.
Montréal (Québec, Canada), Université du Québec à Montréal, Doctorat en informatique.
Fichier(s) associé(s) à ce document :
Résumé
L’analyse et l’apprentissage sur des graphes sont devenus des outils centraux pour modéliser des systèmes complexes tels que les réseaux sociaux, les systèmes de recommandation, les infrastructures de communication ou encore les réseaux biologiques. Dans de nombreux contextes réels, ces graphes sont toutefois distribués entre plusieurs entités qui ne peuvent pas partager librement leurs données en raison de contraintes de confidentialité ou de conformité réglementaire. Au-delà de ces contraintes, ce cadre distribué soulève également un problème de confiance : chaque entité ne dispose que d’une vision partielle du graphe global et ne peut pas nécessairement garantir que les graphes locaux fournis par les autres participants soient exacts ou exempts de manipulations malveillantes, notamment via des attaques d’empoisonnement. Cette thèse s’intéresse aux défis posés par l’analyse de graphes distribués sous l’angle de la protection de la vie privée, de la sécurité et de la robustesse face à l’empoisonnement. Dans un premier temps, nous étudions le problème de la prédiction de liens dans des graphes distribués, une tâche fondamentale utilisée notamment pour la recommandation ou la détection d’anomalies. Pour cela, nous proposons Crypto’Graph, un protocole cryptographique permettant à plusieurs entités de collaborer pour prédire des liens sans jamais révéler leurs voisinages locaux. Crypto’Graph repose sur des primitives de calcul sécurisé et garantit, dans un modèle d’adversaire semi-honnête, que seules des informations agrégées comme le nombre de voisins communs sont directement divulguées. Nous montrons expérimentalement que ce protocole permet d’atteindre une utilité supérieure à des approches non collaboratives, tout en respectant de fortes contraintes de confidentialité. Dans un second temps, nous montrons que la cryptographie ne suffit pas toujours à garantir une confidentialité complète. En particulier, nous introduisons GRAND, une nouvelle approche visant à reconstruire un graphe à partir de sa matrice de voisins communs, éventuellement enrichie par une connaissance partielle de sa structure. Nous formalisons le problème de reconstruction dans différents modèles d’adversaires, et proposons un ensemble d’attaques combinant propriétés combinatoires et algébriques des graphes. Nos résultats montrent qu’un adversaire peut souvent reconstruire une grande partie du graphe, voire l’intégralité de sa structure à une équivalence près, même sans connaissance préalable. Nous introduisons à cet effet la notion de d’équivalence co-carré, une nouvelle forme d’équivalence entre graphes induite par leur matrice de voisins communs. Enfin, nous étudions les implications de ces résultats sur la robustesse des graphes distribués, notamment face aux attaques par empoisonnement des données. Nous montrons comment des mécanismes de recommandation décentralisés peuvent être détournés à des fins de promotion de produits, et proposons des solutions aux vulnérabilités ainsi révélées. L’ensemble de ces travaux met en évidence les compromis fondamentaux entre utilité, confidentialité et robustesse dans l’analyse de graphes distribués, et ouvre la voie à de nouvelles approches intégrant dès leur conception la prise en charge des risques de bris de vie privée, d’empoisonnement et d’inférence.
| Type: |
Thèse ou essai doctoral accepté
|
| Informations complémentaires: |
Fichier numérique reçu en format PDF. |
|
Directeur de thèse: |
Killijian, Marc-Olivier |
| Mots-clés ou Sujets: |
Graphes distribués / Apprentissage automatique / Protection de l'information (Informatique) / Droit à la vie privée |
| Unité d'appartenance: |
Faculté des sciences > Département d'informatique |
| Déposé par: |
Service des bibliothèques
|
| Date de dépôt: |
20 oct. 2026 10:19 |
| Dernière modification: |
23 oct. 2026 13:26 |
| Adresse URL : |
https://archipel.uqam.ca/secure/id/eprint/20416 |
RECHERCHER
PARCOURIR
LIBRE ACCÈS
