Deep k-grouping: An Unsupervised Learning Framework for Combinatorial Optimization on Graphs and Hypergraphs
Preprint
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.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Neural Network-Based Dimensionality Reduction for Large-Scale Binary Optimization With Millions of VariablesIEEE Transactions on Evolutionary Computation, 2024
- MaPart: An Efficient Multi-FPGA System-Aware Hypergraph Partitioning FrameworkIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2024
- K-SpecPart: Supervised Embedding Algorithms and Cut Overlay for Improved Hypergraph PartitioningIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2023
- Hypergraph-Based Interference Avoidance Resource Management in Customer-Centric Communication for Intelligent Cyber-Physical Transportation SystemsIEEE Transactions on Consumer Electronics, 2023
- Quantum bridge analytics I: a tutorial on formulating and using QUBO modelsAnnals of Operations Research, 2022
- Hypergraph Partitioning With EmbeddingsIEEE Transactions on Knowledge and Data Engineering, 2020
- Coloring-Based Channel Allocation for Multiple Coexisting Wireless Body Area Networks: A Game-Theoretic ApproachIEEE Transactions on Mobile Computing, 2020
- UAV-Assisted Emergency Communications in Social IoT: A Dynamic Hypergraph Coloring ApproachIEEE Internet of Things Journal, 2020
- HEPart: A balanced hypergraph partitioning algorithm for big data applicationsFuture Generation Computer Systems, 2018
- Stochastic shadow detection using a hypergraph partitioning approachPattern Recognition, 2017