I have read this article
https://arxiv.org/abs/1307.5708
about vertix-frequency analysis on graph.
David IShuman
in this article claims that,"we generalize one of the most important signal processing tools – windowed Fourier analysis – to the graph setting and When we apply this transform to a signal with frequency components that vary along a path graph, the resulting spectrogram matches our intuition from classical discrete-time signal processing. Yet, our construction is fully generalized and can be applied to analyze signals on any undirected, connected, weighted graph."
What's the intuition behind a ''Graph fourier transform'' ? I'm not so much interested in mathematical details or technical applications. I'm trying to grasp what a graph fourier transform actually represents,and what aspects of a graph it makes accessible.
To clarify the issue:
Graph-structured data appears in many modern applications like social networks, sensor networks,
transportation networks and computer graphics. These applications are defined by an underlying
graph (e.g. a social graph) with associated nodal attributes (e.g. number of ad-clicks by an individual).
A simple model for such data is that of a graph signal—a function mapping every node to a scalar real value
The classical Fourier transform is the expansion of a function fin terms of the eigenfunctions of the Laplace operator; i.e.,
$$ \hat{f} = \langle f, e^{2\pi i \xi t } \rangle$$
Analogously, the graph Fourier transform $\hat{f}$ a function $f \in \mathbb{R}^{N}$ the vertices of graph $G$ the expansion of $f$ in terms of the eigenfunctions of the graph Laplacian. It is defined by
$$\hat{f}( \lambda_{l}) = \langle f , \chi_{l}\rangle = \sum_{n=1}^{N} f(n) \chi_{l}^* (n) .$$
I am looking for some simple concrete examples of the ways in which real problems go through graph signal processing and how graph Fourier transforms are obtained.
Best Answer
• A concrete example of a graph Fourier transform, to the Minnesota road network, is presented in Fourier Analysis on Graphs; another example, to genetic profiling for cancer subtype classification, is discussed in Graph SP: Fundamentals and Applications.
The graph Fourier transform allows one to introduce the notion of a "band width" to a graph. By analogy with smooth time signals, which have a narrow frequency band width, a graph that exhibits clustering properties (signals vary little within clusters of highly interconnected nodes) will have a narrow band width in the graph Fourier transform. Such a clustered graph would be sparse in the frequency domain, allowing for a more efficient representation of the data.
• To obtain the graph Fourier transform you could use the Matlab routine GSP_GFT in the Graph Signal Processing Toolbox.