Harmonic analysis on directed graphs and applications: from Fourier analysis to wavelets
This provides tools for analyzing data on directed graphs, which is incremental relative to existing undirected graph methods.
The authors developed a harmonic analysis framework for functions on strongly connected directed graphs using the random walk operator as a Fourier-type basis, enabling multi-scale wavelet transforms. They demonstrated applications in semi-supervised learning and signal modeling on directed graphs, showing the framework's efficiency.
We introduce a novel harmonic analysis for functions defined on the vertices of a strongly connected directed graph of which the random walk operator is the cornerstone. As a first step, we consider the set of eigenvectors of the random walk operator as a non-orthogonal Fourier-type basis for functions over directed graphs. We found a frequency interpretation by linking the variation of the eigenvectors of the random walk operator obtained from their Dirichlet energy to the real part of their associated eigenvalues. From this Fourier basis, we can proceed further and build multi-scale analyses on directed graphs. We propose both a redundant wavelet transform and a decimated wavelet transform by extending the diffusion wavelets framework by Coifman and Maggioni for directed graphs. The development of our harmonic analysis on directed graphs thus leads us to consider both semi-supervised learning problems and signal modeling problems on graphs applied to directed graphs highlighting the efficiency of our framework.