Half-Hop: A graph upsampling approach for slowing down message passing.

Area of Science:

• Graph Neural Networks
• Machine Learning
• Artificial Intelligence

Background:

• Message passing neural networks (MPNNs) excel on graph data but suffer from over-smoothing and poor performance in heterophilic settings.
• Existing MPNNs struggle when adjacent nodes have differing class labels, limiting their applicability.

Purpose of the Study:

• To develop a general framework to enhance learning in MPNNs.
• To address limitations of standard message passing, such as over-smoothing and heterophily.

Main Methods:

• Introduced a novel framework by upsampling edges with "slow nodes" to mediate communication between source and target nodes.
• Modified the input graph structure, enabling a plug-and-play integration with existing MPNN models.
• Conducted theoretical and empirical analyses to validate the benefits of slowed message passing.

Main Results:

• Demonstrated significant improvements across supervised and self-supervised learning benchmarks.
• Achieved notable performance gains in heterophilic graph conditions where nodes have different labels.
• Showcased the method's utility in generating multi-scale graph augmentations for self-supervised learning.

Conclusions:

• The proposed "slow node" approach effectively enhances MPNN performance by improving communication pathways.
• This method offers a versatile solution for diverse graph learning tasks, particularly in challenging heterophilic environments.
• The framework facilitates novel data augmentation strategies for self-supervised graph learning.