In themathematical field ofgraph theory, theLaplacian matrix, also called thegraph Laplacian,admittance matrix,Kirchhoff matrix, ordiscrete Laplacian, is amatrix representation of agraph. Named afterPierre-Simon Laplace, the graph Laplacian matrix can be viewed as a matrix form of the negativediscrete Laplace operator on a graph approximating the negative continuousLaplacian obtained by thefinite difference method.

The Laplacian matrix relates to many functional graph properties.Kirchhoff's theorem can be used to calculate the number ofspanning trees for a given graph. Thesparsest cut of a graph can be approximated through theFiedler vector — the eigenvector corresponding to the second smallest eigenvalue of the graph Laplacian — as established byCheeger's inequality. Thespectral decomposition of the Laplacian matrix allows the construction oflow-dimensional embeddings that appear in manymachine learning applications and determines aspectral layout ingraph drawing. Graph-basedsignal processing is based on thegraph Fourier transform that extends the traditionaldiscrete Fourier transform by substituting the standard basis ofcomplexsinusoids for eigenvectors of the Laplacian matrix of a graph corresponding to the signal.

The Laplacian matrix is the easiest to define for asimple graph but is more common in applications for anedge-weighted graph, i.e., with weights on its edges — the entries of the graphadjacency 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.

Given asimple graph${\displaystyle G}$ with${\displaystyle n}$ vertices${\displaystyle v_1,\dots ,v_n}$, its Laplacian matrix$L_{n\times n}$ is defined element-wise as^[1]

or equivalently by the matrix

${\displaystyle L=D-A,}$

whereD is thedegree matrix, andA is the graph'sadjacency matrix. Since$G$ is a simple graph,$A$ 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.

Labelled graph	Degree matrix	Adjacency matrix	Laplacian matrix

We observe for the undirected graph that both theadjacency 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).

Fordirected graphs, either theindegree or outdegree might be used, depending on the application, as in the following example:

Labelled graph	Adjacency matrix	Out-Degree matrix	Out-Degree Laplacian	In-Degree matrix	In-Degree Laplacian

In the directed graph, theadjacency matrix and Laplacian matrix are asymmetric. In its Laplacian matrix, column-sums or row-sums are zero, depending on whether theindegree or outdegree has been used.

The$|v|\times |e|$ orientedincidence matrixB with elementB_ve for the vertexv and the edgee (connecting vertices$v_i$ and$v_j$, withi ≠ j) is defined by

Even though the edges in this definition are technically directed, their directions can be arbitrary, still resulting in the same symmetric Laplacian$|v|\times |v|$ matrixL defined as

${\displaystyle L=B{B}^{\mathsf{\text{T}}}}$

where$B^{\mathsf{\text{T}}}$ is thematrix transpose ofB.

Undirected graph	Incidence matrix	Laplacian matrix

An alternative product${\displaystyle B^{\mathsf{\text{T}}}B}$ defines the so-called$|e|\times |e|$edge-based Laplacian, as opposed to the original commonly usedvertex-based Laplacian matrixL.

The Laplacian matrix of a directed graph is by definition generally non-symmetric, while, e.g., traditionalspectral 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 aBoolean sum of the adjacency matrix${\displaystyle A}$ of the original directed graph and itsmatrix transpose${\displaystyle A^T}$, where the zero and one entries of${\displaystyle A}$ are treated as logical, rather than numerical, values, as in the following example:

Adjacency matrix	Symmetrized adjacency	Symmetric Laplacian matrix

A vertex with a large degree, also called aheavy 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.

The symmetrically normalized Laplacian matrix is defined as:^[1]

${\displaystyle L^{\text{sym}}:=(D^{+}{)}^{1/2}L(D^{+}{)}^{1/2}=I-(D^{+}{)}^{1/2}A(D^{+}{)}^{1/2},}$

where${\displaystyle D^{+}}$ is theMoore–Penrose inverse of the degree matrix.

The elements of$L^{\text{sym}}$ are thus given by

The symmetrically normalized Laplacian matrix is symmetric if and only if the adjacency matrix is symmetric.

Adjacency matrix	Degree matrix	Normalized Laplacian

For a non-symmetric adjacency matrix of a directed graph, either ofindegree and outdegree can be used for normalization:

Adjacency matrix	Out-Degree matrix	Out-Degree normalized Laplacian	In-Degree matrix	In-Degree normalized Laplacian

The left (random-walk) normalized Laplacian matrix is defined as:

${\displaystyle L^{\text{rw}}:=D^{+}L=I-D^{+}A,}$

