Hybrid Learning with New Value Function for the Maximum Common Induced Subgraph Problem


  • Yanli Liu Wuhan university of science and technology
  • Jiming Zhao Wuhan University of Science and Technology
  • Chu-Min Li MIS, University of Picardie Jules Verne
  • Hua Jiang Engineering Research Center of Cyberspace & School of Software, Yunnan University
  • Kun He Huazhong University of Science and Technology




CSO: Constraint Optimization, CSO: Constraint Satisfaction, CSO: Search, SO: Heuristic Search


Maximum Common Induced Subgraph (MCIS) is an important NP-hard problem with wide real-world applications. An efficient class of MCIS algorithms uses Branch-and-Bound (BnB), consisting in successively selecting vertices to match and pruning when it is discovered that a solution better than the best solution found so far does not exist. The method of selecting the vertices to match is essential for the performance of BnB. In this paper, we propose a new value function and a hybrid selection strategy used in reinforcement learning to define a new vertex selection method, and propose a new BnB algorithm, called McSplitDAL, for MCIS. Extensive experiments show that McSplitDAL significantly improves the current best BnB algorithms, McSplit+LL and McSplit+RL. An empirical analysis is also performed to illustrate why the new value function and the hybrid selection strategy are effective.




How to Cite

Liu, Y., Zhao, J., Li, C.-M., Jiang, H., & He, K. (2023). Hybrid Learning with New Value Function for the Maximum Common Induced Subgraph Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 37(4), 4044-4051. https://doi.org/10.1609/aaai.v37i4.25519



AAAI Technical Track on Constraint Satisfaction and Optimization