[논문리뷰]Understanding Negative Sampling in Graph Representation Learning

Yang, Z., Ding, M., Zhou, C., Yang, H., Zhou, J., & Tang, J. (2020). Understanding Negative Sampling in Graph Representation Learning. ArXiv (Cornell University). https://doi.org/10.48550/arxiv.2005.09863

Summary

이 논문은 Knowledge Graph Embedding 모델을 학습함에 있어, negative를 랜덤하게 주는 것이 아닌, 확률적인 sampling을 통해 주는 방법을 제안했다. Markov Chain Monte Carlo (MCMC)를 통한 Negative Sampling을 제안했다. MCMC의 핵심은 Markov chain의 구성에 기반한 확률 분포(제안 분포, Proposal Distribution)로부터 정적 분포를 갖는 표본을 추출하는 것이다.

• Markov Chain
  • 어떤 상태에서 다른 상태로 넘어갈 때, 바로 전 단계의 상태에만 영향을 받는 확률 과정을 의미
  • 즉, 직전에 Sampling된 표본이 다음 표본을 뽑을 때 영향을 줌

Related Work

• Degree-Based Negative Sampling
  • Pros: 간단하고 빠르다. (Simple and fast)
  • Cons: 각각의 노드의 특징이 반영이 안됨. (Static, inconsiderate to the personalization of nodes)
• Hard-samples Negative Sampling
  • Pros: Hard negative를 직접적으로 샘플링함
  • Cons: 샘플링시 드는 비용이 클 수 있음.
• GAN-based Negative Sampling
  • 적대적으로 어려운 샘플을 생성 (adversially generate difficult samples)
  • 학습이 어려움 = 학습에 많은 시간 비용이 듬.

Method

MCNS의 핵심은 확률적인 분포를 이용하여 Negative의 분포를 추정하고 조건에 맞는 네거티브를 추출하는 것이다. MCMC 알고리즘을 이용하면 효율적으로 샘플링을 할 수 있다.

1. Approximated Positive Distribution

• Self-Constrast Approximation
  • 인코더를 이용해 \(p_d\)의 확률을 내적으로 대체한다.

이후 네거티브의 분포를 다음과 같은 식으로 추정하는 것이다.

하지만 모든 데이터에 대해 위의 식으로 샘플링을 진행한다면 소요되는 시간이 매우 길어진다. 따라서 논문에서는 Positive를 DFS로 Path를 뽑아 주었다. 이 DFS Path를 순회하며 각각의 노마다 정해진 네거티브 수만큼 샘플링을 시행한다.

GR 카테고리 내 다른 글 보러가기