技術的要約：時系列グラフニューラルネットワークのための時間的モチーフ・シグネチャ

問題提起

現実世界の時間的な相互作用ストリーム（例：社会的コミュニケーション、金融取引、オンラインレビュー）には、反復、相互性、スター多様性、および三者間のフローといった、短期間のモチーフパターンの中に予測的な構造が含まれています。現代の時系列グラフニューラルネットワーク（TGNN）は、理論的には時系列のあらゆる関数を抽出できる表現力豊かなシーケンスモデルですが、その帰納バイアスや限られた学習予算により、特定の短期間の構造的規則性を捉えきれないことがあります。これらの規則性は、分析的に計算することが容易である一方で、ダウンストリームタスクにおいて極めて重要です。本論文は、標準的なTGNNが学習している内容と、時系列の特徴を特徴づける明示的な短期間統計量との間のギャップに対処し、原理的かつアーキテクチャに依存しない拡張によって、この残留するギャップを埋めることができるかという問いに取り組んでいます。

手法

1. 実証的診断とシグネチャの特定

著者らはまず、多様な13種類の実データおよび合成時系列データセット（MOOC、Bitcoin Alpha/OTC、TGBベンチマークを含む）を用いて、候補ごとの過去ウィンドウにおけるモチーフカウントを分析しました。彼らは、モチーフの活動が以下の3つのスケール安定な軸に沿って一貫して整理されていることを特定しました。

• A1 (二者間の近接性/相互性): 候補となるペア $(u, v)$ 間の直接的な相互作用のタイミングと頻度を捉えます。
• A2 (スター多様性): 時間窓内における $u$ または $v$ と相互作用する隣接ノードの多様性を測定します（例：ある学生がやり取りした異なるアイテムの数）。
• A3 (三者間のフロー): $u$ と $v$ を橋渡しする第三者を介した相互作用のフローを捉えます（例：共通の隣接ノード）。

2. モチーフ特徴マップ $h(u, v, t)$

これらの軸に基づき、著者らはコンパクトな13次元の候補ローカル・モチーフ特徴マップ $h(u, v, t) \in \mathbb{R}^{13}$ を設計しました。主な設計上の制約は以下の通りです。

• リーク安全性: 特徴量は過去のウィンドウ $W_{t}^{past}(\Delta) = \{i : t - \Delta \le t_i < t\}$ から厳密に計算され、候補の表現に将来の情報が漏洩しないことを保証します。
• 固定次元: 13個の特徴量は、アーキテクチャの変更なしに、学習可能な線形埋め込み行列 $M$ を介して任意の静的または時系列エンコーダに結合されます。
• サブファミリー: 13個の座標は、3つの軸に対応しています。
  • A1 (5つの特徴): $u \to v$ および $v \to u$ のイベント数、ペアリングされたイベント、バースト性、および最後の相互作用イベントからの正規化された経過時間。
  • A2 (4つの特徴): ウィンドウ内における異なる隣接集合（$N_{u}^{out}, N_{u}^{in}, N_{v}^{out}, N_{v}^{in}$）のサイズ。ハブを扱うために上限が設定されています。
  • A3 (4つの特徴): 隣接集合間の有向クロスウェッジおよびバイウェッジの積集合のサイズ。
• 正規化: ヘビーテイルなカウント座標には、比較可能性を確保するために $\log_{10}(1+x)$ 変形が施されます。

3. 理論的配置 (Temporal Weisfeiler-Leman)

本論文は、標準的な時系列メッセージパッシングGNN（MP-GNN）に対する理論的な境界を確立しています。一般的なエッジスコアリングの抽象化の下で、これらのモデルは、候補アンカー付きの時間的Weisfeiler-Leman階層（temporal-1-WL）の第1レベルに制限されます。

• 著者らは、時間的1-WLでは区別できない（同じ色に収束してしまう）アンカー付きの時間的ストリーム（例：$C_6$ サイクルと2つの離れた三角形 $2K_3$）が存在する一方で、モチーフ特徴マップ $h$ はこれらを完全に区別できることを証明しました。
• これにより、モチーフによる拡張が標準的な時系列MP-GNNの表現力を厳密に上回り、WLのボトルネックを打破する「証人（witness）」として機能することが示されました。

主な貢献

