Stochastic Event Prediction via Temporal Motif Transitions

이 논문은 이산적인 시간적 모티프 전이를 포아송 과정으로 모델링하여 시계열적 특성을 보존하고 기존 그래프 신경망과 호환되는 'STEP' 프레임워크를 제안함으로써, 기존 방법론 대비 정밀도와 효율성을 크게 향상시킨 사건 예측 기법을 제시합니다.

핵심

1. 기존 방법의 문제점: "무작위 추측" vs "패턴 읽기"

기존의 네트워크 예측 프로그램들은 대부분 "이 두 사람이 다시 연락할까? (Yes/No)" 라는 질문을 던지며, 정답을 맞추기 위해 수많은 가상의 실패 사례 (Negative Sampling) 를 만들어내며 학습했습니다.

• 비유: 마치 주사위를 던지는 것과 비슷합니다. "내일 A 와 B 가 연락할까?"라고 물으면, "아니, A 와 C 가 연락할 수도 있고, 아무도 연락 안 할 수도 있어"라고 무작위로 부정적인 경우를 많이 만들어내며 확률을 계산합니다.
• 문제점: 하지만 실제 세상은 무작위가 아닙니다. 사람들은 일정한 리듬과 패턴을 가지고 행동합니다. 예를 들어, "월요일 아침에 커피를 마시고, 오후 3 시에 동료에게 메일을 보낸다"는 식의 시간적 순서와 연결 고리를 무시하고 단순히 '연락할지 말지'만 판단하는 것은 불완전한 예측입니다.

2. STEP 의 핵심 아이디어: "시간의 레고 블록"

STEP 은 사건들을 개별적인 점으로 보지 않고, 시간의 흐름에 따라 쌓아지는 '레고 블록' (모티프, Motif) 으로 봅니다.

• 비유:
  • 기존 방법: "레고 조각 하나하나가 어디에 있을지"만 예측합니다.
  • STEP: "어떤 레고 블록 (사건) 이 쌓이면, 다음에 어떤 모양 (패턴) 이 만들어질지"를 예측합니다.
  • 예를 들어, "친구 A 가 B 에게 메시지를 보냈고 (1 단계), B 가 C 에게 답장을 보냈다 (2 단계)"는 특정 패턴이 있다면, STEP 는 "이 패턴이 완성되면 다음에 D 가 E 에게 연락할 확률이 높다"고 예측합니다.

이것을 시간적 모티프 (Temporal Motif) 라고 부릅니다. STEP 는 이 레고 블록들이 어떻게 변형되고 이어지는지 관찰하여 미래를 예측합니다.

3. STEP 가 어떻게 작동할까? (두 가지 상황)

STEP 은 매 순간 두 가지 질문을 던지며 다음 사건을 결정합니다.

1. 새로운 시작인가? (Cold Event)
   • 상황: 완전히 새로운 관계가 시작될 때 (예: 처음 연락하는 두 사람).
   • STEP 의 판단: "이 두 사람이 처음 연락할 확률이 얼마나 될까?"를 과거의 데이터 (누가 누구와 자주 연락했는지) 와 시간 간격 (마지막 연락이 언제였는지) 을 바탕으로 계산합니다.
2. 기존의 흐름을 이어가는가? (Hot Event)
   • 상황: 이미 이어지고 있는 대화나 거래가 계속될 때.
   • STEP 의 판단: "지금 쌓여 있는 레고 블록 (패턴) 에 다음 조각을 붙이면 어떤 모양이 될까?"를 계산합니다. 가장 그럴듯한 다음 단계를 선택합니다.

이 모든 과정은 포아송 과정 (Poisson Process) 이라는 수학적 원리를 사용합니다. 쉽게 말해, "사건이 언제 일어날지" 를 확률적으로 계산하는 방식입니다. 마치 비 오는 날을 예측할 때, "지금 비가 얼마나 자주 오고 있었는지"를 보고 "다음 비가 언제 올지"를 계산하는 것과 비슷합니다.

4. 왜 STEP 가 더 뛰어난가?

• 정확도: 기존 최고의 AI 모델들 (TGN, GraphMixer 등) 보다 최대 21% 더 높은 정확도를 보였습니다. 특히 "다음에 일어날 사건 100 개를 순서대로 맞히는" 예측에서는 99% 에 가까운 정확도를 기록했습니다.
• 속도: 복잡한 신경망을 깊게 학습시키는 대신, 간단한 확률 계산으로 작동하므로 매우 빠릅니다.
• 유연성: 기존 AI 모델의 옆에 보조 도구처럼 붙여 쓸 수도 있습니다. STEP 가 만든 "패턴 정보"를 기존 AI 에게 주면, 기존 AI 도 더 똑똑해집니다.

