2021. 5. 12. 18:46ㆍNeural Networks/Graph
이번에 리뷰할 논문은 Knowledge Graph Convolutional Network입니다.
Knowledge graph는 일반적인 graph와 달리 node 또는 vertex를 연결하는 edge가 단순한 수치로 표현하기 어려운 관계를 갖는 high-order graph를 의미합니다.
논문은 Knowledge graph에 기반하여 recommendation system을 구성할 때 사용할 수 있는 방법을 제안합니다.
논문은 간단한 graph의 사전 지식을 요구합니다.
하지만 machine learning에 관심이 있으신 분들이라면 크게 무리 없이 읽으실 수 있을 것 같습니다.
논문 정리를 위해 논문으로부터 그림 및 알고리즘을 스크랩합니다.
논문에 대한 오역, 의역등이 다수 포함되어 있습니다.
댓글로 많은 의견 부탁드립니다.
Author : Hongwei Wang, Miao Zhao, Xing Xie, Wenjie Li, Minyi Guo
Proceedings of the 2019 World Wide Web Conference
hwwang55/KGCN
A tensorflow implementation of Knowledge Graph Convolutional Networks - hwwang55/KGCN
github.com
1. Introduction
기존의 recommendation system을 위한 방법으로 collaborative filtering (CF)이 자주 사용되었습니다. CF는 유저와 item (또는 entity) 간의 상호작용을 matrix로 표현한 adjacency matrix를 활용하여 구현한 방법입니다. 이 방법은 꽤 오래되었지만 효과적이기 때문에 자주 사용되고 있습니다. 하지만 몇가지 문제를 갖고 있으며 아래와 같습니다.
- 유저 $\mathcal{u}$와 item $\mathcal{e}$의 상호관계를 0 또는 1로 모두 표현한 adjacency matrix $A^{\mathcal{u} \times \mathcal{e}}$가 필요합니다. 따라서 메모리를 매우 많이 소모합니다.
- 만들어진 $A$는 sparse matrix이며, 임의의 유저가 item과 상호작용이 적은 경우 예측을 할 수 없는 cold start 문제가 발생합니다.
위 문제와 별개로 실제 온라인 플랫폼에 누적되는 데이터들은 유저의 숫자에 비해 item의 숫자가 압도적으로 많습니다. 또한 item 간의 관계(relation $r$)는 단순하게 scalar로 표현하기 어렵습니다. Knowledge graph (KG)는 relation들을 효과적으로 표현할 수 있는 graph입니다.
위 그림은 KG 예제를 잘 보여줍니다. 모나리자라는 그림이 누구에게 그려졌는지, 어디에 위치하고 있는지, 어떤 사람이 선호하는지 복잡한 관계의 edge를 통해 표현됩니다. 또한 화가와 장소, 인물 또한 다양한 relation을 통해 연결됩니다. 문제는 위와 같은 그림으로 표현가능한 KG를 어떻게 수치화하는가 입니다.
Item을 포함하는 entity $e$와 relation $r$을 가장 간단하게 표현한다면 adjaceny matrix $A$의 element마다 relation을 one hot encoding하여 binary vector로 표현할 수 있습니다. 위 그림은 뉴욕이 미국에 위치한다는 관계를 $\{0,1\} \in \mathbb{R}^{e \times e \times r}$의 tensor로 표현하고 있습니다. 하지만 이것은 adjacency matrix의 sparsity를 더욱 강조하며, 모델의 학습을 어렵게 합니다(curse of dimensionality). 따라서 일반적으로 relation을 embedding하여 사용하며 효과적인 embedding을 위한 연구들이 진행중입니다.
저자는 KG를 사용하여 유저와 item의 상호작용을 학습하고 새로운 item을 추천할 수 있는 recommendation system을 제안합니다. 제안하는 방법에는 user와 item간의 관계뿐만 아니라 item들이 포함된 entity들을 탐사하여 의미를 추론하고 학습에 사용합니다. 논문이 기여하는 바는 1) receptive field를 활용한 graph convolutional network (GCN)를 end-to-end로 학습하여 KG를 탐사하고, 유저가 관심을 갖는 high order relation을 찾아낼 수 있으며 2) 실제 데이터들에 적용했을 때 제일 좋은 성능을 보였고 3) 사용가능한 code를 github로 공유한다는 것입니다.
2. KGCN
KGCN은 $M$명의 유저 $u$와 $N$개의 item $v$간의 상호작용을 기록한 matrix $Y\in \mathbb{R}^{M \times N}$을 사용합니다. Matrix $Y$의 element $y_{uv}$는 상호작용이 존재하는 경우 1, 없는 경우 0을 갖는 sparse matrix입니다. 그리고 knowledge graph $G$는 item들을 포함하는 entities $e$와 relation $r$을 entity-relation-entity $(h,r,t)$로 표현합니다. $h,r,t$는 각각 head, relation, tail이라는 knowledge triple을 의미합니다. 또한 $ (h,t) \in \mathcal{E} , r \in \mathcal{R}$이며 각각 entities와 relation의 집합을 의미합니다. 놓치기 쉬운 점은 item들이 entities에 속하기 때문에 $v \in \mathcal{E}$라는 부분입니다.
KGCN은 모델 $\mathcal{F}$의 parameter $\boldsymbol{\Theta}$와 $Y,G$를 사용하여 임의의 유저 $u$와 item $v$간의 상호작용을 binary classification하도록 고안되었고 아래 식과 같이 쓸 수 있습니다.
$$\hat{y}_{uv}=\mathcal{F}( u,v | \boldsymbol{\Theta},Y,G)$$
목표를 달성하기 위해 KGCN의 layer를 먼저 살펴보겠습니다. $\mathcal{N}(v)$은 item $v$와 연결된 entities의 집합을 의미하고, $r_{e_i,e_j}$는 임의의 두 entity 간의 relation을 의미합니다. 또한 일반적으로 함수 $g: \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}$를 활용하여 user $u \in \mathbb{R}^d$와 relation $r \in \mathbb{R}^d$사이의 점수 $\pi^u_r$를 아래와 같이 계산한다고 합니다. $u$와 $r$의 계산을 위해 일반적으로 내적이 사용됩니다.
$$\pi^u_r = g(u,r)$$
이제 임의의 유저 $u$와 아이템 $v$간의 점수 $\mathbf{v}$를 계산해야 합니다. 임의의 아이템 $v$는 $\mathcal{N}(v)$에 속한 $e$들와 연관이 있기 때문에 다음과 같이 쓸 수 있습니다.
$$\tilde{\pi}^u_{r_{v,e}}=\frac{\exp{(\pi^u_{r_{v,e}})}}{\sum_{e \in \mathcal{N}(v)} \exp{(\pi^u_{r_{v,e}})}}$$
$$\mathbf{v}^u_{\mathcal{N}(v)}=\sum_{e \in \mathcal{N}(v)} \tilde{\pi}^u_{r_{v,e} }e$$
$\tilde{\pi}^u_{r_{v,e}}$는 유저와 관계의 점수 $\pi^u_r$들을 합이 1이 되도록 정규화 한 것입니다. 정규화된 점수를 사용하여 $u$와 아이템 $v$간의 점수 $\mathbf{v^u_{\mathcal{N}(v)}}$를 계산할 수 있게 되었습니다. 이어서 발생하는 문제는 $\mathcal{N}(e)$입니다. 실제 KG에서 $\mathcal{N}(e)$의 크기는 일정하지 않습니다. $e$들은 고립되어 있을 수도 있고, 매우 많은 relation을 가질 수 있습니다. 따라서 $\mathcal{N}(v)$로부터 $S(v) \triangleq \{ e | e \sim \mathcal{N}(v) \}$이고 $|S(v)|=K$인 $K$개의 원소를 갖는 새로운 집합 $S(v)$를 표본 추출합니다. $S(v)$는 많은 $\mathcal{N}(v)$ 중 $K$를 표본추출했기 때문에 receptive filed처럼 작용하여 convolutional 연산을 수행하게 됩니다. 아래 그림은 $K=2$인 경우 KGCN이 어떻게 연산하는지 보여줍니다.
그림을 다시 한번 참고하면 user를 의미하는 파란색 노드로부터 초록색 entities를 선정했고, 초록색 entities 또한 다시한번 $K$개의 entities를 선정하게 됩니다. $h$는 layer의 갯수를 의미하는데 $h=1$인 경우 item과 user의 의미만으로 recommendation system을 만든 것입니다. 따라서 $h>1$인 경우 KG를 탐사하게 되는데 $K \neq 1$이라면 각 entities들로부터 의견을 수렴하여 상위 entity 또는 user에게 의견을 전달할 방법이 필요합니다. 논문은 의견을 모을 방법 $agg$로 $agg: \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}^d$를 만족할 수 있는 sum, concat, neighbor를 제안합니다.
$$ agg_{sum}=\sigma( \mathbf{W} \cdot (\mathbf{v}+\mathbf{v}^u_{S(v)}) + \mathbf{b} )$$
$$ agg_{concat}=\sigma( \mathbf{W} \cdot concat(\mathbf{v},\mathbf{v}^u_{S(v)}) + \mathbf{b} )$$
$$ agg_{neighbor}=\sigma( \mathbf{W} \cdot \mathbf{v}^u_{S(v)} + \mathbf{b} )$$
$\mathbf{W},\mathbf{b}$는 learnable parameter weight와 bias이고 $\sigma$는 ReLU와 같은 비선형 함수를 가리킵니다.
이제 KGCN은 KG를 탐사할 깊이 $H$와 추출할 이웃 갯수 $K$ 그리고 유저, entity 그리고 relation을 embedding할 hidden size $d$로 구성되는 것을 확인했습니다. KGCN의 알고리즘은 논문에 실린 아래 표로 정리합니다. $H$번째 entity로부터 유저-entity까지 의미를 추론해 오는 과정은 아래 그림처럼 표현합니다.
3. Conclusion
결과는 논문을 참고부탁드립니다. 실제 오픈데이터셋에서 가장 좋은 성능을 보였고 저도 논문으로부터 귀중한 아이디어들을 얻을 수 있었습니다. 저자는 또한 $S(v)$가 uniformly sampling되는 것을 넘어서서 중요한 몇몇 entity를 가중추출하는 방향도 제안합니다.
하지만 KGCN은 몇가지 한계를 보였습니다. 실제 실험했을 때와 마찬가지로 논문의 결과표는 K와 H가 큰 경우 오히려 성능이 감소하는 것을 확인할 수 있습니다. 이것은 knowledge graph 탐색이 의도대로 이뤄지지 않았음을 의미합니다. 어쩌면 벤치마크 데이터셋의 KG가 적절하지 않았을 수도 있고 알고리즘 자체가 의도와 다르게 작동했을 수 있습니다.
torch version을 사용하여 모델을 사용해봤습니다. 모델학습 자체는 시간이 많이 소요되지 않았기 때문에 저자의 말과 더불어 몇몇 부분들을 개선한다면 recommendation system에 유용한 방법 중 하나로 사용될 수 있을 것 같습니다.