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

Titel: Optimale Ontwerpen onder Interferentie, Homofilie en Robuustheid Trade-offs

Auteurs: Vydhourie Thiyageswaran, Alex Kokot, Jennifer Brennan, Marina Meilă, Christina Lee Yu, Maryam Fazel.

---

1. Probleemstelling

In experimenten op netwerken (zoals sociale netwerken) is de Stable Unit Treatment Value Assumption (SUTVA) vaak geschonden door netwerkinterferentie: de uitkomst van een eenheid hangt niet alleen af van de eigen behandeling, maar ook van de toewijzingen van zijn buren.

• Het Dilemma: Traditionele cluster-gewijze randomisatie (waarbij sterk verbonden eenheden dezelfde behandeling krijgen) wordt vaak gebruikt om interferentie-bias te verminderen. Echter, in netwerken met homofilie (het fenomeen dat "soort zoekt soort", waarbij gelijkenis in kenmerken leidt tot connecties), kan cluster-randomisatie averechts werken. Als clusters samenvallen met homofiele groepen, kunnen de behandelings- en controlegroepen onbalans vertonen in covariaten, wat de schatting van het Global Average Treatment Effect (GATE) onnauwkeurig maakt.
• De Uitdaging: Er is een fundamenteel compromis nodig tussen:
  1. Interferentie: Een ontwerp dat interferentie minimaliseert (vaak vereist clusteren).
  2. Homofilie: Een ontwerp dat covariaten balanseert over homofiele groepen (vereist spreiding).
  3. Robuustheid: Een ontwerp dat bestand is tegen heterogene variatie (variatie die niet door het netwerk of covariaten wordt verklaard), wat vaak randomisatie vereist.

Bestaande methoden focussen vaak op slechts één van deze aspecten of maken sterke aannames die in de praktijk niet gelden.

---

2. Methodologie

De auteurs ontwikkelen een nieuw raamwerk voor het optimaliseren van experimentele ontwerpen onder een potentiële uitkomsten-model (potential outcomes framework).

A. Het Model

Ze definiëren een model voor de uitkomsten $Y_i(z)$ dat drie componenten bevat:

1. Baseline ($\alpha$) en Behandelings-effect ($\phi$): Deze worden ontbonden in een homofiele component (gladde variatie over het netwerk) en een heterogene variatie component (residuen).
2. Interferentie ($s(z)$): Een term die de invloed van buren beschrijft.
3. Beperkingen: De auteurs introduceren parameters om deze componenten te kwantificeren:
   • $\eta$: Beperkt de homofilie (via de Laplacian $L$).
   • $\gamma$: Beperkt de interferentie (via de pseudo-inverse Laplacian $L^\dagger$).
   • $\kappa$: Beperkt de heterogene variatie (via Schatten-normen van de covariantiematrix van de residuen).

B. De Optimale Ontwerp-Formulering

Het doel is het minimaliseren van de Mean Squared Error (MSE) van de Horvitz-Thompson schatter voor het GATE. De auteurs leiden een bovengrens voor de worst-case MSE af die afhangt van de covariantiematrix $X$ van de toewijzing.

Het optimalisatieprobleem wordt geformuleerd als een Semidefinite Program (SDP):
$$\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)$$
Onder de voorwaarden $X \succeq 0$ en $\text{diag}(X) = 1$.

• $\text{Tr}(LX)$: Straft "gespreide" ontwerpen; bevordert clustering (reductie van interferentie).
• $\text{Tr}(L^\dagger X)$: Straft "geclusterde" ontwerpen; bevordert spreiding over het netwerk (reductie van homofilie-bias).
• $\|X\|_q$: Een straffingsterm voor de Schatten-norm die robuustheid tegen heterogene variatie garandeert (drijft naar meer randomisatie).
• $\text{Tr}(\mathbf{1}\mathbf{1}^T X)$: Zorgt voor een niet-degenererde oplossing.

C. Oplossingsalgoritmen

Om dit probleem op te lossen en een binair toewijzingsvector te genereren, stellen de auteurs twee complementaire methoden voor:

1. SDP met Gaussische Rounding:

   • Het SDP wordt opgelost om de optimale continue covariantiematrix $X_{SDP}$ te vinden.
   • Er wordt een multivariate Gaussische steekproef $\xi \sim \mathcal{N}(0, X_{SDP})$ getrokken.
   • De componenten worden afgerond (via een aangepaste versie van de Goemans-Williamson rounding voor MAXCUT) om een binaire toewijzing te krijgen.
   • Dit biedt sterke theoretische benaderingsgaranties.

