New l2, 1-Norm Relaxation of Multi-Way Graph Cut for Clustering

Xu Yang, Cheng Deng, Xianglong Liu, Feiping Nie

TL;DR

This paper introduces a novel relaxation for multi-way graph cut clustering by employing an $l_{2,1}$-norm to encourage sparser and more distinct cluster structures. They tackle the NP-hard nature of graph cut optimization by transforming it into a quadratic problem on the Stiefel manifold, solvable with an efficient iterative algorithm.

What Problem Does This Paper Address?

Clustering, a fundamental task in machine learning and computer vision, aims to group similar data points together. Graph cut clustering, particularly multi-way variants like Ratio Cut and Normalized Cut, leverages graph theory to capture intrinsic data structures. However, traditional spectral relaxation methods for these NP-hard problems often lead to solutions that deviate from the optimal partition, requiring post-processing (like K-means) which can further degrade quality. This paper addresses the challenge of obtaining more accurate and clearer cluster partitions directly from the graph cut relaxation, especially for multi-way clustering, by proposing a new formulation and an efficient optimization strategy.

Methods

The core of the paper's contribution lies in two key areas:

  • $l_{2,1}$-Norm Relaxation: Instead of using squared distances in the objective function, the authors introduce an $l_{2,1}$-norm. This norm encourages sparsity, meaning many elements in the resulting indicator vectors will be zero. This sparsity is hypothesized to lead to more distinct cluster structures and a better approximation of the ideal discrete solution.
  • Optimization on the Stiefel Manifold: The objective function, involving a ratio of non-smooth terms, is notoriously difficult to optimize. The authors transform this into a Quadratic Problem on the Stiefel Manifold (QPSM). This allows them to leverage existing optimization techniques, specifically an iterative algorithm that updates the solution by minimizing a quadratic form subject to orthogonality constraints. The algorithm involves calculating re-weighted matrices and iteratively updating the F matrix, which represents the cluster indicators.

Datasets

The paper evaluates their method on a variety of datasets:

  • Synthetic Data: Randomly generated data points distributed on three ring shapes with noise.
  • Real-World Datasets:
    • UCI Datasets: Dermatol, Yeast.
  • Object Datasets: COIL20, COIL100.
  • Digit and Character Dataset: BINALPHA.
  • Face Datasets: Yale, YaleB, UMIST.
  • MSRA: A dataset of individuals with varying poses and backgrounds.

Key Insights and Ideas

  • Sparsity for Clarity: The $l_{2,1}$-norm is a powerful tool for inducing sparsity. The insight here is that by forcing many elements of the indicator vectors to be zero, the method can naturally create sharper boundaries between clusters, making the partitions more interpretable.
  • Bridging Continuous and Discrete: Traditional spectral methods produce continuous solutions that need discretization. The $l_{2,1}$-norm aims to make the continuous solution inherently "closer" to a discrete one by encouraging zero values, thus reducing the gap between the relaxed and optimal solutions.
  • Efficient Optimization for Complex Objectives: The transformation to a QPSM is a significant technical achievement. It allows for a structured and efficient iterative optimization process, avoiding the pitfalls of directly optimizing the non-smooth ratio objective. This is crucial for practical applicability.
  • Iterative Refinement: The convergence analysis shows that the algorithm effectively improves cluster similarity and separation over iterations, demonstrating the iterative refinement process is beneficial.

Key Results

The paper reports strong performance across multiple datasets:

  • Superior Accuracy: The proposed method consistently outperforms several state-of-the-art clustering methods, including Ratio Cut (RCut), Normalized Cut (NCut), and various $l_1$-norm based methods, on both synthetic and real-world datasets.
  • High Performance on Challenging Datasets: The method achieves particularly high accuracy on datasets like COIL20 (over 92% accuracy) and performs well even on more complex datasets like COIL100.
  • Improved NMI Scores: Similar to accuracy, Normalized Mutual Information (NMI) scores also show significant improvements with the proposed method.
  • Convergence: The algorithm demonstrates steady growth in clustering performance and objective value over iterations, suggesting effective convergence.

Limitations and Future Work

  • Sensitivity to Initialization: Like many iterative clustering algorithms, the method may be sensitive to initialization, although the authors mention repeating K-means for refinement to mitigate this.
  • Computational Complexity: While the QPSM approach is efficient, the paper notes the complexity as O(kn² + kn²ct), where k is the number of iterations. For very large datasets, further optimizations might be needed.
  • Future Work: The paper doesn't explicitly detail future work, but potential directions could include exploring other robust norms, extending the method to semi-supervised or hierarchical clustering, and investigating its application to more complex data types like graphs with rich node attributes.

Summary updated

BibTeX
@inproceedings{yang2018new,
  author = {Xu Yang and Cheng Deng and Xianglong Liu and Feiping Nie},
  title = {{New l2, 1-Norm Relaxation of Multi-Way Graph Cut for Clustering}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11765},
}
Figure