Close Search Advanced
Journals
Resources
About Us
Open Access

The 1-Laplacian Cheeger Cut: Theory and Algorithms

The 1-Laplacian Cheeger Cut: Theory and Algorithms
Preview
Add to basket

Year:    2015

Author:    K.C. Chang, Sihong Shao, Dong Zhang

Journal of Computational Mathematics, Vol. 33 (2015), Iss. 5 : pp. 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.

Submit Article

You do not have full access to this article.

Already a Subscriber? Sign in as an individual or via your institution

Journal Article Details

Publisher Name:    Global Science Press

Language:    English

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

Journal of Computational Mathematics, Vol. 33 (2015), Iss. 5 : pp. 443–467

Published online:    2015-01

AMS Subject Headings:   

Copyright:    COPYRIGHT: © Global Science Press

Pages:    25

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

Author Details

K.C. Chang

Sihong Shao

Dong Zhang

  1. Higher-Order Systems

    Graphs, Simplicial Complexes and Hypergraphs: Spectral Theory and Topology

    Mulas, Raffaella | Horak, Danijela | Jost, Jürgen

    2022

    https://doi.org/10.1007/978-3-030-91374-8_1 [Citations: 3]

  2. The total variation flow in metric random walk spaces

    Mazón, José M. | Solera, Marcos | Toledo, Julián

    Calculus of Variations and Partial Differential Equations, Vol. 59 (2020), Iss. 1

    https://doi.org/10.1007/s00526-019-1684-z [Citations: 14]

  3. The 1-Yamabe equation on graphs

    Ge, Huabin | Jiang, Wenfeng

    Communications in Contemporary Mathematics, Vol. 21 (2019), Iss. 08 P.1850040

    https://doi.org/10.1142/S0219199718500402 [Citations: 8]

  4. Cheeger’s cut, maxcut and the spectral theory of 1-Laplacian on graphs

    Chang, KungChing | Shao, SiHong | Zhang, Dong

    Science China Mathematics, Vol. 60 (2017), Iss. 11 P.1963

    https://doi.org/10.1007/s11425-017-9096-6 [Citations: 13]
  5. Variational and Diffusion Problems in Random Walk Spaces

    The Total Variation Flow in Random Walk Spaces

    Mazón, José M. | Solera-Diana, Marcos | Toledo-Melero, J. Julián

    2023

    https://doi.org/10.1007/978-3-031-33584-6_3 [Citations: 1]

  6. Cheeger‐like inequalities for the largest eigenvalue of the graph Laplace operator

    Jost, Jürgen | Mulas, Raffaella

    Journal of Graph Theory, Vol. 97 (2021), Iss. 3 P.408

    https://doi.org/10.1002/jgt.22664 [Citations: 2]

  7. Nonsmooth critical point theory and applications to the spectral graph theory

    Chang, Kung-Ching | Shao, Sihong | Zhang, Dong | Zhang, Weixi

    Science China Mathematics, Vol. 64 (2021), Iss. 1 P.1

    https://doi.org/10.1007/s11425-019-1625-8 [Citations: 5]

  8. Nonlinear evolution equation associated with hypergraph Laplacian

    Ikeda, Masahiro | Uchida, Shun

    Mathematical Methods in the Applied Sciences, Vol. 46 (2023), Iss. 8 P.9463

    https://doi.org/10.1002/mma.9068 [Citations: 1]

  9. The Cheeger cut and Cheeger problem in metric graphs

    Mazón, José M.

    Analysis and Mathematical Physics, Vol. 12 (2022), Iss. 5

    https://doi.org/10.1007/s13324-022-00729-y [Citations: 2]

  10. First eigenvalue estimates of Dirichlet-to-Neumann operators on graphs

    Hua, Bobo | Huang, Yan | Wang, Zuoqin

    Calculus of Variations and Partial Differential Equations, Vol. 56 (2017), Iss. 6

    https://doi.org/10.1007/s00526-017-1260-3 [Citations: 13]

  11. Dirichlet p-Laplacian eigenvalues and Cheeger constants on symmetric graphs

    Hua, Bobo | Wang, Lili

    Advances in Mathematics, Vol. 364 (2020), Iss. P.106997

    https://doi.org/10.1016/j.aim.2020.106997 [Citations: 12]

  12. A Cheeger Cut for Uniform Hypergraphs

    Mulas, Raffaella

    Graphs and Combinatorics, Vol. 37 (2021), Iss. 6 P.2265

    https://doi.org/10.1007/s00373-021-02348-z [Citations: 3]

  13. Pseudo-orthogonality for graph 1-Laplacian eigenvectors and applications to higher Cheeger constants and data clustering

    Esposito, Antonio Corbo | Piscitelli, Gianpaolo

    Frontiers of Mathematics in China, Vol. 17 (2022), Iss. 4 P.591

    https://doi.org/10.1007/s11464-021-0961-2 [Citations: 0]

  14. Gradient flows in metric random walk spaces

    Mazón, José M. | Solera, Marcos | Toledo, Julián

    SeMA Journal, Vol. 79 (2022), Iss. 1 P.3

    https://doi.org/10.1007/s40324-021-00272-z [Citations: 1]

  15. Nodal domains of eigenvectors for 1-Laplacian on graphs

    Chang, K.C. | Shao, Sihong | Zhang, Dong

    Advances in Mathematics, Vol. 308 (2017), Iss. P.529

    https://doi.org/10.1016/j.aim.2016.12.020 [Citations: 11]