Abstract : The present paper is devoted to clustering geometric graphs. While the standard spectral clustering is often not effective for geometric graphs, we present an effective generalization, which we call higher-order spectral clustering. It resembles in concept the classical spectral clustering method but uses for partitioning the eigenvector associated with a higher-order eigenvalue. We establish the weak consistency of this algorithm for a wide class of geometric graphs which we call Soft Geometric Block Model. A small adjustment of the algorithm provides strong consistency. We also show that our method is effective in numerical experiments even for graphs of modest size.
https://hal.inria.fr/hal-03169834 Contributor : Konstantin AvrachenkovConnect in order to contact the contributor Submitted on : Monday, March 15, 2021 - 5:42:58 PM Last modification on : Friday, February 4, 2022 - 3:24:51 AM Long-term archiving on: : Wednesday, June 16, 2021 - 7:20:06 PM
Konstantin Avrachenkov, Andrei Bobu, Maximilien Dreveton. Higher-Order Spectral Clustering for Geometric Graphs. Journal of Fourier Analysis and Applications, Springer Verlag, 2021, 27, ⟨10.1007/s00041-021-09825-2⟩. ⟨hal-03169834⟩