SSPO: Structure-Aware Similarity-Weighted Preference Optimization for Neural Combinatorial Optimization

SSPO (Structure-Aware Similarity-Weighted Preference Optimization) is a method for neural combinatorial optimization (NCO) training that addresses two failure modes in existing approaches: gradient signal polarization and baseline redundancy.

Gradient signal polarization occurs in best-anchor methods like BOPO, which treat the single best solution in a group as a privileged 'anchor' and cast every other sample as an undifferentiated negative, discarding fine-grained quality gradients that exist among the non-best solutions—and the structural differences that explain why one non-best solution is better than another.

Baseline redundancy occurs in mean-based baselines that weight peers uniformly, so structurally near-identical peers flood the baseline with redundant information and keep gradient variance high.

SSPO scores all B sampled solutions jointly through a dissimilarity-weighted leave-one-out baseline: structurally distinct peers receive higher weight, resolving both failures in a single mechanism. The baseline uses zero-parameter, problem-adaptive solution embeddings built from the encoder's existing node representations. For TSP, embeddings use Hadamard products of node pairs; for EFL and JSP, they use mean-pooling over solution-relevant selected nodes. Embeddings are centered to remove shared global bias, and dissimilarity weights are computed as wij ∝ (1 − Sij), where Sij is cosine similarity between solutions i and j. Since Sii = 1, the self-weight wii = 0 follows automatically, excluding the reference cost from its own baseline and preserving the leave-one-out construction. When all solutions are structurally identical, wij degenerates uniformly to 1/(B − 1), recovering standard RLOO as a special case.

The paper provides a formal variance analysis (Proposition 1) showing that SSPO achieves lower baseline variance than uniform RLOO precisely when its structure-aware weights sufficiently reduce the contribution of highly correlated peer pairs to offset the penalty caused by weight concentration.

Experiments on TSP, EFL, and JSP benchmarks show consistent gains over prior best-anchor and uniform-weight baselines. On TSP-50, SSPO achieves 0.14% gap vs. BOPO's 0.15%; on TSP-100, SSPO achieves 0.40% vs. BOPO's 0.48% and RLOO's 1.32%. On EFL, SSPO attains the best result (0% relative gap), while BOPO and POMO trail by 7.31% and 7.34% respectively. On JSP, SSPO improves over BOPO by 1.14pp on TA (7.52% vs. 8.66%) and 0.86pp on DMU (12.95% vs. 13.81%), though BOPO holds a marginal 0.05pp edge on the easier LA family (2.50% vs. 2.55%).

A direct comparison against uniform RLOO on TSP and EFL confirms that structure-aware weighting is the primary driver of improvement. The ablation shows that replacing SSPO's dissimilarity weights with uniform weights on TSP-100 degrades the gap from 0.40% to 1.32%—a 3.3× deterioration on the same architecture, initialization, and rollouts, isolating structure-aware weighting as the source of gain.

The SSPO-trained EFL policy has been deployed in a production facility-location system at JD.com, confirming practical viability at scale. The paper concludes that the structural information encoded in the graph representations—so far used only for action selection—is a rich, underused signal for variance reduction.

Improvements to AI systems:

1. Replace uniform baselines with structure-aware, dissimilarity-weighted leave-one-out baselines in any policy-gradient or preference-optimization training loop for combinatorial optimization (e.g., routing, scheduling, facility location). This reduces gradient variance and eliminates the need for a privileged “best” anchor, leading to faster convergence and better final solution quality.

2. Reuse the encoder’s existing node embeddings to construct zero-parameter solution embeddings (e.g., Hadamard products for pairwise problems, mean-pooling for selection problems) for baseline computation. This adds no trainable parameters and requires no extra forward passes, making the improvement computationally free.

3. Automatically degenerate to uniform RLOO when solutions are structurally identical (via self-weight zeroing and uniform fallback), ensuring the method is robust across problem instances with varying diversity—no hyperparameter tuning needed for the baseline.

4. Center solution embeddings to remove shared global bias before computing cosine dissimilarity, which stabilizes weight computation across batches and prevents distribution shift during training.

What the improved AI system can do:

• Solve TSP instances (up to 100 nodes) with 0.40% optimality gap—a 3.3× improvement over uniform RLOO (1.32%) and a 17% relative improvement over best-anchor BOPO (0.48%) on the same architecture.

• Achieve near-optimal solutions on facility location problems (EFL) with 0% relative gap, outperforming BOPO and POMO by over 7 percentage points—making it deployable in real production systems (as demonstrated at JD.com).

• Handle job-shop scheduling (JSP) with consistent gains over BOPO (e.g., 7.52% vs. 8.66% on TA benchmarks) while remaining competitive on easier problem families.

• Train more sample-efficiently by extracting fine-grained quality gradients from all non-best solutions, not just the top one—reducing the number of rollouts needed to reach a target solution quality.

• Scale to real-world logistics and operations where solution diversity is high, because the baseline adapts its weighting to structural similarity, avoiding redundancy and variance spikes.