2025-11-14T22:58:11.335175

Revisiting Node Affinity Prediction in Temporal Graphs

Mantri, Feldman, Eliasof et al.
Node affinity prediction is a common task that is widely used in temporal graph learning with applications in social and financial networks, recommender systems, and more. Recent works have addressed this task by adapting state-of-the-art dynamic link property prediction models to node affinity prediction. However, simple heuristics, such as Persistent Forecast or Moving Average, outperform these models. In this work, we analyze the challenges in training current Temporal Graph Neural Networks for node affinity prediction and suggest appropriate solutions. Combining the solutions, we develop NAViS - Node Affinity prediction model using Virtual State, by exploiting the equivalence between heuristics and state space models. While promising, training NAViS is non-trivial. Therefore, we further introduce a novel loss function for node affinity prediction. We evaluate NAViS on TGB and show that it outperforms the state-of-the-art, including heuristics. Our source code is available at https://github.com/orfeld415/NAVIS
academic

時間グラフにおけるノード親和性予測の再検討

基本情報

  • 論文ID: 2510.06940
  • タイトル: Revisiting Node Affinity Prediction in Temporal Graphs
  • 著者: Krishna Sri Ipsit Mantri, Or Feldman, Moshe Eliasof, Chaim Baskin
  • 分類: cs.LG（機械学習）
  • 発表状態: プレプリント。査読中
  • 論文リンク: https://arxiv.org/abs/2510.06940
  • コードリンク: https://github.com/orfeld415/NAVIS

要約

ノード親和性予測は時間グラフ学習における重要なタスクであり、ソーシャルネットワーク、金融ネットワーク、推薦システムなど多くの分野で広く応用されている。最近の研究は最先端の動的リンク予測モデルを適用することでノード親和性予測タスクに対処しているが、持続予測や移動平均などの単純なヒューリスティック手法がこれらの複雑なモデルを上回っている。本論文は、時間グラフニューラルネットワークがノード親和性予測タスクで直面する訓練上の課題を分析し、対応する解決策を提案する。これらの解決策を組み合わせることで、著者らはNAVIS（Node Affinity prediction model using Virtual State）を開発した。このモデルはヒューリスティック手法と状態空間モデルの等価性を活用してノード親和性予測を実現する。

研究背景と動機

問題定義

ノード親和性予測は、将来の時刻において特定のノードと他のすべてのノード間の相互作用強度を予測することを目的としている。これは従来のリンク予測タスクとは異なる。リンク予測は特定のエッジが出現するかどうかに焦点を当てるのに対し、親和性予測はすべての潜在的な隣接ノードに対して完全な順序付けを行う必要があり、このためタスクはより挑戦的であると同時に、実際のアプリケーション要件により適合している。

核心的な問題

  1. 性能のパラドックス：複雑な時間グラフニューラルネットワーク（TGNN）がノード親和性予測タスクで単純なヒューリスティック手法より劣る性能を示す
  2. 表現能力の制限：既存のTGNNは移動平均などの基本的な操作を表現できない
  3. 損失関数の不一致：交差エントロピー損失が順序付けの性質を持つ親和性タスクと適合していない
  4. 情報利用の不十分性：TGNNが全体的な時間動態と長期依存情報を十分に活用していない

研究動機

著者らは理論分析を通じて、単純なヒューリスティック手法が実は線形状態空間モデル（SSM）の特殊ケースであることを発見した。これはより強力なTGNNアーキテクチャの設計に対する理論的基礎を提供する。

核心的な貢献

  1. 理論的貢献：単純なヒューリスティック手法が線形SSMの特殊ケースであることを証明し、この関連性に基づいてヒューリスティック手法を一般化できるTGNNアーキテクチャを設計した
  2. アーキテクチャの革新：仮想グローバル状態と線形状態空間メカニズムを組み合わせたNAVISモデルを提案し、ノード親和性予測問題を効果的に解決する
  3. 損失関数の改善：親和性予測における交差エントロピー損失の不足を分析し、順序付けベースのLambda損失代替案を提案した
  4. 実験検証：TGBベンチマークと複数のデータセットでの検証を通じて、既存手法とヒューリスティック基線を一貫して上回る方法の有効性を実証した

方法の詳細

タスク定義

連続時間動的グラフ（CTDG）が与えられた場合： Gt={(uj,vj,τj,wj)}j=1J(t)G_t = \{(u_j, v_j, \tau_j, w_j)\}_{j=1}^{J(t)}

クエリノード u∈Vu \in V と将来の時刻 t+>tt^+ > t に対して、目標は親和性スコアベクトルを予測することである： s=Fθ(u,Gt,t+)∈R∣V∣s = F_\theta(u, G_t, t^+) \in \mathbb{R}^{|V|}

理論的基礎

