Temporal Hyperbolic Graph Representation Learning for Scale-Free Internet Routing and Delay Prediction

기술 요약: HERMIT – 확장성 있는 인터넷 라우팅 및 지연 예측을 위한 시간적 쌍곡선 그래프 표현 학습

문제 정의
인터넷 왕복 시간 (RTT) 을 정확하게 예측하는 것은 라우팅 최적화, 서비스 품질 (QoS), 트래픽 엔지니어링에 필수적입니다. 그러나 RTT 예측은 다음과 같은 세 가지 주요 과제를 직면하고 있습니다:

1. 무거운 꼬리 분포: RTT 데이터는 밀리초 미만에서 수 초에 이르기까지 극심한 변이성을 보이며, 이로 인해 전통적인 평균 제곱 오차 (MSE) 기반 회귀 모델은 이상치에 지배를 받아 일반적인 지연 범위에서의 성능이 저하됩니다.
2. 동적 토폴로지: RTT 는 진화하는 라우팅 경로, 혼잡 상태, 네트워크 토폴로지 변화의 영향을 받으며, 이는 정적 거리 임베딩이나 전통적인 회귀 모델로 포착하기 어렵습니다.
3. 구조적 불일치: 대부분의 기존 시간적 그래프 신경망 (TGNN) 은 유클리드 공간에서 작동합니다. 이는 계층적이고 스케일 프리 (scale-free) 구조를 지닌 인터넷 라우팅 그래프에 적합하지 않습니다. 유클리드 임베딩은 이러한 토폴로지를 표현하기 위해 고차원이 필요하거나 기하학적 왜곡을 초래하는 반면, 쌍곡선 기하학은 저차원에서 낮은 왜곡으로 이러한 구조를 자연스럽게 수용합니다.

방법론: HERMIT 프레임워크
저자들은 HERMIT(통합 토폴로지를 통한 쌍곡선 엣지 인식 RTT 모델링) 을 제안합니다. 이는 링크 예측과 RTT 예측을 공동으로 수행하도록 설계된 하이브리드 프레임워크입니다. 이 아키텍처는 쌍곡선 다양체 보존 시간적 GNN 과 트리 기반 랜덤 포레스트 회귀 모델을 통합합니다.

• 데이터 전처리: 모델은 CAIDA IPv4 Ark 프로젝트의 10 년 데이터셋 (2015–2024) 을 활용합니다. 원시 traceroute 로그는 "완료"된 추적만 유지하도록 정제되고, 네트워크 백본에 집중하기 위해 차수 (degree) 기준 상위 5% 노드로 가지치기되며, 계산 부하를 관리하기 위해 주 단위 (주 3 일) 롤링 전략으로 샘플링됩니다. 결과 데이터는 로그 변환된 평균 RTT, RTT 표준 편차, 링크 가중치를 포함하는 엣지 특징을 가진 일별 가중 그래프 시퀀스로 구조화됩니다.
• 쌍곡선 시간적 인코더: HMPTGN 백본을 기반으로 HERMIT 은 두 가지 주요 개선을 도입합니다:
  1. RTT 인식 엣지 특징: 미세한 링크 상태를 특성화하기 위해 명시적 엣지 특징 (로그 변환된 RTT 평균, 표준 편차, 가중치) 이 통합됩니다.
  2. 학습 가능한 엣지 인코더: 선형 변환을 followed by 시그모이드 활성화 함수가 3 차원 엣지 특징을 스칼라 가중치로 압축합니다. 이는 메시지 전달 중 중요한 링크와 안정적인 링크를 강조하기 위해 적응적으로 엣지에 가중치를 부여하는 어텐션 메커니즘 역할을 합니다.
  3. 다양체 보존: 인코더는 HTGN 과 같은 모델에서 사용되는 접선 공간 투영과 관련된 기하학적 왜곡을 피하기 위해, Möbius 덧셈과 Poincaré 선형 변환을 사용하여 Poincaré 볼 다양체 (곡률 $c=1.0$) 에서 직접 메시지를 전달합니다.
