3  Components and the Graph Laplacian

Properties of the Graph Laplacian

We now investigate the mathematical properties of the graph Laplacian. We’ll leave proofs of many of these properties as exercises. Throughout, this section, let \(\mathbf{L} \in \mathbb{R}^{n\times n}\) be the combinatorial Laplacian matrix of a graph \(G\) on \(n\) nodes, and let \(\mathbf{1} \in \mathbb{R}^n\) be the vector of ones.

Another important property of the Laplacian is that it is positive semi-definite.

Because the Laplacian is symmetric, this is equivalent to:

Can we get more specific about the spectral structure of the eigenvalues? In fact, we already have one important piece of information:

Furthermore, the multiplicity of the zero eigenvalue gives us information about the number of connected components in the network:

Here’s an example of applying this theorem: we’ll construct a graph with 3 connected components and show that the Laplacian has 3 zero eigenvalues.

Show code

fig, ax = plt.subplots(1, 1, figsize = (3, 2))
G = nx.Graph()
G.add_edges_from([(1, 2), (2, 3), (2,5), (2,6), (3, 4), (3, 7), (4, 3), (4, 8), (5, 1), (5, 6), (6, 7), (7, 6), (8, 4), (8, 7), (9, 10), (10, 11), (11, 9), (12, 13), (13, 14), (14, 12)])

pos = nx.planar_layout(G)

plot_kwargs.update({"node_size" : 100})

nx.draw(G,pos, ax = ax, **plot_kwargs)

Now we can check that there are exactly 3 zero eigenvalues.

L = laplacian(G)

eigvals, eigvecs = np.linalg.eig(L)
num_0_eigs = np.isclose(eigvals, 0, atol = 1e-10).sum() # number of zero eigenvalues
print("Number of zero eigenvalues: ", num_0_eigs)

Number of zero eigenvalues:  3

Show code

fig, ax = plt.subplots(1, 2, figsize = (7, 3), gridspec_kw={'width_ratios': [1.5, 1]})

G = nx.stochastic_block_model([10, 10], [[0.5, 0.02], [0.02, 0.5]], seed = 1234)

pos = nx.spring_layout(G, seed = 1234)

L = laplacian(G)
eigvals, eigvecs = np.linalg.eig(L)
# eigvecs[:,1]

nx.draw(G, pos, ax = ax[0], node_color = eigvecs[:,1], node_size = 100, cmap = "BrBG", edge_color = 'gray', width = 0.5, edgecolors = "white")

ax[1].scatter(np.arange(len(eigvals)), np.sort(eigvals), facecolor = 'white', edgecolor = 'black')

ax[1].set(xlabel = "Eigenvalue index", ylabel = "Eigenvalue of Laplacian")

The eigenvalue on the very far left is the zero eigenvalue guaranteed for any graph, while the very small eigenvalue right next to it reflects the structure of the graph as “almost disconnected” into two components.

The Graph Laplacian as a Smoothness Measure

Suppose that we have a vector \(\mathbf{x} \in \mathbb{R}^n\), where we interpret entry \(x_i\) as describing some quantity at node \(i\). The Laplacian matrix can be used to measure the “smoothness” of this vector on the graph, by which we mean the extent to which neighboring nodes have similar values of \(x\). One way to quantify this is using the measure

\[ \begin{aligned} S(\mathbf{x}) = \frac{1}{2}\sum_{i = 1}^n \sum_{j = 1}^n A_{ij}(x_i - x_j)^2 \,. \end{aligned} \]

The term corresponding to \(i\) and \(j\) in \(S(\mathbf{x})\) is zero if either \(A_{ij} = 0\) (i.e. node \(i\) is not connected to node \(j\)) or if \(x_i = x_j\) (i.e. nodes \(i\) and \(j\) have the same values in their corresponding entries of \(\mathbf{x}\)). So, intuitively, \(S(\mathbf{x})\) is small when connected nodes have similar entries in \(\mathbf{x}\) and large when connected nodes have very different entries in \(\mathbf{x}\). The Laplacian can be used to concisely represent the smoothness measure \(S(\mathbf{x})\):

\[ \begin{aligned} S(\mathbf{x}) &= \frac{1}{2}\sum_{i = 1}^n \sum_{j = 1}^n A_{ij}(x_i - x_j)^2 \\ &= \frac{1}{2} \sum_{i = 1}^n \sum_{j = 1}^n A_{ij}(x_i^2 - 2x_ix_j + x_j^2) \\ &= \frac{1}{2} \sum_{i = 1}^n \sum_{j = 1}^n A_{ij}x_i^2 - \sum_{i = 1}^n \sum_{j = 1}^n A_{ij}x_ix_j + \frac{1}{2}\sum_{i = 1}^n \sum_{j = 1}^n A_{ij}x_j^2 \\ &= \frac{1}{2} \sum_{i = 1}^n k_i x_i^2 - \sum_{i = 1}^n \sum_{j = 1}^n A_{ij}x_ix_j + \frac{1}{2} \sum_{j = 1}^n k_j x_j^2 \end{aligned} \]

