[논문리뷰]Relational Message Passing for Knowledge Graph Completion

Wang, H. (2020, February 17). Relational Message Passing for Knowledge Graph Completion. arXiv.2002.06757
Relational Message Passing for Knowledge Graph Completion

Problem Statement

Incompleteness and noisy
Knowledge Graph는 head와 relation, tail로 이루어진 트리플(Triple, <\(h,r,t\)>)형태로 정보를 표현한다. Knowledge Graph는 보통의 Homogeneous Graph와는 다르게 엔티티(Entity, Node)나 릴레이션(Relation, Edge)이 여러 가지 타입을 가지는 Heterogeneous Graph이며 엔티티와 릴레이션의 수가 매우 많은 Large-Scale Graph이다. 이러한 일련의 이유로, 1)KG는 불완전(Incomplete)할 수 있으며 noisy할 수 있다. 이는 다시 말해서, 노드 또는 엔티티의 수가 많다 보니 그래프 전반적으로 missing link가 많고, 그에 따라 여러 hop을 거친 path information이 불완전하기에 정보가 noisy하다는 것이다.

Limitation of existing message passing models
두 번째로 2)기존의 존재하는 message passing 모델들은 한계점으로 Knowledge Graph에 부적합하다는 것이다. 그 모델들은 모두 Input을 Entity의 Embedding vector로 받아 이웃 노드들의 정보를 Aggregation하고 그 메세지 정보로 hidden state를 업데이트 시키는 방식으로 학습이 진행된다. 이럴 경우 노드 수가 많은 Knowledge Graph의 경우 Computational Complexity가 압도적으로 증가하기 때문이다.

따라서, Knowledge Graph에 적당한 Message Passing 방법을 적용시킨 모델이 ‘PathCon’이다.

Related Work

Relation Prediction
관련된 연구로는 Relation Prediction이 있다. Knowledge Graph Completion task는 쉽게 말하면 head나 tail을 찾는 엔티티 기반의 추론 문제이다. 비슷하게 Relation Prediction은 Triple에서 relation edge를 찾는 것을 목적으로 하는 추론 문제이다. 논문에서는 더 나아가, Relation Prediction을 확률 분포로 주어진 head와 tail에 대한 relation type의 분포를 모델링 하는 것이라고 정의한다.

Knowledge Graph Completion(KGC)
두번째로는 KGC이다. KGC는 위의 노란색 박스에서와 같이, head와 relation의 임베딩이 주어졌을 때 tail임베딩을 찾는 것이 목표이다. Link Prediction과 비슷하다.

Method

1. Notation

논문에서 나오는 Notation으로는 왼쪽의 표와 같다. 트리플은 <\(h,r,t\)>로 정의된다. \(s^i\)는 Hidden state 임베딩을 의미한다. 이 노테이션을 바탕으로 Relation Prediction의 내용을 보충하자면, Relation Prediction을 다음과 같이 베이즈 정리(Bayes’ Theorem)로 나타내면 다음과 같다.

Relation Prediction은 앞서 말했듯, 헤드와 테일이 주어졌을 때 릴레이션을 찾는 것이다. 그리고 이는 릴레이션의 유형(Relation Type)에 의한 분포를 모델링하는 것과 같다. 따라서 Posterior의 경우 조건 그대로 <\(h,t\)> 가 주어졌을 때 릴레이션을 찾는 것이므로 조건부 확률(Conditional Probability)의 조건 부에 \(h,t\)가 들어간다. 하지만 , Posterior의 경우 직접적으로 모델링하기 힘들다.

따라서 베이즈 정리를 이용해 Likelihood와 Prior의 곱과 비례한다는 식으로 바꿔 모델링이 가능하다. Likelihood의 경우 조건식과 구하려던 확률식의 위치가 바뀌게 되고 이는 \(p(h,t \vert r)\)으로 표기한다. 이 Likelihood(우도)가 의미하는 것은 특정 가설이나 모델이 참인 경우 특정 데이터 또는 증거 집합을 관찰할 확률을 나타낸다. Likelihood의 의미를 좀 더 쉽게 설명하자면 결국 릴레이션 r에 관한 다른 서브 루프가 없는가를 측정해 확률로서 나타낸 것이다.

