The Missing Signal: Gradient Injection Recovers O(n2) Residual Decoding in GNNs

Residual decoding algorithms repeatedly score the current elements, prune the lowest-scoring candidate, and update the residual state. Classical implementations are efficient because their scores are built from locally maintainable statistics such as degree: after a deletion, surviving scores change by local corrections, giving O(n2) total decoding cost. However, a Graph Neural Network (GNN) score does not automatically have this property. After nonlinear activations such as tanh or sigmoid, equal changes in the underlying statistic need not induce equal changes in the output, so no fixed-additive correction can generally update the score after a deletion. The standard adaptive alternative is to rerun the full network after every deletion, inflating decoding cost to O(n3). We show that, for Max-Clique, the gradient of an unsupervised clique objective provides an update-compatible residual signal. After each vertex deletion, every surviving gradient coordinate changes by a local, maintainable quantity, updatable in O(n) per step. Supplying this live gradient to a lightweight learned updater recovers O(n2) decoding at state-of-the-art quality on Easy and Medium planted clique regimes. Zero-shot evaluation on six real-world graph benchmarks confirms consistent gains over score-only updating.