- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3(+2)
- Soundness
- 2
Read review
Paper summary
This paper deals with two interesting questions within the continuous DAG learning domain: How informative is a small nonzero residual? Which edges should be removed when several repairs restore acyclicity? For the first question, this authors show sharp local limits for sufficiently smooth exact representations. For the second question, this authors show how a score margin breaks a feasibility tie in an isolated-cycle flow. The experiments verify the proposed ideas.
Critical strengths
- The theory part of this paper is rather strong: Theorem 2.1 gives a clean, formula-independent restriction on the Taylor structure of any smooth exact residual; Theorem 2.2 formalizes the known gradient degeneracy of NOTEARS and DAGMA at the origin. Theorem 4.1 gives a finite-sample guarantee that does not need a unique optimum.
- The task itself is important.
- The paper is honest and frank, even reporting some unfavorable findings: the flow ordering does not transfer to Adam or L-BFGS-B, the initial ratio explains the predictor gain in Table 1, and 23 of 80 certified absent adjacencies disagree with the true graph.
- The exact-population calibration is a well-designed sanity check of the certificate, and the Lean formulation provides more trust.
Critical weaknesses
- This paper is presented very badly: 1) there are many theorems, but not providing some brief sketch or intuitive examples for the readers to quickly capture the main ideas. 2) Table 1 and Table 2 are sparsely presented, leaving a lot of empty spaces, maybe using wraptable can be helpful. 3) Figure 2 is also not so informative, only 4 points in one line, giving shallow reliability.
- The theory part needs more refinement, e.g., Theorem 2.1 is essentially a corollary of vanishing on coordinate subspaces, and when candidates include all missing edges, , so the bounds say only and carry no information.
- Please give a concrete case where the q or r analysis changes the choice of constraint or stopping rule?
Questions for authors
See above.
4 comments
We sincerely appreciate your time and effort in reviewing our manuscript and offering valuable suggestions. As the author-reviewer discussion phase is drawing to a close, we would like to confirm whether our responses have effectively addressed your concerns. If you require further clarification or have any additional concerns, please do not hesitate to contact us. We are more than willing to continue our communication with you.
Thanks for the detailed response and the revision. The added proof sketches, the four-node example, the confidence intervals in Figure 2 and the improved layout make the paper much easier to follow. My concerns regarding the presentation have been addressed, and I will raise my Presentation score accordingly.
However, I think the theoretical part still needs further refinement. Two of my questions are not directly answered:
- The case q = 1. When all missing edges are candidates, q = 1, and Theorem 2.1 only gives O(t²). The response moves to r instead. What does Theorem 2.1 itself tell us in this setting? Also, r can be as large as d here, so the bound of Theorem 2.2 becomes 1/(2d). Is this bound still informative?
- Practical use of q and r. The stopping check τ(W) ≤ δ does not use q or r, and the constant K cannot be computed in practice. Could you give one concrete case where knowing q or r changes what a practitioner does, for example which constraint to use or when to stop?
Therefore, I keep my overall rating for now.
Response to Reviewer P8p2
Thank you for reviewing the revision and for recognizing the improvements in presentation. Our previous reply moved too quickly from to . We appreciate the opportunity to clarify what each result tells us.
1. What does Theorem 2.1 itself tell us when all missing edges are candidates and ?
We agree that alone says little. Theorem 2.1 also tells us which candidate edges must appear together for the residual to respond. Lemma 2 of [1] gives a related return-path criterion for trace constraints in nonnegative adjacency coordinates. In our example on page 4, the base graph has a single unit-weight edge . Only can close a cycle on its own. By our Proposition D.10, the quadratic term of any smooth nonnegative exact residual can therefore only be , with .
Now give edges , , and weight each and set the other candidate weights to zero. All three edges are needed to close the cycle. The candidate set is the same in both cases. The reverse edge alone accounts for . Along the three-edge perturbation, Theorem 2.1 gives , so no term of degree below six can appear. EXP attains this order, with leading term .
On the question of dimension, when all missing edges are candidates and the base graph has at least one edge, . A base graph with a single edge attains this bound, so the optimal EXP distance exponent is and the guarantee does weaken as grows. The case occurs when the base graph has no edges, in which case .
To see which graphs have a stronger guarantee, let be the largest number of vertices in the base graph such that none can reach another. By the strict alternating-cycle property in [2], the tails of the edges in any minimal completion of size at least two are pairwise unreachable. Hence . With all missing edges available, joining those vertices in a directed cycle attains the bound. If , a single back edge suffices. Thus in our setting. For example, two disjoint chains have . By Theorem 2.2, their optimal EXP distance exponent is , however long the chains are.
2. How does knowing change the stopping decision?
Appendix C of [3] measures the smallest edge-weight threshold that makes a given matrix acyclic. Here we fix the threshold first. Suppose we are willing to remove edges of magnitude at most . Is , the default residual tolerance in the linear NOTEARS implementation [4], sufficient? Consider two four-node graphs. In both, the base edges have unit weight and all missing edges are candidates.
The first base graph contains all six forward edges in node order, so . Any back edge of magnitude above forms a two-cycle with a unit-weight edge. That cycle alone contributes more than to EXP. A residual tolerance of therefore guarantees acyclicity after thresholding.
The second base graph contains only , so . If a cycle survives thresholding, there is one of length at most four using at most three candidate edges. In the EXP series, the product of squared edge weights for a four-cycle has coefficient . Shorter cycles have larger coefficients. A sufficient tolerance is therefore .
To see why is too loose for the second graph, give , , and weight each and set the other candidate weights to zero. For this four-cycle, the leading contribution to EXP is . Including all higher-order terms gives , below the tolerance, while all four edges survive the cutoff. Both tolerance calculations follow directly from the fixed base graphs and the EXP formula, without estimating .
References and code
[1] DAGs with No Fears: A Closer Look at Continuous Optimization for Learning Bayesian Networks. NeurIPS 2020, Lemma 2, p. 3.
[2] Dimension, Graph and Hypergraph Coloring. Order, 2000, pp. 170–171.
[3] DAGs with NO TEARS: Continuous Optimization for Structure Learning. NeurIPS 2018. See Appendix C and Fig. 5 in the linked arXiv version, pp. 17–18.
[4] Official linear NOTEARS implementation. Default h_tol in notears_linear.
Response to Reviewer P8p2
Thank you for reviewing our paper.
1. What does Theorem 2.1 add beyond vanishing on coordinate subspaces?
We apologize for not clearly explaining this part in the text. Coordinate vanishing does indeed directly provide a q-order bound for signed or vector residuals. However, the 2q-order bound for nonnegative scalars requires another step. If there exists a first nonnegative, non-zero homogeneous Taylor term in the signed neighborhood, then each Newton vertex monomial should involve at least q candidate edge weights, and all exponents must be even; otherwise, we only need to change the sign of one edge weight to make the dominant monomial negative. Therefore, the total degree is at least 2q. Furthermore, it is significant that this argument does not require the assumption (W∘W), and the constructions in the theorem in the text also achieve both bounds.
2. What remains informative when all missing edges are allowed and q=1?
q=1 indicates that for the easiest cycle to form, we only need to add one edge. However, there may be other ways to form cycles in the same graph. We added a four-node example on page 4 of the revised version. If the original graph has only one edge 1→2 with a weight of 1, and we take a very small value t>0 and only add weight t to the reverse edge 2→1, then the EXP residual is approximately t2. However, if we add weight t to 2→3, 3→4, and 4→1, the residual is only about t6/6. In both cases, we need to delete an edge with a weight of t to break the cycle. That is, we actually need to change the same amount, but the residual can be much smaller. In the second case, the residual h is approximately t6/6, so the repair distance t is approximately (6h)1/6. If a larger exponent is used to estimate the distance, when t is sufficiently small, the calculated upper bound will actually be smaller than the actual change needed. This is why, in this example, although q=1, the cycle completed by the three edges r=3 still restricts the exponent of the uniform distance upper bound to 1/6.
3. How would these results change a penalty choice or stopping check?
If we follow the path that reaches the sharp order, the response will be pushed from order 2q to order 4q due to the square of the nonnegative scalar residual. Table 11 in the paper provides a direct comparison of this. When we set q=6 and perform 1,000 projected gradient steps, and then use the vector residual norm as a penalty, the median of the remaining edge weights is 0.122. However, if we use its square, the result is 0.406. Therefore, for the stopping decision, we can first determine the maximum edge weight δ that we are willing to delete, and then check whether the remaining edges form a DAG. That is, τ(W)≤δ in equation 141. However, if we want to calculate the residual tolerance from δ, then in addition to r, we also need the error bound constant and the effective neighborhood to achieve this goal.
4. Typography and presentation.
We have carefully considered your feedback and revised the layout and representation of the tables and figures. In Figure 2, the four points on each curve actually correspond to four different sample sizes. Each point is based on 200 independent replicate experiments, and we have also provided point-by-point, two-sided 95 exact binomial intervals. We have also optimized the writing style, adding some proof sketches and simple examples to improve the readability of the paper. These revisions will be presented in the revised version.