NOTEARS Smooth Acyclicity

Worked Example

Consider a 3-node graph with three potential edges forming a cycle: W₀₁ = a, W₁₂ = b, and W₂₀ = c. All other edges are zero. The NOTEARS acyclicity constraint h(W) uses the Hadamard (elementwise) square of the adjacency matrix, B = W ∘ W, to prevent negative weight cycles from canceling out positive ones. The constraint is defined as h(W) = tr(e^B) - 3.

Let a = 1, b = 1, and c = 0.5. The cycle product is abc = 0.5, and the squared cycle product is (abc)² = 0.25. Since the only closed walks in this graph are multiple traversals of the 0 → 1 → 2 → 0 cycle, B³ = (abc)²I. The Taylor series for the matrix exponential simplifies significantly:

h(W) = 3 Σ (abc)^(2k) / (3k)!

For a=1, b=1, c=0.5:
k=1: (0.25)^1 / 3! = 0.25 / 6 ≈ 0.041666666666666664
k=2: (0.25)^2 / 6! = 0.0625 / 720 ≈ 0.00008680555555555555
k=3: (0.25)^3 / 9! = 0.015625 / 362880 ≈ 0.00000004305831128747

h(W) = 3 * (0.041666666666666664 + 0.00008680555555555555 + ...)
h(W) = 0.12526054586606772

To optimize this constraint using gradient descent, we also need its derivative. The derivative of h(W) with respect to the closing edge c is:

∂h/∂c = 6c(ab)^2 Σ k [(abc)^2]^(k-1) / (3k)!

For a=1, b=1, c=0.5:
k=1: 1 * 1 / 6 = 0.16666666666666666
k=2: 2 * 0.25 / 720 = 0.0006944444444444445

∂h/∂c = 6(0.5)(1)(1) * (0.16666666666666666 + 0.0006944444444444445 + ...)
∂h/∂c = 0.5020848838240236

Interactive Experiment

Explore the smooth acyclicity constraint in the NOTEARS Smooth Acyclicity module:

1. 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.
2. 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.
3. 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.

Limitations

While the smooth constraint revolutionized structure learning, it comes with numerical and practical limitations. For large cycles with large weights, the term (abc)^2k can grow extremely fast before the factorial denominator dominates, potentially leading to floating-point overflow during the computation of the matrix exponential.

Additionally, this module isolates only the acyclicity constraint h(W) and its gradient for a 3-node cycle. In a full causal discovery pipeline, h(W) is used as a penalty term alongside a data-fit measure (like least squares). A positive h(W) strictly indicates the presence of cycles; it does not measure how well the graph explains the observed data. Furthermore, while h(W)=0 guarantees a DAG mathematically, numerical optimizers often terminate when h(W) falls below a small tolerance, which may require post-processing (thresholding) to yield a strict DAG.

References

The following primary sources establish the mathematical foundation for the NOTEARS smooth acyclicity constraint and its role in transforming structure learning from a combinatorial search to a continuous optimization problem. They detail both the theoretical derivation of the matrix exponential constraint and the practical algorithms used to optimize it via augmented Lagrangian methods.

• Zheng, X., Aragam, B., Ravikumar, P., & Xing, E. P. (2018). DAGs with NO TEARS: Continuous Optimization for Structure Learning. Introduces the smooth trace exponential constraint for directed acyclic graphs.