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

• URL: http://arxiv.org/abs/2505.20972v1
• Date: Tue, 27 May 2025 10:04:54 GMT
• Title: Deep k-grouping: An Unsupervised Learning Framework for Combinatorial Optimization on Graphs and Hypergraphs
• Authors: Sen Bai, Chunqi Yang, Xin Bai, Xin Zhang, Zhengang Jiang,
• Abstract summary: Existing unsupervised neural network solvers struggle to solve $k$-grouping problems.<n>In this work, we propose Deep $k$-grouping, an unsupervised learning-based framework.
• Score: 2.244324685724497
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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.

Related papers

• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization.<n>We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution.<n>Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
  arXiv  Detail & Related papers  (2025-02-07T15:57:56Z)
• Brain-inspired Chaotic Graph Backpropagation for Large-scale Combinatorial Optimization [3.97492577026225]
  Graph neural networks (GNNs) with unsupervised learning can solve large-scale optimization problems (COPs) with efficient time complexity.<n>However, the current mainstream backpropagation-based training algorithms are prone to fall into local minima.<n>We introduce a chaotic training algorithm, i.e. chaotic graph backpropagation (CGBP), which makes the training process not only chaotic but also highly efficient.
  arXiv  Detail & Related papers  (2024-12-13T05:00:57Z)
• Assessing and Enhancing Graph Neural Networks for Combinatorial Optimization: Novel Approaches and Application in Maximum Independent Set Problems [0.0]
  Graph Neural Networks (GNNs) show promise for researchers in solving Combinatorial optimization (CO) problems. This study investigates the effectiveness of GNNs in solving the maximum independent set (MIS) problem.
  arXiv  Detail & Related papers  (2024-11-06T09:12:31Z)
• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  We introduce a novel algorithm, denoted hereafter as QRF-GNN, leveraging the power of GNNs to efficiently solve Combinatorial optimization (CO) problems. It relies on unsupervised learning by minimizing the loss function derived from QUBO relaxation. Results of experiments show that QRF-GNN drastically surpasses existing learning-based approaches and is comparable to the state-of-the-art conventionals.
  arXiv  Detail & Related papers  (2024-07-23T13:34:35Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  An emerging strategy to tackle optimization problems involves the adoption of graph neural networks (GNNs) as an alternative to traditional algorithms. 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. We introduce a decision-focused framework that utilizes GNNs to address CO problems with auxiliary support.
  arXiv  Detail & Related papers  (2024-06-05T22:52:27Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  We propose a graph gradual pruning framework termed CGP to dynamically prune GNNs. Unlike LTH-based methods, the proposed CGP approach requires no re-training, which significantly reduces the computation costs. Our proposed strategy greatly improves both training and inference efficiency while matching or even exceeding the accuracy of existing methods.
  arXiv  Detail & Related papers  (2022-07-18T14:23:31Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  We propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity.
  arXiv  Detail & Related papers  (2021-06-09T09:18:18Z)
• Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs [35.14404918074861]
  This work proposes an unsupervised learning framework for Combinatorial optimization problems on graphs. Inspired by Erdos' probabilistic method, we use a neural network to parametrize a probability distribution over sets. We show that when the network is optimized w.r.t. a suitably chosen loss, the learned distribution contains, with controlled probability, a low-cost integral solution.
  arXiv  Detail & Related papers  (2020-06-18T16:13:36Z)
• Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
  We present a new class of geometrically-driven optimization algorithms on the orthogonal group $O(d)$. We show that our methods can be applied in various fields of machine learning including deep, convolutional and recurrent neural networks, reinforcement learning, flows and metric learning.
  arXiv  Detail & Related papers  (2020-03-30T15:37:50Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  Graph representation learning has achieved a remarkable success in many graph-based applications, such as node classification, prediction, and community detection. However, for some kind of graph applications, such as graph compression and edge partition, it is very hard to reduce them to some graph representation learning tasks. In this paper, we propose to attack the graph ordering problem behind such applications by a novel learning approach.
  arXiv  Detail & Related papers  (2020-01-18T09:14:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.