1. 診断 (セクション4): 本論文は、モチーフカウントが、モチーフの軸（A1, A2, A3）に沿って時系列を整理していることを明らかにしています。これらのパー・データセット・シグネチャは、モチーフ拡張が最大の性能向上をもたらす場所を予測する診断ツールとなります。
2. 時間的表現力 (セクション6): 著者らは、標準的な時系列MP-GNNを、候補アンカー付きの時間的WL階層内に配置する理論的根拠を提供しています。彼らは、モチーフ特徴が、時間的1-WLが収束させてしまう候補を区別する具体的な一対のストリームを示すことで、この拡張がモデルをこの階層の第1レベル以上に引き上げることを実証しました。
3. 実証的性能 (セクション7): モチーフ拡張が、強力なTGNNベースラインと比較して、ヘテロジニアスなタスク（TGBリンク特性予測、エッジ分類、およびグラフレベル分類）において一貫して性能を向上させることを示しています。その利得は解釈可能です。すなわち、ベースラインが短期間の構造を捉えきれない場合に最大となり（例：MOOC）、ベースラインがすでに該当する構造を捉えている場合には無視できる程度になります。

実験結果

フレームワークは以下で評価されました。

• TGB リンク特性予測: 5つのベースライン（TPNet, HyperEvent, DyGFormer, TNCN, TGN）と3つのデータセット（Wiki, Review, Coin）を用いて評価。
  • 結果: モチーフ拡張は、評価されたすべてのベースライン-データセットのペアにおいて性能を向上させました。最も顕著な利得は、tgbl-review-v2 データセットにおける DyGFormer で観察され、平均逆順位（MRR）が 0.224 から 0.413 に増加しました。
  • 観察: tgbl-coin-v2 における TPNet のようなベースラインでは、利得がゼロの標準偏差内であり、これはそれらのベースラインがすでにその特定のデータセットに関する関連する短期間構造を捉えていることと一致しています。
• エッジ分類:
  • MOOC: 学生のドロップアウトを予測するバイナリ分類タスク。バニラな GraphSAGE エンコーダは PR-AUC 0.0164 を達成しました。4つの特徴を持つスターカウント・サブセット（A2）を追加すると 0.1430 に上昇し、完全な13特徴マップは 0.1659 に達しました。
  • Bitcoin Alpha/OTC: トラスト分類タスクにおいて、緩やかではあるが一貫した改善を示しました（例：Alpha における SAGE PR-AUC が 0.9282 から 0.9667 へ向上）。
• グラフレベル分類: 合成時系列生成器において、モチーフ拡張は精度を大幅に向上させました。特に、GAT が崩壊した 16.7%（多数派クラスの予測）から、アーキテクチャを変更することなく 94.0% まで引き上げたことは注目に値します。

アブレーションとコントロール:

• Leave-one-out 分析により、単一の座標が画一的に冗長であることはなく、データセットごとに異なる軸に依存していることが確認されました（例：MOOC は A2 スター多様性に大きく依存し、Bitcoin Alpha は A1 相互性に依存しています）。
• コントロール実験により、「追加容量」が利得の源ではないことが確認されました（ランダムな特徴量は利得を再現しませんでした）。また、この利得が単なる単純なノード活動カウントのプロキシではないことも確認されました。

意義と主張

本論文は、時間的モチーフ・シグネチャが、短期間の構造的規則性を TGNN に注入するための、コンパクトで解釈可能、かつアーキテクチャに依存しない手法であることを主張しています。

• 予測力: A1/A2/A3 軸に沿ったパー・データセット・シグネチャは、拡張が最も有益となる場所を予測するための診断ツールとして機能します。
• 理論的根拠: 拡張を時間的WL階層の中に配置することで、本論文はなぜ標準的な TGNN が特定のタスクで失敗するのか（それらは時間的1-WLに制限されているため）、そしてどのようにしてこの拡張がその制限を克服するのかを明確にしています。
• 実用的有用性: この手法は、基礎となるエンコーダ・アーキテクチャを変更する必要がなく、事前計算された特徴ベクトルを結合するだけで済むため、既存のパイプラインへの導入が容易です。

著者らは、ウィンドウ半径 $\Delta$ は敏感なハイパーパラメータであること、および、三者間のフローが無視できるほど疎なストリームにおいては、拡張がより低次元のサブスペースに縮小し、それに伴い利得も小さくなることを指摘し、控えめな立場をとっています。本フレームワークは、バニラの TGNN がエッジスコアラーに提示することに失敗しがちな、特定の構造的信号を露出させるための原理的な方法として提示されています。