[논문리뷰]Investigating the Effect of Hard Negative Sample Distribution on Contrastive Knowledge Graph Embedding

Zhang, H. (2023, May 17). Investigating the effect of hard negative sample distribution on contrastive knowledge graph embedding. “arXiv.org. https://arxiv.org/abs/2305.10563”

Knowledge Graph 분야에서 “SimKGC”와 같이 자연어 기반의 모델을 적용하고, negative sampling을 통한 Contrastive learning의 연구가 활발히 진행되고 있다. 본 논문인 Investigating the Effect of Hard Negative Sample Distribution on Contrastive Knowledge Graph Embedding 역시 Knolwedge Graph Complition에 Contrastive learning을 적용한 연구이며, 특히 기존의 negative sampling 방식에서 벗어나, 자연어 처리와 컴퓨터 비젼 분야에서 많은 연구가 이루어지고 있는 Hard Negative Sampling방식을 KGC에 성공적으로 적용했다는 것이 가장 큰 Contribution이다.

Problem Statement

Gap between the negative samples and heuristic generation quality negative samples
Knowledge Graph Complition 분야에서도 최근들어 그래프의 Text description을 이용하여 그래프 정보를 학습하는 모델에 관한 논문이 많이 등장하였다. 특히, SimKGC같이 자연어 모델과 더불어 Contrastive learning을 접목하여 banchmakr dataset인 WN18RR에서 SOTA를 달성한 모델도 등장했다. Batch수를 늘리고, negative sampling을 통한 성능 향상에도 불구하고 여전히 general한 그래프에서 Link prediction에 좋은 성적을 내지는 못한다. 저자는 이러한 문제점을 ‘Gap between the negative samples and heuristic generation quality negative samples’라고 말한다. 즉, 특정 classification task에서 사용되는 negative sample과 특정 heuristic 방법을 사용하여 생성된 negative sample을 말한다. 이 때, random하게 생성된 negative sample과 특정한 메커니즘을 통해 만들어진 negative sample간에 모델을 학습하는데 있어서 random 생성 negative sample들은 오히려 noise로 작동할 수 있다. 저자는 이러한 이유로 그래프 내의 shortest path length를 이용한 hard negative sampling 방식을 제안한다.

Related Work

1. Notation

Knowledge Graph는 Triple이라는 단위로 데이터가 저장된다. Graph는 \(\mathcal{G} \; = \; (\mathcal{E}, \mathcal{R}, \mathcal{T})\) 로 정의한다. \(\mathcal{E}\)와 \(\mathcal{R}\)은 각각 Entity Set과 Relation Set을 의미하고 \(\mathcal{T}\)는 Triple Set을 의미한다. \(\mathcal{T} = {(h,r,t) \vert h,r \in \mathcal{E}, r \in \mathcal{R}}\)의 관계를 가진다. 즉, Triple은 head와 tail의 관계를 relation으로 표현한 것이며, 논문에 따라서 head를 subject, realtion을 predicate 그리고 tail을 object로 기술하기도 한다. Knowledge Graph Completion (KGC)이라는 것은 \((h,r)\)이 주어졌을 때 관계에 알맞는 \(t\)를 찾는 것이 목표인 task이다.

2. InfoNCE Loss with Simple Negative Triples

