Kavli Affiliate: Jia Liu
| First 5 Authors: Ismail Alkhouri, Ismail Alkhouri, , ,
| Summary:
We propose a scalable framework for solving the Maximum Cut (MaxCut) problem
in large graphs using projected gradient ascent on quadratic objectives.
Notably, while our approach is differentiable and leverages GPUs for
gradient-based optimization, it is not a machine learning method and does not
require training data beyond the given problem formulation. Starting from a
continuous relaxation of the classical quadratic binary formulation, we present
a parallelized strategy that explores multiple initialization vectors in batch,
offering an efficient and memory-friendly alternative to traditional solvers.
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 address this, we
introduce a lifted quadratic formulation that over-parameterizes the solution
space, allowing the algorithm to escape poor fixed-points. 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, leveraging their complementary strengths along 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
training-data-intensive, dataless, and GPU-accelerated sampling approaches.
| Search Query: ArXiv Query: search_query=au:”Jia Liu”&id_list=&start=0&max_results=3