full
search.png

Search

close.png

Cancel

arrow
Volume 33, Issue 5
The 1-Laplacian Cheeger Cut: Theory and Algorithms

K.C. Chang, Sihong Shao & Dong Zhang

DOI: 10.4208/jcm.1506-m2014-0164

J. Comp. Math., 33 (2015), pp. 443-467.

Published online: 2015-10

Preview Purchase PDF 2157 32411

Cited by

google scholar semantic scholar
Export citation
  • 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.

  • Keywords

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

  • AMS Subject Headings

05C85, 05C50, 05C35, 58C40, 90C27, 35P30, 05C75, 90C26, 90C35.

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

kcchang@math.pku.edu.cn (K.C. Chang)

sihong@math.pku.edu.cn (Sihong Shao)

dongzhang@pku.edu.cn (Dong Zhang)

  • BibTex
  • RIS
  • TXT
@Article{JCM-33-443, author = {Chang , K.C.Shao , Sihong and Zhang , Dong}, title = {The 1-Laplacian Cheeger Cut: Theory and Algorithms}, journal = {Journal of Computational Mathematics}, year = {2015}, volume = {33}, number = {5}, pages = {443--467}, 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.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.1506-m2014-0164}, url = {http://global-sci.org/intro/article_detail/jcm/9854.html} }
TY - JOUR T1 - The 1-Laplacian Cheeger Cut: Theory and Algorithms AU - Chang , K.C. AU - Shao , Sihong AU - Zhang , Dong JO - Journal of Computational Mathematics VL - 5 SP - 443 EP - 467 PY - 2015 DA - 2015/10 SN - 33 DO - http://doi.org/10.4208/jcm.1506-m2014-0164 UR - https://global-sci.org/intro/article_detail/jcm/9854.html KW - Spectral graph theory, Spectral clustering, 1-Laplace operator, Graph Laplacian, Eigenvalue problems, Cheeger constant, Graph cut, Optimization, Convergence AB -

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.

Chang , K.C.Shao , Sihong and Zhang , Dong. (2015). The 1-Laplacian Cheeger Cut: Theory and Algorithms. Journal of Computational Mathematics. 33 (5). 443-467. doi:10.4208/jcm.1506-m2014-0164
Copy to clipboard
BibteX RIS TXT
The citation has been copied to your clipboard