# GraphReach: Position-Aware Graph Neural Network using Reachability Estimations

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Aug 2020.

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

- [Topology-Imbalance Learning for Semi-Supervised Node Classification](https://mlsanity.com/paper/2110.04099/) (2021)
- [Global Counterfactual Explainer for Graph Neural Networks](https://mlsanity.com/paper/2210.11695/) (2022)
- [A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization](https://mlsanity.com/paper/2211.03074/) (2022)
- [FRIGATE: Frugal Spatio-temporal Forecasting on Road Networks](https://mlsanity.com/paper/2306.08277/) (2023)
- [ULTRA-DP: Unifying Graph Pre-training with Multi-task Graph Dual Prompt](https://mlsanity.com/paper/2310.14845/) (2023)
- [GRAFENNE: Learning on Graphs with Heterogeneous and Dynamic Feature Sets](https://mlsanity.com/paper/2306.03447/) (2023)
- [On the Topology Awareness and Generalization Performance of Graph Neural Networks](https://mlsanity.com/paper/2403.04482/) (2024)
- [Graph Inference Representation: Learning Graph Positional Embeddings with Anchor Path Encoding](https://mlsanity.com/paper/2105.03821/) (2021)
- [GRAPHGINI: Fostering Individual and Group Fairness in Graph Neural Networks](https://mlsanity.com/paper/2402.12937/) (2024)
- [GnnXemplar: Exemplars to Explanations -- Natural Language Rules for Global GNN Interpretability](https://mlsanity.com/paper/2509.18376/) (2025)
- [Bonsai: Gradient-free Graph Condensation for Node Classification](https://mlsanity.com/paper/2410.17579/) (2024)
- [Position: Graph Condensation Needs a Reset -- Move Beyond Full-dataset Training and Model-Dependence](https://mlsanity.com/paper/2605.18893/) (2026)
- [Invariant-Stratified Propagation for Expressive Graph Neural Networks](https://mlsanity.com/paper/2603.01388/) (2026)
- [GFFMERGE: Efficient Merging of Graph Neural Force Fields and Beyond](https://mlsanity.com/paper/2606.03232/) (2026)

## Abstract (arXiv)

Majority of the existing graph neural networks (GNN) learn node embeddings that encode their local neighborhoods but not their positions. Consequently, two nodes that are vastly distant but located in similar local neighborhoods map to similar embeddings in those networks. This limitation prevents accurate performance in predictive tasks that rely on position information. In this paper, we develop GraphReach, a position-aware inductive GNN that captures the global positions of nodes through reachability estimations with respect to a set of anchor nodes. The anchors are strategically selected so that reachability estimations across all the nodes are maximized. We show that this combinatorial anchor selection problem is NP-hard and, consequently, develop a greedy (1-1/e) approximation heuristic. Empirical evaluation against state-of-the-art GNN architectures reveal that GraphReach provides up to 40% relative improvement in accuracy. In addition, it is more robust to adversarial attacks.