Learning to Bound for Maximum Common Subgraph Algorithms

Buddhi W. Kothalawala, Henning Koehler, Qing WangCP 2025 · DOI

TL;DR

This paper introduces a novel, tighter upper bound for the Maximum Common Subgraph (MCS) problem, significantly improving the efficiency of branch-and-bound algorithms like McSplit. By leveraging graph degree sequences and a reinforcement learning approach to strategically apply this bound, the authors achieve substantial reductions in search space exploration and solve more challenging instances.

What Problem Does This Paper Address?

The Maximum Common Subgraph (MCS) problem, which aims to find the largest subgraph common to two given graphs, is a fundamental and computationally challenging NP-hard problem. While exact algorithms like branch-and-bound (BnB) exist, their efficiency heavily relies on effective pruning of the search space. Existing state-of-the-art BnB algorithms, such as McSplit, use heuristics to guide their search, but their upper bounding mechanisms are often too generous, leading to inefficient exploration. Recent advancements have focused on improving the branching strategies (how to choose the next vertex pair to match), but this paper argues that improving the bounding heuristic is crucial for further accelerating the search. The core challenge is to develop a tighter upper bound that is still computationally feasible and can be effectively integrated into existing search frameworks.

Methods

The paper proposes a two-pronged approach:

  1. A Tighter Upper Bound (Degree Sequence Bound - DSB): Instead of relying on simple vertex counts (like min(|Vi|, |U1|) in McSplit), the authors derive a new upper bound based on the degree sequences of induced subgraphs within bidomains. This leverages more detailed structural information about the graphs. Theorem 4 provides the theoretical foundation, showing how degree sums can bound the size of common subgraphs. This new bound, denoted as UBdsb, is shown to be tighter than the original McSplit bound.
  2. Reinforcement Learning (RL) for Strategic Bound Application: Since computing the new DSB is more computationally expensive than the original bound, the authors propose an RL framework to decide when to apply it. An agent learns to predict which bidomains are most likely to benefit from the tighter bound, thus maximizing pruning efficiency. The RL agent uses a reward function based on the bound gap (difference between McSplit's bound and the DSB) and a value function to guide its decisions. This approach aims to apply the expensive bound only in high-potential pruning regions.

The paper also introduces enhanced versions of existing RL-based McSplit extensions (McSplit+RL, McSplit+LL, McSplit+DAL) by integrating the DSB, resulting in McSplit+DSB, McSplit+RL+DSB, McSplit+LL+DSB, and McSplit+DAL+DSB.

Datasets

The authors evaluate their approach on several standard benchmark datasets for the MCS problem:

  • Images-PR15: 24 pairs from segmented images.
  • Images CVIU11: 6,278 graph pairs.
  • Meshes CVIU11: 3,018 graph pairs.
  • LV dataset: 2,352 pairs.
  • LargerLV extension: 3,430 pairs.
  • Scalefree dataset: 100 pairs.
  • SI dataset: 1,170 pairs.
  • Phase dataset: 200 Erdos-Rényi graph pairs.

No new datasets were introduced.

Key Insights and Ideas

  • Structure Matters More Than Size: The core insight is that the degree sequence of a subgraph provides a much more informative signal for bounding the MCS than simply its vertex count. This is because degrees reveal connectivity patterns, which are directly relevant to isomorphism.
  • The "Bound Gap" is Key: The difference between the original McSplit bound and the new DSB (termed the "bound gap") is a crucial metric. This gap represents the potential for pruning and is used as the reward signal in the RL framework.
  • Strategic Application is Crucial: The DSB is computationally more expensive. The RL component is essential for making this tighter bound practical by intelligently deciding when to use it, avoiding unnecessary computation.
  • RL Can Interfere with Learning: While the DSB generally improves performance, integrating it with existing RL-based branching heuristics can sometimes disrupt their learning process, leading to fewer branches explored by the original algorithm in rare cases. This highlights a nuanced trade-off.

Key Results

  • Improved Performance: McSplit+DSB outperforms the baseline McSplit, solving a greater number of moderate instances and achieving a 3.41% improvement in solved instances within a 1800-second time limit.
  • Reduced Branching: Figure 4 demonstrates that the DSB consistently reduces the number of search branches explored across various algorithms (McSplit, McSplit+RL, McSplit+LL, McSplit+DAL) compared to their baseline versions.
  • Closer to Oracle: Figure 3 shows that the DSB's bound reduction closely approximates that of an "oracle" (which uses the true MCS size for bounding), indicating its effectiveness in tightening bounds.
  • Effective on Hard Instances: Table 2 shows that the proposed method consistently finds larger common subgraphs on "hard" instances (those unsolved within the time limit), which can then be used as better lower bounds for pruning.
  • Low Activation Frequency: The new bound was activated in only about 1.64% of the cases, demonstrating the RL agent's efficiency in selecting opportune moments for its application.

Limitations and Future Work

Limitations:

  • Computational Cost of DSB: The new bound calculation is more computationally intensive than the original McSplit bound, necessitating the RL strategy for efficient application.
  • Potential RL Disruption: In some cases, integrating the DSB with RL-based branching heuristics can disrupt the learning process of those heuristics, leading to fewer branches explored by the original algorithm in rare instances.

Future Work:

  • Extending to Related Problems: The principles of the DSB could be applied to other combinatorial search problems like subgraph isomorphism.
  • Exploring Other Graph Properties: Investigating additional graph properties beyond degree sequences could lead to even tighter bounds.
  • Alternative Learning Paradigms: Exploring different learning approaches for more efficient application of improved bounds could further enhance performance.

Summary updated

BibTeX
@inproceedings{kothalawala2025learning,
  author = {Buddhi W. Kothalawala and Henning Koehler and Qing Wang},
  title = {{Learning to Bound for Maximum Common Subgraph Algorithms}},
  booktitle = {CP},
  year = {2025},
  doi = {10.4230/lipics.cp.2025.22},
}
Figure