[논문리뷰]Structure Aware Negative Sampling in Knowledge Graphs
카테고리: GR
Ahrabian, K., Feizi, A., Salehi, Y., Hamilton, W. L., & amp; Bose, A. J. (2020). Structure aware Negative Sampling in knowledge graphs. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). https://doi.org/10.18653/v1/2020.emnlp-main.492
Problem Statement(Abstract)
최근 자연어 처리(NLP)분야와 컴퓨터 비젼 분야를 기점으로, 많은 인공지능 분야에서 Contrastive learning 방식을 사용한다. Contrastive learning의 중요한 측면 중 하나는 hard Negative Sampling을 생성하는 손상 분포(corruption distribution)의 선택이다. 이는 임베딩 모델이 차별적 표현(discriminative representation)을 학습하고 관찰된 데이터의 중요한 특성을 찾도록 강요(forcing)하는 역할을 한다.
하지만 기존의 연구들에서는 Negative Sampling을 하는 일반적인 방법으로 corruption distribution을 단순하게 uniform distribution으로 간주한다. 이는 결과적으로 Knowledge Graph에 부적합하다. 명시적인 통합(의미적인 통합, semnatically incorporate)을 이루지 못한다. Uniform하고 고정된 sampling 방식은 학습 중 쉽게 분류 가능한 Negative triple을 생성하며, 이는 유의미한 정보를 모델에 전혀 제공하지 못한다. 이와 같은 이유로 ‘계산 비용(Computational cost)가 크지 않으며, 좀 더 그래프 구조를 반영할 수 있는 방법이 없는가?’라는 open question을 야기한다.
Related Work
1. Contrastive learning in Knowledge Graph
Knowledge Graph(KG)는 낮은 차원의 벡터 공간으로 인코딩하는 그래프 인베딩 기술을 활용한 방법이 급증하고 있으며, 이는 데이터 조작(data manipulation)을 용이하게 하는 동시에 데이터 희소성과 불완전성(sparsity & incompleteness)을 다루는 프레임워크이다. Contrastive estimation을 활용하여 KG 임베딩을 학습시키는 것ㅇ느 모델이 최적화하기 위해 관측된 positive triplet에 대한 energy, 영향력를 올리는 동시에 Negative triple에 대한 energy를 낮추는 과정을 포함한다. 결과적으로, Negative Sampling 분포의 선택은 Energy landscape를 형성하는 데 중요한 역할을 한다. 기존의 연구들을 간단하게 random sampling과 같은 방식으로 energy landscape를 구성한 것이다.
Self-adversarial Negative Sampling
이 방식이 처음 Knowledge Graph에 적용된 것은 Rotate모델이다. 간단하게 말하면 모든 Negative sample의 score에 대해 weight를 부여하는 방법이다.
Method
1. Overview
이 논문에서는 Negative Sampling distribution으로 uniform distribution을 사용하지 않는다. 논문에서의 핵심은 바로 Random Walk Algorithm이다. 이 논문에서는 서로의 이웃(neighbor)에 존재하지만 직접적인 관계를 공유하지 않는, Disconnected된 엔티티는 구조적으로 서로 관련되어 있을 가능성이 높고, 따라서 서로에 대한 Negative Sampling의 좋은 후보일 것이라 가정한다. 즉, target entity의 이웃에 존재하지만 직접적으로 연결이 되어있지 않은 엔티티들을 Center triple의 Negative로 사용하는 방식이다.
2. Structure Aware Negative Sampling
Triple (\(h, r, t\))가 주어졌을 때, Negative sample을 만드는 방법은 head 또는 tail을 바꾸는 것이다. 그러면 Negative sample은 (\(h^{'}, r, t\)) 또는 (\(h,r,t^{'}\))로 표현할 수 있으며, Negative를 만들어 내는 엔티티는 그래프 내에 존재하는 엔티티이다. 논문에서는 여러 가지 major한 Knowledge Graph Emnedding 모델을 가지고 실험을 하였는데, 기존의 모델들과는 달리 Self-Adversarial Loss를 사용하여 Negative에 대한 정보를 좀 더 강조해서 모델을 학습시켰다.
위 식에서 \(d_r(h,t)\)는 head와 tail에 대한 scoring function이다. Scoring function은 Loss에 직접적으로 들어가는 logit을 말한다. \(\gamma\)는 고정된 ma-rgin값이며 \(\sigma\)는 Sigmoid function이다. \(n\)은 Negative sample의 수이며 논문에서는 정보가 많은 그래프 구조를 이용하여, 특정 target에 이웃에 있지만 disconnected 된 명시적인 엔티티를 Negative로 sampling하는 방식을 사용하였다.
역사적으로 Negative Sampling이 발달한 Word Embedding 학습의 이전 작업에는 KG 설정에서 즉시 접근할 수 있는 그래프 구조의 풍부함(rich-ness)이 부족하다는 관찰에 기초하여 접근 방식을 잡았다. 결과적으로 구조 정보로 Negative Sampling Process를 풍부하게 하면 효과적인 임베딩을 학습하는 데 중요한 더 어려운 Hard Negative Sample들을 얻을 수 있다고 가정한다.
Figure 1. 첫 번째 단계에서 각 노드에 대한 k-hop neighborhood(K)를 구축해야 하는 접근 방식을 잘 보여준다.
\(k\)는 정수이고, \(k > 0\)일 때 이는 이웃의 직경(radius)를 표현한다. \(A\)는 인접 행렬(Adjacency matrix)이고 \(S^+\)는 element-wise sign 함수이다. 이 함수는 만약 path가 존재하는 경우 1, 아닌 경우 0으로 값을 mapping한다. 직관적으로 이 모델(SANS)은 랜덤하게 negative tail을 뽑는 것이 아니라, target의 이웃들을 고려해서 sampling하기 떄문에 어느정도 구조정보가 반영된다는 것을 알 수 있다. 하지만 이 negative sample들은 모두 target과는 직접적으로 연결이 되지 않은 2-hop이상 떨어져 있는 이웃 엔티티들로 구성된다. 이렇게 random walk를 이용해 직접적으로 연결되지 않은 이웃들을 negative로 사용할 경우 기존의 uniform하고 fixed된 방식보다는 모델이 좀 더 어려운 negative를 학습하는 것과 같다. 즉, Hard negative가 되는 것이다. K를 구성하는 디테일 중 하나는 여러 relation type의 존재로 인해 그래프 연결성을 인접 및 k-hop 텐서로 표현하기 위해 추가적인 차원이 필요하다는 것이다.
3. Pseudo Code
Experiment
Knowledge Graph Embedding모델들 중 TransE, DistMult, RotatE를 사용해 실험을 진행하였으며, 실험에 사용된 Dataset 역시 banchmark인 WN18RR 과 FB15K-237을 사용하였다.
실험을 통해 저자는 3가지 질문에 대한 답을 내놓는다.
- Q1. Hard Negatives: Can we sample hard negatives purely using structure?
- Q2. Can we combine graph structure with other SOTA negative samples?
- Q3. Can we effectively approximate the adjacencty tensor with random walks?
Q1. Hard Negatives: Can we sample hard negatives purely using structure?
첫 번째 질문은 ‘그래프 구조를 이용해서 hard negative sampling을 할 수 있는가?’ 에 대한 질문이다.
위의 표는 SANS(uniform distribution sampling)과 RW-SANS(Random Walk sampling)에 대한 결과를 보여준다. 전반적으로 SANS는 모든 세 데이터 셋에서 Uniform 및 KBGAN negative보다 거의 항상 더 hard negative sample을 얻는다는 것이 실험적으로 증명되었다. 또한 SANS는 TransE와 결합될 때 NSCaching과 충분히 경쟁력이 있는 성능을 달성하며, 추가적인 매개 변수를 필요로하지 않는 경우 DistMult에 적용할 때 두 번째로 성능이 좋은 알고리즘이다. 명백히, SANS를 통해 찾은 negative는 의미적으로 구분하기 어렵고, 결과적으로 Hard negative sampling에 그래프의 구조를 통합하는 것이 중요하다는게 입증되었다. 따라서, random walk를 이용해 그래프의 구조를 본 것이 좀 더 성능이 좋게 나온 것을 확인할 수 있다.
Q2. Can we combine graph structure with other SOTA negative samples?
두번 째 질문은 ‘SOTA를 달성한 모델들의 negative에 그래프 구조를 결합할 수 있는가?’이다. 이를 확인하기 위해 SANS와 RW-SANS에 Self Adversarial loss를 결합하여 실험을 진행하였다.
결론적으로, 그래프 구조를 적용하였을 때 좀 더 좋은 성능을 보여주었으며, 부분적으로 채워진 Adjacency tensor를 고려함으로써, 더 적은 메모리를 필요로 하며 희소 텐서 연산을 수행할 수 있는 계산적 실현성이 향상되었다는 점을 고려하면, Negative Sampling시 그래프 구조를 통합하는 것이 성능 향상으로 귀결된다는 걸 알 수 있다.
Q3. Can we effectively approximate the adjacencty tensor with random walks?
마지막 질문은, ‘인접 행렬 텐서를 random walk를 이용하여 좀 더 효율적으로 근사할 수 있는가?’이다. 이걸 실험하기 위해 random walk cycle수(\(\mathcal{w}\))를 조정해가며 진행하였다.
k-hop 텐서가 3000개의 random walf로 잘 근사될 뿐만 아니라, RW-SANS가 두 가지 baseline을 모두 압도한다는 것이다. 이는 특정 엔티티가 중심 엔티티와 더 많은 경로를 공유하며 샘플링될 확률이 높아지기 때문에, 암묵적으로 weighted negative sampling 체계가 형성되기 때문이다.
Ablation Study
Contribution
Knowledge Graph모델에 Random walk 알고리즘을 이용해 negative sampling을 하는 방식을 적용하였고, 결론적으로 그래프의 구조를 고려한 샘플링 방법을 제시하였다.
댓글 남기기