Optimizing NOTEARS Objectives via Topological Swaps

Chang Deng, Kevin Bello, Bryon Aragam, Pradeep Kumar Ravikumar

Introduction

Learning the structure of a Directed Acyclic Graph (DAG) from data—a process known as causal discovery—is a fundamental yet computationally taxing problem in machine learning. Traditionally, researchers approached this as a combinatorial search, utilizing greedy score-based methods or constraint-based independence tests.

In 2018, the field was transformed by the "NOTEARS" framework, which reformulated DAG learning as a continuous optimization problem. By replacing the discrete "no-cycles" constraint with a smooth, non-convex function, NOTEARS allowed the use of high-performance gradient-based solvers. However, this transition introduced a significant challenge: the optimization landscape of these continuous formulations is often riddled with poor local minima. Consequently, standard solvers frequently converge to sub-optimal graphs that satisfy the acyclicity constraint but fail to capture the true underlying structure.

The TOPO Algorithm

To address these optimization hurdles, this research introduces TOPO (Topological Swaps), a bi-level optimization algorithm designed to navigate the non-convex landscape of DAG learning more effectively. TOPO bridges the gap between discrete structure search and continuous optimization by alternating between two levels of refinement:

  1. Inner Level (Order-Constrained Optimization): When a topological order (a sequence of nodes where edges only point from earlier to later nodes) is fixed, the DAG learning problem simplifies significantly. The acyclicity constraint is inherently satisfied, and the resulting optimization problem often becomes convex or significantly more well-behaved.
  2. Outer Level (Topological Swaps): The algorithm performs a search over the space of topological orders. Rather than relying on random permutations, TOPO employs a strategic "Topological Swap" mechanism to iteratively improve the ordering.

The Role of KKT Conditions

The primary innovation of TOPO lies in its use of Karush-Kuhn-Tucker (KKT) conditions to guide the search. While KKT conditions are typically used as a stopping criterion to verify local optimality, TOPO uses them as a compass. By analyzing the gradients of the score function, the algorithm identifies specific node pairs that, if swapped in the topological order, are most likely to decrease the objective score. This allows TOPO to "jump" between local minima in the continuous space by intelligently modifying the underlying discrete structure.

Experimental Evaluation

The authors evaluated TOPO against state-of-the-art baselines, including NOTEARS, GOLEM, and NOFEARS, across a diverse set of synthetic benchmarks:

  • Linear Structural Equation Models (SEMs): Testing under various noise distributions, including Gaussian (equal and unequal variance), Gumbel, and Exponential noise.
  • Graph Topologies: Evaluations on Erdős-Rényi (ER) and Scale-Free (SF) graphs ranging from sparse to high-density configurations.
  • Nonlinear Relationships: Testing the algorithm's versatility using logistic models for binary data and complex nonlinearities represented by Neural Networks (MLPs).
  • The Fully Connected Challenge: A rigorous test involving a complete DAG (a graph with no missing edges), a scenario where continuous solvers typically struggle to identify the correct edge directions.

Key Insights and Results

TOPO demonstrates significant improvements in both optimization performance and structural accuracy:

  • Superior Optimization Scores: TOPO consistently achieved lower (better) objective scores than its predecessors across nearly all tested environments.
  • Structural Accuracy: The algorithm significantly reduced the Structural Hamming Distance (SHD). In dense graph settings, TOPO achieved up to a 90% reduction in SHD compared to NOTEARS. In the challenging 50-node "fully connected" test, NOTEARS produced an SHD of approximately 1198, while TOPO achieved a remarkably low SHD of 19.
  • Theoretical Contributions: The paper proves that TOPO is guaranteed to return a local minimum or a KKT point under weaker conditions than previously thought necessary. Specifically, it debunks the requirement for "irreducibility," simplifying the theoretical framework for local optimality in DAG learning.
  • Versatility as a Refiner: Beyond acting as a standalone solver, TOPO can function as a post-processing tool. It can take the output of an existing algorithm like NOTEARS and "polish" the result by identifying nearby, strictly better local minima through node swaps.

Limitations and Future Directions

While TOPO offers a robust leap in accuracy, it involves a trade-off in computational complexity. Solving multiple inner optimization problems makes it slower than simple gradient descent. While a "greedy" variant exists to mitigate this, scaling the approach to graphs with thousands of nodes remains an open challenge. Additionally, while TOPO is highly effective at finding high-quality local minima, the problem of finding the global minimum remains NP-hard.

Future work may focus on optimizing the iteration complexity of the swap logic and extending the framework to accommodate non-differentiable score functions, further broadening the applicability of topological search in causal discovery.

Summary updated

Abstract

Recently, an intriguing class of non-convex optimization problems has emerged in the context of learning directed acyclic graphs (DAGs). These problems involve minimizing a given loss or score function, subject to a non-convex continuous constraint that penalizes the presence of cycles in a graph. In this work, we delve into the optimality challenges associated with this class of non-convex programs. To address these challenges, we propose a bi-level algorithm that leverages the non-convex constraint in a novel way. The outer level of the algorithm optimizes over topological orders by iteratively swapping pairs of nodes within the topological order of a DAG. A key innovation of our approach is the development of an effective method for generating a set of candidate swapping pairs for each iteration. At the inner level, given a topological order, we utilize off-the-shelf solvers that can handle linear constraints. The key advantage of our proposed algorithm is that it is guaranteed to find a local minimum or a KKT point under weaker conditions compared to previous work and finds solutions with lower scores. Extensive experiments demonstrate that our method outperforms state-of-the-art approaches in terms of achieving a better score. Additionally, our method can also be used as a post-processing algorithm to significantly improve the score of other algorithms. Code implementing the proposed method is available at https://github.com/duntrain/topo.
BibTeX
@inproceedings{deng2023optimizing,
  author = {Chang Deng and Kevin Bello and Bryon Aragam and Pradeep Kumar Ravikumar},
  title = {{Optimizing NOTEARS Objectives via Topological Swaps}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=BTwEqF0s34},
}
Figure