논문 링크 : https://arxiv.org/abs/2006.10637
<Intorduction>
지금까지 GNN 모델은 주로 시간이 지나도 변하지 않는 정적 그래프 위주로 연구되어 왔습니다 . 그러나 소셜 네트워크, 금융 거래 및 추천 시스템을 포함한 많은 분야들의 실제 그래프는 동적이며 시간이 지남에 따라 변화합니다. 이러한 분야에서 정적 그래프만 고려하면 상당히 많은 정보가 손실될 수 있습니다.
동적 그래프는 노드 및 엣지의 추가 또는 삭제와 같은 시간에 따라 변하는 이벤트의 정렬된 목록 또는 비동기 "스트림"으로 나타낼 수 있습니다. 예를 들면,Twitter와 같은 소셜 네트워크는 사람이 새로 가입하면 새 노드가 생성되고, 다른 사용자를 팔로우하면 팔로우 엣지가 생성되며, 프로필을 변경하면 노드가 업데이트됩니다.
이러한 이벤트들은 그래프의 각 노드에 대해 시간 종속성 임베딩을 생성하는 인코더 신경망에 의해 생성됩니다. 그런 다음 임베딩은 특정 작업을 위해 설계된 디코더에 입력으로 들어갑니다. 이러한 시나리오 중 하나는, 시간 t 에서 노드 i 와 j 사이에 에지를 가질 확률을 계산하는 것입니다. 예를 들면, 소셜 네트워크 사용자에게 팔로우할 대상을 제안하거나 표시할 콘텐츠를 결정하는 추천 시스템등이 있습니다.
본 논문에서는 이러한 시간의 흐름에 따른 변화를 효과적으로 모델링 할 수 있는 Temporal Graph Network를 제안합니다. 이 모델은 이벤트의 흐름으로 표현되는 동적 그래프에 대한 학습의 다양한 문제에 적용할 수 있습니다. 간단히 말해서, TGN 인코더는 상호 작용을 기반으로 노드의 표현을 생성하여 작동하고 각 이벤트에서 업데이트합니다. 요약하자면, 어떻게 시간 t를 GNN의 요소 (node embedding, message)에 반영하는지에 대한 방법을 설명하고, RNN과 유사한 메모리 모듈을 GNN에 융합하였습니다.
<Model>
- Memory : 메모리는 모든 노드의 상태를 저장하여 노드의 과거 상호 작용을 압축적으로 표현합니다. RNN의 hidden state와 유사합니다. 여기서는 각 노드 i 에 대해 별도의 상태 벡터 s ᵢ ( t )가 있습니다. 새 노드가 나타나면 0으로 구성된 벡터로 초기화된 해당 state를 추가합니다. 또한 각 노드의 메모리는 매개변수가 아닌 상태 벡터일 뿐이므로 모델이 새로운 노드들 사이의 상호 작용을 수집할 때 업데이트될 수도 있습니다.
- Message function :
메모리 업데이트의 주요 메커니즘입니다. 시간 t 에서 노드 i 와 j 사이의 상호 작용이 주어지면 message function 는 메모리를 업데이트하는데 사용되는 두 개의 메시지( i 와 j )를 계산 합니다. 이것은 일반적인 그래프 신경망에서의 메시지 패싱과 유사합니다. 메시지는 상호작용 이전의 시간 t⁻ , 상호작용 시간 t 및 에지 특징에서 노드 i 와 j 의 메모리 함수입니다 .
- Memory update :
새로운 메시지로 메모리를 업데이트하는 데 사용됩니다. 이 모듈은 일반적으로 RNN으로 구현됩니다. 노드의 메모리가 시간이 지남에 따라 업데이트되는 벡터라는 점을 감안할 때 가장 간단한 방법은 노드 임베딩으로 직접 사용하는 방법을 생각해볼 수 있습니다. 그러나 이는 실효성 측면에서 문제가 발생합니다. 주어진 노드가 상호 작용에 관여하는 경우에만 메모리가 업데이트되도록 한다면, 노드가 상호작용에 관여하지 않으면 그 노드는 너무 오래된 정보를 갖게 됩니다. 예를 들어 사용자가 몇 달 동안 Twitter를 사용하지 않는 경우를 생각해 본다면, 사용자가 돌아올 때 그 동안 이미 새로운 관심사를 개발했을 수 있으므로 과거 활동에 대한 정보는 더 이상 필요가 없게됩니다. 따라서 임베딩을 계산하는 더 나은 방법이 필요합니다.
- embedding :
위 문제점의 해결책은 노드 이웃을 살펴보는 것입니다. 임베딩 모듈은 해당 노드의 시공간적 이웃에 대해 정보 통합을 수행하여 노드의 시간적 임베딩을 계산합니다. 노드가 잠시 동안 비활성 상태였더라도 이웃 중 일부가 활성 상태였을 가능성이 있으며 메모리를 집계하여 TGN은 노드에 대한 최신 임베딩을 계산할 수 있습니다. 이 예에서 사용자가 Twitter를 사용하지 않는 경우에도 친구는 계속 활성 상태이므로 사용자가 돌아올 때 친구의 최근 활동이 사용자 자신의 기록보다 관련성이 더 높을 수 있습니다.
위의 그림에서 노드 1에 대한 임베딩을 계산할 때 t보다 큰 시간인 t₂ , t ₃ 및 t ₄ 는 포함되지만, t보다 작은 t ₅ 는 포함되지 않습니다. 시간적 이웃은 시간 t 이전에 발생한 엣지만 포함합니다. 따라서 노드 5가 있는 간선은 미래에 발생하므로 포함되지 않습니다. 대신, 임베딩 모듈은 노드 1에 대한 임베딩을 계산하기 위해 노드 2, 3, 4의 feature(v)와 메모리뿐만 아니라 엣지의 feature등을 이용합니다.
- 메모리 관련 모듈들의 학습 방법
이러한 모듈이 학습시에 loss에 영향을 미치려면 일괄 상호 작용을 예측하기 전에 메모리를 업데이트해야 합니다. 그러나 메모리에는 우리가 예측하려는 정보가 이미 포함되어 있기 때문에 누출이 발생할 수 있습니다. 이 문제를 해결하기 위해 제안하는 전략은 이전 메시지로 메모리를 업데이트하는 것입니다.
이전에 모델에서 처리한 상호 작용에 대해 raw 메시지라고 하는 메시지를 계산하는 데 필요한 정보를 저장하는 raw 메시지 저장소라는 새로운 구성 요소가 필요합니다. 이를 통해 모델은 상호 작용으로 인해 이후 배치로 가져온 메모리 업데이트를 지연할 수 있습니다. 처음에는 이전 배치(1 및 2)에 저장된 raw 메시지에서 계산된 메시지를 사용하여 메모리가 업데이트됩니다. 그러면 방금 업데이트된 메모리(회색 링크)(3)를 사용하여 임베딩을 계산할 수 있습니다. 이렇게 하면 메모리 관련 모듈의 계산이 손실(4, 5)에 직접적인 영향을 미치고 기울기를 받습니다. 마지막으로 이 배치 상호 작용에 대한 raw 메시지는 raw 메시지 저장소(6)에 저장되어 향후 배치에서 사용됩니다.
댓글