Algorithms for Causal Inference on Networks

PI: Johan Ugander
Assistant Professor, Management Science & Engineering
School of Engineering
Stanford University
NSF Award #1657104
Activity period: 04/01/2017 - 3/31/2020

Award abstract

Randomized experiments (sometimes called "A/B tests") play increasingly fundamental roles in the design and refinement of modern online systems that drive the internet economy. Common design decisions include: What headline should be used with a news article; What prices should an item be offered at; or How should search results be ranked? However, modern web platforms exist atop strong networks of information flow and social interactions that mar the statistical validity of traditional experimental designs and analyses. This project aims to design graph clustering algorithms that can be used to administer experimental treatments in network-aware randomization designs and yield practically useful results. The project will train new graduate and undergraduate students in cutting-edge data science as they develop and deploy new research algorithms and software for causal inference at the intersection of modern computational and statistical research. The project will ultimately deliver new technical tools that increase the certainty of experiments that feature network interference, helping designers of online systems, both in industry and in government, make better decisions and craft better policies for an increasingly networked world.

This project aims to develop algorithmic tools for causal inference under network interference that go beyond mere proof-of-concepts, placing a specific focus on developments that will make network experimentation tools practical and provide significant and relevant results. The project will develop tools that harness graph metadata for variance reduction, and also develop techniques for running experiments in marketplaces, bipartite graphs rife with interference. In considering graph metadata, the goal is to develop stratified graph sampling methods that balance graph structure directly against latent traits. The deliverable assets of this project, which include algorithmic research as well as software for designing experiments, are intended to benefit computer scientists and statisticians, as well the broader community of researchers in the social and economic sciences that study networks.

Related literature and prior work

As a resource to those interested in the subject of this award, here is an overview of prior work and literature that this grant builds upon.



Large-scale graph partitioning

Seeding experiments:

Publications produced


Modeling the joint structure of attributes on networks:

Graph partitioning:

Seeding experiments:

Market experiments:

Software and code produced

All published papers supported by this grant include extensive notebooks documentating all data analysis, where applicable, that are shared as repositories on Github per the data management plan of this award.