How can we derive a Convolution Neural Network from a more generic Graph Neural Network?
Spectral Graph Convolution
We use the Convolution Theorem to define convolution for graphs. The Convolution Theorem states that the Fourier transform of the convolution of two functions is the pointwise product of their Fourier transforms:
$$\mathcal{F}(w*h) = \mathcal{F}(w) \odot \mathcal{F}(h) \tag{1}\label{1} $$
$$ w * h = \mathcal{F}^{-1}(\mathcal{F}(w)\odot\mathcal{F}(h))  \tag{2}\label{2}$$
Here $w$ is the filter in spatial domain(time domain) and $h$ is the signal in spatial domain(time domain). For images this signal $h$ is a $2D$ matrix and for other cases this $h$ can be a $1D$ signal.
Assume we have $n$ number of node in a graph. In graph fourier transform the eigenvalues carry the notion of frequency. $\Lambda$ is the $ n \times n$ egenvalue matrix and it is a diagonal matrix. We can write equation 2 as:
$$w * h = \phi(\phi^{T}w \odot \phi^{T}h) = \phi\hat{w}(\Lambda)\phi^{T}h \tag{3}$$
Here $\phi$ is the eigenvector matrix of graph Laplacian $\in R^{n \times n}$,
$\hat{w}(\Lambda)$ is the filter in spectral domain(frequency domain) $\in R^{n \times n}$ a diagonal matrix, $h$ is the $1D$ graph signal $\in R^{n}$ in spatial domain and w is the filter in spatial domain $\in R^{n}$.
Vanilla Spectral GCN
We define the spatial convolutional layer such that given layer $h^{l}$ , the activation of the next layer is:
$$h^{l+1}=\sigma(w^l*h^l)  \tag{4}\label{4},$$
where $\sigma$ represents a nonlinear activation and $w^l$ is a spatial filter and $h$ is the graph signal.
We can perform the above equation in terms of spectral graph convolution operation as:
$$h^{l+1}=\sigma(\hat{w}^l*\hat{h}^l)  \tag{5}\label{5},$$
where $\hat{w}$ is the same filter but in the spectral domain(frequency domain). In case of vanilla GCN this equation yeild to:
$$ h^{l+1} = \sigma(\phi\hat{w}^{l}(\Lambda)\phi^{T}h)  \tag{6}\label{6}$$
Now, we will learn the $\hat{w}$ using backpropagation.
This vanilla GCN has several limitations, like larger time complexity and this does not guarantee localization in the spatial domain that we get from CNN's filter.
In next works, such as SplineGCNs, ChebNet, Klipf and Welling's GCN, and many other works address those issues, and try to solve them.
Note that we can think of ChebNet and Klipf and Welling's GCN as a message-passing system, but, in the background, they are computing spectral convolution and also they use some standard assumption that's why we do not need any eigenvector and we implement them in the spatial domain, but still they are spectral convolution.
There is also another branch in graph convolution called spatial graph convolution. I only talked about the spectral graph convolution.