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

1. Problem Statement

The paper addresses the challenge of estimating the Global Average Treatment Effect (GATE) in the presence of network interference (where a unit's outcome depends on the treatment assignments of its neighbors).

• The Conflict: Standard approaches to mitigate interference bias involve cluster randomization (grouping connected nodes and assigning treatment at the cluster level). However, social networks often exhibit homophily (the tendency for similar individuals to connect). If clusters align with homophilous groups (e.g., caste, age, or socioeconomic status), cluster randomization can lead to unrepresentative treatment/control samples, inflating variance and bias.
• The Trade-off: There is a fundamental tension between:
  1. Interference Reduction: Requires clustering connected nodes (minimizing cut edges).
  2. Homophily Mitigation: Requires spreading treatment across natural clusters to ensure covariate balance.
  3. Robustness: Requires randomization to protect against heterogeneous variation (unexplained variation in outcomes not captured by the network structure).
• Goal: Develop a unified framework to optimize experimental designs that balance these three competing objectives to minimize the worst-case Mean Squared Error (MSE) of the Horvitz-Thompson estimator.

2. Methodology

A. Potential Outcomes Model

The authors propose a novel potential outcomes model that decomposes the baseline ($\alpha$) and treatment effect ($\phi$) vectors into three components:

1. Homophilous Component ($h$): Smooth variation aligned with the graph structure. Formalized via a quadratic constraint using the Graph Laplacian $L$: $h^T L h \leq \eta$.
2. Interference Component ($s$): Captures the deviation caused by neighbors' treatments. Formalized via the pseudo-inverse Laplacian $L^\dagger$: $\sup_z s(z)^T L^\dagger s(z) \leq \gamma$.
3. Heterogeneous Variation ($\epsilon$): Residual variation not explained by the graph. Constrained via Schatten norms of the covariance matrix $\Sigma$: $\|\Sigma\|_{q^*} \leq \kappa$.

B. Optimization Framework

The authors derive a worst-case MSE bound for the Horvitz-Thompson estimator. The bound depends on the design covariance matrix $X = E[xx^T]$ (where $x = 2z - 1$ is the recoded treatment assignment).

The optimization problem is formulated as a Semidefinite Program (SDP):
$$\begin{aligned} \min_{X \in \mathbb{R}^{n \times n}} \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) \\ \text{s.t.} \quad & X \succeq 0, \\ & \text{diag}(X) = 1. \end{aligned}$$

• $\text{Tr}(LX)$: Encourages clustering (minimizing cuts) to reduce interference.
• $\text{Tr}(L^\dagger X)$: Encourages "spread-out" designs (minimizing effective resistance) to balance homophilous covariates.
• $\|X\|_q$: A Schatten norm penalty that encourages randomization (robustness) against heterogeneous variation. As $\kappa \to \infty$, the solution approaches unit-level Bernoulli randomization.

C. Solution Approaches

The paper proposes two complementary algorithms to solve this problem:

1. SDP + Gaussian Rounding:

   • Solves the convex SDP relaxation to obtain a continuous covariance matrix $X_{SDP}$.
   • Applies Gaussian rounding (inspired by the Goemans-Williamson algorithm for MAXCUT). A multivariate Gaussian vector is sampled from $N(0, X_{SDP})$, and entries are rounded to $\pm 1$ based on sign or quantiles to satisfy marginal treatment probabilities.
   • Pros: Provides strong theoretical approximation guarantees; flexible for adding constraints.
   • Cons: Computationally expensive for large $n$.

2. Adapted Gram-Schmidt Walk (GSW):

   • Adapts the Gram-Schmidt Walk vector balancing algorithm (Harshaw et al., 2024).
   • Treats the trade-off terms as covariates to be balanced. The algorithm iteratively updates a fractional assignment to a binary one while maintaining balance in the span of the augmented covariate matrix.
   • Pros: Computationally efficient ($O(n^2)$ or better); scales to larger networks.
   • Cons: Theoretical bounds may be looser than the SDP approach for very large $n$.

3. Key Contributions

• Unified Framework: The first framework to simultaneously optimize for interference, homophily, and robustness, recovering existing designs (like cluster randomization or Bernoulli randomization) as limiting cases of the trade-off parameters.
• Novel MSE Bound: Derivation of a tight worst-case MSE bound that explicitly links the design covariance matrix to the spectral properties of the network (via $L$ and $L^\dagger$) and the magnitude of heterogeneous variation.
• Algorithmic Innovation:
  • Application of Gaussian rounding to the specific structure of network interference problems.
  • Adaptation of the Gram-Schmidt Walk algorithm to handle network interference and homophily constraints, framing them as a covariate balancing problem.
• Interpretability: The authors provide a natural interpretation of interference and homophily by viewing eigenvalue-scaled Laplacian eigenvector embeddings as unit-level covariates, bridging the gap between causal inference and spectral graph theory.

4. Results

• Theoretical Guarantees:
  • SDP Approach: Theorem 8 establishes that the Gaussian rounding procedure yields a covariance matrix $\Xi$ such that the resulting MSE is within a constant factor of the optimal SDP solution, provided the SDP solution is non-degenerate.
  • GSW Approach: Theorem 9 provides a worst-case error bound for the adapted GSW algorithm, showing it effectively balances the trade-off parameters.
• Empirical Performance:
  • Simulated Data: Experiments on Synthetic Block Models (SBM), Barabási-Albert, and Erdős-Rényi graphs show that the proposed designs (both SDP and GSW) consistently achieve lower worst-case MSE compared to standard cluster randomization (Louvain, Spectral, Causal clustering) and Bernoulli randomization.
  • Real Data: Using a village network dataset from Karnataka, India (Banerjee et al., 2013), which exhibits strong caste-based homophily:
    • Standard cluster randomization designs resulted in high MSE because they aligned with caste groups, leading to imbalanced treatment assignment across castes.
    • The proposed optimal designs successfully "spread" treatment across caste groups while managing interference, significantly reducing the worst-case MSE.
  • Trade-off Visualization: The paper demonstrates how varying parameters ($\eta, \gamma, \kappa$) shifts the design from clustered (low interference, high homophily bias) to spread-out (low homophily bias, high interference) to fully randomized (high robustness).

5. Significance

• Practical Impact: Provides a principled, data-driven method for designing experiments in social networks (e.g., microfinance, public health, technology adoption) where interference and homophily are prevalent. It prevents the common pitfall of blindly applying cluster randomization in homophilous networks.
• Theoretical Advancement: Generalizes the MAXCUT approximation literature and vector balancing techniques to the specific context of causal inference under interference. It offers a rigorous way to quantify the "cost" of interference and homophily in experimental design.
• Flexibility: The framework is adaptable to various estimators (e.g., Difference-in-Means) and can incorporate prior knowledge or covariates beyond the network structure (e.g., demographic data) via general similarity kernels.

In summary, this paper offers a robust, optimization-based solution to the complex problem of experimental design in networked environments, successfully navigating the delicate balance between reducing interference bias, accounting for homophily, and ensuring robustness against unmodeled variation.