링크 예측을 위한 엣지 제안 세트

그래프는 소셜 네트워크나 단백질 상호작용과 같은 복잡한 관계형 데이터를 모델링하는 데 흔히 사용되는 도구이며, 이러한 데이터는 시간이 지남에 따라 변화할 수 있다(예: 새로운 친구 관계 형성)는 특징을 지닌다. 또한 측정되지 않은 상호작용 등으로 인해 노이즈가 포함될 수도 있다. 링크 예측은 그래프 내 미래의 간선을 예측하거나 누락된 간선을 추론하는 것을 목표로 하며, 추천 시스템, 실험 설계, 복잡계 분석 등 다양한 분야에 응용된다. 링크 예측 알고리즘은 그래프 내 간선 집합에 크게 의존하지만, 기존의 접근 방식들은 성능 향상을 위해 그래프의 구조를 수정하지 않는 경향이 있다. 본 연구에서는 단순히 그래프에 특정 간선 집합을 사전 처리 단계에서 추가하는 것—우리가 이를 \emph{제안 집합(proposal set)}이라 부르는—이 여러 링크 예측 알고리즘의 성능을 향상시킬 수 있음을 보여준다. 그 근본적인 아이디어는 제안 집합의 간선들이 그래프의 구조와 일반적으로 일치할 경우, 링크 예측 알고리즘이 올바른 간선을 더 잘 예측하도록 더 강력한 지침을 제공한다는 점이다. 즉, 제안 집합을 추가하는 것은 신호 강화를 위한 사전 처리 단계로 볼 수 있다. 우리는 기존의 링크 예측 알고리즘을 활용하여 효과적인 제안 집합을 생성하는 방법을 제시하고, 다양한 합성 및 실측 데이터셋을 대상으로 이 접근법의 성능을 평가한다. 그 결과, 이웃 기반 히우리스틱과 그래프 신경망 기반 링크 예측 알고리즘 모두에서 제안 집합이 정확도를 의미 있게 향상시킨다는 것을 확인하였다. 관련 코드는 \url{https://github.com/CUAI/Edge-Proposal-Sets}에서 제공된다.