A Scalable Lift-and-Project Differentiable Approach For the Maximum Cut Problem

Ismail Alkhouri, Mian Wu, CUNXI YU, Jia Liu, Rongrong Wang, Alvaro Velasquez
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:334-342, 2026.

Abstract

We propose a scalable framework for solving the Maximum Cut (MaxCut) problem in large graphs using projected gradient ascent on quadratic objectives. Our approach is differentiable and leverages GPUs for gradient-based optimization. It is not a machine learning method and does not require training data. Starting from a continuous relaxation of the classical quadratic binary formulation, we present a parallelized strategy that explores multiple initialization vectors in batch. We analyze the relaxed objective, showing it is convex and has fixed-points corresponding to local optima—particularly at boundary points—highlighting a key challenge in non-convex optimization. To improve exploration, we introduce a lifted quadratic formulation that over-parameterizes the solution space. We also provide a theoretical characterization of these lifted fixed-points. Finally, we propose DECO, a dimension-alternating algorithm that switches between the unlifted and lifted formulations, combined with importance-based degree initialization and a population-based evolutionary hyper-parameter search. Experiments on diverse graph families show that our methods attain comparable or superior performance relative to recent neural networks and GPU-accelerated sampling approaches.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-alkhouri26a, title = { A Scalable Lift-and-Project Differentiable Approach For the Maximum Cut Problem }, author = {Alkhouri, Ismail and Wu, Mian and YU, CUNXI and Liu, Jia and Wang, Rongrong and Velasquez, Alvaro}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {334--342}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/alkhouri26a/alkhouri26a.pdf}, url = {https://proceedings.mlr.press/v300/alkhouri26a.html}, abstract = { We propose a scalable framework for solving the Maximum Cut (MaxCut) problem in large graphs using projected gradient ascent on quadratic objectives. Our approach is differentiable and leverages GPUs for gradient-based optimization. It is not a machine learning method and does not require training data. Starting from a continuous relaxation of the classical quadratic binary formulation, we present a parallelized strategy that explores multiple initialization vectors in batch. We analyze the relaxed objective, showing it is convex and has fixed-points corresponding to local optima—particularly at boundary points—highlighting a key challenge in non-convex optimization. To improve exploration, we introduce a lifted quadratic formulation that over-parameterizes the solution space. We also provide a theoretical characterization of these lifted fixed-points. Finally, we propose DECO, a dimension-alternating algorithm that switches between the unlifted and lifted formulations, combined with importance-based degree initialization and a population-based evolutionary hyper-parameter search. Experiments on diverse graph families show that our methods attain comparable or superior performance relative to recent neural networks and GPU-accelerated sampling approaches. } }
Endnote
%0 Conference Paper %T A Scalable Lift-and-Project Differentiable Approach For the Maximum Cut Problem %A Ismail Alkhouri %A Mian Wu %A CUNXI YU %A Jia Liu %A Rongrong Wang %A Alvaro Velasquez %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-alkhouri26a %I PMLR %P 334--342 %U https://proceedings.mlr.press/v300/alkhouri26a.html %V 300 %X We propose a scalable framework for solving the Maximum Cut (MaxCut) problem in large graphs using projected gradient ascent on quadratic objectives. Our approach is differentiable and leverages GPUs for gradient-based optimization. It is not a machine learning method and does not require training data. Starting from a continuous relaxation of the classical quadratic binary formulation, we present a parallelized strategy that explores multiple initialization vectors in batch. We analyze the relaxed objective, showing it is convex and has fixed-points corresponding to local optima—particularly at boundary points—highlighting a key challenge in non-convex optimization. To improve exploration, we introduce a lifted quadratic formulation that over-parameterizes the solution space. We also provide a theoretical characterization of these lifted fixed-points. Finally, we propose DECO, a dimension-alternating algorithm that switches between the unlifted and lifted formulations, combined with importance-based degree initialization and a population-based evolutionary hyper-parameter search. Experiments on diverse graph families show that our methods attain comparable or superior performance relative to recent neural networks and GPU-accelerated sampling approaches.
APA
Alkhouri, I., Wu, M., YU, C., Liu, J., Wang, R. & Velasquez, A.. (2026). A Scalable Lift-and-Project Differentiable Approach For the Maximum Cut Problem . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:334-342 Available from https://proceedings.mlr.press/v300/alkhouri26a.html.

Related Material