Date of Award
12-20-2024
Date Published
January 2023
Degree Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Department
Electrical Engineering and Computer Science
Advisor(s)
Reza Zafarani
Keywords
Graph;Graph convolution networks;Graph neural networks;Graph Sparsification;Spectral-based method
Subject Categories
Computer Sciences | Physical Sciences and Mathematics
Abstract
Graphs are pervasive in both the natural world and various domains of science and engineering. Numerous advanced classifiers, such as Graph Neural Networks (GNNs), have been developed to perform node classification on these graphs. However, as graphs become denser with an increasing number of edges, GNNs often suffer from suboptimal generalization performance due to the presence of task-irrelevant connections. These redundant connections can introduce noise, consume excessive computational resources, and degrade performance. Identifying and preserving critical connections in large-scale graphs, while pruning unnecessary ones, is crucial for enhancing the efficiency and accuracy of GNNs in node classification, particularly for GCNs. As a result, the first challenge is determining whether it is possible to identify skeletal substructures within graphs—key subsets of connections—that can preserve the predictive performance of node classification. This involves either maintaining accuracy when using these critical subgraphs instead of the entire graph or training classifiers on these subgraphs with minimal performance degradation. To address the challenge, we propose the Sparsified Graph Convolutional Network (SGCN), a neural network-based graph sparsifier. SGCN effectively reduces graph density by pruning certain edges while still maintaining comparable performance in node classification tasks. To further improve the efficiency of GNN with even more sparse graph, we introduce the Graph Ultra-sparsifier, a semi-supervised graph sparsification method that incorporates dynamically-updated regularization terms derived from graph convolution. This approach preserves the properties of graph filters, enabling the generation of sparser graphs that maintain the performance of GCN models when used as input. To further explore the significance of key subsets of connections, we propose a sparse adversarial attack framework, AdverSparse. This framework demonstrates how the removal of just a few critical connections can severely disrupt the spatial dependencies learned by spatial-temporal models, leading to issues such as increased prediction errors. While graph sparsification effectively addresses the space and time consumption issues of GCNs while maintaining their performance, existing graph editing methods are specifically designed for the low-pass filter structure of GCNs, which inherently favor homophilic graphs. However, real-world graphs often exhibit varying levels of homophily. To further enhance the capability of GCNs on graphs with diverse homophily ratios, it is essential to go beyond merely removing edges. Instead, we propose dynamically assigning weights to both existing edges and hidden edges (i.e., edges from complement graphs). This introduces a second challenge: dynamically editing graphs. The goal is to modify graphs by incorporating edges from both the original graph and its complement in a way that allows them to serve as adaptive graph filters. Such filters should dynamically adjust their behavior based on the homophily ratio of the graph, improving node classification performance. To address the second challenge, we introduce Complement Graph Convolution (CGC), a method designed to overcome the limitations of GCNs and enhance the performance of GNNs that use GCNs as basic modules for node classification tasks across graphs with varying homophily levels. CGC incorporates a trainable, adaptive frequency-response filter that utilizes both an original graph and its complement graph. Spectral analysis reveals that this filter can be expressed as a Bernstein polynomial approximation, allowing it to dynamically adjust the importance of different frequency components for spectral convolution, effectively accommodating diverse homophily and heterophily ratios. Furthermore, we demonstrate that CGC mitigates the over-smoothing problem commonly associated with GCNs. The overall objective of this thesis is to explore methods for enhancing the efficiency and capability of GNNs, particularly the GCN family, by editing graph structures to affect the properties of graph filters.
Access
Open Access
Recommended Citation
Li, Jiayu, "Enhancing Graph Neural Networks by Editing Graphs" (2024). Dissertations - ALL. 2045.
https://surface.syr.edu/etd/2045