For a given graph $\mathcal G$, we have an attribute on each node, denoted as $f_v$. All the node attributes put together can be written as a list $\mathbf f\to (f_{v_1}, f_{v_2}, \cdots, f_{v_N})$.

Convolution on graph is combining attributes on nodes with their neighbors'. The $\mathbf A$ applied on all node attributes $\mathbf f$ is such an operation, i.e,

$$\mathbf A \mathbf f,$$

as it combines all the neighbors of each node. To include the node attribute itself, we can perform

$$(\mathbf I + \mathbf A) \mathbf f.$$

A graph $\mathcal G$ can be represented with an adjacency matrix $\mathbf A$. There are some nice and clear examples on wikipedia1, for example, $$\begin{pmatrix} 2 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}$$ for the graph Public Domain, Link

We could include higher orders too. In general, a graph convolution $\mathbf Q$ can be a polynomial of $\mathbf A$, i.e.,

$$\mathbf Q = \sum_{i=0}^{N} \alpha_i \mathbf A^i.$$

Commutation Relations

The above definition of convolution commutes with the adjacency matrix,

$$\left[ \mathbf Q, \mathbf A \right] = 0.$$

However, the commutation relation with the Laplacian $\mathbf L$ is not 0 in general, i.e.,

$$\left[ \mathbf Q, \mathbf L \right] \neq 0.$$

However, we can make both commutation relations 0 using symmetric normalized adjacency matrix $\mathbf A_{s} = \mathbf D^{-1/2}\mathbf A \mathbf D^{-1/2}$ and symmetric normalized Laplacian $\mathbf L_{s}=\mathbf D^{-1/2}\mathbf L \mathbf D^{-1/2}=\mathbf I - \mathbf A_{s}$.

Laplacian, Fourier Transform, and Graph Convolution

Using the relation between convolution and Fourier transform, as well as the relation between graph Laplacian and Fourier transform, we can establish the following relation.

$$\mathbf f * \mathbf h = \mathbf U ( \mathbf U^{\mathrm T} \mathbf f \circ \mathbf U^{\mathrm T} \mathbf h ),$$

where $\mathbf U$ are the eigenvectors,

$$\mathbf L = \mathbf U \mathbf \lambda \mathbf U^{\mathrm T}.$$

Graph Fourier Transform

$\mathbf U^{\mathrm T} \mathbf f$ is the graph Fourier transform.

Published: by ;

L Ma (2021). 'Graph Convolution Operator', Datumorphism, 11 April. Available at: https://datumorphism.leima.is/cards/graph/graph-convolution-operator/.