where${\displaystyle D^{+}}$ is theMoore–Penrose inverse.The elements of$L^{\text{rw}}$ are given by

Similarly, the right normalized Laplacian matrix is defined as

${\displaystyle L{D}^{+}=I-A{D}^{+}}$.

The left or right normalized Laplacian matrix is symmetric if the adjacency matrix is symmetric and the graph is regular. Otherwise, the left or right normalized Laplacian matrix is asymmetric. For example,

Adjacency matrix	Degree matrix	Left normalized Laplacian	Right normalized Laplacian

The example also demonstrates that if${\displaystyle G}$ has no isolated vertices, then${\displaystyle D^{+}A}$right stochastic and hence is the matrix of arandom walk, so that the left normalized Laplacian${\displaystyle L^{\text{rw}}:=D^{+}L=I-D^{+}A}$ has each row summing to zero. Thus we sometimes alternatively call${\displaystyle L^{\text{rw}}}$ therandom-walk normalized Laplacian. In the less uncommonly used right normalized Laplacian${\displaystyle L{D}^{+}=I-A{D}^{+}}$ each column sums to zero since${\displaystyle A{D}^{+}}$ isleft stochastic.

For a non-symmetric adjacency matrix of a directed graph, one also needs to chooseindegree or outdegree for normalization:

Adjacency matrix	Out-Degree matrix	Out-Degree left normalized Laplacian	In-Degree matrix	In-Degree right normalized Laplacian

The left out-degree normalized Laplacian with row-sums all 0 relates toright stochastic${\displaystyle D_{\text{out}}^{+}A}$ , while the right in-degree normalized Laplacian with column-sums all 0 containsleft stochastic${\displaystyle A{D}_{\text{in}}^{+}}$.

Common in applications graphs with weighted edges are conveniently defined by their adjacency matrices where values of the entries are numeric and no longer limited to zeros and ones. Inspectral clustering and graph-basedsignal processing, where graph vertices represent data points, the edge weights can be computed, e.g., as inversely proportional to thedistances between pairs of data points, leading to all weights being non-negative with larger values informally corresponding to more similar pairs of data points. Using correlation and anti-correlation between the data points naturally leads to both positive and negative weights. Most definitions for simple graphs are trivially extended to the standard case of non-negative weights, while negative weights require more attention, especially in normalization.

The Laplacian matrix is defined by

${\displaystyle L=D-A,}$

whereD is thedegree matrix andA is theadjacency matrix of the graph.

Fordirected graphs, either theindegree or outdegree might be used, depending on the application, as in the following example:

Adjacency matrix	In-Degree matrix	In-Degree Laplacian	Out-Degree matrix	Out-Degree Laplacian

Graph self-loops, manifesting themselves by non-zero entries on the main diagonal of the adjacency matrix, are allowed but do not affect the graph Laplacian values.

For graphs with weighted edges one can define a weighted incidence matrixB and use it to construct the corresponding symmetric Laplacian as${\displaystyle L=B{B}^{\mathsf{\text{T}}}}$. An alternative cleaner approach, described here, is to separate the weights from the connectivity: continue using theincidence matrix as for regular graphs and introduce a matrix just holding the values of the weights. Aspring system is an example of this model used inmechanics to describe a system of springs of given stiffnesses and unit length, where the values of the stiffnesses play the role of the weights of the graph edges.

We thus reuse the definition of the weightless$|v|\times |e|$incidence matrixB with elementB_ve for the vertexv and the edgee (connecting vertexes$v_i$ and$v_j$, withi > j) defined by

We now also define a diagonal$|e|\times |e|$ matrixW containing the edge weights. Even though the edges in the definition ofB are technically directed, their directions can be arbitrary, still resulting in the same symmetric Laplacian$|v|\times |v|$ matrixL defined as

${\displaystyle L=BW{B}^{\mathsf{\text{T}}}}$

where$B^{\mathsf{\text{T}}}$ is thematrix transpose ofB.

The construction is illustrated in the following example, where every edge$e_i$ is assigned the weight valuei, with$i=1,2,3,4.$

Undirected graph	Incidence matrix	Edge weights	Laplacian matrix

Just like for simple graphs, the Laplacian matrix of a directed weighted graph is by definition generally non-symmetric. The symmetry can be enforced by turning the original directed graph into an undirected graph first before constructing the Laplacian. The adjacency matrix of the undirected graph could, e.g., be defined as a sum of the adjacency matrix${\displaystyle A}$ of the original directed graph and itsmatrix transpose${\displaystyle A^T}$ as in the following example:

Adjacency matrix	Symmetrized adjacency matrix	Symmetric Laplacian matrix