마지막으로 Prior는 일종의 사전 지식으로 여기서는 \(h(r)\)로 표현된다. 이 때, prior의 수식은 간단하게 전체 릴레이션의 수에 대한 특정 Relation Type의 출현 확률이다. 따라서 (1)식으로 정의된다.

이를 (2)번식과 같이 Decomposition할 수 있다. Decompostion을 함으로써 직접적으로 구해야하는 확률의 무엇인지 정해진다. PathCon모델에서는 엔티티의 정보(Entitiy’s Identity)를 고려하지 않고, 엔티티의 Local Relational Subgraph만을 고려한다. 다시 말해서 엔티티의 Local Relational Subgraph를 \(C(\cdot)\)으로 표현했을 때 \(p\left(C(h) \vert r \right)\) 와 \(p\left(C(t) \vert r \right)\)로 정의된다.

이 그림을 보면, 진한 빨간색이 head와 tail로부터 1-hop만큼 떨어진 릴레이션의 정보를 모으는 것을 시각화 한 것이고, 옅은 빨간색은 2-hop만큼의 릴레이션 정보를 Aggregation하는 것을 시각화 한 것이다. 또한 초록색선이 바로 Relation Path가 된다. Relation Path는 head에서 tail로 릴레이션을 따라서 가는 path를 말한다. 이는 Shortest path일 수도 있고, 몇 hop까지 정보를 aggregation하느냐에 따라 달라질 수 있다.

2. Overview of Relational Context and Path

논문에서 제안한 PathCon 모델은 기존의 Relational message passing모델들과는 다르게 Context뿐만 아니라 Path에 대한 정보도 같이 이용해 훈련한다.

왼쪽그림은 Relation Context에 관한 그림이다. Harry potter라는 노드를 중심으로 tail이 Ron일지 Hadwig인지 추론하려고 할 때, 논문에서는 1-hop만큼 떨어진 이웃 노드의 정보 뿐만 아니라 Multi-hop 떨어진 릴레이션 타입까지 정보를 모으는 방식을 제안한다. 이러한 정보는 추론 과정에서 유요한 정보로 중요한 역할을 할 수 있다. 그림에서 조지 위즐리 노드와 론위즐리 노드는 형제관계로 정의된다. 이를 통해 론과 조지는 같이 산다라고 추측할 수 있다. 따라서, Lives with라는 릴레이션에 적합한 tail은 해드위그라고 추론하는 것이 합당하다.

오른쪽 그림은 Relation Path의 중요성을 보여준다. Relation Path는 head에서 tail로 가는 relation들의 조합이다. 예컨대 서로 다른 Path는 엔티티들의 서로 다른 관계 정보를 주고 이 정보가 많아질수록 추론하는데 도움이 된다. 그림은 해리포터가 head이고, 헤르미온느 그레인저와 드레이코 말포이중 tail이 무엇인지를 추측하는 문제이다. 이 때 실제로 연결되어 있는 Positive relation path를 보면 해리포터에서 Wizard로 가는 릴레이션인 Occupation과 Wizard에서 후보군으로 가는 릴레이션인 Occupation이 있다. 즉 후보 노드로 가는 두 Path모두 <Occupation, Occupation>으로 동일하다. 따라서 추론에서는 도움이 되지 않는 정보이다.

따라서 다른 Relation Path의 정보를 이용해야 한다. 그 예시가 바로 다른 Postivie relation Path인 <house, house>이다. 헤르미온느 그레인저와 <house, house> path를 따라가면 연결이 되므로 tail은 헤르미온느 그레인저라고 추론할 수 있다.

3. Pros of Relational Message Passing

