Spectral Clustering from a Cell Graph

From a Cell Graph to a Laplacian

A cell graph represents cells as vertices and neighborhood relationships as edges. In a weighted graph, a larger edge weight means a stronger relationship between the two cells. Spectral clustering uses a matrix built from these weights to find coordinates in which graph-connected cells tend to lie near one another. Clustering those coordinates can reveal a partition that is not obvious from the original high-dimensional expression measurements.

Assume the graph is undirected, its edge weights are nonnegative, and there are no self-loops. Write \(W\) for its symmetric weight matrix, so \(W_{ij}=W_{ji}\geq 0\) and \(W_{ii}=0\). The weighted degree of vertex \(i\) is \(d_i=\sum_j W_{ij}\). The degree matrix \(D\) is diagonal, with \(D_{ii}=d_i\).

The unnormalized Laplacian is often useful for understanding the basic spectral idea. The normalized Laplacian adjusts for degree, which can matter when some cells have many strong graph connections and others have few. The inverse degree matrices in the normalized definitions require positive degrees; an isolated vertex has \(d_i=0\), so it must be handled explicitly rather than inserted into these formulas without adjustment.

Why Low-Eigenvalue Coordinates Reflect Graph Structure

For any real vector \(x\) with one coordinate \(x_i\) per vertex, the Laplacian quadratic form measures how much \(x\) changes across weighted edges. Because \(W\) is symmetric and \(d_i=\sum_j W_{ij}\), expanding \(x^\mathsf{T}(D-W)x\) gives

Each term on the right is nonnegative. If two vertices have a large edge weight, assigning them very different coordinates incurs a large penalty. Thus vectors with small Laplacian quadratic form are smooth across strong connections.

The spectral theorem for real symmetric matrices gives an orthonormal set of eigenvectors for \(L\), with real, nonnegative eigenvalues. The smallest eigenvalue is 0, with the constant vector as an eigenvector. A vector for the next-smallest eigenvalue, often called the Fiedler vector, is the smoothest nonconstant direction: it minimizes \(x^\mathsf{T}Lx\) among unit-length vectors orthogonal to the constant vector. Further low-eigenvalue eigenvectors provide additional smooth directions.

The last statement is a useful structural clue, not a guarantee that the graph has a uniquely correct clustering. Eigenvectors specify coordinates; a separate step turns the coordinates into labels. For two groups, a threshold on a Fiedler vector can be used. For \(k\) groups, a common approach is to use the first \(k\) eigenvectors as coordinates and apply \(k\)-means to the resulting rows.

A Practical Spectral-Clustering Procedure

A common normalized procedure uses the symmetric normalized Laplacian. It is designed to reduce the influence of raw degree differences, but it still requires positive degrees and a choice of the number of groups \(k\). One standard version is:

The row normalization in step 3 is part of a widely used normalized spectral-clustering variant, not a universal requirement for every spectral method. The unnormalized approach instead uses eigenvectors of \(L\), while normalized alternatives use \(L_{\mathrm{sym}}\) or \(L_{\mathrm{rw}}\). Their coordinates and sensitivity to degree can differ, so the Laplacian and embedding choices should be reported rather than treated as interchangeable implementation details.

Diagnostics, Alternatives, and Limitations

Before interpreting a spectral partition, check the graph and the spectral calculation. Confirm that weights are nonnegative and symmetric, that the degree distribution is as expected, and that there are no unhandled isolated vertices. Inspect the smallest eigenvalues: several exact or near-zero values can indicate disconnected or weakly connected regions. Check whether the proposed partition cuts a few strong edges or instead separates many strongly connected neighbors. If small eigenvalues are tightly clustered, the corresponding eigenvectors may not define a stable orientation on their own; different numerical bases for the same eigenspace can produce different coordinates.

A common mistake is to treat any low-eigenvalue eigenvector as a set of cluster labels. An eigenvector gives a continuous coordinate, and its sign or magnitude is not automatically a categorical assignment. The correction is to state the embedding and partitioning step explicitly—for example, thresholding a Fiedler vector for a two-way split or clustering rows of a selected eigenvector matrix. Also avoid interpreting a spectral cluster as a proven cell type: the result depends on the graph construction, edge weights, chosen \(k\), Laplacian, and downstream partitioning.

Spectral clustering differs from the community-detection methods already encountered in this unit. Modularity-based methods seek partitions that score well under a comparison with a degree-based random-graph reference, while Infomap uses the coding cost of random walks. Spectral clustering instead derives low-dimensional coordinates from eigenvectors of a Laplacian, then partitions those coordinates. All three approaches can use a cell graph, but their objectives and outputs need not agree. Spectral methods can be computationally demanding for very large graphs because they require eigenvectors, and their results may depend on the selected number of groups and the choice between normalized and unnormalized coordinates.

The central justification is the smoothness identity: strong edges penalize large coordinate differences, so low-eigenvalue directions tend to preserve strongly connected neighborhoods. This explains why spectral coordinates can expose weak connections between groups. It does not establish that every graph has a meaningful discrete partition; the graph must represent relevant cell relationships, and the resulting groups still require appropriate scientific interpretation.