# Hierarchical Position Embedding of Graphs with Landmarks and Clustering for Link Prediction

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 54 references that are in the map.
- First posted on arXiv 13 Feb 2024.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (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)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [Position-aware Graph Neural Networks](https://mlsanity.com/paper/1906.04817/) (2019)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [Learning from Counterfactual Links for Link Prediction](https://mlsanity.com/paper/2106.02172/) (2021)
- [Neural Link Prediction with Walk Pooling](https://mlsanity.com/paper/2110.04375/) (2021)
- [Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling](https://mlsanity.com/paper/1304.4661/) (2013)

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

- [From Anchors to Answers: A Novel Node Tokenizer for Integrating Graph Structure into Large Language Models](https://mlsanity.com/paper/2410.10743/) (2024)
- [A Survey on GNN-based Link Prediction: Techniques, Applications, and Challenges](https://mlsanity.com/paper/2607.16198/) (2026)
- [Multi-Granularity Position Embedding of Graphs via Granular-Ball for Link Prediction](https://mlsanity.com/paper/2607.29115/) (2026)

## Abstract (arXiv)

Learning positional information of nodes in a graph is important for link prediction tasks. We propose a representation of positional information using representative nodes called landmarks. A small number of nodes with high degree centrality are selected as landmarks, which serve as reference points for the nodes' positions. We justify this selection strategy for well-known random graph models and derive closed-form bounds on the average path lengths involving landmarks. In a model for power-law graphs, we prove that landmarks provide asymptotically exact information on inter-node distances. We apply theoretical insights to practical networks and propose Hierarchical Position embedding with Landmarks and Clustering (HPLC). HPLC combines landmark selection and graph clustering, where the graph is partitioned into densely connected clusters in which nodes with the highest degree are selected as landmarks. HPLC leverages the positional information of nodes based on landmarks at various levels of hierarchy such as nodes' distances to landmarks, inter-landmark distances and hierarchical grouping of clusters. Experiments show that HPLC achieves state-of-the-art performances of link prediction on various datasets in terms of HIT@K, MRR, and AUC. The code is available at urlhttps://github.com/kmswin1/HPLC.