mlsanityData to 7 Oct 2026

Next Level Message-Passing with Hierarchical Support Graphs

arXiv 2406.15852 ↗First posted 22 Jun 2024cs.LG cs.AIcited by 5

Not on the map. Why?

Abstract (arXiv)

Message-Passing Neural Networks (MPNNs) are extensively employed in graph learning tasks but suffer from limitations such as the restricted scope of information exchange, by being confined to neighboring nodes during each round of message passing. Various strategies have been proposed to address these limitations, including incorporating virtual nodes to facilitate global information exchange. In this study, we introduce the Hierarchical Support Graph (HSG), an extension of the virtual node concept created through recursive coarsening of the original graph. This approach provides a flexible framework for enhancing information flow in graphs, independent of the specific MPNN layers utilized. We present a theoretical analysis of HSGs, investigate their empirical performance, and demonstrate that HSGs can surpass other methods augmented with virtual nodes, achieving state-of-the-art results across multiple datasets.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 26 of its 39 references that are in the map. First posted on arXiv 22 Jun 2024.

Builds on

26 of 39 references.

References · 26

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2018How Powerful are Graph Neural Networks?cited by 4,355
  3. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  4. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 786
  5. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  6. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  7. 2019Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networkscited by 540
  8. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  9. 2021Rethinking Graph Transformers with Spectral Attentioncited by 468
  10. 2017Residual Gated Graph ConvNetscited by 341
  11. 2023Graph Inductive Biases in Transformers without Message Passingcited by 150
  12. 2019Hierarchical Graph Network for Multi-hop Question Answeringcited by 83
14 more
  1. 2023Where Did the Gap Go? Reassessing the Long-Range Graph Benchmarkcited by 83
  2. 2023DRew: Dynamically Rewired Message Passing with Delaycited by 81
  3. 2021Scaling Up Graph Neural Networks Via Graph Coarseningcited by 80
  4. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  5. 2022Hierarchical Graph Transformer with Adaptive Node Samplingcited by 72
  6. 2023On the Connection Between MPNN and Graph Transformercited by 60
  7. 2023Efficient and Scalable Graph Generation through Iterative Local Expansioncited by 35
  8. 2017Graph Classification via Deep Learning with Virtual Nodescited by 30
  9. 2024Distinguished In Uniform: Self Attention Vs. Virtual Nodescited by 19
  10. 2023Hierarchical Transformer for Scalable Graph Learningcited by 17
  11. 2024Probabilistic Graph Rewiring via Virtual Nodescited by 15
  12. 2021Hierarchical Graph Neural Networkscited by 2
  13. 2022Hierarchical Graph Structures for Congestion and ETA Predictioncited by 2
  14. 2024CoRe-GD: A Hierarchical Framework for Scalable Graph Visualization with GNNscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 2.

5 papers.

  1. 2024FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Networkcited by 8
  2. 2025Improving the Effective Receptive Field of Message-Passing Neural Networkscited by 6
  3. 2025Learn to Jump: Adaptive Random Walks for Long-Range Propagation through Graph Hierarchiescited by 0
  4. 2026Beyond Convolution: Advancing Hypergraph Neural Networks with Hypergraph U-Netscited by 0
  5. 2026CoRe-GNN: Multilevel Message passing on Coarsened graphscited by 0