8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @BenBarber I edited my question. $\endgroup$ Jun 4, 2018 at 19:45
  • 2
    $\begingroup$ I find this question so interesting. It is better to offer a response rather to vote closing it. $\endgroup$
    – ABB
    Jun 4, 2018 at 20:14

1 Answer 1

8
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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?! $\endgroup$ Jun 6, 2018 at 22:34
  • 2
    $\begingroup$ if the graph Laplacian is different, then also its Fourier transform will be different, won't it? $\endgroup$ Jun 7, 2018 at 5:30
  • $\begingroup$ Sorry, Is there a book about Graph Structured Data Viewed Through a Fourier analysis? $\endgroup$ Oct 2, 2018 at 7:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.