Résumé Technique : Compromis Vie Privée–Utilité pour l'Estimation de Paramètres dans les Réseaux d'Ordre Supérieur à Hétérogénéité de Degré

1. Formulation du Problème

L'article traite du défi de l'estimation des paramètres dans les modèles statistiques pour les données relationnelles où les liens individuels (ou hyperarêtes) doivent rester privés face à des requêtes adverses. Dans de nombreuses applications sensibles — telles que le traçage de contacts, les transactions financières et le marketing sur les réseaux sociaux — les fournisseurs de données ne publient souvent que des informations structurelles agrégées, spécifiquement la séquence de degrés (le nombre d'interactions par nœud), plutôt que la topologie complète du réseau.

Les auteurs se concentrent sur le modèle $\beta$, un modèle statistique prototypique pour les réseaux à hétérogénéité de degré. Ils étendent ce modèle des graphes standards ($r=2$) aux hypergraphes $r$-uniformes ($r \geq 2$), où les interactions impliquent des groupes de $r$ nœuds. Dans ce cadre, la donnée observée est la séquence des $r$-degrés, et l'objectif est d'estimer le vecteur de paramètres $\beta \in \mathbb{R}^n$ régissant la probabilité de formation d'une hyperarête :
$$P[(i_1, \dots, i_r) \in E_r] = \frac{e^{\beta_{i_1} + \dots + \beta_{i_r}}}{1 + e^{\beta_{i_1} + \dots + \beta_{i_r}}}$$

Le problème central est de déterminer le risque d'estimation minimax-optimal (l'erreur quadratique moyenne dans le pire des cas) pour la récupération de $\beta$ sous des contraintes de Confidentialité Différentielle (DP). Les auteurs analysent deux cadres de confidentialité distincts :

1. Confidentialité Différentielle Locale (LDP) : Chaque nœud perturbe son propre degré avant la publication.
2. Confidentialité Différentielle Centrale (CDP) : Un curateur de confiance observe les vrais degrés et publie une statistique agrégée privatisée.

2. Méthodologie

Cadre Théorique

Les auteurs adoptent un cadre minimax pour caractériser les limites fondamentales des compromis entre vie privée et utilité. Ils supposent que le vecteur de paramètres réels est borné ($\|\beta\|_\infty \leq M$). La métrique de performance est l'erreur quadratique moyenne (MSE) normalisée : $\frac{1}{n} \mathbb{E}[\|\hat{\beta} - \beta\|_2^2]$.

