How can we derive a Convolution Neural Network from a more generic Graph Neural Network?

Question

Convolution Neural Network (CNNs) operate over strict grid-like structures ($M \times N \times C$ images), whereas Graph Neural Networks (GNNs) can operate over all-flexible graphs, with an undefined number of neighbors and edges.

On the face of it, GNNs appear to be neural architectures that can subsume CNNs. Are GNNs really generalized architectures that can operate arbitrary functions over arbitrary graph structures?

An obvious follow-up - How can we derive a CNN out of a GNN?

Since non-spectral GNNs are based on message-passing that employ permutation-invariant functions, is it possible to derive a CNN from a base-architecture of GNN?

Answer 1

Yes, a CNN can be formalized as a specific kind of GNN where nodes are connected together in a 2D lattice structure and the outer edge is padded with zeros. Down-sampling techniques or pooling layers are an additional operation which remove edge nodes or low activation nodes. Convolutional layers act in the same manner as GNN weights by comparing each node with it's neighbors.

Yes, GNNs are generalized architectures of CNNs. A CNN is derivable by treating the image as a lattice graph and augmenting pooling and/or down-sampling layers. N w x w convolutional kernels has a node with feature of length N interacting with a w-hop neighborhood. Any node of distance w is considered adjacent.

I am an expert on convolutional networks and not graph neural networks. Maybe these two articles would also be helpful. https://towardsdatascience.com/understanding-graph-convolutional-networks-for-node-classification-a2bfdb7aba7b?gi=4c06cb6c8e30

https://medium.com/@rmwkwok/gnn-notes-series-explain-graph-convolutional-networks-gcn-with-knowledge-in-cnn-b827be1c872b

My goal in writing this was to provide a more novice accessible answer than the others on this post.

Answer 2

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.