定理1（線形SSMが基本的なヒューリスティック手法を一般化）： HH を基本的なヒューリスティック手法の集合（PF、SMA、EMA）とし、Flin-SSMF_{\text{lin-SSM}} を線形SSMで実現可能なマッピングの集合とすると： H⊊Flin-SSMH \subsetneq F_{\text{lin-SSM}}

定理2（RNN/LSTM/GRUの表現制限）： 標準的なRNN、LSTM、またはGRUユニットは最も基本的な持続予測（PF）ヒューリスティック手法を表現できない。つまり、すべての入力シーケンスに対して hi=xih_i = x_i となるパラメータが存在しない。

NAVISモデルアーキテクチャ

NAVISは線形状態空間メカニズムを採用して、各ノードの状態 h∈Rdh \in \mathbb{R}^d と仮想グローバル状態 g∈Rdg \in \mathbb{R}^d を維持する：

zh = σ(Wxh*x + Whh*hi-1 + bh)
hi = zh ⊙ hi-1 + (1-zh) ⊙ x
zs = σ(Wxs*x + Whs*hi + Wgs*g + bs)  
s = zs ⊙ hi + (1-zs) ⊙ x

ここで：

  • xx：前の親和性ベクトル
  • hi−1,hih_{i-1}, h_i：前の状態と更新状態
  • gg：仮想グローバルベクトル
  • ss：予測親和性ベクトル
  • zh,zsz_h, z_s：適応的なゲート制御メカニズム

主要な設計特性

  1. 線形更新メカニズム：EMAとの概念的類似性を保持しながら、実行時の適応的調整を可能にする
  2. 仮想グローバル状態：最近の親和性ベクトルバッファを維持することでグローバルトレンドをキャプチャする
  3. t-Batchメカニズムとの互換性：隣接ノードの隠れ状態に依存せず、効率的なバッチ処理をサポートする
  4. スケーラビリティ：親和性予測パイプラインのスパース化を通じて大規模グラフに対応する

損失関数の設計

問題分析： 定理3（交差エントロピーの順序付けに対する準最適性）：無限に多くの三つ組 (y,s1,s2)(y, s_1, s_2) が存在し、rank(s1)=rank(y)\text{rank}(s_1) = \text{rank}(y) かつ rank(s2)≠rank(y)\text{rank}(s_2) \neq \text{rank}(y) であるが、ℓCE(s1,y)>ℓCE(s2,y)\ell_{CE}(s_1, y) > \ell_{CE}(s_2, y) である。

解決策：Lambda損失を採用する： ℓLambda(s,y)=∑yi>yjlog⁡2(11+e−σ(sπi−sπj))δij∣Aπi−Aπj∣\ell_{\text{Lambda}}(s,y) = \sum_{y_i > y_j} \log_2\left(\frac{1}{1 + e^{-\sigma(s_{\pi_i} - s_{\pi_j})}}\right) \delta_{ij} |A_{\pi_i} - A_{\pi_j}|

ペアワイズマージン正則化と組み合わせる： ℓReg(s,y)=∑yi>yjmax⁡(0,−(sπi−sπj)+Δ)\ell_{\text{Reg}}(s,y) = \sum_{y_i > y_j} \max(0, -(s_{\pi_i} - s_{\pi_j}) + \Delta)

実験設定

データセット

TGBデータセット：

  • tgbn-trade：1986-2016年の国連加盟国間の農業貿易ネットワーク（255ノード、468,245エッジ）
  • tgbn-genre：ユーザー-音楽ジャンル相互作用ネットワーク（1,505ノード、17,858,395エッジ）
  • tgbn-reddit：ユーザー-subreddit相互作用ネットワーク（11,766ノード、27,174,118エッジ）
  • tgbn-token：ウォレット-暗号資産トークン相互作用ネットワーク（61,756ノード、72,936,998エッジ）

変換されたリンク予測データセット：

  • Wikipedia：編集者-記事相互作用ネットワーク
  • Flights：COVID-19期間中の空港ルートネットワーク
  • USLegis：米国上院協力ネットワーク
  • UNVote：国連総会投票ネットワーク

評価指標

  • 主要指標：NDCG@10（正規化割引累積ゲイン）
  • 実験設定：70%-15%-15%の時間分割、50エポック、バッチサイズ200

比較手法

  • ヒューリスティック手法：Persistent Forecast、Moving Average、Historical Average
  • TGNN手法：JODIE、TGAT、CAWN、TCL、GraphMixer、DyGFormer、DyRep、TGN、TGNv2

実験結果

主要な結果

TGBデータセットの性能（NDCG@10）：

  • tgbn-trade: NAVIS 0.863 vs 最良基線TGNv2 0.735 (+17.4%)
  • tgbn-genre: NAVIS 0.520 vs 最良基線TGNv2 0.469 (+10.9%)
  • tgbn-reddit: NAVIS 0.552 vs 最良基線TGNv2 0.507 (+8.9%)
  • tgbn-token: NAVIS 0.444 vs 最良基線TGNv2 0.294 (+51.0%)

