Maximum common induced subgraph algorithm based on vertex conflict learning

doi:10.11772/j.issn.1001-9081.2020091381

Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (6): 1756-1760.DOI: 10.11772/j.issn.1001-9081.2020091381

Special Issue: 先进计算

• Advanced computing • Previous Articles Next Articles

Maximum common induced subgraph algorithm based on vertex conflict learning

WANG Yu¹, LIU Yanli^1,2, CHEN Shaowu¹

1. College of Science, Wuhan University of Science and Technology, Wuhan Hubei 430081, China;
2. Hubei Province Key Laboratory of Systems Science in Metallurgical Process(Wuhan University of Science and Technology), Wuhan Hubei 430081, China

Received:2020-09-07 Revised:2020-11-02 Online:2021-06-10 Published:2020-11-16
Supported by:
This work is partially supported by the Innovative Training Program for College Students of Hubei (S201910488044), the Open Funds of Hubei Province Key Laboratory of Systems Science in Metallurgical Process (Y201716).

基于顶点冲突学习的最大公共子图算法

王宇¹, 刘燕丽^1,2, 陈劭武¹

1. 武汉科技大学理学院, 武汉 430081;
2. 冶金工业过程系统科学湖北省重点实验室(武汉科技大学), 武汉 430081

通讯作者: 刘燕丽
作者简介:王宇(1999-),男,湖北汉川人,主要研究方向:最大公共子图问题;刘燕丽(1980-),女,河南西平人,副教授,博士,CCF会员,主要研究方向:组合优化问题求解、算法设计;陈劭武(1999-),男,湖北武汉人,主要研究方向:最大公共子图问题。
基金资助:
湖北省大学生创新训练项目（S201910488044）；冶金工业过程系统科学湖北重点实验室开放基金资助项目（Y201716）。

Abstract

Abstract: The traditional branching strategies of Maximum Common induced Subgraph (MCS) problem rely on the static properties of graphs and lack learning information about historical searches. In order to solve these problems, a branching strategy based on vertex conflict learning was proposed. Firstly, the reduction value of the upper bound was used as the reward to the branch node for completing a matching action. Secondly, when the optimal solution was updated, the optimal solution obtained actually was the result of continuous inference of the branch nodes. Therefore, the appropriate rewards were given to the branch nodes on the complete search path to strengthen the positive effect of these vertices on search. Finally, the value function of matching action was designed, and the vertices with the maximum cumulative rewards would be selected as new branch nodes. On the basis of Maximum common induced subgraph Split (McSplit) algorithm, an improved McSplit Reinforcement Learning and Routing (McSplitRLR) algorithm combined with the new branching strategy was completed. Experimental results show that, with the same computer and solution time limit, excluding the simple instances solved by all comparison algorithms within 10 seconds, compared to the state-of-the-art algorithms of McSplit and McSplit Solution-Biased Search (McSplitSBS), McSplitRLR solves 109 and 33 more hard instances respectively, and the solution rate increases by 5.6% and 1.6% respectively.

Key words: combinatorial optimization problem, Non-deterministic Polynomial Hard (NP-Hard) problem, reinforcement learning, algorithm design, Maximum Common induced Subgraph (MCS)

摘要： 针对最大公共子图（MCS）的传统分支策略依赖于图的静态属性，缺少学习历史搜索信息的问题，提出了基于顶点冲突学习的分支策略。首先，把上界的减少值作为分支点完成匹配动作的奖励；其次，由于当最优解被更新时，得到的最优解是分支点不断推理产生的结果，因此给予在完整的搜索路径上的分支点适当的奖励，从而强化这些顶点对搜索的积极作用；最后，设计了匹配动作的价值函数，并选择具有最大累计奖励的顶点作为新的分支点。在McSplit算法基础上，提出了糅合新分支策略的McSplitRLR算法。实验结果表明，除去均可以被所有对比算法在10 s之内解决的简单算例，在相同机器和求解限制时间条件下，相较当前先进的算法McSplit、McSplitSBS，McSplitRLR分别多解决了109、33个困难算例，求解率分别提高了5.6%、1.6%。

