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
https://github.com/kmswin1/HPLC.

使用代表性节点（地标）的位置信息，通过选择高度中心性节点作为地标，提供节点位置的参考点。该方法被应用于实际网络中，结合地标选择和图聚类，实现在不同层级上利用节点的位置信息，取得了关于链接预测的最新成果。