[논문리뷰]End-to-end Structure-Aware Convolutional Networks for Knowledge Base Completion

Shang, C. (2018, November 11). End-to-end Structure-Aware Convolutional Networks for Knowledge Base Completion. arXiv present: 1811.04441
Paper

Problem Statement

Knowledge Graph는 현 시점에서 많은 수의 엔티티(Entity, Node)와 릴레이션(Relation, Edge)를 가지고 있다. 또한 그 정보 역시 다양한 Heterogeneous Graph이다. 하지만 기존의 존재하던 Knowledge Base Model들은 모두 Large-Graph에 부적합하다. Graph Embedding모델중에서는 PinSage 모델을 제외하고는 기존 모델들은 모두 Large Scale Graph에 부적합하다. 따라서 새로운 Graph Embedding 모델의 필요하다.

1. Knowledge Graph는 이미 수백만의 Triple을 포함한다.
   • 실제 데이터가 계속해서 추가되기 때문에 그 수가 기하급수적으로 늘어난다.
   • 따라서 KG Completion Task를 푸는 것이 점점 더 중요해진다.
     
2. 기존의 임베딩 모델들은 Large Scale Graph에 부적합하며, ConvE역시 마찬가지이다.
   • ConvE는 Triple의 임베딩 연산이 TransE와는 다르게 translation property가 존재하지 않는다.
   • TransE의 임베딩 연산은 \(e_s + e_r = e_o\)이다. 즉, Subject(head)와 relation의 임베딩의 합이 Object(tail)임베딩과 같다.
   • ConvE는 임베딩 공간에서 KG의 연결성을 설명하는데 부적합하다.

Relation Work

• Knowledge Graph Embedding
• TransE, TransR, TransD, TransH
• DistMult, ComplEx
• convKB, convE
• GCN

Method

1. Overview

모델의 아키텍쳐는 크게 두 부분으로 나누어지며, Encoder-Decoder 모델이다. Encoder는 WGCN으로 기존의 GCN에 Weight(가중치)를 추가하여 수정한 구조이다. 그리고 디코더는 SACN이라고 불리며 이는 Structure-Aware Convolution Network이다.

이 모델의 전체적인 구조를 단 한 줄로 설명하자면 ConvE의 prediction performance에 TransE의 Translation Property를 병합시킨 모델이다.

2. Encoder: WGCN

1) GCN vs WGCN

Encoder는 GCN모델의 성능을 향상시켜만든 모델이다. Weighted GCN의 약자이며, 이름 그대로 가중치에 대한 정보를 GCN에 추가한 것이다. 그림을 보면 빨간색 노드가 중심노드가 된다. GCN은 Graph Embedding 모델의 한 종류이다. 즉, 하나의 노드를 기준으로 이웃 노드들의 대한 정보를 Aggregation한다.

마찬가지로 WGCN도 이웃 노드들의 정보를 Aggregation한다. 기존의 GCN과 다른점은 WGCN은 중심 노드를 기준으로 이웃 정보를 취합할 때 Relation Type마다 이웃 노드들에 가중치(Weight)를 부여한다. 이로서 어떤 이웃노드들이 중심노드에 더욱 더 큰 영향력을 행사하는지 파악할 수 있다. 가중치는 Learning parameter이다.

그림에서 예시를 들면, 빨간색 노드가 중심노드이고, 중심 노드에대해 이웃들의 relation은 총 3가지 종류가 있으며 각각이 Blue, Green, Orange 노드로 표현되어 있다.

WGCN (Weighted Graph Convolutional Network) determines how much weight to assign to each subgraph 
when combining the GCN (Graph Convolutional Network) embeddings for a node. This approach enhances 
the learning capabilities of the model by emphasizing important subgraphs and their relationships 
within the network, ultimately improving the overall performance in tasks such as node classification, 
link prediction, or graph clustering.

2) Mechanism of WGCN

WGCN은 여거래의 Layer가 쌓여져있는 형태이다. 먼저 하나의 노드에서 Aggregation되는 과정을 살펴보면, \(l^{th}\) 레이어의 입력은 이전 레이어에서 나온 크기가 \(F^l\)인 벡터가 된다. 그렇게 들어온 입력이 WGCN을 거치면 \(F^{l+1}\) 번째의 성분이 입력 벡터에 추가된다. 다시 말해, 레이어를 하나씩 거칠때마다 출력 벡터의 성분 개수가 하나씩 늘어난다.

