技術要約：HOPPER – 線形化グラフシーケンスモデルのための学習可能なホップ抽出

1. 問題提起

グラフニューラルネットワーク（GNN）、特にメッセージパッシングニューラルネットワーク（MPNN）は、長距離依存性のモデリングにおいて根本的な課題に直面しています。標準的なMPNNでは、情報の伝搬距離（情報深度）と適用される非線形変換の数（処理深度）が密結合しています。$r$ホップ離れたノードからの情報を捉えるには、モデルに少なくとも$r$層のレイヤーが必要です。この結合は、最適化の困難さ、オーバースムーシング（ノードのアイデンティティの喪失）、およびオーバースクアッシング（固定次元ベクトルへの大規模な近傍の圧縮）を引き起こし、グローバルなコンテキストを必要とするタスクにおける性能を著しく制限します。

これらの次元を分離するために、線形化グラフシーケンスモデル（LGSM）が提案されました。LGSMは、各ノードの逐次的な伝搬状態を情報深度にわたるシーケンスとして扱うことで、ノードの順序とは独立して、現代的なシーケンスモデル（例：状態空間モデル）がこれらの状態を処理することを可能にします。しかし、既存のLGSMは、固定されたグラフ演算子（正規化された隣接行列の累乗や非バックトラッキングの漸化式など）に依存してこれらのシーケンスを構築しています。これらの固定されたルールは、特定のグラフ構造、ノード特徴、あるいは異なるタスクや情報深度における異なる近傍範囲の有用性に適応することができません。その結果、ダウンストリームのシーケンスモデルは、固定された抽出器によって課される不適切な伝搬戦略を補完することを強いられる可能性があります。

2. 手法：HOPPER

著者らは、LGSMの学習可能なエンドツーエンドの拡張であるHOPPERを導入します。これは、ホップシーケンスが状態空間モデルによって処理される前に、どのようにホップシーケンスが抽出されるかを学習します。HOPPERは、情報深度と処理深度の分離を維持しつつ、4つの主要なコンポーネントを通じて適応性を導入します。

2.1 置換不変グラフサマリー

置換等変性を損なうことなく、入力グラフに伝搬を条件付けるために、HOPPERはまず固定次元のグラフサマリー（$h_{graph}$）を構築します。

• ノード特徴は、1ホップの近傍情報（$H_{nbr} = A_{rw}H$）で拡張されます。
• 学習可能なシードクエリ（$Q_s$）のセットが、これらの拡張されたノード表現にクロスアテンションを行います。
• 得られた潜在表現はベクトル化され、$h_{graph}$を形成します。このサマリーは、ノードの順序に対して不変であり、グラフのサイズに依存しません。

2.2 ホップ条件付き係数生成

ハイパーネットワークは、グローバルなグラフサマリー（$h_{graph}$）と特定のホップ埋め込み（$e_k$）の両方に条件付けられた伝搬係数を生成します。

• ハイパーネットワークは、各ホップにおける構造演算子の線形結合を決定するスカラー（$\alpha_A, \alpha_D, \alpha_I, \beta$）を出力します。
• これにより、伝搬ルールが異なるグラフ間で変化し、情報深度が増すにつれて動的に適応することが可能になります。

2.3 線形構造状態漸化式

抽出器の核となるのは、有限のメモリウィンドウサイズ$M$にわたって構造状態$U^{(k)}$を累積する線形漸化式です。
$$U^{(k)} = \sum_{j=1}^{M} \left( \alpha_A^{(k)}[j]A + \alpha_D^{(k)}[j]D + \alpha_I^{(k)}[j]I \right) U^{(k-j)}$$

• $U^{(0)} = H$（初期特徴量）。
• 漸化式は、正確な多項式構造を維持するために非正規化隣接行列（$A$）と次数行列（$D$）を使用しますが、深いシーケンスにおける数値的安定性のために正規化されたバリアントが使用されます。
• 決定的なのは、固定LGSM抽出器を復元するために必要な代数的性質を保持するため、正規化と非線形性は漸化式の外部に保持されていることです。

2.4 特徴アテンション補正

構造的な漸化式に非線形性を導入することなく、抽出されたシーケンスを豊かにするために、特徴アテンション項が出力状態にのみ適用されます。
$$S^{(k)} = \text{LayerNorm}\left( U^{(k)} + \beta_k F_k U^{(k)} \right)$$
ここで、$F_k$は元のノード特徴から計算されたアテンション行列です。これにより、モデルは特徴内容に基づいて構造的状態を補正または重み付けすることができます。