Bornes Inférieures (Résultats d'Impossibilité)

• LDP : En utilisant une version localement privée de l'inégalité de Fano, les auteurs dérivent une borne inférieure sur le risque d'estimation. Ils construisent un empilement de vecteurs de paramètres séparés en norme $\ell_2$ mais induisant des distributions de degrés proches en divergence de Kullback–Leibler. Après la privatisation locale, l'incertitude introduite par le mécanisme rend la distinction fiable entre ces modèles informationnellement impossible.
• CDP : En utilisant une version différentiellement privée du lemme d'Assouad, ils établissent des bornes inférieures pour le cadre central. L'analyse révèle que le coût de la confidentialité n'apparaît que dans le terme de second ordre du risque, contrairement à l'effet dominant observé dans le cadre local.

Estimateurs (Bornes Supérieures)

Pour correspondre aux bornes inférieures, les auteurs proposent deux estimateurs spécifiques :

1. Estimateur Localement Privé ($\hat{\beta}^{loc}$) :

   • Mécanisme : Chaque nœud ajoute un bruit de Laplace discret indépendant à son vrai $r$-degré. Ce mécanisme satisfait la DP d'arête locale $\epsilon$.
   • Estimation : Un estimateur de maximum de vraisemblance (MLE) régularisé est calculé en utilisant la séquence de degrés bruitée. Le paramètre de régularisation $\lambda$ est ajusté pour équilibrer le biais et la variance.
   • Note : Les auteurs reconnaissent que pour $r \geq 3$, l'espace des séquences de degrés d'hypergraphes réalisables est complexe, et projeter les degrés bruités vers cet espace n'est pas actuellement efficace. Ainsi, ils travaillent directement avec la séquence perturbée.

2. Estimateur Centralement Privé ($\hat{\beta}^{cen}$) :

   • Mécanisme : Un curateur de confiance effectue une Descente de Gradient Différentiellement Privée (DP-GD) sur la fonction de log-vraisemblance négative régularisée en utilisant la vraie séquence de degrés.
   • Confidentialité : Un bruit gaussien est injecté dans les gradients à chaque itération pour satisfaire la DP d'arête $(\epsilon, \delta)$.
   • Optimisation : L'algorithme utilise une descente de gradient projetée avec une règle d'arrêt précoce pour éviter une injection excessive de bruit tout en assurant la convergence.

3. Résultats Clés

Taux Minimax

L'article établit des caractérisations précises en échantillon fini des taux de risque d'estimation :

• Référence Non-Privée : Le taux minimax scale en $O(n^{-(r-1)})$.
• LDP : Le risque minimax scale comme :
  $$\Omega\left( \frac{1}{\epsilon^2 n^{r-1}} \right)$$
  L'imposition de la confidentialité locale augmente la complexité de l'échantillonnage d'un facteur $O(\epsilon^{-2})$. L'estimateur de Laplace discret atteint ce taux (à un facteur logarithmique près).
• CDP : Le risque minimax scale comme :
  $$\Omega\left( \max\left\{ \frac{1}{n^{r-1}}, \frac{1}{\epsilon^2 n^{2(r-1)}} \right\} \right)$$
  Ici, le coût de la confidentialité n'apparaît que dans le terme de second ordre (le terme $1/n^{2(r-1)}$). Cela indique que la DP centrale permet des taux d'estimation nettement meilleurs que la LDP, à condition qu'un curateur de confiance existe. L'estimateur DP-GD atteint ce taux (à un facteur logarithmique près).

Validation Empirique

Les auteurs valident leurs résultats théoriques via :

1. Données Synthétiques : Expérimentations sur des hypergraphes 3-uniformes avec des tailles de réseau variables ($n \in \{50, 100, 150, 200\}$) et des budgets de confidentialité ($\epsilon$). Les résultats confirment que l'excès de risque décroît linéairement avec $\log n$ et que l'estimateur CDP surpasse systématiquement l'estimateur LDP, particulièrement pour de petits $n$ et de faibles $\epsilon$.
2. Données Réelles : Analyse du jeu de données d'emails Enron (modélisé comme un hypergraphe 3-uniforme). L'étude évalue la performance de la prédiction de liens (ROC-AUC, Average Precision) sous les deux cadres de confidentialité.
   • Constats : Les deux cadres montrent une dégradation de la performance par rapport au MLE non-privé, la LDP souffrant d'une chute plus sévère. La performance s'améliore de manière monotone à mesure que $\epsilon$ augmente.
   • Calibration : Les auteurs notent que la calibration des probabilités reste médiocre pour toutes les méthodes, attribuant cela à la nature intrinsèquement creuse (sparse) des données d'hypergraphes plutôt qu'au mécanisme de confidentialité lui-même.

4. Signification et Revendications

L'article affirme fournir la première caractérisation complète en échantillon fini des compromis vie privée–utilité pour l'estimation de paramètres dans les modèles $\beta$ sous la confidentialité différentielle locale et centrale.

• Nouveauté : Les travaux précédents sur les modèles $\beta$ privés étaient limités aux analyses asymptotiques sous des mises à l'échelle spécifiques des paramètres de confidentialité ou reposaient sur l'observation du réseau complet. Ce travail fournit des bornes minimax nettes qui capturent explicitement la dépendance vis-à-vis de la taille du réseau $n$, l'ordre de l'hyperarête $r$, et les paramètres de confidentialité $\epsilon$ et $\delta$.
• Portée : Il étend l'analyse des graphes standards aux hypergraphes d'ordre supérieur, traitant de la complexité de l'hétérogénéité de degré dans les interactions de groupe.
• Optimalité : Les estimateurs proposés sont montrés comme étant minimax-optimaux (à des constantes et facteurs logarithmiques près), établissant les limites fondamentales de ce qui est réalisable dans ces contextes.

5. Limites et Directions Futures

Les auteurs reconnaissent modestement plusieurs questions ouvertes :

• Existence du MLE Borné : Pour $r \geq 3$, les conditions sous lesquelles une solution bornée aux équations de vraisemblance existe ne sont pas totalement comprises. Les résultats actuels supposent qu'une telle solution existe.
• Stylisation du Modèle : Le modèle $\beta$ est une représentation simplifiée. Les travaux futurs pourraient explorer des modèles d'espace latent ou des paramétrisations non linéaires (ex: via des réseaux de neurones).
• Définitions de Confidentialité : L'étude se concentre sur la confidentialité des arêtes ; étendre ces résultats à la confidentialité au niveau des nœuds dans le cadre central reste une direction ouverte.
• Écart Algorithmique : Les auteurs conjecturent que si le MLE borné n'existe pas pour $r \geq 3$, il pourrait y avoir un écart intrinsèque entre les bornes inférieures informationnelles et la performance des estimateurs calculables.