Randomized Rank-2 for Max-3-Cut: When Two Eigenvectors Beat One

1. From Exact to Randomized

In Blog 1, we showed that the exact rank-2 algorithm for Max-3-Cut enumerates \(O(n^3)\) candidate partitions — one for each triple of hyperplane indices. Throwing 15 GPUs at the problem pushed this to \(n = 3{,}600\) nodes, but cubic scaling is a hard wall: doubling \(n\) multiplies work by 8. Meanwhile, Blog 2 demonstrated that rank-1 scales to a million nodes but uses only one of the two dominant spectral directions.

The natural question: can we get rank-2 quality without rank-2 cost? The answer is randomized sampling. Instead of enumerating all \(\binom{n}{3}\) triples, we sample \(S\) random triples and take the best. The key finding is striking:

This is surprising. A priori, one might expect the “good” triples to become a vanishing fraction of the \(O(n^3)\) total as \(n\) grows. Instead, the spectral structure concentrates the mass: most random triples produce partitions that are close to optimal. The randomized algorithm inherits rank-2’s ability to explore the full spectral subspace at a cost that is independent of \(n\). (Tested at \(n = 250\) to \(1{,}500\) against exact rank-2; indirect evidence to \(n = 1{,}400{,}000\) via fixed-budget runs.)

Since sampling is cheap, the practical question becomes: on which graphs does the rank-2 subspace contain better partitions than rank-1?

2. Where Does Rank-2 Help?

Rank-1 uses a single eigenvector to partition the graph: it projects nodes onto a 1D subspace and sweeps a single hyperplane. Geometrically, this covers a great circle on the unit sphere in the spectral embedding. When the graph’s structure is well-captured by one spectral direction — as in torus or regular graphs where the top two eigenvalues are nearly degenerate — this great circle already passes through the optimal partition.

But when the top two eigenvalues are separated by a gap, the rank-1 projection loses information. The optimal partition lies off the great circle, in the full 2D spectral subspace. Rank-2 recovers this by sampling triples of hyperplanes that sweep the entire sphere, not just a single meridian.

The eigengap — defined as the relative separation \((\lambda_1 - \lambda_2) / \lambda_1\) between the top two eigenvalues — predicts where rank-2 helps. The scatter plot below shows the relationship between eigengap and the percentage improvement of rank-2 over rank-1.

An important caveat: the eigengap predicts where rank-2 standalone improves over rank-1, but it does not predict where the full pipeline (rank-2 + greedy) beats other methods. On web-Google, rank-2 alone scores 21% worse than rank-1 (eigengap 15.4%), yet the pipeline beats every competitor. The reason: when rank-2’s partition is fed to greedy local search, the greedy phase converges to a different — and sometimes better — local optimum than when started from rank-1. This depends on the graph’s community structure, not its eigengap. Section 3 makes this concrete.

3. The 3-Phase Pipeline

The full algorithm, which we call R2G (Rank-2 + Greedy), consists of three phases:

1. Eigensolve. Compute the top 2 eigenvectors \(\mathbf{v}_1, \mathbf{v}_2\) of the graph Laplacian \(\mathbf{Q}\) using ARPACK. Cost: \(O(\text{nnz} \cdot k_{\text{iter}})\).
2. Randomized rank-2 sampling. Construct the transformed matrix \(\tilde{V} \in \mathbb{R}^{3n \times 4}\) from the two eigenvectors. Sample \(S\) random triples of row indices from \(\tilde{V}\), compute the null vector for each triple, project all vertices onto the resulting complex direction, and round to the nearest cube root of unity. Keep the highest-scoring partition. Cost: \(O(S \cdot n)\).
3. Greedy refinement. Starting from the rank-2 partition, run steepest-ascent local search until convergence. Cost: \(O(n \cdot d \cdot T)\) where \(T\) is the number of greedy passes.

The pipeline is modular: phase 2 replaces the rank-1 sweep from Blog 2, while phases 1 and 3 are identical. The key difference is that rank-2 sampling provides a different starting partition for the greedy phase, which leads to improved local optima on social, product, and web graphs.

Results: R2G vs. Hybrid vs. SA

We compare three methods on 12 representative instances across 9 graph families: R2G (rank-2 + greedy), Hybrid (rank-1 + greedy, from Blog 2), and SA (simulated annealing). All methods use the same greedy refinement; they differ only in initialization.

R2G beats Hybrid on 10 of 15 tested instances and beats SA on 6 of 12 graph families: social networks (email-Enron, soc-Epinions1), product networks (amazon0601), location-based networks (loc-Brightkite), web graphs (web-Google), and structured graphs (torus). On road networks, Delaunay meshes, and Erdős–Rényi graphs, SA retains its advantage.

Additional results on SNAP datasets reinforce the pattern:

4. Timing: When R2G Wins on Both Axes

On most graphs, R2G trades a small quality deficit against SA for a large speedup. But on two important families, R2G wins on both axes — better quality and faster wall-clock time:

Torus graphs: R2G achieves the optimal score of 3,000,000 on the torus with \(n = 500{,}000\) nodes, matching rank-1 exactly (since rank-1 already finds the optimum on torus). SA runs for over 1,000 seconds and still falls 1.58% short. The eigensolve + rank-2 sampling + greedy pipeline finishes in under 40 seconds on the same graph — a 25× speedup.

email-Enron: This social network is small enough (\(n = 36{,}692\)) that all methods run in comparable time. But R2G produces a cut of 445,293 vs. SA’s 444,426 — a 0.19% improvement with no additional cost. The spectral structure of the Enron email graph (strong community structure with a clear eigengap) is precisely the regime where rank-2 shines.

5. What Doesn’t Work

Regular graphs: tied with rank-1. On 5-regular graphs, the top two eigenvalues are nearly degenerate (eigengap < 0.02%), so rank-2 provides no additional spectral information over rank-1. The R2G score of 703,767 on the 100K-node regular graph is actually worse than the Hybrid score of 727,090: the rank-2 partition, while similar in quality to rank-1’s, leads the greedy phase to a less favorable local optimum on these graphs. When the eigengap is effectively zero, rank-1 is the right initialization.

The structural ceiling. Rank-2 sampling alone — without greedy refinement — does not beat greedy local search on any instance. The spectral rounding produces a partition that captures global structure but misses local optimizations. The greedy phase is essential: it converts spectral “potential” into actual score improvements. R2G should be understood as rank-2 initialization, not rank-2 optimization.

ER and road networks. On Erdős–Rényi graphs and road networks, SA still wins. We verified that increasing the sample budget from 1M to 10M on both roadNet-PA and roadNet-TX produces negligible improvement (+0.035% and +0.07% respectively), confirming that the rank-2 ceiling on these graphs is structural. R2G beats Hybrid on these instances but the gap to SA remains.

What about rank-3? We tested rank-3 sampling (using 3 eigenvectors, candidate tuples of size 5) on six graphs. At equal sample budgets, rank-3 is ~7× slower per candidate due to the larger SVD (5×6 vs 3×4 matrices), and the results are within ±0.1% of rank-2:

The additional eigenvector does not justify the cost. Rank-2 appears to be the sweet spot for the 3-phase pipeline.

6. Open Questions

1. Can we prove \(S^*(n) = O(1)\)? Our experiments strongly suggest that the number of random samples needed to approximate the exact rank-2 optimum is independent of \(n\). A proof would likely require showing that the spectral embedding concentrates the “good” triples into a constant-fraction region of the sample space, independent of the ambient dimension. Connections to random matrix theory (the Marchenko–Pastur law for Laplacian spectra) may be relevant.
2. Eigengap → quality gap characterization. The scatter plot in Section 2 shows a clear trend: larger eigengaps correlate with larger rank-2 gains. Can we formalize this? Specifically, is there a bound of the form
   $$\frac{\textrm{score}(\textrm{R2})}{\textrm{score}(\textrm{R1})} \geq 1 + c \cdot \frac{\lambda_1 - \lambda_2}{\lambda_1}$$
   for some constant \(c > 0\)? Such a result would enable algorithm selection: compute the eigengap in \(O(\text{nnz})\), and decide whether to run rank-1 or rank-2 before paying the sampling cost.
3. Connection to zonotopes and oriented matroids. The rank-2 candidate set — all partitions achievable by three hyperplanes in the 2D spectral embedding — is the set of vertices of a zonotope. The combinatorial structure of this zonotope (its face lattice, its oriented matroid) may explain why random sampling works: if the zonotope has a small number of “important” vertices (those achieving near-optimal scores), the sampling complexity depends on this combinatorial quantity rather than on \(n\).

7. Summary

The table below summarizes the winner for each graph family among the three main competitors: R2G, Hybrid (rank-1 + greedy), and SA.

The 3-phase pipeline (eigensolve → rank-2 sample → greedy refine) beats SA on 6 of 12 graph families tested, including social networks, product graphs, and web graphs with up to 875K vertices. On structured graphs (torus), it finds the exact optimum. On road networks and random graphs, SA remains better.

The \(O(1)\) sample complexity makes the pipeline practical at any graph size — the same 10⁶ random samples work at \(n = 250\) and \(n = 1{,}400{,}000\). The pipeline is simple to implement, embarrassingly parallel, and requires only the top-2 eigenvectors of the graph Laplacian.

References

1. A. Frieze and M. Jerrum. “Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION.” Algorithmica, 18(1):67–81, 1997.
2. S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi. “Optimization by Simulated Annealing.” Science, 220(4598):671–680, 1983.
3. T. A. Davis and Y. Hu. “The University of Florida Sparse Matrix Collection.” ACM Transactions on Mathematical Software, 38(1):1–25, 2011.
4. J. Leskovec and A. Krevl. “SNAP Datasets: Stanford Large Network Dataset Collection.” snap.stanford.edu/data, 2014.

Citation