where the zero and one entries of${\displaystyle A}$ are treated as numerical, rather than logical as for simple graphs, values, explaining the difference in the results - for simple graphs, the symmetrized graph still needs to be simple with its symmetrized adjacency matrix having only logical, not numerical values, e.g., the logical sum is 1 v 1 = 1, while the numeric sum is 1 + 1 = 2.

Alternatively, the symmetric Laplacian matrix can be calculated from the two Laplacians using theindegree and outdegree, as in the following example:

Adjacency matrix	Out-Degree matrix	Out-Degree Laplacian	In-Degree matrix	In-Degree Laplacian

The sum of the out-degree Laplacian transposed and the in-degree Laplacian equals to the symmetric Laplacian matrix.

The goal of normalization is, like for simple graphs, to make the diagonal entries of the Laplacian matrix to be all unit, also scaling off-diagonal entries correspondingly. In a weighted graph, a vertex may have a large degree because of a small number of connected edges but with large weights just as well as due to a large number of connected edges with unit weights.

Graph self-loops, i.e., non-zero entries on the main diagonal of the adjacency matrix, do not affect the graph Laplacian values, but may need to be counted for calculation of the normalization factors.

Thesymmetrically normalized Laplacian is defined as

${\displaystyle L^{\text{sym}}:=(D^{+}{)}^{1/2}L(D^{+}{)}^{1/2}=I-(D^{+}{)}^{1/2}A(D^{+}{)}^{1/2},}$

whereL is the unnormalized Laplacian,A is the adjacency matrix,D is the degree matrix, and${\displaystyle D^{+}}$ is theMoore–Penrose inverse. Since the degree matrixD is diagonal, its reciprocal square root$(D^{+}{)}^{1/2}$ is just the diagonal matrix whose diagonal entries are the reciprocals of the square roots of the diagonal entries ofD. If all the edge weights are nonnegative then all the degree values are automatically also nonnegative and so every degree value has a unique positive square root. To avoid the division by zero, vertices with zero degrees are excluded from the process of the normalization, as in the following example:

Adjacency matrix	In-Degree matrix	In-Degree normalized Laplacian	Out-Degree matrix	Out-Degree normalized Laplacian

The symmetrically normalized Laplacian is a symmetric matrix if and only if the adjacency matrixA is symmetric and the diagonal entries ofD are nonnegative, in which case we can use the term thesymmetric normalized Laplacian.

The symmetric normalized Laplacian matrix can be also written as

${\displaystyle L^{\text{sym}}:=(D^{+}{)}^{1/2}L(D^{+}{)}^{1/2}=(D^{+}{)}^{1/2}BW{B}^{\mathsf{\text{T}}}(D^{+}{)}^{1/2}=S{S}^T}$

using the weightless$|v|\times |e|$incidence matrixB and the diagonal$|e|\times |e|$ matrixW containing the edge weights and defining the new$|v|\times |e|$ weighted incidence matrix$S=(D^{+}{)}^{1/2}B{W}^{1/2}$ whose rows are indexed by the vertices and whose columns are indexed by the edges of G such that each column corresponding to an edgee = {u, v} has an entry$\frac{1}{\sqrt{d_u}}$ in the row corresponding tou, an entry$-\frac{1}{\sqrt{d_v}}$ in the row corresponding tov, and has 0 entries elsewhere.

Therandom walk normalized Laplacian is defined as

${\displaystyle L^{\text{rw}}:=D^{+}L=I-D^{+}A}$

whereD is the degree matrix. Since the degree matrixD is diagonal, its inverse$D^{+}$ is simply defined as a diagonal matrix, having diagonal entries which are the reciprocals of the corresponding diagonal entries ofD. For the isolated vertices (those with degree 0), a common choice is to set the corresponding element$L_{i,i}^{\text{rw}}$ to 0. The matrix elements of$L^{\text{rw}}$ are given by

The name of the random-walk normalized Laplacian comes from the fact that this matrix is$L^{\text{rw}}=I-P$, where$P=D^{+}A$ is simply the transition matrix of a random walker on the graph, assuming non-negative weights. For example, let$e_i$ denote the i-thstandard basis vector. Then$x=e_{i}P$ is aprobability vector representing the distribution of a random walker's locations after taking a single step from vertex$i$; i.e.,$x_j=\mathbb{P}\left(v_i\to v_j\right)$. More generally, if the vector$x$ is a probability distribution of the location of a random walker on the vertices of the graph, then$x^{\prime }=x{P}^t$ is the probability distribution of the walker after$t$ steps.

