A Learning based Branch and Bound for Maximum Common Subgraph Problems

2019/05/15 by Yanli Liu, Chu-Min Li, Liu, Yan-li +5
Computer Science · #Complexity and Algorithms in Graphs #Computer Vision and Pattern Recognition (cs.CV) #Constraint Satisfaction and Optimization #F.2.2 #FOS: Computer and information sciences #Graph Theory and Algorithms #I.5.2 #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · pdf · doi:10.48550/arxiv.1905.05840

openalex publication_date 2019/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Branch-and-bound (BnB) algorithms are widely used to solve combinatorial problems, and the performance crucially depends on its branching heuristic.In this work, we consider a typical problem of maximum common subgraph (MCS), and 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.Extensive experiments show that our method is beneficial and outperforms current best BnB algorithm for the MCS.

Related

• A Strengthened Branch and Bound Algorithm for the Maximum Common (Connected) Subgraph Problem
• Hybrid Learning with New Value Function for the Maximum Common Subgraph Problem
• TreeDQN: Learning to minimize Branch-and-Bound tree
• Learning to Branch
• Targeted Branching for the Maximum Independent Set Problem Using Graph Neural Networks