기존의 방식인 Node-to-Node Message Passing 대신에 Relational Message Passing 방식을 사용하는 이유는 여러가지가 있다.

먼저 Inductive Learning이 가능하다. 추론 과정에서는 절대 나오지 않는 엔티티들을 사용해 학습에 이용하기 때문이다. 이는, 이웃 노드들 뿐만 아니라, Multi-hop에 대한 릴레이션의 정보를 받기 때문에 실제로는 여러 노드를 거쳐서 정보를 모으는 것이며, 이에 따른 Relation Path도 다양해져 실제로는 Shortest Path가 아닌 Path에 대해서도 정보를 모아오기 때문에 추론 과정에서는 보이지 않는 정보도 학습에 반영이된다. 따라서, 추론에서 나오는 정보 외에도 사용하므로 Inductive하다.

두번째 이유는 Storage-Efficient이다. 아무래도 KG에서 엔티티의 수가 Relation Type보다는 많기 때문에 기존의 node-to-node Message Passing 방식은 Computational Complexity가 매우 크다. 하지만, Relational Message Passing은 릴레이션에 의존하므로 엔티티 임베딩을 계산하지 않아 시간 복잡도도 감소하고 이에 따라 메모리 측면에서 저장 효율성도 좋다.

마지막으로 Explainable하다는 것이다. 추론한 결과를 Relational Path를 이용하여 쉽게 설명을 할 수 있다.

4. PathCon Model

노드를 이용한 기존의 Message Passing은 \(i\)번째 Layer의 노드의 임베딩 정보인 Hidden state 임베딩을 Aggregation 함수를 이용해 메세지 정보를 만든다. 이 만들어진 정보를 Hidden state 임베딩을 업데이트 함수를 통해 다음 Layer의 Hidden state 임베딩을 생성한다. 이 때 수식에서도 알 수 있듯 \(s_u^i\)이므로 노드 기반의 임베딩인 것을 알 수 있다. 노드 베이스 방식은 N개의 엔티티와 M의 릴레이션에 대해 Cost가 2M + 2N이 된다.

