'Si'multaneous 'S'patial-'T'emporal Message Passing for Dynamic Graph Representation Learning

본 논문은 교차 시간 간선을 그래프에 추가하여 공간 및 시간 메시지 전달을 단일 연산으로 통합하는 새로운 동적 그래프 신경망인 SiST-GNN 을 소개함으로써 다양한 벤치마크에서 링크 예측 및 노드 분류 분야에서 최첨단 성능을 달성함을 제시한다.

핵심

거대하고 끊임없이 변화하는 소셜 네트워크에서 누가 누구와 친구가 될지 예측한다고 상상해 보세요. 이를 위해서는 네트워크 내 모든 사람에 대해 두 가지를 이해해야 합니다:

1. 지금 그들이 누구인지: 현재의 프로필, 관심사, 그리고 정확히 이 순간 누구와 대화하고 있는지 (공간적 정보).
2. 그들이 과거에 누구였는지: 지난 몇 달 동안의 우정, 논쟁, 상호작용에 대한 전체적인 역사 (시간적 정보).

오랫동안 컴퓨터 과학자들은 이를 해결하기 위해 "동적 그래프 신경망 (DGNN)"을 구축해 왔습니다. 그러나 해당 논문은 거의 모든 기존 방법론이 치명적인 실수를 저지르고 있다고 주장합니다. 즉, 이 두 가지 정보를 마치 책을 한 장씩 읽듯이 순차적으로 바라본다는 것입니다.

구식 방식: 조립 라인의 병목 현상

논문은 이러한 구식 모델이 작동하는 두 가지 일반적인 방식을 설명하며, 둘 다 "정보 병목 현상"으로 고통받고 있다고 지적합니다.

• "시간 우선" 공장: 한 직원이 먼저 한 사람의 전체 인생 이야기 (역사) 를 읽고 짧은 요약 노트 하나를 작성한다고 상상해 보세요. 그 노트가 작성된 이후에야 두 번째 직원이 그 사람이 지금 누구와 대화하고 있는지 살펴봅니다.
  • 문제점: 두 번째 직원은 "이 사람은 옛날 절친과 대화하고 있는데, 현재 프로필은 그들을 싫어한다고 말하고 있네"라고 물을 수 없습니다. 현재 맥락이 보이기 전에 역사는 이미 요약 노트에 잠겨버렸기 때문입니다.
• "공간 우선" 공장: 반대로 상상해 보세요. 한 직원이 먼저 그 사람이 지금 누구와 대화하고 있는지 살펴보고 그룹화합니다. 그 그룹화가 완료된 이후에야 두 번째 직원이 그 사람의 역사를 살펴봅니다.
  • 문제점: 두 번째 직원은 "잠깐, 이 그룹은 의심스러워 보이네. 역사적으로 이 사람은 결코 이들과 어울린 적이 없는데"라고 말할 수 없습니다. 역사가 참조되기 전에 현재 그룹화가 이미 끝났기 때문입니다.

두 경우 모두 모델은 과거 또는 현재의 "압축된" 버전을 기반으로 결정을 내릴 수밖에 없어, 실시간으로 서로를 저울질할 기회를 놓칩니다.

새로운 방식: SiST-GNN (동시적 공간 - 시간)

저자들은 SiST-GNN이라는 새로운 아키텍처를 제안합니다. 조립 라인이 아니라, 모두가 동시에 발언할 수 있는 원탁 회의를 상상해 보세요.

간단한 비유를 들어 SiST-GNN 이 작동하는 방식을 설명해 보겠습니다.

1. 쌍둥이 개념: 네트워크 내 모든 사람에 대해 모델은 "쌍둥이"를 생성합니다.
   • 쌍둥이 A는 그 사람의 현재 프로필과 현재 친구들을 가지고 있습니다.
   • 쌍둥이 B는 그 사람의 전체 역사 (과거에 대한 지속적인 요약) 를 가지고 있습니다.
2. 확장된 그래프: 모델은 특수하고 더 큰 지도를 구축합니다. 이 지도에서 쌍둥이 A 와 쌍둥이 B 는 서로 연결되어 있습니다. 또한, 쌍둥이 A 는 쌍둥이 B 의 이웃들과 연결되고, 쌍둥이 B 는 쌍둥이 A 의 이웃들과 연결됩니다.
3. 동시 채팅: 이제 모델은 단일 "메시지 전달" 단계를 실행합니다. 이 단계에서 모든 사람 (그리고 그들의 쌍둥이) 은 이웃들과 모두 동시에 대화합니다.
   • 모두가 함께 대화하기 때문에 모델은 다음과 같이 결정할 수 있습니다: "이 특정 예측을 위해 현재 대화가 혼란스러우니 쌍둥이 B(역사) 에 더 귀를 기울여야겠다"거나, "역사가 구식이라 쌍둥이 A(현재 상태) 에 더 귀를 기울여야겠다"고요.

