A Learning Based Branch and Bound for Maximum Common Subgraph Related Problems
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.
Cite
Text
Liu et al. "A Learning Based Branch and Bound for Maximum Common Subgraph Related Problems." AAAI Conference on Artificial Intelligence, 2020. doi:10.1609/AAAI.V34I03.5619Markdown
[Liu et al. "A Learning Based Branch and Bound for Maximum Common Subgraph Related Problems." AAAI Conference on Artificial Intelligence, 2020.](https://mlanthology.org/aaai/2020/liu2020aaai-learning/) doi:10.1609/AAAI.V34I03.5619BibTeX
@inproceedings{liu2020aaai-learning,
title = {{A Learning Based Branch and Bound for Maximum Common Subgraph Related Problems}},
author = {Liu, Yanli and Li, Chu-Min and Jiang, Hua and He, Kun},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2020},
pages = {2392-2399},
doi = {10.1609/AAAI.V34I03.5619},
url = {https://mlanthology.org/aaai/2020/liu2020aaai-learning/}
}