5. 실생활 예시: "소셜 미디어 알림"

• 기존 방식: "내일 A 가 B 에게 글을 올릴까?"라고 물어서 "아니"라고 답할 확률이 높으면 알림을 보내지 않습니다. 하지만 실제로는 A 가 B 에게 글을 올릴 수도 있는데 놓칠 수 있습니다.
• STEP 방식: "A 는 보통 월요일 아침에 B 와 대화하고, 그다음 C 와 대화하는 패턴이 있다"는 것을 파악합니다. 그래서 "지금 A 가 B 와 대화했으니, 곧 C 와 대화할 시간이 왔을 것이다"라고 예측하여 정확한 타이밍에 알림을 보냅니다.

요약

이 논문은 "미래의 사건을 예측할 때, 단순히 '연결될지'만 보는 게 아니라, '어떤 순서와 패턴으로' 연결될지" 를 분석해야 한다는 점을 강조합니다.

STEP 은 마치 시간의 흐름을 읽는 천재 예언가처럼, 과거의 사건들이 쌓여 만든 패턴 (레고) 을 분석하고, 확률 (비 오는 날 계산) 을 적용하여 가장 그럴듯한 다음 사건을 찾아냅니다. 이는 SNS 알림, 사기 거래 탐지, 질병 전파 예측 등 다양한 분야에서 더 빠르고 정확한 예측을 가능하게 합니다.

기술 요약

1. 문제 정의 (Problem Definition)

• 배경: 소셜 미디어, 금융, 생물학 등 다양한 분야에서 타임스탬프가 찍힌 상호작용 데이터가 생성됩니다. 이러한 데이터의 미래 사건을 예측하는 것은 네트워크의 진화하는 위상과 시간적 순서를 모두 고려해야 하는 중요한 과제입니다.
• 기존 접근법의 한계:
  • 대부분의 기존 방법 (TGNN 등) 은 링크 예측을 이진 분류 (Binary Classification) 문제로 접근하며, 부정적 샘플링 (Negative Sampling) 을 사용합니다.
  • 이는 실제 세계의 상호작용이 갖는 연속성과 상관관계 (Sequential and Correlated nature) 를 무시합니다.
  • 또한, 부정적 샘플링 전략은 실제 발생하지 않을 가능성이 높은 사소한 부정 사례를 포함하여 평가 지표를 왜곡할 수 있으며, 미래의 에지가 독립적인 이진 결정이라고 가정하는 것은 비현실적입니다.
• 목표: 실제 시나리오 (알림 스케줄링, 이벤트 우선순위 지정 등) 에 더 부합하도록, 미래의 상호작용 시퀀스를 연속적인 시간 흐름 속에서 예측하는 생성적 예측 (Generative Forecasting) 모델을 개발하는 것입니다.

2. 방법론 (Methodology: STEP Framework)

저자들은 STEP (STochastic Event Predictor) 을 제안했습니다. 이는 포아송 과정 (Poisson Process) 에 기반한 확률적 모델과 이산적인 시간 모티프 (Temporal Motif) 전이를 결합한 경량 생성 모델입니다.

• 핵심 개념:

  • 시간 모티프 (Temporal Motif): 시간 순서를 따르는 연결된 하위 그래프 패턴.
  • 모티프 전이 (Motif Transition): 하나의 모티프가 새로운 사건이 발생하여 다른 모티프로 진화하는 과정.
  • 오픈 모티프 (Open Motif): 현재까지 생성된 부분 모티프 인스턴스로, 새로운 사건이 들어와 확장될 수 있는 상태.
  • 콜드/핫 이벤트:
    • 콜드 이벤트 (Cold Event): 새로운 모티프 인스턴스를 시작하는 사건.
    • 핫 이벤트 (Hot Event): 기존 오픈 모티프를 확장하는 사건.

