Recursive Message Passing is Topology-Adaptive

Graph neural networks perform message passing through a fixed sequence of layers and thus couple parameterization, receptive field, and computation. We identify this _coupling problem_ as a central structural limitation of message passing: no single depth $L$ can simultaneously avoid over-smoothing dense, low-diameter graphs while reaching across elongated or weakly connected ones. We argue that input-adaptive depth is therefore a structural requirement of the message-passing paradigm, and introduce Tiny Recursive Graph Neural Networks (TRGNNs) to realize it. TRGNNs combine _recursive message passing_, which decouples effective depth from parameterization, with _iterative prediction refinement_, which refines node predictions at each recursive step so that effective depth emerges from a learned function of the downstream accuracy, where predictions stabilize as effective depth increases, rather than a predetermined layer count or other external halting signal. We show empirically that these mechanisms yield _topology-adaptive effective depth_. Moreover, we establish a restricted formal connection between the rate at which latent representations approach a fixed point and the spectral quantity governing over-smoothing. Empirically, TRGNNs match or exceed GNN performance while using far fewer parameters and support anytime prediction.