polyDAG: Polynomial Acyclicity Constraints for Efficient Continuous Causal Discovery in Visual Semantic Graphs

2026-06-08 · Source: cs.CV updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Data Science & Analytics · Depth: Expert, extended

Summary

polyDAG is a novel polynomial acyclicity framework designed for efficient continuous causal discovery in visual semantic graphs. It replaces the computationally expensive matrix-exponential acyclicity constraint used in methods like NOTEARS with a finite polynomial trace constraint, proven to be zero exactly for acyclic graphs. A geometric-series implementation, polyDAG-Geo, further optimizes this, avoiding explicit summation loops. Experiments on synthetic Erdős–Rényi graphs (d ∈ {100, 200, 500}) show polyDAG-Geo reduces mean structural Hamming distance from 318.4 to 285.4 and improves mean F1 score from 0.725 to 0.756. At 100 nodes, it achieves a 33.4% speedup, running in 3.44 seconds compared to 5.16 seconds for the exponential baseline. It also demonstrates application to CelebA facial visual attributes.

Key takeaway

For Machine Learning Engineers building causal discovery pipelines, polyDAG-Geo offers a significant efficiency and accuracy improvement over existing continuous acyclicity constraints. You should consider integrating this geometric-series evaluation into your gradient-based DAG solvers, especially for datasets with hundreds of nodes, to achieve faster training and better structure recovery. Always perform post-threshold DAG validity checks to ensure the learned graph is truly acyclic for downstream causal inference.

Key insights

polyDAG offers a faster, provably equivalent polynomial acyclicity constraint for continuous causal discovery.

Principles

• A finite polynomial trace can replace matrix-exponential acyclicity.
• Geometric series evaluation improves O(d^3) constant factors.
• Constraint equivalence ensures identical feasible sets.

Method

polyDAG formulates acyclicity as ∈tr((I-A)^-1(A-A^d+1))=0, where A=W∘W. This is embedded in an augmented Lagrangian framework, solving ∈min_W F(W) + α h(W) + ρ/2 h(W)^2 with Adam.

In practice

• Use polyDAG-Geo for faster continuous DAG learning.
• Apply to visual semantic graph learning for interpretability.
• Verify post-threshold DAG validity with topological sort.

Topics

• Causal Discovery
• Directed Acyclic Graphs
• Acyclicity Constraints
• Visual Semantic Graphs
• Augmented Lagrangian Optimization
• NOTEARS
• CelebA Dataset

Code references

• wenhaoz-fengcai/polyDAG

Best for: Computer Vision Engineer, AI Scientist, Machine Learning Engineer, Research Scientist

Related on AIssential

• polyDAG: Polynomial Acyclicity Constraints for Efficient Continuous Causal Discovery in Visual Semantic Graphs — polyDAG introduces a polynomial trace constraint for efficient continuous causal discovery in visual semantic graphs.
• MARLIN: Multi-Agent Reinforcement Learning for Incremental DAG Discovery — MARLIN efficiently learns causal DAGs incrementally in online settings using a multi-agent reinforcement learning approach.
• Estimate Collapsibility of Causal Effects in Completed Partial DAGs via Strong d-Convex Hulls — A collapsible method estimates causal effects in CPDAGs, maintaining consistency before and after marginalization.
• Causal Learning with the Invariance Principle — Two auxiliary environments suffice for causal graph and counterfactual inference in acyclic, invertible SCMs.
• v185: Proceedings of KDD Workshop on Causal Discovery 2022 — This volume, PMLR 185, compiles the proceedings of "The KDD'22 Workshop on Causal Discovery," which took place on August 15, 2022, in Washington D.C.
• Identifiability of Causal Graphs under Non-Additive Conditionally Parametric Causal Models — CPCMs offer flexible causal discovery by modeling conditional distributions with diverse parametric families.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.CV updates on arXiv.org.