得られたシーケンス$S$は、各ノードのシーケンスに対して独立して動作するMamba2ベースの状態空間モデル（SSM）ブロックのスタックによって処理されます。

3. 主要な貢献と理論的特性

本論文は、HOPPERに関するいくつかの理論的保証を確立しています。

• 置換等変性: 学習されたグラフサマリーに基づいて伝搬を条件付けているにもかかわらず、HOPPERは置換等変性を維持しています。入力グラフのラベルを付け替えても、抽出されたノードシーケンスに同じ置換が適用されるため、モデルは任意のノード順序に依存しません。
• グラフ適応型多項式構造: 構造状態は、$A$と$D$における有限次数の非可換多項式に対応します。ハイパーネットワークの係数に条件付けると、$k$番目の状態は最大で$k$ホップまでの情報を伝搬します。しかし、係数自体はグラフと特徴に適応するため、伝搬ルールを動的に変更できます。
• 固定抽出器の復元: HOPPERは既存のLGSMの一般化です。特定の係数を設定することで、以下のものを正確に復元できます。
  • 正規化隣接行列による伝搬（$S = A_{sym}$）。
  • 非バックトラッキング伝搬。
  • 安定したチェビシェフ伝搬（非膨張的）。
• 最適な長距離感度: 一様なスペクトル安定性制約（プロパゲーターのノルムが$\le 1$である場合）の下で、本論文は、チェビシェフ伝搬が、標準的な累乗伝搬と比較して、距離$r$にあるノードに対して最大（$2^{r-1}$倍）の初到達感度を達成することを証明しています。
• オーバースムーシングの緩和: 理論的分析によれば、繰り返しの隣接行列伝搬は非定常なスペクトル情報を消失させますが（オーバースムーディング）、チェビシェフシーケンスは、シーケンス深度全体にわたってこの情報の消失しない割合を保持することを示しています。

4. 実験結果

HOPPERは2つのベンチマークで評価されました。

1. ECHO-SYNTH (合成グラフ特性):

   • タスク: グラフ直径（DIAM）、ノード偏心率（ECC）、および単一始点最短経路（SSSP）予測。
   • 結果: HOPPERはECC（MSE: 6.571 vs. LGSM: 13.549）およびSSSP（MSE: 0.021 vs. LGSM: 0.040）において、最先端の性能を達成しました。DIAMについては、最高のLGSMバリアントにわずかに及びませんでしたが、Graph Transformerやリワイアリング手法を含むすべてのベースラインを上回りました。

2. LRIM-16 (物理ベースの長距離依存性):

   • タスク: 長距離相互作用を持つ16x16周期イジング格子におけるノードレベルのエネルギー回帰。
   • 結果: パフォーマンスは構造的メモリウィンドウサイズ$M$によって変動しました。ウィンドウサイズ$M=8$が最良の結果（log10 MSE: -3.505）をもたらし、抽出中に保持される構造的メモリの量が、物理ベースのタスクにおける性能に大きく影響することを示しました。

5. 意義と主張

本論文は、ホップシーケンスの抽出プロセスを学習可能にすることで、HOPPERが長距離グラフ表現学習のための柔軟かつ効果的なアプローチを提供すると主張しています。

• デカップリング: 情報深度と処理深度を正常に分離し、従来のGNNでオーバースムーディングやオーバースクアッシングを引き起こす、蓄積される非線形性なしでの深い伝搬を可能にしました。
• 適応性: 固定されたLGSMとは異なり、HOPPERは特定のグラフ構造、ノード特徴、および情報深度に合わせて伝搬戦略を適応させ、固定された演算子が生成する可能性のある不適切なシーケンスを回避します。
• 理論的根拠: 本フレームワークは経験的に効果的であるだけでなく、確立された伝搬スキームを復元し、長距離感度を最適化しスペクトル情報を保持する、より豊かなクラスのグラフ多項式を提供するという、理論的根拠に基づいています。
• 今後の展望: 著者らは、HOPPERを実際の分子ドメインに拡張することが自然な今後の研究方向であると述べていますが、現在のその領域での成功については主張していません。

要約すると、HOPPERは、学習可能なシーケンス抽出を現代的な状態空間モデルと組み合わせることで、グラフにおける長距離依存性を捉えるための、固定された伝搬ルールよりも優れた代替案となることを示しています。