🤖 machine learning

TN-SHAP-G: Graph-Structured Tensor Network Surrogates for Shapley Values and Interactions

本論文は、グラフ構造の入力に対して正確なシャプレー値および高次相互作用を効率的に計算するために、グラフ整合テンソルネットワークサロゲートを利用するフレームワークであるTN-SHAP-Gを導入しており、これにより従来のメソッドに内在する指数関数的な複雑さとサンプリング分散を克服している。

原著者： Farzaneh Heidari, Guillaume Rabusseau

公開日 2026-06-02

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Farzaneh Heidari, Guillaume Rabusseau

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたは、分子の画像（原子と結合のグラフ）を入力すると、それが危険か安全かを予測する、複雑なブラックボックス・マシンを持っていると想像してください。あなたはこう知りたいと考えています：どの特定の原子がその予測の責任を持っているのか？ そしてさらに重要なのは、特定の原子のグループが協力してその結果を生み出しているのか？ ということです。

ここで**シャプレイ値（Shapley values）**の登場です。これは、ゲームにおけるすべてのプレイヤー（原子）に対して、「貢献度」を公平に分配する方法だと考えてください。しかし、この貢献度を計算するのは悪夢のような作業です。ある原子がどれほど貢献しているかを正確に知るためには、あらゆる原子の組み合わせ（ある原子を残したり、隠したりしながら）をテストして、予測がどのように変化するかを確認しなければなりません。もし原子が20個あれば、100万通り以上の組み合わせが存在します。もし50個あれば、その数はあまりにも膨大で、宇宙の寿命よりも長い時間がかかるでしょう。

現在の手法は、ランダムな組み合わせをサンプリングすることで答えを推測しようとしますが、これは遅く、ノイズが多く、原子同士の微妙な「チームワーク」を見逃してしまうことがよくあります。

TN-SHAP-Gは、賢い翻訳機でありショートカットとして機能することで、この問題を解決する新しい手法です。その仕組みを、簡単な比喩を用いて説明します。

1. 「影絵」 (サロゲートモデル)

ブラックボックス・マシンに何百万回ものテストを実行させる代わりに、TN-SHAP-Gは、わずか数百回のテスト（例えば、レシピを推測するために、異なる材料を入れたスープを味見するようなこと）を行うよう指示します。

そして、そのマシンに対して簡略化された「影絵」バージョンを構築します。これは単なるランダムな推測ではありません。これは**テンソルネットワーク（Tensor Network）**と呼ばれる数学的な構造です。

比喩: 分子が都市の地図だとします。ブラックボックス・マシンは複雑な交通システムです。TN-SHAP-Gはその都市の簡略化されたモデルを構築します。そこでは道（原子間の接続）は維持されていますが、交通ルールは計算しやすいコンパクトな地図へと簡略化されています。
鍵となる点: この簡略化された地図は、分子の形状と全く同じに見えるように作られています。もし分子が環状（リング状）であれば、数学モデルも環状になります。これにより、宇宙全体をシミュレートする必要なく、原子が隣接する原子にどのように影響を与えるかを捉えることができます。

2. 「魔法の公式」 (決定論的な復元)

この簡略化された「影絵」が学習されると、魔法が起こります。このモデルは特定の種類の数学（多重線形多項式）を使用して構築されているため、著者らはすべての原子に対する正確な貢献度を計算するための**閉形式の公式（closed-form formula）**を見つけ出しました。

比喩: 通常、車の平均速度を知るには、1,000回時間を計測して平均を取るかもしれません（サンプリング）。TN-SHAP-Gは、車のエンジンの完璧な設計図を持っているようなものです。車を1,000回走らせる必要はありません。設計図を計算機に入力するだけで、瞬時に正確な速度を教えてくれます。
結果: モデルが一度学習されれば、推測やランダム性を一切排除し、すべての原子および原子のペアの重要性を即座に、かつ完璧に吐き出すことができます。

3. なぜ優れているのか（「チームワーク」の優位性）

ほとんどの手法は、2つの原子がどのように「協力」するか（相互作用）を理解することに苦労します。それらは、人々がランダムに握手している様子を見て、秘密の握手の仕方を当てようとしているようなものです。

TN-SHAP-Gは、設計図の上で握手が起きている様子をスローモーションで見ているようなものです。追加のテストを行うことなく、2つの原子の間にどれだけの「相乗効果（シナジー）」が存在するか（例：「窒素と酸素が組み合わさると、それぞれ単独である時よりも10倍危険になる」など）を正確に計算できます。
効率性: 他の手法がまともな答えを得るために5,000回や50,000回のクエリ（ブラックボックスへの問い合わせ）を必要とする一方で、TN-SHAP-Gは多くの場合、わずか50回から100回のクエリで、ほぼ完璧な答えを得ることができます。

4. 検証内容

