Algorithmics for Graphical Separation Criteria

Moisés Chavira-Flores, Sebastian Weichwald, Leonard HenckelarXiv 2026 · arXiv

TL;DR

This paper introduces a unifying algorithmic framework for checking various graphical separation criteria—the rules that define independence in causal models. By reducing complex criteria like d-separation, trek-separation, and $\sigma$-separation to simple reachability problems in a state graph, the authors achieve optimal linear-time performance and provide ready-to-use R and Python implementations.

What Problem Does This Paper Address?

In the world of statistical graphical models, "separation criteria" are the mathematical bridge between a graph's structure and the statistical dependencies it represents. For example, in a Directed Acyclic Graph (DAG), we use d-separation to determine if two variables are independent given a third.

As researchers have developed more complex models—such as those involving feedback loops (cyclic models), time-dependent variables, or extreme events—they have invented a "proliferation of often only subtly distinct" separation criteria. Implementing efficient algorithms for each new criterion is a major bottleneck. Many existing implementations are either slow, limited to specific graph types, or non-existent. This paper aims to close the gap between theoretical criteria and practical, high-performance software.

Methods

The authors leverage the CIfly framework, which treats graphical separation as a "causal primitive" that can be reduced to a standard reachability problem (like Breadth-First Search) in a purpose-built directed graph.

The "Causal-to-Reach" Reduction

The core idea is to transform the original graph into a state graph. Each node in the new graph represents a combination of a node from the original graph, the direction from which it was entered, and a "color."

  • Colors as Memory: The authors use "colors" to encode non-local path information. For instance, in $\ast$-separation (used for max-linear models), a path is only valid if it contains at most one collider. A "color" can track whether a collider has already been encountered, allowing a local reachability search to respect this global path constraint.
  • Rule Tables: The logic for these transitions is defined in language-agnostic "rule tables." These tables specify which transitions are allowed based on node properties (e.g., "is this node in the conditioning set $C$?").
A rule table for d-separation (left) and its implementation in R (right).

Datasets

The paper relies on extensive simulation studies using synthetically generated graphs to evaluate scaling behavior:

  • Graph Types: Directed Acyclic Graphs (DAGs), Directed Graphs (DGs), and Directed Mixed Graphs (DMGs).
  • Sampling Schemes: Uniform sampling, Erdős-Rényi (ER) models, and Barabási-Albert (scale-free) models.
  • Regimes: Both sparse ($m = O(p)$) and dense ($m = O(p^2)$) edge densities were tested, with graph sizes ranging from $p=128$ to $p=6144$ nodes.

Key Insights and Ideas

  • Universal Reachability: Seemingly disparate criteria (from trek-separation in Gaussian models to $\delta$-separation in time-series models) can all be understood through the same algorithmic lens.
  • Optimal Complexity: For almost all studied criteria, the algorithm runs in $O(p + m)$ time. Since you must at least read the graph (which is $O(m)$), this is effectively the best possible theoretical performance.
  • Language Agnostic Logic: By using rule tables, the core logic of the algorithm is separated from the implementation language. This allows the same "rule" to be deployed instantly in both R and Python via the ciflyr and ciflypy packages.
Summary of the different separation criteria unified by the framework.

Key Results

  • Empirical Scaling: The simulations confirmed that the algorithms scale linearly with the number of edges in sparse graphs.
  • Massive Speedups: When compared to established R packages like pcalg and dagitty, the CIfly-based implementation was orders of magnitude faster. For a sparse DAG with 4,096 nodes, ciflyr checked d-separation in ~1 millisecond, while dagitty took ~400ms and pcalg took over 16 seconds.
  • $\sigma$-Separation: Even for the highly complex $\sigma$-separation (used in cyclic models), the authors developed an $O(p(p+m))$ algorithm, which remains fast enough for large-scale studies.

Limitations and Future Work

The primary limitation identified is the handling of $\sigma$-separation. Because this criterion depends on Strongly Connected Components (SCCs), the CIfly framework requires an additional implementation layer to dynamically generate rule tables based on the graph's SCC decomposition. This adds a linear factor to the complexity, resulting in $O(p(p+m))$ rather than pure linear time.

Future work includes extending this framework to other emerging criteria, such as $c$-separation for discrete-time processes and $\mu$-separation for marginalized local independence graphs. The authors also suggest that this approach could be applied to extremal graphical models used in risk analysis.

Summary updated

Abstract

Statistical graphical models are representations of the dependences between the components of a random vector. They encode these dependences via graphical separation criteria. We consider the algorithmic problem of checking separation statements for the various graph classes and separation criteria that have been developed by the community. We establish that all criteria we study can be checked by modular variations of reachability. For all separation criteria but $σ$-separation, this yields a linear-time algorithm. This is effectively the optimal attainable time since loading the graph itself is linear-time in the number of edges in the graph. Using the CIfly framework for deploying modular variations of reachability, we also provide R and Python code implementing our algorithms. We evaluate empirical runtime and scaling behavior in a simulation study.
BibTeX
@misc{chaviraflores2026algorithmics,
  author = {Moisés Chavira-Flores and Sebastian Weichwald and Leonard Henckel},
  title = {{Algorithmics for Graphical Separation Criteria}},
  year = {2026},
  eprint = {2610.36502},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.36502},
}
Figure