TIDFormer: Exploiting Temporal and Interactive Dynamics Makes A Great Dynamic Graph Transformer

기술 요약: TIDFormer

문제 정의

본 논문은 기존의 트랜스포머 기반 연속 시간 동적 그래프(Continuous-Time Dynamic Graph, CTDG) 학습 방법의 두 가지 결정적인 한계를 다룹니다:

1. 해석 불가능한 자기 주의 메커니즘 (Self-Attention Mechanisms, SAMs): 기존 연구들은 동적 그래프에 대한 SAM을 링크 단위의 다운스트림 태스크에 대한 해석 가능성이 결여된 방식으로 정의합니다. 구체적으로, 단일 노드 레벨(Single-Node Level, SL) 정의(예: TGAT)는 링크 예측에 필요한 노드 쌍 간의 의존성을 포착하지 못하며, 다중 노드 레벨(Multi-Node Level, ML) 정의(예: DyGFormer)는 소스 노드와 타겟 노드의 시퀀스를 혼합하여 시간적 순서를 깨뜨리고 주의 가중치(attention weights) 학습을 저해할 수 있습니다.
2. 비효식적이고 불충분한 역학 모델링 (Dynamics Modeling): 기존 방법들은 과도한 복잡성을 도입하지 않으면서 시간적 및 상호작적인 역학을 효과적으로 인코딩하는 데 어려움을 겪습니다.
   • 시간적 인코딩 (Temporal Encoding): 일반적인 코사인 기반 매핑은 동적 그래프에 내재된 위상 및 주기적 특성(예: 주간, 월간 패턴)을 포착하지 못합니다.
   • 상호작적 인코딩 (Interactive Encoding): 이웃 상호작용 모듈은 이분 그래프(예: 사용자-아이템 시스템)에 적용될 때 성능이 저하되는 경우가 많습니다. 이는 1차 샘플링(first-order sampling) 하에서 소스 노드와 타겟 노드가 공통 이웃을 공유하지 않아, 해당 모듈이 단순히 상호작용 시간만을 기록하는 수준으로 전락하기 때문입니다.

방법론

저자들은 해석 가능한 SAM과 일련의 효율적인 인코딩 모듈을 사용하여 Temporal(시간적) 및 Interactive(상호작적인) Dynamics(역학)를 완전히 활용하도록 설계된 동적 그래프 트랜스포머인 TIDFormer를 제안합니다.

1. 상호작용 레벨(Interaction Level, IL)에서의 해석 가능한 자기 주의 메커니즘

핵러 아키텍처의 변화는 SAM을 상호작용 레벨에서 정의하는 것입니다.

• 개념: 개별 노드를 토큰화(SL)하거나 소스/타겟 시퀀스를 혼합(ML)하는 대신, 노드 쌍 간의 과거 상호작용을 기반으로 시퀀스를 구성합니다.
• 구조: 시퀀스 $H_{IL}$의 각 토큰은 원래의 노드/에지 특징에 시간-상호작용 임베딩($I$)을 결로합하여 구성됩니다.
• 이점: 이는 원래의 연대기적 순서를 보존하는 동시에, 상호작용하는 노드 쌍 간의 의존성을 명시적으로 모델링함으로써 주의 메커니즘을 링크 단위의 다운스트림 태스크 요구사항에 부합하게 만듭니다.

2. 인코딩 모듈

TIDFormer는 오직 **1차 이웃(first-order neighbors)**만을 사용하여 역학을 효율적으로 인코딩하는 세 가지 특정 모듈을 도입합니다.

• 혼합 입도 시간 인코딩 (Mixed-granularity Temporal Encoding, MTE):

  • 미세한 상대적 타임스탬프와 거친 입도의 달력 기반 시간 분할(주간, 월간, 연간)을 통합합니다.
  • 미세한 간격에는 코사인 함수를 사용하고, 거친 세그먼트에는 선형 투영(linear projection)을 사용합니다.
  • 이를 통해 복잡한 주파수 영역 변환 없이도 즉각적인 시간적 의존성과 전역적인 주기적 패턴을 모두 포착합니다.

• 양방향 상호작용 인코딩 (Bidirectional Interaction Encoding, BIE):

  • 이분 그래프에서의 "공통 이웃 부재" 문제를 해결합니다.
  • 양방향 메커니즘을 활용하여, 소스-타겟 쌍에 대해 모델은 현재 배치의 이웃 딕셔너리로부터 다른 노드의 2차 이웃을 검색합니다.
  • 이는 명시적인 고차 샘플링의 계산 비용 없이 1차 샘플링만으로 고차 상호작용 정보를 효과적으로 재구성하여 수용 영역(receptive field)을 크게 확장합니다.