\(v_i\)노드에 대한 임베딩을 수식으로 나타내면 다음과 같다. \(\alpha_t^l\)은 새롭게 추가된 parameter인 가중치(weight) 이다. \(t\)는 edge type의 개수로 총 \(T\)개가 있다. GCN과 마찬가지로 기본적인 Operation은 1)Weighted Sum을 하고 2)Nonlinearity를 먹이는 모양이다. 식의 의미를 해석하자면, \(i\)노드를 중심으로 모든 이웃 노드의 정보를 가중치를 부여해 취합하고, Nonlinearity를 먹여 신경망의 표현 능력을 향상시킬 수 있는 출력값을 만들어 내는것이다.

이 식을 보면 한 가지 문제점이 발생한다. 바로 중심 노드가 이웃 노드들의 정보만 취합하고, 자기 자신에 대한 정보를 취합하지 못했다는 것이다. 따라서, 중심 노드의 정보를 담을 수 있는 term을 추가해 줘야 하고 이를 Self-Loop라고 한다.

최종적으로 위의 식처럼 이웃 노드들의 정보를 가진 term과 \(v_i\)자신에 대한 정보를 가진 term으로 표현된다. \(A_t\)는 노드들의 연결 정보가 담겨져 있는 인접행렬(Adjacency matrix)이다. 이때, Self-Loop에 대한 정보까지 담아 둔 행렬을 \(A_l\)라 하고, 정리하면 오른쪽 위의 식처럼된다. 이를 \(h_i^l\)에 대입해서 정리한 후, 하나의 노드에 대해서가 아닌 레이어 전체 연산으로 바꾸어 행렬식으로 나타내면 최종 임베딩 식이 나온다. 수식을 다시 한 번 정리하면 다음과 같다.

이를 좀 더 직관적으로 이해하기 위해서 행렬식으로 정리하는 과정을 그림으로 나타내면 다음과 같다. \(N \times N\) 의 크기를 가지는 Self-loop가 포함된 인접행렬에 크기가 \(N \times F^l\)인 \(H^l\)을 곱하고 거기에 크기가 \(F^l \times F^{l+1}\)인 \(W^l\)을 곱하고 각 요소마다 Nonlinearity를 먹이면 인코더의 최종 임베딩인 \(H^{l+1}\)이 나온다.

3) Node Attribute

Knowledge Graph에서 노드들은 종종 (\(entity(subject), relation, attribute(object)\))형태 여러 속성과 연결된다. 예를 들어, (s = Tom, r = people.person.gender, o = male) 이다. 이를 해석하면, 'Subject인 Tom과 Object인 male은 성별이라는 관계가 있다.'로 해석할 수 있다.

만약에 Node Attribute가 Node 정보를 나타내는 Vector Representation가 같으면 2가지 문제가 발생한다. 먼저 각 노드의 Node Attribute의 수 일반적으로 매우 적으며, 각 노드마다 다르다는 것이다. 이러한 이유로 Attribute Vector는 매우 Sparse하다.

두번째로 Attribute Vector에서 성분이 0이면 그 의미가 매우 모호해진다는 것이다. 예를 들어 그 값이 0일 경우 노드가 구체적인 Attribute가 없는것이거나 또는 attribute에 대한 값을 노드가 유실한 것 둘 모두로 해석될 수 있다.

이 논문에서는 Knowledge Graph의 node attribute가 다른 node set으로 표현되고 그걸 ‘attribute node’라고 표현한다. Attribute nodes는 연관된 엔티티들과 연결을 해주는 일종의 다리(bridge) 역할을 한다.

Because these attributes exhibit in triplets, we represent the attributes 
similarly to the representation of the entity o in relation triplets. Note 
that each type of attribute corresponds to a node.

왜냐하면 이 attribute들이 triple로 표현되며, triple에 관련하여 object의 표현과 유사한 속성을 나타낸다. 예를 들어, ‘male’과 ‘female’은 두 개의 노드가 아닌 단일 노드로 표시된다. 이러한 방식으로 WGCN은 그래프의 Connectivity structure를 이용할 뿐만 아니라 note attribute를 효과적으로 사용한다. 이렇기 때문에 WGCN이 Structure-Aware Convolution network라고 불리는 것이다.

3. Decoder: Conv-TransE

1) Model Concept

디코더는 Conv-TransE라는 아키텍쳐를 사용한다. 이 모델은 기존에 존재하던 Graph Embedding 모델인 ConvE에 기반해서 만들어졌다. 거기에 TransE모델의 장점인 Translation Property를 가져와 사용하는 모델이다. 즉, Conv-TransE는 ConvE모델의 장점과 TransE모델의 장점을 모두 취한 새로운 아키텍쳐라고 할 수 있다. ConvE모델과 다른 점은 트리플을 임베딩해서 나온 임베딩 벡터 \(e_s\)와 \(e_r\)을 stacking한 후에 reshape을 할 필요가 없다는 것이다.

