기술 요약: 시계열 그래프 신경망을 위한 시간적 모티프 시그니처 (Temporal Motif Signatures for Temporal Graph Neural Networks)

문제 정의

실제 세계의 시간적 상호작용 스트림(예: 사회적 커뮤니케이션, 금융 이체, 온라인 리뷰)은 반복(repetition), 상호성(reciprocity), 스타 다양성(star diversity), 삼각 흐름(triadic flow)과 같은 단기 지평(short-horizon) 모티프 패턴 내에 예측 가능한 구조를 포함하고 있습니다. 현대적인 시계열 그래프 신경망(TGNN)은 이론적으로 시간적 스트림의 모든 함수를 추출할 수 있는 표현력 있는 시퀀스 모델이지만, 이들의 귀납적 편향(inductive biases)과 제한된 학습 예산은 특정 단기 구조적 정규성을 포착하는 데 한계를 보입니다. 이러한 정규성은 분석적으로 계산하기 매우 간단하지만 다운스트림 태스크에서 매우 중요합니다. 본 논문은 표준 TGNN이 학습하는 내용과 명시적인 단기 통계 사이의 간극을 다루며, 원칙적이고 아키텍처에 구애받지 않는 증강(augmentation)이 이 잔여 간극을 메울 수 있는지 질문합니다.

방법론

1. 경험적 진단 및 시그니처 식별

저자들은 먼저 다양한 13개의 실제 및 합성 시계열 데이터셋(MOOC, Bitcoin Alpha/OTC, TGB 벤치마크 포함)을 대상으로 후보별 과거 윈도우 모티프 카운트를 분석합니다. 이들은 모티프 활동이 세 가지 척도 안정적 축(scale-stable axes)을 따라 일관되게 조직됨을 확인했습니다:

• A1 (Dyadic Recency/Reciprocity): 후보 쌍 $(u, v)$ 사이의 직접적인 상호작용 타이밍과 빈도를 포착합니다.
• A2 (Star Diversity): 시간 윈도우 내에서 $u$ 또는 $v$와 상호작용하는 이웃의 다양성을 측정합니다 (예: 학생이 상호작용한 서로 다른 항목의 수).
• A3 (Triadic Flow): $u$와 $v$를 연결하는 제3자를 통한 상호작용의 흐름을 포착합니다 (예: 공통 이웃).

2. 모티프 특징 맵 $h(u, v, t)$

이러한 축들을 기반으로, 저자들은 컴팩트한 13차원 후보 지역 모티프 특징 맵 $h(u, v, t) \in \mathbb{R}^{13}$을 설계했습니다. 주요 설계 제약 조건은 다음과 같습니다:

• 누출 안전성 (Leakage Safety): 특징은 과거 윈도우 $W_{t}^{past}(\Delta) = \{i : t - \Delta \le t_i < t\}$로부터 엄격히 계산되어, 후보 표현에 미래 정보가 유출되지 않도록 보장합니다.
• 고정 차원: 13개의 특징은 학습 가능한 선형 임베딩 행렬 $M$을 통해 아키텍처 변경 없이 모든 정적 또는 시계열 인코더에 결합됩니다.
• 서브 패밀리 (Sub-families): 13개의 좌표는 세 가지 축에 대응합니다:
  • A1 (5개 특징): $u \to v$ 및 $v \to u$ 이벤트 카운트, 쌍(paired) 이벤트, 버스트성(burstiness), 그리고 마지막 상호적 이벤트 이후의 정규화된 시간.
  • A2 (4개 특징): 윈도우 내의 서로 다른 이웃 집합 크기($N_{u}^{out}, N_{u}^{in}, N_{v}^{out}, N_{v}^{in}$), 허브 문제를 처리하기 위해 캡핑(capping) 처리됨.
  • A3 (4개 특징): 이웃 집합 간의 방향성 크로스 웨지(cross-wedge) 및 바이 웨지(bi-wedge) 교집합 크기.
• 정규화: 롱테일 분포를 보이는 카운트 좌표는 비교 가능성을 확보하기 위해 $\log_{10}(1+x)$ 변환을 거칩니다.

3. 이론적 배치 (Temporal Weisfeiler-Leman)

본 논문은 표준 시간적 메시 전달 GNN(MP-GNN)에 대한 이론적 경계를 설정합니다. 일반적인 에지 스코어링 추상화 하에서, 이 모델들은 후보 고정 시간적 Weisfeiler-Leman(candidate-anchored temporal WL) 계층의 첫 번째 레벨(temporal-1-WL)에 의해 제한됩니다.

• 저자들은 (예: $C_6$ 사이클 vs 두 개의 분리된 삼각형 $2K_3$) 시간적-1-WL이 구분하지 못하는(동일한 색상으로 붕괴시키는) 앵커드 시간적 스트림이 존재함을 증와하며, 모티프 특징 맵 $h$는 이를 완벽하게 구분함을 증명합니다.
• 이는 모티프 증강이 표준 시간적 MP-GNN의 표현력을 엄격히 상회하며, WL 병목 현상을 깨뜨리는 "증거(witness)" 역할을 함을 의미합니다.

주요 기여

