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

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.


GNN Without Message Passing

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


University of Notre Dame

 In this perspective, where GNNs were developed as a generalization of Euclidean convolutions to the non-Euclidean graph domain, they first arise from the question: How can we generalize the notion of convolutions to general graph-structured data?

GNN and Graph Convolutions

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

Given a discrete time-varying signal $f(t_0),f(t_2),...,f(t_{N−1})$, we can represent this signal as a chain (or cycle) graph. Each node in the graph represents a point in time $t$ and the signal value at that node represents the function value $f(t)$

Representing discrete time-varying signals with a graph

In order to generalize the notion of a convolution to graphs, we first must define
what we wish to generalize and provide some brief background details. We can define the general continuous convolution operation * shown below, let f and h be two functions.


Learn Before

Related

Learn After