Cycle-Aware Spectral Testing for Community Structure via Renewal Non-Backtracking Random Walks

We study goodness-of-fit testing for community structure in networks. Classical spectral tests for the Erdős–Rényi null rely on adjacency information alone and can lose power in sparse or weak-signal regimes. We propose RNBRW-GOF, a cycle-aware spectral test based on renewal non-backtracking random walk retracing probabilities. The method replaces the adjacency matrix by a centered and normalized matrix of RNBRW edge weights and rejects for large values of its largest eigenvalue. On the theory side, we prove exact null centering under edge exchangeability, crude second-moment control, and finite-walk concentration for empirical RNBRW weights. We also establish sparse-regime local dependence decay for bounded truncated scores and derive truncation and normalization results that support the use of RNBRW-based spectral calibration. These results do not yield a full universality theorem for the final matrix statistic; accordingly, inference is theory-motivated and simulation-calibrated via a Bartlett-type correction together with a Tracy–Widom type 1 reference law. Across simulated Erdős–Rényi nulls, the corrected statistic is reasonably calibrated in moderate and large graphs. Under assortative stochastic block alternatives, RNBRW-GOF improves over adjacency-based spectral testing in several sparse and weak-signal regimes and remains competitive with a non-backtracking spectral baseline, which is itself highly competitive in intermediate regimes. Overall, the results position RNBRW-GOF as a practically calibrated, cycle-aware goodness-of-fit test for assortative community structure.