Graphs, Laplacians, and Spectral Structure

A feature matrix describes objects one row at a time. A graph adds edges that state which pairs interact, resemble one another, or exchange information. The adjacency matrix records those links. The degree matrix records how strongly each node is connected. Combining them produces a graph Laplacian, an operator that measures variation across edges. This mathematics supports spectral clustering, graph smoothing, diffusion, and many graph neural network intuitions.

What those two matrices actually weigh varies by orders of magnitude, and the sizes are published. The Open Graph Benchmark, released in 2020, lists exact counts for the graphs its Laplacians would be built from. ogbn-papers100M has 111,059,956 nodes and 1,615,685,872 edges, at an average degree of 29.1. The paper introduces it in one line: “ogbn-papers100M is an extremely large paper citation network from the entire MAG with more than 100 million nodes and 1 billion edges.” In the same suite, ogbn-proteins has 132,534 nodes and 39,561,252 edges at average degree 597.0. ogbl-collab has 235,868 nodes and 1,285,465 edges at average degree 8.2. That is roughly a seventy-fold spread in mean degree between benchmark graphs offered side by side. The diagonal of D is never a formality, and the warning about hubs later in this lesson has teeth.

Given a node signal x, the quantity xᵀLx equals a weighted sum of squared differences across edges, up to a conventional factor. It is small when connected nodes have similar values. This makes the Laplacian a discrete smoothness operator. Minimizing Laplacian energy encourages neighboring nodes to share information.

The conventional factor is not folklore. It is the difference between two published statements of one identity. Mohar writes the inner product (Q(G)x,x) as the sum over edges vu of a_vu (x_v - x_u)^2, with no leading constant. Von Luxburg writes f'Lf = 1/2 sum w_ij (f_i - f_j)^2. The one-half appears because the double sum over ordered pairs counts every edge twice. Her tutorial also carries the positive semidefiniteness and the component count that Mohar's Theorem 2.1 states. Same theorem, different bookkeeping. A reader who copies an energy value from one convention into a threshold tuned under the other is out by a factor of two.

The conclusion is only as trustworthy as the graph. Wrong edges can smooth together objects that should remain distinct.

Different Laplacians encode different geometry and lead to different algorithms. The unnormalized form L = D − A uses raw edge and degree scale. Its energy interpretation is the simplest, and it is natural for combinatorial arguments. It is also sensitive to degree variation, and it can let hubs dominate. The random-walk form Lrw = I − D⁻¹A connects to random-walk transitions, so its rows relate to neighbor averaging. It is useful for diffusion intuition, asymmetric in the ordinary inner product, and requires care with isolated nodes. The symmetric form Lsym = I − D⁻¹ᐟ²AD⁻¹ᐟ² normalizes by degree on both sides. It supports orthogonal eigenvectors, balances degree effects, and is the common choice in spectral clustering. It still depends on edge construction.

“Sensitive to degree variation” is a bullet point. There is a theorem underneath it. The tutorial's author and two colleagues published it in The Annals of Statistics in 2008, and their abstract states the result plainly: “As a result, we can prove that one of the two major classes of spectral clustering (normalized clustering) converges under very general conditions, while the other (unnormalized clustering) is only consistent under strong additional assumptions, which are not always satisfied in real data.”

A later section of the tutorial turns that into a check you can run on your own matrix, rather than a preference you assert. The eigenvalues of L you cluster on must lie far below the minimum degree min_j d_j. Eigenvectors belonging to eigenvalues above min_j d_j approximate Dirac functions, and a Dirac function splits a single vertex off from the rest instead of finding a group. So compute the k eigenvalues you intend to use, read off the smallest degree in the graph, and compare the two numbers. If they are close, the unnormalized form is not the safe default it looks like.

