How do convolutional layers of basic Graph Convolutional Networks work?

I was reading the following article on Towards Data Science (here) and it says the following, regarding the calculation of convolutional layers:

So the overall steps are:

1. Transform the graph into the spectral domain using eigendecomposition
2. Apply eigendecomposition to the specified kernel
3. Multiply the spectral graph and spectral kernel (like vanilla convolutions)
4. Return results in the original spatial domain (analogous to inverse GFT)

Question: How can we visualize the convolutional layer working for a graph neural network?

For example, for a CNN we can imagine the following (source: Stanford CS231n YouTube lectures, Lecture 5: Convolutional Neural Networks (here)). What is the analogous image for a graph convolutional filter?

• Note that there are several graph neural networks and, from what I remember when I was studying them, they can be quite different, so it may not be possible to give an explanation that applies to all GNNs. Moreover, it seems to me that now you changed the question to ask for a diagram that illustrates how the convolutional layer for some specific GNN works. If that's the case, you may also want to change the title to reflect that.
– nbro
Sep 18 '21 at 14:15
• Thanks @nbro, I'll make the updates in the morning. Do you have any links to resources you used when you were studying the topic? Sep 19 '21 at 1:32
• I didn't study geometric deep learning or graph neural networks thoroughly. I had read a few papers and articles online, so my knowledge of the topic is not very solid, so I don't really have one resource that I would recommend. Back then (i.e. about 2-3 years ago), there weren't many good resources on this topic. Maybe this answer is useful. Don't forget to upvote the question and answer there if you find them useful ;). In any case, it seems to me you're already aware of this book.
– nbro
Sep 19 '21 at 23:53
• Many thanks @nbro! Appreciate the help Sep 20 '21 at 2:48

Actually, the given pipeline was used in the old days of Graph Neural Networks.

Canonical paper on the subject is Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering.

You start from arbitrary graph with adjacency matrix $$A_{ij}$$ (let us assume that graph is undirected), such that: $$A_{ij} = \begin{cases} 1 & \text{if there and edge between vertices i and j} \\ 0 & \text{otherwise} \end{cases}$$

Then one constructs graph Laplacian: $$L = D-A$$ $$D$$ is the degree matrix (number of edges entering the given vertex). There are also different normalizations in the literature, like $$I - D^{-1/2} A D^{-1/2}$$ is called normalized Laplacian.

This matrix has several properties:

• It is symmetric
• Non-negative definite

From the first statement it follows, that the matrix can be diagonalized due to the Spectral theorem,

Therefore, it makes sense to perform the eigendecomposition of this operator. And the eigenvectors form the graph Fourier basis.

Note, that in the special case, when the graph is a regular square grid, graph Laplacian just the discrete Laplace operator: $$\begin{pmatrix} 0 & -1 & 0 \\ -1 & 4 & -1 \\ 0 & -1 & 0 \\ \end{pmatrix} \qquad (\text{for 2d case})$$ And the Fourier basis consists of plane waves: $$\sim e^{i (k_i i + k_j j)}$$

The next important fact is the Convolution theorem that states that convolution of two signals can be done as inverse Fourier transform of the dot product of their Fourier transforms: $$f * g = \mathcal{F}^{-1} [\mathcal{F}[f] \cdot \mathcal{F}[g]]$$

These operations correspond to steps 3 and 4 in the pipeline in the OP.

I am not aware of the simple geometrical intuition in this setting. But in the following research, full eigendecomposition was truncated to Chebyshev polynomials, and then up to the first term in the decomposition, which gave rise to Graph Convolutional Networks by T.Kipf.

They allow for more intuitive and visual interpretation. Given adjacency matrix $$A$$, input feature map on the graph $$H^{(l)}$$ one defines the output of the layer to be: $$f(H^{(l)}, A) = \sigma(\tilde{D}^{-1/2} A \tilde{D}^{-1/2} H^{(l)} W^{(l)})$$ $$\tilde{D}$$ is the graph Laplacian for adjacency matrix with self-loops (arrows $$i \rightarrow i$$). $$W^{(l)}$$ is the matrix of learnable parameters.

In essence, one transforms the feature vectors $$H^{(l)}$$ by a pointwise linear transformation, and aggregates the information from the neighborhood with some coefficients. Equivalently the function above can be rewritten as;

$$H_{i}^{l+1}=\eta\left(\frac{1}{\hat{d}_{i}} \sum_{j \in N_{i}} \hat{\boldsymbol{A}}_{i j}{W}^{l} H_{j}^{l}\right)$$

From the formula above one can see, that graph convolution is the summation of the features in the neighborhood vertices which are transformed by the weight matrix $${W}^{l}$$ and division by the normalizing constant.

• You may also explain or at least link to some other external resource that motivates your claim "it makes sense to perform the eigendecomposition of this operator" (i.e. the normalized Laplacian). In other words, why if a matrix is symmetric and non-negative semi-definitive, then we can find the eigendecomposition? What also does "graph Fourier basis" mean? Why do we care about this basis? And why does the eigenvectors of the normalised Laplacian form this basis?
– nbro
Nov 28 '21 at 20:58
• You don't need to explain this completely in your answer, but it may be a good idea to link to an external resource that explains this for people not familiar with these concepts. Finally, to make this a better answer, I would also explain the relationship between your diagram and the last sentence. For people that are more or less familiar with GNNs, that last sentence makes sense, but it may not be clear how it is related to the diagram.
– nbro
Nov 28 '21 at 21:00