• 공동 예측 작업:
  • 링크 예측: 모델은 노드 임베딩 간의 Poincaré 제곱 거리를 계산하고, 페르미 - 디랙 활성화 함수를 사용하여 링크 존재 확률로 매핑합니다.
  • RTT 예측: 쌍곡선 노드 임베딩 ($z_u, z_v$) 은 엣지 종점의 역사적 RTT 통계 ($f_u, f_v$) 와 연결됩니다. 이 결합된 특징 벡터는 무거운 꼬리를 처리하기 위해 로그 변환 및 최소 - 최대 정규화된 RTT 값으로 훈련되며, 예측은 평가 시 밀리초 스케일로 역변환되는 랜덤 포레스트 회귀 모델에 입력됩니다.
• 훈련 목적 함수: 모델은 $L = L_{link} + \lambda L_{RTT}$로 정의된 결합 손실 함수로 최적화되며, 여기서 $L_{link}$는 이진 교차 엔트로피이고 $L_{RTT}$는 정규화된 값에 대한 MSE 입니다. 가중치 하이퍼파라미터 $\lambda$는 10 으로 설정됩니다.

주요 기여

1. 재현 가능한 파이프라인: traceroute 측정에서 흔히 발생하는 데이터 불일치를 해결하는 데이터 전처리 파이프라인으로, 원시 CAIDA Ark 로그를 엣지 수준 RTT 통계가 포함된 일별 가중 그래프 시퀀스로 변환합니다.
2. 하이브리드 아키텍처 (HERMIT): 쌍곡선 시간적 GNN 과 랜덤 포레스트 회귀 모델을 결합한 새로운 프레임워크입니다. 이는 10 년에 걸친 대규모 실세계 데이터셋에서 평가되었습니다.
3. 성능 개선:
   • RTT 예측: HERMIT 은 역사적 통계만 사용하는 강력한 랜덤 포레스트 기준선 대비 RMSE 에서 6% 향상을 달성합니다. 구체적으로, 기존 링크에서는 6.4%, 새로 나타나는 링크에서는 **2.3%**의 RMSE 개선을 보입니다.
   • 링크 예측: 명시적 엣지 특징과 학습 가능한 엣지 인코더를 통합함으로써 HERMIT 은 기존 쌍곡선 TGNN 기준선 (HMPTGN 및 HTGN) 을 능가하여 기존 링크와 새 링크 모두에서 0.99 이상의 AUC 및 AP 점수를 달성합니다.
4. 확장성: 이 접근법은 16 차원 쌍곡선 임베딩이 계층적 라우팅 구조를 효율적으로 인코딩할 수 있음을 보여주며, 대규모 네트워크를 위한 확장 가능한 솔루션을 제공합니다.

결과 및 의의
본 논문은 HERMIT 이 실세계의 무거운 꼬리 네트워크 지연 조건 하에서 RTT 예측을 위한 강력하고 확장 가능한 솔루션을 제공한다고 주장합니다. CAIDA 데이터셋에 대한 실험 결과는 다음과 같습니다:

• 무거운 꼬리 처리: 하이브리드 설계는 무거운 꼬리 샘플에서의 큰 오차를 효과적으로 완화하여 역사적 통계나 유클리드 임베딩에만 의존하는 모델보다 우수한 성능을 보입니다.
• 일반화: 모델은 이전에 보지 못한 연결 (새 링크) 에 대해 강력한 일반화 능력을 보여주며, 학습된 쌍곡선 시간적 표현이 새로운 네트워크 연결을 추론하는 데 도움이 되는 잠재적 계층 구조를 포착함을 시사합니다.
• 상호 보완성: 쌍곡선 인코더가 포착하는 매크로 수준의 네트워크 조직과 랜덤 포레스트가 활용하는 마이크로 수준의 특징 상호작용의 결합은 어느 단일 접근법보다 더 정확하고 강력한 예측을 산출합니다.

저자들은 RTT 인식 엣지 모델링을 쌍곡선 시간적 그래프에 통합함으로써 링크 및 지연 예측을 모두 크게 향상시킬 수 있으며, 지연 인식 트래픽 엔지니어링 및 사전 예방적 성능 모니터링을 위한 실용적인 경로를 제시한다고 결론지었습니다.