디코더는 총 두 개의 입력을 받는다. 첫 번째 입력은 WGCN의 결과로 나운 임베딩 행렬(Embedding Matrix)이다. 임베딩 행렬의 크기는 각각의 노드가 \(F^l\) 차원의 임베딩을 가지고 총 N개의 노드가 있는 것이므로 \(\mathbb{R}^{N \times F^L}\)이다. 두 번째 입력은 릴레이션 임베딩 행렬(Relation Embedding Matrix)이다. Mini-batch stochastic train algorithm을 사용하기 때문에 릴레이션 임베딩 행렬도 학습된다.

디코더의 첫 번째 단계는 미니 배치에 있는 Triplet들의 \(e_s\)와 \(e_r\)을 찾기위해 임베딩 행렬을 참조하는 Look-up 연산을 수행한다. 더 정확하게는 서로 다른 \(C\)개의 커널(Kernel)이 있고, \(c\) 번째 커널은 \(w_c\)로 파라미터(Parameterized)로 정의된다고하면 다음의 위의 식을 따른다. \(K\)는 커널의 폭이고, \(n\)은 출력 벡터의 항목을 인뎅싱한다.

• \(K\) = Kernel Width. 논문에서는 \(2 \times k\)의 Kernel size를 정의하고, \(k\)는 1,3,5 세 가지로 실험을 진행했다.
• \(n\) = Indexing the entries of output vector, \(n \in [0, F^L - 1]\) 이다.
• \(w_c\)는 학습 가능하다.
• \(\hat{e_s}\)과 \(\hat{e_r}\)은 임베딩에 패딩(Padding)을 한 것이다.

여기서 패딩(Padding)을 하는 이유는 Convolution 프로세스 전체에서 입력 데이터의 공간 차원(Spatial Dimensions)을 보존하는 것을 목표로 한다. 패딩은 입력 데이터의 가장자리 주변에 추가적인 픽셀(Pixel) 또는 Data Point를 추가하느데 사용되는 방법으로 종종 출력이 입력과 동일한 크기를 갖도록 하게 만든다. 이 논문에서 패딩 방식은 컨볼루션 연산에 사용되는 커널을 구체적으로 다룬다. 커널의 첫 번째와 마지막 구성 요소에 0을 추가함으로써 커널 자체에 일종의 패딩을 효과적으로 적용한다. 이 패딩은 컨볼루션 연산에 필요 이상으로 입력 데이터의 공간 차원을 왜곡하거나 축소하지 않도록 도움이 되며, 이는 데이터 구조를 유지하는데 중요하다.

예시를 들어 살펴보면 위와 같다. 다시 한 번 강조하면, 패딩은 컨볼루션 연산에서 입력 데이터의 공간 차원(Spatial Dimensions)을 유지하고 데이터의 원래 구조를 더 잘 보존하는데 유용하다. 이러한 이유로 Convolutional Operation은 결론적으로 \(e_s,e_r\) 임베딩의 Translation Property을 보존한다. 최종적으로 SACN 디코더는 출력의 벡터의 형태로 만드어내고 이를 수식으로 나타내면 \(M_c(e_s,e_r) = [m_c(e_s,e_r,0), \cdots,m_c(e_s,e_r,F^L -1) ]\)이다. 모든 커널의 컨볼루션 결과로 나온 출력 벡터를 정렬하면 최종적으로 \(\bf{M_c} (e_s, e_r) \in \mathbb{R}^{C \times F_L}\)가 출력된다.

마지막으로, KG Completion을 풀기위해 Scoring function을 정의해준다. Scoring function은 \(\psi(e_s, e_r) = f(vec(\bf{M}(e_s, e_r))W)e_o\)로 정의한다. \(W\)는 크기가 \(\vert CF^L \times F^L \vert\)인 Linear Transform을 위한 행렬이고, \(f\)는 Non-Linear Function이다. \(vec(\bf{M})\)을 통해 행렬이 Vectorization되어 크기가 \(\vert 1 \times CF^L \vert\)인 벡터로 바뀌고 \(W\)와 곱해주면 최종적으로 크기가 \(\vert F^L \vert\)인 벡터가 나온다. 이 값이 Object의 임베딩인 \(e_o\)와 내적(Dot-Product)를 함으로써 최종적으로 Scalar값이 나온다. 추가적으로 학습 중 Scoring을 위해 Logistic sigmoid function을 적용했다.