모델은 어떤 정보를 먼저 유지할지 선택할 필요가 없습니다. 판사가 판결을 내리기 전에 현재의 증언과 과거 기록을 모두 듣는 것처럼, 두 가지를 동시에 저울질할 수 있습니다.

결과: 획기적인 도약

저자들은 이 새로운 "원탁 회의" 방식을 비트코인 신뢰 네트워크, 대학 게시판, 레딧 (Reddit) 을 포함한 9 개의 다양한 실제 데이터셋에서 14 개의 기존 모델과 비교하여 테스트했습니다.

• 링크 예측 (미래 연결 예측):

  • "고정" 테스트 (한 번에 전체 그림을 봄) 에서 SiST-GNN 은 이전 최우수 방법보다 109% 에서 277% 더 우수했습니다.
  • "실시간" 테스트 (새로운 데이터가 들어옴에 따라 업데이트, 실시간 피드와 유사) 에서 68% 에서 194% 더 우수했습니다.
  • 비유: 구식 모델이 50% 정확도로 날씨를 예측했다면, SiST-GNN 은 거의 완벽한 정확도로 예측하는 것입니다.

• 노드 분류 (이상 징후 탐지):

  • 모델은 데이터의 연속적인 흐름에서 "악의적 행위자" (예: 차단된 사용자) 를 찾아내는 작업에서도 테스트되었습니다. SiST-GNN 은 데이터를 시간 단위로 그룹화 (이메일을 일일 폴더에 넣는 것과 유사) 해야 했음에도 불구하고, 최상의 "이산 시간 (discrete-time)" 모델보다 7% 에서 22% 더 우수했습니다.
  • 놀랍게도, 데이터를 단위로 그룹화할 필요가 없는 가장 진보된 "연속 시간 (continuous-time)" 모델과도 동등한 성능을 발휘했습니다.

왜 이것이 중요한가 (논문에 따르면)

논문에 따르면, 이 엄청난 개선의 이유는 모델이 단순히 "더 똑똑하다"거나 더 많은 컴퓨팅 파워를 가지고 있기 때문이 아닙니다. 아키텍처가 마침내 한 사람의 역사와 현재 상황을 서로 직접 대화할 수 있는 이웃으로 취급할 수 있게 해주기 때문입니다.

"조립 라인" 병목 현상을 제거함으로써 모델은 이제 다음과 같이 말할 수 있습니다: "지금 당신과 낯선 사람이 대화하고 있지만, 당신의 역사는 당신이 항상 이런 낯선 사람을 신뢰해 왔음을 보여주니, 나는 이 상호작용을 신뢰할 것입니다." 또는 반대로: "당신은 친구와 대화하고 있지만, 당신의 역사는 방금 다툼이 있었음을 보여주니, 나는 의심할 것입니다."

논문은 이 "동시적" 접근 방식이 다양한 유형의 네트워크와 작업에서 작동하는 근본적인 업그레이드이며, 변화하는 관계를 이해하도록 컴퓨터를 가르치는 방식에 대한 새로운 기준을 설정했다고 결론지었습니다.

기술 요약

기술 요약: 동적 그래프 표현 학습을 위한 SiST-GNN

문제 정의

그래프 스냅샷 시퀀스에서 작동하는 동적 그래프 신경망 (DGNN) 은 현재 경직된 순차적 처리로 인한 정보 병목 현상이라는 근본적인 구조적 한계에 직면해 있습니다. 기존 접근법들은 보편적으로 두 가지 패러다임 중 하나를 채택합니다:

1. 시간 우선 (T→S): 순환 또는 어텐션 모듈이 먼저 노드 특징 궤적을 인코딩하여 시간적 요약을 생성한 후, 이를 공간적 집적을 위해 그래프 신경망 (GNN) 에 입력합니다.
2. 공간 우선 (S→T): GNN 이 먼저 스냅샷 내 이웃 특징을 집적한 후, 생성된 구조 임베딩을 GRU, LSTM 과 같은 시간 모듈에서 처리합니다.

