본 문서에서는 AAAI '25 학회에서 발표된 "Accurate Link Prediction for Edge-Incomplete Graphs via PU Learning" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.
- Title : Accurate Link Prediction for Edge-Incomplete Graphs via PU Learning
- Authors: Junghun Kim, Ka Hyun Park, Hoyoung Yoon, and U Kang
- Conference: AAAI Conference on Artificial Intelligence (AAAI) 2025
Introduction
그래프 데이터는 소셜 네트워크, 추천 시스템, 논문 인용 네트워크 등 다양한 분야에서 활용됩니다. 하지만 현실 세계의 그래프는 불완전 (edge-incomplete) 한 경우가 많으며, 존재해야 할 링크가 관측되지 않은 경우가 많습니다.
그래프 링크 예측 (Link Prediction) 은 주어진 그래프에서 연결될 가능성이 높은 링크를 찾아내는 문제입니다. 예를 들어, 소셜 네트워크에서 사용자에게 친구를 제안하거나, 추천 시스템에서 사용자에게 아이템을 추천하거나, 논문 인용 네트워크에서 인용할 논문을 제안하는 것 모두 실생활에서 쉽게 찾아볼 수 있는 그래프 링크 예측 문제들입니다. 이 문제를 다른 관점에서 바라보면, 그래프 링크 예측은 어떠한 노드 쌍 (node pair) 가 연결되었을지 (positive), 연결되지 않았을지 (negative) 를 분류하는 이진 분류 문제입니다.
그러나 기존 링크 예측 기법 (GCN, GAT, GAE 등) 은 주어진 그래프에서 연결되지 않은 노드 쌍을 무조건 연결되지 않았다고 (negative 샘플로) 간주하는 문제가 있습니다. 하지만, 실제로 연결이 없는 것 (실제 negative 샘플) 이 아니라 누락된 정보일 가능성이 큽니다.
본 논문에서는 PULL (PU-Learning-based Link predictor) 을 제안하여 edge-incomplete graph (불완전한 그래프) 에서 보다 정확한 링크 예측을 수행하는 방법을 소개합니다. 기존 방법들은 관찰된 (observed) 그래프에 과도하게 의존하여 연결되지 않은 (unconnected) 노드 쌍을 실제 음성 (negative) 데이터로 간주하는 오류를 범합니다. 반면, PULL 은 PU (Positive-Unlabeled) learning 개념을 적용하여, 관찰된 엣지는 양성(Positive) 데이터로, 연결되지 않은 노드 쌍은 레이블이 없는(Unlabeled) 데이터로 처리하여 보다 정밀한 예측을 가능하게 합니다. 기존 기법들의 가장 큰 한계점과 제안 기법 PULL 이 기존 한계점들을 극복한 핵심 아이디어는 아래 그림 1에 정리되어 있습니다.
Proposed Method
PULL은 기존 방법의 한계를 극복하기 위해 PU Learning 을 기반으로 주어진 그래프 데이터의 연결되지 않은 노드 쌍을 처리하는 방식을 채택합니다. PULL의 핵심은 주어진 그래프를 학습에 바로 활용하는 것이 아닌, 그래프 구조의 기대값 (expectation of graph structure) 을 대신 활용하여 불완전한 그래프 구조에 대한 의존성을 낮추고, 점진적으로 expected graph 의 퀄리티를 올리면서 더욱 정확한 링크 예측 모델을 학습하는 것 입니다. 모델의 전체적인 구조는 아래 그림 2와 같습니다.
PULL 은 먼저 모든 노드 쌍 (i, j) 들에게 연결 정보를 나타내는 잠재 변수 (latent variable) z_{ij} 를 도입하여 주어진 그래프 구조의 불완정성을 학습에 반영합니다. 즉, z_{ij} 는 주어진 그래프 \mathcal{G}_\mathcal{P} 에서 관찰된 엣지 (i, j) 들에 대해서는 z_{ij}=1 이지만, 연결되지 않은 노드 쌍 (i,j) 들에 대해서는 항상 z_{ij}=0 이 아니라 z_{ij}=1 이 될수도 있습니다.
그 다음 PULL 은 잠재 변수 \mathbf{z} 에 대한 그래프의 기대 구조를 계산합니다. 이 때 어려운 점은, 기대 구조를 구하는 과정에서 현실적으로 계산할 수 없는 수준의 연산량이 요구되는 것 입니다. 예를 들어 주어진 그래프 \mathcal{G}_\mathcal{P} 에서 연결되지 않은 노드 쌍들의 집합을 \mathcal{E}_\mathcal{U} 라고 하면, 가능한 그래프 구조의 경우의 수는 2^{|\mathcal{E}_\mathcal{U}|} 개 이고, 이 모든 구조에 대해서 기대 확률을 구하는 과정이 필요한데, 이는 지수적 시간 복잡도를 가지기 때문에 비현실적입니다.
그래프의 기대 구조를 효율적으로 구하기 위해서는 그래프 구조의 확률 분포, 즉 노드 쌍들의 결합 분포를 효과적으로 모델링하는 것이 중요합니다. PULL 은 이를 위해 두가지 트릭을 사용합니다. 첫 번째로, 주어진 그래프를 라인 그래프 (line graph) 로 변환합니다. 라인 그래프에서는 원본 그래프에서의 엣지를 노드로 변환하고, 원본 그래프의 두 엣지가 서로 만난다면 라인 그래프에서 해당되는 두 노드를 연결합니다. 두 번째로, 변환된 라인 그래프를 마코브 네트워크 (Markov network) 로 가정합니다. 마코브 네트워크에서는 특정 노드의 상태가 인접한 노드들의 상태에 의존한다는 가정을 기반으로 노드들의 관계를 지역적인 연결 정보에 집중하여 모델링 할 수 있습니다. 위 두 가지 트릭을 통해서 PULL 은 라인 그래프의 노드들의 결합 확률 분포를 효율적으로 구할 수 있고, 이는 원본 그래프의 노드 쌍들의 결합 확률 분포이기 때문에 그래프의 기대 구조를 효과적으로 구할 수 있습니다.
그래프의 기대 구조를 구한 후에는, 이를 활용하여 링크 예측 모델을 학습합니다. 이 때 정확한 링크 예측 모델은 더욱 정확한 그래프 기대 구조를 계산할 때 활용될 수 있으므로, PULL 은 그래프 기대 구조의 업데이트와 링크 예측 모델 학습을 반복적으로 진행합니다.
PULL 은 학습 과정에서 두 개의 손실 함수를 활용합니다. 첫 번째 손실 함수는 기대 그래프 구조와 링크 예측 모델의 결과를 조정하는 역할을 합니다. 이를 통해 불완전한 원본 그래프에 대한 과하게 의존하는 (over-trust) 문제를 완화할 수 있고, 기대 그래프 구조가 정확해질수록 링크 예측 모델의 성능도 올릴 수 있습니다. 다만 학습 초기에는 기대 그래프 구조가 부정확할 수 있는데, 이는 오히려 링크 예측 모델의 성능을 떨어뜨릴 수 있습니다. 이 때문에 PULL 은 원본 그래프 구조와 링크 예측 모델의 결과를 조정하는 두 번째 손실 함수를 통해 과한 자기 강화 (excessive self-reinforcement) 문제를 방지합니다.
Experiments
본 연구에서는 PULL 의 성능을 다양한 실험을 통해 검증하였습니다. 현실 세계의 다양한 그래프 데이터 (PubMed, Cora-Full, Chameleon, Crocodile, Facebook) 등에서 기존의 여러 링크 예측 모델들 (GCN, GAT, SAGE, ARGA, ARGVA, GAE, VGAE, VGNAE, Bagging-PU, NESS) 과 성능을 비교해보았습니다. 평가 지표로는 기존 링크 예측 문제에서 주로 사용되던 AUROC (Area Under ROC Curve) 와 AUPRC (Area Under Precision-Recall Curve) 를 사용하였습니다.
아래 표 1은 PULL 과 기존 링크 예측 모델들의 링크 예측 성능을 비교한 결과입니다. 거의 모든 데이터셋에서 PULL 이 가장 높은 성능을 보이고 있는데, 이는 기대 그래프 구조를 활용하여 원본 그래프의 불완전성을 고려하는 것이 성능 향상에 도움이 되는 것을 보입니다.
아래 그림 3은 PULL 의 iteration 별 성능 변화를 보여줍니다. 이를 통해 우리는 두 가지 결과를 얻을 수 있습니다. 첫째로, iteration 이 계속될수록 PULL 의 링크 예측 성능이 올라가는데, 이는 점진적 학습을 통해 PULL 이 기대 그래프 구조를 더욱 정확하게 구하고 예측 모델의 정확도가 올라가는 것을 의미합니다. 두 번째로, PULL 의 두 번째 손실 함수를 사용하지 않으면 모델의 성능이 떨어지는데, 이는 원본 그래프 구조와 링크 예측 모델의 결과를 조정하는 두 번째 손실 함수가 과한 자기 강화 (excessive self-reinforcement) 문제를 방지하여 성능 하락을 막는 것을 의미합니다.
Conclusion
본 문서에서는 불완전한 그래프 (edge-incomplete graph) 에서 보다 정확한 링크 예측을 수행하는 PU learning 기반의 링크 예측 기법 PULL 을 소개합니다. 기존 링크 예측 기법들은 주어진 그래프에 의존하여 연결되지 않은 노드 쌍을 음성 데이터로 간주하는 한계를 가지고 있었으며, 이는 숨겨진 연결들을 무시하는 결과를 초래했습니다. 이를 해결하기 위해, PULL 은 PU learning 을 활용하여 관찰되지 않은 노드 쌍을 미확인 데이터로 처리하고, 그래프의 기대 구조를 점진적으로 학습하여 예측 성능을 향상시키는 방법을 제안하였습니다. 본 연구에서 제안된 PULL 은 다양한 그래프 기반 연결 예측 문제에 폭넓게 활용될 수 있습니다. 예를 들어, 소셜 네트워크에서 친구 추천, 추천 시스템에서 사용자-아이템 관계 예측, 논문 인용 네트워크에서 학술 논문의 잠재적 연결 예측 등 실생활에서 활용 가능한 여러 응용 사례에서 효과적으로 적용될 수 있습니다. 또한, PULL의 PU Learning 기반 접근 방식은 생물학적 네트워크 분석(예: 단백질-단백질 상호작용 예측), 지식 그래프 완성(Knowledge Graph Completion) 등 다양한 도메인에서도 활용 가능할 것으로 기대됩니다. 논문의 자세한 내용은 링크 에서 확인할 수 있습니다.