Graph Laplacian

In graph theory, the graph Laplacian, also referred to as Laplacian matrix, admittance matrix, or Kirchhoff matrix, is a matrix representation of a graph. The graph Laplacian matrix can be viewed as a matrix form of the negative discrete Laplace operator on a graph approximating the negative continuous Laplacian obtained by the finite difference method.

Graph Laplacian naturally captures the phenomenon of network flooding. For example in social network modeling, Graph Laplacians are used to model spread of information (such as opinions and rumors) over time, due to diffusion property. Simple models operate under the assumption that every initial condition evolves towards consensus, defined as locally-constant solutions, However in more complex settings this is not necessarily the case.

# Definition

Given a graph $G$ with adjacency matrix $\mathbf{A}$ and a degree matrix $\mathbf{D}$, the graph Laplacian $\mathbf{L}_G$ is defined as:

$$\mathbf{L}_G = \mathbf{D}_G - \mathbf{A}_G$$

## Physical meaning

Given a vertex $v \in G$ equipped with a time-dependent function $x(t)$, the Laplacian operator acts on it by diffusion for some $\alpha > 0$:

$$\dot{x}(t) = -\alpha \mathbf{L}_G x(t)$$

Equivalently, in discrete time case, where the state the state of a node is given by a sequence $(x_t)$:

$$x_{n+1} = (\mathbf{I} - \alpha \mathbf{L}_G) x_n$$

Discrete Laplacians can be thought of in a familiar setting for engineers in the context of Kirchhoff's current laws which state that an algebraic sum of directed currents meeting at a node is zero.

## Symmetric Laplacian

The Symmetrically normalized Laplacian is defined as:

$$\mathbf{L}^\mathrm{sym}_G := (\mathbf{D}^+_G)^{1/2} \mathbf{L}_G(\mathbf{D}^+_G)^{1/2}$$

For undirected graph with weighted edges one can define a weighted incidence matrix $\mathbf{W}_G$ and use it to construct the corresponding symmetric Laplacian as

$$\mathbf{L}_G = \mathbf{W}_G\mathbf{W}_G^\mathrm{T}$$

## Properties

For an undirected graph $G$ and it's Laplacian $\mathbb{L}$ with eigenvalues $\lambda_0 \leq \lambda_1 \leq \cdots \leq \lambda_{n-1}$:

• Graph Laplacian is symmetric.
• Graph Laplacian is positive-semidefinite, (real parts of its eigenvalues are non-negative).
• Graph Laplacian's off-diagonal entries are nonpositive, yet the real parts of its eigenvalues are nonnegative.
• Every row sum and column sum of Graph Laplacian is zero.
• The number of connected components in the graph is the dimension of the nullspace of the Laplacian, (this is equivalent to 0-th Betti number).

The smallest non-zero eigenvalue of the graph Laplacian extends the notion of a spectral gap to graph theory. The second smallest eigenvalue of L (could be zero) is the algebraic connectivity (or Fiedler value) of G and approximates the sparsest cut of a graph.

# Graph Fourier Transform

The graph Fourier transform extends the notion of Fourier transform to graphs and eigendecomposes the Laplacian matrix of a graph into eigenvalues and eigenvectors. Analogously to the classical case, the eigenvalues represent frequencies and eigenvectors form what is known as a graph Fourier basis.

The Graph Fourier transform is important in spectral graph theory. It is widely applied in the recent study of graph structured learning algorithms, such as the widely employed convolutional networks.

Given an undirected weighted graph $G = (V,E)$, where $V$ is the set of nodes with $|V| = N$ ($N$ being the number of nodes) and $E$ is the set of edges, a graph signal $f: V \rightarrow \mathbb{R}$ is a function defined on the vertices of the graph $G$. The signal $f$ maps every vertex $\{v_i\}_{i=1,\ldots,N}$ to an associated height function $f_i : v_i \to \mathbb{R}$. Any graph signal can be projected on the eigenvectors of the Laplacian matrix $\mathbf{L}$.

Let $\lambda_l$ and $\mu_l$ be the $l_\text{th}$ eigenvalue and eigenvector of the [[Laplacian]] matrix $\mathbf{L}$ (the eigenvalues are sorted in an increasing order, i.e., $\lambda_0\leq\lambda_1\leq\cdots\leq\lambda_{N-1}$, the graph Fourier transform (GFT) [$\hat{f}$ of a graph signal $f$ on the vertices of $G$ is the expansion of $f$ in terms of the eigenfunctions of $\mathbb{L}$.

$$\mathrm{G F}[f](\lambda_{l})=\hat{f}\left(\lambda_{l}\right)=\langle f, \mu_{l}\rangle=\sum_{i=1}^{N} f(i) \mu_{l}^*(i)$$

where $\mu_l^* = \mu_l^\text{T}$.

Since $\mathbb{L}$ is a real symmetric matrix, its eigenvectors $\{\mu_l\}_{l=0,\cdots, N-1}$ form an orthogonal basis. Hence an inverse graph Fourier transform (IGFT) exists, and it is written as:

$$\mathrm{IGF}[\hat{f}](i)=f(i)=\sum_{l=0}^{N-1} \hat{f}(\lambda_l) \mu_l(i)$$