Towards Long-Range Interactions and Heterophily Modeling in Message Passing Graph Neural Networks
COM1 Level 2
SR5, COM1-02-01
Abstract:
Graph Neural Networks (GNNs) have proven effective for learning from graph-structured data, with the Message Passing Neural Network (MPNN) framework at their core. This paradigm refines node representations by iteratively aggregating local neighborhood information. However, two key challenges hinder GNN performance. First, long-range information propagation can be challenging. A GNN with K layers can only incorporate information from nodes within K hops, leading to underreaching. Expanding the network's reach by increasing the number of layers is often suboptimal as it could encounter issues such as over-squashing, where valuable long-range information gets diluted as it passes through the graph's bottlenecks, diminishing its impact on the target nodes. Second, some graphs exhibit heterophily, where connected nodes are likely to be dissimilar. In such cases, aggregating information from the dissimilar neighbors might introduce noise and hinder the graph representation learning performance.
This thesis addresses these challenges by first tackling underreaching with novel training strategies for deep GNNs. We identify stacked transformations as the primary cause of performance degradation, leading to training instability, overfitting, and variance inflation. To mitigate these issues, we introduce node normalization techniques that enable deeper and more effective GNNs.
While node normalization improves deep GNNs, it does not resolve oversquashing or computational inefficiencies. To further enhance long-range information propagation, we propose the prototype-assisted message passing framework, which introduces class prototypes as auxiliary nodes. These prototypes act as shortcuts, efficiently capturing non-local feature information and integrating it with local graph embeddings.
Although this approach improves long-range propagation, it does not explicitly address heterophilous neighborhood aggregation or provide a principled learning mechanism for auxiliary nodes. To bridge this gap, we propose the Differentiable Cluster Graph Neural Network, which embeds a clustering inductive bias into message passing through auxiliary cluster nodes. By optimizing a differentiable global-local clustering objective, it captures both local and global patterns, enabling meaningful long-range connections and selective aggregation within local clusters.
Extensive experiments on diverse datasets demonstrate the effectiveness of these techniques in improving long-range interactions and heterophilous graph modeling. Our findings highlight the potential of integrating node normalization, auxiliary nodes, and clustering mechanisms to overcome fundamental GNN limitations, providing a more effective framework for graph representation learning.