• 계절성 및 추세 인코딩 (Seasonality & Trend Encoding, STE):

  • 단순 평균 풀링 연산을 사용하여 상호작용 시퀀스를 **추세(trend)**와 계절성(seasonal) 성분으로 분해합니다.
  • 추세 성분($Z_t$)은 평활화된 전체 상호작용 패턴을 나타내며, 계절성 성분($Z_s$)은 주기적 변동을 포착합니다.
  • 이를 통해 모델은 과거 상호작용 패턴의 잠재적 변화를 포착함으로써 시간적 및 상호작적인 특징을 공동으로 모델링할 수 있습니다.

3. 아키텍처

인코딩된 임베딩(초기 노드/에지 + MTE + BIE + STE)은 트랜스포머 백본을 위한 입력 시퀀스를 형성하기 위해 결합됩니다. 모델은 상호작용 레벨에서 멀티 헤드 자기 주의(Multi-Head Self-Attention, MSA)를 사용하며, 그 뒤에 잔차 연결(residual connections)과 레이어 정규화(Layer Normalization)가 포함된 표준 피드 포워드 네트워크(FFN)를 배치합니다.

주요 기여

1. TIDFormer 모델: 시간적 및 상호작적인 역학을 완전히 채굴하는 트랜스포머 기반 동적 그래프 모델입니다.
2. 해석 가능한 SAM: 기존의 SL 및 ML 정의의 해석 가능성 문제를 해결하는, 상호작용 레벨(Interaction-Level) SAM을 제안하고 실험적으로 검증했습니다.
3. 새로운 인코딩 모듈: MTE, BIE, STE 모듈을 도입하여 고차 샘플링이나 복잡한 주파수 변환의 계산 오버헤드 없이 복잡한 역학을 효과적으로 포착합니다.

실험 결과

저자들은 7개의 실제 세계 CTDG 데이터셋(Wikipedia, Reddit, MOOC, LastFM, Enron, Social Evo., UCI)에 대해 두 가지 태스크(동적 링크 예측 및 동적 노드 분류)로 TIDFormer를 평가했습니다.

• 성능: TIDFormer는 대부분의 데이터셋과 실험 설정(전이 학습 및 귀납적 학습)에서 SOTA 모델(JODIE, TGAT, TGN, DyGFormer, FreeDyG 등 포함)을 능가했습니다.
  • 무작위 네거티브 샘플링을 사용한 전이 학습 링크 예측에서, TIDFormer는 평균 순위 1.57을 달관했습니다.
  • 노드 분류에서 평균 순위 2.00을 달성했습니다.
• 효율성:
  • TIDFormer의 시간 복잡도는 $O(n) + O(n^2 \times dim)$으로, 1차 샘플링 트랜스포머와 유사합니다.
  • 샘플링 단계에서 $O(n^2)$의 복잡도를 갖는 2차 샘플링 방법보다 훨씬 더 효율적입니다.
  • Wikipedia 데이터셋에 대한 실증적 결과에 따르면, TIDFormer는 TGAT, TGN, DyGFormer와 비교하여 더 낮은 에폭당 훈련 시간을 기록하면서도 더 높은 링크 예측 정밀도(AP)를 달성했습니다.

의의 및 주장

본 논문은 **시간적 및 상호작적인 역학을 올바르게 활용한다면 "쉽게 훌륭한 동적 그래프 트랜스포머를 만들 수 있다"**고 주장합니다. 본 연구의 의의는 다음과 같습니다:

• 해석 가능성 교정: 데이터의 연대기적 특성과 링크 예측의 요구사항에 부합하는, 동적 그래프를 위한 이론적으로 타당하고 실험적으로 검증된 SAM 정의를 제공합니다.
• 효율성 vs 성능: 높은 성능을 얻기 위해 복잡하고 계산 비용이 많이 드는 모듈(예: 푸리에 변환 또는 고차 샘플링)이 반드시 필요하지 않음을 입증합니다. 제안된 단순한 분해 및 양방향 메커니즘만으로도 복잡한 역학을 포착하기에 충분합니다.
• 일반화 가능성: 모델은 이분 그래프(예: 사용자-아이템)와 비이분 그래프 모두에서 견고하게 작동하며, 기존의 이웃 인코딩 접근 방식이 가진 특정 한계를 극복합니다.

저자들은 TIDFormer가 효율성과 효과성 사이의 균형을 맞추는 데 있어 한 단계 진보한 모델이라고 결론지었으나, 향-후 연구에서는 확장성 최 최적화 및 메모리 기반 모델과의 비교에 집중할 수 있음을 인정했습니다.