In the last line, we’ve used the definition of the degree: \(k_i = \sum_{j = 1}^n A_{ij}\). Now we need to use an indexing trick. Let \(\delta_{ij}\) be the Kronecker delta, which is 1 if \(i = j\) and 0 otherwise. Then, we can write

\[ \begin{aligned} \frac{1}{2} \sum_{i = 1}^n k_i x_i^2 + \frac{1}{2} \sum_{j = 1}^n k_j x_j^2 = \sum_{i = 1}^n\sum_{j = 1}^n \delta_{ij} k_i x_i x_j\;, \end{aligned} \]

which allows us to write our entire smoothness measure as

\[ \begin{aligned} S(\mathbf{x}) &= \sum_{i = 1}^n\sum_{j = 1}^n \left(\delta_{ij} k_i - A_{ij}\right)x_ix_j \\ &= \sum_{i = 1}^n\sum_{j = 1}^n L_{ij}x_ix_j \\ &= \mathbf{x}^T\mathbf{Lx} \,. \end{aligned} \]

So, our smoothness measure is the quadratic form \(\mathbf{x}^T\mathbf{Lx}\). The role of the Laplacian in measuring the smoothness of functions defined on graphs is another perspective on its use in both algorithms and modeling of dynamical systems.

To operationalize this, let’s implement a smoothness score:

def smoothness(G, x): 
    L = laplacian(G)
    return x@L@x

Now we can compare the smoothness of a random vector with the smoothness of a vector that varies in a more continuous fashion across the graph. I’ve obtained the smooth vector as the eigenvector corresponding to the second-smallest eigenvalue (as in the example above), but this isn’t important in this context; it’s just one convenient way to get a smooth vector.

Show code

G = nx.random_geometric_graph(50, 0.25, seed = 1234)
pos = nx.kamada_kawai_layout(G)

n = G.number_of_nodes()
fig, ax = plt.subplots(1, 2, figsize = (6, 3))

# nonsmooth version, normalized
x_random = np.random.rand(n)
x_random = x_random / np.linalg.norm(x_random)

nx.draw(G, pos, node_color = x_random, ax = ax[0], node_size = 30, edge_color = "grey", edgecolors = "white", width = 0.5, cmap = "BrBG")
ax[0].set_title(f"Smoothness: {smoothness(G, x_random):.2f}")

# smooth version, normalized
L = laplacian(G)
x_smooth = np.linalg.eig(L)[1][:,1]
x_smooth = x_smooth / np.linalg.norm(x_smooth)

nx.draw(G, pos, node_color = x_smooth, ax = ax[1], node_size = 30, edge_color = "grey", edgecolors = "white", width = 0.5, cmap = "BrBG")

title = ax[1].set_title(f"Smoothness: {smoothness(G, x_smooth):.2f}")

Indeed, the vector which varies more smoothly across the graph (with fewer large large “jumps” along edges) has a much smaller smoothness score.

The Graph Laplacian as a Diffusion Operator

\[ \begin{aligned} \mathbf{x} \gets \mathbf{x} -\alpha\mathbf{Lx} \,, \end{aligned} \]

where \(\alpha\) is some constant that describes the rate of heat transfer. Let’s see how this looks:

from matplotlib import pyplot as plt
import networkx as nx
import numpy as np

fig, axarr = plt.subplots(2, 3, figsize = (7, 3.7))

# create a network for visualization and set up a layout
n = 50
rad = 0.25
G = nx.random_geometric_graph(n, rad, seed = 1234)

layout = nx.kamada_kawai_layout(G)

# construct the Laplacian matrix
A = nx.to_numpy_array(G)
D = np.diag(np.sum(A, axis = 1))
L = D - A

# rate of heat transfer
rate = 0.12

# initial condition: all heat on a single node
x = np.zeros(n)
x[20] = 10

# main loop
for i, ax in enumerate(axarr.flatten()):
    nx.draw(G, ax = ax, node_size = 20, edge_color = 'gray', node_color = x, width = 0.5, pos = layout, cmap = "coolwarm", vmin = 0, vmax = 1)
    ax.set_title("$t = " + str(i) + "$")

    # Laplacian dynamical update
    x -= rate*L@x

The Laplacian operator also has many other applications in network science, many of which we will study later in these notes.