Learning a causal graph by gradient descent requires a smooth penalty that is zero exactly when the graph has no directed cycles. The penalties in use, the matrix exponential trace of NOTEARS, the log-determinant of DAGMA, and their power-series relatives, all work the same way: they add up weighted counts of closed walks. The weight given to a cycle depends steeply on its length, so long cycles either go nearly unpenalized or make the penalty explode as the graph grows. This proposal starts from a different picture. Attach to a weighted graph its cycle polynomial, $Z_W(z)=\det(I - zA)$, where $A = W\circ W$ is the matrix of squared edge weights and $z$ is an auxiliary complex variable. The graph is acyclic exactly when this polynomial has no zeros anywhere in the complex plane. Learning a DAG then becomes the task of pushing every complex zero of $Z_W$ out to infinity.
That reframing lets us borrow a principle from deterministic approximate counting: how well a polynomial's logarithm can be controlled depends only on how far its complex zeros are from where you evaluate it. Jensen's formula from complex analysis turns "how many zeros lie inside the disc of radius $r$, and how deep" into an exact average of $\log|Z_W|$ over a circle. The resulting penalty treats cycles of every length on equal footing. It is exactly zero whenever the disc is free of zeros, and it can be computed from a few determinants without eigenvector derivatives. Optimization proceeds by growing the zero-free disc from radius near $0$, where every graph is trivially feasible, toward large $r$. This mirrors the way Barvinok-style algorithms continue from an easy point to a hard one through a region known to be free of zeros.
Core Claim
Since $Z_W(z)=\prod_i(1 - z\lambda_i)$ over the eigenvalues $\lambda_i$ of $A$, and $Z_W(0)=1$, Jensen's formula gives
$$J_r(W) \;=\; \frac{1}{2\pi}\int_0^{2\pi}\ln\left|Z_W(re^{i\theta})\right|d\theta \;=\; \sum_{i}\max\big(0,\ \ln(r|\lambda_i|)\big).$$
$J_r$ is zero if and only if $Z_W$ has no zeros in the open disc of radius $r$, which is the same as requiring spectral radius at most $1/r$. Otherwise it equals the summed log-depth of the zeros inside that disc.
The decisive property concerns a single directed $k$-cycle with squared weights $a_e$. Its eigenvalues are the $k$ roots of $\prod_e a_e$, so once the cycle is inside the disc it contributes $k\ln r + \sum_e \ln a_e$. The gradient with respect to each edge is $1/a_e$, with no dependence on $k$. Under the exponential trace, the same edge's gradient carries a $1/(k-1)!$ factor. Under DAGMA's log-determinant at scale $s$ it carries an $s^{-k}$ factor. So the claim is that a zero-counting penalty removes the cycle-length bias that On the Convergence of Continuous Constrained Optimization for Structure Learning, DAGMA and Stable Differentiable Causal Discovery identify as the source of vanishing or exploding signals. It also avoids the zero-gradient degeneracy at feasible points for every finite $r$, because the constraint is inactive in the interior of the zero-free set rather than flat at a single point.
Computing It the Barvinok Way
Evaluating $J_r$ through eigenvalues is a poor idea. Near a DAG, $A$ is close to nilpotent and badly defective, and the derivatives of its eigenvalues blow up there. Instead we discretize the circle with $M$ equally spaced points rotated by a random phase $\varphi$. The product over $M$-th roots of unity collapses, giving
$$\widehat J_{r,M}(W) \;=\; \frac{1}{M}\ln\left|\det\!\big(I - (re^{i\varphi}A)^M\big)\right|.$$
This is one complex determinant of a matrix power, computable in $O(d^3\log M)$ time by repeated squaring, the same doubling trick used in Analytic DAG Constraints for Differentiable DAG Learning. Its gradient needs only a linear solve. Per eigenvalue, the quadrature error is at most about $q^M/M$, where $q=\min(r|\lambda|, 1/(r|\lambda|))<1$ measures how far that zero sits from the contour. This is exactly the Barvinok error law: accuracy degrades only when a zero approaches the circle, and the number of terms needed scales as $\log(d/\epsilon)/\log(1/q)$.
The circle literally hits a zero only when an eigenvalue crosses it. That is the same failure that blocks deterministic counting at $|\lambda|=1$ in The Ising Partition Function: Zeros and Deterministic Approximation. We handle it the way a numerical analyst would: we resample the phase and jitter the radius in a thin band at every step. This turns the kink of the hinge into a smooth annulus average and makes exact contour hits occur with probability zero.
The radius $r$ is then increased on a schedule, in the spirit of DAGMA's central path. A final edge-thresholding step removes residual weak cycles, which can survive at finite $r$ with spectral radius at most $1/r_{\max}$.
Relation to Prior Work
Three lines of DAG-learning work supply the setting and motivate the gap. DAGs with NO TEARS introduced the exponential trace constraint solved by augmented Lagrangian. Learning Sparse Nonparametric DAGs extended it to neural network models by applying the constraint to first-layer weights, and our penalty plugs into that construction unchanged. The convergence analysis in On the Convergence of Continuous Constrained Optimization for Structure Learning shows that the constraint gradient vanishes at every DAG, so the penalty coefficient must grow to about $10^{14}$. We read that as evidence that point-evaluated constraints are the wrong object.
DAGMA is the closest relative, and it is worth being precise about why. Its $-\ln\det(sI-A)+d\ln s$ is $-\ln Z_W(1/s)$ evaluated at a single positive real point. It penalizes every cycle, however weak, with length-dependent weight $s^{-k}/k$. We average $\ln|Z_W|$ over a whole circle instead, which cancels the contribution of every zero outside the disc and leaves a zero count.
Analytic DAG Constraints studies the radius of convergence of positive-coefficient series, but only along the positive real axis. It treats the non-convexity of high-order constraints with pruning heuristics.
There is an honest caveat here. Without the absolute value, the logarithm of our quadrature formula expands as a positive-coefficient series in $A^M$, so it sits near that paper's class $\mathcal{F}$. What distinguishes our penalty is the modulus inside the logarithm. That is what makes the circle average vanish identically inside the zero-free disc. The other distinguishing pieces are the continuation in $r$ and the length-independent gradient.
Stable Differentiable Causal Discovery uses the spectral radius $\rho(A)=0$, computed by power iteration. This is our most serious competitor: $J_r$ for large $r$ is a sum of log-hinges on all eigenvalue moduli, whereas SDCD acts only on the top one.
The counting literature supplies the method rather than the application. Correlation Decay and Partition Function Zeros continues from an easy point to a target through a region proven free of zeros. Correlation decay and the absence of zeros property shows that zero-freeness has structural consequences for how far influence propagates. We use those ideas in reverse: zero locations become the optimization target rather than a precondition for approximation.
We deliberately leave graph matching aside. Its natural partition function is a permanent, and we know of no tractable zero-free theory for it. Real smoothing (Gaussian Smoothing Based Optimization) and two-stage starts (Graph Matching: Relax at Your Own Risk) remain the right tools there.
Research Program
The theory work has three parts. First, prove the length-independence property for general cycle structures, including cycles that share edges, where eigenvalues no longer factor cleanly; we expect a bound rather than an identity. Second, characterize the stationary points of the annulus-smoothed $J_r$ restricted to the acyclicity term, asking whether a DAGMA-style result holds that every stationary point is feasible. Third, give the quadrature error and gradient-variance bounds as a function of the distance from the zeros to the contour.
The implementation work is a drop-in penalty for linear models and for the neural-network models of NOTEARS-MLP. It comes with a radius schedule and a contour-jitter rule, written in a single codebase that also implements the competing penalties so solvers and tuning are shared.
Baselines
The naive reference point is the same least-squares or likelihood loss with an L1 penalty, thresholded and then made acyclic by greedily deleting the weakest edge in each remaining cycle. This shows how much any acyclicity penalty buys.
The first strong baseline is DAGMA (DAGMA) with its own central-path schedule. It is the most direct competitor because it evaluates the same polynomial $Z_W$ at one real point. The file reports it as roughly ten times faster than NOTEARS and able to detect cycles in a 100-node graph that earlier methods saw as zero acyclicity. No SHD number is reported on Lacuna, so we will rerun it.
The second is the order-3 and order-4 constraints of Analytic DAG Constraints, reported to beat DAGMA in structural Hamming distance (SHD, the number of edge additions, deletions and reversals separating the estimated graph from the truth) on graphs up to 2,000 nodes. No reported SHD value is found on Lacuna.
The third is SDCD's spectral-radius constraint (Stable Differentiable Causal Discovery), reported to run on 4,000 variables in under three hours while other baselines crashed numerically at 50. Here too no SHD value is found on Lacuna.
NOTEARS with L-BFGS serves as the classical reference.
Fairness is enforced by swapping only the acyclicity term. Every penalty uses the same data-fit loss, the same solver (L-BFGS and Adam, both reported), the same thresholding rule, and the same hyperparameter search: twenty configurations per method on held-out seeds, with the same wall-clock cap per run. SDCD's Stage-1 pruning is reported both on and off, so we can separate the effect of pruning from the effect of the constraint.
The key-ingredient ablation replaces the circle average with the same expression at a single real point $z=r$, which recovers a DAGMA-like penalty. A second ablation keeps only the top eigenvalue in $J_r$, which recovers a log-spectral-radius hinge. Beating the baselines means lower median SHD at matched runtime on at least the long-cycle-heavy graphs: scale-free graphs and larger $d$ with denser ER graphs. It also means a higher fraction of runs ending acyclic before post-processing, and no numerical failures where competitors fail.
Why not just…?
Why not just use SDCD's spectral radius, which already avoids exploding power series? This is the real threat. If the top-eigenvalue ablation matches full $J_r$, then the contribution reduces to a better way of computing the spectral radius through determinants, which is still useful near defective matrices but much narrower. We expect full $J_r$ to win because the spectral radius penalizes one cycle at a time, and because its gradient, built from the leading eigenvectors, degenerates as $A$ approaches nilpotency. The top-eigenvalue ablation, run on planted graphs with many simultaneous cycles, settles this directly.
Why not just tune DAGMA's scale $s$, or log-transform the exponential trace? Neither removes the length weighting. At a real point $1/s$, a $k$-cycle is still weighted by $s^{-k}/k$, and taking the log of $\mathrm{tr}\,e^A-d$ only rescales a sum whose terms already carry $1/k!$. We include log-NOTEARS and a sweep over $s$ as baselines. The single-real-point ablation isolates whether the circle average itself matters.
Why not just rely on L-BFGS to absorb the ill-conditioning? On the Convergence of Continuous Constrained Optimization shows L-BFGS survives where first-order methods fail, but the underlying degeneracy still forces penalties toward $10^{14}$. DAGMA shows NOTEARS with L-BFGS still misses long cycles. We run every penalty under both L-BFGS and Adam and record the largest penalty coefficient reached and the curvature of the penalty term. If our penalty only helps under Adam, that is a weaker but honest result.
Why not just use discrete search such as greedy equivalence search? Learning Sparse Nonparametric DAGs reports the greedy nonparametric search taking over 90 minutes on 40 nodes, where NOTEARS-MLP finished in under 5. Discrete search is not the regime this proposal targets, so we include it only at small $d$.
Proposed Experiments
The synthetic suite follows the cited papers. It uses ER and scale-free DAGs with $d$ from 10 to 2,000, sample sizes 20 and 1,000, and Gaussian, exponential and Gumbel noise, as in NOTEARS and Analytic DAG Constraints. It extends to $d$ up to 4,000 on the SDCD protocol and the DCDI simulated suite. Nonlinear models use the additive Gaussian-process and MLP structural equations at $d=40$, $n=1000$. The real-data test is Sachs, where the reference point is NOTEARS-MLP's reported 7 correct edges and 3 reversed. Metrics are SHD, true and false discovery rates, runtime, numerical-failure rate, and the fraction of runs ending acyclic before post-processing.
Three checks are decisive. First, a planted long-cycle test in the style of DAGMA's 100-node experiment. We start optimization from graphs containing one cycle of controlled length $k$ from 3 to 60 and measure the penalty gradient on its edges. Prediction: flat in $k$ for $J_r$, falling factorially for the exponential trace and geometrically for log-determinant. Second, a quadrature check. We compare the log error of $\widehat J_{r,M}$ against $M$, which should fall linearly with slope $\log q$ set by the nearest zero's distance to the contour. If it does not, the Barvinok-style error control fails. Third, the two ablations above: single real point, and top eigenvalue only. If full $J_r$ fails to beat both on dense and scale-free graphs at $d\ge 500$, the zero-counting idea is not pulling its weight, and we will report it as such.
References
- On the Convergence of Continuous Constrained Optimization for Structure Learning
- DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization
- Stable Differentiable Causal Discovery
- Analytic DAG Constraints for Differentiable DAG Learning
- The Ising Partition Function: Zeros and Deterministic Approximation
- DAGs with NO TEARS: Continuous Optimization for Structure Learning
- Learning Sparse Nonparametric DAGs
- Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions
- Correlation decay and the absence of zeros property of partition functions
- Effiecient Graph Matching by Adjacency Matrix Based Model and Gaussian Smoothing Based Optimization
- Graph Matching: Relax at Your Own Risk