# Hierarchical graph neural nets can capture long-range interactions

arXiv: https://arxiv.org/abs/2107.07432 · HTML: https://mlsanity.com/paper/2107.07432/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 25 references that are in the map.
- First posted on arXiv 15 Jul 2021.

## Builds on (most cited first, 21 of 21)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [Multipole Graph Neural Operator for Parametric Partial Differential Equations](https://mlsanity.com/paper/2006.09535/) (2020)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [Combining Label Propagation and Simple Models Out-performs Graph Neural Networks](https://mlsanity.com/paper/2010.13993/) (2020)
- [GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding](https://mlsanity.com/paper/1910.02370/) (2019)
- [Scattering GCN: Overcoming Oversmoothness in Graph Convolutional Networks](https://mlsanity.com/paper/2003.08414/) (2020)
- [Edge Contraction Pooling for Graph Neural Networks](https://mlsanity.com/paper/1905.10990/) (2019)
- [Graph Cross Networks with Vertex Infomax Pooling](https://mlsanity.com/paper/2010.01804/) (2020)
- [Graph Networks with Spectral Message Passing](https://mlsanity.com/paper/2101.00079/) (2020)

## Built on by (most cited first, 12 of 12)

- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [Probabilistic Graph Rewiring via Virtual Nodes](https://mlsanity.com/paper/2405.17311/) (2024)
- [Capturing Graphs with Hypo-Elliptic Diffusions](https://mlsanity.com/paper/2205.14092/) (2022)
- [On Measuring Long-Range Interactions in Graph Neural Networks](https://mlsanity.com/paper/2506.05971/) (2025)
- [Hierarchical Graph Neural Networks for Particle Track Reconstruction](https://mlsanity.com/paper/2303.01640/) (2023)
- [Best of Both Worlds: Advantages of Hybrid Graph Sequence Models](https://mlsanity.com/paper/2411.15671/) (2024)
- [Vision HgNN: An Electron-Micrograph is Worth Hypergraph of Hypernodes](https://mlsanity.com/paper/2408.11351/) (2024)
- [Multi-Source Knowledge-Based Hybrid Neural Framework for Time Series Representation Learning](https://mlsanity.com/paper/2408.12409/) (2024)
- [Attributed Graph Clustering with Multi-Scale Weight-Based Pairwise Coarsening and Contrastive Learning](https://mlsanity.com/paper/2507.20505/) (2025)
- [Learn to Jump: Adaptive Random Walks for Long-Range Propagation through Graph Hierarchies](https://mlsanity.com/paper/2509.01381/) (2025)
- [Connectivity-Guided Sparsification of 2-FWL GNNs: Preserving Full Expressivity with Improved Efficiency](https://mlsanity.com/paper/2511.12838/) (2025)
- [NEMORA: Neural Equivariant Multipole Operators for Long-Range Atomistic Learning](https://mlsanity.com/paper/2610.10776/) (2026)

## Abstract (arXiv)

Graph neural networks (GNNs) based on message passing between neighboring nodes are known to be insufficient for capturing long-range interactions in graphs. In this project we study hierarchical message passing models that leverage a multi-resolution representation of a given graph. This facilitates learning of features that span large receptive fields without loss of local information, an aspect not studied in preceding work on hierarchical GNNs. We introduce Hierarchical Graph Net (HGNet), which for any two connected nodes guarantees existence of message-passing paths of at most logarithmic length w.r.t. the input graph size. Yet, under mild assumptions, its internal hierarchy maintains asymptotic size equivalent to that of the input graph. We observe that our HGNet outperforms conventional stacking of GCN layers particularly in molecular property prediction benchmarks. Finally, we propose two benchmarking tasks designed to elucidate capability of GNNs to leverage long-range interactions in graphs.