On Measuring Long-Range Interactions in Graph Neural Networks

Jacob Bamberger, Benjamin Gutteridge, Scott Le Roux, Michael M. Bronstein, Xiaowen Dong
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:2770-2789, 2025.

Abstract

Long-range graph tasks — those dependent on interactions between ‘distant’ nodes — are an open problem in graph neural network research. Real-world benchmark tasks, especially the Long Range Graph Benchmark, have become popular for validating the long-range capability of proposed architectures. However, this is an empirical approach that lacks both robustness and theoretical underpinning; a more principled characterization of the long-range problem is required. To bridge this gap, we formalize long-range interactions in graph tasks, introduce a range measure for operators on graphs, and validate it with synthetic experiments. We then leverage our measure to examine commonly used tasks and architectures, and discuss to what extent they are, in fact, long-range. We believe our work advances efforts to define and address the long-range problem on graphs, and that our range measure will aid evaluation of new datasets and architectures.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-bamberger25a, title = {On Measuring Long-Range Interactions in Graph Neural Networks}, author = {Bamberger, Jacob and Gutteridge, Benjamin and Roux, Scott Le and Bronstein, Michael M. and Dong, Xiaowen}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {2770--2789}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/bamberger25a/bamberger25a.pdf}, url = {https://proceedings.mlr.press/v267/bamberger25a.html}, abstract = {Long-range graph tasks — those dependent on interactions between ‘distant’ nodes — are an open problem in graph neural network research. Real-world benchmark tasks, especially the Long Range Graph Benchmark, have become popular for validating the long-range capability of proposed architectures. However, this is an empirical approach that lacks both robustness and theoretical underpinning; a more principled characterization of the long-range problem is required. To bridge this gap, we formalize long-range interactions in graph tasks, introduce a range measure for operators on graphs, and validate it with synthetic experiments. We then leverage our measure to examine commonly used tasks and architectures, and discuss to what extent they are, in fact, long-range. We believe our work advances efforts to define and address the long-range problem on graphs, and that our range measure will aid evaluation of new datasets and architectures.} }
Endnote
%0 Conference Paper %T On Measuring Long-Range Interactions in Graph Neural Networks %A Jacob Bamberger %A Benjamin Gutteridge %A Scott Le Roux %A Michael M. Bronstein %A Xiaowen Dong %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-bamberger25a %I PMLR %P 2770--2789 %U https://proceedings.mlr.press/v267/bamberger25a.html %V 267 %X Long-range graph tasks — those dependent on interactions between ‘distant’ nodes — are an open problem in graph neural network research. Real-world benchmark tasks, especially the Long Range Graph Benchmark, have become popular for validating the long-range capability of proposed architectures. However, this is an empirical approach that lacks both robustness and theoretical underpinning; a more principled characterization of the long-range problem is required. To bridge this gap, we formalize long-range interactions in graph tasks, introduce a range measure for operators on graphs, and validate it with synthetic experiments. We then leverage our measure to examine commonly used tasks and architectures, and discuss to what extent they are, in fact, long-range. We believe our work advances efforts to define and address the long-range problem on graphs, and that our range measure will aid evaluation of new datasets and architectures.
APA
Bamberger, J., Gutteridge, B., Roux, S.L., Bronstein, M.M. & Dong, X.. (2025). On Measuring Long-Range Interactions in Graph Neural Networks. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:2770-2789 Available from https://proceedings.mlr.press/v267/bamberger25a.html.

Related Material