変換データセットの性能：

  • Wikipedia: NAVIS 0.573 vs TGNv2 0.433 (+32.3%)
  • Flights: NAVIS 0.499 vs TGNv2 0.299 (+66.9%)
  • USLegis: NAVIS 0.347 vs TGNv2 0.253 (+37.2%)
  • UNVote: NAVIS 0.952 vs TGNv2 0.813 (+17.1%)

アブレーション実験

アブレーション研究は各コンポーネントの重要性を検証した：

  • 線形状態更新 vs GRU：tgbn-tradeで0.863 vs 0.850
  • グローバルベクトルを含める：約1-2パーセントポイントの改善
  • 順序付け損失 vs 交差エントロピー：性能の大幅な改善

主要な発見

  1. ヒューリスティック手法の優位性の確認：単純なヒューリスティック手法が実際に複雑なTGNNより優れている
  2. グローバル情報の重要性：仮想グローバル状態がネットワークレベルのトレンドを効果的にキャプチャする
  3. 損失関数の適合性：順序付け認識損失がノード親和性予測に不可欠である
  4. 一貫した改善：NAVISがすべてのデータセットで一貫した改善を達成している

関連研究

時間グラフの表現能力

従来の研究はWLテストで測定される構造的表現能力に焦点を当てているが、本論文は機能的表現能力、つまり特定の数学的操作を表現する能力に焦点を当てている。

ヒューリスティック手法と状態空間モデル

最近の研究は、単純なヒューリスティック手法が複数のベンチマークで複雑なTGNNより優れていることを発見している。本論文は、ヒューリスティック手法とSSMの形式的等価性を初めて明確に活用してアーキテクチャを設計している。

時間グラフニューラルネットワーク

既存の手法には、メモリベース（TGN、DyRep）および非メモリベース（DyGFormer、GraphMixer）アーキテクチャが含まれるが、いずれもノード親和性予測の特殊な要件に効果的に対処できていない。

結論と考察

主要な結論

  1. ノード親和性予測におけるTGNNの不足は、表現能力の制限と訓練目標の不一致に起因する
  2. 線形状態空間モデルはヒューリスティック手法を一般化するための理論的枠組みを提供する
  3. NAVISは仮想グローバル状態と順序付け認識損失を組み合わせることで、ノード親和性予測問題を効果的に解決する

制限事項

  1. 複雑な依存関係のモデリング：複雑なマルチホップ依存関係のモデリングは依然として困難である
  2. スケーラビリティ：パラメータスケールがノード数に対して線形に増加し、スパース化戦略が必要である
  3. 理論的完全性：すべての関連する問題が完全に解決されていない

今後の方向性

  1. より複雑な時間依存関係のモデリングへの拡張
  2. 大規模グラフのスケーラビリティの向上
  3. 非線形状態空間モデルの可能性の探索

深い評価

長所

  1. 堅実な理論的貢献：厳密な数学的証明を通じてヒューリスティック手法とSSMの関連性を確立している
  2. 深い問題分析：ノード親和性予測におけるTGNNの不足を体系的に分析している
  3. 合理的な方法設計：NAVISの設計には明確な理論的根拠と実用的な考慮がある
  4. 十分な実験：複数のデータセットでの広範な実験が方法の有効性を検証している
  5. 明確な記述：論文の構成は明確で、技術的詳細は正確に説明されている

不足

  1. 革新性の程度：主に既存の理論（SSM）を新しい問題領域に適用している
  2. 実験設定：一部のデータセットの規模が比較的小さく、大規模実験が限定的である
  3. 比較の公平性：基線手法との比較に実装上の差異がある可能性がある
  4. 汎化能力：異なるタイプのグラフでのさらなる検証が必要である

影響力

  1. 学術的価値：時間グラフ学習に新しい理論的視点を提供している
  2. 実用的価値：推薦システムなどの実際のアプリケーションで直接的な価値がある
  3. 再現性：完全なコード実装が提供されている
  4. 啓発性：後続の研究に価値のある洞察を提供している

適用可能なシーン

  1. 推薦システム：ユーザーから物品への親和性予測
  2. ソーシャルネットワーク：ユーザー相互作用強度の予測
  3. 金融ネットワーク：取引関係強度の予測
  4. サプライチェーンネットワーク：協力関係の予測

総合評価：これは質の高い研究論文であり、深い理論分析を通じて既存手法の不足を明らかにし、効果的な解決策を提案している。NAVISモデルは合理的に設計されており、実験結果は説得力があり、時間グラフ学習分野に積極的な貢献をしている。論文の主な価値は、新しい理論的視点と実用的な方法論的枠組みを提供することにある。