关键词: 组合优化问题, NP-Hard问题, 强化学习, 算法设计, 最大公共子图

CLC Number:

TP301.6

WANG Yu, LIU Yanli, CHEN Shaowu. Maximum common induced subgraph algorithm based on vertex conflict learning[J]. Journal of Computer Applications, 2021, 41(6): 1756-1760.

王宇, 刘燕丽, 陈劭武. 基于顶点冲突学习的最大公共子图算法[J]. 计算机应用, 2021, 41(6): 1756-1760.

References

[1] 祝园园, 秦璐, 于旭. 图匹配问题的应用和研究[J]. 中国计算科学会通讯, 2012, 8(11):21-27.(ZHU Y Y,QIN L,YU X. Application and research of graph matching problem[J]. Communications of the CCF,2012,8(11):21-27.)
[2] KRIEGE N M,DROSCHINSKY A,MUTZEL P. A note on blockand-bridge preserving maximum common subgraph algorithms for outerplanar graphs[J]. Journal of Graph Algorithms and Applications,2018,22(4):607-616.
[3] KATSAROU F, NTARMOS N, TRIANTAFILLOU P. Hybrid algorithms for subgraph pattern queries in graph databases[C]//Proceedings of the 2017 IEEE International Conference on Big Data. Piscataway:IEEE,2017:656-665.
[4] GIUGNO R,BONNICI V,BOMBIERI N,et al. GRAPES:a software for parallel searching on biological graphs targeting multicore architectures[J]. PLoS ONE,2013,8(10):Article No. e76911.
[5] WEI F,ZOU W X. Suboptimal network coding subgraph algorithms for 5G minimum-cost multicast networks[J]. Frontiers of Information Technology and Electronic Engineering,2018,19(5):662-673.
[6] SOLNON C,DAMIAND G,DE LA HIGUERA C,et al. On the complexity of submap isomorphism and maximum common submap problems[J]. Pattern Recognition,2015,48(2):302-316.
[7] 冯朔, 申德荣, 聂铁铮, 等. 一种基于最大公共子图的社交网络对齐方法[J]. 软件学报, 2019, 30(7):2175-2187.(FENG S,SHEN D R,NIE T Z,et al. Maximum common subgraph based social network alignment method[J]. Journal of Software,2019,30(7):2175-2187.)
[8] MCGREGOR J J. Backtrack search algorithms and the maximal common subgraph problem[J]. Software:Practice and Experience,1982,12(1):23-34.
[9] KRISSINEL E B,HENRICK K. Common subgraph isomorphism detection by backtracking search[J]. Software:Practice and Experience,2004,34(6):591-607.
[10] ABU-KHZAM F N,SAMATOVA N F,RIZK M A,et al. The maximum common subgraph problem:faster solutions via vertex cover[C]//Proceedings of the 2007 IEEE/ACS International Conference on Computer Systems and Applications. Piscataway:IEEE,2007:367-373.
[11] MCCREESH C, PROSSER P, TRIMBLE J. A partitioning algorithm for maximum common subgraph problems[C]//Proceedings of the 2017 26th International Joint Conference on Artificial Intelligence. Menlo Park:AAAI Press,2017:712-719.
[12] SOLNON C. AllDifferent-based filtering for subgraph isomorphism[J]. Artificial Intelligence,2010,174(12/13):850-864.
[13] 陈学松, 杨宜民. 强化学习研究综述[J]. 计算机应用研究, 2010,27(8):2834-2838,2844. (CHEN X S,YANG Y M. Reinforcement learning:survey of recent work[J]. Application Research of Computers,2010,27(8):2834-2838,2844.)
[14] SUTTON R S, BARTO A G. Reinforcement Learning:an Introduction[M]. 2nd ed. Cambridge:MIT Press,2018:6-30.
[15] FRANÇOIS-LAVET V,HENDERSON P,ISLAM R,et al. An introduction to deep reinforcement learning[J]. Foundations and Trends in Machine Learning,2018,11(3/4):219-354.
[16] ARCHIBALD B,DUNLOP F,HOFFMANN R,et al. Sequential and parallel solution-biased search for subgraph algorithms[C]//Proceedings of the 2019 16th International Conference on Integration of Constraint Programming,Artificial Intelligence,and Operations Research, LNCS 11494. Cham:Springer, 2019:20-38.

