技術的概要：設計段階で解釈可能性を備えた一般化されたティホノフ層を備えたグラフニューラルネットワーク

問題定義

グラフニューラルネットワーク（GNN）は、グラフトポロジー上で特徴を集約することを学習することで、グラフ分類およびノード分類タスクにおいて著しい成功を収めています。しかし、その解釈可能性は依然として重要な課題です。古典的なニューラルネットワークとは異なり、GNN は入力特徴がどのように変換されるかだけでなく、グラフトポロジー自体がどのように利用されているかも説明する必要があります。既存の解釈可能性手法は、忠実性の保証がない事後近似（例：GNNExplainer、勾配サリエンシー）に依存するか、説明抽出器が分類器から分離された二モジュールアーキテクチャに依存しており、後者の場合、分類器は損失を最小化しながら説明を無視することが許容されます。さらに、深層 GNN は、ノード表現の崩壊（オーバースムーシング）や長距離感度の指数関数的減衰（オーバースクワッシング）といった病理に悩まされています。

手法

著者は、設計段階で解釈可能となるように設計されたグラフニューラルネットワーク層であるティホノフ層を提案します。中核的な革新は、グラフ伝播行列 $R$ を、一般化されたグラフティホノフ正則化問題から導出された特定の閉形式解に制限することにあります。

伝播演算子

正規化ラプラシアン $L$ を持つグラフにおいて、入力特徴 $X$ に対する層の出力は次式で与えられます：
$$X^{(k+1)} = \sigma \left( R X^{(k)} W \right)$$
ここで、伝播行列 $R$ は以下のように定義されます：
$$R = (p(L) + Q)^{-1} Q$$
ここで：

• $L$ は正規化グラフラプラシアンです。
• $Q = \text{diag}(q_1, \dots, q_n)$ は、厳密に正のノード重要度スコアの学習可能な対角行列です。
• $p(\cdot)$ は、$\lambda \in [0, 2]$ に対して $0 < p(\lambda) < 1$ を満たす学習可能な多項式です。
• $\sigma$ は点ごとの非線形関数であり、$W$ は重み行列です。

変分解釈

演算子 $R$ は、一般化されたティホノフ問題の一意の閉形式最小解です：
$$R x = \arg \min_{z \in \mathbb{R}^n} \sum_{i \in V} q_i (x_i - z_i)^2 + z^\top p(L) z$$
この定式化は、ノードレベルのデータ忠実性（$q_i$ によって重み付けされる）とトポロジー駆動の正則化（$p(L)$ によって支配される）の間の明示的なトレードオフを表しています。

• 大きな $q_i$：ノード $i$ は自身の特徴に強く依存します。出力 $z_i$ は $x_i$ に近接したままになります。
• 小さな $q_i$：ノード $i$ は、グラフトポロジー（$p$ によって定義される滑らかさまたは特定のスペクトル特性）によって駆動される解を優先し、自身の特徴を棄却します。
• $p(\lambda)$ の形状：トポロジカルな影響の性質を決定します。増加する $p$ は高周波数を罰則化し（同質性/滑らかさを優先）、減少する $p$ は低周波数を罰則化します（異質性を優先）。

アーキテクチャと表現力

高い表現力を維持しつつ解釈可能性を犠牲にしないために、アーキテクチャは関心の分離を採用しています：

1. Q-ネットワーク：グラフ $(G, X)$ を入力とし、ノード重要度スコア $Q$ を出力する専用の、潜在的に深層の GNN（例：ChebNet または ARMA）です。このコンポーネントは複雑な表現学習を処理し、$q_i$ を局所的なグラフ構造と特徴に適応させます。
2. ティホノフ層：伝播 $R$ を適用する単一の透明な層です。隠れた非線形性や複雑なメッセージパッシングステップは含まれておらず、そのパラメータは多項式 $p$ の係数と Q-ネットワークの出力です。
3. ヘッド：最終的な予測のためのグローバルプーリング操作に続く MLP です。

このモデルは、複数の独立した Q-ネットワークと多項式を使用するマルチチャネル拡張をサポートしますが、実験は単一チャネルの場合（$J=1$）に焦点を当てています。

実装の詳細

• 計算：$(p(L) + Q)^{-1}QX$ の計算には線形システムの求解が含まれます。著者は、密行列の逆行列計算の $O(n^3)$ コストを回避するために、対角（ヤコビ）前処理付きの**共役勾配法（PCG）**を使用し、反復回数 $T$ に対して $O(dTKm)$ のスケーラビリティを達成しています。
• 微分：ソルバの計算グラフを保存することを避けるため、著者は陰関数微分を使用しています。これにより、$Q$ と $p$ に関する勾配を計算するために、バックワードパスで追加の PCG 求解が 1 回だけ必要になります。
• 制約：多項式 $p(\lambda)$ は、$0 < p(\lambda) < 1$ を厳密に満たすようにシグモイド活性化を用いたベルンシュタイン多項式でパラメータ化されます。スコア $q_i$ は、対数空間でのクリンプ関数を通じて厳密に正の値にマッピングされます。

