首页|A unified pre-training and adaptation framework for combinatorial optimization on graphs
A unified pre-training and adaptation framework for combinatorial optimization on graphs
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
万方数据
维普
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.
combinatorial optimizationgraph neural networksdomain adaptationmaximum satisfiability problem
Ruibin Zeng、Minglong Lei、Lingfeng Niu、Lan Cheng
展开 >
School of Computer Science and Technology,University of Chinese Academy of Sciences,Beijing 100049,China
Faculty of Information Technology,Beijing University of Technology,Beijing 100124,China
School of Economics and Management,University of Chinese Academy of Sciences,Beijing 100190,China
School of Mathematics and Statistics,Central South University,Changsha 410075,China
展开 >
National Natural Science Foundation of ChinaNational Natural Science Foundation of ChinaNational Natural Science Foundation of China
万方数据
维普
