Laplacian matrix

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. The Laplacian matrix can be used to find many useful properties of a graph. Together with Kirchhoff's theorem, it 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 second smallest eigenvalue of its Laplacian by Cheeger's inequality. It can also be used to construct low dimensional embeddings, which can be useful for a variety of machine learning applications.
Definition.
Laplacian matrix for "simple graphs".
Given a simple graph formula_1 with formula_2 vertices, its Laplacian matrix formula_3 is 
defined as:
where "D" is the degree matrix and "A" is the adjacency matrix of the graph. Since formula_5 is a simple graph, formula_6 only contains 1s or 0s and its diagonal elements are all 0s.
In the case of directed graphs, either the indegree or outdegree might be used, depending on the application.
The elements of formula_7 are given by
where formula_9 is the degree of the vertex formula_10.
Symmetric normalized Laplacian.
The symmetric normalized Laplacian matrix is defined as:
The elements of formula_12 are given by
Random walk normalized Laplacian.
The random-walk normalized Laplacian matrix is defined as:
The elements of formula_15 are given by
Generalized Laplacian.
The generalized Laplacian formula_17 is defined as:
Notice the ordinary Laplacian is a generalized Laplacian.
Example.
Here is a simple example of a labelled, undirected graph and its Laplacian matrix.
Properties.
For an (undirected) graph "G" and its Laplacian matrix "L" with eigenvalues formula_19:
Incidence matrix.
Define an formula_31 oriented incidence matrix "M" with element "M""ev" for edge "e" (connecting vertex "i" and "j", with "i" > "j") and vertex "v" given by
Then the Laplacian matrix "L" satisfies
where formula_34 is the matrix transpose of "M".
Now consider an eigendecomposition of formula_7, with unit-norm eigenvectors formula_36 and corresponding eigenvalues formula_37:
Because formula_37 can be written as the inner product of the vector formula_40 with itself, this shows that formula_20 and so the eigenvalues of formula_7 are all non-negative.
Deformed Laplacian.
The deformed Laplacian is commonly defined as
where "I" is the identity matrix, "A" is the adjacency matrix, "D" is the degree matrix, and "s" is a (complex-valued) number. The standard Laplacian is just formula_44 and formula_45 is the signless Laplacian.
Signless Laplacian.
The signless Laplacian is defined as
where formula_47 is the degree matrix, and formula_48 is the adjacency matrix. Like the signed Laplacian formula_49, the signless Laplacian formula_17 also is positive semi-definite as it can be factored as
where formula_52 is the incidence matrix. formula_17 has a 0-eigenvector if and only if it has a bipartite connected component other than isolated vertices. This can be shown as
This has a solution where formula_55 if and only if the graph has a bipartite connected component.
Symmetric normalized Laplacian.
The (symmetric) normalized Laplacian is defined as
where "L" is the (unnormalized) Laplacian, "A" is the adjacency matrix and "D" is the degree matrix. Since the degree matrix "D" is diagonal and positive, its reciprocal square root formula_57 is just the diagonal matrix whose diagonal entries are the reciprocals of the positive square roots of the diagonal entries of "D". The symmetric normalized Laplacian is a symmetric matrix.
One has: formula_58, where S is the matrix whose rows are indexed by the vertices and whose columns are indexed by the edges of G such that each column corresponding to an edge e = {u, v} has an entry formula_59 in the row corresponding to u, an entry formula_60 in the row corresponding to v, and has 0 entries elsewhere. (formula_61 denotes the transpose of S).
All eigenvalues of the normalized Laplacian are real and non-negative. We can see this as follows. Since formula_12 is symmetric, its eigenvalues are real. They are also non-negative: consider an eigenvector formula_63 of formula_12 with eigenvalue λ and suppose formula_65. (We can consider g and f as real functions on the vertices v.) Then:
where we use the inner product formula_67, a sum over all vertices v, and formula_68 denotes the sum over all unordered pairs of adjacent vertices {u,v}. The quantity formula_69 is called the "Dirichlet sum" of f, whereas the expression formula_70 is called the "Rayleigh quotient" of g.
Let 1 be the function which assumes the value 1 on each vertex. Then formula_71 is an eigenfunction of formula_72 with eigenvalue 0.
In fact, the eigenvalues of the normalized symmetric Laplacian satisfy 0 = μ0 ≤ … ≤ μn−1 ≤ 2. These eigenvalues (known as the spectrum of the normalized Laplacian) relate well to other graph invariants for general graphs.
Random walk normalized Laplacian.
The random walk normalized Laplacian is defined as
where "D" is the degree matrix. Since the degree matrix "D" is diagonal, its inverse formula_74 is simply defined as a diagonal matrix, having diagonal entries which are the reciprocals of the corresponding positive diagonal entries of "D".
For the isolated vertices (those with degree 0), a common choice is to set the corresponding element formula_75 to 0.
This convention results in a nice property that the multiplicity of the eigenvalue 0 is equal to the number of connected components in the graph.
The matrix elements of formula_15 are given by
The name of the random-walk normalized Laplacian comes from the fact that this matrix is formula_78, where formula_79 is simply the transition matrix
of a random walker on the graph. For example, let formula_80 denote the i-th standard basis vector. Then formula_81 is a probability vector representing the distribution of a random walker's locations after taking a single step from vertex formula_21; i.e., formula_83. More generally, if the vector formula_84 is a probability distribution of the location of a random walker on the vertices of the graph, then formula_85 is the probability distribution of the walker after formula_86 steps.
One can check that
i.e., formula_15 is similar to the normalized Laplacian formula_12. For this reason, even if formula_15 is in general not hermitian, it has real eigenvalues. Indeed, its eigenvalues agree with those of formula_12 (which is hermitian). 
Graphs.
As an aside about random walks on graphs, consider a simple undirected graph. Consider the probability that the walker is at the vertex "i" at time "t", given the probability distribution that he was at vertex "j" at time "t − 1" (assuming a uniform chance of taking a step along any of the edges attached to a given vertex):
or in matrix-vector notation:
We can rewrite this relation as
formula_97 is a symmetric matrix called the reduced adjacency matrix. So, taking steps on this random walk requires taking powers of formula_98, which is a simple operation because formula_98 is symmetric.
Interpretation as the discrete Laplace operator.
The Laplacian matrix can be interpreted as a matrix representation of a particular case of the discrete Laplace operator. Such an interpretation allows one, e.g., to generalise 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.
Suppose formula_100 describes a heat distribution across a graph, where formula_101 is the heat at vertex formula_21. According to Newton's law of cooling, the heat transferred from node formula_21 to node formula_104 is proportional to formula_105 if nodes formula_21 and formula_104 are connected (if they are not connected, no heat is transferred). Then, for heat capacity formula_108,
In matrix-vector notation,
which gives
Notice that this equation takes the same form as the heat equation, where the matrix −"L" is replacing the Laplacian operator formula_112; hence, the "graph Laplacian".
To find a solution to this differential equation, apply standard techniques for solving a first-order matrix differential equation. That is, write formula_100 as a linear combination of eigenvectors formula_36 of "L" (so that formula_115) with time-dependent coefficients, formula_116
Plugging into the original expression (because "L" is a symmetric matrix, its unit-norm eigenvectors formula_36 are orthogonal):
whose solution is
As shown before, the eigenvalues formula_37 of "L" are non-negative, showing that the solution to the diffusion equation approaches an equilibrium, because it only exponentially decays or remains constant. This also shows that given formula_37 and the initial condition formula_122, the solution at any time "t" can be found.
To find formula_122 for each formula_21 in terms of the overall initial condition formula_125, simply project formula_125 onto the unit-norm eigenvectors formula_36;
This approach has been applied to quantitative heat transfer modelling on unstructured grids.
In the case of undirected graphs, this works because formula_7 is symmetric, and by the spectral theorem, its eigenvectors are all orthogonal. So the projection onto the eigenvectors of formula_7 is simply an orthogonal coordinate transformation of the initial condition to a set of coordinates which decay exponentially and independently of each other.
Equilibrium behavior.
To understand formula_131, the only terms formula_132 that remain are those where formula_133, since
In other words, the equilibrium state of the system is determined completely by the kernel of formula_7. 
Since by definition, formula_136, the vector formula_137 of all ones is in the kernel. If there are formula_108 disjoint connected components in the graph, then this vector of all ones can be split into the sum of formula_108 independent formula_140 eigenvectors of ones and zeros, where each connected component corresponds to an eigenvector with ones at the elements in the connected component and zeros elsewhere.
The consequence of this is that for a given initial condition formula_141 for a graph with formula_142 vertices
where
For each element formula_145 of formula_100, i.e. for each vertex formula_104 in the graph, it can be rewritten as
In other words, at steady state, the value of formula_100 converges to the same value at each of the vertices of the graph, which is the average of the initial values at all of the vertices. Since this is the solution to the heat diffusion equation, this makes perfect sense intuitively. We expect that neighboring elements in the graph will exchange energy until that energy is spread out evenly throughout all of the elements that are connected to each other.
Example of the operator on a grid.
This section shows an example of a function formula_100 diffusing over time through a graph. The graph in this example is constructed on a 2D discrete grid, with points on the grid connected to their eight neighbors. Three initial points are specified to have a positive value, while the rest of the values in the grid are zero. Over time, the exponential decay acts to distribute the values at these points evenly throughout the entire grid.
The complete Matlab source code that was used to generate this animation is provided below. It shows the process of specifying initial conditions, projecting these initial conditions onto the eigenvalues of the Laplacian Matrix, and simulating the exponential decay of these projected initial conditions.
N = 20; % The number of pixels along a dimension of the image
A = zeros(N, N); % The image
Adj = zeros(N * N, N * N); % The adjacency matrix
% Use 8 neighbors, and fill in the adjacency matrix
dx = [- 1, 0, 1, - 1, 1, - 1, 0, 1];
dy = [- 1, - 1, - 1, 0, 0, 1, 1, 1];
for x = 1:N
 for y = 1:N
 index = (x - 1) * N + y;
 for ne = 1:length(dx)
 newx = x + dx(ne);
 newy = y + dy(ne);
 if newx > 0 && newx <= N && newy > 0 && newy <= N
 index2 = (newx - 1) * N + newy;
 Adj(index, index2) = 1;
 end
 end
 end