主要な貢献と理論的性質

1. 組み込みの解釈可能性：ペア $\{ \{q_i\}_{i \in V}, p(\cdot) \}$ は、直接的で忠実な説明を構成します。大きな $q_i$ は特徴への依存を示し、小さな $q_i$ はトポロジーへの依存を示します。$p$ の形状は、スペクトルバイアス（同質性、異質性、バンドパス）を明らかにします。
2. 構造的結合：著者は（命題 3.6 で）写像 $Q \mapsto R$ が単射であることを証明しています。事後手法とは異なり、説明（$Q$）を変更することは、伝播演算子（$R$）を変更することを必然的に伴うため、説明が計算に対して忠実であることを保証します。
3. 表現力：均一な場合、この層は連続スペクトルフィルタの空間において稠密であることが示されています。異質な $Q$ を用いる場合、定常性を破ることで（命題 3.3）、従来のスペクトルフィルタを超えて表現力を厳密に拡張します。
4. GNN 病理の緩和：
   • オーバースムーシング：単一層の使用と $p(L) + Q$ の可逆性によって回避されます。ノードの崩壊は、モデルが意図的にすべての $q_i \to 0$ を駆動する場合にのみ発生します。
   • オーバースクワッシング：長距離感度 $|R_{ij}|$ の減衰率は、学習された $Q$ に依存するシステムの条件数 $\kappa$ によって支配されます。モデルは、必要な場所で長距離感度を高めるために $\kappa$ を低下させる（特定の $q_i$ を低下させる）ことを学習でき、これにより局所的な精度とグローバルな到達範囲の間のトレードオフを効果的に実現します。

実験結果

このモデルは、合成および標準的なベンチマークで評価され、性能と解釈可能性の両方を示しました：

• 制御された合成タスク：
  • Colors-3：このタスクはノード特徴のみに依存します。モデルは全域で大きな $q_i$ を学習し、トポロジーを事実上無視して MLP のように振る舞い、特徴が予測を駆動していることを正しく識別しました。
  • Clique Distance：純粋に構造的なタスクです。モデルはパスノードに対して小さな $q_i$ を（距離を感知するためにトポロジーに依存）、クラックノード（アンカー）に対して大きな $q_i$ を学習し、100% の精度を達成しました。
  • Triangles：三角形を検出する構造的タスクです。モデルは一般的に小さな $q_i$ を割り当てましたが、三角形の頂点にはより大きな $q_i$ を割り当て、教師なしでモチーフを特定しました。
• CSBM（文脈的確率的ブロックモデル）：モデルは、回復のための理論的位相遷移閾値を正常に追跡しました。学習された $q_i$ の値は、特徴優位（大きな $q_i$）からトポロジー優位（小さな $q_i$）の領域へ滑らかに遷移し、混合領域における信号の源を正しく識別しました。
• ECHO-diam（長距離伝播）：グラフ直径回帰タスクにおいて、モデルは平均絶対誤差（MAE）1.17 を達成し、深層 GNN ベースライン（約 1.6）を上回り、Transformer の性能（1.05）に近づきました。説明により、モデルが周辺ノード（端点）に大きな $q_i$ を、内部ノードに小さな $q_i$ を割り当て、アンカーされた端点と滑らかにされた内部の対比を利用して直径を推定していることが明らかになりました。

意義と主張

本論文は、ティホノフ層が、事後に説明を回復するのではなく、層を自己説明可能に設計することにより、GNN の解釈可能性に対する新たなアプローチを提供すると主張しています。

• 忠実性：説明はモデルそのものです。分離された部分グラフや近似はありません。
• 粒度：これは、二値の部分グラフ選択ではなく、連続的で空間的に解像された回答（段階的な $q_i$ 値）を提供します。
• 性能：このモデルは、さまざまなタスクにおいて不透明なベースライン（GIN、GAT、Transformer など）と同等かそれ以上の性能を発揮し、タスクがどのように解決されるか（例：特徴ベースの推論とトポロジーベースの推論の区別）についての洞察を提供します。
• 限界：著者は、いくつかの説明は人間にとって解釈が複雑であり、PCG の計算コストは長距離相互作用を必要とするタスクでは高くなる可能性があると認めています（ただし、近似のための将来の方向性としてランダム数値線形代数を提案しています）。

この研究は、GNN 層を特定の変分形式に制限することで、複雑で非定常なグラフフィルタを学習する能力を犠牲にすることなく解釈可能性を獲得することが可能であることを確立しています。