Graph Laplacians

#Graph #Heterophily

Laplacian is a useful representation of graphs. The unnormalized Laplacian is

$$ \mathbf L = \mathbf D - \mathbf A, $$

where $\mathbf A$ is 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 and $\mathbf D$ is the degree matrix, i.e., a diagonalized matrix with the diagonal elements being the degrees.

Normalized Laplacian

The symmetric normalized Laplacian is

$$ \mathbf L_{\text{sym}} = \mathbf D^{-1/2} \mathbf A \mathbf D^{-1/2}. $$

The random walk Laplacian is

$$ \mathbf L_{\text{RW}} = \mathbf D^{-1} \mathbf A. $$

Diagonalizing Graph Laplacian

The eigenvectors of Graph Laplacian can be used to diagonalize the graph Laplacian $\mathbf L$,

$$ \begin{equation} \mathbf U \mathbf L_D \mathbf U^{\mathrm T} = \mathbf L.\label{eq-laplacian-diag} \end{equation} $$

Laplacians and Fourier Transform

Laplacian and Fourier Transform

The eigen-equation of Laplacian $\nabla^2$ shows that the eigenvectors of the Laplacian (in Hilbert space) have the form $e^{2\pi i \xi x}$. On the other hand, $e^{2\pi i \xi x}$ is also the Fourier basis.

The eigenvectors of the graph Laplacian (Eq. $\eqref{eq-laplacian-diag}$) can be used to perform Fourier transforms on graph1. We apply the matrix $\mathbf U^{\mathrm T}$ in $\eqref{eq-laplacian-diag}$ onto a vector of node attributes,

$$ \mathbf U^{\mathrm T} \mathbf f. $$

The above is the Fourier transform of the node attributes on the graph.

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.
Convolutions Using Fourier Transform
Convolution and Fourier transform

  1. Hamilton2020 Hamilton WL. Graph Representation Learning. Morgan & Claypool Publishers; 2020. pp. 1–159. doi:10.2200/S01045ED1V01Y202009AIM046  ↩︎

Published: by ;

L Ma (2021). 'Graph Laplacians', Datumorphism, 09 April. Available at: https://datumorphism.leima.is/cards/graph/graph-laplacians/.

Current Ref:

  • cards/graph/graph-laplacians.md