end
% BELOW IS THE KEY CODE THAT COMPUTES THE SOLUTION TO THE DIFFERENTIAL EQUATION
Deg = diag(sum(Adj, 2)); % Compute the degree matrix
L = Deg - Adj; % Compute the laplacian matrix in terms of the degree and adjacency matrices
[V, D] = eig(L); % Compute the eigenvalues/vectors of the laplacian matrix
D = diag(D);
% Initial condition (place a few large positive values around and
% make everything else zero)
C0 = zeros(N, N);
C0(2:5, 2:5) = 5;
C0(10:15, 10:15) = 10;
C0(2:5, 8:13) = 7;
C0 = C0(:);
C0V = V'*C0; % Transform the initial condition into the coordinate system
% of the eigenvectors
for t = 0:0.05:5
 % Loop through times and decay each initial component
 Phi = C0V .* exp(- D * t); % Exponential decay for each component
 Phi = V * Phi; % Transform from eigenvector coordinate system to original coordinate system
 Phi = reshape(Phi, N, N);
 % Display the results and write to GIF file
 imagesc(Phi);
 caxis([0, 10]);
 title(sprintf('Diffusion t = %3f', t));
 frame = getframe(1);
 im = frame2im(frame);
 [imind, cm] = rgb2ind(im, 256);
 if t == 0
 imwrite(imind, cm, 'out.gif', 'gif', 'Loopcount', inf, 'DelayTime', 0.1);
 else
 imwrite(imind, cm, 'out.gif', 'gif', 'WriteMode', 'append', 'DelayTime', 0.1);
 end
end
Approximation to the negative continuous Laplacian.
The graph Laplacian matrix can be further viewed as a matrix form of an approximation to the (positive semi-definite) Laplacian operator obtained by the finite difference method.
(See Discrete Poisson equation) 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.
Directed multigraphs.
An analogue of the Laplacian matrix can be defined for directed multigraphs. In this case the Laplacian matrix "L" is defined as
where "D" is a diagonal matrix with "D""i","i" equal to the outdegree of vertex "i" and "A" is a matrix with "A""i","j" equal to the number of edges from "i" to "j" (including loops).