반면, Relational Message Passing은 Hidden state 임베딩이 \(s_{e^{'}}^i\)로 정의되며 릴레이션 기반의 임베딩 정보이다. 이 때 앞서 말했듯, Relational Message Passing은 릴레이션의 분포(Variance)에 대한 수식으로 정의되므로, 이 임베딩 정보도 분포에 대한 식이다. 하지만, 실제로 Knowledge Graph에서는 Long-tail때문에 매우 크므로 Cost가 훨씬 더 크게 나온다. 이럴 경우 Relational Message Passing방식이 적합한지 의문이 생기게 된다.

이런 이유로 논문에서는 이를 해결하기 위한 방식으로 alternative 방식을 제안했다. 이 방식은 쉽게 말해서 릴레이션의 aggregation을 나눠서 하는 것이다. 7번식에서 Hidden state의 정보를 취합한다. 7번식은 앞서 언급했던 Relational Message Passing의 특징인 Relation Path의 end-point인 head와 tail의 이웃 노드들로 뻗어나가는 릴레이션의 정보를 취합한다. 즉, 7번식은 Context 정보 취합한 정보이다.

Context 정보를 모았으면 이제 Relational Path정보를 모아야 한다. 이렇게 End Point에 대한 이웃 노드들의 릴레이션 정보를 모았으므로 이를 토대로 Path를 구성하여 Aggregation function을 통해 취합한다. 즉, Multi-hop의 릴레이션 정보를 기반으로 Path를 구성하고 그 정보를 취합한 것이 8번식이다. 마지막으로 이를 통해 업데이트 함수를 이용해 Hidden state를 업데이트한다.

중요한 사실은 노드는 분포의 중심 역할(End-Point)을 하는 것이고 메세지 정보를 임시로 저장하는 역할을 한다고 논문에서 언급한다. 이를 통해 알 수 있는 것은 Alternative Relational Message Passing의 특징인데 일반적인 Relational Message Passing과는 다른점을 말해준다. Alternative방식은 Edge ➜ Edge 로의 정보 전달이 아닌, Node ➜ Edge 로 정보를 보내는 Cross Passing방식이다. 이를 통해 Cost가 굉장히 완화되는 것을 볼 수 있다. 이 방식을 통해 모델을 Cross Context Aggregator라고 한다.

1) Relational Context 정의

Alternative Relational Message Passing의 전반적인 과정을 앞서 살펴보았고, 따라서 Context와 Path를 수학적으로 명확하게 정의해야 한다.

Konwledge Graph의 Triple에서 head와 tail은 대체적으로 매우 높은 연관성을 보인다. 에를 들어 릴레이션이 graduated from 일 때 head가 출생지와 성별에 관한 릴레이션으로 둘러싸여 있고, tail이 학교 위치, 창립자, 교장에 관한 릴레이션으로 둘러싸여 있다면, 쉽게 head와 tail의 관계성에 r이 들어갈 수 있다라고 추측할 수 있다.

이처럼 노드 v에 대한 메세지를 이웃 노드와 Multi-hop 정보를 모두 취합한 것으로 정의한다. 그 정의된 정보를 토대로 v노드에 대한 메세지 정보와 u노드에 대한 메세지 정보, Hidden State 임베딩을 Concatenation하고 이를 Weight와 곱한 후 bias를 더해준 후 Nonliearity를 먹인 것으로 정의한다.

2) Relational Path 정의

다음으로는 Relational Path를 수학적으로 정의해야한다. 다시 말해** \(p(t \vert h, r)\)와 \(p(h \vert r, t)\)를 어떻게 모델링을 할 것인지 수학적으로 정의**해야 한다. Alternative Relational Message Passing 방식은 엔티티의 Identity를 사용하지 않는다.

다시 아까와 같은 예시를 살펴볼 때, head와 tail의 관계가 graduated from의 릴레이션에 적합하다 추측하였고, 이를 통해 둘 중 하나는 사람, 하나는 학교일 것이다라고 추측할 수 있다. 이런 예시는 KG에서 종종 빈번하게 일어난다. 하지만, 실제로 사람과 학교는 아무 관계가 없고 KG안에서는 매우 거리가 멀 수 있다. 다시 말해 위의 예시는 false sampling이 된다. 이러한 false postive case가 발생하는 이유는 Relational Message Passing이 h와 t의 타입만을 발견하기 때문이다. 실제로는 이 둘의 직접적인 relative position을 찾아내지 못한다.

이 문제를 풀기위해서 Connectivity Pattern이라는 것을 도입한다. 이는 KG에서 Path Connecting을 표현한 것이다. 위와같이 Sequence 형태로 나열하고 이를 Path로 정의하면 아래식과 같이 정의된다. 실험적으로 4-hop이상에서만 직접적으로 control할 수 있고, 그 이후에는 계산이 기하급수적으로 커지므로 조절하기 힘들다.

3) Combining Context and Path(Update)

이제 Hidden State를 업데이트 해주기 위해 Context와 Path를 합쳐주는 Update를 정의해줘야 한다. Context에서 정의한 Hidden State 임베딩 식에 h와 tail을 동시에 넣어주어 \(s_{(h,t)}\)를 뽑아낸다. 중요한 것은 입력으로 두 end-point의 연결성을 나타내는 r이 없이 들어가고, 학습 과정에서 Ground Truth에 해당하는 릴레이션 r은 관찰되지 않는다.

Note here that Eq. (1) should only take messages of ℎ and 𝑡
as input without their connecting edge 𝑟, since the ground truth
relation 𝑟 should be treated unobserved in the training stage.

