CCTC: Constructive–Corrective Transition Calibration for Unsupervised Combinatorial Optimization

Diffusion models have recently shown promise for unsupervised combinatorial optimization (CO), learning to generate high-quality solutions without labeled optimal solutions. However, we find that their training signals can exhibit substantially different discriminative quality across transition directions, a phenomenon we term Constructive-Corrective Transition Asymmetry. Specifically, learned policies exhibit substantially weaker target-conditioned discrimination for constructive transitions than for corrective ones, which our analysis relates to a directional scale asymmetry in the underlying transition signals. These findings highlight a gap between effective trajectory-level credit assignment and discriminative transition-level supervision. To address this problem, we propose Constructive-Corrective Transition Calibration (CCTC), which calibrates transition-level supervision according to signal magnitude and transition direction. CCTC combines bounded calibration with direction-conditioned weighting to selectively strengthen target-favored constructive transitions. Experiments on four node- and edge-selection CO problems across eight settings show that CCTC consistently outperforms existing unsupervised state-of-the-art methods while achieving stronger constructive transition discrimination.