Active Learning on Adversarially Corrupted Graphs

Résumé Technique : Apprentissage Actif sur des Graphes Corrompus de Manière Adversaire

Formulation du Problème
L'article traite du problème de l'apprentissage actif sur des graphes dont la structure sous-jacente a été altérée par un adversaire. Le cadre implique un graphe « de vérité terrain » initial $G^* = (V^*, E^*)$ et un ensemble de sommets corrompus (malveillants) $I$. Un adversaire doté d'un budget $b$ construit un graphe final $G$ à travers trois étapes :

1. La création d'un sous-graphe arbitraire sur un ensemble de nouveaux sommets $I$ (où $|I| \le |V^*|$).
2. La connexion d'au plus $b$ sommets de $V^*$ à l'ensemble $I$. Cela définit le pouvoir de l'adversaire : la taille de la frontière de $I$ dans $G$ est bornée par $b$ (c'est-à-dire $|\partial_G(I)| \le b$).
3. L'ajout arbitraire d'arêtes au sein de $G^*$.
   L'algorithme reçoit le graphe résultant $G$ et a accès à un oracle de labels $O_{G,I}$, qui révèle si un sommet interrogé appartient à $I$. L'objectif est d'atteindre une récupération faible (weak recovery) : identifier un sous-ensemble $\hat{I}$ tel que la différence symétrique $|\hat{I} \triangle I| \le \gamma |V(G)|$ avec une haute probabilité, en utilisant un nombre minimal de requêtes de labels. Le défi réside dans le fait que $G^*$ et le sous-graphe corrompu $G[I]$ peuvent être arbitraires, et l'adversaire peut manipuler la structure du graphe de manière significative, à condition que le nombre de connexions avec le graphe original reste faible.

Méthodologie
La solution proposée repose sur la propriété structurelle de l'expansion de sommets (vertex expansion) et sur un cadre algorithmique récursif.

1. Intuition Structurelle : L'intuition centrale est que si l'ensemble des sommets corrompus $I$ possède une expansion de sommets nettement plus faible que les parties « saines » du graphe $G^*$, il peut être isolé. Plus précisément, les auteurs définissent une condition où $I$ est « mal expansé » par rapport au reste du graphe. Si $I$ satisfait une condition spécifique d'écart d'expansion, tout ensemble $S$ possédant une petite frontière et une taille comparable à celle de $I$ doit être fortement corrélé avec $I$.

2. Cœur Algorithmique (Somme des Carrés) : Pour trouver un tel ensemble $S$, les auteurs adaptent les algorithmes de Somme des Carrés (SoS), en modifiant spécifiquement la relaxation de programmation semi-définie (SDP) pour l'expansion de sommets proposée par Feige et al. (2005).

   • Les algorithmes standards d'expansion de sommets échouent souvent à garantir la taille de l'ensemble retourné ou fournissent des facteurs d'approximation trop lâches pour ce contexte adversaire spécifique.
   • Les auteurs introduisent un nouvel algorithme d'arrondi (rounding algorithm) pour la relaxation SoS de degré 4. Cet arrondi garantit que l'ensemble $S$ produit satisfait des contraintes de cardinalité (spécifiquement, $|S| = \Theta(|I|)$) tout en maintenant une petite frontière.
   • Cette adaptation permet à l'algorithme de trouver un ensemble $S$ qui approxime l'expansion de sommets minimale sous contraintes de taille, un résultat d'intérêt indépendant (Théorème 4).

3. Raffinement Récursif : L'algorithme fonctionne de manière itérative :

   • Il utilise la procédure basée sur SoS pour trouver un ensemble $S$ qui est fortement corrélé avec les sommets corrompus restants.
   • Il interroge l'oracle sur un petit échantillon aléatoire de $S$ et de son complément pour déterminer quel ensemble contient la majorité des nœuds corrompus.
   • L'ensemble identifié est retiré du graphe, et le processus se répète sur le graphe résiduel.
   • Les auteurs prouvent que les propriétés structurelles (spécifiquement l'expansion de sommets du graphe de vérité terrain restant) sont suffisamment préservées à travers ces itérations, permettant à l'algorithme de continuer à récupérer les nœuds corrompus jusqu'à ce qu'une fraction élevée soit identifiée.

Résultats Clés
La contribution principale est le Théorème 3, qui établit la complexité des requêtes pour la récupération faible. L'algorithme parvient à une récupération faible $(\gamma, \delta, q, b)$ si :

• Le budget de requêtes $q$ suit l'ordre de $\tilde{O}\left(\frac{1}{\gamma} (\log \frac{1}{\delta} + b\sqrt{\log n})\right)$.
• Le budget de l'adversaire $b$ est borné par l'expansion de sommets du graphe de vérité terrain $G^*$ : $b \le O\left(\frac{\gamma^6}{\log^3(1/\gamma)\sqrt{\log n}} \cdot \partial_{\eta n}(G^*)\right)$, où $\partial_{\eta n}(G^*)$ est la frontière minimale des sous-ensembles de taille au moins $\eta n$.

Essentiellement, le nombre de requêtes nécessaires est linéaire par rapport au budget de l'adversaire $b$ et inversement proportionnel à la précision souhaitée $\gamma$, à condition que le budget de l'adversaire soit faible par rapport à la connectivité (expansion de sommets) du graphe.

De plus, le Théorème 4 présente un résultat auxiliaire : un algorithme polynomial-temps randomisé qui trouve un ensemble avec une faible expansion de sommets et une taille comprise dans une plage équilibrée $[m, n-m]$, atteignant un facteur d'approximation de $O(\sqrt{\log n})$ pour certains paramètres. Cela améliore ou complète les limites existantes pour les problèmes d'expansion de petits ensembles (small-set expansion).

Signification et Revendications
L'article affirme être le premier à démontrer que l'expansion de sommets est une mesure fondamentale déterminant la complexité des requêtes des algorithmes d'apprentissage actif robustes aux attaques structurelles adverses.

• Nouveauté : Contrairement aux travaux précédents sur les attaques Sybil ou l'empoisonnement de graphes qui supposent souvent que le « bon » graphe est un expanseur ou limitent le nombre d'arêtes ajoutées, ce modèle permet des structures internes arbitraires dans les deux sous-graphes (bon et mauvais), en ne limitant que la taille de la frontière.
• Fondement Théorique : Ce travail fournit un lien théorique entre la connectivité du graphe (expansion de sommets) et la faisabilité de la détection des nœuds corrompus. Il montre que même si le graphe de vérité terrain n'est pas un expanseur global, la récupération faible est possible tant que le budget de l'adversaire est faible par rapport à l'expansion de sous-ensembles suffisamment grands.
• Contribution Algorithmique : L'article introduit un algorithme en temps polynomial pour trouver des ensembles ayant une faible expansion de sommets sous contraintes de cardinalité, un problème connu pour sa difficulté computationnelle, en exploitant et en adaptant les techniques de Somme des Carrés.

Les auteurs maintiennent un ton modeste, notant que leurs résultats dépendent d'écarts d'expansion spécifiques et que la complexité des requêtes se dégrade à mesure que la précision souhaitée $\gamma$ diminue ou que le budget de l'adversaire augmente. Ils ne prétendent pas résoudre le problème pour toutes les structures de graphes possibles ou pour des budgets d'adversaire arbitraires, mais établissent un compromis précis entre le coût des requêtes, la précision et les propriétés structurelles du graphe d'entrée.