2. Aangepast Gram-Schmidt Walk (GSW):

   • Een adaptatie van het recente Gram-Schmidt Walk algoritme (Harshaw et al., 2024), een vector-balancing methode.
   • Het algoritme balanceert covariaten die zijn afgeleid van de Laplacian eigenvectoren en de robustheidsparameters.
   • Dit is computatie-efficiënter voor grote netwerken dan het oplossen van een SDP.

---

3. Belangrijkste Bijdragen

• Unificerend Raamwerk: De eerste methode die homofilie, netwerkinterferentie en robuustheid tegen heterogene variatie expliciet in één optimalisatieprobleem combineert.
• Nieuwe Theoretische Grenzen: Afleiding van worst-case MSE-bounds die de trade-offs tussen de drie factoren kwantificeren via de parameters $\eta, \gamma, \kappa$.
• Interpretatie van Eigenwaarden: Het tonen dat interferentie en homofilie kunnen worden gezien als covariaten die zijn geschaald met Laplacian-eigenwaarden, wat een brug slaat tussen covariaten-balancing en interferentie-literatuur.
• Twee Praktische Algoritmen: Een SDP-benadering (hoogwaardig, theoretisch sterk) en een GSW-benadering (schaalbaar, snel).
• Validatie: Uitgebreide experimenten op gesimuleerde netwerken (SBM, Barabási-Albert) en een real-world dataset van dorpen in Karnataka, India (met caste-homofilie).

---

4. Resultaten

• Simulaties: De voorgestelde ontwerpen presteren consistent beter dan bestaande methoden (zoals Bernoulli-randomisatie, Louvain-clustering, Spectral clustering, en Causal clustering) in termen van worst-case MSE, vooral wanneer de niveaus van homofilie en interferentie hoog zijn.
• Trade-off Visualisatie: De experimenten tonen aan dat het raamwerk flexibel is:
  • Bij hoge $\gamma$ (interferentie) neigt het ontwerp naar clustering.
  • Bij hoge $\eta$ (homofilie) neigt het ontwerp naar spreiding (diffusie).
  • Bij hoge $\kappa$ (robustheid) neigt het ontwerp naar unit-level randomisatie.
• Real Data: Op het dorpsnetwerk in India, waar caste een sterke homofiele structuur vormt, vermijden de nieuwe ontwerpen de onnauwkeurigheid die optreedt bij traditionele cluster-randomisatie (die vaak per ongeluk hele kasten in één groep plaatst).
• Algoritme Vergelijking: De SDP + Gaussische rounding benadert de theoretische optimum zeer nauwkeurig. Het aangepaste GSW-algoritme biedt vergelijkbare prestaties met een lagere rekenkosten, hoewel de theoretische bounds iets ruimer zijn.

---

5. Betekenis en Impact

Dit artikel is significant voor het veld van causale inferentie en experimenteel ontwerp om de volgende redenen:

1. Oplossing voor een Fundamenteel Conflict: Het lost het langdurige probleem op dat cluster-randomisatie, hoewel nuttig voor interferentie, schadelijk kan zijn bij homofilie. Het biedt een wiskundig onderbouwde manier om dit compromis te managen.
2. Robuustheid: Door heterogene variatie expliciet te modelleren, zorgen de ontwerpen voor betrouwbare schattingen zelfs als het netwerkmodel imperfect is of als er onverklaarde variatie bestaat.
3. Praktische Toepasbaarheid: De methode is niet beperkt tot theoretische netwerken; het werkt op complexe, real-world netwerken (zoals sociale structuren in ontwikkelingslanden) en kan worden aangepast aan verschillende schattingsproblemen.
4. Toekomstgericht: Het raamwerk biedt een basis voor online experimenten waar parameters adaptief kunnen worden geleerd, en het opent de deur voor het gebruik van andere similariteitskernels dan de grafische Laplacian.

Kortom, dit werk levert een geavanceerd, wiskundig onderbouwd instrument voor onderzoekers en datawetenschappers om experimenten in netwerkomgevingen te ontwerpen die zowel efficiënt als robuust zijn.