Paper deep dive
Multi-Granularity Position Embedding of Graphs via Granular-Ball for Link Prediction
Sen Zhao, Cheng Liu, Shuyin Xia, Zhiyuan Liu, Yi Liu, Yi Wang, Wei Wang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 8/3/2026, 2:38:48 AM
Summary
The paper proposes MGLP, a method for link prediction that utilizes multi-granularity position embeddings. It introduces an Adaptive Granular-Ball Graph Refinement mechanism to decompose graphs into homophilic subdomains and constructs a Hierarchical Central Graph (HCG) to encode relative positions among landmarks. A Multi-Granularity Hierarchical Distance (MGHD) encoding mechanism is used to capture hierarchical correlations, improving node discriminative power for link prediction tasks.
Entities (6)
Relation Signals (7)
MGLP → appliedto → Link Prediction
confidence 99% · Link prediction aims to identify potential or future connections... We propose the... MGLP method
MGLP → uses → Hierarchical Central Graph
confidence 95% · The central nodes within subdomains are treated as landmarks, which form a Hierarchical Central Graph.
MGLP → uses → MGHD
confidence 95% · Moreover, a novel Multi-granularity Hierarchical Distance encoding mechanism is proposed
MGLP → uses → Adaptive Granular-Ball Graph Refinement
confidence 95% · MGLP introduces an Adaptive Granular-Ball Graph Refinement mechanism to adaptively refine the graph into homophilic subdomains
MGHD → captures → hierarchical correlations
confidence 90% · capture both the homophilic structures within a graph and their hierarchical correlations
Hierarchical Central Graph → encodes → relative positions among landmarks
confidence 90% · encode relative positions among landmarks to derive both global and local relationships of nodes
Adaptive Granular-Ball Graph Refinement → produces → homophilic subdomains
confidence 90% · adaptively refine the graph into homophilic subdomains with optimal levels of granularity
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Link prediction aims to identify potential or future connections within a given graph structure. Position information is essential for link prediction, as it distinguishes homogeneous nodes through their relative relationships, facilitating the accurate capture of structural patterns and implicit connections. Previous studies derive node positional information as distances to single-granularity landmarks, defined as the centers of homophilic regions, while neglecting the multi-granularity nature of homophilic structures and their hierarchical interrelations. We propose the Multi-Granularity Position Embedding of Graphs via Granular-Ball for Link Prediction (MGLP) method to obtain multi-granularity position embedding of graphs. Specifically, MGLP introduces an Adaptive Granular-Ball Graph Refinement mechanism to adaptively refine the graph into homophilic subdomains with optimal levels of granularity. The central nodes within subdomains are treated as landmarks, which form a Hierarchical Central Graph. Moreover, a novel Multi-granularity Hierarchical Distance encoding mechanism is proposed to capture both the homophilic structures within a graph and their hierarchical correlations, improving the discriminative power of nodes. Experimental results demonstrate that the multi-granularity position embedding generated by our method exhibits excellent performance and strong competitiveness compared to baseline algorithms for link prediction. Our codes are available in this https URL.
Tags
Links
- Source: https://arxiv.org/abs/2607.29115v1
- Canonical: https://arxiv.org/abs/2607.29115v1
Trouble viewing inline? Open PDF directly →
Full Text
44,875 characters extracted from source content.
Expand or collapse full text
Multi-Granularity Position Embedding of Graphs via Granular-Ball for Link Prediction Sen Zhao Cheng Liu Shuyin Xia Zhiyuan Liu Liu Yi Yi Wang Wei Wang Abstract Link prediction aims to identify potential or future connections within a given graph structure. Position information is essential for link prediction, as it distinguishes homogeneous nodes through their relative relationships, facilitating the accurate capture of structural patterns and implicit connections. Previous studies derive node positional information as distances to single-granularity landmarks, defined as the centers of homophilic regions, while neglecting the multi-granularity nature of homophilic structures and their hierarchical interrelations. We propose the Multi-Granularity Position Embedding of Graphs via Granular-Ball for Link Prediction (MGLP) method to obtain multi-granularity position embedding of graphs. Specifically, MGLP introduces an Adaptive Granular-Ball Graph Refinement mechanism to adaptively refine the graph into homophilic subdomains with optimal levels of granularity. The central nodes within subdomains are treated as landmarks, which form a Hierarchical Central Graph. Moreover, a novel Multi-granularity Hierarchical Distance encoding mechanism is proposed to capture both the homophilic structures within a graph and their hierarchical correlations, improving the discriminative power of nodes. Experimental results demonstrate that the multi-granularity position embedding generated by our method exhibits excellent performance and strong competitiveness compared to baseline algorithms for link prediction. Our codes are available in https://anonymous.4open.science/r/MGLP-D3C5/. keywords: Link Prediction, Granular-Ball, Multi-Granularity. †journal: Nuclear Physics B [1]organization=Chongqing Key Laboratory of Computational Intelligence, Key Laboratory of Big Data Intelligent Computing, Key Laboratory of Cyberspace Big Data Intelligent Security, Ministry of Education, School of Computer Science and Technology, Chongqing University of Posts and Telecommunications, city=Chongqing, postcode=400065, country=China [2]organization=Chongqing Key Laboratory of Computational Intelligence, Key Laboratory of Big Data Intelligent Computing, Chongqing University of Posts and Telecommunications, city=Chongqing, postcode=400065, country=China [3]organization=Chongqing Ant ConsumerFinance Co,. Ltd, Ant Group, city=Chongqing, postcode=400065, country=China 1 Introduction Link prediction seeks to uncover potential links or future connections that are not yet observed within a given graph structure. By identifying implicit relationships, link prediction supports various applications, including friend recommendation, product recommendation in e-commerce Wang et al. (2019); You et al. (2019a), social networks Adamic and Adar (2003), knowledge graph completion Nickel et al. (2015), protein interaction analysis Airoldi et al. (2008), and beyond. Early link prediction methods rely on heuristics to quantify node similarity and predict link likelihood Barabási and Albert (1999). However, their manual design for specific network structures limits generalizability and cross-domain applicability. To address this limitation, Graph Neural Networks (GNNs) have been proposed as an effective solution for learning structured node representations through neighborhood aggregation Gilmer et al. (2017); Kipf and Welling (2017); Hamilton et al. (2017); Veličković et al. (2018). However, standard GNNs fall short of distinguishing homogeneous nodes, which adversely affects their performance in link prediction tasks. Position-embedding methods have been proposed to address this issue You et al. (2019b); Dwivedi et al. (2020); Kreuzer et al. (2021); Wang et al. (2022), leveraging nodes’ positional information as a feature based on their relative distances to other nodes. This positional information is crucial for link prediction, enabling the differentiation of homophilic nodes and capturing relationships between node pairs effectively. HPLC Kim and Baek (2024) enhances the scalability of position-embedding methods by introducing landmarks to derive node positional information relative to them instead of computing pairwise distances for all nodes, reducing computational complexity while preserving accuracy. However, this approach relies solely on unit-grained landmarks, failing to account for the multi-granularity of homophilic structures within the graph and their hierarchical correlations. Figure 1: The comparison of Uni-Granularity and Multi-Granularity Position Embedding. In real-world link prediction scenarios, graphs are inherently composed of homogeneous subdomains that exhibit varying levels of granularity, where nodes within each subregion demonstrate relatively stronger homophilic properties. As illustrated in Fig. 1, the graph as a whole can be considered the coarsest granularity of homophilic structure, with progressively finer-grained levels of structure represented from top to bottom. Each subdomain aligns optimally with a specific level of granularity. For the example in Fig. 1 (b), 12~ G_1^2 is at the appropriate granularity, while 22~ G_2^2 should be further decomposed into 13~ G_1^3 and 23~ G_2^3 at a finer granularity. These varying levels of granularity naturally organize into a tree-like structure, where the closeness of nodes within the tree, defined by the depth of their nearest common ancestor relative to the nodes, reflects the strength of their correlation and homophilic properties. As shown in Fig. 1(b), the finer-grained landmark c2c_2 is more appropriate for estimating the homophily between nodes v1v_1 and v2v_2 compared to the coarser-grained landmark c1c_1. Additionally, the significant distance between v3v_3 and c1c_1 in the tree indicates their lack of relevance. Disregarding the multi-granularity of homophilic structures within the graph and their hierarchical correlations (as illustrated in Fig. 1 a) may lead to the selection of landmarks at an unsuitable granularity level, resulting in inaccurate homophily estimations between nodes. Actually, it is non-trivial to model the multi-granularity distribution of homophily within the graph for link prediction, due to three challenges: 1) Homophilic structure refinement: Homophilic structures are formed by nodes with high connectivity and strong feature similarity. These structures should be modeled at the appropriate level of granularity, ensuring that neither a coarser-grained parent graph nor a finer-grained subgraph exhibits a higher homophily ratio than the level at which the structure is being analyzed. Building on the strengths of granular-ball computing Xia (2019); Xie et al. (2023) in modeling multi-granular characteristics for scatter data, we further explore its application in graph refinement and introduce an Adaptive Granular-Ball graph refinement mechanism to capture homophilic structures within the graph. 2) Relative position encoding among landmarks: Representing the distance between nodes through landmarks is highly beneficial for improving the accuracy of estimating node position. Therefore, a more comprehensive landmark representation is required to provide a more efficient estimation of node position. 3) Position information encoding: The relative distance of a node to others is essential for distinguishing homogeneous nodes. Measuring these distances requires considering homophilic structures and their hierarchical correlations across different granularities. Thus, an effective position encoding mechanism is needed to capture multi-granularity relationships and provide a refined representation of node positions within the graph. To address these challenges, we propose a novel method called Multi-Granularity Position Embedding of Graphs via Granular-Ball for Link Prediction (MGLP). MGLP introduces an Adaptive Granular-Ball Graph Refinement mechanism that iteratively decomposes the graph into homophilic subdomains, ensuring that each subdomain is refined to the optimal level of granularity. Subsequently, the granular-ball refinement process is represented within the Hierarchical Central Graph (HCG) which uses the initial granular-ball central nodes as the root of the tree and diffuses outward in a tree-like structure, with the hierarchical relationships in the tree reflecting the interconnections between landmarks. Moreover, a novel distance measurement mechanism called Multi-Granularity Hierarchical Distance (MGHD) is designed to capture both the homophilic structures within a graph and their hierarchical correlations across different granularities. MGHD employs the distances between nodes along tree-structured paths as weights, incorporating these weights to evaluate the relationship between nodes and landmarks. Extensive experiments conducted on six real-world datasets demonstrate that MGLP consistently outperforms state-of-the-art methods. Our contributions are summarized as follows: 1. We emphasize the importance of multi-granularity of homophilic structures within the graph and their hierarchical correlations for link prediction. 2. We propose the MGLP method, which adaptively refines the graph into homophilic structures at optimal granularity and we utilize HCG to encode the relative positions among landmarks. Furthermore, we introduce MGHD to incorporate homophilic structures and their hierarchical correlations across multiple granularities. 3. We conducted extensive experiments to demonstrate that the MGLP method is applicable to various types of datasets and consistently delivers outstanding performance. 2 Related Work 2.1 Link Prediction Early research on link prediction primarily employed heuristic methods derived from social network analysis Lü and Zhou (2011). Among these, the homophily mechanism McPherson et al. (2001) suggests that ”similar” nodes are more likely to connect. Most heuristics are based on measures of connectivity. Connectivity-based heuristics, such as the Adamić–Adar index (A) Adamic and Adar (2003), measure node similarity by counting shared neighbors, often resulting in predicted graphs with numerous triangular structures. A primarily considers paths of length two, while other heuristics consider longer paths. For example, the Katz index Katz (1953) computes a weighted sum of walks of all lengths between nodes. GNN methods for link prediction demonstrate the power of GNNs in learning effective graph representations. SEAL Zhang and Chen (2018) introduces an h-hop enclosing subgraph centered on two target nodes, reformulating link prediction as a graph classification task based on the subgraph’s structural topology. Poistion-embedding methods for link prediction leverage both graph structure and node positional information. A notable example is the Graph Autoencoder (GAE) Kipf and Welling (2016b), which uses a GCN to compute node representations and predicts links with a sigmoid function applied to node pair representations. The Variational Graph Autoencoder (VGAE) Kipf and Welling (2016a) extends GAE by using two GCNs to learn the mean and variance of node embeddings, performing the link prediction task with the mean and variance of node pairs’ embeddings. ARGE Pan et al. (2018) enhances GAE with adversarial regularization to align node embeddings with a prior distribution. S-VAE Davidson et al. (2022) replaces the Gaussian distribution in VGAE with a von Mises-Fisher distribution to model hyperspherical latent structures. P-GNN You et al. (2019b) aggregates messages from a subset of anchor nodes to capture positional information for link prediction. In knowledge graph completion, R-GCN Schlichtkrull et al. (2018) assigns different weights to relation types during message passing, while SACN Shang et al. (2019) performs message passing for each relation type and analyzes relations using weighted node embeddings. HPLC Kim and Baek (2024) enhances the scalability of position-embedding methods by introducing the concept of landmarks, enabling the derivation of nodes’ positional information relative to these landmarks rather than relying on pairwise distance calculations for all nodes. 3 Methodology As depicted in Figure 2, our framework consists of four phases: (1) Granular-Ball Graph Refinement, which partitions the graph into granular balls of varying granularity and generates a tree based on the hierarchical structure when splitting; (2) Hierarchical Central Graph Construction, where the central nodes of granular balls are used to form a hierarchical central graph to encode relative positions among landmarks; (3) Multi-Granularity Hierarchical Distance Encoding, which captures both the homophilic structures within a graph and their hierarchical correlations across different granularities; and (4) GNN Training with Node Embeddings, combining center and distance vectors to generate node embeddings, which are subsequently utilized in GNN to predict link probabilities. We start this section by introducing important notations and definitions. 3.1 Notations and Definitions An undirected graph is denoted as =(,ℰ,,),G=(V,E, X,A), where V represents the set of nodes with ||=|V|=N indicating the total number of nodes, ℰE represents the set of edges with |ℰ|=ℳ|E|=M denoting the total number of edges, X is the feature matrix associated with the nodes, and A is the adjacency matrix of the graph. Definition 1 Granular-Ball on Graph: A granular-ball, denoted as ~ G, is defined as a connected subgraph of G and is formally expressed as ~=(G~,ℰG~,G~,G~) G=(V_ G,E_ G,X_ G,A_ G). Our approach refines the G into multiple regions as: =~1,~2,…,~n.G=\ G_1, G_2,…, G_n\. (1) Definition 2 Granular-Ball Quality: The quality Q of a granular-ball ~ G is defined as the average connectivity of nodes within the granular-ball, which is calculated based on the number of edges and nodes in the granular-ball. The formula is as follows: (~)=2×|ℰ~||~|,Q( G)= 2×|E_ G||V_ G|, (2) where |ℰ~||E_ G| represents the number of edges between nodes within the granular-ball, and |~||V_ G| represents the number of nodes in the granular-ball. Figure 2: Overview of MGLP. I. Granularizing the original graph, select the central node of each granular-ball. I. Construct the HCG and compute center vectors. I. Using MGHD and the granularization results to compute the distance vectors, with the node’s hierarchical level represented by the color in the HCG. IV. Concatenate center vectors and distance vectors to form node position embeddings, and put these embeddings into GNN models. 3.2 Granular-Ball Graph Refinement This phase can be further divided into coarse and fine-grained splitting, and the construction of the tree is carried out progressively during the splitting process. The initial step constructs the entire dataset into an original graph =(,ℰ,,)G=(V,E, X,A). G is refined through a progressive splitting process, resulting in finer-grained granular-balls at each step. At refinement step t, the granular-ball t~ G^t is divided into a set of finer-grained granular-balls, denoted as 1t+1~,2t+1~,…,nt+1~\ G_1^t+1, G_2^t+1,…, G_n^t+1\. To represent this hierarchical decomposition to obtain center vectors and distance vectors, a tree T is constructed, where each node it=it~,cit,ℐit,itT^t_i=\ G^t_i,c^t_i,I^t_i,P^t_i\ means the corresponding granular-ball it~ G^t_i, its central node citc^t_i, its identifier ℐitI^t_i and the identifier of its parent granular-ball itP^t_i. Coarse-grained splitting: The coarse-grained splitting phase involves dividing G into initial granular balls of varying sizes. During this process, the top α=α= N nodes with the highest degrees are selected from the node-set as the central nodes of the initial granular balls: =c0,c1,…,cα,C=\c_0,c_1,…,c_α\, (3) where C is the set of central nodes and N is the total number of nodes. The value of N is an empirical choice, drawing on previous work Xie et al. (2020). This approach has been demonstrated to effectively balance computational complexity and accuracy. All nodes, except the selected central nodes, are assigned to central nodes as follows: Assign(v)=~i∣mind(v,ci),ci∈,Assign(v)=\ G_i d(v,c_i),\,c_i \, (4) where Assign(v) denotes that the node v is assigned to the granular-ball ~i G_i and d(v,ci)d(v,c_i) is the shortest path distance between the node v and the central node cic_i on G. The initial granular balls are represented as: init~=10~,20~,…,α0~, G_ init=\ G_1^0, G_2^0,…, G_α^0\, (5) The initial granular balls generated based on highly central nodes ensure strong connectivity, facilitating effective coverage of the graph. Each initial granular-ball i0~(1≤i≤α) G_i^0(1≤i≤α) in init~ G_ init undergoes independent fine-grained splitting. Fine-grained splitting: During this phase, the central node is selected as the node with the highest degree, excluding the node that has been selected as the central node to avoid splitting into an overly large granular-ball and an overly small granular-ball. The fine-grained splitting is performed through iterative binary splits. At the t-th step of splitting phase, given a granular-ball it~ G^t_i, two nodes c1c_1 and c2c_2 with the highest degrees among the unselected nodes are chosen as the central nodes for the current partition to split it~ G^t_i into two finer-grained granular balls 1t+1~ G^t+1_1 and 2t+1~ G^t+1_2. Subsequently, all nodes in it~ G^t_i are assigned to the central node c1c_1 or c2c_2 using Eq.4. Once all nodes in it~ G^t_i have been assigned, the quality of 1t+1~ G^t+1_1 and 2t+1~ G^t+1_2 are computed using Eq.2. A split is retained only if the resulting granular balls satisfy the following condition: Q(it~)<max(Q(1t+1~),Q(2t+1~)),Q( G^t_i)< (Q( G^t+1_1),Q( G^t+1_2)), (6) where this condition requires that at least one of the child granular balls has a higher quality than the parent granular-ball. This ensures that granular balls are refined in the direction of increasing quality. With the completion of this phase, each granular-ball in init~ G_ init is adaptively and iteratively refined, resulting in a set of i~\ G_i\ with granular balls of different granularities and a tree T representing the hierarchical decomposition. 3.3 Hierarchical Central Graph Construction After obtaining i~\ G_i\ and T, we consider how to leverage them to construct the HCG. Our objective is to encode relative positions among landmarks to derive both global and local relationships of nodes. We consider the graph consisting only of landmarks, which we refer to as central nodes. The central nodes of init~ G_ init from the coarse-grained splitting phase are used to construct a fully connected graph. Subsequently, based on the refinement levels of each initial granular-ball and T, we perform the edge addition operation on the connected graph as follows: ℰadd=(cj,ck)∣j=ℐi,k=i,i∈,E^add=\(c_j,c_k) j=I_i,k=P_i,T_i \, (7) where ℰaddE^add represents edge addition operation, ℐiI_i is the identifier of granular-ball i~ G_i, and iP_i is the identifier of the parent granular-ball of i~ G_i. Then tree-like structures are extended outward to form a multi-granularity granular-ball distribution graph, referred to as the HCG. The edge weights in the HCG, connecting two granular-ball central nodes u and v, are defined as euv=exp(−d(u,v)2T),e_uv= (- d(u,v)^2T ), (8) where T is the normalizing parameter of the heat kernel and d(u,v)d(u,v) is the shortest path between u and v on G. Subsequently, we utilize the HCG to generate the multi-granularity center vector (CV). Center Vector For nodes belonging to the same granular-ball ~ G, identical identity information is assigned to enhance consistency. This identity information is derived from the HCG, leveraging the relative positional relationships among granular-ball central nodes. Consequently, nodes within the same granular-ball ~ G share identical information, while those residing in the same coarse-grained granular-ball exhibit similar characteristics. In this work, we introduce the HCG and utilize the graph Laplacian Belkin and Niyogi (2003) to encode the relative positional relationships among granular-ball central nodes. Let A^∈ℝK×K A ^K× K denote the weighted adjacency matrix of the central graph. The normalized graph Laplacian is computed as L=I−Δ−12A^Δ−12,L=I- ^- 12 A ^- 12, (9) where I is the identity matrix and Δ is the degree matrix with diagonal entries Δii=∑jA^ij _i= _j A_ij. The eigenvectors corresponding to the Laplacian L are extracted and utilized as center vectors (CVs), encoding the positional information of the granular-ball central nodes. 3.4 Multi-Granularity Hierarchical Distance Encoding At this phase, we propose a novel distance computation paradigm MGHD that leverages i~\ G_i\ and T to measure the distance between nodes. This method is specifically designed to simultaneously reflect the structural relationships in the original graph G and the hierarchical relationships in T. A limited subset of representative nodes, termed granular-ball central nodes, is selected to effectively capture the graph’s structure. These nodes are represented as c1,c2,…,cK∈c_1,c_2,…,c_K , where K indicates the total number of i~\ G_i\. For a given node u, we define a K-dimensional tuple representing the distances from u to each center cic_i (i=1,2,…,Ki=1,2,…,K). This tuple is referred to as distance vector (DV): DV(u)=(d(u,c1),d(u,c2),⋯,d(u,cK))DV(u)= (d(u,c_1),d(u,c_2),·s,d(u,c_K) ) (10) For the distance, the metric is defined as the weighted sum of distances between nodes. Given a graph =(,ℰ),G=(V,E), where V and ℰE represent the set of nodes and edges. Assume that the shortest path from node u to node v is ath=(u,x1,x2,…,v)Path=(u,x_1,x_2,...,v), then the distance between two nodes u and v, denoted as d(u,v)d(u,v), is computed as follows: d(u,v)=∑i=0lw(xi,xi+1),d(u,v)= _i=0^lw(x_i,x_i+1), (11) where w(xi,xi+1)w(x_i,x_i+1) is the weight of edge (xi,xi+1)(x_i,x_i+1) and l is the number of edges in the athPath. The w(xi,xi+1)w(x_i,x_i+1) is computed as follows: w(xi,xi+1)=1−1Depthmax+1Depthmax−|Depth(xi)−Depth(xi+1)|, splitw(x_i,x_i+1)&=1- 1Depth_max+\\ & 1Depth_max-|Depth(x_i)-Depth(x_i+1)| split, (12) where Depth(xi)Depth(x_i) is the depth of node xix_i on T and DepthmaxDepth_max means the maximum depth of T. By weighting distances at each hierarchical level, the metric represents both the homophilic structures within a graph and their hierarchical correlations across different granularities. CVs and DVs are jointly processed through a position encoder to generate node position embedding. 3.5 GNN Training with Node Embeddings The GNN model used in this study builds upon traditional GNNs by integrating local features, positional encodings, and the Jumping Knowledge (JK) Xu et al. (2018) mechanism. Utilizing node features, node positional embedding, and the adja cency matrix to enhance the geometric representation capability of the features. A three-layer fully connected network is employed to update local node features, enabling the capture of local node characteristics. The update for each node feature vh_v is defined as: v(t+1)=σ((t)v(t)+(t)),h_v^(t+1)=σ (W^(t)h_v^(t)+b^(t) ), (13) where (t)W^(t) and (t)b^(t) are the weight matrix and bias for the t-th layer, and σ is an activation function, such as ReLU. The model aggregates neighborhood information using graph convolution operations. For a node v, its neighborhood aggregation is expressed as: v(t)=Φ(u(t):u∈Neighbors(v)),h_v^(t)= (\h_u^(t):u∈ Neighbors(v)\ ), (14) where Φ(⋅) (·) is the neighborhood aggregation function, and Neighbors(v)Neighbors(v) denotes the set of neighbors of node v. Depending on the architecture, Φ(⋅) (·) can represent mean aggregation (GCN), attention-based weighted sum (GAT), or sampling-based aggregation (GraphSAGE). To address the over-smoothing problem, the model employs the JK mechanism to integrate node representations from multiple layers. The final representation of node v is given by: v(JK)=Ψ(v(l):l=1,…,L),h_v^(JK)= (\h_v^(l):l=1,…,L\ ), (15) where Ψ(⋅) (·) is the layer combination function, which can be mean, max, concatenation, or LSTM-based combination. Using the node position encoding, the model predicts links between node pairs. For a given pair of nodes (v,u)(v,u), the link score is computed as: svu=σ(v⋅u),s_vu=σ (h_v·h_u ), (16) where σ(⋅)σ(·) is a sigmoid function, and vh_v and uh_u are the final embeddings of nodes v and u. The model is trained using a binary cross-entropy loss function, which is commonly used for link prediction tasks. The loss function is defined as: ℒ=−1||∑(v,u)∈[yvulog(svu)+(1−yvu)log(1−svu)],L=- 1|V| _(v,u) [y_vu (s_vu)+(1-y_vu) (1-s_vu) ], (17) where V is the set of all node pairs in the training data, yvu∈0,1y_vu∈\0,1\ indicates whether a link exists between nodes v. 4 Experiments In this section, we validate the effectiveness of the MGLP method through various experimental setups, addressing the following research questions: RQ1: How does the performance of the MGLP method compare to existing baseline methods? RQ2: How do the individual components of the MGLP method affect its overall performance? RQ3: How does the number of coarse-grained granular balls influence the performance of the MGLP method? Baselines COLLAB DDI PubMed Cora Citeseer Facebook Adamic Adar 53.00 ± 0.00 18.61 ± 0.00 66.89 ± 0.00 77.22 ± 0.00 68.94 ± 0.00 99.41 ± 0.00 MF 38.74 ± 0.30 17.92 ± 3.57 58.18 ± 0.01 51.14 ± 0.01 50.54 ± 0.01 98.80 ± 0.00 Node2Vec 41.36 ± 0.69 21.95 ± 1.58 80.32 ± 0.29 84.49 ± 0.49 80.00 ± 0.68 86.49 ± 4.32 GCN(GAE) 44.14 ± 1.45 37.07 ± 5.07 95.80 ± 0.13 88.68 ± 0.40 85.35 ± 0.60 98.66 ± 0.04 GCN(MLP) 44.29 ± 1.88 39.31 ± 4.87 95.83 ± 0.80 90.25 ± 0.53 81.47 ± 1.40 99.43 ± 0.02 GraphSAGE 48.62 ± 0.87 44.82 ± 7.32 96.58 ± 0.11 90.24 ± 0.34 87.37 ± 1.39 99.29 ± 0.01 GAT 44.14 ± 5.95 29.53 ± 5.58 85.55 ± 0.23 82.59 ± 0.14 87.29 ± 0.11 99.37 ± 0.00 JKNet 48.84 ± 0.83 57.98 ± 7.68 96.58 ± 0.23 89.05 ± 0.67 88.58 ± 1.78 99.43 ± 0.02 P-GNN - 1.14 ± 0.25 87.22 ± 0.51 85.92 ± 0.33 90.25 ± 0.42 93.13 ± 0.21 GTrans+LPE 11.19 ± 0.42 9.22 ± 0.20 81.15 ± 0.12 79.31 ± 0.09 77.49 ± 0.02 99.27 ± 0.00 GCN+LPE 49.75 ± 1.35 38.18 ± 7.62 95.50 ± 0.13 76.46 ± 0.15 78.29 ± 0.21 99.17 ± 0.00 GCN+DE 53.44 ± 0.29 26.63 ± 6.82 95.42 ± 0.08 89.51 ± 0.12 86.49 ± 0.11 99.38 ± 0.02 GCN+LRGA 52.21 ± 0.72 62.30 ± 9.12 93.53 ± 0.25 88.83 ± 0.01 87.59 ± 0.03 99.42 ± 0.05 SEAL 53.72 ± 0.95 26.25 ± 8.00 95.86 ± 0.28 92.55 ± 0.50 85.82 ± 0.44 99.60 ± 0.02 NBF-net - 4.03 ± 1.32 97.30 ± 0.45 94.12 ± 0.17 92.30 ± 0.23 99.42 ± 0.04 PEG-DW+ 53.70 ± 1.18 47.88 ± 4.56 97.21 ± 0.18 93.12 ± 0.12 94.18 ± 0.18 99.57 ± 0.05 HPLC 56.04 ± 0.28 70.03 ± 7.02 97.38 ± 0.34 94.95 ± 0.18 96.15 ± 0.19 99.69 ± 0.00 MGLP 56.59 ± 0.53 71.01 ± 6.26 97.92 ± 0.23 95.80 ± 0.15 96.45 ± 0.17 99.66 ± 0.00 Table 1: Comparison of experimental results between MGLP and baseline methods 4.1 Experimental Setup Datasets We conducted experiments on six commonly used datasets for link prediction. Among them, Cora, Citeseer, Pubmed Kipf and Welling (2017), and Facebook are relatively small-scale datasets, while the remaining datasets consist of dense or large graphs provided by OGB Hu et al. (2020). The detailed statistics of the datasets are shown in Table 2. Dataset # Nodes # Edges #Edges#Nodes \#Edges\#Nodes Split ratio Cora 2,708 7,986 2.95 70/10/20 Citeseer 3,327 7,879 2.36 70/10/20 PubMed 19,717 64,041 3.25 70/10/20 Facebook 4,039 88,234 21.85 70/10/20 DDI 4,267 1,334,889 312.84 80/10/10 COLLAB 235,868 1,285,465 5.41 92/4/4 Table 2: Dataset statistics Evaluation metrics We follow previous work Kim and Baek (2024). For the Cora, Citeseer, Pubmed, and Facebook datasets, we used the area under the ROC curve (AUC) as the evaluation metric for the model. For the DDI and COLLAB datasets, we calculated the proportion of positive edges in the test data that ranked within the top-k positions to assess the model’s performance. Additionally, we computed the average value of the evaluation metrics across different datasets to reflect the overall effectiveness of the MGLP method. Baselines To evaluate the effectiveness of the MGLP method on the link prediction task, we compared our approach with 17 existing baseline methods, including Adamic Adar (A) Adamic and Adar (2003), Matrix Factorization (MF) Koren et al. (2009), Node2Vec Grover and Leskovec (2016), GCN Kipf and Welling (2017), GraphSAGE Hamilton et al. (2017), GAT Veličković et al. (2018), P-GNN, NBF-Net Zhu et al. (2021), JKNet Xu et al. (2018), SEAL, GCN+DE Li et al. (2020), GCN+LPE Dwivedi et al. (2020), GCN+LRGA Puny et al. (2021), Graph Transformer+LPE Dwivedi and Bresson (2021), PEG-DW+ Wang et al. (2022) and HPLC. Implementation Details All experiments in the paper were implemented using Python and PyTorch Geometric and conducted on an Intel(R) Xeon(R) W-2245 CPU @ 3.90GHz and an NVIDIA GeForce RTX 3090 GPU. Link prediction performance was evaluated based on the ranking of positive edges relative to negative edges in the test datasets. We uniformly integrated a GCN model with the following hyperparameter settings: a learning rate of 0.001, a hidden layer size of 256, a dropout rate of 0.2, binary cross-entropy (BCE) as the loss function, and Adam as the optimizer. For negative edges, we randomly selected an equal number of negative edges corresponding to the positive edges for the experiments. MG CV DV DDI PubMed Cora Citeseer ✗ ✗ ✗ 40.23 ± 5.14 95.80 ± 0.54 91.05 ± 0.44 82.55 ± 0.64 ✗ ✔ ✗ 64.91 ± 8.25 96.16 ± 0.19 92.66 ± 0.16 93.76 ± 0.16 ✗ ✗ ✔ 65.09 ± 4.64 96.22 ± 0.14 93.08 ± 0.18 95.44 ± 0.23 ✗ ✔ ✔ 68.01 ± 7.23 96.61 ± 0.12 93.69 ± 0.23 95.00 ± 0.11 ✔ ✗ ✔ 68.86 ± 5.76 96.76 ± 0.16 94.37 ± 0.17 95.57 ± 0.21 ✔ ✔ ✗ 66.28 ± 9.14 96.37 ± 0.15 94.01 ± 0.22 94.77 ± 0.15 ✔ ✔ ✔ 71.01 ± 6.26 97.92 ± 0.23 95.80 ± 0.15 96.45 ± 0.17 Table 3: Ablation study of MGLP Figure 3: Parametric Analysis of Initial Granular-Ball Central Nodes 4.2 Overall Performance Comparison(RQ1) The experimental results of the MGLP compared with baselines are summarized in Table 1. All methods were evaluated by performing 10 repeated experiments and calculating the average results. The best performance is highlighted in bold, while the second-best performance is underlined. “-” indicates ”Out of Memory” (OOM). From the table, we can derive the following observations: 1) Outstanding performance of MGLP: As quantified in Table 1, MGLP consistently surpasses all 17 baselines across datasets, establishing state-of-the-art (SOTA) results. On the dataset DDI, MGLP achieves 71.01 ± 6.26 HITS@K, outperforming the previous SOTA (HPLC: 70.03 ± 7.02) by a 1.4 absolute gain. For PubMed, a sparse citation network, MGLP attains 97.92 ± 0.23 AUC versus HPLC’s 97.38 ± 0.34, demonstrating superior robustness to structural sparsity. On the massive COLLAB graph, MGLP achieves 56.59 ± 0.53 HITS@K—a 0.55 improvement over HPLC (56.04 ± 0.28), validating scalability. Cora and Citeseer further confirm MGLP’s dominance, exceeding topology-aware baselines like SEAL (92.55) and HPLC (94.95). This improvement stems from MGLP’s ability to adaptively generate structures with varying granularities, allowing it to flexibly accommodate different data distribution characteristics, thereby enhancing model performance. 2) Effective multi-granularity homogeneous structures and hierarchical relationships: MGHD accurately captures the structural relationships in the original graph while effectively representing the hierarchical relationships in the multi-granularity tree. By integrating these two types of relationships, MGHD provides a more comprehensive distance representation in complex networks, thereby improving model performance. 4.3 Ablation Experiment(RQ2) In this section, we conduct ablation studies on the components of the MGLP model, with the detailed results presented in Table 3. In this table, ”MG” ”CV” and ”DV” represent the use of multi-granularity information, center vectors, and distance vectors, respectively. We incorporate multi-granularity by retaining granular-ball information throughout the splitting process. The experimental results demonstrate that these components contribute significantly to enhancing the model’s performance: (1) When the multi-granularity(MG) module is removed, the performance of MGLP significantly degrades. This change highlights the importance of the multi-granularity feature, which enables the capture of both local and global structural characteristics, thereby providing a more comprehensive data representation. (2) The model performance also significantly declines when the center vectors(CV) generated by the HCG construction are not used. This indicates that refining the relationships between the center points at each hierarchical level in the HCG is beneficial for improving model performance. Refining the interrelationships between the center points helps form more effective node embeddings. (3) The removal of the distance vectors(DV) generated by MGHD also leads to a significant decline in performance. This proves that the proposed distance computation paradigm, integrates structural relationships from the original graph with hierarchical relationships in the multi-granularity tree, offering more precise and effective distance representations. Such representations enhance the model’s generalization capability in complex graph structures, leading to superior experimental performance. 4.4 Parameter Analysis(RQ3) In this part, we conducted experiments with varying initial numbers of granular-ball central nodes, as illustrated in Figure 3. Experimental results show that when we choose N granular-ball central nodes, the performance is the best. This is because the choice of N provides a balanced granularity level, ensuring that structures of different granularities can effectively capture local features while retaining the ability to abstract global relationships. This also serves as a validation of previous work Xie et al. (2020). Conclusion In this paper, we propose an adaptive multi-granularity position embedding method via granular-ball for link prediction, MGLP. MGLP adaptively refines the graph into structures of varying levels of granularity, facilitating the effective representation of homogeneous structures across multi-granularity. And we introduce the HCG to encode the relative positions of the central nodes, serving as an additional representation of the node positional information. Furthermore, we propose a novel distance encoding mechanism MGHD that integrates information from homogeneous structures and multi-granularity relationships within a hierarchical tree framework. Experimental results on six datasets demonstrate the superiority of the MGLP framework. References L. A. Adamic and E. Adar (2003) Friends and neighbors on the web. Social networks 25 (3), p. 211–230. Cited by: §1, §2.1, §4.1. E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing (2008) Mixed membership stochastic blockmodels. Journal of machine learning research 9 (Sep), p. 1981–2014. Cited by: §1. A. Barabási and R. Albert (1999) Emergence of scaling in random networks. science 286 (5439), p. 509–512. Cited by: §1. M. Belkin and P. Niyogi (2003) Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation 15 (6), p. 1373–1396. Cited by: §3.3. T. R. Davidson, L. Falorsi, N. D. Cao, T. Kipf, and J. M. Tomczak (2022) Hyperspherical variational auto-encoders. External Links: 1804.00891, Link Cited by: §2.1. V. P. Dwivedi and X. Bresson (2021) A generalization of transformer networks to graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications. Cited by: §4.1. V. P. Dwivedi, C. K. Joshi, T. Laurent, Y. Bengio, and X. Bresson (2020) Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982. Cited by: §1, §4.1. J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl (2017) Neural message passing for quantum chemistry. In International conference on machine learning, p. 1263–1272. Cited by: §1. A. Grover and J. Leskovec (2016) Node2vec: scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, p. 855–864. Cited by: §4.1. W. Hamilton, Z. Ying, and J. Leskovec (2017) Inductive representation learning on large graphs. Advances in neural information processing systems 30. Cited by: §1, §4.1. W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec (2020) Open graph benchmark: datasets for machine learning on graphs. Advances in neural information processing systems 33, p. 22118–22133. Cited by: §4.1. L. Katz (1953) A new status index derived from sociometric analysis. Psychometrika 18 (1), p. 39–43. Cited by: §2.1. M. Kim and S. Baek (2024) Hierarchical position embedding of graphs with landmarks and clustering for link prediction. p. 389–400. Cited by: §1, §2.1, §4.1. T. N. Kipf and M. Welling (2016a) Variational graph auto-encoders. arXiv preprint arXiv:1611.07308. Cited by: §2.1. T. N. Kipf and M. Welling (2016b) Semi-supervised classification with graph convolutional networks. CoRR abs/1609.02907. External Links: Link, 1609.02907 Cited by: §2.1. T. N. Kipf and M. Welling (2017) Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, External Links: Link Cited by: §1, §4.1, §4.1. Y. Koren, R. Bell, and C. Volinsky (2009) Matrix factorization techniques for recommender systems. Computer 42 (8), p. 30–37. Cited by: §4.1. D. Kreuzer, D. Beaini, W. Hamilton, V. Létourneau, and P. Tossou (2021) Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems 34, p. 21618–21629. Cited by: §1. P. Li, Y. Wang, H. Wang, and J. Leskovec (2020) Distance encoding: design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems 33, p. 4465–4478. Cited by: §4.1. L. Lü and T. Zhou (2011) Link prediction in complex networks: a survey. Physica A: statistical mechanics and its applications 390 (6), p. 1150–1170. Cited by: §2.1. M. McPherson, L. Smith-Lovin, and J. M. Cook (2001) Birds of a feather: homophily in social networks. Annual review of sociology 27 (1), p. 415–444. Cited by: §2.1. M. Nickel, K. Murphy, V. Tresp, and E. Gabrilovich (2015) A review of relational machine learning for knowledge graphs. Proceedings of the IEEE 104 (1), p. 11–33. Cited by: §1. S. Pan, R. Hu, G. Long, J. Jiang, L. Yao, and C. Zhang (2018) Adversarially regularized graph autoencoder. CoRR abs/1802.04407. External Links: Link, 1802.04407 Cited by: §2.1. O. Puny, H. Ben-Hamu, and Y. Lipman (2021) Global attention improves graph networks generalization. External Links: Link Cited by: §4.1. M. Schlichtkrull, T. N. Kipf, P. Bloem, R. Van Den Berg, I. Titov, and M. Welling (2018) Modeling relational data with graph convolutional networks. p. 593–607. Cited by: §2.1. C. Shang, Y. Tang, J. Huang, J. Bi, X. He, and B. Zhou (2019) End-to-end structure-aware convolutional networks for knowledge base completion. p. 3060–3067. Cited by: §2.1. P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio (2018) Graph Attention Networks. International Conference on Learning Representations. External Links: Link Cited by: §1, §4.1. H. Wang, H. Yin, M. Zhang, and P. Li (2022) Equivariant and stable positional encoding for more powerful graph neural networks. External Links: Link Cited by: §1, §4.1. H. Wang, F. Zhang, M. Zhang, J. Leskovec, M. Zhao, W. Li, and Z. Wang (2019) Knowledge-aware graph neural networks with label smoothness regularization for recommender systems. p. 968–977. Cited by: §1. S. Xia (2019) Granular ball computing: a new computational model for data analysis. Journal of Granular Computing 4 (3), p. 181–194. Cited by: §1. J. Xie, W. Kong, S. Xia, G. Wang, and X. Gao (2023) An efficient spectral clustering algorithm based on granular-ball. IEEE Transactions on Knowledge and Data Engineering 35 (9), p. 9743–9753. Cited by: §1. J. Xie, Z. Xiong, Q. Dai, X. Wang, and Y. Zhang (2020) A new internal index based on density core for clustering validation. Information Sciences 506, p. 346–365. Cited by: §3.2, §4.4. K. Xu, C. Li, Y. Tian, T. Sonobe, K. Kawarabayashi, and S. Jegelka (2018) Representation learning on graphs with jumping knowledge networks. p. 5453–5462. Cited by: §3.5, §4.1. J. You, Y. Wang, A. Pal, P. Eksombatchai, C. Rosenburg, and J. Leskovec (2019a) Hierarchical temporal convolutional networks for dynamic recommender systems. p. 2236–2246. Cited by: §1. J. You, R. Ying, and J. Leskovec (2019b) Position-aware graph neural networks. In International conference on machine learning, p. 7134–7143. Cited by: §1, §2.1. M. Zhang and Y. Chen (2018) Link prediction based on graph neural networks. Advances in neural information processing systems 31. Cited by: §2.1. Z. Zhu, Z. Zhang, L. Xhonneux, and J. Tang (2021) Neural bellman-ford networks: a general graph neural network framework for link prediction. Advances in Neural Information Processing Systems 34, p. 29476–29490. Cited by: §4.1.