The Product Cut

Thomas Laurent, James H. von Brecht, Xavier Bresson, Arthur SzlamNeurIPS 2016 · OpenReview

TL;DR

The Product Cut (PCut) is a novel multi-way graph partitioning objective that replaces the traditional additive "Normalized Cut" with a multiplicative approach. By maximizing a geometric mean of cluster probabilities rather than an arithmetic one, it inherently enforces cluster balance and provides significantly better stability against noise and "dirty" data. The result is state-of-the-art accuracy with much faster runtimes.

The Problem: The "Super-Cluster" Trap

Graph partitioning—the task of dividing a network of nodes into meaningful groups—is a cornerstone of machine learning. For years, the gold standard has been the Normalized Cut (NCut). However, NCut suffers from a notorious "super-cluster" problem. When faced with noisy or "dirty" graphs (common in real-world web or text data), NCut often peels off tiny, insignificant clusters while leaving the rest of the graph lumped into one giant, unbalanced mass.

Visualizing the super-cluster problem: A tiny noisy cluster (C) can cause traditional methods to merge distinct main clusters into a single unbalanced mass (c), rather than maintaining balance (b).

This occurs because NCut’s mathematical structure doesn't sufficiently penalize poor balance when clusters are weakly connected. The authors of this paper set out to create a model mathematically "forced" to find well-balanced partitions, even in the presence of noise.

Methods: Shifting from Addition to Multiplication

The authors introduce the Product Cut (PCut). While NCut minimizes the sum of cut ratios, PCut minimizes a product of non-linear functions related to cluster connectivity.

Key components of their approach include:

  • The Objective Function: It combines a measure of intra/inter-connectivity (based on personalized PageRank) with an entropic balance term. This entropic term acts as a "soft" constraint that prevents clusters from becoming too small.
  • Exact Relaxation: The authors prove that the discrete, hard-to-solve partitioning problem can be relaxed into a convex maximization program. Crucially, they prove this relaxation is exact, meaning the optimal solution to the continuous problem is also an optimal solution to the original discrete one.
  • Randomized SLP Algorithm: To solve the optimization, they use Sequential Linear Programming (SLP). To avoid getting stuck in local optima, they introduce a randomized strategy: starting by enforcing only a few constraints and gradually increasing them. This allows the algorithm to "explore" the landscape before settling.
  • Efficiency: They utilize Algebraic Multigrid (AMG) methods to solve the underlying linear systems, allowing the algorithm to scale efficiently to large graphs.

Key Insights

  • Multiplicative vs. Additive: The shift from a sum (NCut) to a product (PCut) is the framework's "secret sauce." Mathematically, this ensures the objective function has a non-vanishing lower bound. Even if clusters are completely disconnected, the Product Cut will still prefer a balanced partition over an unbalanced one.
  • Stability: The paper provides a rigorous stability analysis. They demonstrate that adding a tiny, mediocre cluster to a graph can "break" NCut, whereas PCut remains stable and ignores the infinitesimal perturbation.
  • Likelihood Interpretation: The Product Cut can be viewed as maximizing the formal likelihood of a partition, drawing a parallel between graph partitioning and the classical $k$-means objective used in Euclidean space.

Experimental Results

The model was evaluated on standard benchmark datasets for clustering, including text data (20NEWS, RCV1, WEBKB4, CITESEER) and image/digit data (MNIST, PENDIGITS, USPS, OPTDIGITS).

  • Superior Balance: On "dirty" datasets like WEBKB4, NCut produced partitions where one cluster contained ~99% of the data. PCut, on the other hand, returned clusters of roughly equal size that matched ground-truth labels.
  • Accuracy (Purity): PCut consistently matched or exceeded the performance of state-of-the-art methods like NMFR and GRACLUS. On the 20NEWS dataset, PCut achieved a purity of 61%, significantly higher than NCut's 27%.
  • Computational Speed: PCut is remarkably fast. On the MNIST dataset (70,000 nodes), PCut reached 95% of its limiting purity in just 11 seconds, compared to 4.6 minutes for the competing NMFR algorithm.

Limitations and Future Work

While highly effective, the algorithm relies on hyperparameters like a smoothing parameter (from PageRank) and a constraint increment rate. While the authors suggest good rules of thumb, optimal values might vary for highly irregular graphs. Additionally, the use of personalized PageRank matrices can be memory-intensive for extremely large-scale graphs (billions of edges) without further optimization.

Future work may extend this convex maximization framework to other types of graph-based learning, such as semi-supervised learning or community detection in dynamic networks.

Summary updated

Abstract

We introduce a theoretical and algorithmic framework for multi-way graph partitioning that relies on a multiplicative cut-based objective. We refer to this objective as the Product Cut. We provide a detailed investigation of the mathematical properties of this objective and an effective algorithm for its optimization. The proposed model has strong mathematical underpinnings, and the corresponding algorithm achieves state-of-the-art performance on benchmark data sets.
BibTeX
@inproceedings{laurent2016product,
  author = {Thomas Laurent and James H. von Brecht and Xavier Bresson and Arthur Szlam},
  title = {{The Product Cut}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
  url = {https://openreview.net/forum?id=HJVsF8WO-H},
}
Figure