Graph Convolution Operator

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 [[adjacency matrix]] Graph Adjacency Matrix 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 $\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. $$

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

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