技術的概要：フルスペクトルグラフニューラルネットワーク：表現力とスケーラビリティ

問題定義

標準的なスペクトルグラフニューラルネットワーク（GNN）は、グラフ伝播をラプラシアンフィルタリングとしてパラメータ化します。スペクトル GNN がノード信号を普遍的に近似できることは確立されていますが、非同型グラフを区別する表現力は、1 次元のワイゼフェラー・レマン（1-WL）テストによって厳密に制限されています。この限界は、高次信号を普遍的に近似できないという能力の欠如と対応しています。さらに、古典的なスペクトル GNN は対角スペクトルフィルタ（単一の固有値の関数）に依存しており、複雑な相互作用をモデル化する能力を制限しています。特に、隣接ノードが異なるラベルを持つことが多い異質グラフにおいてその制約が顕著です。1-WL を超える既存のアプローチは、通常、空間ドメインでメッセージパッシングを高次ドメイン（例えばノードペア）へ持ち上げることを伴いますが、それに対応するスケーラブルなスペクトルフレームワークは欠けていました。

手法

著者は、古典的なスペクトル GNN の 2 次一般化であるFSPECGNN（フルスペクトルグラフニューラルネットワーク）を提案します。この手法は、以下の 2 つの中核的な理論的進展に基づいています：

1. 信号ドメインの持ち上げ：ノード信号 $x \in \mathbb{R}^V$ をフィルタリングする代わりに、FSPECGNN はノードペア信号 $\varepsilon \in \mathbb{R}^{V \times V}$ 上で動作します。これにより、信号はノードドメインからノードペアドメインへ持ち上げられます。
2. 二変数スペクトルフィルタリング：古典的なスペクトルフィルタリングは、固有値に対して単変数関数 $g(\lambda)$ を適用します。FSPECGNN はこれを、固有値のペアに対する二変数フィルタ $g(\lambda_i, \lambda_j)$ に拡張します。
   • フルスペクトル畳み込みは以下のように定義されます：
     $$G_\lambda *_{\mathcal{G}} \varepsilon = \sum_{i,j} g(\lambda_i, \lambda_j) u_i u_i^\top \varepsilon u_j u_j^\top$$
     ここで、$L = U\Lambda U^\top$ はグラフラプラシアンの固有値分解です。
   • この定式化は古典的なスペクトル GNN を一般化しており、古典的なスペクトル GNN は FSPECGNN の対角特殊ケース（フィルタを対角 $g(\lambda_i, \lambda_i)$ に制限することで復元される）であることが示されています。

スケーラビリティ実装：
ノードペアドメイン（$n^2 \times n^2$）での直接計算は、大規模グラフでは処理不可能です。これを解決するため、著者は低ランクテンソル分解を用いたスケーラブルな実装を提案します：

• 二変数多項式フィルタは、分離可能な単変数多項式の和として近似されます：$P(L \otimes I, I \otimes L) \approx \sum_{r=1}^S f_r(L) \otimes h_r(L)$。
• 性質 $(A \otimes B)\text{vec}(\varepsilon) = \text{vec}(B\varepsilon A^\top)$ を用いることで、畳み込みは $h(L) \varepsilon f(L)^\top$ として計算され、$n^2$ 次元の演算子の明示的な構築を回避します。
• 初期ノードペア信号 $\varepsilon$ は、単位行列と GAT レイヤーの学習可能な組み合わせ（$I + \alpha \text{GAT}$）を通じて構築され、特徴に依存する非対角混合を誘発します。

主要な貢献

1. 理論的表現力：

   • 普遍近似：著者は、線形 FSPECGNN が 1 次元ノードペア信号を普遍的に近似できることを証明しました（定理 3.4）。これにより、スペクトル GNN の普遍性がノードからノードペアへ拡張されました。
   • 1-WL 優越性：本論文は、FSPECGNN が 1-WL の上限を超え得ることを確立しています。具体的には、単純なスペクトルと非ゼロのスペクトル係数という条件下で、FSPECGNN はローカル 2-GNN（空間 2 次モデル）と同等の表現力を達成し、特定の二変数多項式を用いることでさらにそれを上回る可能性があります（定理 3.8）。

2. 異質グラフ学習：

   • 著者は、異質グラフにおけるクラス分離のための最適畳み込みを分析しました。彼らは、クラス間接続を抑制するために、スペクトル基底において非対角成分が必要であることを証明しました（定理 4.1）。
   • 根本的な限界が証明されました：古典的なスペクトル畳み込み（対角フィルタ）は、単位行列のスカラー倍に退化しない限り、この最適演算子を実現できません（定理 4.2）。FSPECGNN は、非対角スペクトル相互作用を許可することで、この最適演算子を実現できます。

3. スケーラビリティ：

   • 提案された低ランク近似は、計算複雑性を既存の多項式スペクトル GNN と同程度の $O(Kmd)$に削減し、固有値分解の$O(n^3)$コストと明示的なノードペア操作の$O(n^4)$ メモリを回避します。

実験結果

本論文は、FSPECGNN を 3 つのタスクで評価しました：

1. 異質ノード分類：

   • 8 つのデータセット（Texas, Wisconsin, Squirrel, Roman Empire など）でテストされました。
   • FSPECGNN の変種（チェビシェフ、ChebNetII、ベルンシュタイン基底を使用）は、最先端のスペクトルベースライン（ChebNet, GPRGNN, BernNet など）を一貫して上回りました。
   • 除去実験により、非対角相互作用や「in-filter」を除去すると性能が大幅に低下することが確認され、クロス固有空間結合のモデル化の必要性が実証されました。

2. 部分構造カウント（表現力検証）：

   • ホモモルフィズムおよび（弦）サイクルカウントのベンチマークで評価されました。
   • FSPECGNN は、ローカル 2-GNNおよびローカル 2-FGNNと同等の性能を達成し、空間 2 次モデルの表現力と一致するという理論的予測を確認しました。
   • これらのタスクにおいて、スペクトル不変 GNN や標準的な MPNN を大幅に上回る性能を示しました。

3. 効率性：

   • FSPECGNN は、空間 2 次ベースライン（ローカル 2-GNN, ローカル 2-FGNN, サブグラフ GNN）と比較して、実行時間が大幅に短縮（約 5 倍高速）され、ピーク GPU メモリも低く抑えられました。

意義と主張

本論文は、FSPECGNN が空間高次 GNN に対する原理的なスペクトル対応物を提供すると主張しています。その主な意義は、スペクトル手法と高次表現力の間のギャップを埋める点にあります：

• 異質性は本質的に 2 次現象であり、古典的なスペクトル GNN が構造的に欠いている非対角スペクトル成分を必要とすることを示しています。
• 明示的な高次空間手法の過大な計算コストを伴わずに、2 次モデリングの理論的利点（1-WL の超越、ペア上の普遍近似）を保持するスケーラブルなアーキテクチャを提供します。
• 対角スペクトルフィルタの根本的な限界を特定し、それを克服するための一般化可能なフレームワーク（$k$ 次へ拡張可能）を提案しています。