• 예측 프로세스 (Generative Process):

  1. 시간 진행: 전체 네트워크의 평균 도착률 ($\lambda_{global}$) 을 기반으로 포아송 과정을 통해 다음 사건 발생 시간 ($\Delta \tau$) 을 샘플링합니다.
  2. 사건 유형 결정: 베르누이 시행을 통해 새로운 모티프를 시작할지 (콜드), 기존 모티프를 확장할지 (핫) 결정합니다.
  3. 사건 선택 (베이즈 점수화):
     • 새로운 모티프 시작 시: 각 엣지의 대기 시간 분포 (지수 분포) 와 엣지 발생 빈도 (Prior) 를 결합한 베이즈 후행 확률을 계산하여 가장 확률이 높은 엣지를 선택합니다.
     • 기존 모티프 확장 시: 가능한 모든 모티프 전이 ($m \to m'$) 에 대해, 대기 시간의 우도 (Likelihood) 와 모티프 전이 빈도 (Prior) 를 결합한 점수를 계산하여 가장 확률이 높은 확장을 선택합니다.
  4. 상태 업데이트: 선택된 사건을 이벤트 스트림에 추가하고 오픈 모티프 세트를 업데이트합니다.

• 특징 벡터 (Feature Vectors):

  • STEP 는 생성 모델로서뿐만 아니라, 기존 TGNN (TGN, GraphMixer 등) 의 출력과 결합할 수 있는 압축된 확률적 특징 벡터를 생성합니다.
  • 각 사건에 대해, 해당 사건이 어떤 모티프 전이 패턴을 통해 발생했을지에 대한 후행 확률을 벡터로 인코딩하여 TGNN 의 임베딩에 추가합니다. 이는 아키텍처 수정 없이 기존 모델의 성능을 향상시킵니다.

3. 주요 기여 (Key Contributions)

1. 문제 재정의: 링크 예측을 부정적 샘플링이 필요한 이진 분류가 아닌, 순차적 예측 (Sequential Forecasting) 문제로 공식화하여 실제 세계의 시간적 순서와 상관관계를 존중합니다.
2. 경량 생성 모델: 신경망 훈련 없이 포아송 과정과 베이지안 모티프 전이 점수화를 결합하여 연속 시간에서의 다음 $k$개 사건 예측을 가능하게 합니다.
3. 호환성 있는 특징 추출: TGNN 아키텍처를 변경하지 않고도 기존 모델의 출력과 결합하여 성능을 향상시킬 수 있는 모티프 기반 확률적 특징 벡터를 도입했습니다.
4. 효율적인 구현: C++ 로 구현되어 Python 기반 TGNN 과 프로세스 간 통신 (IPC) 을 통해 연동되며, 최대 700 만 개의 이벤트를 가진 대규모 그래프에서도 저지연 추론이 가능합니다.

4. 실험 결과 (Results)

5 개의 실제 데이터셋 (CollegeMsg, Email-Eu, FBWall, SMS-A, Wiki-Talk) 에서 실험을 수행했습니다.

• 순차 예측 성능 (Sequence Forecasting):

  • 다음 $k$개 이벤트를 예측하는 작업에서 **0.99 의 정밀도 (Precision)**를 달성했습니다.
  • 예측 횟수 ($k$) 가 증가함에 따라 성능이 서서히 감소하지만, 대부분의 데이터셋에서 $k=100$ 부근에서 높은 정밀도를 유지했습니다.
  • 반복되는 상호작용 비율 (RER) 이 높은 데이터셋 (Email-Eu 등) 에서 더 뛰어난 성능을 보였습니다.

• 분류 성능 (Classification):

  • STEP 특징 벡터를 TGN 및 GraphMixer 와 결합했을 때, 기존 모티프 인식 모델인 TempME 를 능가했습니다.
  • CollegeMsg 데이터셋에서 TGN 기반 모델의 평균 정밀도 (Average Precision) 를 21.23% 향상시켰습니다.
  • FBWall 과 Wiki-Talk 와 같은 대규모 데이터셋에서 TempME 는 메모리 부족 (OOM) 으로 실패했으나, STEP 는 안정적으로 작동했습니다.

• 실행 시간 (Runtime):

  • STEP 는 TempME 보다 훨씬 효율적이며, 신경망 훈련 없이도 빠른 추론이 가능합니다.
  • Wiki-Talk (약 780 만 이벤트) 와 같은 대규모 데이터셋에서도 실시간에 가까운 예측 속도를 유지했습니다.

5. 의의 및 결론 (Significance)

• 실용성: STEP 는 복잡한 신경망 훈련 없이도 강력한 예측 능력을 제공하며, 대규모 그래프에서도 확장성이 뛰어납니다.
• 이론적 기여: 시간적 모티프 전이를 확률적 과정으로 모델링함으로써, 네트워크의 미시적 진화 (Micro-evolution) 를 포착하는 새로운 관점을 제시합니다.
• 한계 및 향후 과제:
  • 현재 모델은 기존에 존재하던 노드 쌍 간의 상호작용만 예측할 수 있으며, 완전히 새로운 노드 쌍 (Unseen node pairs) 에 대한 일반화 능력은 제한적입니다.
  • 네트워크의 개념 변화 (Concept Drift) 에 적응하기 위한 적응형 모티프 선택 메커니즘이 향후 연구 과제로 남았습니다.

요약하자면, 이 논문은 시간적 그래프 예측의 패러다임을 '분류'에서 '생성적 예측'으로 전환시켰으며, 경량 확률 모델을 통해 기존 딥러닝 기반 방법론의 한계 (계산 비용, 부정적 샘플링의 왜곡) 를 극복하고 뛰어난 성능을 입증했습니다.