[Study]Chapter 10. Knowledge Graph Embeddings

Posted Sep 12, 2023 Updated Apr 28, 2024

By Eastk1te

12 min read

해당 내용은 개인적으로 정리한 내용임으로 틀린 부분이 있을 수 있습니다.

지금까지 무방향 그래프를 다루었고 이제는 다양한 edge type을 가지는 방향 그래프(a.k.a heteroheneous graph)와 지식 그래프에 대해서 설명한다.

I. Heterogeneous graphs and relational GCN(RGCN)

1. Heterogeneous graph

\[G = (V,E,R,T)\]

2. RGCN : Relational GCN

GCN을 확장하여 다양한 edge와 relation 타입을 가지는 헤테로지니어스 그래프를 다룰 것이다. 우선 한개의 관계를 가진 무방향 그래프로 부터 시작한다.

Figure 1 : (좌)여러 관계 edge를 가지는 그래프 (우) 각 관계 type 마다 신경망 가중치를 할당한 계산 그래프

만약 그래프 안에 다양한 관계 타입이 존재한다면, 관계 타입마다 다른 신경망 가중치를 사용해야한다.

Figure 2 : RGCN의 aggregation function; 관계의 노드 degree를 정규화 상수(\(c_{v,r}=\frac{1}{\vert N_v^r\vert}\))로 사용한다.

Message
\[\begin{array}{ll} m_{u,r}^{(l)}=\frac{1}{c_{v,r}}W_r^{(l)}h_u^{(l)}\\ m_{v}^{(l)}=W_0^{(l)}h_u^{(l)}\text{; self-loop} \end{array}\]
Aggregation
\[h_v^{(l+1)}=\sigma(Sum(\{m_{u,r}^{(l)}, u \in \{N(v)\} \cup \{v\}\}))\]
이웃과 셀프 루프에서 온 메시지들위에서 합하고 activation을 적용한다.
Scalability
각 관계는 L개의 행렬(\(W_r^{(L)}\))들을 가지고, 사이즈는 \(d^{(l+1)} \times d^{(l)}\)이 된다.

3. Regulation

가중치 \(W_r^{(L)}\)는 관계 수에 관하여 파라미터가 빠르게 증가해 과적합 문제를 해결하기 위해 아래와 같은 정규화 기법을 사용해야 합니다.

block diagonal matrices
Figure 3 : block diagonal matrices
핵심은 가중치를 희소하게 만드는 것으로 이는 근처에 있는 신경(차원)에서만 가중치를 통해 상호작용 가능하다는 제한으로 저차원 행렬을 사용하면 파라미터의 #는 \(B\times \frac{d^{(l+1)}}{B} \times \frac{d^{(l)}}{B}\)로 줄어들어 모델의 복잡성을 줄이고 계산 효율성을 향상 시킵니다.
basis/dictionary learning
해당 핵심은 다른 관계를 지날때 가중치를 공유하는 것입니다. 각 관계 행렬을 아래와 같이 basis 변형의 선형 조합으로 표현합니다.
\[W_r = \sum_{b=1}^{B}a_{rb}\cdot V_b\]
\(V_b\)는 모든 관계에 걸쳐 공유되고, basis matrices(\(a_{rb}\))는 행렬V의 중요 가중치입니다. 따라서, 이제 각 관계는 \(\{a_{rb}\}^B_{b=1}\)만 학습하면 된다. 이러한 방식은 관계에 대한 기본적인 구조를 나타내는 기저 행렬의 공유를 통해 일반화를 향상시키고 효율적인 학습을 가능하게 합니다.

4. Example(link prediction split)

모든 edge들은 독립적인 4가지의 관계 타입을 가지고 있는 헤테로지니어스 그래프로 모든 단일 관계로 형성된 동질의\(_{homogeneous}\) 그래프들도 4개의 분할로 이루어졌습니다.

Figure 4 : ex. \(f_{r_1}(h_E,h_A) = h^T_EW_{r_1}h_A, W_{r_1} \in \mathbb{R}^{d \times d}\)

