Collaborative Causal Discovery with Atomic Interventions

Raghavendra Addanki, Shiva Prasad Kasiviswanathan

Introduction

Causal discovery—identifying the directed relationships between variables—is a cornerstone of scientific inquiry. While observational data can reveal correlations, establishing causation typically requires interventions, such as randomized controlled trials. However, in a system with $n$ variables, traditional methods often necessitate intervening on every single variable to resolve ambiguities, especially in the presence of unobserved "latent" variables. This "intervention tax" is frequently prohibitive in terms of cost, time, and ethics.

This paper proposes a collaborative framework for causal discovery. Instead of treating entities (e.g., different patients, hospitals, or manufacturing plants) in isolation, the authors leverage the shared underlying structures across a population of $M$ entities. By recognizing that these entities often fall into a small number of clusters with similar causal graphs, the required number of interventions per entity can be drastically reduced.

Causal structures across multiple entities with latent variables.

Methodology: The $(\alpha, \beta)$-Clustering Assumption

The core innovation lies in modeling causal structures using Maximal Ancestral Graphs (MAGs). MAGs are particularly effective because they represent causal relationships among observed variables while implicitly accounting for latent confounders.

The collaborative approach relies on the $(\alpha, \beta)$-clustering assumption:

  1. Separation ($\alpha$): Entities belonging to different clusters possess causal graphs that differ significantly (by at least $\alpha n$ edges).
  2. Similarity ($\beta$): Entities within the same cluster have graphs that are highly similar (differing by at most $\beta n$ edges).
Illustration of the clustering assumption where entities are grouped by graph similarity.

Algorithmic Framework

The authors introduce a suite of algorithms to exploit this structure:

  • $(\alpha, \beta)$-BOUNDEDDEGREE: This algorithm identifies the underlying clusters by performing a small number of random interventions across entities and grouping those that exhibit similar responses.
  • $(\alpha, \beta)$-RECOVERY: Once clusters are established, entities within a cluster "divide and conquer" the intervention space. Instead of one entity testing all $n$ variables, the workload is distributed, and results are pooled to reconstruct the dominant MAG for the cluster.
  • $\alpha$-GENERAL: A specialized version for scenarios where intra-cluster variance is zero ($\beta = 0$), further optimizing efficiency.

Key Results and Insights

The most significant finding is that the number of interventions required per entity scales logarithmically with the number of entities ($\log M$) rather than linearly with the number of variables ($n$). This implies that as more participants join a collaboration, the individual burden of discovery decreases.

Empirical evaluations on standard benchmarks (e.g., Asia, Sachs, Earthquake) and synthetic Erdős-Rényi graphs demonstrated substantial gains:

  • Efficiency: In a 10-variable synthetic setup, the collaborative approach achieved near-perfect graph recovery with only 6 interventions per entity, a 40% reduction compared to the 10 required by individual-based methods.
  • Accuracy: The collaborative method significantly outperformed the standard FCI algorithm. For the "Asia" dataset, precision improved from approximately 0.57 to 0.92.
  • Robustness: The algorithms maintained high recall (above 0.90) across various network structures, proving resilient to the presence of latent variables.

Conclusion

Collaborative causal discovery transforms the challenge of high intervention costs into an opportunity for collective learning. By formalizing the similarity between entities through $(\alpha, \beta)$-clustering, this work provides a scalable path for mapping complex causal systems. Future work may extend these principles to multi-variable interventions and non-adaptive experimental designs, further broadening the practical applicability of the framework.

Summary updated

BibTeX
@inproceedings{addanki2021collaborative,
  author = {Raghavendra Addanki and Shiva Prasad Kasiviswanathan},
  title = {{Collaborative Causal Discovery with Atomic Interventions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=9JkWNsk7rs},
}
Figure