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. 

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

GNN That Use Purely Convolutional Approaches

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}}$

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