A Learning Based Branch and Bound for Maximum Common Subgraph Related Problems
Yanli Liu, Chu-Min Li, Hua Jiang, Kun He
Abstract
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.
Topics & Concepts
Subgraph isomorphism problemInduced subgraph isomorphism problemHeuristicBranching (polymer chemistry)Branch and boundComputer scienceTree (set theory)Reinforcement learningSearch treeUpper and lower boundsMathematicsMathematical optimizationAlgorithmCombinatoricsArtificial intelligenceGraphSearch algorithmLine graphChemistryOrganic chemistryVoltage graphMathematical analysisGraph Theory and AlgorithmsAdvanced Graph Neural NetworksComplexity and Algorithms in Graphs