Matrix-Free Stochastic Training of Low-Rank Spectral Graph Learning via Randomized Adaptive Spectral Estimation

Large-graph spectral learning promises global, trainable propagation beyond local neighborhoods, but explicit spectral layers remain difficult to use in stochastic large-graph training: their bases are commonly obtained by a full-graph spectralization step and their graph-wide contexts are naturally full-batch. Matrix-free polynomial filters avoid eigensolvers and train stochastically, but tie the response to finite propagation bases; explicit spectral-subspace models offer more flexible global responses, but usually pay for full-graph basis construction and context evaluation. We introduce Randomized Adaptive Spectral Estimation (RASE), a matrix-free stochastic training framework for explicit low-rank spectral-context layers. RASE constructs a refreshable randomized block-Krylov/Ritz basis from probe vectors and sparse matrix--vector products, reuses probe-derived summaries as control variates for mini-batch estimates of the spectral context, and keeps the response module replaceable across polynomial, Chebyshev, and transformer-style instantiations. We analyze Krylov/Ritz polynomial-action exactness for the probe-generated subspace and a control-variate variance identity that isolates when the mini-batch context estimator reduces variance. Across 14 node-classification benchmarks, RASE matches its eigenbasis-trained reference within seed noise where the eigensolver is feasible (${\sim}67{\times}$ faster basis on PubMed), and trains the same backbone on the largest graphs where eigensolver preprocessing exceeds a 30-minute budget. The contribution is therefore not a new spectral filter family, but a training route that makes explicit low-rank spectral-context layers matrix-free and mini-batch trainable.