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

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 m3(G), a special eigenvalue for the graph 1-Laplacian. Furthermore, we use it to give an upper bound for the third graph Cheeger constant h3(G), that is, h3(G) ⩽ m3(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 m3 (G), based on a generalized inverse power method.