The 1-Laplacian Cheeger Cut: Theory and Algorithms

Authors

  • K.C. Chang LMAM and School of Mathematical Sciences, Peking University, Beijing 100871, China
  • Sihong Shao LMAM and School of Mathematical Sciences, Peking University, Beijing 100871, China
  • Dong Zhang LMAM and School of Mathematical Sciences, Peking University, Beijing 100871, China

DOI:

https://doi.org/10.4208/jcm.1506-m2014-0164

Keywords:

Spectral graph theory, Spectral clustering, 1-Laplace operator, Graph Laplacian, Eigenvalue problems, Cheeger constant, Graph cut, Optimization, Convergence

Abstract

This paper presents a detailed review of both theory and algorithms for the Cheeger cut based on the graph 1-Laplacian. In virtue of the cell structure of the feasible set, we propose a cell descend (CD) framework for achieving the Cheeger cut. While plugging the relaxation to guarantee the decrease of the objective value in the feasible set, from which both the inverse power (IP) method and the steepest descent (SD) method can also be recovered, we are able to get two specified CD methods. Comparisons of all these methods are conducted on several typical graphs.

Downloads

Published

2018-08-22

Abstract View

  • 38279

Pdf View

  • 2871

Issue

Vol. 33 No. 5 (2015)

Section

Articles

How to Cite

The 1-Laplacian Cheeger Cut: Theory and Algorithms. (2018). Journal of Computational Mathematics, 33(5), 443-467. https://doi.org/10.4208/jcm.1506-m2014-0164