GCN can be viewed as a more complex form of message passing with additional trainable weights and non-linearities. Suppose we combine a simple graph convolution via polynomial $\mathbf{A}+\mathbf{I}$, then we can have:

$\mathbf{H}^{(k)}=\sigma(\mathbf{A} \mathbf{H}^{(k-1)} \mathbf{W}_{neigh}^{(k)} + \mathbf{H}^{(k-1)} \mathbf{W}_{self}^{k})$

We can see that a graph convolution based on $\mathbf{I}+\mathbf{A}$ is equivalent to first aggregate neighborhood information and then combining it with information of the node-self. 


Connection Between GCN And Message Passing

Suppose we have a simplified GNN: $\mathbf{H}^{(k)} = \mathbf{A}_{sym} \mathbf{H}^{(k-1)} \mathbf{W}^{(k)} = \mathbf{A}_{sym}^k \mathbf{X} \mathbf{W} $

If k is big enough such that we reach an fix point, then we’ll have $\mathbf{A}_{sym} \mathbf{H}^k = \mathbf{H}^k$. At this fixed point, all nodes will converge to be defined by the dominant eigenvector of $\mathbf{A}_{sym}$. 

So we can see that stacking many rounds of message passing leads to low-pass convolutional filter, and all nodes can  become to be identical and uninformative.

Over-Smoothing As A Low-Pass Convolutional Filter

Kipf and Welling built the GCN in their work. The idea of GCN is that the model can be powerful by stacking simple convolutional layer and using a normalized variant of adjacency matrix with self-loops.:

$\mathbf{H}^{(k)}=\sigma(\tilde{\mathbf{A}} \mathbf{H}^{(k-1)} \mathbf{W}^{(k)})$

Where $\tilde{\mathbf{A}} = (\mathbf{D}+\mathbf{I})^{-\frac{1}{2}} (\mathbf{I}+\mathbf{A}) (\mathbf{D}+\mathbf{I})^{-\frac{1}{2}}$

University of Notre Dame

There’re several types of GNN inspired by convolutions operations and their conenctions:

1)	GNN That Use Purely Convolutional Approaches

2)	Graph Convolutional Networks (GCN)

3)	GNN Without Message Passing


Convolution-Inspired GNNs

Hamilton, W.L. Graph Representation Learning. *Synthesis Lectures on Artificial Intelligence and Machine Learning*. 2020, 14(3), 1–159. https://doi.org/10.2200/S01045ED1V01Y202009AIM046

Graph Representation Learning by William Hamilton

Some early work of GNN rely solely on convolution operations. The idea of this class of GNN is to define full model as a combination or stacking of multiple convolution layers and nonlinearities. For example, Defferrard et al. defined convolutions based on a spectral convolution based on the eigenvalues of the Laplacian, and defined the spectral filter using Chebyshev polynomials. 

GNN That Use Purely Convolutional Approaches

Graph Convolutional Networks (GCN) 

Several recent GNN model proposed that we can remove the message passing to simplfy the GNN, and these models can be generally defined as:

$\mathbf{Z} = MLP_{\theta}(f(\mathbf{A}) MLP_{\phi}(\mathbf{X}) )$

Where $MLP$ denote dense neural network, $f$ is some deterministic function. For example, Wu define $f$ as:

$f(\mathbf{A}) = \tilde{\mathbf{A}}^k$

The intuition is that we don’t have to involve trainable parameters in convolution layer. Rather, we can apply a dense layer at the start and end of layers, and use a deterministic convolutional layer in the middle to use graph structure. And it has been prove to outperform parameterized message passing models on many classification benchmarks.


Learn Before

Related

Learn After