arXiv:2607.26344cs.LGcs.AI2026-07

GNN解释器在对称分子上无法避免选择性偏差,因结构限制导致解释结果任意。

Automorphism-Induced Non-Canonicity in Top-k Explanations of Graph Neural Networks

  • 利用图自同构证明解释结果必然受输入对称性影响
  • 93.4%的Mutagenicity数据集分子存在对称性,24.0%的双硝基分子仅报告一个
  • 报告原子轨道可消除任意性,仅增加0.11毫秒与0.43条边

基于梯度的GNN解释器在具有两个化学等价硝基的分子上分配的归因分数完全相等。由于消息传递机制具备置换等变性,输入的任何自同构都会使所有归因保持不变。然而标准的top-k边报告必须选择其中一个,其选择由数组顺序决定。我们证明这是结构性障碍而非实现失误:当最小有效解释不被输入自同构群固定时,无法同时满足单值性、最小性和对称性尊重。针对实际中使用的exact-k报告,我们提出一个无需参数的判别准则,已在Lean 4中机械化验证且无公理依赖。在21298个实例预算决策中,该准则与机械模型等价检查完全一致,未发现可替代的中立方案。自同构现象普遍存在:93.4%的Mutagenicity数据集分子含非平凡自同构;在报告的稀疏预算下,25个含两个可互换硝基的分子中有6个(24.0%)仅报告其中一个,且每个选择均经机械验证为任意。模型自身也制造对称性:每个MUTAG分子包含化学上可区分但网络无法分辨的原子,控制实验表明分辨率取决于模型读取内容而非参数化方式。报告轨道可消除任意性,仅增加0.11毫秒与0.43条额外边。

原文摘要 · Abstract (English)

A gradient-based GNN explainer given a molecule with two chemically equivalent nitro groups assigns them attribution scores that are equal to the last bit. It cannot do otherwise: message passing is exactly permutation equivariant, so any automorphism of the input leaves every attribution invariant. Yet the standard report, the top-k edges, names one of the two, and which one is settled by the order of an array. We show this is a structural obstruction rather than an implementation slip. When no minimal valid explanation is fixed by the input's automorphism group, no rule can be single-valued, minimal and symmetry-respecting at once. For the exact-k reports used in practice we give a parameter-free criterion, mechanised in Lean 4 with no axiom dependencies, that decides from the graph alone whether every score-optimal report of that size must split an orbit. Across 21298 instance-budget decisions the criterion agrees with a mechanical model-equivalence check without exception, and no severing case we found admitted a neutral alternative. The obstruction is common. Nontrivial automorphisms occur in 93.4% of Mutagenicity, the dataset the seminal explainability papers use, so the measure-zero dismissal of symmetric inputs, sound on the continuous domains it was made for, collapses here. At the sparsity budget those papers report, 24.0% of molecules with two interchangeable nitro groups (6 of 25) surface exactly one of them, every one arbitrary under mechanical verification. A model's blindness also manufactures symmetry: every MUTAG molecule contains atoms chemistry separates and the network provably cannot, and a matched control shows the resolution is set by what the model reads rather than how it is parameterised. Reporting orbits removes the arbitrariness at 0.11 ms and 0.43 extra edges per graph.

GNN解释对称性可解释性分子图

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。