著者らはこれを分子（薬物やタンパク質など）を用いてテストしました。

低分子: 「ゴールドスタンダード（あらゆる組み合わせをチェックする方法）」と比較しました。TN-SHAP-Gは、ゴールドスタンダードとほぼ完全に一致（精度99%以上）しましたが、それを数千倍速く実行しました。
高分子: 数百のノードを持つ巨大なタンパク質構造を用いてテストしました。他の手法がクラッシュしたり、時間がかかりすぎたりする中で、TN-SHAP-Gはスムーズに処理し、数百のノードを持つグラフまでスケールアップできました。

まとめ

TN-SHAP-Gは、ブラックボックス・モデルがどのように意思決定を行っているかを示す、コンパクトで形状に配慮した「カンニングペーパー」を学習するツールです。一度このカンニングペーパーを手に入れれば、ブラックボックス・モデルに何百万もの答えを求めることなく、グラフ（分子など）のどの部分が重要であり、それらがどのように協力しているかを、即座に、かつ完璧に計算できます。これは、通常であればスーパーコンピュータと一生分の待ち時間を必要とする問題を、標準的なコンピュータ上で数秒で解決可能なものへと変えるのです。

技術要約: TN-SHAP-G

問題提起

ブラックボックス型のグラフニューラルネットワーク（GNN）の予測を説明するには、個々のノードとその相互作用に対して重要度を帰属させる必要がある。シャプレー値や高次の相互作用指数は、原理的かつ公理的な帰属手法を提供するが、その厳密な計算はグラフにおいては計算量的に困難であり、 $n$ をノード数とすると $O(2^n)$ でスケールする。既存の近似手法は重大なトレードオフに直面している。例えば、GNNExplainer のようなアーキテクチャ固有のエクスプレイナーは一般的なブラックボックスモデルには適用できず、一方で GraphSVX や SHAP-IQ のようなサンプリングベースの手法は、数千回のモデル評価を必要とし、特に高次の相互作用において高い分散を生じる。さらに、これらのサンプリング手法は、厳密な列挙が不可能な大規模グラフへのスケーリングに失敗することが多い。

手法: TN-SH-GAP

著者らは、グラフ構造を持つ入力の構造的特性を利用して、シャプレー値と相互作用を効率的かつ決定論的に計算するフレームワークである TN-SHAP-G を提案する。その核心となるアイデアは、予測器のマスクされた入力の振る舞いを近似する、コンパクトでグラフに整合したテンソルネットワーク（TN）サロゲートを学習することである。

1. マスクされたグラフゲーム

本手法は、ノードのマスキングによって誘導される協力ゲームとしてグラフの説明を定式化する。固定された入力グラフ $G=(V, E)$ 、特徴量 $X$ 、およびベースライン $X^0$ に対して、提携（coalition） $S \subseteq V$ は、マスクされた特徴行列 $X_S$ を定義する。ここで、 $S$ 内のノードは元の特徴量を保持し、 $S$ 外のノードはベースラインの特徴量に置き換えられる。ゲームの値は $\nu(S) = f(G, X_S)$ であり、 $f$ はブラックボックス予測器である。

2. 多重線形拡張とテンソル縮約

直接的なシャプレー値の計算には $2^n$ 個の提携を総和する必要がある。著者らは、 $z \in [0, 1]^n$ 上で定義された離散ゲームの連続的な緩和である多重線形拡張 $\hat{\nu}(z)$ を利用する。

テンソル定式化: 多重線形拡張は、テンソル縮約として正確に表現できる： $\hat{\nu}(z) = \sum_{s \in \{0,1\}^n} T_s \prod_{v=1}^n b_v(z_v)^{s_v}$ 。ここで、 $T$ は提携テンソルであり、 $b_v(z_v)$ はベルヌーイ選択ベクトルである。
決定論的な回復: シャプレー値と相互作用指数は、対角線 $z = t\mathbf{1}$ に沿った偏微分の積分に対応する。 $\hat{\nu}$ は多重線形であるため、これらの微分は最大で次数 $n-1$ の単変数多項式となる。したがって、厳密な帰属は少数のプローブポイントからの**ヴァンデルモンド補間（Vandermonde interpolation）**を通じて回復可能であり、これによりモンテカルロ近似の分散を排除できる。

3. グラフに整合したテンソルネットワーク・サロゲート

フルサイズの提請テンソル $T$ は $2^n$ 個のエントリを持つため、TN-SHAP-G は多重線形拡張を近似するために、グラフに整合したテンソルネットワークサロゲート $\hat{\nu}$ を学習する。

