🤖 machine learning

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

该论文引入了 TN-SHAP-G，这是一个利用图对齐张量网络代理（graph-aligned tensor network surrogates）来高效计算图结构输入的精确 Shapley 值及其高阶相互作用的框架，克服了传统方法中固有的指数级复杂度和采样方差。

原作者： 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 值 发挥作用的地方。你可以把它们看作是一种公平分配“功劳”的方法，将预测的贡献分配给所有的参与者（原子）。然而，计算这种功劳简直是一场噩梦。为了准确了解一个原子的贡献度，你必须测试每一种可能的原子组合（保留某些原子，隐藏另一些原子）来观察预测结果的变化。如果你有 20 个原子，就会产生超过一百万种组合。如果你有 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. 为什么它更好（“团队协作”优势）

大多数方法在理解两个原子如何“协同工作”（相互作用）方面表现挣扎。它们就像是通过随机观察人们握手来试图猜出一个秘密握手的动作。

TN-SHAP-G 就像是在蓝图上以慢动作观察握手过程。它可以精确计算出两个原子之间存在的“协同效应”（例如：“氮和氧在一起时的危险程度是它们各自单独存在时的 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）的预测结果，需要将重要性归因于单个节点及其相互作用。虽然 Shapley 值和高阶交互指数提供了具有原则性和公理化的归因方法，但其精确计算在图结构上是难以处理的，其复杂度随节点数 $n$ 呈 $O(2^n)$ 指数级增长。现有的近似方法面临着显著的权衡：架构特定解释器（如 GNNExplainer）无法应用于通用的黑盒模型；而基于采样的方法（如 GraphSVX、SHAP-IQ）则需要数千次模型评估，并且在处理高阶交互时存在高方差问题。此外，这些采样方法在无法进行精确枚举的大规模图上往往难以扩展。

方法论：TN-SHAP-G

作者提出了 TN-SHAP-G，该框架利用图结构输入的结构特性，高效且确定性地计算 Shapley 值和交互指数。其核心思想是学习一个紧凑的、与图对齐的张量网络（TN）代理模型，用以近似预测器的掩码输入行为。

1. 掩码图博弈（The Masked Graph Game）

该方法将图解释形式化为一个由节点掩码诱导的合作博弈。对于给定的输入图 $G=(V, E)$ ，其特征为 $X$ ，基准值为 $X^0$ ，一个联盟 $S \subseteq V$ 定义了一个掩码特征矩阵 $X_S$ ，其中 $S$ 中的节点保留原始特征，而 $S$ 之外的节点被基准特征替换。博弈值定义为 $\nu(S) = f(G, X_S)$ ，其中 $f$ 是黑盒预测器。

2. 多线性扩展与张量收缩

直接计算 Shapley 值需要对 $2^n$ 个联盟求和。作者利用了多线性扩展 $\hat{\nu}(z)$ ，它是定义在 $z \in [0, 1]^n$ 上的离散博弈的连续松弛。

张量形式化： 多线性扩展可以精确表示为张量收缩： $\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)$ 是伯努利选择向量。
确定性恢复： Shapley 值和交互指数对应于 $\hat{\nu}$ 在对角线 $z = t\mathbf{1}$ 沿线的偏导数的积分。由于 $\hat{\nu}$ 是多线性的，这些导数最多为 $n-1$ 次的一元多项式。因此，可以通过来自少量探测点的 范德蒙德插值（Vandermonde interpolation） 来精确恢复归因，从而消除了蒙特卡洛方差。

3. 图对齐张量网络代理

由于完整的联盟张量 $T$ 拥有 $2^n$ 个条目，TN-SHAP-G 学习了一个图对齐张量网络代理 $\hat{\nu}$ 来近似多线性扩展。

