Non-Robustness of Diffusion Estimates on Networks with Measurement Error

Arun G. Chandrasekhar, Paul Goldsmith-Pinkham, Tyler H. McCormick, Samuel Thau, Jerry C. Wei

TL;DR

Network diffusion models are widely used to understand how information, diseases, or technologies spread. This paper reveals that even tiny errors in measuring the network structure can lead to drastically wrong predictions about diffusion, especially when missing links act as "shortcuts" across different parts of the network. This fragility has significant implications for policy and forecasting, suggesting that understanding the geometry of measurement error is more critical than just its quantity.

What Problem Does This Paper Address?

Researchers and policymakers frequently use network diffusion models to predict how phenomena spread through social or physical networks. These models rely heavily on accurate network data. However, real-world network data is often incomplete or imperfect due to various data collection challenges (e.g., survey limitations, sampling biases). The central question this paper addresses is: How robust are network diffusion model predictions to measurement error in the network structure, and under what conditions does this error become catastrophic? The authors specifically investigate the impact of missing links (false negatives) and how their placement, not just their quantity, affects forecast accuracy.

Methods

The paper develops a theoretical framework to analyze network diffusion under measurement error. Key methodological components include:

  • Polynomial Expansion Networks: The core analysis focuses on networks exhibiting "polynomial volume growth," meaning the number of nodes within a certain graph distance grows polynomially with that distance. This class of networks is common and includes regular lattices and random geometric graphs.
  • SIR Diffusion Model: A standard Susceptible-Infected-Removed (SIR) model is used to simulate the diffusion process.
  • Formal Analysis of Measurement Error: The authors distinguish between "aligned" and "unaligned" measurement error.
  • Unaligned Error: Missing links act as "shortcuts," bridging distant parts of the network in graph distance. This is the primary focus and the source of catastrophic failure.
  • Aligned Error: Missing links resemble the structure of observed links, essentially a random thinning of the network. This type of error is shown to be less problematic.
  • Asymptotic Analysis: The results are derived using asymptotic theory as the network size ($n$) and forecast horizon ($T$) grow.
  • Tiling Construction: A novel "tiling" method is introduced to partition the network into disjoint regions, allowing for the analysis of how diffusion escapes local neighborhoods through missing links.
  • Coupling Techniques: Monotone couplings are used to compare diffusion on the true network ($G_n$) versus the observed network ($L_n$).

Datasets

The paper uses real-world data for empirical illustrations:

  • CA/NV Mobility Data: Cell-phone mobility flows between Census tracts in California and Nevada are used to construct networks representing travel patterns. This data is used to compare diffusion under different error structures (geographically correlated vs. i.i.d. missing links).
  • NYC Micro-Cluster Initiative Data: Geographic adjacency and mobility data for New York City's micro-cluster zoning policy are used to demonstrate how using the wrong network (geographic vs. mobility) can lead to policy misallocations.
  • Malawi Village Network Data: Data from Beaman et al. (2021) on village networks in Malawi is used to examine the sensitivity of optimal targeting strategies to measurement error, particularly in structured networks.

Key Insights and Ideas

  • Geometry of Error Matters Most: The paper's most striking insight is that the geometric placement of missing links is far more critical than their sheer number. "Unaligned" missing links that act as shortcuts can cause catastrophic forecast failures, even when they represent a vanishingly small fraction of the total links.
  • "Shortcuts" as Escape Hatches: Missing links that bridge distant regions in graph distance act as "escape hatches," allowing diffusion to spread much faster and wider than predicted by the observed network alone. This is a generalization of the "small-worlds" phenomenon.
  • Fragility of Structured Networks: Diffusion models are most vulnerable to measurement error in structured networks (e.g., lattices, networks with bottlenecks) where optimal diffusion paths are sensitive to specific connections. In contrast, well-mixed networks are more robust.
  • Seed Sensitivity Amplified: Measurement error, particularly unaligned error, can dramatically amplify the sensitivity of diffusion outcomes to the initial seed location. Small perturbations in the seed can lead to vastly different diffusion patterns.
  • Aggregate vs. Disaggregated Forecasts: While aggregate parameters like the basic reproductive number ($R_0$) might remain consistently estimable, they offer little protection against the severe errors in disaggregated forecasts (e.g., predicting which nodes will be reached).