トポロジー: TNのトポロジーは入力グラフ $G$ を反映する。各ノード $v$ は、1つの物理インデックス（提携への所属をエンコード）と、隣接ノードへと接続するボンドインデックスを持つコアテンソル $A^{(v)}$ に対応する。
表現力: ボンド次元 $\chi$ は、情報の流れの容量を制御する。著者らは、ゲームがグラフのセパレータに対して低いカットランクを持つ場合（多くのGNNにおける局所的な依存パターンの特性）、このグラフに整合した構造が、循環的または複雑なグラフでランク膨張を起こしやすい Tensor Train (TT) のような連鎖ベースの分解よりも、より少ないパラメータで高い表現力を達成することを証明している。
学習: サロゲートは、サンプリングされた少数の提携（ $M \ll 2^n$ ）を用いた経験的リスク最小化を通じて学習される。理論的な保証によれば、有界次数グラフの場合、必要なクエリ予算はノード数に対してほぼ線形にスケールする。

4. 推論

一度学習されると、このサロゲートは以下の決定論的な計算を可能にする：

一次シャプレー値: 対角線微分の1次元積分を介して算出。
高次相互作用: 混合偏微分と積分を介して算出。
これらすべての量は、ブラックボックスモデルへの追加のクエリを行うことなく、単一の学習済みサロゲートから計算される。

主な貢献

原理に基づいたグラフ整合型表現: 指数関数的な提携値テーブルを、低ランクかつグラフに整合した多重線形表現へと圧縮する、テンソルネットワーク・サロゲートの導入。これは、サロゲートの帰納バイアスをグラフ予測器における局所的な依存パターンに適合させている。
償却された決定論的計算: ヴァンデルモンド補間を用いて、シャプレー値と相互作用を決定論的に計算する多重線形構造の活用。これにより、わずか $O(n)$ のサロゲート評価のみが必要となり、モンテカルロの分散を伴わない。単一のサロゲートが、すべての一次および高次指数を計算するためのコストを償却する。
理論的保証:
- 学習されたサロゲートが多重線形拡張を一意に決定することを証明し、サロゲート上での帰属の厳密な回復を保証する。
- カットランクの議論を通じて表現力を特徴付け、グラフに整合したTNが（TTのような）連鎖分解よりも優れていることを証明する。
- 有界次数グラフにおける、教師モデルへのクエリ複雑性がほぼ線形であることの境界を示す。
- ゲームの近似誤差とシャプレー値の誤差を結びつける安定性の保証。
実証的性能: 分子ベンチマークにおいて高い精度とスケーラビリティを示し、わずか50回のモデル評価で、厳密なシャプレー値に対して0.99以上のコサイン類似度を達成した（ベースラインよりも10〜100倍少ない評価回数）。

実験結果

著者らは、分子ベンチマーク（Mutagenicity, Benzene）およびタンパク質グラフ（PROTEINS）を用いてTN-SHAP-Gを評価した。

正確性: 小規模なグラフ（ $n \le 20$ ）において、TN-SHAP-Gは厳密なシャプレー値（O1）および相互作用指数（O2）に密接に一致し、精度と分散の両面でGraphSVXや置換サンプリングを大幅に上回った。
クエリ効率: TN-SHAP-Gは、サンプリングベースの推定器（SHAP-IQ, GraphSVX）よりも10〜100倍少ないモデルクエリで、高い帰属精度を達成した。
スケーラビリティ: 本手法は、粗視化ベースのサロゲートアーキテクチャを用いることで、最大600ノードのグラフに対しても効率的にスケールする。一方、厳密な列挙やサンプリングベースの手法は実用的ではなくなる。
構造アブレーション: パラメータ数を一致させた条件下において、グラフに整合したTNは一貫してTensor Train (TT) サロゲートよりも優れた性能を示し、トポロジーに整合した分解の理論的優位性を裏付けた。
忠実度のプロキシ: サロゲートのテスト時の $R^2$ と、回復されたシャプレー値のコサイン類似度との間に強い相関が見られ、 $R^2$ が帰属精度の実用的なプロキシとして有効であることが検証された。

重要性と主張

論文は、TN-SHAP-Gが、シャプレー計算の指数関数的な複雑さを克服する原理に基づいたモデル非依存のフレームワークを提供することで、グラフの説明可能性における最先端技術を進展させたと主張している。グラフ構造を持つ協力ゲームに内在する低ランク構造を利用することで、本手法は決定論的で分散のない帰属を、ほぼ線形なクエリ複雑量で実現する。

著者らは、このアプローチが、計算リソースが限られている実務家、特に創薬や分子特性予測のような高リスクな領域における、厳密な説明手法へのアクセスを民主化するものであると強調している。このフレームワークは、様々なゲームセマンティクス（例：ノードマスキング、ノード削除、Myerson値）や特徴量タイプをサポートしており、標準的なメッセージパッシングGNNを超えて他のグラフ予測器にも拡張可能である。本研究は、テンソルネットワークを単なる圧縮ツールとしてではなく、構造化データに対する扱いやすいゲーム理論的分析のための基本的なメカニズムとして位置づけている。