Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2505.20972

Deep k-grouping: An Unsupervised Learning Framework for Combinatorial Optimization on Graphs and Hypergraphs

Bai, Sen, Chunqi Yang, Xin Wei Bai, Xin Zhang, Zhengang Jiang

Published May 27, 2025• 2 citations
arXivHTMLPDF

Abstract

Along with AI computing shining in scientific discovery, its potential in the combinatorial optimization (CO) domain has also emerged in recent years. Yet, existing unsupervised neural network solvers struggle to solve $k$-grouping problems (e.g., coloring, partitioning) on large-scale graphs and hypergraphs, due to limited computational frameworks. In this work, we propose Deep $k$-grouping, an unsupervised learning-based CO framework. Specifically, we contribute: Novel one-hot encoded polynomial unconstrained binary optimization (OH-PUBO), a formulation for modeling k-grouping problems on graphs and hypergraphs (e.g., graph/hypergraph coloring and partitioning); GPU-accelerated algorithms for large-scale k-grouping CO problems. Deep $k$-grouping employs the relaxation of large-scale OH-PUBO objectives as differentiable loss functions and trains to optimize them in an unsupervised manner. To ensure scalability, it leverages GPU-accelerated algorithms to unify the training pipeline; A Gini coefficient-based continuous relaxation annealing strategy to enforce discreteness of solutions while preventing convergence to local optima. Experimental results demonstrate that Deep $k$-grouping outperforms existing neural network solvers and classical heuristics such as SCIP and Tabu.

DOI
10.48550/arxiv.2505.20972

Related papers

BIPNN: Learning to Solve Binary Integer Programming via Hypergraph Neural Networks

Sen Bai, Chunqi Yang, Xin Wei Bai +2 more

Binary (0-1) integer programming (BIP) is pivotal in scientific domains requiring discrete decision-making. As the advance of AI computing, recent works explore neural network-based solvers for integer linear programming (ILP) problems. Yet, they lack scalability for tackling nonlinear challenges. To handle nonlinearities, state-of-the-art Branch-and-Cut solvers employ linear relaxations, leading to exponential growth in auxiliary variables and severe computation limitations. To overcome these limitations, we propose BIPNN (Binary Integer Programming Neural Network), an unsupervised learning framework to solve nonlinear BIP problems via hypergraph neural networks (HyperGNN). Specifically, BIPNN reformulates BIPs-constrained, discrete, and nonlinear (sin, log, exp) optimization problems-into unconstrained, differentiable, and polynomial loss functions. The reformulation stems from the observation of a precise one-to-one mapping between polynomial BIP objectives and hypergraph structures, enabling the unsupervised training of HyperGNN to optimize BIP problems in an end-to-end manner. On this basis, we propose a GPU-accelerated and continuous-annealing-enhanced training pipeline for BIPNN. The pipeline enables BIPNN to optimize large-scale nonlinear terms in BIPs fully in parallel via straightforward gradient descent, thus significantly reducing the training cost while ensuring the generation of discrete, high-quality solutions. Extensive experiments on synthetic and real-world datasets highlight the superiority of our approach.

arXiv:2505.20997•neural information processing systems•Jan 1, 2025•1 citation

Decision-focused Graph Neural Networks for Combinatorial Optimization

Yang Liu, Chuan De Zhou, Peng Zhang +3 more

In recent years, there has been notable interest in investigating combinatorial optimization (CO) problems by neural-based framework. An emerging strategy to tackle these challenging problems involves the adoption of graph neural networks (GNNs) as an alternative to traditional algorithms, a subject that has attracted considerable attention. Despite the growing popularity of GNNs and traditional algorithm solvers in the realm of CO, there is limited research on their integrated use and the correlation between them within an end-to-end framework. The primary focus of our work is to formulate a more efficient and precise framework for CO by employing decision-focused learning on graphs. Additionally, we introduce a decision-focused framework that utilizes GNNs to address CO problems with auxiliary support. To realize an end-to-end approach, we have designed two cascaded modules: (a) an unsupervised trained graph predictive model, and (b) a solver for quadratic binary unconstrained optimization. Empirical evaluations are conducted on various classical tasks, including maximum cut, maximum independent set, and minimum vertex cover. The experimental results on classical CO problems (i.e. MaxCut, MIS, and MVC) demonstrate the superiority of our method over both the standalone GNN approach and classical methods.

arXiv:2406.03647•Jun 5, 2024•2 citations

A Method for Large Scale Unconstrained Binary Quadratic Programming Problem Based on Graph Neural Network

Jia-jia Huang, Shenshen Gu

