<CS224W> Lecture 10. Knowledge Graph Embeddings

kimkj38·2022년 4월 7일
0

CS224W

목록 보기
10/17

1. Heterogeneous Graphs and Relational GCN(RGCN)

RGCN

  • Heterogeneous graph는 노드 VV 엣지 EE, 노드의 종류 TT, 관계성 종류 RR로 구성된다.
  • GCN은 이전 레이어에서의 이웃 노드와 자기 자신의 임베딩 벡터를 받아 선형변환을 하는 message transformation과 이를 summation해주는 aggregation 과정으로 이루어진다.
  • RGCN에서는 엣지마다 다른 정보를 가지고 있으므로 message transformation 과정에서 다양한 WW를 가지게 된다.
  • 따라서 RGCN은 관계에 대한 summation이 추가된다.
  • cv,rc_{v,r}Nvr|N_v^r|로 relation까지 고려하여 정규화하기 위한 node degree이다.
  • W0(l)hv(l)W_0^{(l)}h_v^{(l)}은 self-loop에 대한 항이다.

Saclability

  • RGCN은 매 레이어 및 관계마다 다른 weight matrix를 가지기 때문에 파라미터 수가 많아 과적합이 발생하기 쉽다.
  • 과적합 문제를 해결하기 위해 block diagonal matrixbasis learning이 사용된다.

Block Diagonal Matrix

  • Weight matrix를 대각 방향의 block 부분행렬로 구성하여 sparse하게 만든다.
  • 파라미터의 수가 dl+1×dd^{l+1} \times d'에서 B×dl+1B×dlBB \times \frac{d^{l+1}}{B} \times \frac{d^{l}}{B}로 줄어들지만 근처 노드들끼리만 연결된다는 한계점이 있다.

Basis Learning

  • Basis의 선형결합을 활용하여 서로 다른 관계들이 weight를 공유하도록 만든다.
  • Wr=b=1BarbVb\mathbf{W}_{r}=\sum_{b=1}^{B} a_{r b} \cdot \mathbf{V}_{b}
  • VbV_b: basis matrix
  • arba_{rb}: 행렬 VbV_b의 importance weight

Split

  • RGCN에서 일부 관계들은 데이터 수가 적어 랜덤 샘플링 할 경우 그 관계들이 validation이나 test에 없을수도 있다.
  • 따라서 층화학습을 통해 모든 관계가 비슷한 분포로 split 되도록 만들어주어야 한다.

Training

  • Training supervision edge: 예측할 엣지 (E,r3,A)(E, r_3, A)
  • Training message edge: 예측을 위해 사용하는 message 엣지(solid lines)
  • Negative edge: (E,r3,B),(E,r3,D)(E,r_3,B), (E,r_3,D)와 같이 supervision/message edge에 모두 속하지 않는 엣지.
  • RGCN을 통해 구한 임베딩 벡터를 통해 supervision edge와 negative edge에 대한 스코어를 구한 뒤 전자는 최대화, 후자는 최소화가 되도록 cross entropy loss를 활용한다.(Lecture6 참조)
    =logσ(fr3(hE,hA))log(1σ(fr3(hE,hB)))\ell=-\log \sigma\left(f_{r_{3}}\left(h_{E}, h_{A}\right)\right)-\log \left(1-\sigma\left(f_{r_{3}}\left(h_{E}, h_{B}\right)\right)\right)
  • 각 관계마다 다른 파라미터를 가져야 하므로 함수 frf_r은 관계의 개수만큼 존재한다.

Evaluation

  • Validation edge (E,r3,D)(E,r_3,D)에 대한 스코어와 negative edges에 대한 스코어를 구한 뒤 hit@k나 reciprocal rank와 같은 목적함수로 전자의 스코어가 더 높도록 만든다.

2. Knowledge Graphs: KG Completion with Embeddings

Knowledge Graph(KG)

  • 지식 그래프는 heterogeneous graph의 일종으로 노드 간의 관계를 도메인 정보를 기반으로 정의한다.
  • 페이스북과 같은 거대한 지식 그래프에서 모든 노드가 연결되어 있지는 않기 때문에 가능성이 높은 엣지를 찾는 것이 중요하며 이를 Knowledge Graph Completion이라 한다.

