Noisy isomorphism: Robust expressivity of GNNs under structural perturbation

The expressivity of graph neural networks is predominantly characterized in a noiseless setting via binary graph isomorphism tests. This perspective certifies whether two graphs can be distinguished, but does not quantify how robust such distinctions are under structural perturbations. In practice, however, real-world graphs are often corrupted by noise, where even small structural changes might lead to disproportionate distortions in learned representations. In this study, we generalize graph isomorphism to a noisy alignment criterion, requiring that graphs that remain identifiable under noise are embedded closer to their source than to any alternative. This yields a margin-based formulation of expressivity that bridges the gap between combinatorial isomorphism-based theory and the continuous learned representations. Notably, our framework is architecture-agnostic and strictly generalizes classical isomorphism-based expressivity. We further derive certified robustness guarantees for node-level tasks and an explicit robustness radius for graph-level representations. Experiments confirm that our criteria predict and improve robustness under structural perturbations.