Relational Context를 정의했으므로, Relational Path를 정의해야 한다. Path는 최단 거리(Shortest Path)를 포함해 여러 개가 있을 것이고, 그 각각이 다른 Importance값을 가진다. 따라서 Attention Mechanism을 이용해 각각의 Path가 주는 영향력을 구해줘야 한다. 다시 말해 Path에 대한 어텐션을 정의 한 것이 \(\alpha_P\)이다. 여기서 \(s_P\)는 각각의 Path에 대한 독립적인 임베딩 벡터이다. (서로 다른 Path의 수는 hop수가 증가함에 따라 기하급수적으로 증가한다.) \(s_P\)는 Learnable Parameter이다.

Attention Weight를 Path에 대한 Hidden State에 곱해줘 \(s_{h \rightarrow t}\)로 표현되는데, 여기서 Attention Weight는 모든 Path의 Average representaion에 사용된다. 결국 \(s_{h \rightarrow t}\)는 모든 End-Point \((h,t)\)에 대한 모든 Relational path의 representation을 취합하는 것이다.

이제 Context representation \(s_{(h,t)}\)와 Path representation \(s_{h \rightarrow t}\)를 구했으니 Likelihood를 정의를 해줘야 한다. 이 Likelihood는 확률값으로 정의하므로 이 두 정보를 더해 Softmax를 취해주면 된다. 이 Likelihood를 Relation에 대한 Cross-Entropy로 정의해 Loss를 정하고 이를 minimization하면 된다.

이러한 Aggregation방식을 Relational Path Aggregator라고 한다.

4) Design Alternative

논문에서는 Relational Path Aggregator외에도 여러 가지 Aggregator를 소개한다.

Mean Context Aggregator
입력 벡터에 Elment-Wise Mean을 취해 정의한다.

Cross Context Aggregator
이 방식은 추천 시스템에서 Combinational feature방식에 영감을 받아 제안한 방식이다. 이 방식은 unit feature간의 상호 작용을 측정한다. Mean과 Concatenation aggregator는 간단하게 두 개읭 입력 노드를 각각 메세지를 변형하고 더하는 방식이다. 이러한 방식은 Link prediction에 도움을 줄 수 있는 입력간의 상호 작용을 측정하지 않는다. 반면 Cross Aggregator는 먼저 head와 tail로부터 나온 메세지간 모든 element-level pairwise interaction을 계산한다. 그리고 이러한 모든 정보를 flatten하고 더해주어 취합해준다.

Cross Context Aggregator는 입력 노드들의 순서를 모두 보존한다.

Learning Path Representation with RNN
Relational Path를 모델링할 때 RNN을 이용해 Relational Path \(P = (r_1,r_2, /cdots)\)를 이용해 학습한다. 즉, P 임베딩 벡터를 직접적으로 이용하는 것이 아니라 RNN을 거쳐서 학습시키는 것이다.

Path 임베딩과는 다르게 RNN방식의 장점은 파라미터 수가 고정되어 있고 path에 independent하다는 사실이다. 또한 서로 다른 Path의 유사성을 포착할수도 있다.

Mean Path Aggregator
\((h,t)\) 쌍에 대한 relational path의 마지막 representation을 계산할 때, Attention path aggregator대신 h에서 t로의 path의 prepresentation을 모두 간단하게 평균을 내는 것이다.

이 방식은 Relational Context가 사용불가능할 때 사용한다.

• 종류 요약
  1. Context Aggregator
     • Mean
     • Concat
     • Cross
  2. Path Aggregator
     • Mean
     • Attention
  3. Path Representation
     • 임베딩 벡터
     • RNN

Experiment & Result

1. Dataset

실험에서는 KG task의 벤치마크 데이터셋인 Freebase와 WordNet, NELL을 사용했고, DDB14의 경우 논문에서 Relation Prediction에 적합한 새로운 데이터 셋이다. 이를 통해 여러가지 그래프 임베딩 모델을 돌렸을때 총 계산된는 파라미터 양은 아래 표와 같다.

2. Result 1) Relation Prediction

Relation Prediction의 경우 전체적인 그래프 임베딩 모델들에비해 좋은 성능을 보여주었다.

3. Result 2-4) Inductive KG Completion / Different Hops / Different Context Aggregator

