# Question about eigenvectors of Laplacian matrix in relation to graph Fourier transform?

(I have copied this question from my post on maths stack exchange as I don't think it was getting much/any traction there)

I am reading the following book/notes on Graph Representation Learning (here) and have a number of questions from Chapter 7.

Context: In section 7.1.3 of the notes, we have the following bit of the notes.

I understand:

• the Laplacian can be thought of as a measure of locality between nodes in a graph network.
• how we figure out that the eigenfunctions (of the Laplacian matrix) correspond to the complex exponential function $$- \Delta (e^{2\pi ist})= - \frac{\partial^2 (e^{2\pi ist})}{\partial t^2} = (2\pi s)^2 \cdot e^{2\pi ist}$$

Question:

1. What is an intuitive way of thinking about the graph Fourier transform? Should I basically be thinking about how much/how quickly the signal varies when moving across the graph? For example, it I think of the nodes each having some sort of signal value, which can be plotted as an elevation, should I think about how much that elevation zig-zags up and down from node-to-node. A lot of variation would suggest higher frequencies, and less variation would suggest lower frequencies.

2. Where do these eigenvectors come from and what is the intuition between the different terms in there? The book has the following block of text and I don't understand intuition of different entries in eigenvector beyond them just being different frequencies to resolve signal onto.

so the eigenfunctions of $$\Delta$$ are the same complex exponentials that make up the modes of the frequency domain in the Fourier transform (i.e., the sinusoidal plane waves), with the corresponding eigenvalue indicating the frequency. In fact, one can even verify that the eigenvectors $$\mathbf{u_1} , ..., \mathbf{u_n}$$ of the circulant Laplacian $$\mathbf{L_c} ∈ R^{n×n}$$ for the chain graph are $$\mathbf{u_j} = \frac{1}{\sqrt n} [1, \omega_j , \omega_j ^2 , ..., \omega_j ^n ]$$ where $$\omega_j = e^{\frac{2πj}{n}}$$

Thanks.

• It seems that you're asking here 2 distinct questions (although they may be related) So, could you please split this post into $n$ post, one for each of your $n$ questions?
– nbro
Dec 17, 2021 at 14:46