Differentiable Spectral Normalization for Large-Scale Ising Optimization

Thinh Nguyen-Cong; Thang N. Dinh

IJCAI 20260 citations

Differentiable Spectral Normalization for Large-Scale Ising Optimization

Abstract

Spectral relaxation is widely used for large-scale combinatorial optimization due to its computational efficiency. Yet its effectiveness depends critically on the choice of graph normalization, a design decision typically made heuristically. Here, we show that normalization can be treated as a continuous optimization variable rather than a fixed preprocessing choice. Our method, Differentiable Spectral Normalization (DSN), parameterizes the spectral relaxation through a diagonal metric and maximizes the resulting lower bound via projected gradient ascent. Exact gradients are obtained through the Hellmann-Feynman theorem using only the principal eigenpair, maintaining linear complexity per iteration. On benchmark instances ranging from 10^3 to 8.4 x 10^6 nodes, DSN improves solution quality by 3-15% over static spectral methods. Its performance comes within 1-3% of state-of-the-art metaheuristics, such as simulated annealing, at up to 190x lower computational cost on large-scale instances. These results suggest that learning problem-specific relaxation geometry can substantially close the gap between spectral scalability and metaheuristic solution quality.

Constraint Satisfaction and Optimization: Constraint optimization problemsConstraint Satisfaction and Optimization: Mixed discrete and continuous optimizationMachine Learning: Matrix/tensor methodsMachine Learning: OptimizationSearch: Combinatorial search and optimisation

BibTeX

@inproceedings{ijcai2026_differentiablesp,
  title = {Differentiable Spectral Normalization for Large-Scale Ising Optimization},
  author = {Thinh Nguyen-Cong and Thang N. Dinh},
  booktitle = {IJCAI 2026},
  year = {2026}
}