Cheeger Spectral Cut Bounds

Worked Example

Let's consider a Path graph on 4 vertices with nodes labeled 0, 1, 2, and 3. Its adjacency matrix describes edges between (0,1), (1,2), and (2,3). We select a Subset mask of 3, which in binary is 0011. This means subset S contains vertices 0 and 1, leaving subset Sc with vertices 2 and 3.

1. The volume of S is the sum of degrees of vertices 0 and 1. Vertex 0 has degree 1, and vertex 1 has degree 2. vol(S) = 1 + 2 = 3.
2. The volume of Sc is the sum of degrees of vertices 2 and 3. Vertex 2 has degree 2, and vertex 3 has degree 1. vol(Sc) = 2 + 1 = 3.
3. The number of cut edges between S and Sc is the single edge connecting vertex 1 and vertex 2. So, cut edges = 1.
4. The selected conductance is the number of cut edges divided by the minimum of vol(S) and vol(Sc). Thus, 1 / min(3, 3) = 1/3 ≈ 0.3333333333333333.

The graph's normalized Laplacian matrix is computed as I - D-1/2AD-1/2. Computing its eigenvalues directly using Jacobi diagonalization yields a second smallest eigenvalue (the normalized spectral gap, λ₂) of 0.5. The Cheeger inequality guarantees that the optimal conductance φ_G satisfies λ2/2 ≤ φG ≤ √(2λ2). Here, the lower bound is 0.25, the upper bound is 1.0, and our actual minimum cut achieves a conductance of 0.3333333333333333.

Experiment

Explore spectral clustering guarantees in the Cheeger Spectral Cut Bounds module.

1. Change the Graph to Complete and observe how the layout forms a dense K₄ topology.
2. Notice how the Normalized spectral gap (λ₂) jumps to 1.3333333333333333 since highly connected graphs do not have tight bottlenecks.
3. Change the Subset mask to 1 (which selects a single node) and verify that the number of cut edges matches the degree of that node, yielding a selected conductance of 0.6666666666666666.
4. Switch the graph to Disconnected and witness the spectral gap plummet to exactly 0, confirming there is a cut with no edges.

Assumptions and Limitations

This module considers unweighted, undirected graphs where no vertex is completely isolated (degree zero). If the entire graph is disconnected (as in the Disconnected preset composed of two independent pairs), the minimum non-trivial cut has zero cut edges. As a result, the selected conductance for a separating cut is 0, and the normalized spectral gap λ₂ is exactly 0.

When the selected subset mask is 0 (an empty subset) or 15 (all vertices), the conductance is undefined (labeled as Unavailable) because the definition requires non-empty, strict partitions to calculate a meaningful bottleneck ratio. The visualization accurately places cut edges on dashed boundaries, but relies on absolute subset boundaries rather than a continuous force-directed layout.

References

Spectral Graph Theory algorithms and the Cheeger Inequality derivation are heavily explored in Spielman's lectures on spectral graph theory. See the formal derivation of the normalized spectral bounds at:
Spectral Graph Theory and its Applications - Lecture 6 (Spielman).