In recent years, the advantages of Graph Neural Networks (GNNs) in solving complex combinatorial optimization problems have become more and more obvious. Under this background, this paper demonstrates a method based on GNNs to solve large-scale Unconstrained 0–1 Quadratic Programming (UBQP) problems. Firstly, the UBQP problem models of different combinatorial optimization problems are converted into a unified graph model. This approach makes up for the shortcoming that GNNs cannot be effectively applied to combinatorial optimization problems not based on graph. Secondly, based on Graph Attention Network (GAT) algorithm, this study designs a general GNN model capable of solving UBQP problems. In addition, a random sampling scheme for the complete graph structure is devised, which greatly alleviates the pronounced over-smoothing phenomenon when the model is applied to complete graphs and speeds up the convergence rate. In this paper, a supervised learning approach is adopted to train and test a unified structured model (without changing network parameters) on UBQP problems of varying sizes, and to evaluate the model's generalization ability on high-dimensional UBQP problems. Furthermore, an unsupervised learning mechanism is utilized to train and solve individual sample problems of different dimensions. These experimental results consistently demonstrate that the model and strategy presented in this paper exhibit strong solving ability and generalization ability for combinatorial optimization problems.

International Conference on Intelligent Control and Information Processing•Mar 8, 2024•1 citation

Solving Combinatorial Optimization Problem Over Graph Through QUBO Transformation and Deep Reinforcement Learning

Tianle Pu, Chao Chen, Li Zeng +3 more

Many complex problems encountered in both production and daily life can be conceptualized as combinatorial optimization problems (COPs). Many ad-hoc deep learning methods have been proposed to solve these problems, but there still lacks an effective unified framework. In this work, we take a step towards this goal by designing an unified end-to-end deep reinforcement learning framework named CONQUER. CONQUER first translates various COPs into the unified QUBO (Quadratic Unconstrained Binary Optimization) formalization, and afterwards trains a neural QUBO solver to search high-quality strategies, which are then checked and repaired to obtain the solutions for original COPs. The QUBO solver is a purely data-driven neural model, which does not rely on any expert inputs. We adopt the graph transformer network to represent the QUBO graph, so as to effectively capture the features of problem objective and constraints. The Deep Q-network is utilized to train the QUBO solver to find long-sighted solution strategies. Despite being trained solely on small synthetic graphs, CONQUER exhibits promising generality on much larger instances, and can be easily adapted to real-world datasets. Experimentally, we show that CONQUER achieves the state-of-the-art performances on four COPs over graphs, including minimum vertex cover, maximum independent set, maximum clique and maximum cut problem.

Proceedings•Dec 9, 2024•3 citations

Combinatorial Optimization with Automated Graph Neural Networks

Yang Liu, Peng Zhang, Yang Gao +3 more

In recent years, graph neural networks (GNNs) have become increasingly popular for solving NP-hard combinatorial optimization (CO) problems, such as maximum cut and maximum independent set. The core idea behind these methods is to represent a CO problem as a graph and then use GNNs to learn the node/graph embedding with combinatorial information. Although these methods have achieved promising results, given a specific CO problem, the design of GNN architectures still requires heavy manual work with domain knowledge. Existing automated GNNs are mostly focused on traditional graph learning problems, which is inapplicable to solving NP-hard CO problems. To this end, we present a new class of \textbf{AUTO}mated \textbf{G}NNs for solving \textbf{NP}-hard problems, namely \textbf{AutoGNP}. We represent CO problems by GNNs and focus on two specific problems, i.e., mixed integer linear programming and quadratic unconstrained binary optimization. The idea of AutoGNP is to use graph neural architecture search algorithms to automatically find the best GNNs for a given NP-hard combinatorial optimization problem. Compared with existing graph neural architecture search algorithms, AutoGNP utilizes two-hop operators in the architecture search space. Moreover, AutoGNP utilizes simulated annealing and a strict early stopping policy to avoid local optimal solutions. Empirical results on benchmark combinatorial problems demonstrate the superiority of our proposed model.

arXiv:2406.02872•Jun 5, 2024•13 citations

Unsupervised learning with GNNs for QUBO-based combinatorial optimization

Olga Valerevna Krylova, Frank Phillipson

