Spectral vs. Combinatorial:
Two Views of Graph Structure for Max-3-Cut

1. Two Views of Graph Structure

Every method for Max-3-Cut must answer the same question: which vertices should go in which group? The methods we compare in this post all use the same greedy local search to refine their answers. They differ only in how they construct the initial partition — the starting point for greedy.

We compare two fundamentally different construction strategies:

The local view: DSatur

The DSatur algorithm assigns vertices one at a time, in order of decreasing saturation degree — the number of distinct labels already present among a vertex's neighbors. Each vertex receives the label that maximizes the immediate number of crossing edges. This is a purely combinatorial, sequential approach that uses only 1-hop neighborhood information.

Runtime: \(\mathcal{O}(|E| \log |V|)\) for construction, plus \(\mathcal{O}(r|E|)\) for greedy improvement rounds.

The global view: Rank-2 spectral (R2G)

The rank-2 spectral approach computes the top-2 eigenvectors of the graph Laplacian, constructs a spectral embedding of all vertices in \(\mathbb{C}^2\), samples a (often substantial) number of random directions in this embedding, and rounds each to the nearest cube root of unity. The best-scoring partition is kept. This captures global structure — community membership, spectral gaps — that may not be visible in any single vertex's neighborhood. This is the randomized version of the exact rank-2 algorithm, which computes a polynomial-size candidate set with no randomness; see Blog 1 and Blog 3 for details.

Runtime: \(\mathcal{O}(\mathrm{nnz} \times k_{\mathrm{iter}})\) for eigensolve + \(\mathcal{O}(S \times n)\) for sampling. Slower, but sees further. Importantly, the rank-\(r\) framework comes with provable approximation guarantees relative to the rank-\(r\) optimum (see the paper), whereas DSatur, as a heuristic, provides no worst-case quality bound.

2. Head-to-Head

We compare four methods on 15 instances across 13 graph families: DSG (DSatur + greedy), R2G (rank-2 + greedy, from Blog 3), Hybrid (rank-1 + greedy, from Blog 2), and SA (simulated annealing). All methods use the same greedy refinement; they differ only in construction.

DSG is the outright winner on 6 instances, R2G on 4, SA on 4, with 1 tie (DSG and R2G both find the torus optimum). The best-of-both ensemble — which simply picks the higher-scoring construction — beats SA on 11 of 13 graph families and beats Hybrid on all 13 (100%).

3. Why the Split?

In our experiments, DSG tends to win on spatial and geometric graphs, while R2G tends to win on social and web networks. We observe a pattern but note that our sample of graph families is limited; the following discussion is speculative and should be tested on more instances.

DSG tends to win on spatial and geometric graphs

On Delaunay meshes, road networks, and regular graphs, DSG consistently outperforms R2G. One possible explanation is that these graphs have strong local regularity: vertices with high saturation degree (many distinct neighbor labels) may correspond to natural cut boundaries, and DSatur's priority queue selects these vertices early. However, we have not formally verified this mechanism, and the advantage could also stem from DSatur's deterministic construction avoiding the variance inherent in random spectral sampling.

R2G tends to win on social and web networks

On email networks, web graphs, and product co-purchase networks, R2G outperforms DSG. A plausible explanation is that these graphs have community structure that is encoded in the top eigenvectors of the Laplacian but not visible in any single vertex's 1-hop neighborhood. The rank-2 spectral embedding may capture inter-community boundaries that DSatur's local view misses. That said, this hypothesis has not been tested on controlled instances (e.g., planted partition models), and other factors — degree distribution, graph density, or the specific greedy dynamics — could also contribute to the difference.

4. Stress-Testing the Split: Controlled Graph Families

The comparison in Section 2 uses real-world and standard synthetic graphs, but the sample is limited. To test whether the observed pattern — R2G wins on community-structured graphs, DSG wins elsewhere — holds more broadly, we ran a systematic sweep across two controlled graph families at multiple sizes and density levels, with 5 random seeds per configuration.

Sparse Stochastic Block Model (planted communities)

SBM graphs have \(K=3\) equal-sized communities with intra-community edge probability \(p_{\mathrm{in}}\) and inter-community probability \(p_{\mathrm{out}} = p_{\mathrm{in}}/10\). As density decreases, the community signal weakens locally (fewer same-community neighbors per vertex) while the spectral signal — encoded in the top eigenvectors — persists until the information-theoretic detection threshold.

