A Learning Based Branch and Bound for Maximum Common Subgraph Related Problems

The performance of a branch-and-bound (BnB) algorithm for maximum common subgraph (MCS) problem and its related problems, like maximum common connected subgraph (MCCS) and induced Subgraph Isomorphism (SI), crucially depends on the branching heuristic. We propose a branching heuristic inspired from reinforcement learning with a goal of reaching a tree leaf as early as possible to greatly reduce the search tree size. Experimental results show that the proposed heuristic consistently and significantly improves the current best BnB algorithm for the MCS, MCCS and SI problems. An analysis is carried out to give insight on why and how reinforcement learning is useful in the new branching heuristic.

Authors

• Yanli Liu Wuhan university of science and technology
• Chu-Min Li Aix Marseille Université Université de Picardie Jules-Verne
• Hua Jiang Engineering Research Center of Cyberspace & School of Software, Yunnan University
• Kun He Huazhong University of Sceince and Technology

Keywords

No keywords are indexed for this paper.