The random walk normalized Laplacian can also be called the left normalized Laplacian${\displaystyle L^{\text{rw}}:=D^{+}L}$ since the normalization is performed by multiplying the Laplacian by the normalization matrix${\displaystyle D^{+}}$ on the left. It has each row summing to zero since${\displaystyle P=D^{+}A}$ isright stochastic, assuming all the weights are non-negative.

In the less uncommonly used right normalized Laplacian${\displaystyle L{D}^{+}=I-A{D}^{+}}$ each column sums to zero since${\displaystyle A{D}^{+}}$ isleft stochastic.

For a non-symmetric adjacency matrix of a directed graph, one also needs to chooseindegree or outdegree for normalization:

Adjacency matrix	Out-Degree matrix	Out-Degree left normalized Laplacian	In-Degree matrix	In-Degree right normalized Laplacian

The left out-degree normalized Laplacian with row-sums all 0 relates toright stochastic${\displaystyle D_{\text{out}}^{+}A}$ , while the right in-degree normalized Laplacian with column-sums all 0 containsleft stochastic${\displaystyle A{D}_{\text{in}}^{+}}$.

Negative weights present several challenges for normalization:

• The presence of negative weights may naturally result in zero row- and/or column-sums for non-isolated vertices. A vertex with a large row-sum of positive weights and equally negatively large row-sum of negative weights, together summing up to zero, could be considered a heavy node and both large values scaled, while the diagonal entry remains zero, like for an isolated vertex.
• Negative weights may also give negative row- and/or column-sums, so that the corresponding diagonal entry in the non-normalized Laplacian matrix would be negative and a positive square root needed for the symmetric normalization would not exist.
• Arguments can be made to take the absolute value of the row- and/or column-sums for the purpose of normalization, thus treating a possible value -1 as a legitimate unit entry of the main diagonal of the normalized Laplacian matrix.

For an (undirected) graphG and its Laplacian matrixL witheigenvalues${\lambda }_0\le {\lambda }_1\le \cdots \le {\lambda }_{n-1}$:

• L issymmetric.
• L ispositive-semidefinite (that is${\lambda }_i\ge 0$ for all$i$). This can be seen from the fact that the Laplacian is symmetric anddiagonally dominant.
• L is anM-matrix (its off-diagonal entries are nonpositive, yet the real parts of its eigenvalues are nonnegative).
• Every row sum and column sum ofL is zero. Indeed, in the sum, the degree of the vertex is summed with a "−1" for each neighbor.
• In consequence,${\lambda }_0=0$, because the vector${\mathbf{v}}_0=(1,1,\dots ,1)$ satisfies$L{\mathbf{v}}_0=\mathbf{0}.$ This also implies that the Laplacian matrix is singular.
• The number ofconnected components in the graph is the dimension of thenullspace of the Laplacian and thealgebraic multiplicity of the 0 eigenvalue.
• The smallest non-zero eigenvalue ofL is called thespectral gap.
• The second smallest eigenvalue ofL (could be zero) is thealgebraic connectivity (orFiedler value) ofG and approximates thesparsest cut of a graph.
• TheLaplacian is an operator on the n-dimensional vector space of functions$f:V\to \mathbb{R}$, where$V$ is the vertex set of G, and$n=|V|$.
• When G isk-regular, the normalized Laplacian is:$\mathcal{L}=\frac{1}{k}L=I-\frac{1}{k}A$, where A is the adjacency matrix and I is an identity matrix.
• For a graph with multipleconnected components,L is ablock diagonal matrix, where each block is the respective Laplacian matrix for each component, possibly after reordering the vertices (i.e.L is permutation-similar to a block diagonal matrix).
• The trace of the Laplacian matrixL is equal to$2m$ where$m$ is the number of edges of the considered graph.
• Now consider an eigendecomposition of$L$, with unit-norm eigenvectors${\mathbf{v}}_i$ and corresponding eigenvalues${\lambda }_i$:

Because${\lambda }_i$ can be written as the inner product of the vector$M{\mathbf{v}}_i$ with itself, this shows that${\lambda }_i\ge 0$ and so the eigenvalues of$L$ are all non-negative.

• All eigenvalues of the normalized symmetric Laplacian satisfy 0 = μ₀ ≤ … ≤ μ_n−1 ≤ 2. These eigenvalues (known as the spectrum of the normalized Laplacian) relate well to other graph invariants for general graphs.^[1]

• One can check that:

${\displaystyle L^{\text{rw}}=I-D^{-\frac{1}{2}}\left(I-L^{\text{sym}}\right)D^{\frac{1}{2}}}$,

