UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

On Generalized Spectral Clustering: Theories and Algorithms

Saito, Shota; (2024) On Generalized Spectral Clustering: Theories and Algorithms. Doctoral thesis (Ph.D), UCL (University College London). Green open access

[thumbnail of Saito_Thesis.pdf]
Preview
Text
Saito_Thesis.pdf - Submitted Version

Download (4MB) | Preview

Abstract

This thesis considers generalizing spectral graph clustering. Spectral graph clustering exploits the spectrum of graph Laplacian. There is room for generalizations of spectral graph clustering in two directions. The first involves extending the graph Laplacian to the nonlinear pLaplacian, with the expectation of enhancing performance. The second generalization extends from graphs to hypergraphs, which allows for richer modeling by connecting an arbitrary number of vertices in one edge. Despite recent advancements in these generalizations, there remains to be untapped potential for graph spectral clustering. This thesis addresses this gap by introducing three theoretical frameworks. Firstly, we propose a unified class of hypergraph p-Laplacians that incorporates existing variants and novel generalizations. Although existing Laplacians have a similar structure, some Laplacians miss some key features. This framework provides a comprehensive foundation for all key features, applying to the entire class of hypergraph p-Laplacians. Secondly, we consider how to model a hypergraph from vector data. While graph modeling using kernel functions is well-established, an equivalent framework for hypergraph modeling has not been established. We propose such a formulation and establish its theoretical foundations. Thirdly, we propose a multi-class clustering algorithm leveraging the nonlinearity of p-Laplacian. Spectral clustering via p-Laplacian is difficult since it is difficult to obtain higher eigenvectors. Thus, we take an alternative approach using p-resistance induced by p-Laplacian. We develop a theory on p-resistance for practical use and its application to graph multi-class clustering. Finally, as a fourth part, we extend our theoretical insights to develop a learning framework for vertex classification tasks, where we present a simple alternative approach to graph neural networks (GNNs). While GNNs are commonly used for this task, they often exhibit biases towards homophilous information. Instead of overcoming GNNs’ limitations, we propose an alternative approach aiming to mitigate these biases.

Type: Thesis (Doctoral)
Qualification: Ph.D
Title: On Generalized Spectral Clustering: Theories and Algorithms
Open access status: An open access version is available from UCL Discovery
Language: English
Additional information: Copyright © The Author 2024. Original content in this thesis is licensed under the terms of the Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) Licence (https://creativecommons.org/licenses/by-nc/4.0/). Any third-party copyright material present remains the property of its respective owner(s) and is licensed under its existing terms. Access may initially be restricted at the author’s request.
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/10198685
Downloads since deposit
61Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item