• 综合
  • 标题
  • 关键词
  • 摘要
  • 学者
  • 期刊-刊名
  • 期刊-ISSN
  • 会议名称
搜索

作者:

Zeng, Ruibin (Zeng, Ruibin.) | Lei, Minglong (Lei, Minglong.) | Niu, Lingfeng (Niu, Lingfeng.) | Cheng, Lan (Cheng, Lan.)

收录:

Scopus SCIE

摘要:

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.

关键词:

graph neural networks domain adaptation combinatorial optimization maximum satisfiability problem

作者机构:

  • [ 1 ] [Zeng, Ruibin]Univ Chinese Acad Sci, Sch Comp Sci & Technol, Beijing 100049, Peoples R China
  • [ 2 ] [Lei, Minglong]Beijing Univ Technol, Fac Informat Technol, Beijing 100124, Peoples R China
  • [ 3 ] [Niu, Lingfeng]Univ Chinese Acad Sci, Sch Econ & Management, Beijing 100190, Peoples R China
  • [ 4 ] [Cheng, Lan]Cent South Univ, Sch Math & Stat, Changsha 410075, Peoples R China

通讯作者信息:

  • [Cheng, Lan]Cent South Univ, Sch Math & Stat, Changsha 410075, Peoples R China

查看成果更多字段

相关关键词:

来源 :

SCIENCE CHINA-MATHEMATICS

ISSN: 1674-7283

年份: 2024

期: 6

卷: 67

页码: 1439-1456

1 . 4 0 0

JCR@2022

被引次数:

WoS核心集被引频次:

SCOPUS被引频次: 1

ESI高被引论文在榜: 0 展开所有

万方被引频次:

中文被引频次:

近30日浏览量: 1

归属院系:

在线人数/总访问数:419/4899660
地址:北京工业大学图书馆(北京市朝阳区平乐园100号 邮编:100124) 联系我们:010-67392185
版权所有:北京工业大学图书馆 站点建设与维护:北京爱琴海乐之技术有限公司