Graph Convolution Operator
#Graph #Convolution
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. $$
Graph Adjacency Matrix
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}. $$
L Ma (2021). 'Graph Convolution Operator', Datumorphism, 11 April. Available at: https://datumorphism.leima.is/cards/graph/graphconvolutionoperator/.
Table of Contents
Current Ref:

cards/graph/graphconvolutionoperator.md
Links to:
What is Graph
Graph A graph $\mathcal G$ has nodes $\mathcal V$ and edges $\mathcal E$, $$ \mathcal G = ( \mathcal …
Graph Adjacency Matrix
A graph $\mathcal G$ can be represented with an adjacency matrix $\mathbf A$. There are some nice …
Convolutions Using Fourier Transform
Convolution and Fourier transform
Graph Laplacians
Laplacian is a useful representation of graphs. The unnormalized Laplacian is $$ \mathbf L = \mathbf …