REVIEW 2 major objections 5 minor 32 references
Hilbert Transform on Graphs: Let There Be Phase
T0 review · 2 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict Useful graph-Hilbert-transform method with a fixable proof gap in its cycle-cover proposition; worth engaging after a revision. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (2)
- [III-C, Proposition 1] 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.
- [III-C, Corollary 1.1] 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.
minor comments (5)
- [IV-A.1] 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.
- [IV-B.1] "Removing the non-trivial Jordan blocks" is inaccurate as a description of the algorithm, which adds edges to dismantle Jordan blocks; please rephrase.
- [Eq. (3)] 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].
- [Throughout] 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.
- [Fig. 2] 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.
Circularity Check
Minimal circularity: the GHT is an explicit definition whose single-cycle equivalence holds by construction; the cycle-cover theorem rests on an external result rather than on the paper's own claims.
-
self definitional
[Section III-B, Eq. (1); Section III-C first paragraph; Abstract]
"We introduce the GHT by defining the following filter in the spectral domain by the diagonal matrix \hat{H}: \hat{H}[k,k] = -j if imag(\lambda_k) > 0, +j if imag(\lambda_k) < 0, 0 if imag(\lambda_k) = 0. (1) In traditional signal processing, the Hilbert transform of a signal provides the magnitude of its envelope and phase of its oscillatory pattern."
Equation (1) is exactly the classical Hilbert transfer function -j sgn(imag(\lambda)) applied eigenvalue-wise. On a directed cycle, the adjacency eigenvalues are the DFT roots of unity, so the sign of imag(\lambda_k) coincides with the sign of the discrete frequency; therefore the paper's statement that the proposed GHT is 'equivalent to the generalized Hilbert Transform on a single cycle' is true by construction of the filter, not by an independent derivation. This is a mild self-definitional consistency, not a fitted-parameter or self-citation problem, because the paper explicitly says 'we introduce the GHT by defining' and the cycle-cover claim does not depend on this definition.
full rationale
The main theoretical step, Proposition 1, is not circular: it derives the existence of a cycle cover from invertibility of the perturbed adjacency via the external theorem [21, Th. 4.4]. The GHT itself is introduced as a definition rather than fitted to data, and the experiments use hand-constructed ground-truth signals to verify that the definition recovers the expected phase and amplitude behavior; no parameter is fitted and then renamed a prediction. The only mild construction-dependent point is that matching the classical Hilbert transform on a single directed cycle is built into the filter. The only self-citation, [25] in the discussion of monogenic signals, is not load-bearing. Two non-circular correctness and verifiability concerns should be noted separately: (i) the proof of Proposition 1 as printed appears invalid because '0-acyclic' under the paper's stated definition ('any collection of vertex-disjoint cycles covers at most N nodes') is trivially true for every graph, so the inference from the contradiction to the existence of a cycle cover requires [21]'s exact definition or a direct determinant argument; and (ii) the proof of Corollary 1.1 is deferred to supplementary material not included in the arXiv version. These issues affect rigorous verifiability but do not make the derivation circular.
Assumptions & free parameters
assumptions (4)
- standard math Theorem 1 from [21]: a graph is r-acyclic iff every subgraph adjacency matrix in S_G has at least r zero eigenvalues; used in the proof of Proposition 1.
- domain assumption The perturbation framework of Seifert and Puschel [14] guarantees a minimal edge addition yielding an adjacency matrix A' that is both diagonalizable and invertible.
- standard math A real matrix has eigenvalues that are real or in complex conjugate pairs with corresponding conjugate eigenvectors (Horn and Johnson [17]).
- ad hoc to paper The graph Hilbert transform is defined by the spectral filter in Eq. (1), assigning -j, +j, or 0 based on the sign of the imaginary part of the adjacency eigenvalue.
Cite this review
Pith. "Pith review of Hilbert Transform on Graphs: Let There Be Phase." pith.science (2026). https://pith.science/paper/FFICCWLS
@misc{pith2026241218501,
author = {Pith},
title = {Pith review of: Hilbert Transform on Graphs: Let There Be Phase},
year = {2026},
howpublished = {\url{https://pith.science/paper/FFICCWLS}},
note = {Machine review of arXiv:2412.18501}
}
read the original abstract
In the past years, many signal processing operations have been successfully adapted to the graph setting. One elegant and effective approach is to exploit the eigendecomposition of a graph shift operator (GSO), such as the adjacency or Laplacian operator, to define a graph Fourier transform when projecting graph signals on the corresponding basis. However, the extension of this scheme to directed graphs is challenging since the associated GSO is non-symmetric and, in general, not diagonalizable. Here, we build upon a recent framework that adds a minimal number of edges to allow diagonalization of the GSO and thus provide a proper graph Fourier transform. Furthermore, we show that such minimal addition of edges creates a cycle cover and that it is essential for the phase analysis of a signal throughout the graph. Concurrently, we propose a generalization of the Hilbert transform interpreted over the newfound cycle cover, which re-establishes intuitions from traditional Hilbert Transform, equivalent to the generalized Hilbert Transform on a single cycle. This generalization leads to a number of simple and elegant recipes to effectively exploit the phase information of graph signals provided by the graph Fourier transform. The feasibility of the approach is demonstrated on several examples.
Figures
Reference graph
Works this paper leans on
-
[21]
Connections between graphs and matrix spaces,
Y . Li, Y . Qiao, A. Wigderson, Y . Wigderson, and C. Zhang, “Connections between graphs and matrix spaces,” Israel Journal of Mathematics , vol. 256, pp. 513–580, Sept. 2023
work page 2023
-
[1]
D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Van- dergheynst, “The emerging field of signal processing on graphs: Ex- tending high-dimensional data analysis to networks and other irregular domains,” IEEE Signal Processing Magazine , vol. 30, pp. 83–98, May 2013
work page 2013
-
[2]
Graph Signal Processing: Overview, Challenges, and Ap- plications,
A. Ortega, P. Frossard, J. Kova ˇcevi´c, J. M. F. Moura, and P. Van- dergheynst, “Graph Signal Processing: Overview, Challenges, and Ap- plications,” Proceedings of the IEEE , vol. 106, pp. 808–828, May 2018
work page 2018
-
[3]
A. G. Marques, S. Segarra, and G. Mateos, “Signal Processing on Directed Graphs: The Role of Edge Directionality When Processing and Learning From Network Data,” IEEE Signal Processing Magazine , vol. 37, pp. 99–116, Nov. 2020
work page 2020
-
[4]
Discrete Signal Processing on Graphs,
A. Sandryhaila and J. M. F. Moura, “Discrete Signal Processing on Graphs,” IEEE Transactions on Signal Processing , vol. 61, pp. 1644– 1656, Apr. 2013
work page 2013
-
[5]
A. Sandryhaila and J. M. Moura, “Big Data Analysis with Signal Processing on Graphs: Representation and processing of massive data sets with irregular structure,” IEEE Signal Processing Magazine, vol. 31, pp. 80–90, Sept. 2014
work page 2014
-
[6]
Signal denoising on graphs via graph filtering,
S. Chen, A. Sandryhaila, J. M. F. Moura, and J. Kovacevic, “Signal denoising on graphs via graph filtering,” in 2014 IEEE Global Confer- ence on Signal and Information Processing (GlobalSIP) , (Atlanta, GA, USA), pp. 872–876, IEEE, Dec. 2014
work page 2014
-
[7]
Infinite Impulse Response Graph Filters in Wireless Sensor Networks,
Xuesong Shi, Hui Feng, Muyuan Zhai, Tao Yang, and Bo Hu, “Infinite Impulse Response Graph Filters in Wireless Sensor Networks,” IEEE Signal Processing Letters , vol. 22, pp. 1113–1117, Aug. 2015
work page 2015
Show all 32 references
-
[8]
Discrete Signal Processing on Graphs: Frequency Analysis,
A. Sandryhaila and J. M. F. Moura, “Discrete Signal Processing on Graphs: Frequency Analysis,” IEEE Transactions on Signal Processing , vol. 62, pp. 3042–3054, June 2014
2014
-
[9]
Computational aspects of the Jordan canonical form,
T. Beelen and P. V . Dooren, “Computational aspects of the Jordan canonical form,” in Reliable Numerical Commputation (M. G. Cox and S. Hammarling, eds.), pp. 57–72, Oxford University PressOxford, Sept. 1990
1990
-
[10]
Graph Signal Processing: Modulation, Convolution, and Sampling,
J. Shi and J. M. F. Moura, “Graph Signal Processing: Modulation, Convolution, and Sampling,” Dec. 2019. arXiv:1912.06762 [eess]
2019 arXiv
-
[11]
Graph Fourier Trans- form for directed graphs based on Lov ´asz extension of min-cut,
S. Sardellitti, S. Barbarossa, and P. Di Lorenzo, “Graph Fourier Trans- form for directed graphs based on Lov ´asz extension of min-cut,” in 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), (New Orleans, LA), pp. 3894–3898, IEEE, Mar. 2017
2017
-
[12]
A Directed Graph Fourier Transform With Spread Frequency Components,
R. Shafipour, A. Khodabakhsh, G. Mateos, and E. Nikolova, “A Directed Graph Fourier Transform With Spread Frequency Components,” IEEE Transactions on Signal Processing , vol. 67, pp. 946–960, Feb. 2019
2019
-
[13]
Graph Signal Processing for Directed Graphs Based on the Hermitian Lapla- cian,
S. Furutani, T. Shibahara, M. Akiyama, K. Hato, and M. Aida, “Graph Signal Processing for Directed Graphs Based on the Hermitian Lapla- cian,” in Machine Learning and Knowledge Discovery in Databases (U. Brefeld, E. Fromont, A. Hotho, A. Knobbe, M. Maathuis, and C. Ro- bardet,...
2020
-
[14]
Digraph Signal Processing With Generalized Boundary Conditions,
B. Seifert and M. Puschel, “Digraph Signal Processing With Generalized Boundary Conditions,” IEEE Transactions on Signal Processing, vol. 69, pp. 1422–1437, 2021
2021
-
[15]
Low Rank Perturbation of Jordan Structure,
J. Moro and F. M. Dopico, “Low Rank Perturbation of Jordan Structure,” SIAM Journal on Matrix Analysis and Applications , vol. 25, pp. 495– 506, Jan. 2003
2003
-
[16]
On the Change in the Spectral Properties of a Matrix under Perturbations of Sufficiently Low Rank,
S. V . Savchenko, “On the Change in the Spectral Properties of a Matrix under Perturbations of Sufficiently Low Rank,” Functional Analysis and Its Applications , vol. 38, pp. 69–71, Jan. 2004
2004
-
[17]
R. A. Horn and C. R. Johnson, Matrix Analysis . Cambridge University Press, 1 ed., Dec. 1985
1985
-
[18]
On Hilbert transform, analytic signal, and modulation analysis for signals over graphs,
A. Venkitaraman, S. Chatterjee, and P. H ¨andel, “On Hilbert transform, analytic signal, and modulation analysis for signals over graphs,” Signal Processing, vol. 156, pp. 106–115, Mar. 2019
2019
-
[19]
S. L. Hahn, Hilbert transforms in signal processing. Artech House signal processing library, Boston: Artech House, 1996
1996
-
[20]
J. G. Proakis and M. Salehi, Digital communications . Boston, Mass.: McGraw-Hill, 5. ed ed., 2008
2008
-
[22]
Graph Fourier Transform: A Stable Approximation,
J. Domingos and J. M. F. Moura, “Graph Fourier Transform: A Stable Approximation,” IEEE Transactions on Signal Processing , vol. 68, pp. 4422–4437, 2020
2020
-
[23]
Analysis of the phase unwrapping algorithm,
K. Itoh, “Analysis of the phase unwrapping algorithm,” Applied Optics, vol. 21, p. 2470, July 1982
1982
-
[24]
The monogenic signal,
M. Felsberg and G. Sommer, “The monogenic signal,” IEEE Transac- tions on Signal Processing , vol. 49, pp. 3136–3144, Dec. 2001
2001
-
[25]
The monogenic Riesz- Laplace wavelet transform,
M. Unser, K. Balac, and D. V . D. Ville, “The monogenic Riesz- Laplace wavelet transform,” in 2008 16th European Signal Processing Conference (EUSIPCO), (Lausanne, Switzerland), IEEE, 2008
2008
-
[26]
A. V . Oppenheim, A. S. Willsky, and S. H. Nawab, Signals & systems . Prentice-Hall signal processing series, Upper Saddle River, N.J: Prentice Hall, 2nd ed ed., 1997
1997
-
[27]
Graph Fourier transform based on directed Laplacian,
R. Singh, A. Chakraborty, and B. S. Manoj, “Graph Fourier transform based on directed Laplacian,” in 2016 International Conference on Signal Processing and Communications (SPCOM) , (Bangalore, India), pp. 1–5, IEEE, June 2016
2016
-
[28]
Frequency Analysis and Filter Design for Directed Graphs with Polar Decomposition,
S. Kwak, L. Shimabukuro, and A. Ortega, “Frequency Analysis and Filter Design for Directed Graphs with Polar Decomposition,” inICASSP 2024 - 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , (Seoul, Korea, Republic of), pp. 9661– 9665, IE...
2024
-
[29]
Joint Sampling and Reconstruction of Time-Varying Signals Over Directed Graphs,
Z. Xiao, H. Fang, S. Tomasin, G. Mateos, and X. Wang, “Joint Sampling and Reconstruction of Time-Varying Signals Over Directed Graphs,” IEEE Transactions on Signal Processing , vol. 71, pp. 2204–2219, 2023
2023
-
[30]
Complex seismic trace analysis,
M. T. Taner, F. Koehler, and R. E. Sheriff, “Complex seismic trace analysis,” GEOPHYSICS, vol. 44, pp. 1041–1063, June 1979
1979
-
[31]
Fourier-, Hilbert- and wavelet-based signal analysis: are they really different approaches?,
A. Bruns, “Fourier-, Hilbert- and wavelet-based signal analysis: are they really different approaches?,” Journal of Neuroscience Methods , vol. 137, pp. 321–332, Aug. 2004
2004
-
[32]
Comparison of Hilbert transform and wavelet methods for the analysis of neuronal synchrony,
M. Le Van Quyen, J. Foucher, J.-P. Lachaux, E. Rodriguez, A. Lutz, J. Martinerie, and F. J. Varela, “Comparison of Hilbert transform and wavelet methods for the analysis of neuronal synchrony,” Journal of Neuroscience Methods, vol. 111, pp. 83–98, Sept. 2001
2001
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.