Advances in Spectral Graph Neural Networks: Theory and Applications

Abstract

Graph-structured data are widely used across various fields, effectively representing complex relationships and connections, such as user interactions in social networks, path planning in transportation systems, and recommendation systems in e-commerce. The increasing demand for graph data analysis and processing has driven numerous scholars to explore this domain. Among the prominent techniques, graph neural networks (GNNs) stand out for their ability to extract features from graph-structured data, uncovering hidden relationships and patterns that support more accurate decision-making and predictions, which have become a research hotspot in recent years. Unlike node aggregation-based GNNs, which aggregate only neighbouring node information in an iterated operation, spectral GNNs can analyze information flow propagation between any nodes in the graph through a single operation. This thesis summarizes the opportunities and challenges of spectral GNNs and designs algorithms to optimize their computational efficiency. Additionally, the improved spectral GNNs developed in this thesis are applied to various fields with corresponding solutions. The main research content and innovations of this thesis are as follows:

Firstly, the graph structure and the background of the general GNNs are introduced. Then, the contribution and significance of this thesis are detailed. Based on spectral theory, this thesis then identifies the structure of traditional spectral GNNs and the main research gaps of spectral GNNs: the difficulty and inefficiency of parameter fitting due to using a single orthogonal basis in graph structure feature extraction, as well as the high computational complexity of eigen-decomposition. To address these issues, the thesis designs a multi-kernel graph convolution operator based on wavelet functions, accelerating model convergence. Additionally, the Chebyshev polynomial estimation method is employed to further speed up feature extraction on the graph, with quantitative results provided. Experimental results demonstrate that, compared to existing advanced methods, the proposed approach not only accelerates the convergence of the traditional spectral GNN but also achieves better model performance than other conventional graph neural network methods.

In the following two chapters, the thesis individually introduces solutions in multiple fields, i.e., traffic systems with general graphs and other systems with specific graphs, using spectral graph neural network methods. For different practical problems, different preprocessing methods are used to normalize the representation of raw data so that it can be directly learned and reasoned using deep learning methods. Additionally, given the complexity of some application tasks, the combination of graph neural networks with other deep learning methods, such as transformer models and reinforcement learning models, is explored to further improve the robustness and generalization performance of the overall solution.

Finally, this thesis summarizes its contributions and discusses potential future work. Prospective research directions include generalizing the current model to broader applications across various fields.

Date of Award	2 Jan 2025
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Xiangyu ZHAO (Supervisor) & Dingxuan ZHOU (Supervisor)