2020
AAAI
AAAI 2020
A Learning Based Branch and Bound for Maximum Common Subgraph Related Problems
Abstract
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.
🌉
Interdisciplinary Bridge
— Computer Science and Deep Learning and Machine Learning and Mathematics & Optimization and Reinforcement Learning
🐝
Cross-Pollinator
— Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics, Security & Privacy, Speech & Audio
Authors
Topics
Machine Learning > Optimization & Theory > Optimization
Deep Learning > Architectures > Neural Networks
Reinforcement Learning > Methods > Deep RL
Reinforcement Learning > Methods > Policy Learning
Mathematics & Optimization > Mathematics > Graph Theory
Computer Science > Foundations > Algorithms
Machine Learning > Learning Types > Reinforcement Learning