i.e.,$L^{\text{rw}}$ is similar to the normalized Laplacian$L^{\text{sym}}$. For this reason, even if$L^{\text{rw}}$ is in general not symmetric, it has real eigenvalues — exactly the same as the eigenvalues of the normalized symmetric Laplacian$L^{\text{sym}}$.

The graph Laplacian matrix can be further viewed as a matrix form of the negativediscrete Laplace operator on a graph approximating the negative continuousLaplacian operator obtained by thefinite difference method.(SeeDiscrete Poisson equation)^[2] In this interpretation, every graph vertex is treated as a grid point; the local connectivity of the vertex determines the finite difference approximationstencil 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 homogeneousNeumann 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.

The generalized Laplacian${\displaystyle Q}$ is defined as:^[3]

Notice the ordinary Laplacian is a generalized Laplacian.

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 betweeni andj.In models of such networks, the entries of theadjacency matrix are complex, but the Kirchhoff matrix remains symmetric, rather than beingHermitian.Such a matrix is usually called an "admittance matrix", denoted${\displaystyle Y}$, rather than a "Laplacian".This is one of the rare applications that give rise tocomplex symmetric matrices.

Adjacency matrix	Weighted degree matrix	Admittance matrix

There are other situations in which entries of the adjacency matrix are complex-valued, and the Laplacian does become aHermitian matrix. The Magnetic Laplacian for a directed graph with real weights${\displaystyle w_{ij}}$ is constructed as theHadamard product of thereal symmetric matrix of the symmetrized Laplacian and the Hermitian phase matrix with thecomplex entries

${\displaystyle {\gamma }_q(i,j)=e^{i2\pi q(w_{ij}-w_{ji})}}$

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${\displaystyle q}$ is called electric charge.^[4]In the following example${\displaystyle q=1/4}$:

Adjacency matrix	Symmetrized Laplacian	Phase matrix	Magnetic Laplacian

Thedeformed Laplacian is commonly defined as

${\displaystyle \mathrm{\Delta }(s)=I-sA+s^2(D-I)}$

where$I$ is the identity matrix,$A$ is the adjacency matrix,$D$ is the degree matrix, and$s$ is a (complex-valued) number.^[5]
The standard Laplacian is just$\mathrm{\Delta }(1)$ and$\mathrm{\Delta }(-1)=D+A$ is the signless Laplacian.

Thesignless Laplacian is defined as

${\displaystyle Q=D+A}$

where${\displaystyle D}$ is the degree matrix, and${\displaystyle A}$ is the adjacency matrix.^[6] Like the signed Laplacian${\displaystyle L}$, the signless Laplacian${\displaystyle Q}$ also is positive semi-definite as it can be factored as

${\displaystyle Q=R{R}^{\mathsf{\text{T}}}}$

where$R$ is the incidence matrix.${\displaystyle Q}$ 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

${\displaystyle {\mathbf{x}}^{\mathsf{\text{T}}}Q\mathbf{x}={\mathbf{x}}^{\mathsf{\text{T}}}R{R}^{\mathsf{\text{T}}}\mathbf{x}⟹R^{\mathsf{\text{T}}}\mathbf{x}=\mathbf{0}.}$

This has a solution where${\displaystyle \mathbf{x}\ne \mathbf{0}}$ if and only if the graph has a bipartite connected component.

An analogue of the Laplacian matrix can be defined for directed multigraphs.^[7] In this case the Laplacian matrixL is defined as

${\displaystyle L=D-A}$

whereD is a diagonal matrix withD_i,i equal to the outdegree of vertexi andA is a matrix withA_i,j equal to the number of edges fromi toj (including loops).

• SciPy^[8]
• NetworkX^[9]
• Julia^[10]

• scikit-learn Spectral Clustering^[11]
• PyGSP: Graph Signal Processing in Python^[12]
• megaman: Manifold Learning for Millions of Points^[13]
• smoothG^[14]
• Laplacian Change Point Detection for Dynamic Graphs (KDD 2020)^[15]
• LaplacianOpt (A Julia Package for Maximizing Laplacian's Second Eigenvalue of Weighted Graphs)^[16]
• LigMG (Large Irregular Graph MultiGrid)^[17]
• Laplacians.jl^[18]

• Stiffness matrix
• Resistance distance
• Transition rate matrix
• Calculus on finite weighted graphs
• Graph Fourier transform

• Algebraic graph theory
• Matrices (mathematics)
• Numerical differential equations

• Use American English from March 2019
• All Wikipedia articles written in American English
• Articles with short description
• Short description matches Wikidata