BEYOND LOCAL NEIGHBORHOODS: LEVERAGING INFORMATIVE NODES FOR IMPROVED GRAPH NEURAL NETWORKS PERFORMANCE

Many real-world datasets, such as those from social and scientific domains, can be represented as graphs, where entities are depicted as nodes and their relationships as edges. To analyze the properties of individual entities (node classification) or the community as a whole (graph classification), graph neural networks (GNNs) serve as a powerful tool. Most GNNs utilize a message-passing scheme to aggregate information from neighboring nodes. This localized aggregation allows the network to learn representations that incorporate the context of each node, thereby enhancing its ability to capture complex local structures and relationships. Despite their success, many GNNs heavily rely on local 1-hop neighborhood information and a stacked architecture of $K$ layers. This dependency can result in poor handling of long-range dependencies and lead to issues like information over-squashing. Consequently, there is a pressing need for advanced methodologies that can systematically aggregate more informative nodes beyond the default graph structure to achieve more accurate classification results. In this thesis, we highlight the challenges of information over-squashing and the limited capacity of existing GNNs to capture long-range dependencies, focusing on addressing these issues through innovative informative node selection and end-to-end learning strategy using three approaches. Our first approach, \textit{Two-view GNNs with adaptive view-wise structure learning strategy}, posits that more informative nodes should have proximal node representations within a graph structure constructed on such attributes. We reconstruct a new graph structure based on the proximity of node representations and simultaneously learn a graph object from both the newly constructed and default graph structures for relationship reasoning. Additionally, we employ an adaptive strategy that learns inter-structure relationships based on classifier performance. While this approach achieves more accurate classifications, it is still limited by relying on a single or two graph structures. Our second approach, \textit{Cauchy-smoothing GCN (CauchyGCN)}, utilizes the default graph structure but regards more informative nodes as those closely embedded in the embedding space. CauchyGCN develops a new layer-wise message-passing scheme that follows the properties of the Cauchy distribution, preserving smoothness between closely embedded nodes while penalizing distant 1-hop neighbors less severely. This approach shows competitive results compared to other advancements. From our first two approaches, we observe that (1) Understanding the graph requires learning from multiple perspectives, and informative nodes could reside beyond the default graph structure. (2) Preserving smoothness among informative nodes is beneficial for effective learning. Our third approach, \textit{Topological-induced Graph Transformer (TOPGT)}, defines the additional useful graph structures as topological structures and leverages a self-attention mechanism to assess the importance of closely embedded nodes. This approach achieves state-of-the-art performance compared to existing methods in the domain. Finally, we summarize our contributions through the three approaches that address the challenges that this thesis highlights. Additionally, I discuss potential future work to explore and utilize informative node information beyond local neighborhoods, aiming to develop large pre-trained GNNs capable of tackling various downstream tasks across different domains.