[Network Science]16.Knowledge Graphs

YongUk·2025년 2월 21일
GNNGraphnetwork science

Graph Theory

목록 보기
17/17

Knowledge Graph

  • 지식그래프는 여러 개체의 상호작용을 표현하는 그래프이다. 이때 각 노드와 각 edge들은 서로 다른 종류를 가질 수 있다.
  • 예를 들어 A라는 사람이 있고 1월1일 이라는 날짜가 있을 때 이 둘 사이에 생년월일이라는 edge로 연결할 수 있고 또 다른 Student라는 노드가 있으면 A노드와 이 노드를 직업이라는 edge로 연결할 수 있다. 이처럼 실제 세계의 여러 개체들과 그들 간의 관계를 표현한 그래프라고 생각하면 된다.

장점

  1. 기본적으로 검색엔진에서 쿼리에 기반하여 질의응답을 할 수 있다.
  2. 기존의 구조화되지않은 정보들을 구조화시켜 그래프로 표현하였기에 그래프 분석을 이용해 그 내부에 있는 인사이트를 도출할 수 있다.

단점

  1. 실제 텍스트에서 각 노드들의 관계를 모두 찾아내는 것을 어렵다.
  2. 또한 자동화 시스템을 이용해 찾아낼 경우 노이즈 및 잘못된 데이터를 가져올 가능성이 높다.

구성요소

  • 지식기반 그래프에서 각 쌍은 총 3가지의 구성요소를 가진다.
    1. Head : 어디에서 출발하는지
    2. Tail : 어디로 도착하는지
    3. Relation : Head가 Tail과 무슨 관계인지

Link Prediction

  • Head와 Relation이 주어졌을 때 Tail을 찾는 문제이다. 이전에 본 Link Prediction는 일반적으로 서로 다른 두 노드가 연결될지 되지 않을지이고 여기서는 조금 다르게 Relation이 주어지고 그 Relation이 어떤 노드를 가리키는 지를 찾는 문제이다
  • Knowledge Graph에서는 임베딩을 통해 임베딩 공간에서의 벡터를 이용하여 h,r이 주어졌을 때 t를 예측할 수 있다.

KG Embedding

  • 그래프로 표현되는 (h,r,t) triples를 특정 임베딩 공간 Rn\R^n에 매핑시키는 문제이다.
  • 이때 가장 중요한 것은 h+r=t , h′+r=t′h+r=t \ , \ h^{'} + r = t^{'} 을 만족시키는 방향으로 임베딩학습이 진행되야한다는 것이다. 즉 head와 tail에 관계없이 같은 특성인 경우 평행을 유지해야한다라는 것이다.

TransE

fr(h,t)=−∥h+r−t∥f_r(h,t) = - \|h+r-t\|
  • TransE에 따르면 실제 사실인 정보에 대해서는 h+r≈th+r \approx t를 만족해야하고 사실이 아닌 정보와는
    h+r≠th+r \ne t를 만족하도록 학습을 진행하여야한다. 따라서 scoring function은 다음과 같이 정의할 수 있다.
  • 이 규칙으로 학습을 시키게 된다면 위에서 Link Prediction에서 말한 것처럼 h,r만 주어졌을 때 h+r이 해당 지식의 t에 해당하는 노드로 향할 것을 기대할 수 있다.

Algorithm

  1. 각 Entity(E)들과 Relation(L)을 모두 Uniform(−6k,6k)Uniform\left(-\frac{6}{\sqrt{k}}, \frac{6}{\sqrt{k}}\right)을 이용하여 랜덤하게 초기화 시킨다. 이때 k는 dimention이다. 또한 초기화된 값들은 L∥L∥\frac{L}{\| L \|}을 이용하여 정규화 시켜준다.
  2. 각 step에서 positive sample과 negative sample을 각각 하나씩 샘플링하여 TbatchT_{batch}에 추가한다.
∑((h,l,t),(h′,l,t′))∈Tbatch∇[γ+d(h+l,t)−d(h′+l,t′)]+\sum_{((h,l,t),(h^\prime,l,t^\prime))\in T_{batch}}∇[γ+d(h+l,t)−d(h^\prime+l,t^\prime)]_+
  1. Positive Sample의 오차는 줄이고 Negative Sample의 오차는 늘리는 방향으로 학습을 진행한다.
  2. 이것을 반복한다.

Limits

  • 그래프 임베딩은 다양한 특성을 만족시켜야한다
  1. Symmetric : 양방향 edge일 경우 r(h,t)=r(t,h)r(h,t) = r(t,h)를 만족해야한다
    • h+r=t, t+r=hh+r = t , \ t+r=h를 만족시키기 위해서는 h=t,/r=0h = t , / r=0을 따라야하지만 불가능하다.
  2. Inverse Relations : r2(h,t)=r1(t,h)r_2(h,t) = r_1(t,h) 와 같이 역을 만족시킬 수 있어야한다.
    • r2=−r1r_2 = -r_1을 만족하면 된다.
  3. Composition : r1(x,y)∧r2(y,z)=r3(x,z)r_1(x,y) \wedge r_2(y,z) = r_3(x,z) 합성 관계를 만족시켜야한다.
    • 벡터의 성질을 이용하면 이를 만족하는 r1,r2,r3가 존재함을 알 수 있다.
  4. 1-N relations : r(h,t1),r(h,t2),...,r(h,tn)r(h,t_1), r(h,t_2) , ... ,r(h,t_n) 일대다 관계를 만족시켜야한다.
    • 이 모델에서 같은 (h,r)이 서로 다른 t를 가지는 것은 불가능하다.
  • TransE 모델의 경우 Symmetric과 1-N relations 특성을 만족하지 못한다.

DistMult

fr(h,t)=<h,r,t>=∑ihiritif_r(h,t) = \left< h,r,t \right> = \sum_ih_ir_it_i
  • DistMult모델에서는 거리기반의 scoring이 아닌 내적을 이용한 scoring function을 가진다.
  • 하지만 이 모델은 TransE의 단점을 보완한 모델이지만 반대로 TransE에서 만족하는 Inverse Relation과 Composition의 특성은 만족시키지 못한다.
profile
YongUk
이전 포스트

[Network Science]15.Cascades in Networks

0개의 댓글