Research map / Learning theory and algorithms / Sample complexity
Identification for Tree-Shaped Structural Causal Models in Polynomial Time
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.
Gives a randomized polynomial-time algorithm that decides generic identifiability (identifiable, 2-identifiable, or unidentifiable) of each parameter in tree-shaped linear SCMs, returning FASTPs when identifiable.
Problem
Identification of linear structural causal model parameters (direct and confounding effects) from covariances; prior algorithm for tree-shaped SCMs (TreeID) was PSPACE and not shown complete.
Approach
Finds identifying missing-edge cycles via randomized matrix products of 2x2 Möbius-type weights over layered graphs (avoiding cycle enumeration), uses resultants/rank of missing edges to show completeness, and outputs FASTPs with a Schwartz-Zippel-based check.
Key results
- Randomized polynomial-time algorithm (overall O(e·n^4) running time) decides for each structural parameter whether it is generically identifiable, 2-identifiable, or unidentifiable in tree-shaped SCMs.
- Algorithm is complete: it returns one or two FASTPs for identifiable or 2-identifiable parameters, improving on TreeID's PSPACE bound.
Limitations
- Restricted to tree-shaped directed components
- Randomized (Schwartz-Zippel) rather than deterministic algorithm; derandomization is open
- Generic identifiability only
Experimental setup
Metrics: running time complexity
Baselines: TreeID Gröbner basis approach
Builds on: TreeID (van der Zander et al. 2022) Wright's trek rule Schwartz-Zippel lemma FASTP (Foygel et al.)
Closest papers by meaning
- On the Complexity of Identification in Linear Structural Causal Models (NeurIPS 2024 · similarity 0.93)
- Standardizing Structural Causal Models (ICLR 2025 · similarity 0.88)
- Identifiability of Direct Effects from Summary Causal Graphs (AAAI 2024 · similarity 0.88)
- A Fixed-Point Approach for Causal Generative Modeling (ICML 2024 · similarity 0.87)
- Strong and Weak Identifiability of Optimization-based Causal Discovery in Non-linear Additive Noise Models (ICML 2025 · similarity 0.87)
- Consistency of Neural Causal Partial Identification (NeurIPS 2024 · similarity 0.87)
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.