KG Completion Task

  • Link prediction과 달리 completion은 노드 하나와 엣지가 주어질 때 부합하는 노드를 예측하는 task이다.

3. Knowledge Graph Completion: TransE, TransR, DistMul, ComplEx

  • KR은 (h,r,t)(h,r,t)로 표현되며 각각 head, relation, tail을 의미한다.
  • (h,r)(h,r)의 임베딩이 tt의 임베딩에 가까워지도록 만들어야 한다.

Connectivity Patterns

  • Symmetric relation: 룸메이트와 같이 head와 tail이 바뀌어도 동일한 관계
  • Antisymmetric relation: 상위어와 같이 head와 tail이 바뀌면 성립하지 않는 관계
  • Inverse relation: Advisor, Advisee와 같이 서로 반대되는 개념의 관계
  • Composition relation: 엄마의 남편=아빠와 같이 합성하면 성립되는 관계
  • 1-to-N relation: 교수의 학생들과 같이 하나의 head가 여러 tail을 가지는 관계

TransE

  • (h,r,t),h,r,tRd(h,r,t),h,r,t \in \mathbb{R}^d에 대해 h+rth+r \approx t가 성립되게 만드려고 한다.
  • ((h,l,t),(h,l,t))Tbatch [γ+distance(h+l,t)distance(h+l,t)]\sum_{\left((h, l, t),\left(h, l, t^{\prime}\right)\right) \in T_{\text {batch }}} \nabla\left[\gamma+\operatorname{distance}(h+l, t)-\operatorname{distance}\left(h+l, t^{\prime}\right)\right]
    관계가 성립하는 tt에 대해서는 거리를 최소화하고 관계가 성립하지 않는 tt'에 대해서는 거리를 최대화하도록 만들어 학습한다.
  • Antisymmetry, Inverse, Composition은 TransE로 잘 정의된다.
  • Symmetric이 성립하기 위해서는 h+r=th+r=tt+r=ht+r=h가 모두 성립해야 하므로 h=th=t가 되는데 이는 두 노드가 동일함을 의미하므로 TransE로는 설명되지 않는다.
  • 1-to-N 또한 h+rh+rt1,t2t_1, t_2 모두와 동일해야 하지만 두 노드는 다르므로 표현할 수 없다.

TransR

  • TransR에서는 entity의 공간 h,tRdh,t \in \mathbb{R}^d와 relation의 공간 rRkr \in \mathbb{R}^k을 분리하고 entity를 relation 공간으로 맵핑하는 선형변환 MrRk×kM_r \in \mathbb{R}^{k \times k}을 정의한다.

  • 각 relation마다 다른 공간을 가져 그에 따른 MrM_r을 가진다.

  • score function은 fr(h,t)=h+rtf_r(h,t) = -||h_{\bot} + r - t_{\bot}||h,th_{\bot}, t_{\bot}는 relation 공간으로 투영된 entity들을 의미한다.

  • TransR에서는 entity 공간에서 다르더라도 relation 공간에서는 같은 점으로 맵핑하는 관계를 만들 수 있기 때문에 symmetric을 정의할 수 있다.

  • 1-to-N 또한 동일한 이유로 가능하다.

  • Antisymmetric과 Inverse는 맵핑을 하더라도 TransE와 동일한 모습이므로 가능하다.

  • Relation에 따라 각각 다른 공간을 만들기 때문에 위와 같은 관계를 하나의 선형변환으로 표현하기는 어려워 composition은 표현할 수 없다.

