NOTEARS Smooth Acyclicity
Detect directed cycles with a smooth matrix-exponential constraint and its gradient.
Free theory articleDetect directed cycles with a smooth matrix-exponential constraint and its gradient.
Concept & interpretation
The NOTEARS (Non-combinatorial Optimization via Trace Exponential and Augmented lagRangian for Structure learning) algorithm fundamentally shifts how we discover directed acyclic graphs (DAGs). Instead of searching through a discrete, combinatorial space of possible graphs, NOTEARS introduces a smooth algebraic constraint that is exactly zero if and only if the weighted adjacency matrix represents a DAG. This allows DAG learning to be framed as a continuous constrained optimization problem.
Interactive Experiment
Explore the smooth acyclicity constraint in the NOTEARS Smooth Acyclicity module:
- Start with the default cycle: Edge zero to one = 1, Edge one to two = 1, and Edge two to zero = 0.5. The graph has a directed cycle, and h > 0.
- Change Edge two to zero to 0. The cycle is broken, making it a DAG. Notice that h becomes exactly 0, and the gradient is 0.
- Change Edge two to zero to -1. The sign of the edge weight changes, but because NOTEARS squares the weights (W ∘ W), the acyclicity penalty h remains identical to when the weight was +1. However, the gradient ∂h/∂c changes sign to properly direct the optimizer toward zero.