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) .$$

It should be mentioned

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


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.

  • $\begingroup$ maybe you can think of the Fourier Transform as the number of amplitude clicks of an individual frequency where each frequency is a node. i dunno. i must confess that i do not know graph theory. $\endgroup$ – robert bristow-johnson Jun 5 '18 at 1:49
  • $\begingroup$ I was going to recommend that you read this but since then, this and this have also appeared. So, I have some reading to do myself too. Assuming you have not seen these publications, they might be helping (?) $\endgroup$ – A_A Jun 5 '18 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.