Research map / Probabilistic and scientific modeling / Causal discovery
An Efficient Maximal Ancestral Graph Listing Algorithm
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 MAGLIST, the first brute-force-free algorithm for listing all maximal ancestral graphs (MAGs) in the Markov equivalence class of a PAG, using local vertex transformations with validity conditions and sound and complete orientation rules.
Problem
Listing all MAGs consistent with a partial ancestral graph (PAG) in the presence of latent confounders and selection variables; prior work only had brute-force enumeration.
Approach
Recursively determine the local structure of each vertex: a graphical condition (Thm. 1) prunes invalid local transformations early, and a new orientation rule R11 plus updated rules propagate the consequences, yielding a sound and complete listing with no redundant intermediate graphs.
Key results
- MAGLIST matches BruteForce in number of listed MAGs when d and edge density are small, and lists far more MAGs than BruteForce when they are large, within a 1800-second limit.
- Under the 1800-second limit, MAGLIST is substantially faster than BruteForce across the simulated settings (Fig. 4), with BruteForce often spending very large amounts of time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MAGLIST instead of brute-force enumeration | MAG listing · Simulated PAGs | running time | Helped |
| Use MAGLIST instead of brute-force enumeration | MAG listing · Simulated PAGs with relatively large d and ρ | number of listed MAGs within 1800 seconds | Helped |
| Use MAGLIST instead of brute-force enumeration | MAG listing · Simulated PAGs with d and ρ not large | number of listed MAGs | No clear effect |
Surprising findings
- BruteForce's number of listed MAGs can decrease as graph density increases, because most enumerated graphs are not consistent MAGs.
Limitations
- No theoretical time complexity analysis of MAGLIST, since the number of MAGs in an MEC is unknown.
- Per-vertex enumeration of local transformations is O(2^p) in the number of circles.
- Experiments use only simulated graphs with true PAGs as input, not learned PAGs.
Experimental setup
Datasets: simulated Erdos-Renyi DAGs with 3 latent variables converted to true MAGs and PAGs
Benchmarks: simulated PAGs with d in {6,...,16} and edge probability in {0.1,...,0.5}
Metrics: running time number of listed MAGs
Baselines: BruteForce enumeration
Builds on: Zhang (2008) FCI orientation rules R1-R10 Wang et al. 2023b local background knowledge rules Meek rules DAG transformation (Chickering 1995)
Closest papers by meaning
- Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules (ICML 2025 · similarity 0.94)
- An Efficient Search-and-Score Algorithm for Ancestral Graphs using Multivariate Information Scores for Complex Non-linear and Categorical Data (ICML 2025 · similarity 0.89)
- Local Causal Discovery Without Causal Sufficiency (AAAI 2025 · similarity 0.87)
- Local Identifying Causal Relations in the Presence of Latent Variables (ICML 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)
- A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the Same Skeleton (AAAI 2024 · similarity 0.85)
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.