Optimal Design under Interference, Homophily, and Robustness Trade-offs

1. Problématique et Contexte

L'estimation de l'effet moyen global du traitement (GATE) dans les réseaux sociaux est entravée par deux phénomènes majeurs :

• L'interférence réseau : Le résultat d'une unité dépend non seulement de son propre traitement, mais aussi de celui de ses voisins, violant l'hypothèse SUTVA (Stable Unit Treatment Value Assumption).
• L'homophilie : La tendance des individus à se connecter à des personnes qui leur sont similaires (démographiquement, comportementalement, etc.).

Le dilemme central :
Les approches classiques de randomisation par grappes (cluster randomization) visent à réduire le biais d'interférence en regroupant les unités fortement connectées dans le même groupe de traitement. Cependant, dans un contexte d'homophilie, ces grappes peuvent devenir non représentatives (par exemple, un groupe de traitement composé uniquement d'une caste ou d'un groupe démographique spécifique). Cela introduit un biais de sélection et augmente la variance de l'estimateur, car les covariables ne sont pas équilibrées entre les groupes de traitement et de contrôle.

L'objectif de l'article est de concevoir des plans d'expérience optimaux qui naviguent intelligemment entre trois compromis :

1. Minimiser le biais d'interférence (en regroupant les voisins).
2. Minimiser le biais d'homophilie (en dispersant les traitements à travers les groupes similaires pour assurer l'équilibre des covariables).
3. Assurer la robustesse face à une variation hétérogène non expliquée par la structure du réseau (bruit résiduel).

2. Méthodologie et Cadre Théorique

Les auteurs proposent un nouveau modèle de résultats potentiels et un cadre d'optimisation pour minimiser l'erreur quadratique moyenne (MSE) dans le pire des cas.

A. Modèle de Résultats Potentiels

Le modèle décompose les résultats $Y$ en trois composantes :

1. Composante homophile ($h$) : Une variation lisse liée à la structure du graphe, contrainte par une norme quadratique impliquant le Laplacien du graphe $L$ (paramètre $\eta$).
2. Composante d'interférence ($s$) : Un terme qui dépend des traitements des voisins, contraint par une norme quadratique sur l'inverse du Laplacien pseudo-inversé $L^\dagger$ (paramètre $\gamma$).
3. Variation hétérogène ($\epsilon$) : Un résidu non expliqué, modélisé comme un effet aléatoire avec une contrainte sur la norme de Schatten de sa matrice de covariance (paramètre $\kappa$).

L'estimateur utilisé est l'estimateur de Horvitz-Thompson (version "vanilla"), choisi pour sa simplicité et sa capacité à capturer les compromis sans nécessiter de mappage d'exposition complexe.

B. Formulation de l'Optimisation

Le problème est reformulé comme une optimisation sur la matrice de covariance $X = \mathbb{E}[xx^T]$ de l'assignation de traitement (où $x = 2z - 1$). L'objectif est de minimiser une borne supérieure du MSE, qui s'exprime comme une combinaison linéaire de termes de trace et de normes :

$$\min_X \quad \tilde{\eta}\text{Tr}(L^\dagger X) + \tilde{\gamma}\text{Tr}(LX) + \tilde{\kappa}\|X\|_q + \text{Tr}(\mathbf{1}\mathbf{1}^T X)$$

Sous les contraintes $X \succeq 0$ et $\text{diag}(X) = 1$.

