One critical aspect of the convolution operation is that it can be computed by
an element-wise product of the Fourier transforms of the two functions:

Fourier Transform of the Convolution Operation

We can represent a convolution by a filter $h$ as matrix multiplication on the vector **f**:

$(f \star h)(t) = \sum_{\tau=0}^{N-1} f(\tau)h(\tau - t)$

= $Q_hf$

where $Q_h \in \mathbb{R}^{N*N}$  is a matrix representation of the convolution operator by a filter function $h$ and **f** = $\mathbf{[f(t_0),f(t_2),...,f(t_{N-1}]}^\top$ is a vector representation of the function $f$

Representing convolutions with matrix multiplications

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.


Carleton College

Hamilton College

 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

 The General Continuous Convolution Operation

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


Learn Before

Related

Learn After