Learning to Walk across Time for Interpretable Temporal Knowledge Graph Completion

본 문서에서는 데이터 마이닝 분야 학회인 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) 태스크가 등장하였습니다. 모델은 시점, 개체 하나와 관계로 구성된 쿼리를 입력으로 받아, 기존 지식 그래프를 바탕으로 쿼리 완성에 적합한 개체 하나를 출력하게 됩니다.

그림 1. 시간 지식 그래프 완성 태스크의 예시.

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에서는 지식의 시간에 따른 중요성을 반영하기 위해, 쿼리 시점(즉 우리가 현재 관심 있는 입력값의 시점)과 인코딩되는 각 지식 시점 사이의 편차에 대한 임베딩을 학습합니다. 또한 이 편차 임베딩을 그래프 뉴럴 네트워크에서 전파되는 메시지에 포함, 개체 표현에 편차 정보가 반영되도록 하였습니다.

  • 사전 그래프 뉴럴네트워크 (Preliminary graph neural network)와 서브 그래프 뉴럴 네트워크 (Subgraph graph neural network)에 의한 듀얼 인코딩

지식 그래프에는 만 단위를 넘어서는 수많은 지식들이 간선으로 존재하기 때문에, 이들 모두를 여러 층의 그래프 뉴럴 네트워크를 이용해 인코딩하는 것은 비효율적입니다. 더욱이 각 쿼리를 응답할 때 필요한 기존 지식은 전체 지식 그래프의 일부에 지나지 않기 때문에, 쿼리와 관련성이 높은 기존 지식만을 추출해 인코딩하는 작업이 필요합니다. 따라서 T-GAP에서는 (얕은 층으로 구성된) 사전 그래프 뉴럴 네트워크, PGNN으로 전체 지식 그래프를 인코딩 한 뒤, 쿼리와 관련 있는 서브 그래프만을 추출해 (깊은 층으로 구성된) 서브 그래프 뉴럴 네트워크 SGNN으로 인코딩하는 듀얼 인코딩 방식을 취하였습니다.

  • 어텐션 전파 (Attention Propagation)에 의한 경로 기반 추론

경로 기반 추론 방식은 임베딩 기반 방법에 비해 모델의 추론 과정을 더 잘 해석할 수 있게 해주며, 디코딩 과정에서 그래프의 구조를 더 잘 이용할 수 있다는 강점이 있습니다. 그러나 그래프 상에서의 경로 탐색은 필연적으로 현재 이동할 수 있는 정점 중 하나를 샘플링하는 이산적인 계산을 포함하며, 이는 모델 전체의 종단간 학습 (End-to-End learning)을 방해하는 요소로 작용합니다. T-GAP에서는 경로 기반 추론을 수행하면서도 종단간 학습을 효율적으로 진행하기 위해 어텐션 전파의 개념을 도입하였습니다. 모델은 쿼리 내 개체에서 출발해, 현재 진행할 수 있는 이웃 정점 중 하나를 선택하는 대신 모든 이웃 정점에 연속적인 어텐션 값을 전파하게 됩니다. 사전에 정한 여러 번의 전파 스텝이 끝난 후, 최종적인 정답 개체는 가장 높은 어텐션 값을 가지는 정점으로 추론하게 됩니다. 어텐션 전파는 연속적인 계산만을 포함하므로 종단간 학습을 가능케하며, 모델 추론이 끝난 후 어텐션 분포를 분석함으로써 모델의 해석 가능성(interpretability)을 높일 수 있습니다.

상기한 세 아이디어를 종합한 최종적인 모델 구조는 아래 그림과 같습니다.
그림 2. T-GAP의 개괄 구조

1. Preliminary GNN
사전 지식 그래프 뉴럴 네트워크는 전체 지식 그래프를 입력으로 받아, 쿼리-지식 시간 편차를 이용해 개체의 맥락적 표현을 만들어 냅니다.

2. Subgraph GNN
서브 그래프 뉴럴 네트워크는 현재 들어온 입력 쿼리에 관련된 서브 그래프가 추출된 이후, 이 서브 그래프 상의 개체 표현을 만들어 냅니다. 또한 서브 그래프 상의 개체 표현이 쿼리 벡터를 반영하도록 만드는 추가적인 과정(Query Context Fusion)을 거칩니다.

3. Attention Flow
상기한 어텐션 전파가 이루어지는 과정입니다. 이 모듈에서는 두 그래프 뉴럴 네트워크를 통해 나온 개체들의 표현을 이용, 각 개체에서 어텐션 값을 전파할 전이 확률 (transition probability)을 계산합니다. 최종 전파 과정이 끝난 후 어텐션 값이 가장 높은 정점이 정답 개체가 됩니다.

