본 문서에서는 데이터 마이닝 분야 학회인 KDD 2021에서 발표 예정인 논문 "Learning to Walk across Time for Interpretable Temporal Knowledge Graph Completion"을 소개합니다. 논문의 상세한 정보는 아래와 같습니다.
- Title: Learning to Walk across Time for Interpretable Temporal Knowledge Graph Completion
- Authors: Jaehun Jung, Jinhong Jung and U Kang
- Conference: The 27th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2021
Temporal Knowledge Graph Completion
통상적인 지식 그래프(knowledge graph)는 현실 세계의 다양한 개체들을 정점(node)로, 개체들 사이의 관계를 간선(edge)로 표현하는 그래프를 일컫습니다. 이들 지식 그래프는 요컨대 (Joe Biden, is_president_of, United States) 등과 같이 다양한 개체들에 대한 관계적 지식을 트리플(triple)로 표현할 수 있어 추천 시스템, 지식 기반 AI 등 여러 분야에서 활용됩니다.
다만, 기존의 지식 그래프는 개체들 사이의 관계를 실제 시간적인 유효성과 관계없이 영속적인 것으로 간주하기 때문에 현실의 지식을 온전히 표현하기 어렵다는 한계가 있습니다. 이러한 단점을 보완해 근래 새로 등장한 지식 저장 형태가 시간 지식 그래프(temporal knowledge graph)입니다. 시간 지식 그래프는 개체들 간의 관계에 더해 그 관계가 유효한 시점을 추가한 쿼드러플(quadruple)을 표현함으로써 일시적으로만 유효한 사실도 나타낼 수 있습니다.
그러나 시간 지식 그래프 상에 수많은 지식을 수작업으로 기입하는 것은 비현실적이기에, 기존의 시간 지식 그래프를 바탕으로 모델이 새로운 지식을 추론토록 하는 시간 지식 그래프 완성(temporal knowledge graph completion) 태스크가 등장하였습니다. 모델은 시점, 개체 하나와 관계로 구성된 쿼리를 입력으로 받아, 기존 지식 그래프를 바탕으로 쿼리 완성에 적합한 개체 하나를 출력하게 됩니다.
Limitations of Existing Methods
시간 지식 그래프 완성을 목표로 한 선행 연구들은 주로 기존 지식 그래프 임베딩(knowledge graph embedding)에 시간 차원을 넣어 확장하는 방식을 취했습니다. 임베딩 방식의 접근법은 훈련이 수월하고 차원 확장에 유연하다는 장점이 있지만, (1) 그래프 상의 지식을 독립적으로 학습하기 때문에 각 개체의 맥락젹 표현(contextual representation)을 만들기 어려우며, (2) 모델이 어떤 기존 지식을 바탕으로 추론을 하였는지 해석하기 힘들다는 한계가 존재합니다.
본 연구에서는 (1) 시간 지식 그래프를 위한 그래프 뉴럴 네트워크(graph neural network)를 새롭게 제안해 각 개체의 표현을 맥락화하였으며, (2) 임베딩 기반 추론 방식을 경로 기반 추론(path-based inference)으로 대체해 상기한 한계들을 해결하고자 하였습니다.
Proposed Method
본 연구에서 제안한 모델 T-GAP의 핵심 아이디어는 다음과 같습니다.
- 쿼리-지식 시간 편차를 이용한 그래프 뉴럴 네트워크
지식 그래프 상의 개체 표현을 맥락화하기 위한 그래프 뉴럴 네트워크는
선행 연구에서도 제안되어 왔습니다. 그러나 이들은 시간 정보를 반영하지
않는 정적 지식 그래프(static knowledge graph)를 대상으로 하고 있어,
시점에 따라 달라지는 기존 지식의 중요성을 반영할 수 없었습니다.
T-GAP에서는 지식의 시간에 따른 중요성을 반영하기 위해, 쿼리 시점(즉
우리가 현재 관심 있는 입력값의 시점)과 인코딩되는 각 지식 시점 사이의
편차에 대한 임베딩을 학습합니다. 또한 이 편차 임베딩을 그래프 뉴럴
네트워크에서 전파되는 메시지에 포함, 개체 표현에 편차 정보가 반영되도록
하였습니다.
지식 그래프 상의 개체 표현을 맥락화하기 위한 그래프 뉴럴 네트워크는 선행 연구에서도 제안되어 왔습니다. 그러나 이들은 시간 정보를 반영하지 않는 정적 지식 그래프(static knowledge graph)를 대상으로 하고 있어, 시점에 따라 달라지는 기존 지식의 중요성을 반영할 수 없었습니다. T-GAP에서는 지식의 시간에 따른 중요성을 반영하기 위해, 쿼리 시점(즉 우리가 현재 관심 있는 입력값의 시점)과 인코딩되는 각 지식 시점 사이의 편차에 대한 임베딩을 학습합니다. 또한 이 편차 임베딩을 그래프 뉴럴 네트워크에서 전파되는 메시지에 포함, 개체 표현에 편차 정보가 반영되도록 하였습니다.
- 사전 그래프 뉴럴네트워크 (Preliminary graph neural network)와 서브 그래프 뉴럴 네트워크 (Subgraph graph neural network)에 의한 듀얼 인코딩
지식 그래프에는 만 단위를 넘어서는 수많은 지식들이 간선으로 존재하기
때문에, 이들 모두를 여러 층의 그래프 뉴럴 네트워크를 이용해 인코딩하는
것은 비효율적입니다. 더욱이 각 쿼리를 응답할 때 필요한 기존 지식은 전체
지식 그래프의 일부에 지나지 않기 때문에, 쿼리와 관련성이 높은 기존
지식만을 추출해 인코딩하는 작업이 필요합니다. 따라서 T-GAP에서는 (얕은
층으로 구성된) 사전 그래프 뉴럴 네트워크, PGNN으로 전체 지식 그래프를
인코딩 한 뒤, 쿼리와 관련 있는 서브 그래프만을 추출해 (깊은 층으로
구성된) 서브 그래프 뉴럴 네트워크 SGNN으로 인코딩하는 듀얼 인코딩 방식을
취하였습니다.
-
어텐션 전파 (Attention Propagation)에 의한 경로 기반 추론
경로 기반 추론 방식은 임베딩 기반 방법에 비해 모델의 추론 과정을 더 잘 해석할 수 있게 해주며, 디코딩 과정에서 그래프의 구조를 더 잘 이용할 수 있다는 강점이 있습니다. 그러나 그래프 상에서의 경로 탐색은 필연적으로 현재 이동할 수 있는 정점 중 하나를 샘플링하는 이산적인 계산을 포함하며, 이는 모델 전체의 종단간 학습 (End-to-End learning)을 방해하는 요소로 작용합니다. T-GAP에서는 경로 기반 추론을 수행하면서도 종단간 학습을 효율적으로 진행하기 위해 어텐션 전파의 개념을 도입하였습니다. 모델은 쿼리 내 개체에서 출발해, 현재 진행할 수 있는 이웃 정점 중 하나를 선택하는 대신 모든 이웃 정점에 연속적인 어텐션 값을 전파하게 됩니다. 사전에 정한 여러 번의 전파 스텝이 끝난 후, 최종적인 정답 개체는 가장 높은 어텐션 값을 가지는 정점으로 추론하게 됩니다. 어텐션 전파는 연속적인 계산만을 포함하므로 종단간 학습을 가능케하며, 모델 추론이 끝난 후 어텐션 분포를 분석함으로써 모델의 해석 가능성(interpretability)을 높일 수 있습니다.
Experimental Results
요컨대 사람이 (Entity, award_won, ?, 2021)이라는 쿼리에 응답한다고 가정해보겠습니다. 직관적으로 사람은 해당 개체가 2021년, 혹은 그 보다 약간 과거인 2020년 등에 어떤 성취를 달성하였는지 확인하고, 이를 바탕으로 어떤 상을 수상하였는지 추론할 것입니다. 왼쪽 차트에서 확인 가능하듯, T-GAP 또한 쿼리와의 시간 편차가 0이나 -1인, 즉 2021년 혹은 2020년에 발생한 해당 개체와 관련된 사건에 주목하였습니다. 또한 (Entity, educated_at_since, ?, 2018)라는 쿼리에 응답하기 위해 가장 핵심적인 단서는 이 개체가 2018년 이후 어떤 학교를 졸업하였는지 보는 것입니다. 마찬가지로 어텐션 분포를 분석해보면, 오른쪽 차트에서 나타나듯 모델이 쿼리 시점보다 1년~3년 뒤의 사건에 주목하는 것을 볼 수 있습니다. 이처럼 T-GAP의 추론을 통해 나타난 어텐션 분포를 확인함으로써 모델이 어떤 기존 지식을 활용해 응답을 생성하였는지 검증할 수 있으며, 그 추론 과정이 사람의 사고 과정과도 합치함을 확인하였습니다.
Conclusion