🙌

10

10. Heterogeneous Graphs and Knowledge Graph Embeddings

Heterogeneous Graph란, 노드와 엣지가 여러 종류로 이루어진 것을 의미한다.

따라서 위처럼 각 node, edge, node type, relation type으로 이루어진다.

10.1 Relational GCN

GCN은 위처럼 표현할 수 있었다. W(weight)를 곱해주어 message로 transform하고, aggregate한다. GCN에서는 각 layer마다 W가 존재하고, 각 레이어의 노드들은 같은 W matrix를 사용한다.

하지만 각 edge가 여러 종류의 relation을 갖게 된다면? message transformation 도 각 realtion의 종류에 따라 달라져야 할 것이다.

각 layer마다, relation type마다 다른 Weight를 필요로하기 때문에, parameter수가 매우 커지고 (relation 종류만큼 배로 늘어남), overfitting issue가 생긴다.

해결방법으로는 (1) Use block diagonal matrices, (2) Basis / Dictionary learning 이 있 다.

(1) Use block diagonal matrices

Weight matrix의 parameter를 줄이기 위해 weight matrix의 일부 값을 0으로 바꾸어서 sparse하게 바꾼다는 아이디어이다. 하지만 해당 Weight matrix에 hidden state vector를 곱한다고 생각해보자. 1,2 는 3,4 에 해당하는 hidden state 정보를 가져오지 못한다. 1,2노 드와 3,4 노드가 다른 클러스터에 있는 구조가 아닌 이상 정보 유실의 한계점이 존재한다.

(2) Basis learning

relation 들이 wegith를 sharing(공유)하도록 하는 것이다. relation들이 basis matrix를 공 유하고, 이의 선형결합을 weight matrix로 한다.

[111]은 [1,0,1]+[0,1,0] 꼴로 나타낼 수 있다. 따라서 [1,1,1]은 선형의존이

위와 같이 행렬곱은 열벡터의 선형결합으로 나타 낼 수 있다.

다. basis는 선형독립인 벡터들을 의 미한다.

Relational GCN for link prediction

8강 recap

link prediction을 하기 위해, original graph가 있으면, 주황색(supervision edge)는 예측하 고자하는 엣지이다. 이를 예측하도록 gnn을 학습시키겠다는 것. 따라서 학습할 때,

message edge만 input graph로 넣는다.

Inductive link prediction split

8장에서 언급했듯이, 학습을 위해 그래프를 training set, validation set, test set으로 나눈 다. Inductive link prediction이란, 어느 그래프를 input으로 넣어도 link prediction을 수행 하도록 한다는 의미로, 각 training, val, test set이 독립적인 그래프가 쓰인다. 각 set은 message edge와 supervision edge를 가진다.

Transductive link prediction split

Transductive link prediction은, 특정 그래프에서만 사용 가능한 모델임을 의미한다. 따라 서 한 그래프를 train, val, test set으로 나누어 사용한다.

1) Training : training set의 message edge로 모델 학습, training supervision edge 예측 2) Validation : 1번에서의 edge로 validation edge 예측

3) Test : 2번에서의 edge로 test edge 예측

→ 점점 누적해가며 검증하는 모습을 보임.

Relational Graph, link prediction split

Relational GCN에서는, 그래프의 relation type이 다양하므로, 그래프를 나눌 때, 각 relation별로 edge를 training message, training supervision, validation, test 로 나눈다.

그리고나서 합친다. (개별적으로 4type으로 나누고, 다시 합쳐서 사용) Training (1)

점선으로 표시된 (E, r_3, A)가 training supervision edge이고, 나머지는 training

message edge라고 가정하면, 지금 예측하고자 하는 건 점선에 해당하는 edge의 relation type.

RGCN을 통해 해당 edge score를 구한다.

우선 각 노드 E,A의 final layer를 통해 node hidden state vector를 구하고, 두 hidden state를 transform 하고 product하여 두 노드 사이에 edge의 relation type이 r_3일 확률을 구한다.

