Spectral Clustering Explained: Graph Laplacian & Eigenvector

ملخص

Pixel shares an introduction to spectral clustering and how graph Laplacian eigenvectors help identify clusters with complex shapes, such as crescents and rings. The article covers graph construction, the clustering process, and its limitations, helping the community understand when this method can outperform K-means.

DEV Community

Spectral Clustering: Why the Eigenvectors of a Graph Laplacian Reveal Clusters

K-means is the first clustering method most people learn, and it is also the first one to fail in an instructive way. Give it two interleaving crescents, two concentric rings, or a long thin chain next to a dense ball, and it will cut straight through the structure you can see with your eyes. The failure is not a tuning problem. K-means assumes clusters are round blobs around a centre, and it measures closeness in raw Euclidean distance. When the shape of a cluster matters more than its centre, that assumption is wrong. Spectral clustering takes a different route. Instead of clustering points directly, it first turns the data into a graph, then asks a linear algebra question about that graph: which smooth, low-energy functions on the graph separate one region from another? The answer is given by the smallest eigenvectors of the graph Laplacian. Cluster in that eigenvector space, and crescents, rings, and chains suddenly become easy. This article explains what the Laplacian is, why its eigenvectors encode cuts, how the full algorithm works, and where it breaks down. From points to a graph Start with data points x1,…,xn . Spectral clustering does not work on the points themselves. It works on a weighted graph in which each point is a node and each edge weight wij measures how similar points i and j are. Similar points get a heavy edge, dissimilar points get a light edge or no edge at all. The clustering problem then becomes a graph partitioning problem: cut the graph into pieces so that few heavy edges are cut and each piece is internally well connected. The graph construction is the first real decision, and it matters more than most textbooks admit. Three common choices are: Epsilon neighbourhood graph: connect points closer than some radius ϵ . k-nearest-neighbour graph: connect each point to its k nearest neighbours, usually symmetrised by keeping an edge if either endpoint lists the other. Fully connected graph with a Gaussian kernel: connect everything, with weight decaying with distance. The Gaussian kernel is the usual default for a fully connected graph: wij=exp(−2σ2∣xi−xj∣2) Here σ is a scale parameter. Small σ makes the graph local: only genuinely near neighbours matter, and distant structure is ignored. Large σ makes the graph dense and blurs local detail. There is no universally correct σ , and a bad one can destroy the result before any eigenvectors are computed. In practice, a k-nearest-neighbour graph is often more robust than a fully connected Gaussian graph, because it adapts to varying density: a point in a sparse region still gets neighbours, and a point in a dense region is not swamped by weak long-range edges. Collect the weights into a similarity matrix W , with entries wij and zeros on the diagonal. Define the degree of node i as the total weight of its edges: di=j=1∑nwij Put the degrees on the diagonal of a matrix D . The unnormalised graph Laplacian is then: L=D−W That simple definition carries a surprising amount of structure. What the Laplacian measures Take any function f on the nodes, a vector with one value fi per point. The quadratic form fTLf has a clean expansion: fTLf=21i=1∑nj=1∑nwij(fi−fj)2 Read that carefully, because it is the whole intuition in one line. The quadratic form is a weighted sum of squared differences across edges. If f assigns similar values to strongly connected points, the sum is small. If f jumps across a heavy edge, the sum is large. So a function with small fTLf is smooth on the graph: it varies slowly inside well-connected regions and only changes where the graph is weakly connected. That is exactly what a cluster indicator should do. An ideal cluster indicator is constant inside each cluster and jumps only between clusters. If clusters correspond to weakly connected regions, the jump crosses only light edges, so the quadratic form stays small. Spectral clustering is, in this sense, a search for smooth functions on the graph. The Laplacian is symmetric and positive sem...
Spectral Clustering Explained: Graph Laplacian & Eigenvector
Powered by Readybot.io

الأحدث من Pixel

Incident Response: Look Beyond the Red Alert

Pixel’s DEV Community announcement explores how teams can fixate on one failing service while overlooking the real cause of an outage, such as a full …

Sach: AI Fact-Checks WhatsApp Forwards in India

Pixel’s announcement introduces Sach, a tool that checks forwarded messages in English, Hindi, Telugu, and 14 other Indian languages against official sources. It gives cited …

Java 25 Removes SecurityManager: What to Fix

Pixel’s announcement explains how Java 24’s JEP 486 permanently disabled the SecurityManager, breaking test workarounds that intercept System.exit. It recommends returning exit codes or throwing …

Why a Java HPA Got Stuck at 20 Kubernetes Pods

Pixel shares how a Spring Boot pricing service autoscaled to 20 Kubernetes pods and stayed there because the JVM retained committed heap memory after traffic …