Scoring function을 계산하는 과정을 요약하면 위와 같다. SACN 모델을 요약하자면, Knowledge Graph의 노드 연결성(node Connectivity)와 노드와 릴레이션의 어트리뷰트(Node attribute, relation attribute)의 장점을 이용하는 모델이라고 할 수 있다.

전체 모델의 메커니즘을 요약하자면 WGCN에서 학습가능한 Weight들은 이웃 노드들의 정보를 모을때 Type별로 영향력을 달리하여 정보를 모을 수 있고 엔티티의 특성이 네트워크에 추가적인 Attribute node로 추가되며 WGCN에서 쉽게 통합된다. Conv-TransE는 엔티티와 릴레이션간의 translation property를 유지해 노드 임베딩을 학습하고 Link prediction에 적용한다.

Experiment & Result

1. Dataset

실험에서 사용한 Data Set은 총 3가지이다. Knowledge Graph Completion에서 많이 사용되는 Freebase와 WorldNet이고, FB15k-237-Attr는 FB15k-237에서 attribute node를 추가하여 만든 Dataset이다. 총 4가지

2. Experiments

1) Link Prediction

• ConvE-TransE만을 이용해 학습을 시킨 결과가 기존의 Graph Embedding모델들에 비해 성능이 좋음.
• SACN에 Attribute Node가 추가된 dataset으로 학습한 결과 성능이 가장 좋게 나옴
• 높은 성능 향상을 보여줌

2) Convergence Analysis

• Convergence Analysis는 어떤 모델이 가장 빠르게 Converging되는지 확인하는 실험
• SACN에 Attribute Node가 추가된 dataset으로 학습한 것이 가장 빠르게 Converging됨.
• 즉, SACN은 성능도 좋으며 더 빠르게 수렴해 학습 시간도 단축됨.
  

3) Kernel Size Analysis

• Kernel Width를 조절하며 실험 진행. 즉, Kernel의 차원수를 조절하며 실험을 함
• Kernel의 크기가 대체적으로 커질 때 가장 좋은 성능을 보임
• SACN + Att 에서 \(2 \times 5\)의 커널 사이즈일때 성능이 가장 높음

4) Node Indegree Study

노드 Indegree를 기준으로 실험을 진행. Node를 기준으로 노드쪽으로 들어오는 edge의 깊이를 의미한다. 커질수록 더 멀리있는 노드까지 연결이 된 것이다. 기본적으로 Conv-TransE나 SACN모두 Indegree의 범위가 커질수록 성능이 좋아진다. 하지만, Indegree의 범위가 높을 때 SACN보다 Conv-TransE모델의 성능이 더 좋다는 결과를 나온다. Indegree가 높은 노드(A large number of incoming connections)에서는 이웃 간의 더 많은 정보가 취합되고 smooth된다. 이는 노드로 하여금 너무 많은 이웃 정보를 취합해 노드 표현이 오히려 희석되거나 지나치게 smoothing될 수 있음을 의미한다. 결과적으로 학습된 임베딩은 노드의 특정 특성이나 기능 중 일부를 잃어 정보가 없거나 정확하지 않게 될 수 있다.

반면 Conv-TransE는 KG에서 엔티티와 해당 속성 간의 관계를 학습하는데 중점을 둔다. 그래프의 구조를 보다 효과적으로 포착하여 특히 Indegree가 높은 노드의 경우 더 좋은 임베딩 representation으로 이어질 수 있다.

요약하면, SACN과 Conv-TransE의 학습 과정의 차이로 Indegree가 높은 노드의 경우 SACN의 임베딩 성능이 저하될 수 있다. 다시 말해, Indegree가 너무 높아지면 SACN에서는 GCN에서도 발생하는 문제인 Over-Smoothing이 발생하며 일부 특종 노드의 기능을 손실하게 만든다. 반면, Conv-TransE는 그래프 구조와 릴레이션을 더 잘 포착하여 더 정확한 임베딩 결과를 만들어 낸다.

Contribution

1. GCN에 Attribute node를 추가해 Attribute에 대한 추가적인 정보를 주어 성능을 향상시켰다.
2. ConvE모델을 개선해 좀 더 노드의 관계성에 집중할 수 있는 Conv-TransE모델을 제안했다.
3. ConvE모델을 기반으로 구성해 동일한 Translation Property를 사용한다.

GR 카테고리 내 다른 글 보러가기