1. 진단 (섹션 4): 본 논문은 후보별 모티프 카운트가 시간적 스트림을 세 가지 지배적이고 척도 안정적인 축(A1, A2, A3)에 따라 조직함을 명시합니다. 이러한 데이터셋별 시그니처는 모티프 증강이 가장 큰 성능 향상을 가져올 지점을 예측합니다.
2. 시간적 표현력 (섹션 6): 저자들은 표준 시간적 MP-GNN을 후보 고정 시간적-WL 계층 내에 배치하는 이론적 위치를 제공합니다. 이들은 모티프 특징이 시간적-1-WL이 붕괴시키는 후보들을 구분해내는 특정 스트림 쌍을 제시함으로써, 증강이 모델을 해당 계층의 첫 번째 레벨 너머로 끌어올림을 입증합니다.
3. 경험적 성능 (섹션 7): 모티프 증강이 강력한 TGNN 베이스라인들과 비교했을 때 다양한 이질적 태스크(TGB 링크 속성 예측, 에지 분류, 그래프 수준 분류)에서 일관되게 성능을 높임을 보여줍니다. 이 이득은 해석 가능합니다: 베이스라인이 단기 구조를 포착하지 못하는 곳(예: MOOC)에서 가장 크며, 베이스라인이 이미 관련 구조를 포착하고 있는 곳에서는 미미합니다.

실험 결과

프레임워크는 다음을 통해 평가되었습니다:

• TGB 링크 속성 예측: 5개의 베이스라인(TPNet, HyperEvent, DyGFormer, TNCN, TGN)과 3개의 데이터셋(Wiki, Review, Coin)을 대상으로 수행되었습니다.
  • 결과: 모티프 증강은 평가된 모든 베이스라인-데이터셋 쌍에서 성능을 높였습니다. 가장 유의미한 이득은 tgbl-review-v2 데이터셋에 대한 DyGFormer에서 관찰되었으며, 평균 역순위(MRR)가 0.224에서 0.413으로 증가했습니다.
  • 관찰: tgbl-coin-v2에 대한 TPNet과 같은 베이스라인의 경우 이득이 0의 1 표준 편차 이내였는데, 이는 해당 베이스라인들이 이미 해당 데이터셋에 대한 관련 단기 구조를 포착하고 있음을 시사합니다.
• 에지 분류:
  • MOOC: 학생의 중도 탈락을 예측하는 이진 분류 태스크입니다. 바닐라 GraphSAGE 인코더는 0.0164의 PR-AUC를 달려했습니다. 4개 특징의 스타 카운트 서브셋(A2)을 추가했을 때 0.1430으로 상승했고, 전체 13개 특징 맵을 사용했을 때는 0.1659를 달려했습니다.
  • Bitcoin Alpha/OTC: 신뢰 분류 태스크에서 완만하지만 일관된 개선을 보였습니다 (예: Alpha에서 SAGE PR-AUC가 0.9282에서 0.9667로 상승).
• 그래프 수준 분류: 합성 시간적 생성기 상에서 모티프 증강은 아키텍처 변경 없이 GAT의 정확도를 붕괴된 16.7%(다수 클래스 예측)에서 **94.0%**로 크게 끌어올렸습니다.

절제 및 대조 실험 (Ablation and Controls):

• Leave-one-out 분석을 통해 어떤 단일 좌표도 일률적으로 중복되지 않음을 확인했습니다. 즉, 데이터셋마다 서로 다른 축에 의존합니다 (예: MOOC는 A2 스타 다양성에 크게 의존하는 반면, Bitcoin Alpha는 A1 상호성에 의존함).
• 대조 실험을 통해 이득의 원인이 "추가 용량(extra capacity)"이 아님을 입증했습니다 (랜덤 특징은 이러한 상승을 재현하지 못함). 또한 이 이득이 단순히 노드의 활동 카운트의 대리 지표가 아님을 확인했습니다.

의의 및 주장

본 논문은 시간적 모티프 시그니처가 TGNN에 단기 구조적 정규성을 주입하는 컴팩트하고, 해석 가능하며, 아키텍처에 구애받지 않는 방법이라고 주장합니다.

• 예측력: A1/A2/A3 축을 따르는 데이터셋별 시그니처는 증강이 가장 유익할 곳을 예측하는 진단 도구 역할을 합니다.
• 이론적 근거: 증강을 시간적-WL 계층과 관련하여 배치함으로써, 본 논문은 왜 표준 TGNN이 특정 태스크에서 실패하는지(그들은 시간적-1-WL에 의해 제한됨)와 이 증강이 어떻게 이를 극복하는지를 명확히 합니다.
• 실용적 유용성: 이 방법은 기본 인코더 아키텍처의 변경을 요구하지 않고 사전 계산된 특징 벡터를 결번에 결합하기만 하면 되므로, 기존 파이프라인에 쉽게 배포할 수 있습니다.

저자들은 윈도우 반경 $\\Delta$가 민감한 하이퍼파라미터라는 점과, 삼각 흐름이 미미한 희소한 스트림에서는 증가된 차원으로 축소되어 그에 따라 이득도 작아질 수 있다는 점을 언급하며 신중한 입장을 유지합니다. 이 프레임워크는 바닐라 TGNN이 에지 스코어러에게 노출하지 못하는 특정 구조적 신호를 드러내기 위한 원칙적인 방법으로 제시됩니다.