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{eqlaplaciandiag} \end{equation} $$
Laplacians and Fourier Transform
The eigenvectors of the graph Laplacian (Eq. $\eqref{eqlaplaciandiag}$) can be used to perform Fourier transforms on graph^{1}. We apply the matrix $\mathbf U^{\mathrm T}$ in $\eqref{eqlaplaciandiag}$ 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
Convolutions Using Fourier Transform
L Ma (2021). 'Graph Laplacians', Datumorphism, 09 April. Available at: https://datumorphism.leima.is/cards/graph/graphlaplacians/.
Table of Contents
Current Ref:

cards/graph/graphlaplacians.md
Links to:
Graph Adjacency Matrix
A graph $\mathcal G$ can be represented with an adjacency matrix $\mathbf A$. There are some nice …
Graph Cuts
Cut For a subset of nodes $\mathcal A\subset \mathcal V$, with the rest of nodes $\bar {\mathcal A} …
Convolutions Using Fourier Transform
Convolution and Fourier transform
Graph Convolution Operator
For a given graph $\mathcal G$, we have an attribute on each node, denoted as $f_v$. All the node …