polydag-efficient-causal-discovery

name	polydag-efficient-causal-discovery
description	Polynomial acyclicity constraints for efficient continuous causal discovery in visual semantic graphs - 33% speedup over exponential baseline with improved F1 scores.
authors	["Wenhao Zhang","Ramin Ramezani","Tao Han"]
date	2026-06-05T00:00:00.000Z
arxiv	2606.06908v1
tags	["causal-discovery","DAG","efficiency","visual-graphs","continuous-optimization"]

polyDAG: Efficient Continuous Causal Discovery

Overview

Polynomial acyclicity framework replacing matrix-exponential constraints for efficient directed acyclic graph (DAG) learning. Achieves 33.4% speedup with improved structure recovery in visual semantic graphs.

Key Innovation

Polynomial vs. Exponential Constraint:

• Prior: Matrix-exponential acyclicity (expensive to compute)
• polyDAG: Finite polynomial trace constraint
• Proof: Polynomial constraint is zero exactly for acyclic graphs

Geometric-Series Implementation:

• Avoids explicit summation loop
• Preserves same acyclicity condition
• Faster computation without approximation loss

Methodology

Standard DAG Learning Problem

NOTEARS Framework (prior):

Constraint: trace(e^{W ⊙ W}) - d = 0
Where W is adjacency matrix, d is dimension

Computation: matrix exponential (O(d^3) operations)

polyDAG Polynomial Constraint

# Polynomial trace constraint
Constraint: polynomial_trace(W) = 0
Exactly zero for acyclic graphs

# Geometric-series implementation (no loop)
polynomial_trace(W) = trace(W^k) for appropriate k
Computed via efficient matrix multiplication

Theoretical Foundation

Key Result:

• Polynomial constraint equivalent to exponential constraint
• Both detect acyclicity exactly
• Polynomial cheaper to compute

Geometric Series Identity:

e^{W ⊙ W} = Σ (W ⊙ W)^k / k!
polyDAG uses finite terms from this series

Algorithm

Input: Data X, initial adjacency matrix W
Output: DAG structure (acyclic W)

Objective:
    loss(W) = reconstruction_error(W, X) + λ * L1(W)
    
Constraint:
    polynomial_trace(W) = 0  # Acyclicity
    
Optimization:
    Project gradient onto constraint surface
    Use augmented Lagrangian or penalty method

Reusable Patterns

Pattern 1: Polynomial Acyclicity Constraint

Use when: DAG learning with continuous optimization Advantage: 33% faster than exponential baseline Implementation:

• Replace matrix exponential with polynomial trace
• Finite sum, no infinite series
• Exact acyclicity detection

Pattern 2: Geometric-Series Avoidance

Use when: Summation loops slow computation Technique:

• Derive closed-form for required terms
• Matrix multiplication chain optimization
• No explicit loop over polynomial terms

Pattern 3: Visual Semantic Graph Causal Discovery

Use when: Structured variables from images (attributes, concepts, descriptors) Application:

• Convert images to semantic variables (e.g., facial attributes)
• Learn directed dependencies among variables
• Produces interpretable causal graphs

Implementation Considerations

Computational Cost

Synthetic Erdős-Rényi graphs (d = 100, 200, 500):

• polyDAG: Mean structural Hamming distance 285.4 (vs. 318.4 baseline)
• polyDAG: Mean F1 score 0.756 (vs. 0.725 baseline)

CelebA facial attributes:

• Improved structure recovery
• Faster convergence

Runtime:

• 100 nodes: 3.44 seconds (polyDAG) vs. 5.16 seconds (baseline)
• 33.4% speedup

Matrix Operations

• Polynomial trace: O(d^2) per term (vs. O(d^3) for exponential)
• Multiple terms still cheaper overall
• Use optimized matrix libraries (e.g., BLAS)

Constraint Satisfaction

• Augmented Lagrangian method (common)
• Penalty method (alternative)
• Projected gradient descent

Extensions

Large-Scale Graphs

• Apply to graphs with thousands of nodes
• Polynomial constraint scalability better than exponential

Dynamic Causal Discovery

• Time-varying DAG structures
• Polynomial constraint per time slice

Multi-Modal Semantic Graphs

• Combine visual, textual, audio attributes
• Cross-modal causal dependencies

Pitfalls

1. Polynomial Degree Selection: Too few terms → incomplete acyclicity check
2. Numerical Stability: Matrix powers can overflow/underflow
3. Convergence Speed: Constraint may be harder to satisfy than exponential
4. Approximation Quality: Finite polynomial must be exact equivalent (choose degree carefully)
5. Gradient Computation: Polynomial trace requires careful gradient derivation

Related Methods

• NOTEARS (DAG learning with continuous optimization)
• DAG-GNN (graph neural networks for DAGs)
• PC algorithm (traditional constraint-based)
• GES (greedy equivalence search)
• CorrGAN (GAN-based causal discovery)

Mathematical Details

Acyclicity Condition

Graph is acyclic iff:
    trace(e^{W ⊙ W}) = d

polyDAG replaces with:
    Σ trace((W ⊙ W)^k) / k! for finite k = d

Why Polynomial Works

• Matrix exponential expands to infinite polynomial series
• Finite terms sufficient for acyclicity detection (proven)
• Exactness theorem in paper

Code Reference

Public repository: https://github.com/wenhaoz-fengcai/polyDAG

Applications

• Visual semantic graph structure learning
• Facial attribute causal discovery
• Object concept dependencies
• Scene descriptor relationships
• Any DAG learning with efficiency requirements

Activation Keywords

polyDAG, polynomial acyclicity, efficient DAG learning, causal discovery, visual semantic graphs, continuous optimization, NOTEARS alternative, acyclicity constraint, 33% speedup, geometric series, matrix trace constraint