Half-Hop: A graph upsampling approach for slowing down message passing
Mehdi Azabou Venkataramana Ganesh Shantanu Thakoor Chi-Heng Lin Lakshmi Sathidevi Ran Liu Michal Valko Petar Veličković Eva L. Dyer
Message passing neural networks have shown a lot of success on
graph-structured data. However, there are many instances where message passing
can lead to over-smoothing or fail when neighboring nodes belong to different
classes. In this work, we introduce a simple yet general framework for
improving learning in message passing neural networks. Our approach essentially
upsamples edges in the original graph by adding "slow nodes" at each edge that
can mediate communication between a source and a target node. Our method only
modifies the input graph, making it plug-and-play and easy to use with existing
models. To understand the benefits of slowing down message passing, we provide
theoretical and empirical analyses. We report results on several supervised and
self-supervised benchmarks, and show improvements across the board, notably in
heterophilic conditions where adjacent nodes are more likely to have different
labels. Finally, we show how our approach can be used to generate augmentations
for self-supervised learning, where slow nodes are randomly introduced into
different edges in the graph to generate multi-scale views with variable path
lengths.