Saito, Shota;
(2024)
On Generalized Spectral Clustering: Theories and Algorithms.
Doctoral thesis (Ph.D), UCL (University College London).
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 |
Archive Staff Only
View Item |