An Efficient Search-and-Score Algorithm for Ancestral Graphs using Multivariate Information Scores for Complex Non-linear and Categorical Data
Nikita Lagrange, Hervé Isambert
Abstract
We propose a greedy search-and-score algorithm for ancestral graphs, which include directed as well as bidirected edges, originating from unobserved latent variables. The normalized likelihood score of ancestral graphs is estimated in terms of multivariate information over relevant "ac-connected subsets" of vertices, C, that are connected through collider paths confined to the ancestor set of C. For computational efficiency, the proposed two-step algorithm relies on local information scores limited to the close surrounding vertices of each node (step 1) and edge (step 2). This computational strategy, although restricted to information contributions from ac-connected subsets containing up to two-collider paths, is shown to outperform state-of-the-art causal discovery methods on challenging benchmark datasets.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on3
- Large-Scale Differentiable Causal Discovery of Factor GraphsRomain Lopez, Jan-Christian Hütter, Jonathan K. Pritchard, Aviv RegevNeurIPS 2022 · 78 citations
- Scores for Learning Discrete Causal Graphs with Unobserved ConfoundersAlexis Bellot, Junzhe Zhang, Elias BareinboimAAAI 2024 · 6 citations
- Scalable and Flexible Causal Discovery with an Efficient Test for AdjacencyAlan Nawzad Amin, Andrew Gordon WilsonICML 2024 · 4 citations
Related papers
- Local Causal Discovery Without Causal SufficiencyZhaolong Ling, Jiale Yu, Yiwen Zhang, Debo Cheng et al.AAAI 2025 · 6 citations
- Integer Programming for Causal Structure Learning in the Presence of Latent VariablesRui Chen, Sanjeeb Dash, Tian GaoICML 2021 · 19 citations
- Estimating Possible Causal Effects with Latent Variables via AdjustmentTian-Zuo Wang, Tian Qin, Zhi-Hua ZhouICML 2023 · 16 citations
- Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential familiesGoutham Rajendran, Bohdan Kivva, Ming Gao, Bryon AragamNeurIPS 2021 · 18 citations
- Efficient Intervention Design for Causal Discovery with LatentsRaghavendra Addanki, Shiva Prasad Kasiviswanathan, Andrew McGregor, Cameron MuscoICML 2020 · 34 citations
