Differences-in-Neighbors for Network Interference in Experiments

Tianyi Peng, Naimeng Ye, Andrew Zheng

Introduction

In modern experimental design, particularly within large-scale digital platforms and marketplaces, the Stable Unit Treatment Value Assumption (SUTVA) is frequently violated. SUTVA posits that the treatment assigned to one unit does not affect the outcomes of others. However, in interconnected systems—such as social networks or ride-sharing markets—interference is ubiquitous. A treatment applied to one user (e.g., a discount or a UI change) often spills over to their neighbors or competitors, leading to biased estimates of the Average Treatment Effect (ATE).

The Bias-Variance Trade-off

Traditionally, researchers have faced a stark choice between two suboptimal estimators when dealing with network interference:

  1. Difference-in-Means (DM): This "naive" estimator ignores interference. While it offers low variance, it suffers from high bias because it fails to account for spillover effects from treated neighbors to control units.
  2. Horvitz-Thompson (HT): This estimator uses importance sampling to provide an unbiased estimate. However, its variance grows exponentially with the degree of the network, rendering it impractical for dense, real-world graphs.

Tianyi Peng, Naimeng Ye, and Andrew Zheng propose the Differences-in-Neighbors (DN) estimator as a "Goldilocks" solution that bridges this gap, providing significant bias reduction without the variance explosion characteristic of HT.

Methodology: The DN Estimator

The DN estimator is derived from a first-order Taylor expansion of the potential outcome function. While the DM estimator can be viewed as a zeroth-order approximation, DN incorporates the first-order effects of a unit's neighbors.

Mathematical Intuition

The core innovation lies in how the estimator attributes outcomes. Instead of only attributing a node's outcome to its own treatment status, the DN estimator uses a propensity score correction to weight the outcomes of both the node and its immediate neighbors. When the treatment probability is 50%, the estimator simplifies to a comparison between the sum of outcomes for a node and its neighbors under treatment versus control.

This approach reduces the bias from $O(\delta)$ to $O(\delta^2)$, where $\delta$ represents the strength of the interference. Crucially, while the HT estimator's variance scales at $2^d$ (where $d$ is the network degree), the DN estimator's variance scales polynomially at $d^4$. This makes the DN estimator viable for the dense networks typical of modern social media and e-commerce platforms.

Empirical Validation

The authors evaluated the DN estimator across three distinct environments:

  • Synthetic Graphs: Using Watts-Strogatz and Erdos-Renyi models, the authors demonstrated the estimator's performance under controlled levels of network density.
  • Twitter Social Network: Utilizing a real-world graph of 81,000 nodes and 1.7 million edges, the DN estimator achieved an RMSE of 0.06, a stark improvement over the 1.22 RMSE produced by the naive DM estimator.
  • Ride-sharing Simulation: In a spatio-temporal simulator based on Manhattan taxi data, the DN estimator reduced bias by over 50% and RMSE by approximately 35% compared to traditional methods.

Synergy with Clustered Design

A significant finding of the paper is that the DN estimator does not replace clustered experimental design but rather enhances it. Clustered designs attempt to minimize interference by grouping connected units together. However, interference often persists at cluster boundaries. Because DN is highly effective at "de-biasing" this boundary interference, researchers can utilize smaller clusters. Smaller clusters increase the number of independent samples, thereby reducing the overall variance of the experiment and pushing the "bias-variance frontier" further than previously possible.

Limitations and Future Directions

The effectiveness of the DN estimator relies on the "smoothness" of the outcome function (specifically, bounded second-order derivatives). In scenarios where interference is highly non-linear or discontinuous, the first-order Taylor approximation may be less effective. Additionally, in marketplace settings, the "interference network" is not always explicit and must be defined through hyperparameters (e.g., spatial or temporal proximity), which requires careful calibration.

Conclusion

The Differences-in-Neighbors estimator represents a significant advancement in the field of causal inference on networks. By providing a mathematically grounded method to capture first-order spillover effects with manageable variance, it offers a practical tool for data scientists and researchers working on large-scale interconnected platforms.

Summary updated

BibTeX
@inproceedings{peng2025differences,
  author = {Tianyi Peng and Naimeng Ye and Andrew Zheng},
  title = {{Differences-in-Neighbors for Network Interference in Experiments}},
  booktitle = {EC},
  year = {2025},
  doi = {10.1145/3736252.3742626},
}
Figure