Discrete Laplacian (2)

In our previous post, we explored the Laplacian in both continuous and discrete forms, and how they are related. Now, we will concentrate on the properties of the Laplacian, particularly its eigenvalues, which are the most significant.

If you look up the eigenvalues of the Laplacian matrix you can find statements like the below:

• The smallest non-zero eigenvalue is called the “algebraic connectivity” of the graph, and it provides information about the connectedness of the graph. A larger algebraic connectivity value indicates that the graph is more strongly connected.
• The second smallest eigenvalue is called the “Fiedler value”, and it has applications in graph partitioning. The Fiedler value is related to the size of the smallest cut in the graph, which separates the graph into two connected components.
• In general, the eigenvalues of the Laplacian matrix provide information about the graph’s spectrum, which can be used to study various properties of the graph, such as its clustering structure, centrality, and community structure.

It can be challenging to understand the connection between the eigenvalue or spectral analysis of the Laplacian matrix and its “connectedness.” In this section, we aim to find a clearer way to grasp this concept.

Let’s first define what an eigenvector of matrix A is. If we view A as a transformation matrix, it can be thought of as transforming an input vector, x, into an output vector, y. These x and y vectors can represent states in a system, and matrix A performs a special transformation on x to produce y. This transformation could range from leaving x unchanged to computing the average of x’s neighboring elements and placing the result in x (y).

However, if we keep A fixed, we can also consider various states that A acts upon. For instance, one state of a specific transform matrix A could be a state that remains unchanged or a scaled version of itself. This is the definition of an eigenvector.

For example, if lambda=1 then we can think about x as the steady state! If the system is changing with A it will stay the same.

Now let's go back to the Laplacian Matrix, if we look at Laplacian as a transformation matrix what kind of transformation it is? This can be answered by looking at the formula below from the previous post:

as you can see the value of each state will change to a new value that is the sum of all differences between that state and the neighbors. It is like each state leaks its value to the neighbors. This is a process called dissipation in physics. Dissipation could happen in so many different ways, dissipation of heat, protons, chemicals, or even rumors! let’s focus on heat. In the most general case if I have a graph with the adjacency matrix A then each node has a temperature phi_i and its temperature will change according to Newton’s law of cooling:

The heat transfer from node i to node j is proportional to phi_i-ph_j if there is a link between i and j

There is a very important detail here: the heat doesn’t transfer instantly according to the difference, instead the transfer rate is proportional to the difference, so we write:

In which k is the heat conductivity. Now we show that this is exactly the Laplacian.

In matrix form:

which gives:

You can use standard methods to solve this equation, but what I want to emphasize is the underlying intuition. What this equation says is pretty simple: we can find the next temperature by applying the Laplacian to an initial state phi_0 and get a new state phi_1, or in general:

To find the final steady state it’s enough to compute when the second term is zero:

This is called the Laplace equation and in this case, is a simple system of linear equations. if the graph is connected it’s easy to know that the answer to steady state is when all the nodes have the same temperature and that temperature is equal to the average of all the initial temperatures (when the temperature is fully dissipated and the graph is homogenous).

But what about the eigenvectors of L? if we calculate the eigenvector phi_i of L:

by plugging this back into the equation:

this is a very famous equation and shows the exponential decay of phi_i. the rate of decay (considering k=1) is proportional to -lambda_i, the greater the lambda the faster the decay! Now let’s take a look at the eigenvalues: In the Laplacian matrix if we sort the eigenvalues the first one is always zero (if the graph is connected, think why). The zero eigenvalue in the equation above reduces down to the Laplace equation that we just mentioned. It means in the connected graph eventually all the nodes will be at equilibrium. But the next biggest eigenvalue shows the slowest decay: The slowest rate of decay occurs when heat is confined in isolated parts of the graph due to insufficient connectivity with the rest of the graph. To illustrate this, consider two extreme examples: one with two fully connected components that are connected by a single link, and another that is a fully connected graph. In the first case, we can expect the heat to quickly reach equilibrium within each component but take longer to transfer from one component to another.

The eigenvalues of this network are:

0, 0.1994, 7, 7, 7, 7, 7, 7.6355, 10, 10, 10, 10, 10, 10, 10, 10, 11.1651

As you can see, the second eigenvalue is very small, indicating a slow rate of decay and weak connectivity. In contrast, the following eigenvalues are much larger, demonstrating strong connectivity throughout the rest of the network.

Now consider all the nodes are connected to each other. Even though we used a slower time step (dt), the speed of convergence is very fast.

In this case, the eigenvalues are:

0, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17
In practice, these two extreme cases are rare, instead, we usually have a continuum of eigenvalues.

By adding more edges to the graph we can go from lower eigenvalues to higher.

As you can see, the number of zeros indicates the disconnected parts of the graph. If the second eigenvalue is zero, it means that the heat will be trapped in two parts of the graph indefinitely, which mathematically translates to having two Laplace equations (one for the first eigenvalue and another for the second eigenvalue). The lower the eigenvalue, the less connected the graph is. The subsequent eigenvalues reflect the connectivity within smaller clusters of the graph.

With this additional information, you can revisit the first three bullet points and gain a better understanding of them.