A Unified Pre-training and Adaptation Framework for Combinatorial Optimization on Graphs
Not on the map. Why?
Abstract (arXiv)
Combinatorial optimization (CO) on graphs is a classic topic that has been extensively studied across many scientific and industrial fields. Recently, solving CO problems on graphs through learning methods has attracted great attention. Advanced deep learning methods, e.g., graph neural networks (GNNs), have been used to effectively assist the process of solving COs. However, current frameworks based on GNNs are mainly designed for certain CO problems, thereby failing to consider their transferable and generalizable abilities among different COs on graphs. Moreover, simply using original graphs to model COs only captures the direct correlations among objects, which does not consider the mathematical logicality and properties of COs. In this paper, we propose a unified pre-training and adaptation framework for COs on graphs with the help of the maximum satisfiability (Max-SAT) problem. We first use Max-SAT to bridge different COs on graphs since they can be converted to Max-SAT problems represented by standard formulas and clauses with logical information. Then, we further design a pre-training and domain adaptation framework to extract the transferable and generalizable features so that different COs can benefit from them. In the pre-training stage, Max-SAT instances are generated to initialize the parameters of the model. In the fine-tuning stage, instances from CO and Max-SAT problems are used for adaptation so that the transferable ability can be further improved. Numerical experiments on several datasets show that features extracted by our framework exhibit superior transferability and Max-SAT can boost the ability to solve COs on graphs.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 28 of its 59 references that are in the map. First posted on arXiv 16 Dec 2023.
Builds on
28 of 59 references.
References · 28
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
- 2017Graph Attention Networkscited by 8,854
- 2017Inductive Representation Learning on Large Graphscited by 6,284
- 2018How Powerful are Graph Neural Networks?cited by 4,355
- 2017Neural Message Passing for Quantum Chemistrycited by 3,460
- 2018Attention, Learn to Solve Routing Problems!cited by 646
- 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
- 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 313
- 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
- 2022Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNscited by 208
- 2021Learning to Optimize: A Primer and A Benchmarkcited by 206
- 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 182
16 more
- 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 163
- 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
- 2022Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimizationcited by 118
- 2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 107
- 2022Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvaturecited by 96
- 2022Evaluating Explainability for Graph Neural Networkscited by 85
- 2019Exploratory Combinatorial Optimization with Reinforcement Learningcited by 82
- 2019Graph Transfer Learning via Adversarial Domain Adaptation with Graph Convolutioncited by 67
- 2019Graph Neural Networks for Maximum Constraint Satisfactioncited by 46
- 2023Structural Re-weighting Improves Graph Domain Adaptationcited by 45
- 2019Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problemscited by 40
- 2018Domain Adaptation on Graphs by Learning Aligned Graph Basescited by 24
- 2019Experimental performance of graph neural networks on random instances of max-cutcited by 15
- 2023Contrastive Graph Prompt-tuning for Cross-domain Recommendationcited by 9
- 2021Can Graph Neural Networks Learn to Solve MaxSAT Problem?cited by 5
- 2022Self-Supervised Graph Neural Network for Multi-Source Domain Adaptationcited by 5
Built on by
Citing papers per year: 2026: 1.
1 paper.