Recent advances in deep learning techniques pose a question of whether they can facilitate the task of finding good quality solutions to combinatorial optimization (CO) problems in a practically relevant solution time. Specifically, it is of practical relevance to determine to which extent graph neural networks (GNNs) can be applied to CO problems that can be formulated as QUBO’s and thus be naturally interpreted as graph problems. In this research a GNNsolver is applied to two classical CO problems–the maximum cut problem and maximum independent set problem–in an unsupervised learning setting. We show that while GNN solver consistently finds good quality solutions for the Max Cut problem irrespective of the size and density of the graph, solving MIS problems is challenging for all but very sparse graphs. We further show how this problem can be addressed by embedding transfer between these two problems and compare two different GNN architectures–GCN and GraphSAGE on their robustness with respect to graph density and symmetry. Finally we demonstrate that change of widely used Adam optimizer to Rprop optimizer can lead to considerable reduction of solution times. • Previously suggested GNNsolver is effective on sparse graphs only. • Replacing Adam with RPROP reduced solution times. • GraphSAGE can handle denser graphs, GCN performs better on sparse graphs. • Transfer learning between MaxCut and MIS problems improves solvers performance.

EURO Journal on Computational Optimization•Jan 1, 2025•3 citations
Along with AI computing shining in scientific discovery, its potential in the combinatorial optimization (CO) domain has also emerged in recent years. Yet, existing unsupervised neural network solvers struggle to solve kkk-grouping problems (e.g., coloring, partitioning) on large-scale graphs and hypergraphs, due to limited computational frameworks. In this work, we propose Deep kkk-grouping, an unsupervised learning-based CO framework. Specifically, we contribute: Novel one-hot encoded polynomial unconstrained binary optimization (OH-PUBO), a formulation for modeling k-grouping problems on graphs and hypergraphs (e.g., graph/hypergraph coloring and partitioning); GPU-accelerated algorithms for large-scale k-grouping CO problems. Deep kkk-grouping employs the relaxation of large-scale OH-PUBO objectives as differentiable loss functions and trains to optimize them in an unsupervised manner. To ensure scalability, it leverages GPU-accelerated algorithms to unify the training pipeline; A Gini coefficient-based continuous relaxation annealing strategy to enforce discreteness of solutions while preventing convergence to local optima. Experimental results demonstrate that Deep kkk-grouping outperforms existing neural network solvers and classical heuristics such as SCIP and Tabu.
Binary (0-1) integer programming (BIP) is pivotal in scientific domains requiring discrete decision-making. As the advance of AI computing, recent works explore neural network-based solvers for integer linear programming (ILP) problems. Yet, they lack scalability for tackling nonlinear challenges. To handle nonlinearities, state-of-the-art Branch-and-Cut solvers employ linear relaxations, leading to exponential growth in auxiliary variables and severe computation limitations. To overcome these limitations, we propose BIPNN (Binary Integer Programming Neural Network), an unsupervised learning framework to solve nonlinear BIP problems via hypergraph neural networks (HyperGNN). Specifically, BIPNN reformulates BIPs-constrained, discrete, and nonlinear (sin, log, exp) optimization problems-into unconstrained, differentiable, and polynomial loss functions. The reformulation stems from the observation of a precise one-to-one mapping between polynomial BIP objectives and hypergraph structures, enabling the unsupervised training of HyperGNN to optimize BIP problems in an end-to-end manner. On this basis, we propose a GPU-accelerated and continuous-annealing-enhanced training pipeline for BIPNN. The pipeline enables BIPNN to optimize large-scale nonlinear terms in BIPs fully in parallel via straightforward gradient descent, thus significantly reducing the training cost while ensuring the generation of discrete, high-quality solutions. Extensive experiments on synthetic and real-world datasets highlight the superiority of our approach.
In recent years, there has been notable interest in investigating combinatorial optimization (CO) problems by neural-based framework. An emerging strategy to tackle these challenging problems involves the adoption of graph neural networks (GNNs) as an alternative to traditional algorithms, a subject that has attracted considerable attention. Despite the growing popularity of GNNs and traditional algorithm solvers in the realm of CO, there is limited research on their integrated use and the correlation between them within an end-to-end framework. The primary focus of our work is to formulate a more efficient and precise framework for CO by employing decision-focused learning on graphs. Additionally, we introduce a decision-focused framework that utilizes GNNs to address CO problems with auxiliary support. To realize an end-to-end approach, we have designed two cascaded modules: (a) an unsupervised trained graph predictive model, and (b) a solver for quadratic binary unconstrained optimization. Empirical evaluations are conducted on various classical tasks, including maximum cut, maximum independent set, and minimum vertex cover. The experimental results on classical CO problems (i.e. MaxCut, MIS, and MVC) demonstrate the superiority of our method over both the standalone GNN approach and classical methods.
In recent years, the advantages of Graph Neural Networks (GNNs) in solving complex combinatorial optimization problems have become more and more obvious. Under this background, this paper demonstrates a method based on GNNs to solve large-scale Unconstrained 0–1 Quadratic Programming (UBQP) problems. Firstly, the UBQP problem models of different combinatorial optimization problems are converted into a unified graph model. This approach makes up for the shortcoming that GNNs cannot be effectively applied to combinatorial optimization problems not based on graph. Secondly, based on Graph Attention Network (GAT) algorithm, this study designs a general GNN model capable of solving UBQP problems. In addition, a random sampling scheme for the complete graph structure is devised, which greatly alleviates the pronounced over-smoothing phenomenon when the model is applied to complete graphs and speeds up the convergence rate. In this paper, a supervised learning approach is adopted to train and test a unified structured model (without changing network parameters) on UBQP problems of varying sizes, and to evaluate the model's generalization ability on high-dimensional UBQP problems. Furthermore, an unsupervised learning mechanism is utilized to train and solve individual sample problems of different dimensions. These experimental results consistently demonstrate that the model and strategy presented in this paper exhibit strong solving ability and generalization ability for combinatorial optimization problems.
Many complex problems encountered in both production and daily life can be conceptualized as combinatorial optimization problems (COPs). Many ad-hoc deep learning methods have been proposed to solve these problems, but there still lacks an effective unified framework. In this work, we take a step towards this goal by designing an unified end-to-end deep reinforcement learning framework named CONQUER. CONQUER first translates various COPs into the unified QUBO (Quadratic Unconstrained Binary Optimization) formalization, and afterwards trains a neural QUBO solver to search high-quality strategies, which are then checked and repaired to obtain the solutions for original COPs. The QUBO solver is a purely data-driven neural model, which does not rely on any expert inputs. We adopt the graph transformer network to represent the QUBO graph, so as to effectively capture the features of problem objective and constraints. The Deep Q-network is utilized to train the QUBO solver to find long-sighted solution strategies. Despite being trained solely on small synthetic graphs, CONQUER exhibits promising generality on much larger instances, and can be easily adapted to real-world datasets. Experimentally, we show that CONQUER achieves the state-of-the-art performances on four COPs over graphs, including minimum vertex cover, maximum independent set, maximum clique and maximum cut problem.
In recent years, graph neural networks (GNNs) have become increasingly popular for solving NP-hard combinatorial optimization (CO) problems, such as maximum cut and maximum independent set. The core idea behind these methods is to represent a CO problem as a graph and then use GNNs to learn the node/graph embedding with combinatorial information. Although these methods have achieved promising results, given a specific CO problem, the design of GNN architectures still requires heavy manual work with domain knowledge. Existing automated GNNs are mostly focused on traditional graph learning problems, which is inapplicable to solving NP-hard CO problems. To this end, we present a new class of \textbf{AUTO}mated \textbf{G}NNs for solving \textbf{NP}-hard problems, namely \textbf{AutoGNP}. We represent CO problems by GNNs and focus on two specific problems, i.e., mixed integer linear programming and quadratic unconstrained binary optimization. The idea of AutoGNP is to use graph neural architecture search algorithms to automatically find the best GNNs for a given NP-hard combinatorial optimization problem. Compared with existing graph neural architecture search algorithms, AutoGNP utilizes two-hop operators in the architecture search space. Moreover, AutoGNP utilizes simulated annealing and a strict early stopping policy to avoid local optimal solutions. Empirical results on benchmark combinatorial problems demonstrate the superiority of our proposed model.
Recent advances in deep learning techniques pose a question of whether they can facilitate the task of finding good quality solutions to combinatorial optimization (CO) problems in a practically relevant solution time. Specifically, it is of practical relevance to determine to which extent graph neural networks (GNNs) can be applied to CO problems that can be formulated as QUBO’s and thus be naturally interpreted as graph problems. In this research a GNNsolver is applied to two classical CO problems–the maximum cut problem and maximum independent set problem–in an unsupervised learning setting. We show that while GNN solver consistently finds good quality solutions for the Max Cut problem irrespective of the size and density of the graph, solving MIS problems is challenging for all but very sparse graphs. We further show how this problem can be addressed by embedding transfer between these two problems and compare two different GNN architectures–GCN and GraphSAGE on their robustness with respect to graph density and symmetry. Finally we demonstrate that change of widely used Adam optimizer to Rprop optimizer can lead to considerable reduction of solution times. • Previously suggested GNNsolver is effective on sparse graphs only. • Replacing Adam with RPROP reduced solution times. • GraphSAGE can handle denser graphs, GCN performs better on sparse graphs. • Transfer learning between MaxCut and MIS problems improves solvers performance.