Algorithmics for Graphical Separation Criteria
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.
Related
- Learning extremal graphical structures in high dimensions
- A graphical approach to integration and the fundamental theorem
- Degree of the Gaussian graphical model of the cycle
- Interior curvature estimates for graphical curvature quotient equations
- Interior Curvature Estimates for the Graphical Scalar Curvature Equation in All Dimensions
BibTeX
@misc{chaviraflores2026algorithmics,
title = {{Algorithmics for Graphical Separation Criteria}},
author = {Moisés Chavira-Flores and Sebastian Weichwald and Leonard Henckel},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.36502},
eprint = {2610.36502},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.36502},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Algorithmics for Graphical Separation Criteria
AU - Moisés Chavira-Flores
AU - Sebastian Weichwald
AU - Leonard Henckel
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.36502
UR - https://arxiv.org/abs/2610.36502
AB - 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.
ER -