두 경우 모두 두 번째 단계는 첫 번째 단계에서 생성된 사전 압축된 요약을 소비해야 합니다. 이러한 순서 정렬은 토폴로지와 진화에 대한 **공동 추론 (joint reasoning)**을 방해합니다. 구체적으로, 공간 우선 모델은 해당 정보가 아직 계산되지 않았기 때문에 이웃의 역사적 궤적에 기반하여 메시지 전달 연산자를 조건화할 수 없습니다. 반대로, 시간 우선 모델은 순환 셀을 현재 구조적 이웃에 기반하여 조건화할 수 없습니다. 이러한 경직성은 모델이 각 이웃의 특정 상황에 기반하여 신호를 동적으로 가중치 부여하는 대신, 구조적 신호와 시간적 신호 중 하나를 선택하도록 강요합니다.

방법론: SiST-GNN

저자들은 공간 및 시간 신호를 단일 메시지 전달 연산 내에서 융합하는 세 번째 패러다임인 **SiST-GNN (Simultaneous Spatial-Temporal GNN)**을 제안합니다.

핵심 아키텍처

모듈을 체인하는 대신, SiST-GNN 은 각 스냅샷 $t$에서 시간적으로 확장된 그래프 ($\hat{G}_t$) 를 구성합니다:

1. 노드 확장: $N$개의 노드를 가진 그래프의 경우, 확장된 그래프는 $2N$개의 노드를 포함합니다. 첫 $N$개의 노드는 현재 공간적 특징 ($X_t$) 을 carry 하며, 후속 $N$개의 노드는 $t-1$까지의 각 노드 역사를 요약한 순환 은닉 상태 ($H_t$) 를 carry 합니다.
2. 엣지 확장:
   • 동시 내 엣지 (Intra-time edges): 원래 엣지 $E_t$가 공간적 노드들을 연결합니다.
   • 교차 시간 엣지 (Cross-time edges): 모든 원래 엣지 $(u, v) \in E_t$에 대해, $u$의 시간적 복사본 (노드 $u+N$) 을 공간적 노드 $v$와 연결하고, 또한 공간적 노드 $u$ 자신과 연결하는 새로운 엣지들이 추가됩니다.
   • 이 구조는 한 노드가 하나의 그래프 컨볼루션 단계 내에서 이웃의 현재 특징과 역사적 요약으로부터 동시에 메시지를 수신할 수 있게 합니다.
3. 메시지 전달: 표준 GNN(예: GCN, GraphSAGE) 이 $\hat{G}_t$에서 작동합니다. 메시지 전달 연산자는 각 이웃에 대해 공간적 메시지 (현재 특징) 와 시간적 메시지 (역사적 궤적) 에 독립적인 가중치를 부여하도록 학습합니다.
4. 출력: 다음 레이어의 표현은 GNN 출력의 첫 $N$개 노드에서 파생됩니다. 순환 상태는 모든 노드 간에 공유되는 LSTM 셀을 통해 업데이트되어 치환 등변성 (permutation equivariance) 을 유지합니다.

이론적 속성

본 논문은 다음을 입증하는 공식적 증명을 제공합니다:

• 엄격한 일반화: SiST-GNN 은 T→S 및 S→T 패러다임 모두의 엄격한 일반화입니다. 특정 게이트 매개변수를 설정함으로써 (예: 교차 시간 엣지를 0 으로 설정), SiST-GNN 은 순차적 패러다임 중 하나를 시뮬레이션할 수 있습니다. 그러나 이는 특히 이웃의 현재 상태와 역사를 구별하여 가중치 부여해야 하는 함수들을 표현할 수 있어, 어느 순차적 패러다임도 표현할 수 없는 함수들을 나타낼 수도 있습니다.
• 메시지 다양성: 단일 레이어에서 SiST-GNN 은 노드당 $2|N(u)| + 1$개의 메시지를 전파합니다 (공간적 이웃, 교차 시간 이웃, 자기 자신). 반면, 순차적 모델은 최대 $|N(u)| + 1$개의 복합 메시지를 전파합니다.
• 복잡도: 계산 오버헤드는 공간 우선 기준 대비 상수 인자입니다. 확장된 그래프는 $2N$개의 노드와 대략 $2|E| + N$개의 엣지를 가지며, LSTM 비용은 표준 시간 기준과 동일합니다.

주요 기여