\((E,r3, A)\)는 학습 지도 edge이고 다른 edge들은 학습 메시지 edge입니다.
RGCN을 이용하여 (E,r3, A)에 점수를 매긴다.
마지막층에서 \(A:h_A^{(L)}\) and \(E:h_E^{(L)}\)를 받아서 관계-특정 스코어 함수(\(f_r:\mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}\))에 넣음.
Training
Figure 10-5:좌측항은 시그모이드 안에 학습 지도 간선, 우측항은 시그모이드 안에 negative edge
1. RGCN을 사용하여 학습 지도 edge \((E,r3, A)\)의 점수화
  - 학습 메시지 edge는 Figure 4에서 존재하는 모든 edge(solid lines)들이다.
2. 감독 edge를 혼란시키는 negative edge(\(\notin\) 학습 edges)를 생성.
3. GNN 모델을 사용하여 negative edge를 점수화.
4. 정규 CE loss를 최적화.
Evaluation
평가 edge \((E,r3, D)\)를 예측합니다. 이 edge는 학습 메시지와 학습 지도 edge에 없기 때문에 초기의 \((E,r3, D)\)의 점수는 \((E,r3, v)\)보다 높을 것입니다.
1. (E,r3, D)의 점수 계산
2. 모든 negative edge의 점수를 계산
3. (E,r3, D)의 랭킹 RK를 얻는다.
4. metrics를 계산한다.
  - Hits@k : 상위 K개의 edge 중 실제 평가 edge가 등장하는 개수
  - reciprocal rank : \(\frac{1}{RK}\)

II. Knowledge graphs : KG completion with embeddings

그래프 지식인 엔티티, 타입, 관계를 수집하는 것으로 헤테로지니어스 그래프의 한 예이다.

Figure 6 : example of Knowledge Graphs

지식 그래프의 일반적인 특징으로는 아래와 같다.

거대한 KG가 주어졌을때 가능한 경우를 모두 나열하는것은 매우 다루기 힘들다\(_{intractable}\). 이러한 경우 가능성 있는 링크를 예측할수\(_{plausible}\) 있을까?

III. Knowlege grtaph completion : TransE, TransR, DistmMul, Complex

KG completion task는 거대한 KG가 주어졌을때 KG를 완전하게(missing link를 연결) 만드는 Task로 (head, relation)이 주어졌을때 잃어버린 tail을 예측한다.

Figure 8 : (“J.K. Rowling”, “genre”)가 주어졌을때, 누락된 tail인 “Science Fiction”을 예측한다.

1. representation of KG

KG는 각각의 head, relation, tail인 (h,r,t)의 세쌍으로 표현됩니다.

주된 핵심은 임베딩 공간에서 엔티티와 관계를 모델링하는 것으로 이러한 shallow embedding을 통해 실제 세쌍이 주어졌을때 목표는 (h,r)의 임베딩을 (t)의 임베딩에 근접하게 만드는 것입니다.

그럼 (h,r)을 임베딩하는 방법과 (t)와의 근접함을 정의하는가?

Figure 9 : KG completion Model Seqeunce

2. connectivity patterns in KG

Figure 11 : 지식 그래프 KG에서의 연결 패턴

symmetric relation
\[r(h,t) \Rightarrow r(t,h)\]
ex. A는B의 룸메이트이다. B의 룸메이트는 A이다.
antisymmetric relation
\[r(h,t) \Rightarrow \neg r(t,h)\]
ex. A의 담임선생님은 B이다. B의 담임선생님은 C이다.
inverse relations
\[r_2(h,t) \Rightarrow r_1(t,h)\]
ex. A의 선생님은 B이다 B의 학생은 A이다
composition(transitive) relation
\[r_1(h,t) \wedge r_2(t,h) \Rightarrow r_3(x,z)\]
ex. 엄마의 남편은 내 아빠이다.
1-to-N relation
\[r(h,t_1), r(h,t_1), ..., r(h,t_n) \Rightarrow True\]
ex. A의 직업은 학생이다. A의 직업은 학원 성생님이다.