본 문서에서는 ICDM 2025 학회에 발표된 "PiGLeT: Probabilistic Message Passing for Semi-supervised Link Sign Prediction" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.
- Title: PiGLeT: Probabilistic Message Passing for Semi-supervised Link Sign Prediction
- Authors: Ka Hyun Park, Junghun Kim, Jinhong Jung and U Kang
- Conference: IEEE International Conference on Data Mining (ICDM) 2025
Signed Graph & Link Sign Prediction
부호 그래프(signed graph)는 노드 사이의 관계가 단순히 연결 여부만으로 표현되지 않고, 긍정 또는 부정의 부호까지 함께 가지는 그래프를 의미합니다. 예를 들어 사회 관계망에서는 신뢰와 불신, 거래 네트워크에서는 우호적 관계와 비우호적 관계, 생물학적 네트워크에서는 활성화와 억제 관계 등을 부호가 있는 간선으로 나타낼 수 있습니다. 이러한 그래프에서는 관측되지 않은 간선의 부호를 예측하는 링크 부호 예측(link sign prediction)이 중요한 문제로 다뤄집니다. 관계의 방향성과 성격을 정확하게 파악해야 추천, 이상 탐지, 관계 분석과 같은 다양한 응용에 활용할 수 있기 때문입니다. 하지만 실제 환경에서는 모든 간선의 부호가 명확히 주어지는 경우가 드물고, 상당수의 간선은 연결은 존재하지만 긍정인지 부정인지 알 수 없는 미표기 상태로 남아 있습니다. 본 논문은 바로 이러한 상황에 주목합니다.
Goal & Limitations of Previous Works
기존의 부호 그래프 신경망 (signed graph neural network) 방법들은 부호 그래프의 구조적 특성을 활용하여 노드 표현을 학습해 왔습니다. 예를 들어 “내 친구의 친구는 내 친구”와 같은 균형 관계나 “내 친구의 적은 내 적”과 같은 비균형 관계를 바탕으로 이웃 정보를 나누어 모으는 방식이 널리 사용되었습니다. 그러나 이러한 방법들은 대부분 모든 간선의 부호가 이미 관측되어 있다고 가정합니다. 이 가정은 실제 응용에서는 비현실적인 경우가 많습니다. 온라인 거래 플랫폼에서 거래 자체는 많이 발생하지만 사용자 간 신뢰 여부는 일부만 존재하고, 사회 관계망에서도 언급이나 공유는 풍부하지만 그것이 지지인지 비판인지 명시적으로 주어지지 않는 경우가 많기 때문입니다. 이처럼 부호가 없는 간선이 많은 환경에서는 기존 방식의 정보 전달 규칙 자체를 적용하기 어렵고, 결과적으로 노드 표현의 품질이 떨어질 수 있습니다. 그렇다면 부호 표시가 일부만 주어진 상황에서도 미표기 간선을 효과적으로 활용하여 정확한 링크 부호 예측을 수행하려면 어떻게 해야 할까요?
Proposed Method
본 논문에서는 이러한 문제를 해결하기 위해 PiGLeT을 제안합니다. PiGLeT의 핵심 아이디어는 unlabeled edge를 단순히 버리거나 하나의 hard label로 고정하지 않고, positive와 negative일 가능성을 모두 가진 soft label로 해석하는 것입니다. 이를 통해 레이블이 없는 엣지도 메시지 패싱 과정에 포함할 수 있으며, 현재 모델이 가진 불확실성까지 함께 반영할 수 있습니다. 또한 단순히 soft label만 사용하는 데서 그치지 않고, 신뢰도 기반 가중치 처리 (confidence-based weighting)와 관계 기반의 어텐션 (relation-aware attention) 을 함께 도입하여 보다 신뢰할 수 있는 정보를 중심으로 노드 임베딩을 개선합니다. 이러한 과정을 반복적으로 수행하여 임베딩과 pseudo-label을 함께 정제하는 iterative refinement 구조를 갖게 됩니다.
 |
