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

Michal Valko, Petar Veličković, Chi-Heng Lin, Shantanu Thakoor, Mehdi Azabou, Eva Dyer, Ran Liu, Lakshmi Sathidevi, Venkataramana Ganesh

arXiv · PDF · Open in the Atlas

Code that ran

We lifted 1 functions out of this paper's own repositories and ran 0 of them in a sandbox. "Ran" means the function executed on a synthesized input and returned a value. It is not a reproduction of the paper's results.

Repositories linked to this paper

• nerdslab/halfhop — marked official in Papers with Code; named in the paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

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.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2308.09198")
get_code_for_paper("2308.09198")
have("2308.09198")

Connect an agent — have() is free.