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

Current Ref:

  • cards/graph/graph-convolution-operator.md