| 그림 2. PiGLeT의 전체적인 동작 과정 |
Probabilistic pseudo-labeling
첫 번째 핵심은 unlabeled edge를 확률적으로 해석하는 것입니다. 기존 방법처럼 unlabeled edge를 완전히 무시하면 그래프의 많은 구조 정보를 버리게 되고, 반대로 이를 positive 혹은 negative로 한 번에 hard하게 결정하면 잘못된 pseudo-label이 propagation 과정 전체를 오염시킬 수 있습니다. PiGLeT은 이 문제를 피하기 위해 각 unlabeled edge가 positive일 확률을 예측하고, 이를 바탕으로 positive와 negative일 가능성을 모두 열어둔 채 메시지 패싱에 반영합니다. 즉, 어떤 edge가 완전히 positive라고 확정되지 않았다면, 그 불확실성을 유지하면서 두 관계 모두에 부분적으로 기여하도록 만드는 방식입니다. 이를 통해 unlabeled edge를 활용하면서도 과도하게 한쪽 관계로 단정하는 위험을 줄일 수 있습니다.
Confidence-weighted Relation-aware Attention
두 번째 핵심은 모든 확률적 레이블을 갖게 된 edge를 동일하게 취급하지 않는다는 점입니다. 어떤 unlabeled edge는 모델이 비교적 확신을 가지고 예측할 수 있지만, 어떤 edge는 positive와 negative 가능성이 비슷하여 매우 불확실할 수 있습니다. 이러한 차이를 반영하기 위해 PiGLeT은 confidence-based weighting을 사용합니다. 즉, confidence가 높은 edge는 더 크게 반영하고, confidence가 낮은 edge는 그 영향을 줄여 noisy message가 임베딩 학습을 방해하지 않도록 합니다. 여기에 relation-aware attention을 결합하여 edge의 sign 정보와 관계 유형에 따라 이웃의 중요도를 다르게 반영합니다. 다시 말해, PiGLeT은 단순히 unlabeled edge를 포함하는 데서 끝나지 않고, 어떤 edge를 얼마나 신뢰할 수 있는지까지 함께 고려하여 보다 정교한 메시지 패싱을 수행합니다.
Iterative Refinement
PiGLeT은 현재 노드 임베딩으로 레이블이 없는 엣지의 soft label을 추정하고, 그 결과를 이용해 다시 메시지 패싱을 수행하여 노드 임베딩을 업데이트합니다. 이후 개선된 임베딩을 바탕으로 soft label을 다시 정제하는 과정을 반복합니다. 이 iterative refinement 구조를 통해 임베딩과 soft label이 서로를 점진적으로 보완하게 됩니다. 논문은 이러한 반복적 갱신이 단순한 heuristic이 아니라 EM 알고리즘과 유사한 해석이 가능하다는 점도 함께 제시합니다.
Experiments
본 논문은 실험을 통해 PiGLeT의 우수한 성능을 보였습니다. Semi-supervised setting에서 실세계의 부호 그래프 데이터셋을 대상으로 실험을 수행했으며, PiGLeT은 기존 baseline들보다 일관되게 더 높은 성능을 보였습니다.
아래 그림 3은 confidence distribution을 epoch별로 분석한 결과입니다.
그림 3. 학습 진행에 따른 예측 확률 confidence 분포 양상
부호가 올바르게 예측된 unlabeled edge의 confidence는 학습이 진행될수록 높아지는 반면 잘못 예측된 edge의 confidence는 낮고 분산된 상태로 남는다는 점을 보여줍니다. 이는 PiGLeT의 학습이 진행될수록 점점 더 신뢰할 수 있는 pseudo-label에 집중하고, 불확실한 edge의 영향을 줄이는 방향으로 작동함을 시사합니다.
Conclusion
본 문서에서 부호가 부분적으로 주어진 signed graph에서 semi-supervised link sign prediction 문제를 다룬 PiGLeT 논문을 소개했습니다. unlabeled edge를 positive와 negative 양쪽 가능성을 모두 가진 soft label로 해석하고, confidence-based weighting과 relation-aware attention을 통해 신뢰할 수 있는 정보 위주로 메시지 패싱을 수행하는 방법을 제안합니다. 또한 임베딩과 pseudo-label을 함께 반복적으로 정제하는 iterative refinement 구조를 통해 보다 정확한 부호 예측을 가능하게 하였습니다. 이를 통해 기존 signed GNN들의 모든 엣지의 부호가 존재한다는 비현실적인 가정을 완화하고, 보다 실생활과 밀접한 환경에서 signed graph learning을 수행할 수 있는 방향을 제시했다는 점에서 의미가 큽니다. 이 기법은 온라인 거래 네트워크에서 신뢰/비신뢰 관계를 추정하는 문제, SNS에서 지지/반대 관계를 파악하는 문제, 그리고 명시적인 사용자의 피드백이 일부만 주어진 추천 시스템 등 다양한 분야에 활용될 수 있습니다. 특히 부호 레이블이 일부만 존재하는 것이 오히려 일반적인 상황이라는 점을 고려하면, 본 연구는 signed graph learning을 보다 현실적인 문제 설정으로 확장했다는 점에서 중요한 임팩트를 가진다고 볼 수 있습니다. 본 논문에 대한 자세한 정보는 [링크] 에서 확인할 수 있습니다.