Research map / Graph learning / Graph algorithms and clustering

Graph Distance Based on Cause-Effect Estimands with Latents

NeurIPS 2026 · Graph learning › Graph algorithms and clustering · approach: Continuous DAG structure 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 Fixing Identification Distance (FID), a graph distance for acyclic directed mixed graphs that counts how often two graphs yield different symbolic cause-effect estimands obtained via fixing-based identification, and compares it to SHD and a separation-based distance on MAGs.

Problem

Evaluating discovered causal graphs is difficult, especially under latent confounding; existing graph distances (SHD, SID, AID, separation-based distances) either ignore downstream causal implications or do not apply to ADMGs with latent variables.

Approach

Extends the identification-strategy/verifier framework (AID) to ADMGs by using identification via fixing to enumerate all valid identifying expressions for each treatment-outcome pair, canonicalizing them symbolically with sympy, and scoring the proportion of candidate-graph estimands not matched by the reference graph.

Key results

• FID increases roughly monotonically with the number of edits; mean normalized FID for 5 edits ranges about 0.35-0.60 across settings.
• Reversing a directed edge yields the largest single-edit impact (pooled mean 0.336), while deleting bidirected edges yields among the smallest (0.153).
• FID correlates with SHD (Pearson r=0.820) and only weakly with ZL-SD (Pearson r=0.292) on MAGs, indicating complementary information.

Surprising findings

• Adding or deleting bidirected edges yields the lowest average FID, but its distribution has a heavy tail with substantial downstream differences in some cases.
• On a small example, AID gives zero distance while FID detects a disagreement in the required adjustment.

Limitations

• Super-exponential complexity from ID-based fixing and enumeration of all fixing sequences, limiting scalability to large graphs.
• Canonicalization is sound but not complete, so some equal estimands may not be merged.
• Evaluation limited to small synthetic graphs (5 variables) with no semi-synthetic or real benchmarks.

Experimental setup

Datasets: synthetic ER-generated ADMGs (420 graphs, 5 variables)

Benchmarks: synthetic ADMG perturbations

Metrics: normalized FID (aidbar) symmetrized normalized FID Pearson correlation with SHD and ZL-SD

Baselines: Structural Hamming Distance ZL-SD separation-based distance

Builds on: Adjustment Identification Distance (AID) Structural Intervention Distance (SID) identification via fixing (nested Markov models) ID algorithm Structural Hamming Distance

Closest papers by meaning

• Toward Falsifying Causal Graphs Using a Permutation-Based Test (AAAI 2025 · similarity 0.89)
• Characterization and Learning of Causal Graphs from Hard Interventions (NeurIPS 2025 · similarity 0.89)
• Adaptive Online Experimental Design for Causal Discovery (ICML 2024 · similarity 0.89)
• Identifying Macro Causal Effects in C-DMGs over DMGs (NeurIPS 2025 · similarity 0.88)
• A Recipe for Causal Graph Regression: Confounding Effects Revisited (ICML 2025 · similarity 0.88)
• Causal Discovery with Fewer Conditional Independence Tests (ICML 2024 · similarity 0.88)