Top-k Explanations of GNNs Face Structural Symmetry Problem

A recent study published on arXiv (2607.26344) identifies a critical limitation in gradient-based explainers for Graph Neural Networks (GNNs). In molecules featuring two equivalent nitro groups, any automorphism results in equal attribution scores. Yet, conventional top-k edge reports arbitrarily select one group based purely on array order. The authors demonstrate that this issue is structural rather than an implementation flaw: when no minimal valid explanation is determined by the input's automorphism group, it is impossible for any rule to be minimal, single-valued, and respect symmetry. For exact-k reports commonly used, they introduce a parameter-free criterion, implemented in Lean 4 without axiom dependencies, to ascertain whether every optimal report must divide an orbit, aligning with results from 21,298 instance-budget decisions.