Inductive KG Completion
먼저 학습중에 얼마나 Inductive Learning이 가능한지를 실험한다. Test Set에 나타나는 노드의 Subset을 무작위로 랜덤하게 샘플링한 후, 이러한 노드를 Relation Edge와 함께 Training Set에서 제거한다. 머지 Training Set은 모델을 학습하는데 사용되며, Evaluation 중에 제거된 Edge들은 다시 추가한다. 제거된 노드의 비율이 0에서 1로 증가하면 Evaluation의 척도가 Fully Conductive에서 Fully Inductive로 넘어가는 것을 볼 수 있다.

Inductive Setting에서 PathCon모델의 성능은 아주 약간 감소(0.954 \(\rightarrow\) 0.952)하는 반면 RotatE와 DistMult의 경우는 무작위로 추측하는 것처럼 성능이 감소하는 것을 볼 수 있다. 이로써, PathCon은 Inductive하다.(Relational Message Passing의 장점) 이는 RotatE와 DistMult의 경우는 노드의 정보(node identity)에 기반한 임베딩 모델인 반면, PathCon의 경우는 노드의 ID를 고려하지 않기 때문에 Inductive KG Completion으로 자연스럽게 일반화 할 수 있다.

Different Hops & Length on WN18RR
이 실험은 End-Point(h,t)로부터 Hop수가 달라졌을때 Path길이에 따른 성능 차이를 보기위함이다. 먼저 최대 Hop수를 0에서 4까지 올려가면서 실험을 했고, 확실히 hop수가 높아질수록 더 많은 릴레이션 정보를 모으기 때문에 성능이 높아지는 것을 볼 수 있다. 또한, Path의 길이가 길어질수록 마찬가지로 성능이 더욱 더 좋아진다. 이를 통해 더 많은 이웃들을 거칠경우 성능이 좋아진다는 것이 증명된다.

하지만, 여기서 중요한 점이 있다. Hop수가 늘어나고, Path의 길이가 증가하는 것은 Computational Complexity와 Trade-off관계에 있다는 것이다. 따라서 5-hop이상 증가하면 효율성이 너무 떨어진다.

Different Context Aggregator
다음 실험은 Context Aggregator를 다르게 했을 때 성능을 비교했다. Mean Context Aggregator의 경우 모드 Dataset에서 성능이 가장 안좋게 나왔다. Concat와 Cross의 경우는 Dataset마다 결과가 상이하다. 상기해야할 점은, Cross의 경우 Concat보다 파라미터 수가 더 많다는 단점이 있고 이는 결론적으로 Training에 걸리는 시간과 메모리에 많은 자원을 소모하게 된다.

4. Result 5-6) Different Path Aggregator / Different Initial Features

Different Path Aggregator
Path Representation에는 두 종류가 있다. 임베딩 벡터를 이용하는 방식과 RNN을 이용하는 방식으로, 임베딩 벡터를 이용하는 방식이 WN18RR 데이터셋을 가지고 실험했을 때 더 좋은 결과를 보여주었다. 그 이유는 relational Path의 길이가 일반적으로 짧기 때문이다. 이로 인해, RNN의 경우 입력 시퀀스 길이가 짧기 때문에 제대로 성능을 발휘하지 못한다.

또한 Path Aggregator에는 Mean과 Attention방식이 있고 PathCon에서는 Attention방식을 사용한다. 또한 결과적으로 둘 중 Attention방식이 조금 더 성능이 좋은 것을 볼 수 있다.

Different Initial Features
이 실험은 Intial Edge feature를 Identity, BOW와 BERT 임베딩으로 했을 때 결과이다. 또한 Path모델만 사용했을 때, Con만 사용했을 때 그리고 둘을 모두 사용한 PathCon의 경우로 비교를 하였다. 결과적으로 PathCon이 제일 좋은 성능을 보였으며 세 모델에서 모두 릴레이션 타입의 BERT임베딩을 intial feature로 사용했을 때 가장 성능이 낮았다. 논문에서는 이 이유를 BERT 임베딩이 Relation Type간의 Semantic relationship을 더 잘 식별할 수 있기 때문이라고하며, PathCon의 Context/Path의 BERT 임베딩에서 예측된 관계 유형의 정체성에 대한 매핑을 배우는 것을 목표로 한다.