Each object plays a distinct role in the geometry of the network. The adjacency A stores edge weights between pairs of nodes. The degree D places each node's total incident weight on the diagonal. The Laplacian L = D − A measures disagreement between neighboring node values. A normalized Laplacian adjusts for degree so hubs do not dominate every comparison. The eigenvectors of L provide smooth coordinate directions over the graph.

The normalization step in that chain has been measured, not merely recommended. Thomas Kipf and Max Welling held the graph fixed — Cora — and varied only the propagation operator, in a 2017 paper on graph convolutional networks. The renormalized symmetric operator D̃^-1/2 à D̃^-1/2, with à = A + I, scored 81.5% accuracy. (I + D^-1/2 A D^-1/2) scored 79.2%. D^-1/2 A D^-1/2 alone scored 80.5%. The first-order model scored 80.0%, and a Chebyshev filter with K=3 scored 79.5%. A multilayer perceptron that ignores the graph entirely scored 55.1%. Every normalization choice in that table lands between 79.2% and 81.5%; the model that throws the graph away lands at 55.1%. The edges carry far more than the choice of how to scale them. Scaling them is still worth measuring.

The self-loop was introduced for a numerical reason, and the paper says so: “Repeated application of this operator can therefore lead to numerical instabilities and exploding/vanishing gradients when used in a deep neural network model.” A 2019 paper, Simplifying Graph Convolutional Networks, later proved what the self-loop is doing. It shrinks the largest normalized-Laplacian eigenvalue, from 2 to about 1.5 on Cora.

There is a graph on which the spectral answer is provably wrong, and it is small enough to draw by hand. Stephen Guattery and Gary L. Miller built it in 1995 and called it the roach. The family G_k is planar, has maximum degree 3, and is made from two paths of 3k vertices joined by k rungs — an edge from vertex 2k+i to 5k+i for 1 <= i <= k. Their own description: “A graph in our first counterexample class looks like a ladder with the top 2/3 of its rungs kicked out (see Figure 1); a straightforward spectral bisection algorithm cuts the remaining rungs, where the optimal bisection is made by cutting across the ladder above the remaining rungs.” The optimal bisection cuts 2 edges, across the antennae. Their Theorem 4.1 shows the simple spectral method produces Theta(n) separators on this family, the proof establishing that a bisection taken on the second Laplacian eigenvector must cut at least half the rungs. Half the rungs, where two edges would have done.

Spectral methods fail most often because edge semantics were never audited. Six steps, in order. Define nodes: state what one node represents, and at what time. Define edges: explain whether links mean interaction, similarity, dependency, or proximity. Choose weights: set scales, kernels, and thresholds using domain evidence. Inspect degree: find hubs, isolated nodes, and construction artifacts. Select normalization: match the Laplacian to the objective and to the degree distribution. Stress-test edges: remove, perturb, or time-split them to test spectral stability.

Steps 1 and 2 have a public worked example, and it is the graph most spectral and graph-learning papers benchmark on. In Cora, one node is a machine-learning paper and one edge is a citation link. The corpus holds 2,708 papers in seven classes with 5,429 citation links. Each node's features come from a 1,433-word vocabulary, produced by stemming, removing stop words, and dropping every word with document frequency below 10. Prithviraj Sen and five co-authors stated the counts in AI Magazine in 2008: “The final corpus has 2708 documents, 1433 distinct words in the vocabulary, and 5429 links in the case of Cora; and 3312 documents, 3703 distinct words in the vocabulary, and 4732 links in the case of CiteSeer.”

That is what an audited step 1 and step 2 look like: a stated unit, a stated link type, and a preprocessing chain fixed before any spectrum is computed. It is also checkable by a third party. Kipf and Welling list Cora as 2,708 nodes, 5,429 edges, 7 classes and 1,433 features, and Simplifying Graph Convolutional Networks independently lists 2,708 nodes and 5,429 edges. If your own graph cannot be described to a stranger in one sentence per step, and counted the same way twice, steps 3 through 6 are being run on an object nobody has defined.