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

技術概要：HERMIT – スケールフリーインターネットルーティングおよび遅延予測のための時間的双曲グラフ表現学習

問題定義
インターネットの往復時間（RTT）を正確に予測することは、ルーティング最適化、サービス品質（QoS）、トラフィックエンジニアリングにとって不可欠である。しかし、RTT 予測は以下の 3 つの主要な課題に直面している：

1. 重尾分布: RTT データは、サブミリ秒から数秒まで極端な変動を示し、従来の平均二乗誤差（MSE）に基づく回帰モデルが外れ値に支配され、一般的な遅延範囲での性能を劣化させる原因となっている。
2. 動的トポロジー: RTT は、進化中のルーティング経路、輻輳状態、ネットワークトポロジーの変化の影響を受けるため、静的な距離埋め込みや従来の回帰モデルでは捉えにくい。
3. 構造的ミスマッチ: 既存のほとんどの時間的グラフニューラルネットワーク（TGNN）はユークリッド空間で動作する。これは、階層的かつスケールフリーな構造を持つインターネットルーティンググラフには不適切である。ユークリッド埋め込みは、これらのトポロジーを表現するために高次元を必要とするか、幾何学的歪みを伴うが、双曲幾何学は低次元で低歪みによりそのような構造を自然に受け入れることができる。

手法：HERMIT フレームワーク
著者は、リンク予測と RTT 予測を同時に行うように設計されたハイブリッドフレームワークである HERMIT（統合トポロジーによる双曲エッジ認識 RTT モデリング）を提案する。このアーキテクチャは、双曲多様体保存型時間的 GNN と、木ベースのランダムフォレスト回帰器を統合している。

• データ前処理: モデルは、CAIDA IPv4 Ark プロジェクトからの 10 年間のデータセット（2015–2024 年）を利用する。生のトレーサートログは、「完了」したトレースのみを保持するようにクリーニングされ、ネットワークのバックボーンに焦点を当てるために次数上位 5% のノードに剪定され、計算負荷を管理するためにローリング週次戦略（週 3 日）でサンプリングされる。得られたデータは、エッジ特徴として対数変換された平均 RTT、RTT 標準偏差、リンク重みを含む、日次重み付きグラフのシーケンスとして構造化される。
• 双曲時間エンコーダ: HMPTGN バックボーンに基づき、HERMIT は 2 つの主要な強化を導入する：
  1. RTT 認識型エッジ特徴: 微細なリンク状態を特徴づけるために、明示的なエッジ特徴（対数 RTT 平均、標準偏差、重み）が組み込まれる。
  2. 学習可能エッジエンコーダ: 線形変換に続くシグモイド活性化により、3 次元のエッジ特徴をスカラー重みに圧縮する。これはアテンション機構として機能し、メッセージパッシング中にエッジを適応的に重み付けして、重要かつ安定したリンクを強調する。
  3. 多様体保存: エンコーダは、HTGN などのモデルで使用される接空間射影に関連する幾何学的歪みを回避し、ポアンカレ球多様体（曲率 $c=1.0$）上で直接メッセージパッシングを実行する。これには、メビウス加算とポアンカレ線形変換が用いられる。
• 同時予測タスク:
  • リンク予測: モデルはノード埋め込み間のポアンカレ二乗距離を計算し、フェルミ・ディラック活性化関数を使用してリンク存在確率にマッピングする。
  • RTT 予測: 双曲ノード埋め込み（$z_u, z_v$）は、エッジ終点の歴史的 RTT 統計（$f_u, f_v$）と連結される。この結合特徴ベクトルは、重尾を処理するために対数変換および最小 - 最大正規化された RTT 値でトレーニングされる ランダムフォレスト回帰器 に投入され、RTT を予測する。予測値は評価のためにミリ秒スケールに逆変換される。
• トレーニング目的: モデルは、結合損失関数 $L = L_{link} + \lambda L_{RTT}$ を用いて最適化される。ここで、$L_{link}$ は二値交差エントロピー、$L_{RTT}$ は正規化値上の MSE である。重み付けハイパーパラメータ $\lambda$ は 10 に設定される。

主な貢献

1. 再現可能なパイプライン: 生 CAIDA Ark ログを、エッジレベルの RTT 統計を持つ日次重み付きグラフのシーケンスに変換するデータ前処理パイプライン。これは、トレーサート測定で一般的に発生するデータの不整合に対処する。
2. ハイブリッドアーキテクチャ（HERMIT）: 双曲時間的 GNN とランダムフォレスト回帰器を組み合わせた新規フレームワーク。10 年にわたる大規模な実世界データセット上で評価される。
3. 性能向上:
   • RTT 予測: HERMIT は、歴史的統計のみを使用する強力なランダムフォレストベースラインと比較して、RMSE で 6% の改善 を達成する。具体的には、既存リンクで RMSE が 6.4%、新規出現リンクで 2.3% 改善される。
   • リンク予測: 明示的なエッジ特徴と学習可能エッジエンコーダを組み込むことで、HERMIT は先行する双曲 TGNN ベースライン（HMPTGN および HTGN）を上回り、既存リンクおよび新規リンクの両方で AUC および AP スコアが 0.99 以上 となる。
4. スケーラビリティ: このアプローチは、16 次元の双曲埋め込みが階層的ルーティング構造を効率的にエンコードできることを示しており、大規模ネットワークに対するスケーラブルな解決策を提供する。

結果と意義
本論文は、HERMIT が実世界の重尾ネットワーク遅延条件下において、頑健でスケーラブルな RTT 予測ソリューションを提供することを主張している。CAIDA データセット上の実験結果は、以下を示している：

• 重尾の処理: ハイブリッド設計は、重尾サンプルにおける大きな誤差を効果的に軽減し、歴史的統計またはユークリッド埋め込みのみに依存するモデルを上回る。
• 汎化能力: モデルは、以前に未見の接続（新規リンク）に対して強い汎化能力を示しており、学習された双曲時間表現が、新興ネットワーク接続の推論を支援する潜在的な階層構造を捉えていることを示唆している。
• 相乗効果: 双曲エンコーダによって捉えられるマクロレベルのネットワーク組織と、ランダムフォレストによって活用されるミクロレベルの特徴相互作用の組み合わせは、いずれかの単独のアプローチよりも正確で頑健な予測をもたらす。

著者は、RTT 認識型エッジモデリングを双曲時間グラフに組み込むことが、リンクおよび遅延予測の両方を大幅に強化し、遅延を認識したトラフィックエンジニアリングおよびプロアクティブなパフォーマンス監視への実用的な道筋を提供すると結論づけている。