# graph signal processing

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.

• @BenBarber I edited my question. – niloofar jamshidi Jun 4 '18 at 19:45
• I find this question so interesting. It is better to offer a response rather to vote closing it. – Ali Bagheri Jun 4 '18 at 20:14

"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."

• 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.

• According to your answer, if we consider the graph and a number of signals on this graph, While these signals are obviously different,but their spectral representations on this graph are the same! Is it true?! – niloofar jamshidi Jun 6 '18 at 22:34
• if the graph Laplacian is different, then also its Fourier transform will be different, won't it? – Carlo Beenakker Jun 7 '18 at 5:30
• Sorry, Is there a book about Graph Structured Data Viewed Through a Fourier analysis? – niloofar jamshidi Oct 2 '18 at 7:32