Hierarchical Position Embedding of Graphs with Landmarks and Clustering for Link Prediction
This work addresses link prediction in graphs, which is important for applications like social networks and recommendation systems, and it is incremental as it builds on existing landmark-based methods with hierarchical clustering.
The paper tackles the problem of learning positional information of nodes in graphs for link prediction by proposing a hierarchical position embedding method using landmarks and clustering, achieving state-of-the-art performance on various datasets in terms of HIT@K, MRR, and AUC.
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 \url{https://github.com/kmswin1/HPLC}.