Spectral Clustering with a Fiedler Cut

Worked Example

Consider an undirected four-node path graph with nodes 0, 1, 2, 3 and edge weights(0,1) = 1, (1,2) = w = 0.1, and (2,3) = 1.

The unnormalized Laplacian L = D - A is a 4x4 matrix. The second smallest eigenvalue (algebraic connectivity) for this specific graph is given by the formula:

λ2 = 1 + w - √(1 + w2)

1. Substituting w = 0.1: λ2 = 1 + 0.1 - √(1 + 0.01) ≈ 1.1 - 1.004987562 ≈ 0.09501243788791114
2. The corresponding eigenvector (Fiedler vector) v takes the form [a, (1 - λ2)a, -(1 - λ2)a, -a].
3. To make v a unit vector (norm 1), we find a such that: 2a2 + 2(1 - λ2)2a2 = 1, which gives a = 1 / √(2(1 + (1 - λ2)2))
4. Using λ2 ≈ 0.095012, 1 - λ2 ≈ 0.904987.
   a ≈ 1 / √(2(1 + 0.819002)) ≈ 1 / √3.638004 ≈ 0.5242861144024794
5. Thus, the selected coordinate for Vertex 0 is 0.5242861144024794. By partitioning based on the sign of the eigenvector components, we split the nodes into groups where v[i] > 0 and v[i] ≤ 0. Here, nodes 0 and 1 are positive, and nodes 2 and 3 are negative, resulting in the partition 0,1 | 2,3.
6. The normalized cut score for this partition is exactly 2w / (2 + w) = 2(0.1) / (2.1) ≈ 0.09523809523809523.

Experiment

We can visualize how the algebraic connectivity and partition change interactively. Follow these steps to observe the calculation in action:

1. Open the Spectral Clustering with a Fiedler Cut module.
2. Set the Bridge weight to 1. Notice that the graph is now a uniform path. The second eigenvalue increases to roughly 0.585786, and the normalized cut score becomes 0.666666.
3. Change the Bridge weight to 0. The graph is now disconnected into two components (0-1 and 2-3). The second eigenvalue is exactly 0.0, representing this disconnection. The algorithm gracefully handles the multiple zero eigenvalue by picking a chosen component basis.
4. Select a different Vertex, like 3, and observe its coordinate on the Fiedler vector embedding. It mirrors Vertex 0's magnitude but with the opposite sign.

Limitations

This module uses a specific teaching family of four-node graphs with a highly symmetric weight structure (1, w, 1). The algebraic formulas for the eigenvalues and eigenvectors are exact for this specific topology but do not serve as a general k-means or eigensolver for arbitrary graphs.

Additionally, this module uses the unnormalized Laplacian L = D - A to find the Fiedler vector. While the Fiedler vector determines the partition, we do not claim it is a normalized-Laplacian eigenvector. At exactly w = 0, the graph has two connected components, leading to a multiple zero eigenvalue. In such cases, there is no unique Fiedler direction, so the module deliberately falls back to a deterministic chosen component basis.

References

• scikit-learn: Spectral clustering - Documentation discussing spectral clustering, normalized cuts, and the use of graph Laplacian matrices in finding low-dimensional embeddings for clustering.

The scikit-learn documentation provides a comprehensive overview of how spectral clustering algorithms scale and operate on arbitrary graph laplacians in practice.