{"id":"b299346c-8c36-4f18-a275-1d114988639f","arxiv_id":"2506.13407","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Directed graphs with identical characteristic imset vectors are always covariance equivalent in cyclic linear structural equation models.","lead":"This mathematics paper shows that if two directed graphs (which may contain feedback loops) have the same characteristic imset vector, an algebraic summary of each node's parent set, then they are covariance equivalent: they produce the same set of covariance matrices in linear structural equation models. The result could make causal discovery from observational data faster by searching over smaller algebraic summaries rather than all graphs.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.1's proof relies on an unproved invariant: the algebraic path in C'_n must pass through graph monomials whose column labels match the sparsity of Q at every step.","rationale":"The reader's weakest_assumption identifies the same gap: the proof of Theorem 4.1 depends on an external Givens-rotation lemma and on an unformalized induction guaranteeing that every intermediate monomial is compatible with the column labels and sparsity of Q. I agree that this is the load-bearing weak point. The algebraic development — the Chickering ideal, the doubled ideal, the primary decomposition in Theorem 3.16, and the variety-inclusion argument — appears substantial and internally coherent; those parts are not where the argument is insecure. The insecurity is specifically the translation from algebra to geometry: Eq. (6) is a binomial representation, not a sequence of graph-to-graph moves, and the proof does not establish that one can choose the order of binomials so that each partial sum corresponds to an actual n x n matrix with matching column supports. The second-form moves change which vertex owns a column, so the induction requires tracking column permutations against fixed row labels, and the cited [12, Proposition 3] only covers a single covered edge flip from the initial sparsity pattern. These are concrete, checkable claims, not mere style objections. A computational search on n = 4 and n = 5 can settle whether the required graph-monomial connectivity holds and whether the numerical Givens simulation respects the sparsity invariant at every step. If the search finds a counterexample, the theorem as stated is unsupported; if it succeeds, it would strongly corroborate the proof's missing lemma. Because the claim is plausible, the algebraic core is a genuine contribution, and the gap is repairable in principle, the reader's CONDITIONAL verdict is appropriate; I would not change it.","tokens_in":20803,"tokens_out":20128,"duration_ms":212266,"concrete_test":"Enumerate all loopless directed graphs on n = 4 and n = 5, compute c_G for each, and for every pair (G, H) with c_G = c_H perform a breadth-first search in the space of graph monomials over the moves generated by (5): covered edge flips and support-preserving column relabelings. If some pair is disconnected, the combinatorial part of the Theorem 4.1 proof is refuted. If all pairs are connected, for each connected pair sample 100 random full-rank matrices Q with sparsity of G, simulate the found move sequence with Givens rotations chosen at each covered flip, and verify after every step that the intermediate matrix's zero pattern equals the sparsity of the intermediate graph monomial. Report the first pair or step where the invariant fails; that failure would pinpoint exactly where the unproved induction in Eq. (6) breaks down.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 4.1 (Section 4, around Eq. (6)) asserts that a representation of z_G - z_H in the doubled Chickering ideal C'_n yields a sequence of moves acting on an n x n matrix Q: first-form binomials do nothing, second-form binomials relabel a column between families A∪{b}->c and A∪{c}->b, and third-form binomials act by a proper Givens rotation from [12, Definition 6 / Proposition 3]. The load-bearing invariant — that at every partial sum the active z-exponent vector has exactly one family per vertex and that the column labels of Q agree with its sparsity support — is never proved. A binomial representation as in (6) can pass through monomials with repeated families or multiple families per vertex; for such monomials no n x n matrix with the corresponding column-support set exists. The second-form move also changes the distinguished child of a column, so the column permutation must be tracked against the row indices of Q; the text only asserts this. Moreover, [12, Proposition 3] supplies a Givens rotation for a single covered edge flip starting from a matrix whose sparsity is the initial graph, not for the arbitrary intermediate states that Eq. (6) can create. Without an inductive lemma fixing the order of binomials so that every intermediate monomial is a graph monomial and every relabeled column remains compatible with Q, the implication c_G = c_H => covariance equivalence does not follow from the written argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies characteristic imset vectors for directed graphs that may contain directed cycles. It defines the Chickering ideal, a toric ideal associated with the linear map from family variable vectors to characteristic imset vectors, and introduces a 'doubled' version in which extra y-variables are added. The algebraic heart of the paper is Theorem 3.16, which identifies the Chickering ideal with the intersection of the doubled ideal with the polynomial ring in the z-variables. The main statistical result, Theorem 4.1, asserts that two directed graphs with the same characteristic imset vector are covariance equivalent. The proof proceeds by writing the difference of the two graph monomials as a sum of binomials in the doubled ideal and claiming that each binomial induces an orthogonal transformation of the matrix Q from Proposition 2.5, ultimately showing that the covariance/precision set of G is contained in the Euclidean closure of that of H.","tokens_in":20929,"tokens_out":3137,"duration_ms":34598,"significance":"If Theorem 4.1 is correct, it is a meaningful structural contribution to the theory of cyclic linear SEMs: characteristic imset vectors would provide a vector-valued representative that refines the covariance equivalence relation, and the smaller search space of imsets could be used in score-based or greedy causal discovery. The paper's algebraic development is extensive and largely convincing: Proposition 3.4, the primary decomposition in Proposition 3.12, and the proof of Theorem 3.16 are worked out in detail and appear internally sound. The paper also gives useful examples, including a pair of covariance-equivalent graphs that are not imset-equivalent, clarifying that the implication in Theorem 4.1 is not reversible. The main weakness is that the proof of Theorem 4.1 contains a substantial gap: the translation from a binomial representation in the doubled ideal to a valid sequence of sparsity-preserving orthogonal transformations on the matrix Q is asserted rather than proved. This gap is load-bearing, because the central claim of the paper rests on exactly this geometric realization of the algebraic path.","major_comments":[{"comment":"The proof of Theorem 4.1 asserts that a representation z_G - z_H = sum_i z^{p_i} y^{q_i}(z^{u_i^+} - z^{u_i^-} y^{v_i}) in the doubled Chickering ideal yields a sequence of moves acting on the matrix Q. This requires that each partial sum corresponds to a valid graph monomial, i.e. a z-monomial in which, for every vertex, exactly one family A -> b with b in A appears. The text does not prove that the binomial representation can be ordered so that every intermediate monomial has this property. A general binomial representation can pass through monomials with repeated families or with multiple families for the same vertex, and for such monomials no matrix Q with the corresponding column-supports exists. Without an explicit induction showing that the sequence of binomials can be chosen to stay in the set of graph monomials, the claimed action on Q is not well-defined.","section":"Section 4, Eq. (6)"},{"comment":"The second-form binomial z_{A cup b -> c} - (y_{A -> c}/y_{A -> b}) z_{A cup c -> b} is said to 'relabel' the column labeled A cup b -> c as A cup c -> b. While the two families have the same support, they have different distinguished children, and the column labels of Q are tied to the row indexing of the matrix through the families fa_G(i). The proof does not track how the row indices of Q are permuted when the distinguished child changes. A rigorous argument needs a bookkeeping lemma that fixes the row labels of Q and shows that after relabeling, the column sparsity still matches the active graph monomial. As written, the claimed preservation of 'column labels agree with sparsity' is simply asserted.","section":"Section 4, paragraph on second-form binomials"},{"comment":"The third-form binomial z_{A -> b} z_{A cup b -> c} - z_{A -> c} z_{A cup c -> b} is implemented by a 'proper Givens transformation' cited from [12, Definition 6 and Proposition 3]. That result supplies a Givens rotation realizing a single covered edge flip, starting from a matrix whose sparsity is the initial graph and, generically, preserving the column sparsity pattern. In the present proof, however, the third-form move must be applied to arbitrary intermediate states created by the partial sums of Eq. (6), and those states may not have the property that the relevant edge is covered in the sense required by [12]. The paper gives no argument that the intermediate graph monomials produced by the algebraic path correspond to graphs in which the next covered-edge flip is actually available, nor that the genericity of the Givens rotation can be maintained simultaneously over all steps. This is a second load-bearing gap: without it, the conclusion that Q Q^T lies in the Euclidean closure of M(H) does not follow from the written argument.","section":"Section 4, third-form binomials"},{"comment":"The algebraic part of the paper is careful about the distinction between the Chickering ideal C_n and the doubled ideal C'_n, and Theorem 3.16 is proved in detail. However, the passage from 'z_G - z_H belongs to C'_n' to 'the binomials in Eq. (5) can be applied sequentially to z_G to obtain z_H' requires that the representation in Eq. (6) be a Markov-basis-style path that respects the monomial partial order at every step. The proof does not provide such a path; it only states that z_G can be transformed 'via the binomials' and then immediately interprets each binomial as a geometric operation on Q. Even if every individual binomial can be realized geometrically in favorable situations, the global sequencing and compatibility of those realizations is the core of the theorem and is not established.","section":"Theorem 3.16 and Section 4 transition"}],"minor_comments":[{"comment":"The word 'indeterminants' should be 'indeterminates' in several places, including Section 3 before Definition 3.1.","section":"Throughout"},{"comment":"The generators of C_3 are displayed in a format that may confuse readers: the two rows in the displayed list are part of the same list, and the first row consists of the six covered edge flip binomials while the second row contains three additional generators. A short sentence making the grouping explicit would improve readability.","section":"Example 3.5 and Remark 3.6"},{"comment":"The caption says 'Boxed stars represent the distinguished child in the family that indexes the column.' This is helpful, but the figure itself is not referenced in the main text immediately before or after the proof of Theorem 4.1; adding an explicit reference in Example 4.2 would make the relationship between the algebra and the matrix clearer.","section":"Figure 6"},{"comment":"The paper notes that singleton coordinates are included for algebraic reasons. This is a useful remark, but it would be even clearer to state explicitly in Definition 2.15 that the vector is indexed by all nonempty subsets including singletons, and that the singleton coordinates are identically 1 for every graph. This sentence is already present in the text, so the issue is only one of placement and emphasis.","section":"Definition 2.15 and Remark 3.2"},{"comment":"The paper says that greedy search can search over standard imset vectors instead of directed graphs, but notes that one needs a way to recover a graph in the fiber. This is an honest statement of the limitation, but it may be worth adding a sentence on whether the recovery problem is known to be computationally hard for the cyclic case or whether it is open.","section":"Section 5.1"}],"recommendation":"major_revision","confidential_remarks":"The central claim is likely true and the algebraic framework is valuable, but the proof of Theorem 4.1 as written is incomplete in a way that is load-bearing rather than merely expository. I would encourage the authors to add a formal induction lemma that constructs, from the binomial representation in the doubled ideal, a sequence of graph monomials with exactly one family per vertex and a compatible sequence of orthogonal transformations on Q, tracking row and column labels and the genericity conditions on the Givens rotations. If that lemma can be proved, the paper would be a solid contribution. I do not see evidence of circularity: the theorem is a new implication and the self-cited prior work is used only for the local Givens realization, not for the main equivalence."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real contribution to algebraic statistics for cyclic linear SEMs, but the main theorem is not proven as written. The Chickering ideal and the doubled ideal construction are new, and the algebraic sections are careful. The problem is Theorem 4.1's proof skips the one step that connects algebra to geometry.\n\nWhat is new: the paper extends characteristic imsets to cyclic graphs, defines the Chickering ideal as the toric ideal of the linear map from family variables to imsets, and proves a structural sufficient condition (same imset vector implies covariance equivalence). It also shows by example that imset equivalence strictly refines covariance equivalence. The algebraic development — the doubled ideal, primary decomposition into toric ideals, and Theorem 3.16 relating the two — is substantial and looks sound. I did not verify every line, but the arguments are detailed and plausible.\n\nThe soft spot is exactly where the stress-test lands. The proof of Theorem 4.1 asserts that a binomial representation of z_G - z_H in the doubled ideal yields a sequence of moves on a matrix Q, with each move preserving the property that column labels match the sparsity support. That invariant is never proved. The representation in Eq. (6) can pass through monomials that are not graph monomials — e.g., the second-form binomial changes only one z-variable, so the intermediate exponent vector may not have exactly one family per vertex. For such a monomial, there is no n×n matrix with the corresponding column supports. The third-form step relies on [12, Proposition 3], which gives a Givens rotation for a single covered edge flip from a matrix whose sparsity is the initial graph; it does not cover arbitrary intermediate states. Without an inductive lemma fixing the order of binomials so every intermediate monomial is a graph monomial, the implication does not follow from the written argument.\n\nThat said, the claim is plausible, and the algebraic framework is a genuinely new way to think about the problem. The paper is honest about the argument being generic, but for a main theorem the reader needs the missing induction. The examples are helpful, and the discussion of the smaller search space is reasonable.\n\nWho this is for: people working in algebraic statistics and causal discovery on cyclic models. It deserves a serious referee, but the referee should insist on a complete proof of the geometric translation in Section 4 before acceptance. I would not cite the main theorem yet, though I would consider citing the algebraic construction once the proof is filled in.","headline":"New algebraic refinement of covariance equivalence for cyclic SEMs; the main theorem is plausible but the proof of the geometric step is not yet written.","tokens_in":21606,"tokens_out":3984,"would_cite":false,"duration_ms":37809,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62H22","13F65","62E10","13P25","62D20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Two directed graphs that share a characteristic imset vector are covariance equivalent: their cyclic linear SEMs generate the same covariance matrices up to Lebesgue-null sets and Euclidean closure.","keywords":["characteristic imset vector","family variable vector","covariance equivalence","cyclic linear structural equation models","toric ideals","covered edge flips","cycle reversal","causal discovery"],"falsifier":"An explicit pair of directed graphs with identical characteristic imset vectors but different Euclidean closures of their precision-matrix sets would refute Theorem 4.1. A practical search would enumerate all directed graphs on n=5 or 6 vertices, group them by c_G, and compare, for each fiber, numerically sampled precision matrices from the two parameterizations to see whether the closures differ.","tokens_in":20443,"feed_emoji":"🔁","tokens_out":7779,"duration_ms":73808,"temperature":0.7,"pith_summary":"The paper extends the characteristic imset vector, a standard representative of Markov equivalence for acyclic causal models, to directed graphs that contain cycles, and proves that graphs with the same vector are covariance equivalent. In cyclic linear SEMs, covariance equivalence was previously characterized only through sequences of local graph transformations; this result supplies a static, vector-valued certificate. The theorem matters because imset vectors are computable from the graph's parent sets and form a smaller search space for greedy causal discovery when feedback loops are allowed. The proof proceeds through an associated toric ideal, the Chickering ideal, whose binomial moves correspond to orthogonal transformations of the factor matrix that parameterizes precision matrices.","feed_headline":"Identical imset vectors guarantee covariance equivalence","feed_subtitle":"A vector counting nodes' parent sets now certifies equal covariances even when feedback loops break acyclicity.","key_machinery":"The characteristic imset vector c_G(A)=#{a∈A : A\\{a}⊆pa_G(a)} is the finite-dimensional signature at the center of the argument; the family variable vector v_G records, for every possible child b and candidate parent set A, whether pa_G(b)=A. The linear map φ_n sends v_G to c_G, and its kernel is generated by vectors of the form e_{A→b}+e_{A∪b→c}−e_{A→c}−e_{A∪c→b}, exactly the algebraic footprint of covered edge flips. The Chickering ideal C_n is the toric ideal of φ_n's integer matrix, and its doubled version C'_n, with extra invertible variables, is radical and can be eliminated to recover C_n. The final link to covariance equivalence is the proper Givens transformation, imported from the known transformational characterization, which realizes a covered edge flip as an orthogonal change of the factor matrix Q while generically preserving the sparsity pattern of its columns.","core_discovery":"The central claim is Theorem 4.1: if G and H are directed graphs on the same vertex set and c_G = c_H, then G and H are covariance equivalent, meaning their sets of precision matrices have the same Euclidean closure. The vector c_G(A) counts, for each nonempty set A, how many elements a of A have A\\{a} contained in the parent set of a; this is the same definition as in the acyclic case, but now the vector need not be a 0/1-vector because cycles can force a node to receive multiple parent sets. The authors prove the claim by mapping family variable vectors v_G, which record each node's parent set, through a linear map φ_n whose kernel defines the Chickering ideal, showing that the ideal is a saturation of covered-edge-flip binomials, and then demonstrating that each relevant binomial in the doubled Chickering ideal moves the factor matrix Q along orthogonal transformations that generically preserve its column sparsity. Equality of imset vectors therefore forces a path of sparsity-preserving orthogonal transformations joining the two models, so their precision matrices share the same Euclidean closure.","pith_inferences":["Reading beyond the paper, the failure of the converse in Example 4.4 suggests that a complete algebraic characterization of cyclic covariance equivalence will need invariants beyond the characteristic imset, possibly tracking 3-cycles or other local structures that the imset vector cannot see.","If the fibers of the Chickering ideal admit Markov bases, causal discovery over cyclic models could be implemented as walks along these binomial moves, making the algebraic path constructive rather than existential.","The proof strategy indicates a quantitative route toward a converse: one could look for classes of graphs where every binomial in the Chickering ideal is realizable by sparsity-preserving Givens rotations; for such classes, imset equivalence and covariance equivalence might coincide.","Because imset equivalence is finer than covariance equivalence, a search space of imset vectors may contain multiple representatives of a single covariance class; the size of the resulting redundancy is an open geometric question about the Chickering variety."],"forward_implications":["If two cyclic directed graphs share a characteristic imset vector, they cannot be told apart by covariance data alone: their precision matrices fill the same Euclidean closure, so any covariance-based scoring criterion assigns both graphs the same value.","Searching over standard imset vectors instead of over all directed graphs avoids scoring multiple graphs inside one imset equivalence class, shrinking the search space for greedy causal discovery in the cyclic setting.","For Gaussian noise, covariance equivalence coincides with model equivalence, so equal imset vectors imply agreement of the full set of distributions, not merely of covariance matrices.","The Chickering ideal encodes the imset-equivalence relation: its binomials connect graphs with identical imset vectors, and these binomials translate into orthogonal transformations of the factor matrix Q.","Imset equivalence refines covariance equivalence but is strictly finer even among graphs with the same skeleton; the paper exhibits a pair that is covariance equivalent yet imset-distinct, showing the two relations do not coincide in general."],"supporting_citations":[{"why":"Supplies the proper Givens transformation that realizes a covered edge flip while generically preserving the column sparsity of the factor matrix, the key geometric step of the proof.","marker":"[12, Proposition 3]"},{"why":"Introduces characteristic imset vectors and proves they characterize covariance/Markov equivalence for DAGs, the property the paper extends to cyclic graphs.","marker":"[34]"},{"why":"Defines the linear map φ_n from family variable vectors to characteristic imset vectors and gives the generators of its kernel, which form the basis of the Chickering ideal.","marker":"[7]"},{"why":"Provides the covered-edge-flip transformational characterization for DAGs that motivates the binomial generators of the Chickering ideal.","marker":"[4]"},{"why":"Supplies the binomial-ideal and lattice correspondence used to identify the Chickering ideal as the saturation of the covered-edge-flip binomials.","marker":"[9]"},{"why":"Gives an earlier sufficient condition for covariance equivalence of possibly cyclic mixed graphs, which the present criterion generalizes to fully observed cyclic directed graphs.","marker":"[1]"}],"fun_headline_variants":["Same imset vectors imply same covariances","Imset equality certifies covariance equivalence in cycles","Cyclic causal graphs: imset vectors decide equivalence","Imset vectors settle covariance equivalence"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The theorem depends on the claim that the algebraic binomial moves connecting two graphs with the same imset vector can be ordered and the Givens rotations chosen generically so that at every intermediate step the current matrix has exactly the zero pattern that its column labels describe; the paper asserts this translation from algebra to geometry but does not prove the ordering or the genericity.","fun_headline_variants_meta":{"raw":{"variants":["Same imset vectors imply same covariances","Imset equality certifies covariance equivalence in cycles","Cyclic causal graphs: imset vectors decide equivalence","Imset vectors settle covariance equivalence"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000613,"raw_usage":{"total_tokens":2829,"prompt_tokens":904,"completion_tokens":1925,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":520,"completion_tokens_details":{"reasoning_tokens":1866}},"tokens_in":520,"tokens_out":1925,"duration_ms":13097,"temperature":1.0,"reasoning_tokens":1866,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:04:57.363325+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"An explicit pair of directed graphs with identical characteristic imset vectors but different Euclidean closures of their precision-matrix sets would refute Theorem 4.1. A practical search would enumerate all directed graphs on n=5 or 6 vertices, group them by c_G, and compare, for each fiber, numerically sampled precision matrices from the two parameterizations to see whether the closures differ.","supporting_citations":[{"cited_title":"Characteristic imset: a simple algebraic representative of a Bayesian network structure","cited_arxiv_id":null,"evidence_quote":"Introduces characteristic imset vectors and proves they characterize covariance/Markov equivalence for DAGs, the property the paper extends to cyclic graphs."},{"cited_title":"Polyhedral aspects of score equivalence in Bayesian network structure learning","cited_arxiv_id":null,"evidence_quote":"Defines the linear map φ_n from family variable vectors to characteristic imset vectors and gives the generators of its kernel, which form the basis of the Chickering ideal."},{"cited_title":"A transformational characterization of equivalent Bayesian network structures","cited_arxiv_id":null,"evidence_quote":"Provides the covered-edge-flip transformational characterization for DAGs that motivates the binomial generators of the Chickering ideal."},{"cited_title":"Binomial ideals","cited_arxiv_id":null,"evidence_quote":"Supplies the binomial-ideal and lattice correspondence used to identify the Chickering ideal as the saturation of the covered-edge-flip binomials."},{"cited_title":"Structure learning for cyclic linear causal models","cited_arxiv_id":null,"evidence_quote":"Gives an earlier sufficient condition for covariance equivalence of possibly cyclic mixed graphs, which the present criterion generalizes to fully observed cyclic directed graphs."}],"review_version":2}