즉, 예측된 relation type이 BERT 임베딩으로도 표현되면 BERT가 더 나은 성능을 발휘하여 임베딩 공간 내에서 이 매핑을 할 수 있다.(Future Work)

Appendix

1. Proof of Theorem 1: Message Passing

Theorem 1

Proof 1. In each iteration of node-based message passing:
Aggreagation은 총 \(N\)번 수행되고, 각 aggregation 마다 \(\mathbb{E}[d] = \frac{2M}{N}\)의 Element들을 예상 입력으로 사용한다. \(\mathbb{E}[d]\)는 Node Degree이다. 따라서, 각 iteration에서의 aggregation의 Cost는 \(N \cdot \mathbb{E[d]} = 2M\)이 된다.

Update의 경우는 총 N번 수행되며, 각 업데이트는 Aggregation과 Update로 총 2단계로 모든 입력 Element들에 적용된다. 따라서 Total Update Cost는 \(2N\)이 된다.

Expected Cost of Node-based message passing $$: \; 2N + 2M$$

2. Proof of Theorem 2: Relational Message Passing

Theorem 2

Relational Message Passing의 Expected cost는 기존의 Message Passing과는 다르다. 이걸 증명하려면 Line Graph라는 개념을 이해해야 한다. 원래 Original Graph를 \(\mathcal{G}\)라하고, Line Graph를 \(L(\mathcal{G})\)라 할 때, Line Graph는 Original Graph의 node-edge 관계가 뒤바껴 있는 것이다. \(\mathcal{G}\)의 Node가 \(L(\mathcal{G})\)의 Edge로, \(\mathcal{G}\)의 Edge가 \(L(\mathcal{G})\)의 Node가 되는 것이다.

• Original Graph \(\mathcal{G}\)의 Node = Line Graph \(L(\mathcal{G})\)의 Edge
• Original Graph \(\mathcal{G}\)의 Edge = Line Graph \(L(\mathcal{G})\)의 Node

논문에서는 Original Graph보다 Line Graph가 더 크고(Larger) 밀도가 높다(Densor)는 것을 Lemma로서 증명하였다.

For relational message passing, it actually passes messages on the line graph of the original graph. 
The line graph of a given graph G, denoted by 𝐿(G), is a graph such that each node of 𝐿(G) represents 
an edge of G, and two nodes of 𝐿(G) are adjacent if and only if their corresponding edges share a common 
endpoint in G. We show by the following lemma that the line graph is much larger and denser than the 
original graph

LEMMA 1. Line graph \(L(\mathcal{G})\)의 노드 수가 M이고, Expected node degree는 다음과 같다.

$$\mathbb{E}_{L(\mathcal(G))} = \frac{N \cdot \mathsf{Var}_{\mathcal{G}}[d]}{M} + \frac{4M}{N} - 2$$

이 떄, \(\mathsf{Var_{\mathcal{G}}}[d]\)는 Original Graph \(\mathcal{G}\)의 Node degree의 분산(variance)이다. 명확한 것은 Theorem 2정의에 의해서 Original Graph는 N개의 Node와 M개의 Edge로 구성된다. 따라서, Line Graph는 M개의 Node와 N개의 Edge로 구성된다. 따라서 Node Degree의 Expectation값은 다음과 같이 변한다.

$$\mathbb{E}[d] = \frac{2M}{N} \; \; \rightarrow \; \; \mathbb{E}_{L(\mathcal(G))} = \frac{N \cdot \mathsf{Var}_{\mathcal{G}}[d]}{M} + \frac{4M}{N} - 2$$