At \(n \geq 3{,}000\), R2G outperforms DSG on every tested configuration (15 out of 15), winning 4–5 out of 5 seeds each time:

Cells show the R2G improvement over DSG (mean over 5 seeds) and the number of seeds where R2G wins. Green = R2G wins the majority of seeds.

The margins are modest (+0.1% to +0.4%) but consistent across all density levels and graph sizes. The spectral embedding captures the planted partition through the Laplacian's top eigenvectors — information that DSatur's 1-hop saturation degree does not have direct access to at these sparsity levels.

Random geometric graphs

Random geometric graphs place \(n\) points uniformly in the unit square and connect pairs within a radius \(r\). These graphs have spatial structure that is both local (short edges) and global (long-range connectivity patterns). Across 60 seeds (12 configurations × 5 seeds), R2G wins 43 out of 60 seeds (72%) with an average gap of +0.15% over DSG.

Takeaway

These controlled experiments confirm that each method has graph families where it reliably outperforms the other. Neither R2G nor DSG is uniformly better; the advantage depends on the graph's structural properties. This motivates the ensemble approach in the next section.

5. The Ensemble

Since DSG and R2G have complementary strengths, the natural strategy is to run both and keep the better partition. This is the “best-of-both” ensemble:

1. Construct two partitions: run DSatur (\(\mathcal{O}(|E| \log |V|)\)) and rank-2 sampling (\(\mathcal{O}(\mathrm{nnz} \times k_\mathrm{iter} + S \times n)\)).
2. Score both using the Laplacian fast path (\(3 \times |\mathrm{cut\ edges}|\) for \(K=3\)).
3. Pick the higher-scoring partition.
4. Refine with greedy local search until convergence.

The computational cost is dominated by the rank-2 sampling phase (DSatur's construction is negligible in comparison). For practitioners who need speed over the last fraction of a percent, DSG alone is an excellent default — it beats Hybrid on 11 of 15 instances and beats SA on 9 of 13 families, all while running in quasi-linear time.

6. When Neither View Suffices

On 2 of 13 graph families (the three small Delaunay meshes and ca-HepPh), SA still produces higher-quality partitions than both DSG and R2G. We do not have a definitive explanation for why these particular instances favor SA. One possibility is that the greedy landscape on these graphs has deeper local optima that neither DSatur's nor spectral's construction can avoid, while SA's stochastic exploration escapes them given enough iterations. Another possibility is simply that our SA budget (which was generous on these instances) is sufficient to compensate for the lack of a structured starting point.

On Erdős–Rényi random graphs (tested in Blog 3 but not included in the ensemble table above), all construction methods produce similar-quality partitions. SA wins, likely because random graphs have little exploitable structure for either local or spectral methods, and SA benefits from its longer exploration budget.

7. The DSatur Algorithm

DSatur was originally introduced for graph coloring by Brélaz (1979) and adapted for Max-\(K\)-Cut by Apte et al. (2026). The construction phase works as follows:

The construction phase is \(\mathcal{O}(|E| \log |V|)\): each vertex is pushed to the heap at most \(\mathcal{O}(\deg(v))\) times. The local improvement phase is \(\mathcal{O}(r|E|)\) for \(r\) rounds. In practice, \(r \leq 10\) on all tested instances.

8. Summary

Local and global views of graph structure are complementary, not competing. The ensemble that combines DSatur (local, quasi-linear) with rank-2 spectral sampling (global, eigensolve-based) beats simulated annealing on 11 of 13 tested graph families and beats the previous best spectral method on all of them. For speed-constrained applications, DSatur alone is a strong default: quasi-linear time, no eigensolve required, competitive with SA on most graph types.

References

1. A. Apte, S. Boulebnane, Y. Jin, S. Omanakuttan, M. A. Perlin, and R. Shaydulin. “Quantum Approximate Optimization of Integer Graph Problems and Surpassing SDP for Max-k-Cut.” arXiv:2602.05956, 2026.
2. R. Stevens, F. Liao, B. Su, J. Li, and A. Kyrillidis. “Exploiting Low-Rank Structure in Max-K-Cut Problems.” arXiv:2602.20376, 2026.
3. A. Frieze and M. Jerrum. “Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION.” Algorithmica, 18(1):67–81, 1997.
4. D. Brélaz. “New Methods to Color the Vertices of a Graph.” Communications of the ACM, 22(4):251–256, 1979.

Citation