Graph Laplacian

Graph Laplacian, (aka Laplace Matrix, Admittance Matrix, Kirchhoff Matrix, Discrete Laplacian, Laplace-Beltrami operator), is simply a matrix representation of a graph.

Laplacian Matrix can be computed as:

$L=D-A$

Where $L$ is Laplacian Matrix, $D$ is Degree Matrix and $A$ is Adjacency matrix.

Labelled graph	Degree matrix	Adjacency matrix	Laplacian matrix
	${\textstyle \left({\begin{array}{rrrrrr}2&0&0&0&0&0\\0&3&0&0&0&0\\0&0&2&0&0&0\\0&0&0&3&0&0\\0&0&0&0&3&0\\0&0&0&0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrrrr}0&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{array}}\right)}$	${\textstyle \left({\begin{array}{rrrrrr}2&-1&0&0&-1&0\\-1&3&-1&0&-1&0\\0&-1&2&-1&0&0\\0&0&-1&3&-1&-1\\-1&-1&0&-1&3&0\\0&0&0&-1&0&1\\\end{array}}\right)}$

Diagonalization of Laplacian

• The Laplacian of an undirected graph is symmetric as well as unitary.
• Using diagonalization: $L=U\Lambda U^{-1}$ (where $U$ is a set of eigenvectors and $\Lambda$ is a diagonal matrix containing eigenvalues)
• Then $U^{T}=U^{-1}$ OR $UU^{T}=I$

Normalized Laplacian

$L_{n}=D^{-{\frac {1}{2}}}LD^{-{\frac {1}{2}}}$

Random-walk Laplacian

$L_{rw}=D^{-1}L$

Keywords

Laplacian Matrix, GNN, Laplace Matrix, Degree Matrix