InfoNCE Loss는 contrastive learning을 할 때 사용하는 대표적인 loss로, Cross-Entropy가 InfoNCE Loss의 Special Case라고 할 수 있다. Knowledge Graph에서 \((h,r,t) \in \mathcal{T}\)가 주어졌을 때 K개의 negative sample을 독립적으로 동일 분포내에서 추출할 수 있다. 이 때 동일 분포에 대한 확률 값을 \(p^{-}(t)\)로 표현하고 negative sample을 \((h,r,t^{'})\)로 표현한다. 이 때 Original InfoNCE Loss는 다음과 같다.

이 때, \(e_{t_j}^{-}\)는 negative tail \(t_j^{-}\)의 임베딩이다. 기존의 연구들을 통해 InfoNCE loss는 log Bayesian 모델과 동일하다. 따라서 아래와 같이 loss식을 정의할 수 있다. \(\mathcal{T_{batch}} \subseteq \mathcal{T}\)이며, #\((t)\)가 \(\mathcal{T_{batch}}\)에서 발생한 횟수를 의미한다.

이 때 \(p^{-}(t)\)는 negative sample의 분포를 의미한다. 이 분포는 simple distribution으로 단순히 batch안에서 negative sample이 발생 횟수만을 따지기 때문이다. 기존의 SimKGC는 이처럼 batch안에서 단순한 방식으로 Negative sampling을 진행하였다.

Method

1. InfoNCE Loss with Hard Negative Triples

Hard negatives triples are harder to distinguish from the triples in the KG than arbitrarily generated negative samples. One way to generate hard negative triples is to sample the tail entity from a negative sample distribution that also considers the context.

KGE 알고리즘에서는 종종 heuristics를 이용해 hard negative를 생성해낸다. 이런 hard negative를 통해 성능을 최대화하기 위함이다. Hard negative triple들은 실제 정답과 구분하기 힘든 negative triple이다. 다시 말해, \((h,r)\)이 주어졌을 때 정답 tail과 가까운 엔티티들로 이루어진 triple이다. 이러한 hard negative를 추찰하는 방법 중 한 가지는 앞서 언급한 random하게 추출하는 것이다.

논문에서는 이러한 방식은 너무 단순하기에 다른 sampling방식을 제안한다. 바로 tail 엔티티를 negative sampling 하되, context를 고려해서 추출하자는 것이다.(일종의 Context Sub-Graph) 정확하게 말하면, Structural Context information을 사용하여 negative tail을 뽑는 것이다. 그래프의 구조적인 정보를 이용하여, Training set으로 들어온 triple의 tail을 hop수에 dependent하게 바꿔가며 negative를 주는 방식이다.

이와 같은 negative sampling방식을 InfoNCE Loss에 적용하면 위와 같이 식이 변형된다. 본 논문에서는 hard negative triple을 만들 때 Shortest path를 고려하였고, 이를 위해 새로운 확률 분포를 정의하였다. 다시 말해, 정답 triple(Ground Truth)의 hr 임베딩 \(e_{hr}\)에 대한 여러 tail(candidate entities)의 preference를 구하고, 그 임베딩이 가까우면(문맥적으로 의미가 있으면) 더 높은 preference를 부여한다. 이 방식은 KBGAN과 RotatE와 유사하다.

Generate hard negative triples by giving higher preference to the tail entities whose embeddings are close to the context embedding

Using structural context information, extract negative tails (h,r,t) => (h,r,t’)

학습을 시작할 때는, 임베딩과 aggregation function에 대해 논문에서는 Sentence-BERT를 이용해 \(e_{hr}, e_t, e_t^{-}\)를 initialization하였다. 앞에서 제시한 Preference에 근거해 뽑은 K개의 negative sample들을 추출하고 그를 수식으로 나타내면 다음과 같다.

Proposition 1. Hard negative를 적용한 InfoNCE loss는 Joint distribution \(p(e_{hr}, e_t)\) 와 \(p(e_{hr}, e_t^{-})\) 사이의 Kullback-Leiber divergence에 lower bound를 준다. 저자는 이러한 근거들을 이용해 InfoNCE loss를 minimization하면 True Triple과 Hard negative와의 임베딩이 다르게 분포하게 될 것이라 예측하였다.

2. Hard Negative Triple may be False Negative Triple

False negative란 실제로는 정답인데 거짓으로 잘못 예측한 것을 말한다. Graph의 구조 특성상 하나의 엔티티에 여러 개의 이웃이 있기 때문에 실제 정답 Triple에 대해서 head의 다른 이웃을 tail로 모델이 잘못 예측할 수 있다. 이처럼 head의 직접적인 이웃이 hard negative이며, 이 hard negative들을 결국 false negative가 될 확률이 높다. 논문에서는 이러한 False negative의 수를 파악하기 위해서 Banchmark dataset FB15k-237과 WN18RR을 통해서 실험을 진행하였다. 임의로 랜덤하게 30%의 트리플을 train set에서 지우고 이 set을 \(\mathcal{T_{missing}}\)으로 정의하였고, 원래의 set을 \(\mathcal{T_{retain}}\)으로 정의했다.

retain set에서 K개의 negative sample을 앞서 제시한 확률 분포를 이용해 sampling하였고, 만약 negative triple이고 \(\mathcal{T_{missing}}\) set에 존재하는 Triple이면 이 triple은 실제로는 존재하는 triple이며 이 것이 바로 False negative가 되는 것이다. False Triple이 missing set에서 발견이 되지 않으면 True negative이다. 각 Dataset에서 서로 다른 크기의 batch 사이즈로 실험을 진행하였고, K는 hyperparamter로 \(K = 5 \vert \mathcal{T_{batch}} \vert - 1\)로 정의하였다.

다시 강조하자면, \(p^{-}(t)\)는 random negative sampling에 대한 확률 분포이고, 위의 실험 결과에서 파란색이고 결론적으로 False negative가 더 적다. 반면, Hard negative는 \(p^{-}(t \vert e_{hr})\)의 분포를 따라 negative를 samling한 것이고, 실험 결과는 초록색이다. 랜덤 샘플링 방식과 비교했을 때 매우 많은 False negative를 가지는 것을 볼 수 있다.

3. Shortest Path Length Distinguishes True and False Negative Triple

Context information을 사용하고, BERT같은 자연어 모델을 사용해 양방향으로 학습을 진행하므로, Knowledge Graph를 먼저 Undirected하며 Unweighted Graph로 가정하고 실험을 진행한다. 이 때 false negative들이 실제로 head로부터 얼마나 떨어져 있는지, shortest path를 구하는 실험을 진행하였다. 이를 통해 각 data set별로 평균적으로 몇 hop에서 false negative가 많은지 확인할 수 있다.

4. Debiased InfoNCE Loss with Hard Negative Triples

기존에 진행되었던 contrastive learning 연구에서, debiased contrastive loss에 대한 연구가 있다. 이 loss는 InfoNCE loss에 false negative까지 고려해 좀 더 어려운 문제를 푸는 방향성을 제시해 준 연구이다. 이 Loss는 클래스 불균형 문제를 해결하는 데 도움을 준다. 클래스 불균형 문제는 어떤 클래스의 샘플이 다른 클래스보다 훨씬 많거나 적은 경우 발생한다. 이런 상황에서 모델이 클래스 불균형을 무시하고 항상 다수 클래스를 예측하는 경향을 가질 수 있다. Debiased constrastive loss는 이러한 문제를 완화하고 모델을 더 균형 잡힌 예측을 할 수 있도록 도와준다.

마찬가지로, Hard negative sample에 대해 fatual하냐 non-factual하냐에 따라 latent label을 부여해 이 Loss를 이용할 수 있다. 이렇게 정의한 Loss를 논문에서는 \(\mathcal{L_{HaSa}}\)라고 정의하였고, 좀 더 풀어서 설명하자면 Debiased InfoNCE with Hard Negative triple이며, 논문에서 제시한 최종 모델을 이 식을 따라 학습을 진행하였다.

앞선 실험 결과들을 토대로, Negative sampling을 하는데 기존과는 다른 새로운 Loss를 사용하였고, 그렇기 때문에 새로운 확률 분포에 따라 negative sampling을 해야한다. 논문에서는 이를 위해 hop수에 대해 새로운 확률값을 주어서 negative sampling을 진행하였다. 조금은 naive한 방식으로 확률을 주었는데, 바로 기준이 되는 head로부터 1-hop과 2-hop 거리에 있는 엔티티들의 개수의 역수로 확률을 부여하였다. 여기서 잠시 생각해볼 점은 ‘왜 개수의 역수로 확률을 부여했는가?’이다.

3번식을 살펴보면 Hard negative sampling을 위한 새로운 precision식을 제시한다. 여기서 \(\alpha(t \vert e_{hr})\)이 바로 거리에 대한 확률 분포값이다. 만약 거리에 대해 비례해서 확률 값을 부여하면, shortest path가 길어질수록 더 높은 확률을 부여받게 되고 이는 Hard negative와는 거리가 멀어진다. 따라서 거리에 대해 반비례하게 확률값을 부여하는 것이다. 최종적으로 5번식과 같이 negative sampling에 대한 기댓값이 만들어진다. 2번과 5번식을 보면 알 수 있지만, non-factual한 값에 대하여 Law of Total Expectation을 이용한다. 그 이유는, Negative sample을 뽑을 때 직접적으로 direct하게 그 negative가 fatual한지 아니지 모르기 때문에 확률값을 \(Negative(N) = 1 - Positive(P)\)로 부여하는 것이다.

5. Improved HaSa: Hasa+

HaSa보다 negative를 좀 더 어렵게 주기 위해서 tail만 corruption하는 것이 아닌, (\(h,r,t\))를 모두 corruption하는 것이다. 즉 HaSa에서는 negative sample로 (\(h,r,t^{-}\))를 뽑았다면, HaSa+에서는 (\(h^{-},r^{-},t^{-}\))를 뽑는 것이다.

Experiment

1. Dataset

Dataset은 Banch mark인 WN18RR과 FB15k-237을 사용했으며, Evaluation metric으로는 MR(Mean Rank), MRR(Mean Reciprocal Rank)과 Hit@N을 사용했다.

2. Training Process

• Embedding function \(f (\cdot)\)을 sentence-BERT를 통해 만들며, sentence-BERT를 통해 함수를 만들 때 차원을 500(d = 500)까지 줄여서 만든다.
• Aggregation function \(g(\cdot)\)은 Gated Recurrent unit (GRU)로 사용한다.
• Optimization은 PyTorch AdamW를 이용, learning rate(lr) = \(2 \times 10^{-5}\)
• 학습 시 batch size는 \(\mathcal{T_{batch}} = 256\)으로 둔다.
• Negative sample 수 \(K\)는 \(K = 5 (\vert \mathcal{T_{batch}} \vert) -1\)로 둔다.

3. Result

1) Comparing InfoNCE with Simple Negative Samples and Hard Negative Samples

위의 결과를 보면 알 수 있지만, 대부분의 evaluation metric에서 hard negative를 이용해 sampling할 경우 성능이 더 올라간 것을 확인할 수 있다. Plot은 Epoch별 MRR과 Hit@1을 나타낸다.

2) Comparing HaSa and HaSa+ to Other KGE Methods

HaSa+가 HaSa보다 좀 더 좋은 성능을 보이는 것을 확인할 수 있다. t-SNE를 통해서 알 수 있는 사실은 주어진 True head와 relation에 대해 Positive tail이 임베딩 공간에서 같이 clustering되어 있다는 사실이다.

3) Effect of Hyperparameter \(\tau\)

