Spectral graph theory is the study of the intimate relationship of eigenvalues to different properties of graphs. Most typically the eigenvalues are associated to eigenfunctions of matrices associated to graphs known as Laplacians. Let $latex G = (V, E)$ be a weighted or unweighted undirected graph (there are simple extensions to directed graphs for many problems). Let $latex A$ be the adjacency matrix and let $latex D$ be the diagonal degree matrix, that is, $latex (D)_{ii} = d_i$, the degree of vertex $latex i$. Then a common definition for the Laplacian is $latex L = D-A$.
As I develop in my research in spectral graph theory, I am consistently amazed by the truth that many results in spectral graph theory can be seen as discrete analogues to results in spectral geometry. I am not accustomed to thinking of graphs as geometric objects, but in fact graph Laplacian matrices are nicely related to Laplace operators on Riemannian manifolds. In this post, I’d like to discuss a few of these relationships.
Discretizing a membrane
Let’s consider a simple example. Imagine a membrane in the $latex xy$ plane with vertical displacement given by $latex z(x, y)$. Then the movement of the membrane can be described by the wave equation:
$latex \Delta z = \frac{1}{c^2}\cdot\frac{\partial^2 z}{\partial t^2}, \ \ \ \ \ \ \ (1)$
where $latex t$ represents time, $latex c$ is the speed of the wave, and $latex \Delta$ is the Laplace operator acting on the function $latex z$. If we assume the membrane moves like a spring, Hooke’s law gives us
$latex \frac{\partial^2 z}{\partial t^2} = -kz,$
where $latex k$ is a constant representing the stiffness of the spring. Then, plugging
this in to (1), our wave equation simplifies to
$latex -\Delta z = \frac{k}{c^2}z. \ \ \ \ \ \ \ (2)$
In other words, $latex z$ is an eigenfunction of the Laplace operator $latex \Delta$. We’ll return to this in a bit, but for now let’s do a little magic on the left side of the equation.
The Laplace operator returns the sum of second partial derivatives, so we can expand the above as
$latex \frac{\partial^2 z}{\partial x^2}+\frac{\partial^2 z}{\partial y^2} = \frac{1}{c^2}\cdot\frac{\partial^2 z}{\partial t^2}.$
Suppose we want to approximate the membrane by a discrete grid of size $latex w$.
That is, we would like to approximate the continuous Laplacian on the left side of the equation. First, we have that
$latex \frac{\partial z(x,y)}{\partial x} \approx \frac{z(x,y) – z(x-w,y)}{w},$
$latex \frac{\partial z(x,y)}{\partial y} \approx \frac{z(x,y) – z(x,y-w)}{w}$
so we can approximate the second partial derivative with respect to $latex x$ by
$latex \frac{\partial^2 z(x,y)}{\partial x^2} \approx \frac{\frac{\partial z(x+w,y)}{\partial x} – \frac{\partial z(x,y)}{\partial x}}{w} = \frac{z(x+w,y) + z(x-w,y) – 2z(x,y)}{w^2},$
and similarly for $latex y$. Then the left side of (2) becomes:
$latex -\Delta z \approx \frac{4z(x,y) – z(x+w,y) – z(x-w,y) – z(x,y+w) – z(x, y-w)}{w^2}.$
(This is the finite difference method.) Now recall, this was derived by approximating the membrane by a discrete mesh. Let’s visualize a few points on the grid:
If we instead consider these points as nodes and edges in a graph, and use the graph Laplacian $latex L = D-A$ as our operator. Then we can see that
$latex Lz(x,y) = 4z(x,y) – z(x+w,y) – z(x-w,y) – z(x,y+w) – z(x, y-w).$
But this is exactly the (unnormalized) approximated discrete Laplacian above! Remarkable! Now we’re beginning to see that this whole graph “Laplacian” nomenclature has some substance after all, it really is a discrete analogue of the Laplace operator!
Manifolds or graphs?
Beyond their operations, there are elegant parallels between the Riemannian manifold setting and the discrete graph setting for Laplacians. For example, let $latex U \subset \mathbb{R}^d$ be an open, non-empty set and let $latex L^2(U)$ denote the space of square integrable functions on $latex U$. Then the domain of the Laplace operator $latex D(\Delta)$ is the space of smooth, compactly supported functions on $latex U$ and dense in $latex L^2(U)$. Then a first property is that the Laplace operator is symmetric on $latex D(\Delta)$. Similarly, the Laplacian $latex L$ is a symmetric matrix. Another parallel is the range of the spectra of $latex \Delta$ and $latex L$. On $latex \mathbb{R}^n$, the spectrum of $latex \Delta$ is $latex [0,\infty)$, and similarly $latex L$ has all non-negative real eigenvalues (that is, it is always positive semidefinite).
According to spectral graph theorist Fan Chung, it is possible to treat the continuous and discrete cases by a universal approach:
The general setting is as follows:
- an underlying space $latex M$ with a finite measure $latex \mu$;
- a well-defined Laplace operator $latex \mathcal{L}$ on functions on $latex M$ [a matrix or a graph] so that $latex \mathcal{L}$ is a self-adjoint operator in $latex L^2(M,\mu)$ with a discrete spectrum;
- if $latex M$ has a boundary then the boundary condition should be chosen so that
it does not disrupt self-adjointness of $latex \mathcal{L}$;- a distance function $latex dist(x,y)$ on $latex M$ so that $latex |\nabla dist| \leq 1$ for an appropriate notion of gradient.
(Chung, Spectral Graph Theory, 48.)
Boundary conditions and hearing the shape of a graph
The spectrum of the continuous Laplace operator gained due recognition with the famous question posed by Mark Kac: can you hear the shape of a drum? The question essentially asked whether drums can be isospectral, or share eigenvalues.
Specifically, let’s model a drum as a membrane stretched and clamped over a boundary, represented by some domain $latex D$ in the plane. Let $latex \lambda_i$ be the Dirichlet eigenvalues, defined by
$latex -\Delta u = \lambda u,$
with the constraint that $latex u = 0$ on the boundary of $latex D$ (consider the membrane from equation (2) with a boundary, for instance). Then these Dirichlet eigenvalues are precisely the fundamental tone and harmonics the drum can produce. The question, then, is: given the set of Dirichlet eigenvalues, can we infer the shape of the drum? That is, do there exist distinct isospectral domains in the plane?
We can describe a similar problem in the discrete case. Let $latex G$ be a graph and $latex S$ and induced subgraph with non-empty vertex boundary (the set of vertices not in $latex S$ but adjacent to vertices in $latex S$). Then we say a function $latex f: V \rightarrow \mathbb{R}$ satisfies the Dirichlet boundary condition when $latex f(v) = 0$ for every vertex $latex v$ in the vertex boundary of $latex S$. Then, for some function $latex f$ satisfying the Dirichlet boundary condition, the Dirichlet eigenvalues of $latex G$ with respect to $latex S$ are the $latex \lambda_i$ satisfying
$latex \mathcal{L}f(v) = \lambda f(v)$
for every $latex v$ in $latex S$. Note here that $latex \mathcal{L}$ is the normalized Laplacian given by $latex \mathcal{L} = D^{-1/2}LD^{-1/2}$. Then an analagous question is: given the set of Dirichlet eigenvalues, can we infer the shape of $latex S$?
The answer to both questions turns out to be yes. The first construction of isospectral drums in two dimensions was given by Gordon, Webb, and Wolpert in 1992, and toward the end of the 2000 ought’s, Ram Band, Ori Parzanchevski, and Gilad Ben-Shach gave a construction of isospectral drums and graphs (a follow up is here).
The not-so-scary continuous cousin
So, as it turns out the “Laplacian” name of our star player in spectral graph theory is not so arbitrary, and there are many parallels between the continuous Laplace operator and the discrete graph Laplacian. As I continue to enrich my understanding of the connections between the two cases, I can only hope that the power of the Laplace operator will help me gain intuition about the power of the graph Laplacian. To conclude, I leave the reader with a few words from Chung’s book:
For almost every known result in spectral geometry, a corresponding [question] can be asked: Can the results be translated to graph theory?
Chung, Spectral Graph Theory, 54.
A special thanks to Kyle Mooney for the images.