Advances in Differentiable DAG Learning: Analytic Constraints and Truncated Power Iteration

Abstract

Recovering Directed Acyclic Graph (DAG) structures from observational data is a fundamental problem in causal discovery and machine learning. This project integrates two recent advances in differentiable DAG learning: (1) the formulation of analytic DAG constraints, which leverage properties of analytic functions to construct new, efficient DAG constraints that mitigate gradient vanishing and improve computational stability, and (2) the development of Truncated Matrix Power Iteration (TMPI), a novel method designed to escape gradient vanishing by utilizing geometric series-based DAG constraints. The analytic constraints framework unifies existing continuous DAG constraints and introduces novel constraints that preserve differentiability while ensuring acyclicity. Meanwhile, TMPI efficiently approximates higher-order polynomial constraints with a reduced computational burden, significantly enhancing scalability. By combining these methodologies, this project explores improved approaches for DAG learning with applications in causal inference and structure learning in high-dimensional settings. Experimental evaluations demonstrate that these methods outperform existing state-of-the-art approaches in structural accuracy and computational efficiency.

Key Contributions

1. Analytic DAG Constraints:

   • Introduces a unified framework for differentiable DAG constraints based on analytic functions.
   • Mitigates gradient vanishing and improves computational stability.

2. Truncated Matrix Power Iteration (TMPI):

   • Proposes a novel method to approximate higher-order polynomial constraints efficiently.
   • Reduces computational burden and enhances scalability.

3. Applications:

   • Demonstrates improved performance in causal discovery and structure learning.
   • Validates the methods on high-dimensional datasets.

Methods

1. Analytic DAG Constraints:

   • Leverages properties of analytic functions to construct new DAG constraints.
   • Ensures differentiability while preserving acyclicity.

2. Truncated Matrix Power Iteration (TMPI):

   • Utilizes geometric series to approximate higher-order polynomial constraints.
   • Reduces computational complexity and improves scalability.

Results

• Structural Accuracy: Outperforms state-of-the-art methods in recovering DAG structures.
• Computational Efficiency: Demonstrates significant improvements in runtime and scalability.
• High-Dimensional Settings: Validates the methods on large-scale datasets.

Links

• Code: GitHub Repository
• Paper: Truncated Matrix Power Iteration Paper, Analytic DAG Constraints paper

Acknowledgments

This project is supported by Centre for Augmented Reasoning, the University of Adelaide.

Keywords

• Causal Discovery
• Directed Acyclic Graphs (DAGs)
• Differentiable Learning
• Machine Learning
• Optimization