1. 병목 현상 식별: 저자들은 적응형 메시지 가중치를 방해하는 스냅샷 기반 DGNN 의 공유된 구조적 한계로 공간 및 시간 계산의 엄격한 순서 정렬을 식별했습니다.
2. SiST-GNN 아키텍처: 그들은 순환 셀과 시간적으로 확장된 그래프에 대한 그래프 컨볼루션을 융합하는 스택 가능한 레이어를 구현하여 공간 및 시간 신호 간의 동시 상호작용을 가능하게 했습니다.
3. 광범위한 경험적 검증: 이 모델은 고정 분할 및 라이브 업데이트 프로토콜 하에 9 개의 공개 벤치마크에서 14 개의 기준 (정적 GNN, 시간 우선, 공간 우선, 메타 학습 접근법 포함) 과 비교하여 평가되었습니다.
4. 동적 노드 분류: 아키텍처는 연속 시간 이벤트 스트림을 고정 너비 스냅샷으로 이산화하여 동적 노드 분류에 적응되었으며, 이는 동시 융합 접근법이 이산 시간 및 연속 시간 모델 간의 성능 격차를 해소함을 입증했습니다.

실험 결과

동적 링크 예측

SiST-GNN 은 모든 데이터셋 및 평가 체계에서 최첨단 성능을 달성합니다:

• 고정 분할 설정: 평균 역순위 (MRR) 에서 가장 강력한 이전 방법 (ROLAND-GRU) 보다 **109% 에서 277%**까지 성능이 우수합니다. 가장 큰 향상은 밀집 신뢰 네트워크 (Bitcoin-OTC, Bitcoin-Alpha) 에서 관찰됩니다.
• 라이브 업데이트 설정: MRR 에서 가장 강력한 이전 방법보다 **68% 에서 194%**까지 성능이 우수합니다. 이 설정은 모델이 새로운 정답을 관찰하기 전에 예측해야 하는 온라인 배포를 모방합니다.
• 견고성: 이 모델은 모든 데이터셋에서 단일 GPU 에서 효율적으로 실행되며, AS-733 및 Reddit 과 같은 대규모 장기 데이터셋에서 BPTT 기반 기준이 겪는 메모리 부족 (OOM) 오류를 피합니다.

동적 노드 분류

이 모델은 원래 6 시간 스냅샷으로 이산화된 연속 시간 스트림인 JODIE 벤치마크 (Wikipedia, Reddit, MOOC) 에서 테스트되었습니다:

• 이산 시간 (DTDG) 기준 대비: SiST-GNN 은 선도적인 이산 시간 기준 (예: EvolveGCN, ROLAND) 보다 테스트 AUC 를 **7% 에서 22%**까지 향상시킵니다.
• 연속 시간 (CTDG) 기준 대비: 원시 이벤트 스트림 대신 이산화된 스냅샷에서 작동함에도 불구하고, SiST-GNN 은 네이티브 이벤트 스트림을 소비하는 CTDG 모델 (예: TGN, TGAT) 과 비교 가능한 결과를 달성합니다. 이는 성능 향상이 시간 인터페이스가 아닌 동시 융합 아키텍처에서 비롯됨을 시사합니다.

중요성 및 주장

본 논문은 SiST-GNN 이 동적 그래프 처리 방식에 근본적인 변화를 가져왔다고 주장합니다. 노드의 시간적 상태와 공간적 이웃을 단일 확장 그래프 내의 "이웃"으로 취급함으로써, 모델은 메시지 전달 연산자가 데이터 의존적, 이웃별, 모드별 트레이드오프를 학습할 수 있게 합니다.

• 적응형 가중치 부여: 모델은 현재 특징이 정보 제공이 부족할 때 이웃의 최근 역사에 더 주의를 기울이거나, 시간적 맥락이 낡았을 때 현재 구조에 의존하도록 동적으로 선택할 수 있습니다.
• 일반적 구성: 저자들은 이 "시간적으로 확장된 그래프" 구성이 진화 및 구조 정보를 결합하기 위한 일반적인 기법이며, 평가된 특정 작업을 넘어 적용 가능하다고 주장합니다.
• 한계 및 향후 작업: 저자들은 현재 접근법이 노드 분류를 위해 연속 시간 데이터를 이산화해야 하며, 이는 세밀한 이벤트 순서를 폐기한다고 인정합니다. 향후 작업은 더 큰 그래프로 확장하기 위해 교차 시간 엣지에 대한 희소 마스크를 학습하고, 구성을 네이티브 연속 시간 스트림으로 확장하는 것을 포함할 수 있다고 제안합니다. 또한, 그들의 감독 파이프라인은 최근의 사전 학습 및 프롬프트 튜닝 방법과 직접 비교할 수 없으며, 이는 여전히 열린 방향이라고 지적합니다.