Learning Causal Graphs through Score Optimization

34 concepts34 papers1 proposal

To understand the world, we must move beyond simple correlations and uncover the underlying web of cause and effect. In data science, this task is known as causal discovery: reconstructing the directed graph that dictates how variables influence one another.

Historically, researchers approached this problem using constraint-based methods. These algorithms perform a sequence of statistical conditional independence tests to systematically rule out connections. However, constraint-based approaches suffer from a fatal flaw: if a single statistical test returns a false positive or negative due to noisy data, that error cascades, potentially ruining the entire graph.

As reviewed by Clark Glymour et al. and Neville K. Kitson et al., an increasingly dominant alternative is score-based structure learning. Instead of relying on a fragile chain of individual tests, score-based methods transform causal discovery into a global optimization problem. The core intuition is simple: we define a mathematical scoring function that measures how well a candidate graph explains the observed data, and then we search the space of possible graphs to find the one that maximizes this score.

As Sofia Triantafillou argues, this optimization framework provides a global robustness that constraint-based methods lack. Empirically, Vineet K. Raghu et al. demonstrate that score-based discovery typically yields a significantly higher recall of true causal edges, making it a powerful paradigm for open-source toolkits like the one introduced by Yujia Zheng et al..

The Anatomy of a Scoring Function

A scoring function cannot simply reward the graph that fits the data best. If it did, the optimal graph would always be a fully connected mesh where every variable points to every other variable. Such a model perfectly fits any data distribution, but it explains nothing.

To prevent this overfitting, scoring functions must balance two competing forces: goodness-of-fit and structural complexity. As highlighted by Charles K. Assaad et al., score-based methods incorporate regularization terms that penalize overly dense graphs, enforcing the principle of parsimony (Occam's razor).

Several mathematical formulations achieve this balance:

  • Bayesian Information Criterion (BIC): Perhaps the most widely used metric, BIC penalizes the log-likelihood of the data based on the number of parameters (edges) in the graph. It is used across diverse applications, from ensuring algorithmic fairness (Ruta Binkyte et al.) to mapping the complex mechanisms of chronic back pain (J. Russell Huie et al.).
  • Bayesian Dirichlet equivalent uniform (BDeu): Popularized in biological contexts like reconstructing gene regulatory networks (Linlin Xing et al.), BDeu computes the marginal likelihood of the graph by integrating over a Dirichlet prior distribution of the network's parameters.
  • Minimal Description Length (MDL): Grounded in information theory, MDL views structure learning as a data compression problem. As explored by Wai Lam et al., the optimal network topology is the one that minimizes the combined length of the description of the graph itself and the description of the data compressed by that graph.

If we have a reliable scoring function, why not simply score every possible graph and pick the winner? The obstacle is computational. The number of possible directed acyclic graphs (DAGs) grows super-exponentially with the number of variables; a network with just ten nodes has over $4 \times 10^{18}$ potential structures.

The secret weapon that makes score-based learning viable is score decomposability. For standard scoring functions like BIC and MDL, the total score of a graph is simply the sum of local scores calculated at each individual node. A node's local score depends strictly on its immediate parents.

$$\text{Score}(G) = \sum_{i=1}^{n} \text{LocalScore}(X_i \mid \text{Parents}(X_i))$$

Because of decomposability, if an algorithm modifies a single edge in a massive graph, it does not need to re-score the entire network. It only needs to recompute the local score for the node affected by that modification. This property enables several efficient search strategies:

Greedy Hill Climbing

Algorithms often start with an empty graph and iteratively apply local modifications—adding, removing, or reversing a single edge—choosing whichever change yields the steepest ascent in the overall score. This heuristic approach is highly effective for discovering semantic dependencies in text (Alexey Gorbatovski et al.), isolating causal genetic variants (Yanran Ma et al.), or performing model-based clustering (Leonard K. M. Poon et al.).

In sequential domains, such as tracking interactions between agents or events over time, researchers like Debarun Bhattacharjya et al. and Xiufan Yu et al. utilize forward-backward search. The algorithm greedily adds historical dependencies that improve predictive power, and then performs a backward pass to prune away redundant or obsolete edges.

Exact Mathematical Programming

When heuristic approximations are insufficient, the search can be framed as an exact optimization problem. For instance, Petr Ryšavý et al. formulate structure search as a compact Mixed-Integer Quadratic Program (MIQP). By using branch-and-cut algorithms, they guarantee finding the mathematically optimal graph for small-to-medium datasets.

Adapting to Complex Data Realities

The real world rarely presents clean, fully observed, continuous data. The true power of the score-based optimization framework lies in its flexibility to adapt to these messy data realities by altering either the scoring function or the underlying graph representation.

Incomplete and Latent Data

When data contains missing values, calculating the exact marginal likelihood becomes computationally intractable. To bypass this, Marco Ramoni et al. introduced deterministic bounds to estimate the score efficiently during a greedy search. In continuous-time settings, Lukas Studer et al. mathematically marginalize out unobserved transition rates to maintain search efficiency.

Furthermore, standard DAGs assume "causal sufficiency"—that no unobserved common causes exist. To relax this assumption, both Sofia Triantafillou and Petr Ryšavý et al. optimize over Maximal Ancestral Graphs (MAGs), which explicitly score and represent latent confounders.

Ordinal and Mixed Data

Categorical data with a natural ordering (e.g., "low, medium, high") poses a unique challenge: standard models can identify that two variables are related, but struggle to orient the direction of the cause. Yang Ni et al. and Giusi Moffa et al. solve this by mapping ordinal data into a latent continuous space. By optimizing scores within this continuous embedding, the algorithms exploit the data's inherent asymmetry to uniquely identify the correct causal direction.

Time Series and Diffusions

When analyzing dynamic systems, time provides a natural constraint. Elad Eban et al. combine score-based search with copulas to capture complex, non-Gaussian temporal dependencies in real-valued time series. Remarkably, the optimization paradigm is so robust that the authors of Learning Diffusions without Timestamps demonstrate that network topologies can be recovered greedily even when exact event timestamps are missing entirely, relying instead on the final infection states of the nodes.

Whether applied to microservice root-cause analysis (Sarthak Chakraborty et al.) or predicting protein topologies (Gianluca Pollastri et al.), score-based causal discovery works because it reduces a daunting philosophical question—what causes what?—into a tractable, mathematical problem of balancing fit and complexity across a structured search space.

Key Foundational Work

Learning Bayesian Networks from Incomplete Databases (1997) — contributed 1 concept elements to this direction.
A Bayesian Approach to Learning Bayesian Networks with Local Structure (1997) — contributed 1 concept elements to this direction.
On the Use of Skeletons when Learning in Bayesian Networks (2000) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_score_based_causal_discovery_840ea8de,
  title = {score-based causal discovery},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/score-based-causal-discovery/rdr_840ea8de4c614d7d89b4512195d49973},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_score_based_causal_discovery_840ea8de_v1,
  title = {score-based causal discovery},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/score-based-causal-discovery/rdr_840ea8de4c614d7d89b4512195d49973/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake