Implementing The Spectral Graph Partitioning Algorithm: Fiedler Vector And K Means

2026-04-27 · Leonardo Benicio

Summary

A comprehensive technical exploration of implementing the spectral graph partitioning algorithm: fiedler vector and k means, covering key concepts, practical implementations, and real-world applications.

Contents

Spectral Graph Partitioning: From Intuition to Implementation (and Everything In Between)

Imagine you are given the task of dividing a large social network into tightly knit communities, each with minimal connections to the others. Or perhaps you need to segment an image into coherent regions by cutting along natural boundaries between pixels. These problems—whether in network analysis, image processing, VLSI design, or load balancing—share a common core: you have an undirected graph and you must partition its vertices into groups such that the number of edges crossing between groups is as small as possible. This is the classic graph partitioning problem, and it is NP‑hard in its general form. Yet, remarkably, a beautiful piece of mathematics—the spectral decomposition of the graph Laplacian—offers a computationally tractable relaxation that produces high‑quality partitions in practice. At the heart of this approach lies the Fiedler vector, the eigenvector associated with the second smallest eigenvalue of the Laplacian. When combined with a simple clustering algorithm like K‑means, it becomes an elegant and powerful method for multi‑way partitioning, known as spectral graph partitioning.

Why should you care? Graph partitioning is everywhere. In distributed computing, you want to split computation tasks across machines while minimizing communication. In social network analysis, you want to detect communities. In scientific computing, you partition sparse matrices for parallel solvers. In data science, you use spectral clustering to identify clusters in high‑dimensional spaces. The spectral approach is not only practical—it is theoretically grounded: the Fiedler vector provides a continuous approximation to the optimal discrete partition, and the resulting cut values are often near‑optimal. Moreover, the algorithm is remarkably simple to implement, requiring only basic linear algebra and a clustering routine. Yet many tutorials either dive too deep into esoteric mathematics or skip the crucial intuition.

In this comprehensive guide, we will walk through every step of spectral graph partitioning with the Fiedler vector and K‑means. We will start with the fundamental concepts of graph cuts and the Laplacian, then derive the spectral relaxation, explore the meaning of the Fiedler vector, and finally show how to extend it to multiple partitions using an eigenvector embedding and K‑means. Along the way, we will present concrete examples with code (using Python and NumPy/SciPy), discuss practical pitfalls, and connect the method to real‑world applications in image segmentation, social network analysis, and parallel computing. By the end, you will not only understand why spectral partitioning works but also know how to implement it from scratch and adapt it to your own problems. Let’s begin.

1. The Graph Partitioning Problem: A Formal Setup

Before diving into spectral methods, we need a precise mathematical formulation. Let ( G = (V, E) ) be an undirected graph with ( n = |V| ) vertices and ( m = |E| ) edges. We assume the graph is weighted, with a weight function ( w: E \to \mathbb{R}^+ ). For simplicity, we often consider unweighted graphs (all weights = 1), but all results extend naturally.

A cut is a partition of the vertex set into two disjoint subsets ( A ) and ( B = V \setminus A ). The cut value (or cut size) is the sum of weights of edges crossing from ( A ) to ( B ):

[ \text{cut}(A, B) = \sum*{i \in A, j \in B} w*{ij}. ]

The goal of graph bipartitioning is to find a subset ( A ) (nonempty and not the whole set) that minimizes this cut value. However, minimizing the raw cut favors cutting off isolated vertices (e.g., a single vertex with low degree), which is usually not meaningful. To obtain balanced partitions, we normalize the cut by the size or volume of the parts. Two common objective functions are:

Ratio Cut: (\displaystyle \text{RatioCut}(A,B) = \frac{\text{cut}(A,B)}{|A|} + \frac{\text{cut}(A,B)}{|B|})
Normalized Cut: (\displaystyle \text{NCut}(A,B) = \frac{\text{cut}(A,B)}{\text{vol}(A)} + \frac{\text{cut}(A,B)}{\text{vol}(B)}), where (\text{vol}(A) = \sum_{i \in A} d_i) (sum of degrees in (A)).

Both objectives penalize unbalanced partitions. The Ratio Cut is suitable for unweighted graphs where vertex count matters; Normalized Cut is common in image segmentation (Shi and Malik, 2000). Both are NP‑hard to optimize exactly, which leads us to relaxations.

Why Spectral Methods?

Spectral graph theory provides a way to relax these discrete optimization problems into continuous eigenvalue problems. The key object is the graph Laplacian matrix. For a graph with adjacency matrix ( A ) (entries ( a*{ij} = w*{ij} )) and degree matrix ( D = \text{diag}(d_1,\dots,d_n) ), the unnormalized Laplacian is:

[ L = D - A. ]

The Laplacian has several remarkable properties:

It is symmetric and positive semidefinite.
Its eigenvalues are real and non‑negative: ( 0 = \lambda_1 \le \lambda_2 \le \dots \le \lambda_n ).
The eigenvector for ( \lambda_1 = 0 ) is the constant vector ( \mathbf{1} ) (all ones), because ( L\mathbf{1} = 0 ).
The multiplicity of eigenvalue 0 equals the number of connected components of the graph.

The second smallest eigenvalue ( \lambda_2 ) and its associated eigenvector ( \mathbf{v}_2 ) (often called the Fiedler vector, after Miroslav Fiedler) play a central role in graph partitioning. In fact, Rayleigh quotient characterization gives:

[ \lambda2 = \min{\mathbf{x} \perp \mathbf{1},; \mathbf{x} \neq 0} \frac{\mathbf{x}^T L \mathbf{x}}{\mathbf{x}^T \mathbf{x}}. ]

And we can rewrite the numerator as:

[ \mathbf{x}^T L \mathbf{x} = \sum*{(i,j) \in E} w*{ij} (x_i - x_j)^2. ]

Thus, minimizing the Rayleigh quotient over vectors orthogonal to the constant vector is equivalent to finding a continuous assignment of real numbers to vertices that varies as little as possible across edges, while not being constant. This is precisely a relaxed version of the cut problem: if we restrict entries of ( \mathbf{x} ) to be ( +1 ) or ( -1 ), then ( \sum*{ij} w*{ij}(x_i - x_j)^2 = 4\cdot\text{cut}(A,B) ), with ( A = {i: x_i = +1}, B = {i: x_i = -1} ). The orthogonality constraint ( \mathbf{x}^T \mathbf{1} = 0 ) forces the partition to be balanced (equal numbers of +1 and -1 in the unweighted case, but not exactly because the Laplacian relaxation uses continuous values).

The Fiedler vector ( \mathbf{v}_2 ) is the solution to this continuous relaxation. Its entries indicate how “close” each vertex is to one side of a natural cut: vertices with positive entries tend to belong to one cluster, negative entries to the other. In practice, we often use the sign of the Fiedler vector as a partitioning threshold, or we perform a sweep over sorted entries to find the best Ratio Cut or Normalized Cut (the sweep cut approach).

2. The Graph Laplacian: Deep Dive into Eigenvalues and Eigenvectors

To build a solid foundation, let’s examine the Laplacian more carefully with a small example. Consider a path graph with 4 vertices: vertices 1–2–3–4 (edges (1,2), (2,3), (3,4)). Unweighted, unit degree for interior vertices? Actually degrees: d1=1, d2=2, d3=2, d4=1. The Laplacian matrix is:

[ L = \begin{pmatrix} 1 & -1 & 0 & 0\ -1 & 2 & -1 & 0\ 0 & -1 & 2 & -1\ 0 & 0 & -1 & 1 \end{pmatrix}. ]

Its eigenvalues can be computed analytically for a path: (\lambda_k = 2 - 2\cos(\frac{k\pi}{n+1})) for k=1..n. Here n=4: (\lambda_1=0), (\lambda_2=2-2\cos(2\pi/5)\approx 0.382), (\lambda_3=2-2\cos(3\pi/5)\approx 1.382), (\lambda_4=2-2\cos(4\pi/5)\approx 1.618). The Fiedler vector for this graph is proportional to ((\sin(\pi/5), \sin(2\pi/5), \sin(3\pi/5), \sin(4\pi/5)) \approx (0.588, 0.951, 0.951, 0.588)). Notice the symmetry: the eigenvector does not have a clear sign cut because the graph is symmetric? Actually, the eigenvector entries are all positive? Wait, for a path graph, the Fiedler vector entries are all positive? Let’s check: for a connected graph, Fiedler vector entries are not necessarily all positive; they can have both signs if the graph is symmetric. For this path, the Fiedler vector (eigenvector for λ2) is: (0.3717, 0.6015, 0.6015, 0.3717) after normalization? Actually, compute eigenvectors: the exact values are: v2 = (sin(π/5), sin(2π/5), sin(3π/5), sin(4π/5)). Note that sin(π/5) ≈ 0.5878, sin(2π/5)≈0.9511, sin(3π/5)=sin(2π/5)=0.9511, sin(4π/5)=sin(π/5)=0.5878. All are positive! So Fiedler vector is strictly positive for a path graph? That seems to conflict with the idea of using sign for cut. Actually, the typical property: for a connected graph, the Fiedler eigenvector (associated with λ2) can be either strictly positive or can have both signs depending on the graph’s structure. For a tree, it is known that the Fiedler vector entries are all non-zero and have exactly one sign change? Let’s clarify: in a path, the Fiedler vector is monotonically increasing from one end to the middle then decreasing, but all entries are positive. That means sign threshold would put all vertices in one cluster. That’s not useful. So what’s going on?

The confusion arises because the eigenvector is not unique: if v is an eigenvector, -v is also an eigenvector. For the path, we chose the eigenvector that is positive. But there is also the possibility of a negative version: -v would have all negative entries. Still, sign does not create a partition. For many graphs, however, the Fiedler vector does have both positive and negative entries. For instance, consider a graph consisting of two cliques connected by a single edge (a “barbell”). The Laplacian’s second eigenvector will have entries that are positive on one clique and negative on the other. The sign naturally separates the two clusters.

For the simple path, the Fiedler vector is positive because the graph is one-dimensional and the boundary is at the ends? Actually, for a path of even length, the Fiedler vector is symmetric and has both positive and negative? Let’s test a path of 3 vertices: vertices 1-2-3. Laplacian: diag(1,2,1) with off-diagonals -1. Eigenvalues: λ1=0, λ2=1, λ3=3. Eigenvector for λ2: (1, 0, -1) (or scaled). That has both signs. For n=4, why did we get all positive? Let me recalc: The eigenvector for λ2 of a path graph is given by entry k: sin(kπ/(n+1)). For n=4, k=1..4: sin(π/5)=0.5878, sin(2π/5)=0.9511, sin(3π/5)=sin(2π/5)=0.9511, sin(4π/5)=sin(π/5)=0.5878 – all positive. For n=3: sin(π/4)=0.7071, sin(2π/4)=1, sin(3π/4)=0.7071 – all positive again? Wait, that contradicts the eigenvector I computed for 3 vertices. Let’s compute properly for 3-vertex path. Standard formula: for a path graph with n vertices, the eigenvalues are λ_k = 2 - 2 cos(kπ/(n+1)). For n=3, k=1: λ=2-2cos(π/4)=2-√2≈0.586, k=2: λ=2-2cos(2π/4)=2-2cos(π/2)=2, k=3: λ=2-2cos(3π/4)=2+√2≈3.414. The eigenvectors: for k=2, we have cos(π/4)=? Actually, the eigenvector components for a path (assuming vertices numbered 1..n) are sin(π k j / (n+1)). For k=2, j=1: sin(2π1/4)=sin(π/2)=1; j=2: sin(2π2/4)=sin(π)=0; j=3: sin(2π*3/4)=sin(3π/2)=-1. So eigenvector (1,0,-1). This matches my earlier memory. But the formula sin(kπ j/(n+1)) for k=2 and n=3 gives j=1: sin(2π/4)=1, j=2: sin(4π/4)=sin(π)=0, j=3: sin(6π/4)=sin(3π/2)=-1. Yes. For n=4, k=2: sin(2π j/5). j=1: sin(2π/5)≈0.9511; j=2: sin(4π/5)=sin(π-π/5)=sin(π/5)=0.5878; j=3: sin(6π/5)=sin(π+π/5)=-sin(π/5)=-0.5878? Wait, careful: sin(6π/5)=sin(π+π/5) = -sin(π/5) = -0.5878. j=4: sin(8π/5)=sin(2π-2π/5)=-sin(2π/5)≈ -0.9511. So for n=4, the eigenvector is approximately (0.9511, 0.5878, -0.5878, -0.9511). That has both signs! My earlier claim was wrong; I mistakenly used sin(kπ j/(n+1)) with k=1 for the second eigenvalue? Wait, the second smallest eigenvalue is k=2 (since k=1 gives zero). So for path of 4 vertices, eigenvector for λ2 is given by k=2, not k=1. That’s why earlier I used sin(π j/5) which is for k=1 (which gives λ1=0 eigenvector? Actually, λ1=0 eigenvector is constant, not sin. Let’s clarify the standard derivation. For a path graph with Dirichlet boundary conditions (fixed ends?), the eigenvectors of the Laplacian are sin functions, but the indexing is tricky. To avoid confusion, let’s compute numerically using Python. I will include a code snippet later. The important takeaway: the Fiedler vector of a path graph does have both positive and negative entries, making sign-based partitioning feasible. For a path, the entries increase then decrease through zero, so the sign cut occurs near the middle, giving a balanced partition.

So the earlier mistake serves as a lesson: always verify with explicit computation. Now, let’s move on.

3. The Spectral Relaxation: From Ratio Cut to Fiedler Vector

We now formalize the connection between the Ratio Cut and the Laplacian. Define an assignment vector ( \mathbf{x} \in \mathbb{R}^n ) with entries:

[ x_i = \begin{cases} \sqrt{\frac{|B|}{|A|}} & \text{if } i \in A,\ -\sqrt{\frac{|A|}{|B|}} & \text{if } i \in B. \end{cases} ]

Then one can show (see Von Luxburg, 2007) that:

[ \mathbf{x}^T L \mathbf{x} = |V| \cdot \text{RatioCut}(A,B), \quad \text{and} \quad \mathbf{x}^T \mathbf{1} = 0, \quad |\mathbf{x}|^2 = |V|. ]

Thus, minimizing RatioCut over partitions ( A,B ) is equivalent to minimizing (\mathbf{x}^T L \mathbf{x}) subject to (\mathbf{x}) taking only two specific values and being orthogonal to (\mathbf{1}). If we drop the discreteness constraint and allow (\mathbf{x}) to be any real vector, we get:

[ \min_{\mathbf{x} \perp \mathbf{1}, ; |\mathbf{x}|=1} \mathbf{x}^T L \mathbf{x} = \lambda_2, ]

attained by the Fiedler eigenvector. This is the spectral relaxation of the Ratio Cut. The quality of the relaxation is captured by Cheeger’s inequality (for graphs):

[ \frac{\lambda_2}{2} \leq h(G) \leq \sqrt{2\lambda_2}, ]

where ( h(G) ) is the Cheeger constant (or isoperimetric number), defined as:

[ h(G) = \min_{A: |A| \le |V|/2} \frac{\text{cut}(A, V\setminus A)}{|A|}. ]

Cheeger’s inequality tells us that the second eigenvalue gives a lower and upper bound on the best possible ratio cut. Moreover, a sweep over the Fiedler vector (sorting vertices by their values, then considering all prefix cuts) yields a cut whose ratio is at most ( \sqrt{2\lambda_2} ). So the Fiedler vector not only provides a relaxation but also a way to construct a provably good cut.

For the Normalized Cut, we use the normalized Laplacian ( L*{\text{sym}} = D^{-1/2} L D^{-1/2} ) or ( L*{\text{rw}} = D^{-1} L ). The second smallest eigenvalue of these matrices corresponds to the relaxed Normalized Cut. The corresponding eigenvector (after appropriate transformation) is used for partitioning. The algorithm remains similar.

Now that we have the theoretical background, let’s see how to use the Fiedler vector for bipartitioning and then for multi‑way partitioning with K‑means.

4. The Fiedler Vector: How to Use It for Bipartitioning

Given a graph, compute the Laplacian matrix ( L ) (or normalized variant). Then compute the eigenvector corresponding to the second smallest eigenvalue. In practice, for large sparse graphs, we use iterative methods like the Lanczos algorithm (e.g., SciPy’s eigsh for symmetric sparse matrices). The simplest partitioning method is sign cut: assign vertices with positive eigenvector entries to one cluster, negative to the other. However, this can produce unbalanced clusters if the distribution of entries is not symmetric. A better approach is the sweep cut: sort vertices by their entry in the Fiedler vector, evaluate the cut value (or Ratio Cut) for every prefix partition (first k vertices as cluster A, rest as B), and pick the one with the smallest cut ratio.

Let’s illustrate with a small synthetic example. We’ll create a graph with two obvious clusters connected by a few edges. Use Python with NumPy and NetworkX.

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
from scipy.sparse.linalg import eigsh
from scipy.sparse import csgraph

# Create a graph of two cliques (10 nodes each) connected by 3 edges
G = nx.Graph()
G.add_edges_from([(i,j) for i in range(10) for j in range(i+1,10)])  # clique 0-9
G.add_edges_from([(i+10,j+10) for i in range(10) for j in range(i+1,10)])  # clique 10-19
# Add 3 inter-cluster edges
G.add_edges_from([(0,10), (1,11), (2,12)])

# Compute Laplacian
L = nx.laplacian_matrix(G).asfptype()
# Compute eigenvalues, getting the smallest ones
eigvals, eigvecs = eigsh(L, k=3, which='SM')  # 3 smallest eigenvalues (including zero)
print("Eigenvalues:", eigvals)
fiedler = eigvecs[:, 1]  # second eigenvector (index 1)
# Sign cut
clusters = (fiedler >= 0).astype(int)
print("Cluster assignments:", clusters)
# Plot graph colored by sign cut
pos = nx.spring_layout(G, seed=42)
colors = ['red' if c==0 else 'blue' for c in clusters]
nx.draw(G, pos, node_color=colors, with_labels=False)
plt.title("Sign cut on Fiedler vector")
plt.show()

This will likely correctly separate the two cliques, with the three inter-cluster edges being the only crossing edges. The Fiedler vector entries will be roughly constant on each clique, with opposite signs.

But what if the clusters are not so clean? For example, consider a graph where the partition is more subtle—like a ring of nodes with a “bottleneck” (a narrow connection). The Fiedler vector still reveals the cut.

Now, for multi‑way partitioning (>2 clusters), the sign cut or sweep cut only gives two groups. To get, say, k clusters, we need a different strategy.

5. Multi‑Way Partitioning: Embedding with the First k Eigenvectors and K‑Means

A natural extension of the spectral method to more than two clusters is to use the first k eigenvectors of the Laplacian (excluding the trivial constant eigenvector). Let ( \mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_k ) be the eigenvectors corresponding to the k smallest eigenvalues (with ( \mathbf{v}_1 = \mathbf{1} ) for connected graphs). Form an ( n \times k ) matrix ( U ) where the i-th row is the vector of the i-th vertex’s coordinates in this low‑dimensional space: ( u_i = (v_2(i), v_3(i), \dots, v_k(i)) ) (or sometimes we include ( v_1 ) but it’s constant so irrelevant). Then apply K‑means clustering to the rows of ( U ). This is the essence of spectral clustering (Ng, Jordan, Weiss, 2002) and works remarkably well.

Why does this embedding help? If the graph has k well‑separated clusters, the Laplacian will have a block‑diagonal structure (after permuting vertices). In that ideal case, the eigenvectors for the k smallest eigenvalues are piecewise constant: each eigenvector indicates membership in one cluster. The rows of ( U ) then collapse to k distinct points (one per cluster), making K‑means perfect. In practice, even when clusters are not perfectly separated, the embedding “stretches” the clusters apart because the eigenvectors capture the global connectivity structure.

Normalization Matters

For the normalized Laplacian, a common practice is to normalize each row of ( U ) to unit length (so that vertices lie on the unit sphere). This often improves performance, especially when degree varies. The resulting algorithm is the normalized spectral clustering of Ng, Jordan, and Weiss.

Algorithm summary (spectral clustering with K‑means):

Compute the graph Laplacian ( L ) (or normalized version).
Compute the eigenvectors ( \mathbf{v}{1}, \mathbf{v}{2}, \dots, \mathbf{v}_{k} ) (excluding the constant eigenvector if using unnormalized Laplacian; for normalized, you keep k eigenvectors including the first, but then row‑normalize).
Form matrix ( U \in \mathbb{R}^{n \times k} ) with columns ( \mathbf{v}_2, \dots, \mathbf{v}_k ) (or ( \mathbf{v}_1,\dots,\mathbf{v}_k ) and then row‑normalize).
Treat each row of ( U ) as a point in ( \mathbb{R}^k ). Cluster them with K‑means into k clusters.
Assign original vertex i to the cluster of its corresponding row.

Let’s implement this for a classic synthetic dataset: the “two moons” problem, where points are arranged in two interleaving half‑circles. We construct a k‑nearest neighbor graph from the points, then run spectral clustering.

from sklearn.datasets import make_moons
from sklearn.cluster import KMeans
from sklearn.neighbors import kneighbors_graph
from scipy.sparse import csgraph
import numpy as np

X, y = make_moons(n_samples=200, noise=0.05, random_state=0)
# Build k-NN graph
A = kneighbors_graph(X, n_neighbors=10, mode='connectivity', include_self=False)
L = csgraph.laplacian(A, normed=True)  # normalized Laplacian (symmetric)

# Compute smallest 2 eigenvectors (expect 2 clusters)
eigvals, eigvecs = np.linalg.eigh(L.toarray())  # for small dense matrix
# First eigenvector is constant, second is useful
U = eigvecs[:, :2]  # actually we want second smallest? Let's sort ascending
idx = np.argsort(eigvals)
eigvals = eigvals[idx]
eigvecs = eigvecs[:, idx]
# Smallest eigenvalue is ~0, eigenvector constant; we take next two: indices 1 and 2 (but k=2 clusters => we use only one? Wait, for 2 clusters we typically use 2 eigenvectors? Standard spectral clustering: for k clusters, take k eigenvectors. Here k=2, so we take eigenvectors corresponding to the smallest 2 eigenvalues (excluding constant? Actually, the first eigenvalue is 0, eigenvector constant. If we take both 0 and λ2, the constant gives no discriminating info. So we take eigenvectors for λ2 and λ3? Or just λ2? Many formulations: use the 2 eigenvectors associated with the 2 smallest eigenvalues (including 0) and then row-normalize? Let's follow Ng et al.: form U from eigenvectors of normalized Laplacian corresponding to the k smallest eigenvalues, then normalize rows. So for k=2, we take the two eigenvectors with smallest eigenvalues (0 and λ2). The constant eigenvector is included but row normalization will make all rows equal? Actually, row normalization divides each row by its norm; if the first column is constant, it doesn't affect relative distances after normalization? It's safer to skip the constant eigenvector. The typical implementation for normalized Laplacian: compute eigenvectors of L_sym, keep the ones corresponding to the k smallest eigenvalues (including 0?), then row-normalize. But the eigenvector for 0 is constant, so after row normalization, it contributes equally to the norm of each row? Let's check: If we have two columns: one constant (c) and one varying (v_i). The row norm is sqrt(c^2 + v_i^2). After normalization, the first column becomes c / sqrt(c^2+v_i^2) which varies with i, so it's not constant. So it can help. However, in practice, many implementations use the eigenvectors for eigenvalues 2..k+1 (i.e., skip the zero eigenvalue). We'll adopt that for simplicity.

# so take eigenvectors for indices 1 and 2 (0-indexed after sorting)
U = eigvecs[:, 1:3]  # shape (200, 2)
# Now run K-means on rows of U
kmeans = KMeans(n_clusters=2, random_state=0, n_init=10)
labels = kmeans.fit_predict(U)
# Plot
plt.scatter(X[:,0], X[:,1], c=labels, cmap='viridis')
plt.title("Spectral clustering on two moons")
plt.show()

This should correctly separate the two moons, whereas K‑means on raw data would fail because the clusters are not convex. That’s the power of spectral embedding.

6. Code Examples in Depth

Let’s now provide a more detailed example that walks through each step with careful explanation. We’ll generate a small weighted graph with known communities, compute spectral partitioning, and evaluate the result using normalized mutual information (NMI) or adjusted Rand index.

We’ll use the “stochastic block model” (SBM) to generate a graph with 3 clusters of 30 nodes each, with higher intra‑cluster edge probability than inter‑cluster.

import numpy as np
from sklearn.cluster import KMeans
from scipy.sparse import csgraph, diags
from scipy.sparse.linalg import eigsh
import networkx as nx
import matplotlib.pyplot as plt

# Generate SBM graph
n_per_cluster = 30
n_clusters = 3
n = n_per_cluster * n_clusters
probs = [[0.5, 0.05, 0.05],
         [0.05, 0.5, 0.05],
         [0.05, 0.05, 0.5]]
G = nx.stochastic_block_model([n_per_cluster]*n_clusters, probs, seed=42)
# Convert to adjacency matrix as sparse
A = nx.adjacency_matrix(G)
# Compute unnormalized Laplacian
d = np.array(A.sum(axis=1)).flatten()
L = diags(d) - A

# Compute k smallest eigenvectors (k=3)
eigvals, eigvecs = eigsh(L, k=3, which='SM')  # returns sorted ascending
print("Eigenvalues:", eigvals)
# The eigenvectors form an n x 3 matrix. We'll use all three (including constant? Actually, smallest eigenvalue is ~0, eigenvector constant. For 3 clusters, we need 3 eigenvectors? Standard spectral clustering for k clusters uses k eigenvectors of the Laplacian (excluding the trivial one? Or including? Let's include all k=3 and then row-normalize? For unnormalized Laplacian, including constant eigenvector is fine but row-normalization may not help as much. Many implementations skip the constant eigenvector and take the next k eigenvectors (2,3,4). Since we expect 3 clusters, we can take eigenvalues and eigenvectors for indices 0,1,2 (where index 0 corresponds to smallest eigenvalue ≈0). However, using the constant eigenvector tends to make the embedding more robust? Let's test both.)

# Option A: use vectors for λ2, λ3, λ4 (skip the trivial)
U = eigvecs[:, 1:4]  # shape (90, 3) but we only have 3 eigenvectors, so index 1:4 gives 2 eigenvectors (columns 1 and 2). Wait, we computed k=3 smallest eigenvalues, so indices 0,1,2. Skip index 0 gives columns 1 and 2 -> that's only 2 eigenvectors. For 3 clusters we need at least 3 dimensions? Actually, spectral clustering with k clusters typically uses k eigenvectors (excluding the constant). For k=3, we need eigenvectors for λ2, λ3, λ4, i.e., compute at least 4 eigenvectors. So let's recompute with k=4.

eigvals, eigvecs = eigsh(L, k=4, which='SM')
U = eigvecs[:, 1:4]  # columns 1,2,3 (λ2,λ3,λ4)
# Row-normalize (optional)
U = U / np.linalg.norm(U, axis=1, keepdims=True)
# K-means
kmeans = KMeans(n_clusters=n_clusters, random_state=0, n_init=10)
pred_labels = kmeans.fit_predict(U)
# True labels (block index)
true_labels = np.repeat(range(n_clusters), n_per_cluster)
# Compute accuracy (permutation invariant)
from sklearn.metrics import adjusted_rand_score
ari = adjusted_rand_score(true_labels, pred_labels)
print("Adjusted Rand Index:", ari)
# Visualize graph colored by predicted clusters
pos = nx.spring_layout(G, seed=42)
colors = ['red','blue','green']
node_colors = [colors[pred_labels[i]] for i in range(n)]
nx.draw(G, pos, node_color=node_colors, node_size=50, with_labels=False)
plt.title("Spectral clustering (unnormalized Laplacian)")
plt.show()

This code demonstrates a complete pipeline. You can experiment with normalized Laplacian, different number of neighbors if constructing from data, etc.

7. Applications: From Theory to Practice

7.1 Image Segmentation (Normalized Cuts)

One of the most famous applications of spectral partitioning is image segmentation via Normalized Cuts by Shi and Malik (2000). The idea: represent an image as a graph where each pixel is a vertex, and edge weights measure similarity in color, texture, and spatial proximity. Then partition the graph using the normalized cut criterion, computed via the normalized Laplacian. The second smallest eigenvector indicates a bimodal partition; recursively apply to each segment or use multi‑way spectral clustering. This yields segmentation that respects natural boundaries.

We can illustrate with a simple grayscale image: construct a grid graph where each pixel connects to its 4‑neighbors, with weight ( w_{ij} = \exp(-(I_i - I_j)^2 / \sigma^2) ). Then compute the Fiedler vector and threshold to get a foreground‑background separation.

7.2 Social Network Community Detection

In social networks, communities are groups of vertices with many internal edges and few external edges. Spectral clustering can detect these communities. For example, in the karate club network (Zachary’s dataset), spectral clustering using the Fiedler vector (or first few eigenvectors) correctly splits the network into two factions that align with real divisions. For multiple communities, take more eigenvectors.

We can load the karate club graph from NetworkX and run spectral clustering:

G = nx.karate_club_graph()
L = nx.laplacian_matrix(G).asfptype()
eigvals, eigvecs = eigsh(L, k=3, which='SM')
fiedler = eigvecs[:, 1]
# sign cut
clubs = ['Officer' if v>=0 else 'Mr. Hi' for v in fiedler]
# Compare with ground truth (club membership after split)
ground_truth = [G.nodes[i]['club'] for i in range(len(G))]
# Compute accuracy (note: assignment may be flipped)

7.3 Parallel Computing and Load Balancing

In high‑performance computing, large sparse matrices must be partitioned across processors to balance work and minimize communication. This is essentially a graph partitioning problem. Software like METIS and ParMETIS are widely used, but spectral partitioning also plays a role, especially in graph drawing and mesh partitioning. The spectral method tends to produce well‑shaped partitions with good cut quality, though it is more expensive than multilevel methods. However, for moderate‑sized graphs, spectral partitioning can be competitive.

7.4 Dimensionality Reduction and Clustering in Data Science

Spectral clustering is a staple of unsupervised learning. Given a set of data points in high dimensions, we construct a similarity graph (k‑NN or fully connected with Gaussian kernel), then run spectral clustering. This has the advantage of handling arbitrary cluster shapes (e.g., two moons, concentric circles) that K‑means on raw data fails. The embedding step essentially performs nonlinear dimensionality reduction capturing the manifold structure.

8. Practical Considerations and Pitfalls

8.1 Computational Cost

The main bottleneck is computing eigenvectors of an ( n \times n ) matrix. For dense matrices, this is ( O(n^3) ), impossible for large n. However, graphs are sparse (edges ( m = O(n) ) in many applications). Iterative eigensolvers like Lanczos (implemented in eigsh for sparse matrices) can find the smallest k eigenvectors in ( O(mk + nk^2) ) time, which is feasible for graphs with millions of vertices if k is small (say, < 100). For very large graphs, one can use the Nyström method or random projection techniques to approximate the eigenvectors.

8.2 Choosing the Number of Clusters k

Determining k is a challenge. Common heuristics:

Eigengap heuristic: look for a gap in the eigenvalue sequence. If the first k eigenvalues are very small and ( \lambda_{k+1} ) is significantly larger, this suggests k clusters (since eigenvalues close to 0 correspond to near‑disconnected components).
Silhouette score on the embedded points.
Stability analysis: cluster with different random seeds and see how consistent the results are.

8.3 Graph Construction for Point Clouds

When using spectral clustering on data points, the graph construction (choice of similarity kernel, parameter σ, number of neighbors) strongly influences results. Using a fixed σ may give bad results for varying density. Self‑tuning spectral clustering (Zelnik-Manor and Perona) adapts the local scale.

8.4 Normalized vs Unnormalized Laplacian

The unnormalized Laplacian tends to favor equal‑sized clusters (penalizes small ones) because the objective is related to Ratio Cut. The normalized Laplacian (using ( D^{-1/2}LD^{-1/2} )) corresponds to Normalized Cut, which is more robust to degree variation. In practice, normalized spectral clustering is often preferred for data clustering, while unnormalized may be used when degrees are uniform.

8.5 Out‑of‑Sample Extensions

Standard spectral clustering is transductive: you cannot easily assign a new vertex to a cluster without recomputing eigenvectors. There are extensions using the Nyström method or learning a classifier on the embedding, but they are approximations.

8.6 Comparison with Other Partitioning Methods

Multilevel methods (METIS): much faster, often produce comparable cut quality, but may not capture global structure as well as spectral methods in certain scenarios (e.g., manifolds).
Markov clustering (MCL): different principle based on random walks.
Louvain method for community detection: optimizes modularity, not cut based.
Flow‑based methods (Kernighan‑Lin): heuristic local search for improving cuts.

Spectral methods provide a mathematically elegant and often high‑quality solution, but they are not always the fastest or most scalable.

9. Going Deeper: Cheeger’s Inequality and Influence on Modern Algorithms

Cheeger’s inequality, originally from differential geometry, was adapted to graphs by Dodziuk and Alon. It provides a theoretical guarantee that the Fiedler eigenvalue bound the best possible ratio cut. The proof involves constructing a cut based on the level sets of the Fiedler vector. This insight led to the spectral sweep cut algorithm.

Furthermore, the inequality has spurred research into higher‑order Cheeger inequalities (for the k‑th eigenvalue) and algorithms for partitioning into more than two parts using the first k eigenvectors. Recent works connect spectral clustering to graph neural networks and Laplacian eigenmaps.

10. Conclusion

Spectral graph partitioning is a masterpiece of applied mathematics—a discrete combinatorial problem relaxed into a continuous eigenvalue problem, with strong theoretical guarantees and practical success across many domains. The Fiedler vector, as the eigenvector corresponding to the second smallest eigenvalue of the graph Laplacian, provides an optimal 1‑dimensional embedding for bipartitioning. For multi‑way partitioning, stacking multiple eigenvectors and applying K‑means yields the powerful spectral clustering algorithm.

In this blog post, we have covered:

The graph Laplacian and its eigenvalues.
The connection between Ratio Cut, Normalized Cut, and the Fiedler vector.
The spectral relaxation and Cheeger’s inequality.
How to use the Fiedler vector for bipartitioning (sign cut, sweep cut).
Multi‑way partitioning with the first k eigenvectors and K‑means.
Detailed code examples for synthetic and real data.
Practical considerations and pitfalls.

Now you have the tools to apply spectral graph partitioning to your own problems. Whether you are segmenting an image, finding communities in a social network, or balancing computational load across processors, the spectral approach offers a principled and effective solution. The next time you encounter a graph partitioning challenge, reach for the Laplacian, compute its eigenvectors, and let the Fiedler vector guide your cut.