그래프의 다중 분해능 위치 임베딩: 링크 예측을 위한 그래똣 볼 방법

Multi-Granularity Position Embedding of Graphs via Granular-Ball for Link Prediction

링크 예측은 주어진 그래프 구조 내에서 잠재적 또는 미래 연결 관계를 식별하는 것을 목표로 합니다. 위치 정보는 동질 노드를 상대적인 관계로 구별하여 구조적 패턴과 암묵적인 연결을 정확하게 파악하는 데 필수적이므로, 링크 예측에 중요합니다. 기존 연구에서는 노드의 위치 정보를 단일 분해능의 랜드마크까지의 거리로 도출하며, 이는 동질성 영역의 중심점을 정의합니다. 하지만 이러한 방법은 동질 구조의 다중 분해능 특성과 계층적 상호 관계를 간과합니다. 본 논문에서는 링크 예측을 위한 그래프의 다중 분해능 위치 임베딩 기법인 MGLP (Multi-Granularity Position Embedding of Graphs via Granular-Ball) 방법을 제안합니다. 구체적으로, MGLP는 적응적인 그래똣 볼 그래프 정제 메커니즘을 도입하여 그래프를 최적의 분해능 수준을 갖는 동질 하위 영역으로 적응적으로 세분화합니다. 각 하위 영역 내의 중심 노드는 랜드마크로 간주되며, 이는 계층적 중심 그래프를 형성합니다. 또한, 그래프 내 동질 구조와 그들의 계층적 상관 관계를 모두 포착하여 노드의 판별력을 향상시키기 위한 새로운 다중 분해능 계층적 거리 인코딩 메커니즘을 제안합니다. 실험 결과는 본 논문에서 제안하는 방법이 생성하는 다중 분해능 위치 임베딩이 링크 예측에 대한 기존 알고리즘과 비교하여 우수한 성능과 경쟁력을 보여준다는 것을 입증합니다. 관련 코드는 https://anonymous.4open.science/r/MGLP-D3C5/ 에서 확인할 수 있습니다.

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/.