# Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization

arXiv: https://arxiv.org/abs/2602.20376 · HTML: https://mlsanity.com/paper/2602.20376/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 43 references that are in the map.
- First posted on arXiv 23 Feb 2026.

## Builds on (most cited first, 12 of 12)

- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [SNAP: A General Purpose Network Analysis and Graph Mining Library](https://mlsanity.com/paper/1606.07550/) (2016)
- [Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach](https://mlsanity.com/paper/1609.03240/) (2016)
- [QUBO Formulations for Training Machine Learning Models](https://mlsanity.com/paper/2008.02369/) (2020)
- [One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction](https://mlsanity.com/paper/2208.10227/) (2022)
- [Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero](https://mlsanity.com/paper/1905.11623/) (2019)
- [Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration](https://mlsanity.com/paper/2205.14105/) (2022)
- [Asymmetry Helps: Eigenvalue and Eigenvector Analyses of Asymmetrically Perturbed Low-Rank Matrices](https://mlsanity.com/paper/1811.12804/) (2018)
- [Fixed-rank Rayleigh Quotient Maximization by an MPSK Sequence](https://mlsanity.com/paper/1401.6968/) (2014)
- [ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-k-Cut Problems](https://mlsanity.com/paper/2412.05146/) (2024)
- [Complex Semidefinite Programming and Max-k-Cut](https://mlsanity.com/paper/1812.10770/) (2018)
- [Exact algorithms for quadratic optimization over roots of unity](https://mlsanity.com/paper/2508.02006/) (2025)

## Abstract (arXiv)

We study the problem of maximizing a complex-valued quadratic form over the Kth roots of unity. We show that when the objective matrix Q^star ∈ mathbbCn × n of the quadratic has rank r, the global maximizer belongs to a candidate set of size O(rn2r-1). This set can be constructed deterministically in O(rn2r+1) time by enumerating the vertices of a hyperplane arrangement in ℝ2r. The algorithm is embarrassingly parallel; with~P processors, the time complexity drops to O(r n2r+1/P). For approximately low-rank settings, where the objective matrix is a noise-perturbed variant of a rank-r matrix, we prove that applying our framework to a spectral truncation yields a multiplicative (1 - O(left|Hright|2 / δstar))-approximation guarantee, where δstar denotes the eigengap of the underlying rank-r matrix and H represents the perturbation. To scale to high-dimensional problems, we establish a randomized sampling variant. We prove that uniformly sampling S ≥ O(1/varepsilonr-1) candidates achieves a (1-varepsilon)cos2(π / K)-approximation of the optimal rank-r solution with high probability. Crucially, this sample size is entirely independent of n, reducing the overall runtime to O(S · n2). Computational experiments on synthetic benchmarks and large-scale graphs for textscMax-3-Cut confirm that our algorithms match or exceed semi-definite programming solution quality on structured instances while enabling massive parallelization across heterogeneous hardware and scaling seamlessly to problems where n ≥ 106.