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

Abstract

The data clustering problem consists in dividing a data set into prescribed groups of homogeneous data. This is an NP-hard problem that can be relaxed in the spectral graph theory, where the optimal cuts of a graph are related to the eigenvalues of graph 1-Laplacian. In this paper, we first give new notations to describe the paths, among critical eigenvectors of the graph 1-Laplacian, realizing sets with prescribed genus. We introduce the pseudo-orthogonality to characterize m₃(G), a special eigenvalue for the graph 1-Laplacian. Furthermore, we use it to give an upper bound for the third graph Cheeger constant h₃(G), that is, h₃(G) 6 m₃(G). This is a first step for proving that the k-th Cheeger constant is the minimum of the 1-Laplacian Raylegh quotient among vectors that are pseudo-orthogonal to the vectors realizing the previous k - 1 Cheeger constants. Eventually, we apply these results to give a method and a numerical algorithm to compute m₃(G), based on a generalized inverse power method.

Key words： Graph 1-Laplacian; graph Cheeger constants; pseudo-orthogonality; critical values; data clustering

References

1 Amghibech S . Eigenvalues of the discrete p-Laplacian for graphs. Ars Combin, 2003, 67: 283- 302

2 Belloni M , Ferone V , Kawohl B . Isoperimetric inequalities, Wulff shape and related questions for strongly nonlinear elliptic operators. Special issue dedicated to Lawrence E. Payne. Z Angew Math Phys, 2003, 54 (5): 771- 783

3 Belloni M , Kawohl B , Juutinen P . The p-Laplace eigenvalue problem as p → ∞ in a Finsler metric. J Eur Math Soc (JEMS), 2006, 8 (1): 123- 138

4 Bobkov V , Parini E . On the higher Cheeger problem. J Lond Math Soc (2), 2018, 97 (3): 575- 600

5 Bühler T , Hein M . Spectral clustering based on the graph p-Laplacian. In: Bottou L, Littman M, eds. Proceedings of the 26th International Conference on Machine Learning (ICML 2009). 2009, 81- 88

6 Bühler T , Hein M . An inverse power method for nonlinear eigenproblems with applications in 1-spectral clustering and sparse PCA. Adv Neural Inform Process Syst, 2010, 23: 847- 855

7 Caroccia M . Cheeger N-clusters. Calc Var Partial Differential Equations, 2017, 56(2): Art 30 (35 pp)

8 Chang K C . Spectrum of the 1-Laplacian and Cheeger’s constant on graphs. J Graph Theory, 2016, 81 (2): 167- 207

9 Chang K C , Shao S , Zhang D . The 1-Laplacian Cheeger cut: theory and algorithms. J Comput Math, 2015, 33 (5): 443- 467

10 Chang K C , Shao S , Zhang D . Nodal domains of eigenvectors for 1-Laplacian on graphs. Adv Math, 2017, 308: 529- 574

11 Chang K C , Shao S , Zhang D , Zhang W . Nonsmooth critical point theory and applications to the spectral graph theory. Sci China Math, 2021, 64 (1): 1- 32

12 Cheeger J . A lower bound for the smallest eigenvalue of the Laplacian. In: Gunning R C, ed. Problems in Analysis: A Symposium in Honor of Salomon Bochner. Princeton Math Ser, Vol 31. Princeton: Princeton Univ Press, 1970 195- 199

13 Chung F R K . Spectral Graph Theory. CBMS Reg Conf Ser Math, No 92. Providence: Amer Math Soc, 1997

14 Cuesta M . Minimax theorems on C¹ manifolds via Ekeland variational principle. Abstr Appl Anal, 2003, 2003 (13): 757- 768

15 Davies E B , Leydold J , Stadler P F . Discrete nodal domain theorems. Linear Algebra Appl, 2001, 336 (1): 51- 60

16 Della Pietra F , Gavitone N , Piscitelli G . A sharp weighted anisotropic Poincaré inequality for convex domains. C R Math Acad Sci Paris, 2017, 355 (7): 748- 752

17 Della Pietra F , Gavitone N , Piscitelli G . On the second Dirichlet eigenvalue of some nonlinear anisotropic elliptic operators. Bull Sci Math, 2019, 155: 10- 32

18 Della Pietra F , Piscitelli G . Saturation phenomena for some classes of nonlinear nonlocal eigenvalue problems. Atti Accad Naz Lincei Rend Lincei Mat Appl, 2020, 30 (1): 131- 150

19 Drábek P , Robinson S . Resonance problems for the p-Laplacian. J Funct Anal, 1999, 169 (1): 189- 200

20 Esposito L , Kawohl B , Nitsch C , Trombetti C . The Neumann eigenvalue problem for the ∞-Laplacian. Atti Accad Naz Lincei Rend Lincei Mat Appl, 2015, 26: 119- 134

21 Juutinen P , Lindqvist P , Manfredi J J . The ∞-eigenvalue problem. Arch Rational Mech Anal, 1999, 148: 89- 105

22 Kawohl B , Fridman V . Isoperimetric estimates for the first eigenvalue of the p-Laplace operator and the Cheeger constant. Comment Math Univ Carolin, 2003, 44 (4): 659- 667

23 Kawohl B , Novaga M . The p-Laplace eigenvalue problem as p → 1 and Cheeger sets in a Finsler metric. J Convex Anal, 2008, 15 (3): 623- 634

24 Lee J R , Gharan S O , Trevisan L . Multiway spectral partitioning and higher-order Cheeger inequalities. J ACM, 2014, 61 (6): 37 (30 pp)

25 Littig S , Schuricht F . Convergence of the eigenvalues of the p-Laplace operator as p goes to 1. Calc Var Partial Differential Equations, 2014, 49: 707- 727

26 von Luxburg U . A tutorial on spectral clustering. Stat Comput, 2007, 17 (4): 395- 416

27 Parini E . An introduction to the Cheeger problem. Surv Math Appl, 2011, 6: 9- 21

28 Piscitelli G . A nonlocal anisotropic eigenvalue problem. Differential Integral Equations, 2016, 29(11-12): 1001- 1020

29 Piscitelli G . The anisotropic ∞-Laplacian eigenvalue problem with Neumann boundary conditions. Differential Integral Equations, 2019, 32(11-12): 705- 734

30 Rabinowitz P H . Minimax methods in critical point theory with applications to differential equations. CBMS Reg Conf Ser Math, No 65. Providence: Amer Math Soc, 1986

31 Tudisco F , Hein M . A nodal domain theorem and a higher-order Cheeger inequality for the graph p-Laplacian. J Spectr Theory, 2018, 8 (3): 883- 908