Submodular Optimization for Causal Structure and Control

This direction is merged into another direction: greedy approximation guarantees. Its last version stays readable and citable here.

Version 1 of 110 papers17 conceptsfrozen 2026-10-04

Causal inference is often a search for needles in a haystack of exponential size. Whether we are trying to learn the architecture of a gene regulatory network or deciding which variables to manipulate to lower a patient's blood pressure, we are faced with a combinatorial explosion. There are simply too many possible experiments to run and too many sets of variables to intervene upon.

However, a recurring insight across recent research is that many of these daunting causal problems share a specific mathematical property: submodularity. This property acts as a bridge, allowing researchers to trade intractable exhaustive searches for simple greedy algorithms that come with provable performance guarantees.

The Diminishing Returns of Discovery

In causal discovery, we use interventions to move beyond mere correlation. While observational data can narrow down the possible structures of a system to a "Markov Equivalence Class," interventions are required to orient the remaining edges and find the true directed acyclic graph (DAG).

The challenge is that we usually have a limited budget. We cannot perturb every variable. In ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discovery, Raj Agrawal, Chandler Squires, and their colleagues frame this as an optimization problem: which batch of experiments yields the most information?

They demonstrate that the utility function for these experiments—specifically the mutual information between outcomes and the causal structure—is submodular. Submodularity is the mathematical formalization of "diminishing returns." If you have already performed many experiments, adding one more provides less new information than if you had performed only a few.

Because of this property, a simple greedy strategy—picking the single best experiment at each step—is guaranteed to be near-optimal. Specifically, as noted in Interventional Experiment Design for Causal Structure Learning by AmirEmad Ghassami and Negar Kiyavash, these greedy approaches are guaranteed to achieve at least 63% ($1 - 1/e$) of the information gain of the theoretically perfect (but computationally impossible) set of interventions.

Beyond Single Interventions

Real-world systems often require more than one change at a time. In Near-Optimal Multi-Perturbation Experimental Design for Causal Structure Learning, Scott Sussex and Andreas Krause extend this logic to multi-perturbation designs. They prove that even when we perturb multiple variables simultaneously, the objectives for edge orientation still follow submodular patterns. This allowed them to develop algorithms like DGC and SSG, which efficiently navigate the massive space of multi-variable experiments with the same near-optimal guarantees.

Causal Control as Optimization

The utility of submodularity isn't limited to learning the graph; it also applies to using the graph. In Optimal Causal Imputation for Control, Roy Dong and Eric Mazumdar look at the "dual" problem. If we already know the causal structure, how do we intervene to reach a target state at the lowest cost?

They found that when unique causal paths exist between nodes, the cost function for selecting intervention points is submodular. This means that choosing where to intervene to control a system is not just a matter of intuition, but a problem that can be solved efficiently using convex relaxations or greedy selection.

Similarly, Jiaqi Zhang and Caroline Uhler in Matching a Desired Causal State via Shift Interventions use submodular surrogates to reach target mean states in complex networks. By maximizing the expected gain in causal information per experiment, they show that systems can be steered toward desired outcomes exponentially faster than through brute-force methods.

The Geometric Foundation

Why does submodularity keep appearing in causality? The answer may lie in the underlying geometry of probabilistic models. In Generalized Permutohedra from Probabilistic Graphical Models, Fatemeh Mohammadi and Josephine Yu show that the conditional independence relations of any DAG are inherently submodular. They map these relations to high-dimensional geometric shapes called polytopes (specifically, generalized permutohedra).

This suggests that submodularity isn't just a convenient trick for these specific papers; it is a fundamental structural property of how information is organized in causal graphs. By recognizing this property, researchers have turned the "holy grail" of causal discovery and control from a search for an needle in a haystack into a manageable, step-by-step optimization.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_submodular_optimization_for_causal_struc_9f71036a,
  title = {Submodular Optimization for Causal Structure and Control},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/submodular-optimization-for-causal-structure-and-control/rdr_9f71036aea5c40f7aaf04e79a22c9527},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_submodular_optimization_for_causal_struc_9f71036a_v1,
  title = {Submodular Optimization for Causal Structure and Control},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/submodular-optimization-for-causal-structure-and-control/rdr_9f71036aea5c40f7aaf04e79a22c9527/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}