Hybrid Learning with New Value Function for the Maximum Common Induced Subgraph Problem

Yanli Liu, Jiming Zhao, Chu-Min Li, Hua Jiang, Kun HeAAAI 2023 · OpenReview

Abstract: Maximum Common Induced Subgraph (MCIS) is an important NP-hard problem with wide real-world applications. An efficient class of MCIS algorithms uses Branch-and-Bound (BnB), consisting in successively selecting vertices to match and pruning when it is discovered that a solution better than the best solution found so far does not exist. The method of selecting the vertices to match is essential for the performance of BnB. In this paper, we propose a new value function and a hybrid selection strategy used in reinforcement learning to define a new vertex selection method, and propose a new BnB algorithm, called McSplitDAL, for MCIS. Extensive experiments show that McSplitDAL significantly improves the current best BnB algorithms, McSplit+LL and McSplit+RL. An empirical analysis is also performed to illustrate why the new value function and the hybrid selection strategy are effective.

Introduction

The Maximum Common Induced Subgraph (MCIS) problem is a fundamental challenge in computer science, requiring the identification of the largest possible subgraph that appears identically in two given graphs. This problem is critical for diverse applications, including chemoinformatics for molecular comparison, computer vision for pattern matching, and cybersecurity for malware detection.

Because MCIS is NP-hard, state-of-the-art solvers typically employ Branch-and-Bound (BnB) algorithms. These solvers explore a search tree by "branching" (selecting pairs of vertices to match) and "bounding" (pruning branches that cannot improve upon the current best solution). The efficiency of these algorithms hinges on the branching heuristic—the strategy used to decide which vertex pair to explore next.

Addressing Limitations in Learning-to-Branch

Recent advancements have introduced Reinforcement Learning (RL) to optimize branching heuristics. However, existing RL methods suffer from two primary flaws:

  1. Narrow Focus: They prioritize actions that reduce the mathematical upper bound ($UB$), often ignoring how much an action simplifies the remaining graph structure.
  2. The Matthew Effect: RL policies often fall into a "rich-get-richer" cycle, repeatedly favoring a small set of high-reward vertices. This leads to local optima, where the solver wastes significant time in unproductive regions of the search tree.

The McSplitDAL Framework

The authors introduce McSplitDAL, which incorporates two key innovations to overcome these hurdles:

1. Domain Action Learning (DAL) Value Function

Unlike standard RL rewards based solely on $UB$ reduction, the DAL value function considers Environment Change. It rewards actions that increase the number of "domains" (vertex subsets). In the McSplit framework, splitting a large domain into many smaller ones simplifies the subproblem. By rewarding this "shattering" of the graph, the algorithm prioritizes actions that make the remaining problem more manageable.

2. Hybrid Branching Policy

To combat the Matthew Effect, McSplitDAL utilizes a switching mechanism between two policies: a traditional RL policy focused on upper bounds and the new DAL policy focused on simplification. The solver alternates between these policies based on a fixed threshold ($MaxNbApp$), resetting only when a new "best" solution is found. This hybridization forces search diversity, preventing the agent from becoming trapped in predictable, suboptimal paths.

Key Insights: Proving vs. Finding

A critical distinction in combinatorial search is the time taken to find an optimal solution versus the time taken to prove its optimality. McSplitDAL excels at both. By diversifying the search, it finds high-quality solutions faster and uses its domain-splitting reward to prune the search tree more effectively during the proof phase.

McSplitDAL significantly reduces the number of recursive calls required to prove optimality compared to state-of-the-art baselines.

Experimental Results

The algorithm was evaluated on a massive dataset of 24,761 instances, including biochemical reactions and large-scale real-world image and network data.

Key findings include: * Superior Scalability: McSplitDAL solved 292 more instances than the previous state-of-the-art, McSplit+LL, representing a 16.3% improvement. * Search Efficiency: The number of recursive calls—a direct measure of the search tree size—was significantly lower for McSplitDAL, confirming the effectiveness of the DAL value function in pruning unproductive branches.

McSplitDAL outperforms existing algorithms in both finding and total runtime across thousands of instances.

Conclusion

McSplitDAL represents a significant step forward for MCIS solvers by recognizing that graph simplification is as valuable a reward as upper-bound reduction. While the current switching threshold is a fixed hyperparameter, future work may involve dynamic policy selection using machine learning to further optimize search performance across different graph topologies.

Summary updated

Abstract

Maximum Common Induced Subgraph (MCIS) is an important NP-hard problem with wide real-world applications. An efficient class of MCIS algorithms uses Branch-and-Bound (BnB), consisting in successively selecting vertices to match and pruning when it is discovered that a solution better than the best solution found so far does not exist. The method of selecting the vertices to match is essential for the performance of BnB. In this paper, we propose a new value function and a hybrid selection strategy used in reinforcement learning to define a new vertex selection method, and propose a new BnB algorithm, called McSplitDAL, for MCIS. Extensive experiments show that McSplitDAL significantly improves the current best BnB algorithms, McSplit+LL and McSplit+RL. An empirical analysis is also performed to illustrate why the new value function and the hybrid selection strategy are effective.
BibTeX
@inproceedings{liu2023hybrid,
  author = {Yanli Liu and Jiming Zhao and Chu-Min Li and Hua Jiang and Kun He},
  title = {{Hybrid Learning with New Value Function for the Maximum Common Induced Subgraph Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=WV8gd1m0Nxa},
}
Figure