Origins of the Graph Laplacian

Question

I understand the definition and the properties of a graph Laplacian but is there any text around how it was derived and what steps led to its discovery? I ask this because it seems rather arbitrary that if we did define the Laplacian as L = D - A then we would find interesting properties ith its eigenvectors and eigenvalues.

Answer 1

The definition of the graph Laplacian is motivated by the associated quadratic form $\mathbf x^{\mathsf T}L \mathbf x$, which can be written as a sum $$ \sum_{ij \in E(G)} (x_i - x_j)^2. $$ This is one of the most natural quadratic forms you could define to encode the edges of a graph. (What else could you take a sum of, over all edges $ij$? You could add up $(x_i + x_j)^2$, and then you'd get the signless Laplacian. You could add up $x_i x_j$, and then you'd get half the adjacency matrix. All of those are also things we study.)

In addition, this particular quadratic form is extra convenient, because trying to find a vector $\mathbf x$ that minimizes it (subject to some conditions) means that $\mathbf x$ assigns values that are close together to adjacent vertices (since we want $(x_i - x_j)^2$ to be small whenever $ij$ is an edge). This is what leads to the nice combinatorial interpretations of the Laplacian's eigenvalues.