Maximum common induced subgraph algorithm based on vertex conflict learning

基于顶点冲突学习的最大公共子图算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	SHANG Fangjian, LI Xin, Di ZHAI, LU Yang, ZHANG Donglei, QIAN Yuwen. Two-phase resource allocation technology for network slices in smart grid [J]. Journal of Computer Applications, 2021, 41(7): 2033-2038.
[2]	WANG Jianping, WANG Gang, MAO Xiaobin, MA Enqi. Motion control method of two-link manipulator based on deep reinforcement learning [J]. Journal of Computer Applications, 2021, 41(6): 1799-1804.
[3]	DU Xixi, CHENG Hua, FANG Yiquan. Reinforced automatic summarization model based on advantage actor-critic algorithm [J]. Journal of Computer Applications, 2021, 41(3): 699-705.
[4]	WANG Zekun, HE Yichao, LI Huanzhe, ZHANG Fazhan. Binary particle swarm optimization algorithm based on novel S-shape transfer function for knapsack problem with a single continuous variable [J]. Journal of Computer Applications, 2021, 41(2): 461-469.
[5]	LIU Sijia, TONG Xiangrong. Urban transportation path planning based on reinforcement learning [J]. Journal of Computer Applications, 2021, 41(1): 185-190.
[6]	YAO Xinghu, TAN Xiaoyang. Reward highway network based global credit assignment algorithm in multi-agent reinforcement learning [J]. Journal of Computer Applications, 2021, 41(1): 1-7.
[7]	FU Kui, LIANG Shaoqing, LI Bing. Commodity recommendation model based on improved deep Q network structure [J]. Journal of Computer Applications, 2020, 40(9): 2613-2621.
[8]	HU Xuemin, CHENG Yu, CHEN Guowen, ZHANG Ruohan, TONG Xiuchi. Motion planning for autonomous driving with directional navigation based on deep spatio-temporal Q-network [J]. Journal of Computer Applications, 2020, 40(7): 1919-1925.
[9]	ZHENG Yanbin, FAN Wenxin, HAN Mengyun, TAO Xueli. Multi-agent collaborative pursuit algorithm based on game theory and Q-learning [J]. Journal of Computer Applications, 2020, 40(6): 1613-1620.
[10]	REN Na, ZHANG Nan, CUI Yan, ZHANG Rongxue, PANG Xinfu. Method of semantic entity construction and trajectory control for UAV electric power inspection [J]. Journal of Computer Applications, 2020, 40(10): 3095-3100.
[11]	CHI Yaping, MO Chongwei, YANG Yintan, CHEN Chunxia. Design and implementation of intrusion detection model for software defined network architecture [J]. Journal of Computer Applications, 2020, 40(1): 116-122.
[12]	CHEN Jiafeng, TENG Chong. Joint entity and relation extraction model based on reinforcement learning [J]. Journal of Computer Applications, 2019, 39(7): 1918-1924.
[13]	SHU Lingzhou, WU Jia, WANG Chen. Urban traffic signal control based on deep reinforcement learning [J]. Journal of Computer Applications, 2019, 39(5): 1495-1499.
[14]	WANG Tiantian, YU Shuangyuan, XU Baomin. Research on proof of work mining dilemma based on policy gradient algorithm [J]. Journal of Computer Applications, 2019, 39(5): 1336-1342.
[15]	SHA Zongxuan, XUE Fei, ZHU Jie. Scheduling strategy of cloud robots based on parallel reinforcement learning [J]. Journal of Computer Applications, 2019, 39(2): 501-508.