Collaborative Causal Discovery with Atomic Interventions

Raghavendra Addanki, Shiva Prasad Kasiviswanathan

TL;DR

This paper introduces Collaborative Causal Discovery, a framework for learning causal graphs across multiple entities simultaneously. By assuming that the causal structures of different entities naturally cluster together, the authors develop algorithms that drastically reduce the number of expensive interventions needed per entity—scaling logarithmically rather than linearly with the number of entities.

What Problem Does This Paper Address?

Causal discovery—the process of determining "what causes what" in a system—is notoriously difficult. While observational data can reveal some relationships, many different causal structures can produce the exact same observations. To distinguish between them, researchers must use interventions (like randomized controlled trials), which are often expensive, time-consuming, or unethical.

Multiple independent entities with their own causal graphs

In many real-world scenarios, such as healthcare or manufacturing, we deal with multiple independent entities (e.g., different patients or different factories). These entities likely have similar, but not identical, causal structures. Learning each entity's graph individually is prohibitively expensive. This paper tackles the challenge of how to "collaborate" across these entities to learn all their individual causal graphs while minimizing the intervention burden on any single entity.

Methods

The authors model the problem using Maximal Ancestral Graphs (MAGs). MAGs are particularly powerful because they can accurately represent causal relations even when some variables are unobserved (latent confounders), avoiding the unrealistic "causal sufficiency" assumption.

Clustering of similar causal graphs

Their approach relies on a novel $(\alpha, \beta)$-clustering assumption: entities in the same cluster have "close" causal graphs, while those in different clusters are "far" apart.

Key algorithms introduced include:

  • Algorithm $(\alpha, \beta)$-BOUNDEDDEGREE: Uses a small set of randomized atomic (single-node) interventions to partition the $M$ entities into their respective clusters.
  • Algorithm $(\alpha, \beta)$-RECOVERY: Once clusters are identified, it aggregates interventional results across the cluster to learn a "dominant MAG" that serves as a high-quality approximation for every entity in that group.
  • Algorithm $\alpha$-GENERAL: A specialized, more efficient version for cases where all entities in a cluster share the exact same causal graph.

Key Insights and Ideas

  • Crowdsourcing Causality: The central "aha" moment is that you don't need to intervene on every node for every entity. By distributing different interventions across a cluster of similar entities, you can reconstruct the whole graph for everyone.
  • Clustering as a Discovery Tool: You don't need to know the clusters beforehand. The paper proves that the same interventions used to learn the graph can also be used to discover the underlying group structure.
  • Logarithmic Scaling: The number of interventions required per entity scales with $\log M$ (where $M$ is the number of entities). This means that as you add more entities to the study, the "cost" per entity actually decreases relative to the total information gained.
  • Optimality: The authors provide a theoretical lower bound, proving that their dependence on the "distance" between clusters ($1/\alpha$) is mathematically optimal.

Datasets and Key Results

The researchers evaluated their algorithms using several well-known Bayesian networks from the Bayesian Network Repository, modified to include latent variables (Asia, Earthquake, Sachs, Survey), as well as synthetic data generated using Erdös-Rényi random graphs.

  • Significant Intervention Reduction: In synthetic tests with 10 nodes, the collaborative approach required at most 6 interventions per entity. In the worst-case scenario for individual learning, 10 interventions would be required—a 40% reduction in experimental cost.
  • High Accuracy: On the Asia network, the algorithm achieved a clustering accuracy of 0.91, significantly outperforming standard baselines like the FCI algorithm, which relies only on observational data.
  • Robustness to Latents: The algorithms successfully recovered structures even in the presence of unobserved confounders, a common hurdle that often breaks simpler causal discovery methods.

Limitations and Future Work

  • Parameter Knowledge: The current algorithms require some prior knowledge or estimates of the clustering parameters ($\alpha$ and $\beta$), though the authors suggest binary search as a potential workaround.
  • Atomic Interventions Only: The study focuses on single-node interventions. Real-world experiments sometimes involve intervening on sets of variables simultaneously, which is not yet covered.
  • Adaptivity: The main algorithms are adaptive (the next intervention depends on previous results). Extending this to a non-adaptive setting—where all experiments are planned upfront—is an important next step for practical implementation in lab settings.

Summary updated

Abstract

We introduce a new Collaborative Causal Discovery problem, through which we model a common scenario in which we have multiple independent entities each with their own causal graph, and the goal is to simultaneously learn all these causal graphs. We study this problem without the causal sufficiency assumption, using Maximal Ancestral Graphs (MAG) to model the causal graphs, and assuming that we have the ability to actively perform independent single vertex (or atomic) interventions on the entities. If the $M$ underlying (unknown) causal graphs of the entities satisfy a natural notion of clustering, we give algorithms that leverage this property and recovers all the causal graphs using roughly logarithmic in $M$ number of atomic interventions per entity. These are significantly fewer than $n$ atomic interventions per entity required to learn each causal graph separately, where $n$ is the number of observable nodes in the causal graph. We complement our results with a lower bound and discuss various extensions of our collaborative setting.
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