Algorithmics for Graphical Separation Criteria

Moisés Chavira-Flores, Sebastian Weichwald, Leonard Henckel
Proceedings of the 13th International Conference on Probabilistic Graphical Models, PMLR 343:210-245, 2026.

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 $\sigma$-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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v343-chavira-flores26a, title = {Algorithmics for Graphical Separation Criteria}, author = {Chavira-Flores, Mois{\'e}s and Weichwald, Sebastian and Henckel, Leonard}, booktitle = {Proceedings of the 13th International Conference on Probabilistic Graphical Models}, pages = {210--245}, year = {2026}, editor = {Camps-Valls, Gustau and Leonelli, Manuele and Varando, Gherardo}, volume = {343}, series = {Proceedings of Machine Learning Research}, month = {09--11 Sep}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v343/main/assets/chavira-flores26a/chavira-flores26a.pdf}, url = {https://proceedings.mlr.press/v343/chavira-flores26a.html}, 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 $\sigma$-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.} }
Endnote
%0 Conference Paper %T Algorithmics for Graphical Separation Criteria %A Moisés Chavira-Flores %A Sebastian Weichwald %A Leonard Henckel %B Proceedings of the 13th International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2026 %E Gustau Camps-Valls %E Manuele Leonelli %E Gherardo Varando %F pmlr-v343-chavira-flores26a %I PMLR %P 210--245 %U https://proceedings.mlr.press/v343/chavira-flores26a.html %V 343 %X 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 $\sigma$-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.
APA
Chavira-Flores, M., Weichwald, S. & Henckel, L.. (2026). Algorithmics for Graphical Separation Criteria. Proceedings of the 13th International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 343:210-245 Available from https://proceedings.mlr.press/v343/chavira-flores26a.html.

Related Material