{"id":"5b1f44ce-2a06-40fc-b7d9-9948f59fc470","arxiv_id":"2412.18501","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A graph Hilbert transform is defined on directed graphs after minimal edge addition, which provably creates a cycle cover that supports phase analysis.","lead":"This paper gives a way to define phase and a Hilbert transform for signals on directed graphs, by first adding a few edges so the graph has a full set of complex frequencies. The authors prove the added edges create a cycle cover, which lets phase be read off along cycles in the usual way.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 1's proof is not valid as written: '0-acyclic' under the given definition is trivial, so the cycle-cover conclusion needs [21]'s exact definition or a direct determinant argument; independent determinant proof shows the claim itself is true.","rationale":"I agree with the reader's weakest_assumption. The central mathematical artifact is Proposition 1, and its proof relies on [21, Th. 4.4] and on a definition of r-acyclic that, as printed, makes '0-acyclic' vacuous. The inference to 'admits a cycle cover' is therefore unsupported by the text as written. This is not merely cosmetic: Proposition 1 is the paper's stated theoretical novelty and underpins the cycle-cover interpretation used to motivate the GHT. However, the proposition is independently true because invertibility of A' implies a nonzero determinant, and the determinant expansion over permutations forces a directed cycle cover. Thus the concern is about proof rigor and verifiability, not about the truth of the theorem. The corollary proof being in an absent supplementary file adds to the unverifiability. The synthetic and experimental results are qualitative; they demonstrate behavior but do not quantitatively establish phase accuracy on arbitrary graphs. Overall, the reader's CONDITIONAL verdict is appropriate, and no change to that verdict is needed; the authors should replace the flawed r-acyclic inference, provide the corollary proof, and ideally include a quantitative evaluation.","tokens_in":8008,"tokens_out":14010,"duration_ms":134954,"concrete_test":"Re-derive Proposition 1 without citing [21]: expand det(A') over permutations; show that det(A')≠0 implies some permutation with all entries nonzero, whose cycle decomposition covers every vertex. If this proof succeeds, ask the authors to replace the r-acyclic argument with this direct argument and to provide the missing proof of Corollary 1.1; if it fails, search for an invertible diagonalizable adjacency without a cycle cover as a counterexample.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing point is the proof of Proposition 1 in Sec. III-C, which is the paper's stated theoretical novelty and the basis for interpreting the GHT over a cycle cover. As printed, 'r-acyclic' is defined by 'any collection of vertex-disjoint cycles covers at most N−r nodes', so '0-acyclic' means 'any such collection covers at most N nodes', which is true for every graph. The sentence 'therefore G' can only be 0-acyclic, consequently G' admits a cycle cover' is therefore an invalid inference from the stated definition. The contradiction only establishes that G' is not r-acyclic for any r>0; converting that into the existence of a collection covering all N nodes requires the r-acyclic notion in [21] to mean a maximal deficiency or an exact covering number, and that is not what the paper states. If [21, Th. 4.4] uses a different definition, the proof as written fails. Independently, the claim itself is true: since A' is invertible, det(A')≠0, and a nonzero term in the determinant expansion over permutations forces at least one permutation with all A'_{i,π(i)}≠0, whose cycles cover V. So the concern is a rigorous-proof gap, not a false theorem; the proof should be rewritten. In addition, the proof of Corollary 1.1 is deferred to a supplementary file that is not present in the arXiv version, leaving that result unverifiable as submitted.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes a graph Hilbert transform (GHT) for directed graphs. The authors build on the Seifert–Püschel framework that adds edges to a digraph's adjacency matrix to make it diagonalizable and invertible, define a spectral filter in Eq. (1) that multiplies GFT coefficients by −j or +j according to the sign of the imaginary part of the corresponding eigenvalue, and define an analytic graph signal. The main theoretical contribution is Proposition 1, which claims that the perturbed graph admits a cycle cover, and Corollary 1.1, which gives amplitude/phase combination rules for signals on subcycles. Experiments on a synthetic \"rosace\" graph and on Manhattan/regular-grid graphs illustrate that the GHT produces π/2 phase shifts along directed cycles and interpretable instantaneous amplitude/frequency.","tokens_in":8326,"tokens_out":6387,"duration_ms":57879,"significance":"If the claims are properly supported, the paper makes a useful contribution to graph signal processing by extending a meaningful phase notion to directed graphs with non-diagonalizable adjacency. The filter definition is simple, has no free parameters, and is shown to reduce to the standard Hilbert transform on a single directed cycle; the public implementation is a strength. The main caveat is that the paper's central structural result (Proposition 1) is not proved as printed, and the proof of Corollary 1.1 is missing from the arXiv version; both need to be repaired before the theoretical claims can be assessed. The experimental section is illustrative rather than a systematic benchmark.","major_comments":[{"comment":"The proof as written is not valid. The manuscript defines a graph G to be r-acyclic if any collection of vertex-disjoint cycles covers at most N−r nodes. Under this definition every graph is 0-acyclic (any collection covers at most N nodes), so the statement \"therefore G′ can only be 0-acyclic, consequently G′ admits a cycle cover\" does not follow: the contradiction only shows that G′ is not r-acyclic for any r>0. The inference to a cycle cover requires the definition of r-acyclic used in [21, Th. 4.4], which appears to be a deficiency-type condition, not the definition printed here. Please either state the correct definition from [21] or replace the argument with a direct determinant proof: since A′ is invertible, det(A′)≠0, so the determinant expansion contains a permutation π with A′_{i,π(i)}≠0 for all i; the cycles of π then form a vertex-disjoint cycle cover of V. This is a local but load-bearing fix, because Proposition 1 is the basis for interpreting the GHT over a cycle cover.","section":"III-C, Proposition 1"},{"comment":"The proof is deferred to a Supplementary Material file that is not present in the arXiv version (v3). As submitted, the result is unverifiable. Since this corollary is used to justify the amplitude/phase interpretation on overlapping subcycles, either include the proof in the paper or make the supplementary material available with the submission.","section":"III-C, Corollary 1.1"}],"minor_comments":[{"comment":"The sentence \"for a the total number of nodes of NCNF\" appears garbled; if each of the NC central nodes has an outgoing fan of NF nodes, the total number of nodes is NC(NF+1), not NCNF. Please clarify.","section":"IV-A.1"},{"comment":"\"Removing the non-trivial Jordan blocks\" is inaccurate as a description of the algorithm, which adds edges to dismantle Jordan blocks; please rephrase.","section":"IV-B.1"},{"comment":"The instantaneous frequency definition uses \"k+1 indicates the next node on the fan\"; this only makes sense on cycles with an explicit ordering, so please state this restriction when defining ω(x)[k].","section":"Eq. (3)"},{"comment":"Typos: \"diagonizable\" in Section IV-B.1, \"Theorem. 1\" in the proof of Proposition 1, and the \"S M\" notation in Proposition 1 should be cleaned up.","section":"Throughout"},{"comment":"The claim that average amplitude and frequency per fan are \"accurate estimates of the ground truth\" is not quantified; please add at least one error measure or specify that the plot is qualitative.","section":"Fig. 2"}],"recommendation":"major_revision","confidential_remarks":"The core idea is interesting and the experimental illustrations are compelling, but the Proposition 1 proof gap is exactly the kind of issue that should be fixed before publication. The missing supplementary proof for Corollary 1.1 is also a concern. I recommend requesting a revision rather than rejecting; the fixes appear local and within the scope of the manuscript."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a solid methods paper for graph signal processing, proposing a Hilbert transform for directed graphs via the minimal-perturbation framework of Seifert and Püschel. What's genuinely new is the claim that the perturbed adjacency always admits a cycle cover, giving a clean structural interpretation of phase: signals on subcycles combine like traditional HT. The filter itself is a natural spectral sign-flip, but the cycle-cover theorem is what makes it more than a definition. The authors also ship code and show nice experiments on synthetic fans, a regular grid, and the Manhattan graph.\n\nThe soft spot is real: the proof of Proposition 1 as written doesn't go through. The text defines 'r-acyclic' as 'any collection of vertex-disjoint cycles covers at most N−r nodes,' so '0-acyclic' just means 'covers at most N nodes,' which is true for every graph. The contradiction only rules out r>0, and that doesn't imply existence of a collection covering all N nodes unless you're using a different notion of r-acyclic from [21]. The stated definition doesn't give you that. The stress-test note is correct on this point. The good news: the claim is true. Since A' is invertible, det(A')≠0, so a non-zero term in the Leibniz expansion yields a permutation whose cycles cover V. The proof can be rewritten directly without the r-acyclic detour. Also, the proof of Corollary 1.1 is deferred to supplementary material that isn't in the arXiv version; that should be fixed.\n\nIn proportion: these are presentation/rigor issues, not a false result. The experiments are qualitative but convincing for an SPL-length paper; the synthetic fan example clearly shows the difference from the JNF-based GHT. The circularity burden is low: the GHT is designed to match the classical HT on a cycle, and the paper demonstrates that, so no parameter fitting is happening.\n\nBottom line: worth a serious referee. A careful revision that fixes the proof of Prop 1 and includes the corollary proof would make this a nice contribution to GSP. I'd be comfortable citing it after that.","headline":"Useful graph-Hilbert-transform method with a fixable proof gap in its cycle-cover proposition; worth engaging after a revision.","tokens_in":8809,"tokens_out":1786,"would_cite":true,"duration_ms":15514,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C20","94A12"],"pacs":[],"model":"deepseek-v4-flash","headline":"The minimal edge additions that make a directed graph's adjacency diagonalizable and invertible always create a cycle cover, and this cycle cover is what lets a graph Hilbert transform give every node a phase.","keywords":["graph signal processing","Hilbert transform","directed graphs","cycle cover","graph Fourier transform","instantaneous phase","analytical signal","minimal edge perturbation"],"falsifier":"Run the edge-addition procedure on a small directed graph that has a node of zero in-degree or zero out-degree, and inspect the resulting graph: if that node is left off every directed cycle, Proposition 1 is false and the phase interpretation fails there. A concrete candidate is a directed star or a directed path with a single added edge; the claimed cycle cover must include all nodes.","tokens_in":1633,"feed_emoji":"🔄","tokens_out":2147,"duration_ms":90860,"temperature":0.7,"pith_summary":"The paper tackles a core obstacle in signal processing on directed graphs: the adjacency matrix is generally not diagonalizable, so the usual graph Fourier transform, and any phase derived from it, is not defined. It takes a recently proposed procedure that adds a minimal number of edges to make the adjacency matrix diagonalizable and invertible, and proves that those added edges always create a cycle cover, a set of directed cycles that visits every node. On this cycle cover the paper defines a graph Hilbert transform whose spectral filter rotates the coefficients of conjugate eigenvalue pairs by plus or minus 90 degrees, recovering the classical notions of instantaneous amplitude and phase on each cycle. A sympathetic reader would take the contribution to be: with a few well-chosen added edges, phase analysis becomes possible on any directed graph, not just on graphs whose adjacency happens to be diagonalizable.","feed_headline":"Adding edges to directed graphs unlocks signal phase via cycle covers","feed_subtitle":"Every node gets instantaneous phase and amplitude via the cycles that minimal edge additions create.","key_machinery":"The central object is the spectral filter $\\hat{H}$ defined in Eq. (1), a diagonal matrix in the eigenbasis of the perturbed adjacency $A' = U\\Lambda U^{-1}$. It assigns $-j$ to eigenvalues with positive imaginary part, $+j$ to those with negative imaginary part, and $0$ to real eigenvalues, so the transform $H(x) = U\\hat{H}U^{-1}x$ maps real graph signals to real graph signals and defines the analytic graph signal $\\tilde{x} = x + jH(x)$. The enabling graph-theoretic fact is Proposition 1: because the perturbed graph is diagonalizable and invertible, it cannot be $r$-acyclic for nonzero $r$, so it is $0$-acyclic and therefore admits a cycle cover; each cycle in that cover behaves like a discrete periodic signal and supplies the local phase reference that makes the Hilbert interpretation meaningful.","core_discovery":"The paper's central claim is that the minimal perturbation that makes a directed graph's adjacency matrix diagonalizable and invertible also gives the graph a cycle cover, and that this cycle cover is necessary for the Hilbert transform to deliver phase information across the whole graph. The proposed graph Hilbert transform acts in the spectral domain: coefficients belonging to eigenvalues with positive imaginary part are multiplied by $-j$, those with negative imaginary part by $+j$, and real-eigenvalue coefficients are left alone, so the analytic graph signal $\\tilde{x} = x + jH(x)$ yields an instantaneous amplitude and phase at every node. On a single directed cycle the construction reduces to the traditional Hilbert transform, and on graphs whose subcycles overlap, the amplitude and phase of the combined signal follow explicit combination rules derived from the contributing cycles. The paper demonstrates the contrast on a synthetic graph with fan cycles, where a Jordan-normal-form Hilbert transform cancels the signal on the fans while the proposed transform produces the expected phase shift.","pith_inferences":["Editorial inference: if Proposition 1 holds for every directed graph, the diagonalizability obstruction to phase analysis is removed in full generality, so any directed graph can be phase-analyzed by accepting the added edges and treating the resulting cycles as the periodic structure of the signal.","Editorial inference: Corollary 1.1 implies interference at nodes shared by several cycles; a natural test the paper does not run is to place two subcycle signals with different frequencies on overlapping cycles and look for amplitude beats at their intersection.","Editorial inference: since the filter only requires conjugate eigenvalue pairs, the same $\\pm j$ construction could be transferred to other graph shift operators with complex spectra, such as a directed Laplacian or polar-decomposition-based operators, which the paper lists only as future directions."],"forward_implications":["After the minimal edge perturbation, every node lies on at least one directed cycle, so the Hilbert transform yields an instantaneous amplitude and phase at every node, not just on the diagonalizable part of the graph.","On a single directed cycle the proposed transform is exactly the classical Hilbert transform, so standard intuitions about envelopes and phase shifts carry over.","For graphs whose subcycles share nodes, Corollary 1.1 gives explicit formulas for combining per-cycle amplitudes and phases into the full graph signal's amplitude and phase.","Because instantaneous phase can be unwrapped along cycles, amplitude and frequency modulation analysis becomes available on directed graphs.","Graphs whose adjacency is already diagonalizable and invertible, such as the regular 2D grid in the experiments, need no added edges and the transform produces the expected $\\pi/2$ phase shift along the wave propagation direction."],"supporting_citations":[{"why":"Supplies the minimal edge-addition procedure that makes the adjacency matrix diagonalizable and invertible, the starting point of the paper.","marker":"[14]"},{"why":"Provides the r-acyclic theorem used in Proposition 1 to infer the cycle cover from invertibility.","marker":"[21]"},{"why":"Defines the earlier Jordan-normal-form graph Hilbert transform that the paper contrasts with its own on the synthetic graph.","marker":"[18]"},{"why":"Gives the fact that real matrices have complex-conjugate eigenvalue and eigenvector pairs, which makes the ±j filter produce real outputs.","marker":"[17]"},{"why":"Supplies the standard Hilbert transform and analytic signal background that the graph construction generalizes.","marker":"[19]"},{"why":"Provides Itoh's phase-unwrapping method used to convert instantaneous phase into instantaneous frequency in the experiments.","marker":"[23]"},{"why":"Supplies the Manhattan midtown graph used for the real-world demonstration.","marker":"[22]"}],"fun_headline_variants":["Minimal edge additions unlock phase on directed graphs via cycle covers","Cycle covers from minimal edges give every node a phase","Hilbert transform for directed graphs made practical with cycle covers","Cycle covers from minimal edge addition enable Hilbert phase on directed graphs"],"cache_read_input_tokens":10880,"weakest_assumption_plain":"The proof of Proposition 1 depends on the cited theorem that a graph is $r$-acyclic exactly when every subgraph adjacency matrix has at least $r$ zero eigenvalues, together with the interpretation that $0$-acyclic means a cycle cover exists; if that theorem uses a different definition of $r$-acyclic, the inference from invertibility to a cycle cover does not go through.","fun_headline_variants_meta":{"raw":{"variants":["Minimal edge additions unlock phase on directed graphs via cycle covers","Cycle covers from minimal edges give every node a phase","Hilbert transform for directed graphs made practical with cycle covers","Cycle covers from minimal edge addition enable Hilbert phase on directed graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000645,"raw_usage":{"total_tokens":2959,"prompt_tokens":936,"completion_tokens":2023,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":552,"completion_tokens_details":{"reasoning_tokens":1954}},"tokens_in":552,"tokens_out":2023,"duration_ms":14716,"temperature":1.0,"reasoning_tokens":1954,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T04:41:55.477523+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the edge-addition procedure on a small directed graph that has a node of zero in-degree or zero out-degree, and inspect the resulting graph: if that node is left off every directed cycle, Proposition 1 is false and the phase interpretation fails there. A concrete candidate is a directed star or a directed path with a single added edge; the claimed cycle cover must include all nodes.","supporting_citations":[{"cited_title":"Digraph Signal Processing With Generalized Boundary Conditions,","cited_arxiv_id":null,"evidence_quote":"Supplies the minimal edge-addition procedure that makes the adjacency matrix diagonalizable and invertible, the starting point of the paper."},{"cited_title":"Connections between graphs and matrix spaces,","cited_arxiv_id":null,"evidence_quote":"Provides the r-acyclic theorem used in Proposition 1 to infer the cycle cover from invertibility."},{"cited_title":"On Hilbert transform, analytic signal, and modulation analysis for signals over graphs,","cited_arxiv_id":null,"evidence_quote":"Defines the earlier Jordan-normal-form graph Hilbert transform that the paper contrasts with its own on the synthetic graph."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the fact that real matrices have complex-conjugate eigenvalue and eigenvector pairs, which makes the ±j filter produce real outputs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the standard Hilbert transform and analytic signal background that the graph construction generalizes."},{"cited_title":"Analysis of the phase unwrapping algorithm,","cited_arxiv_id":null,"evidence_quote":"Provides Itoh's phase-unwrapping method used to convert instantaneous phase into instantaneous frequency in the experiments."},{"cited_title":"Graph Fourier Transform: A Stable Approximation,","cited_arxiv_id":null,"evidence_quote":"Supplies the Manhattan midtown graph used for the real-world demonstration."}],"review_version":1}