Hilbert Transform on Graphs: Let There Be Phase

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.