Modern multiway spectral partitioning algorithms
2025 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE credits
Student thesisAlternative title
Moderna spektrala partitioneringsalgoritmer (Swedish)
Abstract [en]
Spectral clustering, as a particular method in unsupervised learning, has been successfully applied in many fields due to its ability to capture complicated structures in data through graph-based representations. Traditionally, spectral clustering relies on the Kmeans algorithm to post-process the eigenvectors of the standard graph Laplacian. In this thesis, we investigate and compare several advanced clustering algorithms applied to the spectral embeddings derived from both the standard Laplacian and the generalized non-linear graph p-Laplacian. The first algorithm uses the column-pivoted QR (CPQR) factorization to select representative coordinate directions encoded in the eigenvectors of the graph Laplacian. The second constructs an indicator matrix from the eigenvector matrix by solving a minimization problem. These methods are designed to address limitations of the conventional Kmeans approach, particularly its sensitivity to initialization and its poor performance on non-convex structures. The theoretical background of these algorithms are briefly explained, and we evaluate these methods across synthetic and real-world benchmark datasets, analyzing clustering quality and computational complexity. The results demonstrate that these algorithms outperforms the standard Kmeans algorithm for standard graph Laplacian. Applying them to the graph p-Laplacian can significantly improve clustering performance in datasets with non-convex structures, but the improvement over Kmeans becomes minimal. Furthermore, it suffers from a much higher computational cost due to the procedure of solving a nonlinear eigenvalue problem.
Abstract [sv]
Spektral klustring, som är en specifik metod inom oövervakad inlärning, har framgångsrikt tillämpats inom många områden tack vare dess förmåga att fånga komplexa strukturer i data genom grafbaserade representationer. Traditionellt förlitar sig spektral klustring på Kmeans-algoritmen för att efterbehandla egenvektorerna från den standardiserade graf-Laplacianen. I detta projekt undersöker och jämför vi flera avancerade klustringsalgoritmer som tillämpas på spektrala inbäddningar härledda både från standard-Laplacianen och från den generaliserade icke-linjära graf-p-Laplacianen. Den första algoritmen använder kolumnpivoterad QR-faktorisering (CPQR) för att välja representativa koordinatriktningar som kodas i egenvektorerna för graf-Laplacianen. Den andra algoritmen konstruerar en indikator-matris från egenvektormatrisen genom att lösa ett minimeringsproblem. Dessa metoder är utformade för att hantera begränsningarna hos den konventionella Kmeans-metoden, särskilt dess känslighet för initialisering och dess svaga prestanda på icke-konvexa strukturer. Den teoretiska bakgrunden till dessa algoritmer förklaras kortfattat, och vi utvärderar metoderna på syntetiska och verkliga benchmark-dataset, med fokus på klustringskvalitet och beräkningskomplexitet. Resultaten visar att dessa algoritmer överträffar den traditionella Kmeans-metoden när de används med standard-Laplacianen. Att tillämpa dem på graf-p-Laplacianen kan förbättra klustringsprestandan avsevärt i dataset med icke-konvexa strukturer, men förbättringen jämfört med Kmeans är då marginell. Dessutom drabbas metoden av en betydligt högre beräkningskostnad på grund av behovet av att lösa ett icke-linjärt egenvärdesproblem.
Place, publisher, year, edition, pages
2025. , p. 38
Series
TRITA-SCI-GRU ; 2025:355
National Category
Other Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-368732OAI: oai:DiVA.org:kth-368732DiVA, id: diva2:1990571
Subject / course
Scientific Computing
Educational program
Master of Science - Applied and Computational Mathematics
Supervisors
Examiners
2025-08-202025-08-202025-08-20Bibliographically approved