Causal message-passing for experiments with unknown and general network interference
Edited by David Donoho, Stanford University, Stanford, CA; received December 26, 2023; accepted August 8, 2024
Significance
Randomized experiments are the gold standard for assessing the impact of various decisions, including policy changes, medical treatments, or product enhancements. However, these experiments often face the challenge of network interference, where a decision affecting one individual impacts others, complicating the analysis. Our research introduces Causal Message-Passing, a framework inspired by techniques from physics and statistics to tackle this complexity. It allows for a more nuanced understanding of interconnected data, crucial for predicting outcomes in environments where individual responses are interdependent. This approach enhances the accuracy of decision-making in networked settings, offering insights for scientists and practitioners across diverse fields.
Abstract
Randomized experiments are a powerful methodology for data-driven evaluation of decisions or interventions. Yet, their validity may be undermined by network interference. This occurs when the treatment of one unit impacts not only its outcome but also that of connected units, biasing traditional treatment effect estimations. Our study introduces a framework to accommodate complex and unknown network interference, moving beyond specialized models in the existing literature. Our framework, termed causal message-passing, is grounded in high-dimensional approximate message-passing methodology. It is tailored for multiperiod experiments and is particularly effective in settings with many units and prevalent network interference. The framework models causal effects as a dynamic process where a treated unit’s impact propagates through the network via neighboring units until equilibrium is reached. This approach allows us to approximate the dynamics of potential outcomes over time, enabling the extraction of valuable information before treatment effects reach equilibrium. Utilizing causal message-passing, we introduce a practical algorithm to estimate the total treatment effect, defined as the impact observed when all units are treated compared to the scenario where no unit receives treatment. We demonstrate the effectiveness of this approach across five numerical scenarios, each characterized by a distinct interference structure.
Data, Materials, and Software Availability
There are no data underlying this work.
Acknowledgments
Author contributions
S.S. and M.B. designed research; S.S. and M.B. performed research; S.S. analyzed data; and S.S. and M.B. wrote the paper.
Competing interests
The authors declare no competing interest.
Supporting Information
Appendix 01 (PDF)
- Download
- 731.99 KB
References
1
D. R. Cox, Planning of Experiments (Wiley, 1958).
2
D. B. Rubin, Bayesian inference for causal effects: The role of randomization. Ann. Stat. 6, 34–58 (1978).
3
C. F. Manski, Identification of treatment response with social interactions. Econ. J. 16, S1–S23 (2013).
4
L. Forastiere, F. Mealli, A. Wu, E. M. Airoldi, Estimating causal effects under network interference with Bayesian generalized propensity scores. J. Mach. Learn. Res. 23, 1–61 (2022).
5
C. L. Yu, E. M. Airoldi, C. Borgs, J. T. Chayes, Estimating the total treatment effect in randomized experiments with unknown network structure. Proc. Natl. Acad. Sci. U.S.A. 119, e2208975119 (2022).
6
G. W. Basse, E. M. Airoldi, Limitations of design-based causal inference and a/b testing under arbitrary and network interference. Sociol. Methodol. 48, 136–151 (2018).
7
V. Karwa, E. M. Airoldi, A systematic investigation of classical causal inference strategies under mis-specification due to network interference. arXiv [Preprint] (2018). https://arxiv.org/abs/1810.08259 (Accessed 31 August 2022).
8
P. M. Aronow, C. Samii, Estimating average causal effects under general interference, with application to a social network experiment. Ann. Appl. Stat. 11, 1912–1947 (2017).
9
D. L. Sussman, E. M. Airoldi, Elements of estimation theory for causal effects in the presence of network interference. arXiv [Preprint] (2017). https://arxiv.org/abs/1702.03578 (Accessed 31 August 2022).
10
M. Mezard, G. Parisi, M. Virasoro, Spin Glass Theory and Beyond, An Introduction to the Replica Method and Its Applications (World Scientific, Paris, France, 1986), p. 476.
11
M. Mezard, A. Montanari, Information, Physics, and Computation (Oxford University Press, 2009).
12
D. L. Donoho, A. Maleki, A. Montanari, Message-passing algorithms for compressed sensing. Proc. Natl. Acad. Sci. U.S.A. 106, 18914–18919 (2009).
13
M. Bayati, A. Montanari, The dynamics of message passing on dense graphs, with applications to compressed sensing. IEEE Trans. Inf. Theory 57, 764–785 (2011).
14
G. W. Imbens, D. B. Rubin, Causal Inference in Statistics, Social, and Biomedical Sciences (Cambridge University Press, 2015).
15
S. Athey, D. Eckles, G. W. Imbens, Exact p-values for network interference. J. Am. Stat. Assoc. 113, 230–240 (2018).
16
R. Xiong, S. Athey, M. Bayati, G. Imbens, Optimal experimental design for staggered rollouts. arXiv [Preprint] (2019). https://arxiv.org/abs/1911.03764 (Accessed 10 January 2022).
17
K. Imai, Z. Jiang, Identification and sensitivity analysis of contagion effects in randomized placebo-controlled trials. J.R. Stat. Soc. Ser. A Stat. Soc. 183, 1637–1657 (2020).
18
C. F. Manski, Nonparametric bounds on treatment effects. Am. Econ. Rev. 80, 319–323 (1990).
19
P. M. Aronow, A general method for detecting interference between units in randomized experiments. Sociol. Methods Res. 41, 3–16 (2012).
20
J. Bowers, M. M. Fredrickson, C. Panagopoulos, Reasoning about interference between units: A general framework. Polit. Anal. 21, 97–124 (2013).
21
M. Saveski et al., “Detecting network effects: Randomizing over randomized experiments” in Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2017), pp. 1027–1035.
22
J. Pouget-Abadie et al., Testing for arbitrary interference on experimentation platforms. Biometrika 106, 929–940 (2019).
23
Y. Hu, S. Li, S. Wager, Average direct and indirect causal effects under interference. Biometrika 109, 1165–1172 (2022).
24
K. Han, S. Li, J. Mao, H. Wu, Detecting interference in a/b testing with increasing allocation. arXiv [Preprint] (2022). https://arxiv.org/abs/2211.03262 (Accessed 24 March 2023).
25
M. P. Leung, Treatment and spillover effects under network interference. Rev. Econ. Stat. 102, 368–380 (2020).
26
D. Viviano, Experimental design under network interference. arXiv [Preprint] (2020). https://arxiv.org/abs/2003.08421 (Accessed 24 August 2023).
27
M. P. Leung, Causal inference under approximate neighborhood interference. Econometrica 90, 267–293 (2022).
28
M. Cortez, M. Eichhorn, C. L. Yu, Exploiting neighborhood interference with low order interactions under unit randomized design. arXiv [Preprint] (2022). https://arxiv.org/abs/2208.05553 (Accessed 18 January 2023).
29
M. Cortez, M. Eichhorn, C. Yu, “Staggered rollout designs enable causal inference under interference without network knowledge” in Advances in Neural Information Processing Systems (2022).
30
A. Agarwal, S. Cen, D. Shah, C. L. Yu, Network synthetic interventions: A framework for panel data with network interference. arXiv [Preprint] (2022). https://arxiv.org/abs/2210.11355 (Accessed 20 October 2022).
31
A. Belloni, F. Fang, A. Volfovsky, Neighborhood adaptive estimators for causal inference under network interference. arXiv [Preprint] (2022). https://arxiv.org/abs/2212.03683 (Accessed 7 December 2022).
32
S. Li, S. Wager, Network interference in micro-randomized trials. arXiv [Preprint] (2022). http://arxiv.org/abs/2202.05356 (Accessed 31 July 2022).
33
S. Li, S. Wager, Random graph asymptotics for treatment effect estimation under network interference. Ann. Stat. 50, 2334–2358 (2022).
34
P. R. Rosenbaum, Interference between units in randomized experiments. J. Am. Stat. Assoc. 102, 191–200 (2007).
35
O. Candogan, C. Chen, R. Niazadeh, Correlated cluster-based randomized experiments: Robust variance minimization (Chicago Booth Research Paper No. 21-17, 2021).
36
E. Auerbach, M. Tabord-Meehan, The local approach to causal inference under network interference. arXiv [Preprint] (2021). https://arxiv.org/abs/2105.03810 (Accessed 31 July 2023).
37
D. Eckles, B. Karrer, J. Ugander, Design and analysis of experiments in networks: Reducing bias from interference. J. Causal Inf. 5, 20150021 (2016).
38
J. Ugander, B. Karrer, L. Backstrom, J. Kleinberg, “Graph cluster randomization: Network exposure to multiple universes” in Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2013), pp. 329–337.
39
J. Ugander, H. Yin, Randomized graph cluster randomization. J. Causal Inf. 11, 20220014 (2023).
40
A. Chin, Central limit theorems via Stein’s method for randomized experiments under interference. arXiv [Preprint] (2018). https://arxiv.org/abs/1804.03105 (Accessed 4 April 2023).
41
R. Jagadeesan, N. S. Pillai, A. Volfovsky, Designs for estimating the treatment effect in networks with interference. Ann. Stat. 48, 679–712 (2020).
42
Y. Wang, C. Samii, H. Chang, P. Aronow, Design-based inference for spatial experiments with interference. arXiv [Preprint] (2020). https://arxiv.org/abs/2010.13599 (Accessed 4 April 2023).
43
J. Cai, A. D. Janvry, E. Sadoulet, Social networks and the decision to insure. Am. Econ. J.: Appl. Econ. 7, 81–108 (2015).
44
D. Holtz, R. Lobel, I. Liskovich, S. Aral, Reducing interference bias in online marketplace pricing experiments. arXiv [Preprint] (2020). https://arxiv.org/abs/2004.12489 (Accessed 11 February 2023).
45
S. Wager, K. Xu, Experimenting in equilibrium. Manage. Sci. 67, 6694–6715 (2021).
46
E. Munro, S. Wager, K. Xu, Treatment effects in market equilibrium. arXiv [Preprint] (2021). https://arxiv.org/abs/2109.11647 (Accessed 11 January 2023).
47
R. Johari, H. Li, I. Liskovich, G. Y. Weintraub, Experimental design in two-sided platforms: An analysis of bias. Manage. Sci. 68, 7069–7089 (2022).
48
V. Farias, A. Li, T. Peng, A. Zheng, Markovian interference in experiments. Adv. Neural Inf. Process. Syst. 35, 535–549 (2022).
49
V. F. Farias et al., Correcting for interference in experiments: A case study at Douyin. arXiv [Preprint] (2023). https://arxiv.org/abs/2305.02542 (Accessed 4 May 2023).
50
M. G. Hudgens, M. E. Halloran, Toward causal inference with interference. J. Am. Stat. Assoc. 103, 832–842 (2012).
51
G. W. Basse, A. Feller, P. Toulis, Randomization tests of causal effects under interference. Biometrika 106, 487–494 (2019).
52
M. O. Jackson, Z. Lin, N. N. Yu, Adjusting for peer-influence in propensity scoring when estimating treatment effects. Available at SSRN 3522256 (2020).
53
F. Sävje, P. Aronow, M. Hudgens, Average treatment effects in the presence of unknown interference. Ann. Stat. 49, 673 (2021).
54
T. Ni, I. Bojinov, J. Zhao, Design of panel experiments with spatial and temporal interference. Available at SSRN 4466598 (2023).
55
A. Boyarsky, H. Namkoong, J. Pouget-Abadie, Modeling interference using experiment roll-out. arXiv [Preprint] (2023). https://arxiv.org/abs/2305.10728 (Accessed 18 May 2023).
56
C. Harshaw, F. Sävje, Y. Wang, A design-based Riesz representation framework for randomized experiments. arXiv [Preprint] (2022). https://arxiv.org/abs/2210.08698 (Accessed 24 October 2022).
57
W. Li, D. L. Sussman, E. D. Kolaczyk, Causal inference under network interference with noise. arXiv [Preprint] (2021). https://arxiv.org/abs/2105.04518 (Accessed 31 August 2022).
58
P. Goldsmith-Pinkham, G. W. Imbens, Social networks and the identification of peer effects. J. Business Econ. Stat. 31, 253–264 (2013).
59
P. Toulis, E. Kao, “Estimation of causal peer influence effects” in International Conference on Machine Learning (PMLR, 2013), pp. 1489–1497.
60
L. E. Blume, W. A. Brock, S. N. Durlauf, R. Jayaraman, Linear social interactions models. J. Polit. Econ. 123, 444–496 (2015).
61
G. W. Basse, E. M. Airoldi, Model-assisted design of experiments in the presence of network-correlated outcomes. Biometrika 105, 849–858 (2018).
62
A. Chin, Regression adjustments for estimating the global treatment effect in experiments with interference. J. Causal Inference 7, 20180026 (2019).
63
Y. Jiang, H. Wang, Causal inference under network interference using a mixture of randomized experiments. arXiv [Preprint] (2023). https://arxiv.org/abs/2309.00141 (Accessed 31 August 2023).
64
J. D. Angrist, The perils of peer effects. Labour Econ. 30, 98–108 (2014).
65
D. J. Thouless, P. W. Anderson, R. G. Palmer, Solution of “solvable model of a spin glass’’. Philos. Mag. 35, 593–601 (1977).
66
Y. Kabashima, A CDMA multiuser detection algorithm on the basis of belief propagation. J. Phys. A 36, 11111–11121 (2003).
67
E. Bolthausen, An iterative construction of solutions of the tap equations for the Sherrington–Kirkpatrick model. Commun. Math. Phys. 325, 333–366 (2014).
68
A. Javanmard, A. Montanari, State evolution for general approximate message passing algorithms, with applications to spatial coupling. Inf. Inference 2, 115–144 (2013).
69
M. Bayati, M. Lelarge, A. Montanari, Universality in polytope phase transitions and message passing algorithms. Ann. Appl. Probab. 25, 753–822 (2015).
70
R. Berthier, A. Montanari, P. M. Nguyen, State evolution for approximate message passing with non-separable functions. Inf. Inference 9, 33–79 (2020).
71
W. K. Chen, W. K. Lam, Universality of approximate message passing algorithms. arXiv [Preprint] (2020). https://arxiv.org/abs/2003.10431 (Accessed 17 March 2023).
72
X. Zhong, T. Wang, Z. Fan, Approximate message passing for orthogonally invariant ensembles: Multivariate non-linearities and spectral initialization. arXiv [Preprint] (2021). https://doi.org/10.48550/arXiv.2110.02318 (Accessed 17 March 2023).
73
T. Wang, X. Zhong, Z. Fan, Universality of approximate message passing algorithms and tensor networks. arXiv [Preprint] (2022). https://arxiv.org/abs/2206.13037 (Accessed 17 March 2023).
74
R. Dudeja, Y. M. Lu, S. Sen, Universality of approximate message passing with semirandom matrices. Ann. Probab. 51, 1616–1683 (2023).
75
C. Rush, R. Venkataramanan, Finite sample analysis of approximate message passing algorithms. IEEE Trans. Inf. Theory 64, 7264–7286 (2018).
76
G. Li, Y. Wei, A non-asymptotic framework for approximate message passing in spiked models. arXiv [Preprint] (2022). https://arxiv.org/abs/2208.03313 (Accessed 17 March 2023).
77
L. Zdeborová, F. Krzakala, Statistical physics of inference: Thresholds and algorithms. Adv. Phys. 65, 453–552 (2016).
78
A. Montanari, “Mean field asymptotics in high-dimensional statistics: From exact results to efficient algorithms” in Proceedings of the International Congress of Mathematicians (ICM 2018), B. Sirakov, P. N. de Souza, M. Viana, Eds. (World Scientific, 2018), pp. 2973–2994.
79
O. Y. Feng et al., A unifying tutorial on approximate message passing. Found. Trends Mach. Learn. 15, 335–536 (2022).
80
H. A. Bethe, W. L. Bragg, Statistical theory of superlattices. Proc. R. Soc. London Ser. A, Math. Phys. Sci. 150, 552–575 (1935).
81
R. Gallager, Low-density parity-check codes. IRE Trans. Inf. Theory 8, 21–28 (1962).
82
J. Pearl, “Reverend Bayes on inference engines: A distributed hierarchical approach” in Proceedings of the Second National Conference on Artificial Intelligence (AAAI Press, Menlo Park, CA/Pittsburgh, PA, 1982), pp. 133–136 (Retrieved 28 March 2009).
83
P. Bajari et al., Multiple randomization designs. arXiv [Preprint] (2021). https://arxiv.org/abs/2112.13495 (Accessed 11 February 2023).
84
K. Han, J. Ugander, Model-based regression adjustment with model-free covariates for network interference. arXiv [Preprint] (2023). https://arxiv.org/abs/2302.04997 (Accessed 10 February 2023).
85
R. Kohavi, D. Tang, Y. Xu, Trustworthy Online Controlled Experiments: A Practical Guide to a/b Testing (Cambridge University Press, 2020).
86
S. Gupta et al., Top challenges from the first practical online controlled experiments summit. SIGKDD Explor. Newsl. 21, 20–35 (2019).
87
S. Puffer, D. J. Torgerson, J. Watson, Cluster randomized controlled trials. J. Eval. Clin. Pract. 11, 479–483 (2005).
88
J. Leskovec, J. Mcauley, Learning to discover social circles in ego networks. Adv. Neural Inf. Process. Syst. 25, 539–547 (2012).
89
P. Liao, P. Klasnja, A. Tewari, S. A. Murphy, Sample size calculations for micro-randomized trials in mHealth. Stat. Med. 35, 1944–1971 (2016).
90
P. Klasnja et al., Microrandomized trials: An experimental design for developing just-in-time adaptive interventions. Health Psychol. 34, 1220 (2015).
91
P. Klasnja et al., Efficacy of contextually tailored suggestions for physical activity: A micro-randomized optimization trial of heartsteps. Ann. Behav. Med. 53, 573–582 (2019).
92
V. Gupta, M. H. Balter, K. Sigman, W. Whitt, Analysis of join-the-shortest-queue routing for web server farms. Perform. Eval. 64, 1062–1081 (2007).
93
X. Kuang, G. Mendelson, Detecting service slowdown using observational data. arXiv [Preprint] (2024). https://arxiv.org/abs/2401.07305 (Accessed 15 January 2024).
Information & Authors
Information
Published in
Cover image: Pictured is green foxtail (Setaria viridis), an annual grass. Magda Garbowski et al. combined data from more than 75,000 vegetation plots across the United States with functional trait data for more than 5,500 plant species to uncover how naturalized species affect plant community traits. Compared with communities dominated by native species, communities dominated by naturalized species were shorter, more shallowly rooted, and exhibited traits supporting rapid resource acquisition and low reliance on mycorrhizal symbionts. According to the authors, community-level trait shifts likely underpin the functional changes observed in invaded ecosystems. See the article by Garbowski et al. e2403120121. Image credit: Magda Garbowski.
Classifications
Copyright
Copyright © 2024 the Author(s). Published by PNAS. This open access article is distributed under Creative Commons Attribution License 4.0 (CC BY).
Data, Materials, and Software Availability
There are no data underlying this work.
Submission history
Received: December 26, 2023
Accepted: August 8, 2024
Published online: September 27, 2024
Published in issue: October 1, 2024
Keywords
Acknowledgments
Author Contributions
S.S. and M.B. designed research; S.S. and M.B. performed research; S.S. analyzed data; and S.S. and M.B. wrote the paper.
Competing Interests
The authors declare no competing interest.
Notes
*
Rigorous statements are provided in section 3.
†
The result still holds true if the function is almost everywhere continuous in the first argument and continuous in the other arguments.
This article is a PNAS Direct Submission.
Authors
Metrics & Citations
Metrics
Citation statements
Altmetrics
Citations
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.
View Options
View options
PDF format
Download this article as a PDF file
DOWNLOAD PDFGet Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Personal login Institutional LoginRecommend to a librarian
Recommend PNAS to a LibrarianPurchase options
Purchase this article to access the full text.