Training (2)

앞에서, training supervision edge의 score를 RGCN을 통해 구했고, 두번째로 negative edge를 생성한다.

이 때 negative edge는 training message edge, supervision edge에 속하지 않아야한다.

예를 들면 (E,r3,B) , (E,r3,D)와 같은 edge. Head는 같고 tail은 다르며, 기존에 있지 않은 edge를 지칭한다.

Training (3)

3번째로, negative edge의 score도 구한다.

4번째로, 위의 loss function을 최소화 한다. training supervision edge는 score가 최대가 되도록 하고, negative edge는 score가 최소가 되도록 한다.

Evaluation (Validation, Test time)

8강에서 언급했듯이, validation 과정에서는 training message와 supervision edge를 input으로 하고, 모델에서 validation edge를 예측하며 검증한다.

1,2) 그래서 validation edge는 (E, r3, D)이고, training 과정처럼 (E, r3, D)의 score를 구 하고 → 가능한 모든 negative edge를 생성하고 이의 score를 구했다.

3) 이렇게 1,2번에서는 E→B, E→F, E→D 의 score를 구했다. 이 3개의 score을 줄세워서 랭킹을 구한다. 이 중에서 (E,D)의 등수를 구한다.

4) (E,D)의 relation이 r3이 맞다면, negative들의 score보다 높아야 할 것이다. 그래서 이를 평가하는 기준은 (1) Hits@k : 예측한 score 중 정답이었을 때, Top K 안에 몇번 들었나. 자 주 들었을수록 좋다고 평가한다. (2) Reciprocal Rank : 1/(예측한 positive edge의 rank) 가 클수록 좋다고 평가한다.

10.2 Knowledge Graphs : KG completion with Embeddings

각 node는 entity를 가리키며, entity type이 라벨링되어있다. edge는 relationship을 나타 낸다.

이러한 knowledge graph 의 특징은, 노드와 엣지가 굉장히 많은 그래프가 주를 이루며, 여 기서 true edge가 누락되는 경우가 많다는 것이다.

10.3 KG Completion : TransE, TransR, DistMul, ComplEx

예시

Knowledge Graph는 relation 이 누락된 경우가 많다. KG Completion은 이러한 누락을 추 가해주는 것이다. 예를 들면 지금 head : JK롤링, missing relation이 장르일 때, tail은 Science Fiction을 향해야 할 것.

여기서의 아이디어는, 엔티티(노드)와 relation(edge)를 임베딩하고, (head, relation)의 임 베딩이 tail의 임베딩과 유사하게 만드는 것을 목표로 한다. 이 때 '유사함'을 정의하기 위한 방법은 여러가지가 있는데, 그 중 한가지 방법인 transE에 대해 설명한다. transR,DistMul 등 여러가지 방법을 소개해주는데 너무 많다....11강에서는 transE를 중심으로 설명이 나온

TransE

relation 은 몇가지 패턴이 있다.

(1) 대칭, (2) 반대(inverse), (3) transitive , (4) 일대다

transE 이해할 때, 여기서 각 임베딩을 단순 shallew encoding으로 가정하기 때문에, 한 벡 터공간에서 head 벡터, relation 벡터, tail 벡터의 덧셈 뺄셈을 한다고 생각하면된다.

TransE 는 위 중 (1)대칭관계와 (4)일대다 관계를 나타내지 못한다.

h+r = t 일 때, t+r =h 인 것이 대칭관계인데, r이 영벡터일 때만 만족된다.

h+r = t1, t2, t3 .. 도 불가능한 것이, 벡터연산이 하나의 벡터로 대응되기 때문이다. 나머지 는 표현 가능함.

symmetric relation 일 때는, h와 t가 Mr을 통해 relation space로 임베딩될 때, 같은 곳에 매핑되면 된다.

1toN Relation 일 때, 여러 t들이 같은 곳에 매핑되면 됨. relation space에서 h와 t들의 관계 가 하나의 r로 표현되면 됨.