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 with vertices , its Laplacian matrix is defined element-wise as
or equivalently by the matrix
where D is the degree matrix, and A is the graph's adjacency matrix. Since is a simple graph, 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 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: Labelled graph Adjacency matrix Out-Degree matrix Out-Degree Laplacian In-Degree matrix In-Degree Laplacian 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 oriented incidence matrix B with element Bve for the vertex v and the edge e (connecting vertices and , with i ≠ 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 matrix L defined as
where is the matrix transpose of B.
Undirected graph Incidence matrix Laplacian matrix
An alternative product defines the so-called 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 of the original directed graph and its matrix transpose , where the zero and one entries of are treated as logical, rather than numerical, values, as in the following example: Adjacency matrix Symmetrized adjacency Symmetric Laplacian matrix
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:
where is the Moore–Penrose inverse of the degree matrix.
The elements of 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 of indegree and outdegree can be used for normalization: Adjacency matrix Out-Degree matrix Out-Degree normalized Laplacian In-Degree matrix In-Degree normalized Laplacian
Left (random-walk) and right normalized Laplacians
The left (random-walk) normalized Laplacian matrix is defined as:
where is the Moore–Penrose inverse. The elements of are given by
Similarly, the right normalized Laplacian matrix is defined as .
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 has no isolated vertices, then right stochastic and hence is the matrix of a random walk, so that the left normalized Laplacian has each row summing to zero. Thus we sometimes alternatively call the random-walk normalized Laplacian. In the less uncommonly used right normalized Laplacian each column sums to zero since is left stochastic.
For a non-symmetric adjacency matrix of a directed graph, one also needs to choose indegree 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 to right stochastic , while the right in-degree normalized Laplacian with column-sums all 0 contains left stochastic .
Definitions for graphs with weighted edges 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. In spectral clustering and graph-based signal processing, where graph vertices represent data points, the edge weights can be computed, e.g., as inversely proportional to the distances 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.
Laplacian matrix The Laplacian matrix is defined by
where D is the degree matrix and A is the adjacency matrix of the graph.
For directed graphs, either the indegree 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.
Symmetric Laplacian via the incidence matrix
For graphs with weighted edges one can define a weighted incidence matrix B and use it to construct the corresponding symmetric Laplacian as . An alternative cleaner approach, described here, is to separate the weights from the connectivity: continue using the incidence matrix as for regular graphs and introduce a matrix just holding the values of the weights. A spring system is an example of this model used in mechanics 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 incidence matrix B with element Bve for the vertex v and the edge e (connecting vertexes and , with i > j) defined by
We now also define a diagonal matrix W containing the edge weights. Even though the edges in the definition of B are technically directed, their directions can be arbitrary, still resulting in the same symmetric Laplacian matrix L defined as
where is the matrix transpose of B.
The construction is illustrated in the following example, where every edge is assigned the weight value i, with Undirected graph Incidence matrix Edge weights Laplacian matrix
Symmetric Laplacian for a directed graph 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 of the original directed graph and its matrix transpose as in the following example: Adjacency matrix Symmetrized adjacency matrix Symmetric Laplacian matrix where the zero and one entries of 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 the indegree 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.
Laplacian matrix normalization 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.
Symmetrically normalized Laplacian
The symmetrically normalized Laplacian is defined as