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

• URL: http://arxiv.org/abs/2607.26344v1
• Date: Tue, 28 Jul 2026 23:36:05 GMT
• Title: Automorphism-Induced Non-Canonicity in Top-k Explanations of Graph Neural Networks
• Abstract summary: 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.<n>Yet the standard report, the top-k edges, names one of the two, and which one is settled by the order of an array.<n>We show this is a structural obstruction rather than an implementation slip.
• Score: 7.541234468065092
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• The Edge Spectrum of Choice-Derived Item Graphs: Strong and Weak Edges Encode Different Relations in Collaborative Filtering [38.85665556927363]
  We show that strong and weak edges encode qualitatively different relations.<n>We formalize this as a sign mismatch between the smoothing operator and the ranking gradient.<n>This diagnosis explains three empirical observations on MIND and EB-NeRD.
  arXiv  Detail & Related papers  (2026-08-30T05:53:08Z)
• More Data Cannot Break a Symmetry: Identifiability by Design [13.778717173535577]
  Unsupervised representational alignment recovers a stimulus-by-stimulus correspondence from geometry alone.<n>The automorphism group of the stimulus geometry bounds what any such alignment can identify, before data exist.<n>We turn this known in geometry into a design-time diagnostic and intervention.
  arXiv  Detail & Related papers  (2026-08-27T19:38:09Z)
• Reasoning Shortcuts and Value Symmetries: What Symmetry Permits, Architecture Realizes, and Optimization Selects [10.012788934490084]
  Reasoning shortcuts are solutions of a neurosymbolic system's rules that produce correct predictions through unintended concepts.<n>A recent framework of Takemura, Inoue, and Nishino analyzes them through an automorphism group of value relabelings.<n>We first show that the framework's key definition, one shared permutation applied at every position, does not apply as stated to any of the four benchmarks it was evaluated on.
  arXiv  Detail & Related papers  (2026-08-11T03:10:20Z)
• Intrinsic Structure: Spectral Identifiability for Mechanistic Interpretability [51.56484100374058]
  We prove the first identifiability theorem for a mechanistic-interpretability primitive.<n>The spectrum is an identifiable, model-intrinsic fingerprint with a stated error bar, not a legible decomposition.
  arXiv  Detail & Related papers  (2026-08-10T19:42:01Z)
• Quantum-information fingerprints of partial dynamical symmetry in the interacting boson model [0.0]
  Partial dynamical symmetry (PDS) is an algebraic structure in which a prescribed symmetry is neither exact nor completely broken.<n>PDS is identified from spectroscopic data, band-head energies, level systematics, and $B(E2)$ ratios.<n>We encode the model on a qubit register and prepare its solvable and mixed eigenstates variationally, as a step toward evaluating the diagnostic on a quantum device.
  arXiv  Detail & Related papers  (2026-08-05T06:18:36Z)
• Neural Collapse Is Forbidden: Information Floors in Language Models [0.0]
  Within-class variance in language-model representations is commonly read as incomplete neural collapse.<n>We argue it is allocated information storage, and that the allocation obeys a law.
  arXiv  Detail & Related papers  (2026-07-10T15:04:02Z)
• Statistically Meaningful Geometry and Gauge Symmetry Breaking: A Geometric Foundation for Scientific Discovery and Intelligence Emergence [0.7766379063545538]
  Do machine learning systems exhibit genuine intelligence, or are they merely sophisticated statistical pattern matchers?<n>We introduce Statistically Meaningful Geometry, a framework modeling over- parameterized learning systems as infinite-dimensional non-parametric Orlicz fiber bundles.<n>We show that SMG provides a parameter-free, falsifiable dashboard to mathematically certify true intelligence, transforming AI for Science into an engine of autonomous paradigm shifts.
  arXiv  Detail & Related papers  (2026-07-03T13:34:56Z)
• A homotopy-type-theoretic generalization of neurosymbolic inference [46.36639624013224]
  neurosymbolic (NeSy) systems compute one functional: a belief-weighted sum of a logical quantity over a space of $$-structures.<n>We develop the framework from scratch for NeSy systems, prove a conservativity theorem that recovers the classical functional when symmetries are trivial, and show that the symmetry our framework exposes is exactly the one behind reasoning shortcuts.
  arXiv  Detail & Related papers  (2026-06-16T12:22:12Z)
• Exact Structural Abstraction and Tractability Limits [0.0]
  Exact correctness depends only on the induced classes $s sim_R simation' iff mathrmAdm_R(s)$.<n>Decision, search, approximation, statistical, randomized horizon, and distributional guarantees all reduce to this same quotient-recovery problem.
  arXiv  Detail & Related papers  (2026-04-08T17:59:47Z)
• The Attribution Impossibility: No Feature Ranking Is Faithful, Stable, and Complete Under Collinearity [0.0]
  No feature ranking can be simultaneously faithful, stable, and complete when features are collinear.<n>We prove this impossibility, quantify it for four model classes, resolve it via ensemble averaging (DASH), and machine-verify it with 305 Lean 4 theorems.<n>The design space theorem, diagnostics, and impossibility are mechanically verified in Lean 4 (305 theorems from 16 axioms, 0 sorry) -- to our knowledge, the first formally verified impossibility in explainable AI.
  arXiv  Detail & Related papers  (2026-04-08T10:11:45Z)
• RAGEN-2: Reasoning Collapse in Agentic RL [123.40730283427136]
  In RAGEN-2, we find that even with stable entropy, models can rely on fixed templates that look diverse but are input-agnostic.<n>We decompose reasoning quality into within-input diversity (Entropy) and cross-input distinguishability (Mutual Information, MI)<n>Across diverse tasks, mutual information correlates with final performance much more strongly than entropy, making it a more reliable proxy for reasoning quality.
  arXiv  Detail & Related papers  (2026-04-07T04:29:41Z)
• Any-Subgroup Equivariant Networks via Symmetry Breaking [47.72921214239821]
  equivariant architectures are usually highly constrained, designed for symmetries chosen a priori.<n>This precludes the development of flexible, multi-modal foundation models capable of processing diverse data equivariantly.<n>We build a single model that can be simultaneously equivariant to several groups, simply by modulating a certain auxiliary input feature.
  arXiv  Detail & Related papers  (2026-03-19T21:30:41Z)
• Neuro-Symbolic Entity Alignment via Variational Inference [27.4635535516158]
  NeuSymEA is a unified neuro-symbolic reasoning framework.<n>It exploits the cross-KG structural pattern for robust entity alignment.<n>NeuSymEA achieves a significant 7.6% hit@1 improvement on $textDBP15K_textZH-EN$ compared with strong baselines.
  arXiv  Detail & Related papers  (2024-10-05T13:29:22Z)
• Imbalanced Node Classification Beyond Homophilic Assumption [39.94226626445198]
  We propose a novel GraphSANN for imbalanced node classification on both homophilic and heterophilic graphs. Firstly, we propose a unified feature mixer to generate synthetic nodes with both homophilic and heterophilic in a unified way. Next, by randomly sampling edges between synthetic nodes and existing nodes as candidate edges, we design an adaptive subgraph extractor.
  arXiv  Detail & Related papers  (2023-04-28T05:33:19Z)
• Towards Antisymmetric Neural Ansatz Separation [48.80300074254758]
  We study separations between two fundamental models of antisymmetric functions, that is, functions $f$ of the form $f(x_sigma(1), ldots, x_sigma(N)) These arise in the context of quantum chemistry, and are the basic modeling tool for wavefunctions of Fermionic systems.
  arXiv  Detail & Related papers  (2022-08-05T16:35:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.