Key Results

  • Theorem 2 (Asymptotic Forecast Failure): Even vanishingly small amounts of unaligned measurement error lead to catastrophic underestimation of diffusion spread on polynomial-expansion networks. The ratio of the observed forecast to the true diffusion approaches zero.
  • Theorem 3 (Robustness under Aligned Error): If missing links are "aligned" with the observed network structure (i.e., a random thinning), forecasts remain asymptotically correct, even with a non-trivial volume of missing links, provided the censoring rate is sufficiently low.
  • Theorem 1 (Seed Sensitivity): Diffusion on polynomial-expansion networks exhibits significant sensitivity to the initial seed location. Nearby seeds can lead to substantially disjoint diffusion outcomes.
  • Empirical Findings:
    • The CA/NV mobility data showed that i.i.d. missing links (acting as shortcuts) were far more damaging than geographically correlated missing links, leading to much larger forecast underestimation.
  • The NYC micro-cluster analysis demonstrated that a policy relying solely on geographic adjacency missed crucial mobility links, leading to misallocation of resources.
  • The Malawi village network analysis revealed that optimal targeting strategies are most fragile in structured, bottlenecked networks, precisely where measurement error is most damaging.

Limitations and Future Work

  • Intermediate Cases: The paper focuses on "aligned" and "unaligned" error as sufficient conditions for robustness and failure, respectively. Intermediate cases where error components are mixed or partially correlated are noted as an open question.
  • Directed Networks: The analysis primarily considers undirected networks. The authors conjecture that sensitive dependence might be even stronger in directed networks due to asymmetric paths.
  • General Diffusion Models: The results are specific to SIR models. The authors suggest that similar perturbation robustness failures might affect other models of treatment effects with spillovers.
  • Finite-Sample Calibration: While simulations illustrate the theoretical findings, the formal theorems rely on asymptotic properties. The authors note that finite-sample calibrations are illustrative.
  • Data Collection Practices: The paper highlights that common data collection practices often lead to unaligned error, suggesting that applied researchers should prioritize understanding the geometry of measurement error in their data.

Summary updated

Abstract

Network diffusion models are used to study things like disease transmission, information spread, and technology adoption.However, small amounts of mismeasurement are extremely likely in the networks constructed to operationalize these models.We show that estimates of diffusions are highly non-robust to this measurement error.First, we show that even when measurement error is vanishingly small, such that the share of missed links is close to zero, forecasts about the extent of diffusion will greatly underestimate the truth.Second, a small mismeasurement in the identity of the initial seed generates a large shift in the locations of expected diffusion path.We show that both of these results still hold when the vanishing measurement error is only local in nature.Such non-robustness in forecasting exists even under conditions where the basic reproductive number is consistently estimable.Possible solutions, such as estimating the measurement error or implementing widespread detection efforts, still face difficulties because the number of missed links are so small.Finally, we conduct Monte Carlo simulations on simulated networks, and real networks from three settings: travel data from the COVID-19 pandemic in the western US, a mobile phone marketing campaign in rural India, and in an insurance experiment in China.
BibTeX
@misc{chandrasekhar2024non,
  author = {Arun G. Chandrasekhar and Paul Goldsmith-Pinkham and Tyler H. McCormick and Samuel Thau and Jerry C. Wei},
  title = {{Non-Robustness of Diffusion Estimates on Networks with Measurement Error}},
  year = {2024},
  doi = {10.2139/ssrn.4762958},
  howpublished = {SSRN},
}
Figure