Research map / Probabilistic and scientific modeling / Causal discovery

Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules

ICML 2025 · Probabilistic and scientific modeling › Causal discovery · approach: Differentiable and score-based DAG learning

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 the first polynomial-delay algorithm for listing all MAGs in a PAG's Markov equivalence class, using sound and locally complete orientation rules for singleton background knowledge, and gives counterexamples showing existing rules (including its own) are incomplete for general BK.

Problem

Listing all maximal ancestral graphs (MAGs) in the Markov equivalence class represented by a partial ancestral graph (PAG) efficiently, given latent variables and observational data; prior MAG listing (MAGLIST) has exponential delay.

Approach

Enumerate one circle at a time as singleton background knowledge and update the graph with new sound and locally complete orientation rules (R14-R16), so each enumeration is propagated and redundant enumeration is avoided, yielding polynomial delay.

Key results

• MAGLIST-POLY returns identical MAG sets to BRUTEFORCE and MAGLIST when d < 10 and consistently has the lowest runtime across densities and d.
• Under a 3600-second limit, the methods exceed the time budget for d >= 10, so comparisons are reported only for smaller graphs.
• On real phosphoproteins data, maximal-entropy intervention selection identified 98 marks versus 81 for random selection over 10 repetitions.

Measured effects reported in the paper

Surprising findings

• Existing orientation rules, including the paper's own locally complete rules, are shown to be incomplete for general background knowledge via two counterexamples.
• The paper argues MAGLIST has exponential delay, O(2^d/d) per output, on a specific PAG family.

Limitations

• Rules are only locally complete for singleton BK; not complete for general background knowledge.
• Counting MAGs in a MEC remains open, so delay analysis relies on an unknown output count.
• Experiments are limited to small graphs (d up to 14) because larger cases exceed the time limit.

Experimental setup

Datasets: Erdos-Renyi simulated DAGs with 3 latent variables real phosphoproteins/phospholipids measurements (Wang et al., 2017)

Benchmarks: simulated graphs with d in {6,8,10,12,14} and density 0.1-0.3 phosphoproteins real data

Metrics: running time (log seconds) number of listed MAGs agreement of listed MAG sets number of identified marks under interventions

Baselines: MAGLIST BRUTEFORCE

Builds on: MAGLIST Zhang (2008) orientation rules R1-R10 local background knowledge rules (Wang et al., 2023b) Richardson & Spirtes ancestral graphs

Closest papers by meaning

• An Efficient Maximal Ancestral Graph Listing Algorithm (ICML 2024 · similarity 0.94)
• Hybrid Top-Down Global Causal Discovery with Local Search for Linear and Nonlinear Additive Noise Models (NeurIPS 2024 · similarity 0.85)
• An Efficient Search-and-Score Algorithm for Ancestral Graphs using Multivariate Information Scores for Complex Non-linear and Categorical Data (ICML 2025 · similarity 0.85)
• Testing Causal Models with Hidden Variables in Polynomial Delay via Conditional Independencies (AAAI 2025 · similarity 0.84)
• Local Identifying Causal Relations in the Presence of Latent Variables (ICML 2025 · similarity 0.84)
• Local Causal Discovery Without Causal Sufficiency (AAAI 2025 · similarity 0.84)