Chapter 4. Multi-relational Data and Knowledge Graphs
Graph Representation Learning Book 읽고 정리하기 시리즈 중 여섯 번째 이야기. 부디 완주하게 기도해주세요 !
노드와 노드 사이의 관계가 여러 개인 그래프를 multi-relational 그래프라고 한다. 즉, Multi-relational 그래프 $\mathcal{G}=(\mathcal{V}, \mathcal{E}, \mathcal{R})$의 하나의 엣지는 튜플 $(u, \tau, v) \in \mathcal{V}\times\mathcal{R}\times\mathcal{V}$로 정의되며 노드 $u$와 노드 $v$가 관계 $\tau$에 대해 연결되어 있다는 것을 의미한다. Multi-relational 그래프를 knowledge graph라고 부르기도 한다. 이번 챕터에서는 Multi-relational 그래프 안의 노드를 임베딩하는 방법에 대해 알아본다.
4.1 Reconstructing Multi-relational Data
하나의 관계만 다루는 그래프에서 노드 임베딩을 하는 방법은 챕터 $3$에서 자세하게 다뤄보았다. 노드 임베딩에 필요한 요소가 세 가지 있었다. 바로 디코더, 손실 함수, 그리고 유사도 행렬이다. 디코더는 두 노드 $u, v$의 임베딩 벡터 $\mathbf{z}_u, \mathbf{z}_v\in\mathbb{R}^d$를 입력 받아서 두 노드 사이의 그래프 통계량을 출력해주는 함수였다. 해당 그래프 통계량은 두 노드 사이의 유사도 $\mathbf{S}[u, v]$이었다. 그리고 디코더의 출력값과 실제 유사도 사이의 손실을 최소화해주는 임베딩 벡터를 찾는 것이 우리의 목표였다.
한편 Multi-relational 그래프에서는 관계의 종류까지 반영해서 노드들을 임베딩시켜야 할 것이다. 따라서 이 경우 디코더는 두 노드의 임베딩 벡터와 관계의 종류까지 입력 받아서 해당 관계에 대한 유사도를 출력해준다. 즉, $\text{DEC}:\mathbb{R}^d\times\mathcal{R}\times\mathbb{R}^d\rightarrow \mathbb{R}$인 함수이다. 가장 간단한 노드 임베딩 방법인 RESCAL은 다음 디코더를 사용한다. \[\text{DEC}(\mathbf{z}_u,\tau,\mathbf{z}_v)=\mathbf{z}_u^\top\mathbf{R}_\tau\mathbf{z}_v, \quad \quad (4.1)\]
여기서 $\mathbf{R}_\tau \in \mathbb{R}^{d\times d}$는 관계 $\tau$에 대한 학습 가능한 가중치 행렬이다. 만약 유사도 행렬로 인접행렬로 사용하고, 손실 함수로 오차 제곱을 사용한다면 \[\begin{matrix} \mathcal{L}&=&\sum\limits_{u\in\mathcal{V}}\sum\limits_{v\in\mathcal{V}}\sum\limits_{\tau\in\mathcal{R}}\lVert\text{DEC}(\mathbf{z}_u,\tau,\mathbf{z}_v)-\mathcal{A}[u,\tau,v] \rVert^2& \quad \quad (4.2) \\ & = & \sum\limits_{u\in\mathcal{V}}\sum\limits_{v\in\mathcal{V}}\sum\limits_{\tau\in\mathcal{R}}\lVert \mathbf{z}_u^\top\mathbf{R}_\tau\mathbf{z}_v - \mathcal{A}[u,\tau,v] \rVert^2, & \quad \quad(4.3) \end{matrix}\]
여기서 $\mathcal{A}\in\mathbb{R}^{\mid \mathcal{V} \mid \times \mid \mathcal{R} \mid \times \mid \mathcal{V} \mid}$은 multi-relational 그래프에 대응하는 인접 텐서이다. 이번 챕터의 남은 부분에서는 multi-relational 그래프에서의 노드 임베딩을 위한 손실 함수와 디코더에 대해 알아볼 것이다. 유사도 텐서로는 인접 텐서를 사용할 것이다.
4.2 Loss Function
식 $(4.2)$에서 사용한 손실 함수에는 두 가지 문제점이 있다. 첫 번째 문제점은 계산 복잡도가 크다는 것이다. 세 겹으로 겹쳐져 있는 시그마를 보면 숨이 턱 막힌다. 시그마로 인한 덧셈 연산 횟수만 $\mathcal{O}(\mid \mathcal{V} \mid^2 \mid \mathcal{R} \mid)$가 될 것이다. 그리고 일반적으로 multi-relational 그래프는 희소 (sparse)하다. 즉, $\mid \mathcal{E} \mid « \mid \mathcal{V} \mid^2 \mid \mathcal{R} \mid$이다. 따라서 모든 $u\in \mathcal{V}, v \in \mathcal{V}, \tau \in \mathcal{R}$ 조합에 대해 손실을 계산하는 대신 $(u, \tau, v)\in \mathcal{E}$에 대해서만 손실을 계산하면 계산량이 훨씬 감소할 것이다. 하지만 후자의 경우 엣지가 있는 대상만 고려한다는 문제점이 있다. 이 경우 디코더가 항상 1만 출력한다면 손실이 0으로 최소가 될 것이다.
그래서 우리는 엣지 집합에 없는 일부 $(u_n, \tau, v_n)\notin \mathcal{E}$들도 손실 함수에 추가해줄 것이다. 이로 인해 디코더가 $(u_n, \tau, v_n)$에 대해서는 0을 출력해줄 수 있을 것이다. 참고로 엣지가 있는 $(u, \tau, v)\in\mathcal{E}$는 레이블이 1인 데이터 역할을 하기 때문에 positive sample으로 볼 수 있다. 반대로 엣지가 없는 $(u_n, \tau, v_n)\notin \mathcal{E}$은 레이블이 0인 negative sample로 볼 수 있다.
식 $(4.2)$의 두 번째 문제점은 인접 텐서 $\mathcal{A}$가 0 또는 1 값만 갖기 때문에 제곱 오차 $\lVert \cdot \rVert^2$의 선택이 적절하지 않다는 점이다. 분류 문제로 접근하여 크로스 엔트로피 손실 함수를 사용하는 것이 더 적절할 것이다. 식 $(4.2)$의 문제점을 해결할 수 있는 한 가지 손실 함수는 네거티브 샘플링을 이용한 크로스 엔트로피 손실함수이다.
Cross-entropy with negative sampling
네거티브 샘플링을 이용한 크로스 엔트로피 손실함수는 다음과 같다. \[\mathcal{L}=\sum\limits_{(u,\tau,v)\in\mathcal{E}}-\log(\sigma(\text{DEC}(\mathbf{z}_u,\tau,\mathbf{z}_v)))-\gamma\mathbb{E}_{v_n\sim P_{n, u}(\mathcal{V})}[\log(\sigma(-\text{DEC}(\mathbf{z}_u, \tau, \mathbf{z}_{v_n}))], (4.4)\]
여기서 $\sigma$는 시그모이드 함수이고 $P_{n,u}(\mathcal{V})$은 노드 $u$에 대한 네거티브 샘플링 분포이다. $(u, \tau, v_n)\notin \mathcal{E}$인 $v_n \in \mathcal{V}$를 뽑아서 negative sample을 만들어주는 역할을 한다. $\gamma>0$은 네거티브 샘플링에 대한 중요도를 결정하는 하이퍼파라미터이다. 식 $(4.4)$의 첫 번째 항인 \[\log(\sigma(\text{DEC}(\mathbf{z}_u,\tau,\mathbf{z}_v))) \quad \quad (4.5)\]
는 실제 엣지가 있는 $(u, \tau, v)$에 대해서 디코더가 $(u, \tau, v)\in\mathcal{E}$일 것이라고 예측한 확률값에 로그를 씌운 것이다. 따라서 $\text{DEC}(\mathbf{z}_u, \tau, \mathbf{z}_v)\approx1$으로 예측할 수록 손실 함수가 감소할 것이다. 한편, 두 번째 항인 \[\mathbb{E}_{v_n\sim P_{n, u}(\mathcal{V})}[\log(\sigma(-\text{DEC}(\mathbf{z}_u, \tau, \mathbf{z}_{v_n})))] \quad \quad(4.6)\]
은 실제 엣지가 없는 $(u, \tau, v_n)$에 대해서 디코더가 $(u, \tau, v_n)\notin \mathcal{E}$일 것이라고 예측한 확률에 로그를 취한 것의 기댓값이다. 따라서 $\text{DEC}(\mathbf{z}_u, \tau, \mathbf{z}_{v_n}) \approx 0$으로 예측할 수록 손실 함수가 감소할 것이다. 식 $(4.6)$의 기댓값은 단순하게 Monte Carlo 방법을 써서 근사시킨다. 즉, 실제로 $v_n$을 몇 개 샘플링하여 표본 평균을 구한다. \[\mathcal{L}=\sum\limits_{(u,\tau,v)\in\mathcal{E}}\left(-\log(\sigma(\text{DEC}(\mathbf{z}_u,\tau,\mathbf{z}_v)))-\sum_{v_n\in P_{n, u}}[\log(\sigma(-\text{DEC}(\mathbf{z}_u, \tau, \mathbf{z}_{v_n}))]\right), (4.7)\]
한편, 네거티브 샘플링 분포 $P_{n, u}(\mathcal{V})$는 사용자가 정의하기 나름이다. 가장 단순한 방법은 노드 집합 $\mathcal{V}$에서 균등한 확률로 $v_n$을 뽑을 수 있을 것이다. 하지만 이 경우 $(u, \tau, v_n)\in\mathcal{E}$인 $v_n$이 샘플링될 수 있다는 단점이 있다. 따라서 $P_{n, u}(\mathcal{V})$를 어떻게 정의하느냐가 노드 임베딩 결과에 큰 영향을 미칠 수도 있다. 그리고 식 $(4.7)$은 노드 $u$에 대해서 엣지가 없는 $v_n$을 뽑는 방식이다. 하지만 엣지의 방향이 중요한 문제의 경우 이러한 방법이 편향이 생길 수도 있다고 한다. 따라서 실전에서는 노드 $u$에 대해서 양쪽 방향 엣지 $(v_n, \tau, u),(u,\tau,v_n)$을 모두 고려하는 방법이 더 좋은 결과를 만든다고 한다.
Max-margin loss
Coming soon!
참고문헌
[1] https://pixabay.com/ko/illustrations/지구-회로망-3537401/
[2] Hamilton, William L.,Graph Representation Learning, Synthesis Lectures on Artificial Intelligence and Machine Learning, 14, pp.1-159