拓扑结构： TN 拓扑镜像了输入图 $G$ 。每个节点 $v$ 对应一个核心张量 $A^{(v)}$ ，该张量包含一个物理指标（编码联盟成员身份）和连接到邻居的键指标（bond indices）。
表达能力： 键维度 $\chi$ 控制了信息跨越图分隔符（graph separators）的流动能力。作者证明，对于具有低截断秩（cut-rank）的博弈（这是许多 GNN 局部依赖模式的特性），这种图对齐结构能以比链式分解（如 Tensor Trains, TT）更少的参数实现更高的表达能力，因为后者在循环或复杂图上会遭受秩膨胀问题。
训练： 该代理通过在少量采样的联盟（ $M \ll 2^n$ ）上进行经验风险最小化来训练。理论保证表明，对于定度图，所需的查询预算随节点数呈近线性增长。

4. 推理

一旦训练完成，该代理即可实现确定性计算：

一阶 Shapley 值： 通过对角线导数的一维积分实现。
高阶交互： 通过混合偏导数和积分实现。
所有量都直接从训练好的单一代理中计算得出，无需对黑盒模型进行额外的查询。

核心贡献

原则性的图对齐表示： 引入了张量网络代理，将指数级的联盟-值表压缩为低秩、图对齐的多线性表示。这使代理的归纳偏置与图预测器的局部依赖模式保持一致。
摊销确定性计算： 利用多线性结构，通过闭式范德蒙德插值计算 Shapley 值和交互。这仅需 $O(n)$ 次代理评估，且不引入蒙特卡洛方差。单个代理即可摊销所有一阶及高阶指标的计算。
理论保证：
- 证明了学习到的代理能唯一确定多线性扩展，确保了在代理上的归因精确恢复。
- 通过截断秩论证了表达能力，证明了图对齐 TN 在处理图结构博弈时优于链式分解（如 TT）。
- 为定度图提供了近线性的教师查询复杂度界限。
- 建立了将博弈近似误差与 Shapley 误差联系起来的稳定性保证。
实验性能： 在分子基准测试（Mutagenicity, Benzene）上展示了极高的准确性，在仅需 50 次模型评估的情况下，与精确 Shapley 值的余弦相似度达到 $>0.99$ （比基准方法减少了 10–100 倍），并能扩展到采样方法无法处理的规模。

实验结果

作者在分子基准（Mutagenicity, Benzene）和蛋白质图（PROTEINS）上评估了 TN-SHAP-G。

正确性： 在小规模图（ $n \le 20$ ）上，TN-SHAP-G 与精确 Shapley 值 (O1) 和交互指数 (O2) 高度匹配，在准确性和方差方面均显著优于 GraphSVX 和排列采样法。
查询效率： 与基于采样的估计器（SHAP-IQ, GraphSVX）相比，TN-SHAP-G 以少 10–100 倍的模型查询次数实现了高归因精度。
可扩展性： 该方法通过基于粗化（coarsening）的代理架构，能够高效扩展到包含高达 600 个节点的图，而精确枚举和基于采样的方法在此时已变得不切实际。
结构消融实验： 在参数匹配的条件下，图对齐 TN 始终优于张量链（TT）代理，证实了拓扑对齐分解的理论优势。
保真度代理： 观察到代理的测试集 $R^2$ 与恢复的 Shapley 值的余弦相似度之间存在强相关性，验证了 $R^2$ 是衡量归因准确性的实用代理指标。

意义与主张

论文声称 TN-SHAP-G 通过提供一种原则性的、模型无关的框架，克服了 Shapley 计算的指数级复杂度，从而推动了图可解释性的前沿。通过利用图结构合作博弈中固有的低秩结构，该方法实现了确定性的、无方差的归因，且具有近线性的查询复杂度。

作者强调，这种方法通过降低计算门槛，使那些在药物发现和分子属性预测等高风险领域中计算资源有限的从业者，也能使用严谨的解释方法。该框架具有灵活性，支持各种博弈语义（例如节点掩码、节点移除、Myerson 值）和特征类型，并能从标准的消息传递 GNN 扩展到其他图预测器。这项工作将张量网络定位为不仅是压缩工具，更是对结构化数据进行可处理博弈论分析的基础机制。