Research map / Probabilistic and scientific modeling / Causal discovery
An Efficient Search-and-Score Algorithm for Ancestral Graphs using Multivariate Information Scores for Complex Non-linear and Categorical Data
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MIIC_search&score, a two-step greedy search-and-score method for ancestral graphs that scores nodes and edges with local multivariate information terms (ac-connected subsets with up to two-collider paths), initialized from MIIC.
Problem
Causal structure learning for ancestral graphs (DAGs with latent variables, giving directed and bidirected edges) from observational data, where the likelihood is hard to estimate from empirical distributions and existing search-and-score methods are mostly limited to linear Gaussian data.
Approach
Decomposes the likelihood of ancestral graphs into multivariate cross-information over ac-connected subsets, which can be estimated directly from empirical distributions, and uses this in a two-step local search: node scores to prime orientations and remove false-positive edges, then edge orientation scores restricted to subsets with up to two-collider paths.
Key results
- On complex non-linear continuous and categorical datasets, MIIC_search&score outperforms MIIC, M3HC, GFCI, DAG-GNN and FCI in precision and recall, especially at small sample sizes.
- On linear Gaussian models, MIIC_search&score is outperformed by GFCI, M3HC and DAG-GNN.
- MIIC_search&score improves edge precision over MIIC with little to no loss of recall.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MIIC_search&score instead of MIIC | MIIC_search&score · Non-linear continuous models, 50 nodes, average degree 5 | precision | Helped |
| Use MIIC_search&score instead of MIIC | MIIC_search&score · Non-linear continuous models, 50 nodes, average degree 5 | recall | No clear effect |
| Use MIIC_search&score instead of MIIC | MIIC_search&score · Categorical benchmarks: Alarm, Insurance, Barley, and Mildew | precision | Helped |
| Use MIIC_search&score instead of MIIC | MIIC_search&score · Categorical benchmarks: Alarm, Insurance, Barley, and Mildew | recall | No clear effect |
| Use MIIC_search&score instead of FCI | MIIC_search&score · Barley and Mildew, small datasets (N ⩽10, 000 samples) | precision | Helped |
| Use MIIC_search&score instead of FCI | MIIC_search&score · Barley and Mildew, small datasets (N ⩽10, 000 samples) | recall | Helped |
| Use MIIC_search&score instead of FCI | MIIC_search&score · Alarm and Insurance categorical benchmarks | precision | No clear effect |
| Use MIIC_search&score instead of linear-assumption methods | MIIC_search&score · Linear Gaussian models | precision | Hurt |
| Use MIIC_search&score instead of other tested methods | MIIC_search&score · Complex non-Gaussian datasets with non-linear couplings | precision | Helped |
Surprising findings
- Linear-Gaussian-assumption methods such as GFCI and DAG-GNN are best on linear Gaussian data, but the method underperforms them there.
Limitations
- Local scores restricted to ac-connected subsets with at most two-collider paths; longer collider paths are not captured.
- Restricted to MAGs without undirected edges.
- Limit cycles can occur in the orientation step due to the local two-collider approximation.
Experimental setup
Datasets: bnlearn Alarm bnlearn Insurance bnlearn Barley bnlearn Mildew simulated linear Gaussian and non-linear continuous ancestral graphs (50 nodes)
Benchmarks: Alarm Insurance Barley Mildew linear Gaussian and non-linear continuous ancestral graph benchmarks
Metrics: precision recall
Baselines: MIIC M3HC GFCI DAG-GNN FCI
Builds on: MIIC Richardson head-and-tail factorization Hu & Evans parametrizing sets fNML regularization
Closest papers by meaning
- An Efficient Maximal Ancestral Graph Listing Algorithm (ICML 2024 · similarity 0.89)
- Local Causal Discovery Without Causal Sufficiency (AAAI 2025 · similarity 0.86)
- Hybrid Top-Down Global Causal Discovery with Local Search for Linear and Nonlinear Additive Noise Models (NeurIPS 2024 · similarity 0.86)
- Local Identifying Causal Relations in the Presence of Latent Variables (ICML 2025 · similarity 0.85)
- Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules (ICML 2025 · similarity 0.85)
- Differentiable Structure Learning with Ancestral Constraints (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.