Back
Schenk_2021_Spri_machlearn
Journal article

Multiway p-spectral graph cuts on Grassmann manifolds

  • Pasadakis, Dimosthenis ORCID Institute of Computing (CI), Facoltà di scienze informatiche, Università della Svizzera italiana, Svizzera
  • Alappat, Christie Louis ORCID Department of Computer Science, Friedrich-Alexander-Universität Erlangen-Nürnberg, Erlangen, Germany
  • Schenk, Olaf ORCID Institute of Computing (CI), Facoltà di scienze informatiche, Università della Svizzera italiana, Svizzera
  • Wellein, Gerhard ORCID Department of Computer Science, Friedrich-Alexander-Universität Erlangen-Nürnberg, Erlangen, Germany
Show more…
  • 2022
Published in:
  • Machine learning. - 2022, vol. 111, p. 791–829
Graph p-Laplacian
Manifold optimization
Graph clustering
Direct multiway cuts
English Nonlinear reformulations of the spectral clustering method have gained a lot of recent attention due to their increased numerical benefits and their solid mathematical background. We present a novel direct multiway spectral clustering algorithm in the p-norm, for p∈(1,2]. The problem of computing multiple eigenvectors of the graph p-Laplacian, a nonlinear generalization of the standard graph Laplacian, is recasted as an unconstrained minimization problem on a Grassmann manifold. The value of p is reduced in a pseudocontinuous manner, promoting sparser solution vectors that correspond to optimal graph cuts as p approaches one. Monitoring the monotonic decrease of the balanced graph cuts guarantees that we obtain the best available solution from the p-levels considered. We demonstrate the effectiveness and accuracy of our algorithm in various artificial test-cases. Our numerical examples and comparative results with various state-of-the-art clustering methods indicate that the proposed method obtains high quality clusters both in terms of balanced graph cut metrics and in terms of the accuracy of the labelling assignment. Furthermore, we conduct studies for the classification of facial images and handwritten characters to demonstrate the applicability in real-world datasets.
Collections
Language
  • English
Classification
Computer science and technology
License
CC BY
Open access status
hybrid
Identifiers
Persistent URL
https://n2t.net/ark:/12658/srd1324944
Statistics
Document views: 34 File downloads:
  • Schenk_2021_Spri_machlearn.pdf: 88