Proof)
Line graph의 정의에 의하면, Line graph의 각 edge들은 같은 노드에 대해서 original graph의 unordered pair of edges들에 대응한다. 즉, Original graph의 순서가 없는 edge쌍들이 Line graph의 edge를 정의하는 것이다. 따라서, \(L(\mathcal{G})\)의 edge 수는 unordered pairs of edges의 수와 같다. 이를 수식으로 정의하면 다음과 같다.

$$edges \; in \; L(\mathcal{G}) = \displaystyle\sum_i \begin{pmatrix} d_i\\ 2 \\\end{pmatrix} = \displaystyle\sum_i \frac{d_i(d_i - 1)}{2} = \frac{1}{2} \displaystyle\sum_i d_i^2 - M$$

이를 이용하여 \(\mathbb{E_{L(\mathcal{G})}}\)를 구할 수 있고 그 과정은 위의 그림과 같이 정리된다.

Line Graph의 밀도가 더 높다.
LEMMA 1로부터 알 수 있는 것은 \(\mathbb{E_{L(\mathcal{G})}}\)가 적어도 \(\mathbb{E_G}\)보다 두 배 이상이다. 하지만, 실제로 real-world graph에서 Node degree는 매우 중요하며, Power Law Distribution(Scale Free Network: 대부분이 노드는 degree가 적고 소수만이 Long tail을 가진다.)따른다. 다시 말해 variance값이 Long-tail에 의해 매우 크다. 이것이 의미하는 것은 Expected node degree의 값이 orginal graph보다 line graph인 \(\mathbb{E_{L(\mathcal{G})}}\)이 실제로는 훨씬 크다는 사실이다. 반면에, Line graph의 노드 수인 M값은 Original graph의 노드 수인 N값보다 훨씬 크다. 따라서 Line Graph가 훨씬 Dense하다.

Proof) In each iteration of relational message passing:
Aggregation은 총 M번 진행된다. 그리고 각각의 aggregation은 \(\mathbb{E_{L(\mathcal{G})}}[d] = \frac{N \cdot \mathsf{Var_{\mathcal{G}}}[d]}{M} + \frac{4M}{N} - 2\) Element들을 예상 입력으로 한다. 따라서 \(M \cdot \mathbb{E_{L(\mathcal{G})}}[d] = N \cdot \mathsf{Var_{\mathcal{G}}}[d] + \frac{4M^2}{N} - 2M\)이 된다.

Update의 경우 마찬가지로 총 M번 진행된다. 그리고 각 업데이트시 총 2개의 Element들이 input으로 들어간다.(업데이트시 Context와 Path가 input이다.) 따라서, 업데이트의 각 epoch에서의 cost는 \(2M\)이다.

따라서 Relational Message Passing의 각 Epoch별 Expected Cost는 \(N \cdot \mathsf{Var_{\mathcal{G}}}[d] + \frac{4M^2}{N}\)이다.

3. Proof of Theorem 3: Alternative Relational Message Passing

Alternative Relational Message Passing은 총 2번의 aggregation과 1번의 업데이트 연산이 있다. 먼저 Edge-to-Node aggregation 연산 방식이다. 총 N번의 aggregation 이 각 epoch마다 진행되며 \(\mathbb{E}[d] = \frac{2M}{N}\) element들이 예상 입력으로 들어간다. 따라서 \(N \cdot \mathbb{E}[d] = 2M\)의 cost를 가진다.

또한 Node-to-Node aggreagation 연산 방식에서는 총 M번의 aggregation이 각 epoch마다 진행되며 총 2개의 입력(\(m_v^i, m_u^i\))이 들어간다. 따라서 \(2M\)의 cost를 가진다.

마지막으로 업데이트 연산이다. 업데이트는 총 M번 총 2개의 입력으로 각 epoch마다 연산이 이루어진다. 따라서 총 \(2M\)의 cost를 가진다. 따라서 Alternative Relational Message Passing의 epoch별 Total Cost는 \(6M\)이다.

Contribution

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