Linear-Time Correlation-Controlled Shuffling on Random Regular Graphs with Spectral Guarantees
This article proposes a linear-time correlation-controlled shuffling method that attenuates Pearson correlation by permuting one variable through local swaps on a random regular graph. Each round processes a fixed edge order and accepts only vertex-disjoint swaps, producing greedy matching rather than a standard interchange-process update. The analysis uses the induced first-moment operator. A uniform lower bound on edge acceptance yields a Laplacian-domination relation, while a lower bound on the probability that vertices remain unmatched controls the negative spectrum. Conditional on the loop-deleted realized graph being connected and having a spectral gap bounded away from zero, the absolute value of the expected correlation contracts exponentially. For every fixed same-sign attenuation target, an activation probability exists that attains the target in expectation. Finite-sample calibration uses a fixed-budget multi-resolution direct search without assuming monotonicity. Because the procedure applies only permutations, the marginal distribution is preserved exactly. Under fixed degree and fixed calibration budgets, both calibration and shuffling scale linearly with sample size. Experiments show small target errors, exact marginal preservation, and approximately linear runtime scaling. A matched-degree spectral ablation further shows that, with degree and edge count held fixed, the higher-gap random regular graph exhibits substantially faster decay of the mean correlation than the low-gap regular circulant graph.