Spectral Annealing: Normalization-Path Exploration for Large-Scale Ising Optimization

Large-scale Ising optimization underlies critical optimization and learning applications, including correlation clustering, MAP inference, and energy-based models. Spectral relaxation methods run in polynomial time but yield solutions with significant optimality gaps while metaheuristics close those gaps but scale poorly to large instances. In particular, spectral methods are inherently single-shot as they solve exactly one eigenvalue problem. We introduce $\textit{Spectral Annealing}$ (SpecAnn), a new spectral optimization approach that transforms traditional spectral methods from single-shot approximations into exploration-based optimization, by sweeping a parametrized normalization path from the raw adjacency to the signed normalized Laplacian, with an $O(n)$ diagonal predictor that warm-starts successive eigensolves and GPU-batched local search refining candidates in parallel. Experiments on general Ising problems demonstrate that SpecAnn achieves competitive to near-optimal solutions depending on instance structure, with runtimes less than 7 minutes for instances of 8.4M variables. SpecAnn delivers up to 83$\times$ speedup over recent GPU-accelerated methods while maintaining superior solution quality, and scales successfully beyond 524K variables where traditional metaheuristics fail.