TRANS: Temporal Reachability-Aware Negative Sample Weighting for Temporal Graph Link Prediction

국문 초록 (Abstract)

시간 그래프 신경망은 관측된 엣지와 샘플링된 음성 엣지를 대조함으로써 링크 예측을 학습하며, 일반적인 학습 과정에서는 모든 샘플링된 음성 엣지를 이진 교차 엔트로피 손실에서 올바른 음성 예제로 간주한다. 그러나 이러한 가정은 시간 그래프에서는 항상 성립하지 않는다. 시간 t에서 관측되지 않은 노드 쌍이 이후 짧은 시간 안에 실제 상호작용으로 나타날 수 있기 때문이다. 이 경우 모델은 이후 양성으로 확인되는 노드 쌍에 높은 확률을 부여했다는 이유로 손실에 의해 불필요한 패널티를 받게 된다. 본 논문에서는 이러한 샘플을 시간적 거짓 음성 샘플（temporal false negative）로 정의한다.

본 논문은 시간 그래프 링크 예측을 위한 시간적 도달가능성 기반 음성 샘플 가중치 기법인 TRANS를 제안한다. TRANS는 음성 샘플러나 시간 그래프 신경망 구조를 변경하지 않고, 손실 함수 단계에서 동작한다. 각 샘플링된 음성 엣지에 대해 TRANS는 시간 정보가 포함된 상호작용 이력과 시간적 도달가능성 정보를 이용하여 샘플별 손실 가중치를 계산한다. 미래 상호작용 가능성을 시사하는 시간적 증거가 강한 음성 샘플은 낮은 가중치를 부여받고, 그러한 증거가 없는 샘플은 더 강한 음성 감독 신호를 유지한다.

제안한 기법의 효과를 분석하기 위해 본 논문은 샘플링된 음성 샘플 중 미래에 양성으로 나타나는 비율을 측정하는 Raw False Negative Rate（Raw FNR）와, 가중치 적용 이후 손실에 실제로 남아 있는 거짓 음성 신호의 비율을 측정하는 Effective False Negative Rate（Effective FNR）를 구분하여 사용한다. 네 개의 시간 그래프 벤치마크와 TGN, TGAT, CAW 백본 모델을 이용한 실험 결과, TRANS는 모든 설정에서 Effective FNR을 일관되게 감소시켰지만, AP와 AUC 성능은 모든 경우에서 동일하게 향상되지는 않았다. 이는 거짓 음성 노출을 줄이는 것만으로는 예측 성능 향상을 보장할 수 없으며, 과도한 가중치 감소가 결정 경계 학습에 필요한 hard true negative의 유용한 대조 신호까지 약화시킬 수 있음을 보여준다.

종합하면, 본 논문의 결과는 시간 그래프 링크 예측에서 음성 샘플링을 단순히 어떤 음성 샘플을 선택할 것인가의 문제로만 다루기보다, 선택된 음성 샘플을 손실 함수에서 얼마나 강하게 반영할 것인가의 문제까지 함께 고려해야 함을 보여준다. 또한 음성 샘플 가중치 조정의 효과는 시간적 거짓 음성 샘플의 영향을 줄이는 것과, 결정 경계 학습에 필요한 어려운 hard true negative의 대조 신호를 보존하는 것 사이의 균형에 의해 결정됨을 확인하였다.

다국어 초록 (Multilingual Abstract)

Temporal graph neural networks learn link prediction by contrasting observed edges against sampled negative edges, and standard training treats every sampled negative as a correctly labeled negative example in the binary cross-entropy loss. However, this assumption is unreliable in temporal graphs, where an unobserved pair at time t may become an observed interaction shortly afterward. In such cases, the model is penalized for assigning a high probability to a pair that is later confirmed as positive. We refer to these samples as temporal false negatives. This paper proposes TRANS, a temporal reachability-aware negative weighting method for temporal link prediction. Instead of modifying the negative sampler or the temporal graph neural network architecture, TRANS operates at the loss level. For each sampled negative, it computes a sample-specific weight using timestamped interaction history and temporal reachability information. Negative samples with stronger temporal evidence of future interaction are down-weighted, while samples without such evidence retain stronger negative supervision. To analyze this mechanism, we distinguish Raw False Negative Rate （Raw FNR）, which measures false-negative contamination among sampled negatives, from Effective False Negative Rate （Effective FNR）, which measures how much false-negative signal remains in the training loss after weighting. Experiments on four temporal graph benchmarks with TGN, TGAT, and CAW backbones show that TRANS consistently reduces Effective FNR. However, AP and AUC do not improve uniformly. This indicates that reducing false-negative exposure alone is not sufficient for better prediction performance, because aggressive down-weighting can also weaken hard true negatives that provide useful contrastive supervision. Overall, our results show that negative sampling in temporal link prediction should be considered not only as a sampling problem, but also as a loss-weighting problem. The effectiveness of negative reweighting depends on the balance between suppressing temporal false negatives and preserving informative hard true negatives.

목차 (Table of Contents)

• I INTRODUCTION 1
• II BACKGROUND 4
• 1 Temporal graphs 4
• 2 Temporal graph neural networks 4
• 3 Temporal link prediction as supervised learning 5
• 4 Why negative sampling is necessary 6
• 5 Temporal reachability and gamma table 7
• III RELATED WORK 10
• 1 Temporal graph neural network architectures 10
• 2 Negative sampling for link prediction 10
• 3 False negatives, robust losses, and temporal reachability 11
• IV TRANS 13
• 1 Problem formulation 13
• 2 Temporal false negatives and wrong-direction gradients 14
• 3 Temporal reachability evidence 15
• 4 Negative confidence estimator 16
• 5 Toy example of weight computation 18
• 6 Weighted BCE objective 20
• 7 Diagnostics and variants 20
• V EXPERIMENTS 22
• 1 Experimental setup 22
• 2 Predictive performance 24
• 3 False-negative exposure 24
• 4 Suppression versus preservation 27
• 5 Conditions for effectiveness 28
• VI CONCLUSION 32
• 1 Summary 32
• 2 Limitations and future work 32
• BIBLIOGRAPHY 34