4. Subgraph Sampling
서브그래프 뉴럴 네트워크가 작동하기 위해서는 먼저 쿼리와 관련 있는 지식으로만 구성된 서브 그래프가 있어야 합니다. 이를 위해 본 단계에서는 이전 스텝에서 전파된 어텐션 분포를 이용, 가장 어텐션 값이 많이 전파된 정점과 간선들을 샘플링하는 방식으로 서브 그래프를 추출하게 됩니다. 자세한 과정 및 예시는 논문을 참조해주시기 바랍니다.

Experimental Results

그림 3. T-GAP 및 임베딩 기반 모델의 벤치마크 성능 비교


시간 지식 그래프 완성 태스크의 대표적인 3개 벤치마크에서 실험을 수행한 결과, 선행 연구들에서 제안한 지식 그래프 임베딩 방법론들에 비해 약 10% 가량의 성능 향상이 나타났습니다. 특히 성능 지표들마다 순위가 조금씩 다른 기존 임베딩 모델들과 달리, T-GAP은 Mean Reciprocal Rank 및 Hits@1, 3, 10에서 일관되게 성능 격차를 보이는 것을 확인할 수 있습니다.


그림 4. 시간적인 일반화 성능 비교

또한 각 모델이 얼마나 시간적인 일반화(temporal generalization)을 잘 수행하는지 확인하기 위해, 기존 시간 지식 그래프에 한번도 등장하지 않은 시간에 대한 쿼리를 입력으로 주어 성능을 측정하는 추가 실험을 진행하였습니다. 그림 4에서 확인할 수 있듯, T-GAP은 절대적인 시점(timestamp)의 임베딩이 아닌 쿼리-지식 간의 시간 편차를 학습함으로써 기타 모델에 비해 더 잘 일반화하는 것을 확인할 수 있습니다.


그림 5. 쿼리 관계에 따른 시간 편차에 대한 어텐션 분포

더불어 T-GAP의 제안 배경에 모델의 해석 가능성 향상이 있는만큼, 모델의 추론 과정을 얼마나 잘 이해할 수 있는지 볼 수 있는 케이스 스터디를 진행하였습니다. 위 표는 서로 다른 관계를 가지는 쿼리가 입력으로 들어왔을 때, 모델이 어떤 시점의 지식에 더 어텐션 값을 많이 전파하였는지 분포를 나타낸 것입니다.
요컨대 사람이 (Entity, award_won, ?, 2021)이라는 쿼리에 응답한다고 가정해보겠습니다. 직관적으로 사람은 해당 개체가 2021년, 혹은 그 보다 약간 과거인 2020년 등에 어떤 성취를 달성하였는지 확인하고, 이를 바탕으로 어떤 상을 수상하였는지 추론할 것입니다. 왼쪽 차트에서 확인 가능하듯, T-GAP 또한 쿼리와의 시간 편차가 0이나 -1인, 즉 2021년 혹은 2020년에 발생한 해당 개체와 관련된 사건에 주목하였습니다. 또한 (Entity, educated_at_since, ?, 2018)라는 쿼리에 응답하기 위해 가장 핵심적인 단서는 이 개체가 2018년 이후 어떤 학교를 졸업하였는지 보는 것입니다. 마찬가지로 어텐션 분포를 분석해보면, 오른쪽 차트에서 나타나듯 모델이 쿼리 시점보다 1년~3년 뒤의 사건에 주목하는 것을 볼 수 있습니다. 이처럼 T-GAP의 추론을 통해 나타난 어텐션 분포를 확인함으로써 모델이 어떤 기존 지식을 활용해 응답을 생성하였는지 검증할 수 있으며, 그 추론 과정이 사람의 사고 과정과도 합치함을 확인하였습니다.

Conclusion

본 문서에서는 KDD 2021에서 발표 예정인 논문 “Learning to Walk across Time for Interpretable Temporal Knowledge Graph Completion”을 소개하였습니다. 해당 연구에서는 시간 지식 그래프를 자동으로 완성하기 위한 모델 T-GAP을 제안하였으며, 이를 통해 기존 지식 그래프 임베딩의 한계로 지적되었던 개체 표현 맥락화 및 모델 해석 가능성 증대에 기여하였습니다. 실제로 제안된 방법론이 선행 연구의 모델들에 비해 일관되게 높은 벤치마크 성능을 보였으며, 더 높은 시간적인 일반화 성능 및 해석 가능성을 가짐을 여러 실험을 통해 확인하였습니다. 나아가 시간-지식 그래프와 관련된 제안된 여러 기법은 비단 지식 그래프 완성 태스크 뿐 아니라 시간 정보에 기반한 지식 베이스를 활용하는 여러 분야에 확장될 수 있을 것으로 기대됩니다. 논문에 대한 상세 정보는 링크를 통해 확인할 수 있습니다.