Total Variation, Cheeger Cuts

Arthur Szlam, Xavier BressonICML 2010 · OpenReview

Introduction

In machine learning, clustering often involves representing data as a graph, where individual data points are nodes and their similarities are edges. The goal is to find a "good" cluster: a subset of data with many internal connections but very few connections to the rest of the graph. The gold-standard metric for evaluating this is the Cheeger cut, which measures the ratio of the boundary size to the size of the smaller cluster.

However, finding the absolute best Cheeger cut is NP-hard. Traditionally, researchers have relied on spectral clustering, which approximates the cut using the second eigenvector of the graph Laplacian. While fast, spectral clustering suffers from a "quadratic gap," meaning its approximation can be quite far from the optimal cut. Recent attempts to bridge this gap using $p$-Laplacian operators have yielded better results, but these methods are computationally expensive and notoriously slow to converge.

This paper introduces a breakthrough approach that proves the NP-hard Cheeger cut problem is theoretically equivalent to a continuous relaxation using Total Variation (TV). By borrowing "Split-Bregman" techniques from image processing, the authors developed an algorithm that finds high-quality clusters up to 100 times faster than previous state-of-the-art methods.

Bridging Theory and Practice

The authors tackle the graph partitioning bottleneck with two major contributions:

  1. Theoretical Equivalence: They prove that minimizing a specific continuous energy functional—based on the $L^1$ norm and Total Variation—is not just an approximation, but is exactly equivalent to the discrete Cheeger cut problem. They demonstrate that the minimizer of this continuous problem naturally forms a binary "indicator" function that identifies the optimal set.
  2. The Split-Bregman Algorithm: To solve this minimization efficiently, the authors adapt the Split-Bregman method, a technique originally designed for fast image denoising and reconstruction. They combine this with Dinkelbach’s method, which iteratively transforms a complex ratio minimization problem (like the Cheeger ratio) into a sequence of simpler subtraction problems.

By introducing "dummy variables" to decouple the $L^1$ components of the energy, the algorithm turns a daunting global optimization into a series of easy-to-solve sub-problems, such as shrinkage operators and linear systems.

Key Insights: The Power of $L^1$ and Cross-Pollination

A major "aha moment" in this research is the realization that graph partitioning and image segmentation are mathematically cousins. Techniques used to find the sharp edges of an object in a photograph are remarkably effective at finding the boundaries of a cluster in high-dimensional data.

While standard spectral clustering uses $L^2$ norms (which are smooth and easy to differentiate), the $L^1$ norm (Total Variation) is inherently "edge-preserving." In a graph context, this sharpness is exactly what allows the algorithm to find a clean, binary cut rather than a fuzzy approximation.

Smooth gradient typical of L2 spectral clustering on the Two Moons dataset
Sharp, binary cut achieved by the proposed L1 Total Variation method

Furthermore, the Split-Bregman approach allows the algorithm to handle the non-differentiable $L^1$ norm efficiently, avoiding the slow convergence that typically plagues subgradient descent methods.

Experimental Results

The authors evaluated their approach on three standard benchmarks: MNIST (handwritten digits), Two Moons (a synthetic 2D dataset of interlocking semi-circles), and CIFAR-10 (color images).

  • Speed: On the MNIST dataset, the proposed algorithm achieved high-quality clusters in 214 seconds, compared to 7,303 seconds for the previous state-of-the-art $p$-Laplacian method—a massive 34x speedup.
  • Accuracy: On the Two Moons and CIFAR-10 datasets, the algorithm consistently produced lower (better) Cheeger cut values and lower classification errors than standard spectral clustering.
  • Scalability: While slower than a simple eigenvector calculation (which took ~54 seconds on MNIST), the proposed method provided significantly more accurate partitions. This makes it a superior middle ground for researchers who need better results than spectral clustering but cannot wait hours for $p$-Laplacian solvers to finish.

Limitations and Future Work

While the algorithm performs exceptionally well in practice, the authors note a few areas for future exploration:

  • Convergence Proofs: The authors currently lack a formal proof of convergence for this specific heuristic combination of the Split-Bregman and Dinkelbach methods.
  • Initialization Sensitivity: The method is currently initialized using the second eigenvector of the Laplacian. Exploring different initializations might further improve the quality of the resulting cuts.
  • Computational Overhead: Although vastly faster than previous $p$-Laplacian methods, the algorithm is still more complex than standard spectral clustering, leaving room for further computational optimization.

Summary updated

BibTeX
@inproceedings{szlam2010total,
  author = {Arthur Szlam and Xavier Bresson},
  title = {{Total Variation, Cheeger Cuts}},
  booktitle = {International Conference on Machine Learning},
  year = {2010},
  url = {https://openreview.net/forum?id=ryba4sZd-S},
}
Figure