GNN Explanations Show Arbitrary Choices for Symmetric Inputs

Explanations for Graph Neural Networks (GNNs), particularly those that highlight the "top-k" most important edges, suffer from a structural issue when dealing with symmetric inputs. Because GNNs are permutation equivariant, they assign identical attribution scores to elements that are chemically or structurally equivalent, such as two identical nitro groups in a molecule. However, when an explainer is forced to select a fixed number (k) of edges, it arbitrarily picks one of the equivalent elements, leading to inconsistent and non-canonical explanations. This paper demonstrates that this is not an implementation flaw but a fundamental obstruction: no rule can be simultaneously single-valued, minimal, and symmetry-respecting when the input's automorphism group doesn't fix a minimal valid explanation. The issue is prevalent in common datasets, with a significant percentage of molecules exhibiting such symmetries, making the reported explanations potentially misleading.