In the mathematical field of graph theory, the Laplacian matrix, also called the graph Laplacian, admittance matrix, Kirchhoff matrix, or discrete Laplacian, is a matrix representation of a graph. Named after Pierre-Simon Laplace, 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.
The Laplacian matrix relates to many functional graph properties. Kirchhoff's theorem can be used to calculate the number of spanning trees for a given graph. The sparsest cut of a graph can be approximated through the Fiedler vector — the eigenvector corresponding to the second smallest eigenvalue of the graph Laplacian — as established by Cheeger's inequality. The spectral decomposition of the Laplacian matrix allows the construction of low-dimensional embeddings that appear in many machine learning applications and determines a spectral layout in graph drawing. Graph-based signal processing is based on the graph Fourier transform that extends the traditional discrete Fourier transform by substituting the standard basis of complex sinusoids for eigenvectors of the Laplacian matrix of a graph corresponding to the signal.
The Laplacian matrix is the easiest to define for a simple graph but is more common in applications for an edge-weighted graph, i.e., with weights on its edges — the entries of the graph adjacency matrix. Spectral graph theory relates properties of a graph to a spectrum, i.e., eigenvalues and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix. Imbalanced weights may undesirably affect the matrix spectrum, leading to the need of normalization — a column/row scaling of the matrix entries — resulting in normalized adjacency and Laplacian matrices.
Definitions for simple graphs
Laplacian matrix
Given a simple graph <math>G</math> with <math>n</math> vertices <math>v_1, \ldots, v_n</math>, its Laplacian matrix <math display="inline">L_{n \times n}</math> is
defined element-wise as
: <math>L_{i,j} := \begin{cases}
\deg(v_i) & \mbox{if}\ i = j \\
-1 & \mbox{if}\ i \neq j\ \mbox{and}\ v_i \mbox{ is adjacent to } v_j \\
0 & \mbox{otherwise},
\end{cases}</math>
or equivalently by the matrix
: <math>L = D - A, </math>
where D is the degree matrix, and A is the graph's adjacency matrix. Since <math display="inline">G</math> is a simple graph, <math display="inline">A</math> only contains 1s or 0s and its diagonal elements are all 0s.
Here is a simple example of a labelled, undirected graph and its Laplacian matrix.
{|class="wikitable"
! Labelled graph
! Degree matrix
! Adjacency matrix
! Laplacian matrix
|-
| 175px
| <math display="inline">\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)</math>
| <math display="inline">\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)</math>
| <math display="inline">\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) </math>
|}
We observe for the undirected graph that both the adjacency matrix and the Laplacian matrix are symmetric and that the row- and column-sums of the Laplacian matrix are all zeros (which directly implies that the Laplacian matrix is singular).
For directed graphs, either the indegree or outdegree might be used, depending on the application, as in the following example:
{|class="wikitable"
!Labelled graph
! Adjacency matrix
! Out-Degree matrix
! Out-Degree Laplacian
! In-Degree matrix
! In-Degree Laplacian
|-
|center|100x100px
| <math display="inline">\left(\begin{array}{rrr}
0 & 1 & 1\\
0 & 0 & 1\\
1 & 0 & 0\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
2 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
2 & 0 & -1\\
-1 & 1 & 0\\
-1 & -1 & 1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 2\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrr}
1 & -1 & -1\\
0 & 1 & -1\\
-1 & 0 & 2\\
\end{array}\right)</math>
|}
In the directed graph, the adjacency matrix and Laplacian matrix are asymmetric. In its Laplacian matrix, column-sums or row-sums are zero, depending on whether the indegree or outdegree has been used.
Laplacian matrix for an undirected graph via the oriented incidence matrix
The <math display="inline">|v| \times |e|</math> oriented incidence matrix B with element B<sub>ve</sub> for the vertex v and the edge e (connecting vertices <math display="inline">v_i</math> and <math display="inline">v_j</math>, with i ≠ j) is defined by
:<math>B_{ve} = \left\{\begin{array}{rl}
1, & \text{if } v = v_i\\
-1, & \text{if } v = v_j\\
0, & \text{otherwise}.
\end{array}\right.</math>
Even though the edges in this definition are technically directed, their directions can be arbitrary, still resulting in the same symmetric Laplacian <math display="inline">|v| \times |v|</math> matrix L defined as
:<math>L = B B^\textsf{T}</math>
where <math display="inline">B^\textsf{T}</math> is the matrix transpose of B.
{|class="wikitable"
! Undirected graph
! Incidence matrix
! Laplacian matrix
|-
| 100px
| <math display="inline">\left(\begin{array}{rrrr}
1 & 1 & 1 & 0\\
-1 & 0 & 0 & 0\\
0 & -1 & 0 & 1\\
0 & 0 & -1 & -1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrrr}
3 & -1 & -1 & -1\\
-1 & 1 & 0 & 0\\
-1 & 0 & 2 & -1\\
-1 & 0 & -1 & 2\\
\end{array}\right)</math>
|}
An alternative product <math>B^\textsf{T}B</math> defines the so-called <math display="inline">|e| \times |e|</math> edge-based Laplacian, as opposed to the original commonly used vertex-based Laplacian matrix L.
Symmetric Laplacian for a directed graph
The Laplacian matrix of a directed graph is by definition generally non-symmetric, while, e.g., traditional spectral clustering is primarily developed for undirected graphs with symmetric adjacency and Laplacian matrices. A trivial approach to applying techniques requiring the symmetry is to turn the original directed graph into an undirected graph and build the Laplacian matrix for the latter.
In the matrix notation, the adjacency matrix of the undirected graph could, e.g., be defined as a Boolean sum of the adjacency matrix <math>A</math> of the original directed graph and its matrix transpose <math>A^T</math>, where the zero and one entries of <math>A</math> are treated as logical, rather than numerical, values, as in the following example:
{|class="wikitable"
! Adjacency matrix
! Symmetrized adjacency
! Symmetric Laplacian matrix
|-
| <math display="inline">\left(\begin{array}{ccc}
0 & 1 & 1\\
0 & 0 & 1\\
1 & 0 & 0\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{ccc}
0 & 1 & 1\\
1 & 0 & 1\\
1 & 1 & 0\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{ccc}
2 & -1 & -1\\
-1 & 2 & -1\\
-1 & -1 & 2\\
\end{array}\right)</math>
|}
Laplacian matrix normalization
A vertex with a large degree, also called a heavy node, results in a large diagonal entry in the Laplacian matrix dominating the matrix properties. Normalization is aimed to make the influence of such vertices more equal to that of other vertices, by dividing the entries of the Laplacian matrix by the vertex degrees. To avoid division by zero, isolated vertices with zero degrees are excluded from the process of the normalization.
Symmetrically normalized Laplacian
The symmetrically normalized Laplacian matrix is defined as: In this interpretation, every graph vertex is treated as a grid point; the local connectivity of the vertex determines the finite difference approximation stencil at this grid point, the grid size is always one for every edge, and there are no constraints on any grid points, which corresponds to the case of the homogeneous Neumann boundary condition, i.e., free boundary. Such an interpretation allows one, e.g., generalizing the Laplacian matrix to the case of graphs with an infinite number of vertices and edges, leading to a Laplacian matrix of an infinite size.
Generalizations and extensions of the Laplacian matrix
Generalized Laplacian
The generalized Laplacian <math>Q</math> is defined as:
: <math>\begin{cases}
Q_{i,j} < 0 & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j\\
Q_{i,j} = 0 & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is not adjacent to } v_j \\
\mbox{any number} & \mbox{otherwise}.
\end{cases}</math>
Notice the ordinary Laplacian is a generalized Laplacian.
Admittance matrix of an AC circuit
The Laplacian of a graph was first introduced to model electrical networks.
In an alternating current (AC) electrical network, real-valued resistances are replaced by complex-valued impedances.
The weight of edge (i, j) is, by convention, minus the reciprocal of the impedance directly between i and j.
In models of such networks, the entries of the adjacency matrix are complex, but the Kirchhoff matrix remains symmetric, rather than being Hermitian.
Such a matrix is usually called an "admittance matrix", denoted <math>Y</math>, rather than a "Laplacian".
This is one of the rare applications that give rise to complex symmetric matrices.
{|class="wikitable"
! Adjacency matrix
! Weighted degree matrix
! Admittance matrix
|-
| <math display="inline">\left(\begin{array}{rrrr}
0 & i & 0 & 0\\
i & 0 & 1-2i & 0\\
0 & 1-2i & 0 & 1\\
0 & 0 & 1 & 0\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrrr}
i & 0 & 0 & 0\\
0 & 1-i & 0 & 0\\
0 & 0 & 2-2i & 0\\
0 & 0 & 0 & 1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrrr}
-i & i & 0 & 0\\
i & -1+i & 1-2i & 0\\
0 & 1-2i & -2+2i & 1\\
0 & 0 & 1 & -1\\
\end{array}\right)</math>
|}
Magnetic Laplacian
There are other situations in which entries of the adjacency matrix are complex-valued, and the Laplacian does become a Hermitian matrix. The Magnetic Laplacian for a directed graph with real weights <math>w_{ij}</math> is constructed as the Hadamard product of the real symmetric matrix of the symmetrized Laplacian and the Hermitian phase matrix with the complex entries
:<math>\gamma_q(i, j) = e^{i2 \pi q(w_{ij}-w_{ji})}</math>
which encode the edge direction into the phase in the complex plane.
In the context of quantum physics, the magnetic Laplacian can be interpreted as the operator that describes the phenomenology of a free charged particle on a graph, which is subject to the action of a magnetic field and the parameter <math>q</math> is called electric charge.
In the following example <math>q=1/4</math>:
{|class="wikitable"
! Adjacency matrix
! Symmetrized Laplacian
! Phase matrix
! Magnetic Laplacian
|-
| <math display="inline">\left(\begin{array}{rrrr}
0 & 1 & 0 & 0\\
1 & 0 & 1 & 0\\
0 & 0 & 0 & 0\\
0 & 0 & 1 & 0\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrrr}
2 & -2 & 0 & 0\\
-2 & 3 & -1 & 0\\
0 & -1 & 2 & -1\\
0 & 0 & -1 & 1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrrr}
1 & 1 & 1 & 1\\
1 & 1 & i & 1\\
1 & -i & 1 & -i\\
1 & 1 & i & 1\\
\end{array}\right)</math>
| <math display="inline">\left(\begin{array}{rrrr}
2 & -2 & 0 & 0\\
-2 & 3 & -i & 0\\
0 & i & 2 & i\\
0 & 0 & -i & 1\\
\end{array}\right)</math>
|}
Deformed Laplacian
The deformed Laplacian is commonly defined as
:<math>\Delta(s) = I - sA + s^2(D - I)</math>
where <math display="inline">I</math> is the identity matrix, <math display="inline">A</math> is the adjacency matrix, <math display="inline">D</math> is the degree matrix, and <math display="inline">s</math> is a (complex-valued) number.<br /> The standard Laplacian is just <math display="inline">\Delta(1)</math> and <math display="inline">\Delta(-1) = D + A</math> is the signless Laplacian.
Signless Laplacian
The signless Laplacian is defined as
:<math>Q = D + A</math>
where <math>D</math> is the degree matrix, and <math>A</math> is the adjacency matrix. Like the signed Laplacian <math>L</math>, the signless Laplacian <math>Q</math> also is positive semi-definite as it can be factored as
:<math>Q = RR^\textsf{T}</math>
where <math display="inline">R</math> is the incidence matrix. <math>Q</math> has a 0-eigenvector if and only if it has a bipartite connected component (isolated vertices being bipartite connected components). This can be shown as
:<math>\mathbf{x}^\textsf{T} Q \mathbf{x} = \mathbf{x}^\textsf{T} R R^\textsf{T} \mathbf{x} \implies R^\textsf{T} \mathbf{x} = \mathbf{0}.</math>
This has a solution where <math>\mathbf{x} \neq \mathbf{0}</math> if and only if the graph has a bipartite connected component.
Directed multigraphs
An analogue of the Laplacian matrix can be defined for directed multigraphs. In this case the Laplacian matrix L is defined as
:<math>L = D - A</math>
where D is a diagonal matrix with D<sub>i,i</sub> equal to the outdegree of vertex i and A is a matrix with A<sub>i,j</sub> equal to the number of edges from i to j (including loops).
Open source software implementations
- SciPy
- NetworkX
- Julia
Application software
- scikit-learn Spectral Clustering
- PyGSP: Graph Signal Processing in Python
- megaman: Manifold Learning for Millions of Points
- smoothG
- Laplacian Change Point Detection for Dynamic Graphs (KDD 2020)
- LaplacianOpt (A Julia Package for Maximizing Laplacian's Second Eigenvalue of Weighted Graphs)
- LigMG (Large Irregular Graph MultiGrid)
- Laplacians.jl
See also
- Stiffness matrix
- Resistance distance
- Transition rate matrix
- Calculus on finite weighted graphs
- Graph Fourier transform