• $\text{Tr}(LX)$ : Pénalise les coupes dans le graphe (favorise les designs en grappes pour réduire l'interférence).
• $\text{Tr}(L^\dagger X)$ : Favorise les designs "étalés" (diffusifs) pour équilibrer les covariables dans un contexte d'homophilie (minimisation de la résistance effective).
• $\|X\|_q$ : Terme de régularisation (norme de Schatten) qui encourage la randomisation pour la robustesse face à la variation hétérogène.

C. Algorithmes de Résolution

Les auteurs proposent deux approches complémentaires pour résoudre ce problème :

1. Relaxation SDP et Arrondi Gaussien :

   • Le problème est formulé comme un Programme Semi-Défini (SDP).
   • Une procédure d'arrondi de type Goemans-Williamson (inspirée de l'algorithme d'approximation MAXCUT) est utilisée pour convertir la solution continue $X_{SDP}$ en une assignation binaire $z \in \{0, 1\}^n$.
   • Cette méthode offre des garanties théoriques d'approximation solides.

2. Algorithme Adapté Gram-Schmidt Walk (GSW) :

   • Adaptation de l'algorithme de "balancing vector" de Harshaw et al. (2024).
   • L'algorithme traite le problème comme un équilibrage de covariables où les covariables sont induites par les vecteurs propres du Laplacien et de son inverse.
   • Cette approche est plus efficace computationnellement pour les grands réseaux ($n$ élevé) et fournit des garanties directes sur le MSE dans le pire des cas.

3. Résultats Principaux

• Théorèmes de Bornes : Les auteurs établissent des bornes supérieures pour le MSE dans le pire des cas (Théorèmes 2, 8 et 9), montrant que la minimisation de la fonction objectif SDP contrôle effectivement l'erreur d'estimation.
• Interprétation des Compromis :
  • Lorsque l'homophilie ($\eta$) domine, le design optimal tend à disperser les traitements (réduire $\text{Tr}(L^\dagger X)$).
  • Lorsque l'interférence ($\gamma$) domine, le design tend à regrouper les traitements (réduire $\text{Tr}(LX)$).
  • Lorsque la robustesse ($\kappa$) est priorisée, le design se rapproche d'une randomisation de Bernoulli unitaire.
• Performance Empirique :
  • Sur des données simulées (modèles SBM, Barabási-Albert) et un jeu de données réel (réseaux de villages en Inde, données de Banerjee et al.), les designs proposés surpassent systématiquement les méthodes existantes (randomisation par grappes standard, randomisation de Bernoulli, clustering spectral, etc.).
  • L'algorithme SDP + Arrondi Gaussien fournit les meilleures bornes théoriques mais est coûteux en calcul pour les grands $n$.
  • L'algorithme Gram-Schmidt Walk offre un compromis excellent, avec des performances très proches de l'optimum SDP tout en restant scalable.

4. Contributions Clés

1. Unification théorique : Création d'un cadre unifié qui formalise mathématiquement le compromis entre l'interférence, l'homophilie et la robustesse, généralisant des résultats antérieurs (comme la randomisation par grappes ou l'équilibrage de covariables).
2. Nouveau modèle de résultats potentiels : Introduction d'un modèle décomposé en composantes lisses (homophilie/interférence) et résiduelles, permettant une analyse fine des sources d'erreur.
3. Algorithmes pratiques : Développement de deux méthodes de conception (SDP et GSW) adaptées aux contraintes de réseaux complexes, avec des garanties de performance dans le pire des cas.
4. Interprétation spectrale : Lien explicite entre la minimisation de l'erreur d'estimation et l'équilibrage des vecteurs propres du Laplacien du graphe, reliant la littérature sur l'interférence à celle sur l'équilibrage de covariables.

5. Signification et Impact

Cet article est significatif car il résout un problème fondamental en inférence causale sur les réseaux : comment concevoir des expériences qui ne sont pas biaisées par la structure sociale (homophilie) tout en contrôlant les effets de débordement (interférence).

• Pour les praticiens : Il fournit une boîte à outils (via les paramètres $\eta, \gamma, \kappa$) pour adapter la conception d'expériences aux spécificités du réseau étudié, plutôt que d'appliquer des designs rigides.
• Pour la recherche : Il ouvre la voie à des designs adaptatifs en ligne et à l'intégration de connaissances a priori (priors) sur la structure du réseau.
• Application réelle : La validation sur des données de microfinance en Inde démontre l'utilité de la méthode pour des politiques publiques où les biais de sélection et les effets de réseau sont critiques.

En résumé, l'article propose une avancée majeure en passant d'une approche heuristique de la conception d'expériences sur les réseaux à une approche optimisée et mathématiquement garantie, capable de s'adapter dynamiquement aux tensions entre les différentes sources de biais.