• 𝛕 증가
  • Distribution이 smooth해짐. Positive-Negative 간 유사도 차이가 감소한다. 더 큰 τ는 모델이 더 부드러운 결정을 생성하게 만들며, 훈련이 더 쉬워지지만 유용한 표현을 학습하는데 방해가 될 수 있다.
  • 부드러운 확률 분포: 높은 τ 값은 확률 분포를 더 부드럽게 만들며, 모델은 positive와 negative 샘플 간의 차이에 덜 민감하게 된다.
  • 더욱 일반적인 학습: 높은 τ 값은 학습이 더욱 부드럽고, 일반적으로 이루어지게 한다.
  • This smoothens the distribution, decreasing the difference between the similarities of positive and negative samples. A larger τ makes the model produce softer decisions, making the training potentially easier but possibly less discriminative as it won’t differentiate as strongly between positive and negative pairs.
• 𝛕 감소 (for hard negative → Inv_T 는 증가)
  • Distribution이 sharp해짐. Positive-Negative 간의 유사도 차이가 커진다. 더 작은 τ는 정확한 일치에 대한 중요도를 높이고, 훈련을 더욱 집중시키지만, 모델이 더 명확한 결정을 내리도록 강요하기 때문에 훈련이 어려워질 수 있다.
  • 날카로운 확률 분포: 낮은 τ 값은 모델이 positive 샘플과 negative 샘플 간의 차이를 더욱 명확하게 인식하게 만든다.
  • 더 빠른 수렴: τ 값을 낮추면 모델이 더 빠르게 수렴할 가능성이 있다.
  • 강렬한 업데이트: 낮은 τ 값은 모델이 선택적으로, 더욱 강렬하게 업데이트다.
  • This makes the distribution sharper, amplifying the difference between the similarities of positive and negative samples. A smaller τ leads to higher importance to exact matches and making the training more focused but potentially harder, as the model is forced to make more distinct decisions.
  • If τ is small, the softmax function becomes sharper, meaning that even small differences in the similarity scores will result in a larger difference after the softmax

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