Pseudo-orthogonality for graph 1-Laplacian eigenvectors and applications to higher Cheeger constants and data clustering. (English) Zbl 1507.68282

Esposito, Antonio Corbo; Piscitelli, Gianpaolo

Front. Math. China 17, No. 4, 591-623 (2022).

Summary: 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_3(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_3(G)\), that is, \(h_3(G) \leqslant m_3(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_3 (G)\), based on a generalized inverse power method.

MSC:

68T09	Computational aspects of data analysis and big data
05C50	Graphs and linear algebra (matrices, eigenvalues, etc.)

Keywords:

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, 67, 283-302 (2003) · Zbl 1080.31005
[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, 54, 5, 771-783 (2003) · Zbl 1099.35509 · doi:10.1007/s00033-003-3209-y
[3]	Belloni, M.; Kawohl, B.; Juutinen, P., The p-Laplace eigenvalue problem as p → ∞ in a Finsler metric, J Eur Math Soc (JEMS), 8, 1, 123-138 (2006) · Zbl 1245.35078 · doi:10.4171/JEMS/40
[4]	Bobkov, V.; Parini, E., On the higher Cheeger problem, J Lond Math Soc (2), 97, 3, 575-600 (2018) · Zbl 1394.49041 · doi:10.1112/jlms.12119
[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, 23, 847-855 (2010)
[7]	Caroccia M. Cheeger N-clusters. Calc Var Partial Differential Equations, 2017, 56 (2): Art 30 (35 pp) · Zbl 1366.49052
[8]	Chang, K. C., Spectrum of the 1-Laplacian and Cheeger’s constant on graphs, J Graph Theory, 81, 2, 167-207 (2016) · Zbl 1336.05084 · doi:10.1002/jgt.21871
[9]	Chang, K. C.; Shao, S.; Zhang, D., The 1-Laplacian Cheeger cut: theory and algorithms, J Comput Math, 33, 5, 443-467 (2015) · Zbl 1349.05203 · doi:10.4208/jcm.1506-m2014-0164
[10]	Chang, K. C.; Shao, S.; Zhang, D., Nodal domains of eigenvectors for 1-Laplacian on graphs, Adv Math, 308, 529-574 (2017) · Zbl 1366.35204 · doi:10.1016/j.aim.2016.12.020
[11]	Chang, K. C.; Shao, S.; Zhang, D.; Zhang, W., Nonsmooth critical point theory and applications to the spectral graph theory, Sci China Math, 64, 1, 1-32 (2021) · Zbl 1462.58008 · doi:10.1007/s11425-019-1625-8
[12]	Cheeger, J.; Gunning, R. C., A lower bound for the smallest eigenvalue of the Laplacian, Problems in Analysis: A Symposium in Honor of Salomon Bochner, 195-199 (1970), Princeton: Princeton Univ Press, Princeton · Zbl 0212.44903
[13]	Chung, F. R K., Spectral Graph Theory (1997), Providence: Amer Math Soc, Providence · Zbl 0867.05046
[14]	Cuesta, M., Minimax theorems on C^1 manifolds via Ekeland variational principle, Abstr Appl Anal, 2003, 13, 757-768 (2003) · Zbl 1072.58004 · doi:10.1155/S1085337503303100
[15]	Davies, E. B.; Leydold, J.; Stadler, P. F., Discrete nodal domain theorems, Linear Algebra Appl, 336, 1, 51-60 (2001) · Zbl 0990.05093
[16]	Della Pietra, F.; Gavitone, N.; Piscitelli, G., A sharp weighted anisotropic Poincaré inequality for convex domains, C R Math Acad Sci Paris, 355, 7, 748-752 (2017) · Zbl 1373.49010 · doi:10.1016/j.crma.2017.06.005
[17]	Della Pietra, F.; Gavitone, N.; Piscitelli, G., On the second Dirichlet eigenvalue of some nonlinear anisotropic elliptic operators, Bull Sci Math, 155, 10-32 (2019) · Zbl 1421.35232 · doi:10.1016/j.bulsci.2019.02.005
[18]	Della Pietra, F.; Piscitelli, G., Saturation phenomena for some classes of nonlinear nonlocal eigenvalue problems, Atti Accad Naz Lincei Rend Lincei Mat Appl, 30, 1, 131-150 (2020) · Zbl 1439.49082 · doi:10.4171/RLM/883
[19]	Drábek, P.; Robinson, S., Resonance problems for the p-Laplacian, J Funct Anal, 169, 1, 189-200 (1999) · Zbl 0940.35087 · doi:10.1006/jfan.1999.3501
[20]	Esposito, L.; Kawohl, B.; Nitsch, C.; Trombetti, C., The Neumann eigenvalue problem for the ∞-Laplacian, Atti Accad Naz Lincei Rend Lincei Mat Appl, 26, 119-134 (2015) · Zbl 1321.35120 · doi:10.4171/RLM/697
[21]	Juutinen, P.; Lindqvist, P.; Manfredi, J. J., The ∞-eigenvalue problem, Arch Rational Mech Anal, 148, 89-105 (1999) · Zbl 0947.35104 · doi:10.1007/s002050050157
[22]	Kawohl, B.; Fridman, V., Isoperimetric estimates for the first eigenvalue of the p-Laplace operator and the Cheeger constant, Comment Math Univ Carolin, 44, 4, 659-667 (2003) · Zbl 1105.35029
[23]	Kawohl, B.; Novaga, M., The p-Laplace eigenvalue problem as p → 1 and Cheeger sets in a Finsler metric, J Convex Anal, 15, 3, 623-634 (2008) · Zbl 1186.35115
[24]	Lee, J. R.; Gharan, S. O.; Trevisan, L., Multiway spectral partitioning and higher-order Cheeger inequalities, J ACM, 61, 6, 37 (2014) · Zbl 1321.05151 · doi:10.1145/2665063
[25]	Littig, S.; Schuricht, F., Convergence of the eigenvalues of the p-Laplace operator as p goes to 1, Calc Var Partial Differential Equations, 49, 707-727 (2014) · Zbl 1282.35267 · doi:10.1007/s00526-013-0597-5
[26]	von Luxburg, U., A tutorial on spectral clustering, Stat Comput, 17, 4, 395-416 (2007) · doi:10.1007/s11222-007-9033-z
[27]	Parini, E., An introduction to the Cheeger problem, Surv Math Appl, 6, 9-21 (2011) · Zbl 1399.49023
[28]	Piscitelli, G., A nonlocal anisotropic eigenvalue problem, Differential Integral Equations, 29, 11-12, 1001-1020 (2016) · Zbl 1374.35271
[29]	Piscitelli, G., The anisotropic ∞-Laplacian eigenvalue problem with Neumann boundary conditions, Differential Integral Equations, 32, 11-12, 705-734 (2019) · Zbl 1449.35335
[30]	Rabinowitz, P. H., Minimax methods in critical point theory with applications to differential equations (1986), Providence: Amer Math Soc, Providence · Zbl 0609.58002
[31]	Tudisco, F.; Hein, M., A nodal domain theorem and a higher-order Cheeger inequality for the graph p-Laplacian, J Spectr Theory, 8, 3, 883-908 (2018) · Zbl 1491.05126 · doi:10.4171/JST/216