KS-Adaptive Graph Halting

Add adaptive computation to an otherwise standard message-passing GNN. Process a sampled neighborhood one hop at a time, retain the current root logit \(s_\ell\), and define the empirical change \(d_\ell=|s_\ell-s_{\ell-1}|\) or, for classification, the fraction of nodes whose predicted class changed between layers. Estimate \(\Delta\) from the graph and estimate \(\gamma\) either from labels on a calibration split, from a fitted edge-correlation parameter, or as the sigmoid-constrained scalar used by the attenuated model. Compute \(\kappa=\gamma^2\Delta\). For \(\kappa<1\), choose a conservative budget using \(\ell_\varepsilon=\lceil3\log(C/\varepsilon)/\log(1/\kappa)-1\rceil\), with \(C\) calibrated by measuring the error gap between depths 2 and 4 on a validation set. At each layer, halt a node when \(d_\ell<\tau\) for two consecutive layers and the theoretical tail proxy \(C\kappa^{(\ell+1)/3}<\varepsilon\); batch nodes with the same active depth. For \(\kappa\geq1\), disable the subcritical certificate and use a maximum depth plus the empirical change criterion. The paper determines the geometric form, while \(C\), \(c\), and \(\tau\) are validation estimates. Test first on Reddit or ogbn-arxiv with a 2-to-12-layer GraphSAGE, comparing fixed depth, Ponder-style halting, and KS halting at equal accuracy. The target signal is 20–50% fewer message-passing FLOPs and sampled edges at unchanged accuracy, with no increase in worst-case error and a clear correlation between predicted \(\ell_\varepsilon\) and the empirically optimal depth.