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.

Download activity - last month

Export as JSONXMLCSV

Download activity - last 12 months

Export as CSVXMLJSON

Downloads by country - last 12 months

Export as JSONXMLCSV

Archive Staff Only

View Item