DistMul

  • DistMul은 L1, L2 distance 대신 코사인 유사도를 활용하여 score function을
    fr(h,t)=<h,r,t>=ihiriti,h,r,tRkf_r(h,t) = <h,r,t> = \sum_{i} \mathbf{h}_{i} \cdot \mathbf{r}_{i} \cdot \mathbf{t}_{i}, h,r,t \in \mathbb{R}^k로 정의한다.
  • 즉, score function은 elment wise product인 hrh \cdot rtt의 내적값으로 hrh \cdot r 벡터에 수직인 초평면을 기준으로 tthrh \cdot r쪽에 위치하면 양수, 반대편에 위치하면 음수가 된다.

  • hrh \cdot r과 동일한 각을 가지는 직선 상에 여러개의 tt들이 있을 수 있으므로 1-to-N은 표현할 수 있다.
  • Element wise product는 교환법칙을 성립하므로 symmetric 관계 또한 표현할 수 있다.
    fr(h,t)=<h,r,t>=ihiriti=itirihi=<t,r,h>=fr(t,h)f_{r}(h, t)=<h, r, t>=\sum_{i} h_{i} \cdot r_{i} \cdot t_{i}=\sum_{i} t_{i} \cdot r_{i} \cdot h_{i}=<t, r, h>=f_{r}(t, h)
  • 교환법칙이 성립하여 fr(h,t)fr(t,h)f_{r}(h, t) \neq f_{r}(t, h)을 유도할 수 없으므로 antisymmetry는 나타낼 수 없다.
  • 하나의 관계가 하나의 초평면을 만드므로 두 관계의 교집합은 두 관계의 초명면의 교집합을 의미하는데 이는 하나의 초평면으로 표현할 수 없으므로 composition은 정의되지 않는다.
  • Inversefr2(h,t)=<h,r2,t>=<t,r1,h>=fr1(t,h)f_{r_{2}}(h, t)=<\mathbf{h}, \mathbf{r}_{2}, \mathbf{t}>=<\mathbf{t}, \mathbf{r}_{1}, \mathbf{h}>=f_{r_{1}}(t, h)를 만족하기 위해 r2=r1r_2 = r_1가 되어야 하는데 두 관계는 반대여야 하므로 표현할 수 없다.

ComlEx

  • ComlEx는 복소수 체에서의 벡터 공간으로 임베딩 벡터의 공간을 확장한다.

  • DistMul을 복소수 체에서 다뤄 켤레를 활용할 수 있다.

  • Score function은 DistMul과 동일하며 실수 부분만 취한다.

  • DistMul에서와 동일한 이유로 1-to-N은 표현 가능하며 composition은 표현 할 수 없다.

  • 켤레전치를 통해 antisymmetric을 표현할 수 있다.
    fr(h,t)=Re(ihiritˉi)fr(t,h)=Re(iti,rihˉi)\begin{aligned} &f_{r}(h, t)=\operatorname{Re}\left(\sum_{i} h_{i} \cdot r_{i} \cdot \bar{t}_{i}\right) \\ &f_{r}(t, h)=\operatorname{Re}\left(\sum_{i} t_{i}, \cdot r_{i} \cdot \bar{h}_{i}\right) \end{aligned}

  • Relation의 허수 부분이 0일 때 symmetric도 표현할 수 있다.
     When Im(r)=0fr(h,t)=Re(ihiritˉi)=iRe(rihitˉi)=iriRe(hitˉ)=iriRe(hˉiti)=iRe(rihˉiti)=fr(t,h)\begin{aligned} &\text { When } \operatorname{Im}(r)=0 \\ &\qquad \begin{aligned} f_{r}(h, t) &=\operatorname{Re}\left(\sum_{i} h_{i} \cdot r_{i} \cdot \bar{t}_{i}\right) \\ &=\sum_{i} \operatorname{Re}\left(r_{i} \cdot h_{i} \cdot \bar{t}_{i}\right) \\ &=\sum_{i} r_{i} \cdot \operatorname{Re}\left(h_{i} \cdot \bar{t}\right)=\sum_{i} r_{i} \cdot \operatorname{Re}\left(\bar{h}_{i} \cdot t_{i}\right)=\sum_{i} \operatorname{Re}\left(r_{i} \cdot \bar{h}_{i} \cdot t_{i}\right) \\ &=f_{r}(t, h) \end{aligned} \end{aligned}

  • r2=argmaxrRe(<h,r,t>)\mathbf{r}_{2}=\underset{\mathbf{r}}{\operatorname{argmax}} \operatorname{Re}(<\mathbf{h}, \mathbf{r}, \overline{\mathbf{t}}>),
    r1=argmaxrRe(<t,r,h>)\mathbf{r}_{1}=\underset{\mathbf{r}}{\operatorname{argmax}} \operatorname{Re}(<\mathbf{t}, \mathbf{r}, \overline{\mathbf{h}}>)를 통해
    r1=r2ˉr_1 = \bar{r_2}Inverse 관계를 정의할 수 있다.

정리

References

0개의 댓글