技術概要：TreeX - ルールからグラフへの読み出しによるモデルレベルの GNN 説明

問題定義

グラフニューラルネットワーク（GNN）は強力な予測性能を達成する一方で、その意思決定ロジックを理解することは依然として困難です。既存のアプローチは主にインスタンスレベルの説明に焦点を当て、単一の予測に責任がある特定のノードや部分グラフを特定することに留まっています。しかし、局所的な説明は、証拠がデータセット全体で体系的に使用されているかどうか、モデルが誤ったショートカットに依存しているかどうか、あるいは複数の概念がどのようにクラスレベルの決定境界を共同で定義しているかを示すことができません。

現在のモデルレベルの説明器は、通常、特定のクラスに関連するグラフパターンや記号ルールを特定しようとします。これらの手法の決定的な欠点は、ルールを特定のクラスを記述する事後的な記述子として扱うのではなく、機能的な計算単位として扱わない点にあります。これらは、複数のルールがどのように共同して GNN の最終的な決定を生み出すか、あるいはモデルの生予測ロジットを再構築するかを説明するものではありません。その結果、これらにはテスト時にルールレベルの寄与分析を行う能力や、競合するクラスの抑制を説明する能力が欠けています。

手法：TreeX

著者らは、説明の対象をクラスごとのルール抽出からルールベースのロジット再構築へと移行させる、新しいモデルレベルの GNN 説明フレームワークTreeXを提案します。TreeX は、事前学習済みの GNN の読み出しインターフェースに介入し、メッセージパッシング層と分類器ヘッドを固定したまま、元のノードからグラフへの読み出しを、重み付けされたルールからグラフへの読み出しに置き換えます。

手法は 4 つの主要な段階で構成されます：

1. 部分木に着想を得た概念マイニング

グローバルなルールをローカルなインスタンスに根ざさせるため、TreeX は GNN の隠れ状態から部分グラフ概念をマイニングします：

• ローカルマイニング: グラフ内のノード埋め込みをクラスタリングします。各クラスターは、そのメンバーノードの$l$-ホップ受容野（部分木）を集約することで、サポート部分グラフに変換されます。これにより、概念はノイズではなく構造的に安定した証拠へと偏ります。
• グローバルマイニング: ローカル概念の埋め込みを再度クラスタリングして、グローバル概念バンクを形成します。代表部分グラフは、形状と次数シグネチャに基づく 2 段階の辞書式多数決フィルタ、および重心距離による同点決着によって選択されます。
• 理論的正当性: 本論文は、最大限に強力な MPNN（GIN など）において、$l$-層目のノード埋め込みは完全な$l$-ホップ部分木の「完全な根付き木表現」であると主張し、部分構造を表すためにノード埋め込みを使用することを正当化しています。

2. ニューロシンボリックルール学習

TreeX は、CNF（合取標準形）構造、具体的にはOR-of-CNF緩和を用いて、グローバルな部分グラフ概念上で記号ルールを学習します：

• クラスごとの発見: ルールは、各対象クラスに対して 1 対残りの方法で最初に学習されます。正のリテラル（$P[k]$）と負のリテラル（$\neg P[k]$）は、グローバル概念の識別力に基づいてインスタンス化されます。
• 微分可能な論理: 階層的な微分可能な論理パラメータ化が使用されます。節はゲーデル t-コノルム（ゲート付きリテラルの最大値）によって満たされ、ルールは節間での積スタイルのソフト AND によって形成されます。最終的なクラス予測は、候補ルール上の確率的和（ノイズ入り OR）を使用します。
• マージ: クラス固有のルール候補は、統一された共有ルールバンクにマージされます。この 2 段階設計により、クラスごとの識別ルールの発見を確保しつつ、多クラス再構築のための共有構造を維持します。

3. ルールからグラフへの読み出し

中核的な革新は、読み出し層の再構成にあります：

• ルール埋め込み: ルール埋め込みは、その構成リテラルの埋め込み（ゲート活性化で重み付け）を集約することで計算されます。負のリテラルは、対応する正のリテラルの否定された埋め込みとして表現されます。
• ロジット再構築: 活性化されたルールは、学習されたグローバル重みベクトル$w$によって重み付けされます。活性化されたルール埋め込みの重み付き組み合わせは、ベース GNN の固定された分類器ヘッドを通過し、生多クラスロジット（$\hat{o}_G$）を再構築します。
• 目的: モデルは、再構築されたロジットと元の GNN の生ロジットとの間の平均二乗誤差（MSE）を最小化するように訓練されます。

4. テスト時のグラウンディングと分析

テスト時には、TreeX は未見のグラフを共有概念空間に投影し、固定されたルールを評価して、インスタンス固有の説明を生成します。これにより以下が可能になります：

• グラウンディング: 満たされたリテラルを、具体的なローカル部分グラフ証拠（正のリテラルの場合）または概念の欠如（負のリテラルの場合）にマッピングします。
• アブレーション: 各ルールの重みをゼロにして再構築されたロジットの変化（$\Delta_{g,r}$）を観察することで、各ルールの寄与を測定します。

主要な貢献

1. 新しい説明対象: モデルレベルの GNN 説明をルールベースのロジット再構築として定式化し、パターンとラベルの単純な関連付けを超えて、生予測ロジットの生成を説明する方向へ移行させました。
2. シンボリック読み出しインターフェース: 根ざした論理ルールを計算単位として機能させるルールからグラフへの読み出しを導入しました。活性化されたルール埋め込みは集約され、固定された分類器を通過して多クラスロジットを再構築します。
3. グラウンディングされ、構成的なルール構築: 部分木に着想を得た部分グラフ概念をマイニングし、連続的な埋め込みと具体的な証拠を生成します。また、OR-of-CNF ルールを学習し、必要な制約内での代替実現を保持することで、同じルール予算の下で DNF 形式の定式化よりも高い構造的表現力を提供します。
4. 機能的かつ忠実な説明: 特定された重要なルールが予測クラスを積極的に支持し、非ターゲットクラスを抑制して、単なる事後の人工物ではなく機能的単位として機能することを示しました。

実験結果

TreeX は、3 つの合成データセット（BA-2Motifs, BAMultiShapes, BA-Neg）と 2 つの実世界分子データセット（Mutagenicity, NCI1）で評価されました。

• ロジットの忠実性: TreeX はベース GNN の生多クラスロジットを忠実に再構築し、高い**絶対確率忠実度（APF）**を達成しました（例：BA-2Motifs で 97% 超、実世界データセットで 75% 超）。
• ルールの影響: アブレーション研究により、上位の活性化ルールが一貫してターゲットクラスのロジットを増加させ、非ターゲットクラスを抑制することが示され、意思決定プロセスにおける機能的役割が確認されました。
• 設計の必要性: アブレーションにより、ルールモジュール、マージステップ、または負のリテラルを除去すると、特に生ロジットの再構築において性能が大幅に低下することが確認されました。
• 効率性と比較: 以前のクラスごとのルールベースの説明器（LogicXGNN, GLGExplainer, GraphTrail）と比較して、TreeX は競争力のある、あるいはそれ以上の**予測合意（PA）**を達成しつつ、最大 20 倍高速です。ベースラインとは異なり、TreeX はルール重み、テスト時のグラウンディング、およびロジットレベルの寄与分析を提供します。

意義と主張

本論文は、TreeX がグローバルで、テスト時にインスタンス化可能であり、部分グラフに根ざした説明フレームワークを提供すると主張しています。ロジット再構築に焦点を移すことで、TreeX は説明可能性のより厳密な評価を提供します：ルールは単なる記述ではなく、決定マージンを積極的に形成する機能的単位であることが示されています。

著者らは、TreeX が単なる事後の要約ツールではなく、GNN の意思決定ロジックが再利用可能な重み付けされた記号ルールに分解され得る仕組みを明らかにするメカニズムであると強調しています。このアプローチにより、ルールが予測クラスをどのように支持し、競合を抑制するかを分析することが可能となり、複数のルールと最終的な決定境界の間の相互作用が不明瞭であるという現在のモデルレベルの解釈可能性におけるギャップに対処します。このフレームワークは、人間が解釈可能な概念を特定し、それらを記号ルールに構成し、これらのルールを読み出しレベルの単位としてモデルの動作を再構築することで、ニューラルモデルを説明するためのより広範な道筋を示唆しています。