Learning to Bound for Maximum Common Subgraph Algorithms

McCreesh et al. [16] propose a BnB algorithm to solve the MCIS problem, called McSplit. Given two graphs $G$ and $H$, McSplit solves the MCIS problem by finding a maximum-cardinality mapping $M^{\ast }=\{(v_1,u_1),\mathrm{\dots },(v_m,u_m)\}$, where all $v_i\in V(G)$ and $u_i\in V(H)$ are distinct from one another and satisfy the condition $(v_i,v_j)\in E(G)\iff (u_i,u_j)\in E(H)$ for any $v_i,v_j$ with $1\le i\ne j\le m$. Each vertex pair $(v_i,u_i)\in M^{\ast }$ is called a matching vertex pair. Such a maximum-cardinality mapping corresponds to the maximum common subgraphs $G[V^{\ast }]$ and $H[U^{\ast }]$ of $G$ and $H$, where $V^{\ast }=\{v_1,\mathrm{\dots },v_m\}$ and $U^{\ast }=\{u_1,\mathrm{\dots },u_m\}$.

To find a maximum-cardinality mapping between $G$ and $H$, McSplit employs a depth-first search, starting with the empty mapping. It then iteratively extends the mapping with matching vertex pairs, adding one pair at each iteration until no further extensions are possible. The key idea of finding matching vertex pairs is based on bidomain partitioning. This process uses a labelling function that assigns labels to unmatched vertices based on their connectivity with matched vertices.

Based on the labels, McSplit partitions unmatched vertices in $V(G)\setminus V^{\prime }\cup V(H)\setminus U^{\prime }$ into a set of bidomains $P_{GH}=\{⟨V_1,U_1⟩,\mathrm{\dots },⟨V_t,U_t⟩\}$ such that $\forall v\in V_i$ and $\forall u\in U_j$, $i=j\iff \mathrm{\ell }(v)=\mathrm{\ell }(u)$, ensuring that all vertices within a single partition share the same label, while vertices in different partitions have distinct labels.

Specifically, the McSplit algorithm starts by initializing $P_{GH}=\{⟨V(G),V(H)⟩\}$ and picks a matching bidomain pair $⟨V_l,U_l⟩$. Then, the algorithm selects a vertex $v\in V_l$ and $v$ is matched against all the vertices $u\in U_l$. Matching $v$ with any $u$ gives $M=\{(v,u)\}$. Then, unmatched vertices in $G$ and $H$ are labelled based on the connectivity of $v$ and $u$, respectively. This leads to bidomain re-partitioning such that each bidomain $⟨V_l,U_l⟩\in P_{GH}$ is partitioned into two bidomains $⟨V_l\cap N(G,v)$, $U_l\cap N(H,u)⟩$ and $⟨V_l\setminus N(G,v),U_l\setminus N(H,u)⟩$. Iteratively, the algorithm selects another vertex pair to expands $M$. Once $v$ is matched against all the vertices $u\in U_l$, the algorithm removes the vertex $v$ from $V_l$ and continues with the search. The removal of $v$ is denoted as matching $v$ with the special symbol $\perp$. The algorithm continues until there are no more matching vertex pairs to select. In every iteration, alongside the current mapping $M$ being expanded, the algorithm keeps track of the best solution discovered so far, referred to as the $incumbent$. It then uses the following upper bound to eliminate unpromising search branches.

If the current mapping $M$ cannot be expanded more than $incumbent$ in size, i.e., $UB\le |incumbent|$, the algorithm immediately terminate the search, otherwise continues.

Recent studies extend McSplit using reinforcement learning techniques [12, 27, 13], where an agent explores an environment by taking actions [23]. All these studies consider the McSplit algorithm as an agent whose goal is to reach a search tree leaf as early as possible to reduce the overall size of the search tree. The choice of a matching vertex pair $(v,w)$ at each branching step is modelled as an action. This viewpoint naturally leads to using the bound reduction as a crucial factor for defining the reward of the action $(v,w)$, and then incorporating accumulated rewards into heuristics for selecting matching vertex pairs.

Within the branch and bound framework, search heuristics used by algorithms for solving the MCIS problem can be generally categorized into two types:

• $\mathrm{■}$

  Branching heuristic: This typically involves partition selection (selecting a bidomain $⟨V_l,U_l⟩$ from $P_{GH}$), node selection (selecting a vertex $v$ from $V_l$), and match selection (selecting a vertex $u$ from $U_l$ to form a matching vertex pair $(v,u)$).

• $\mathrm{■}$

  Bounding heuristic: This estimates the maximum number of vertices (i.e., upper bound) in the maximum common subgraph. If this estimated upper bound is less than the found common subgraph, it prunes that search branch.

Currently, all existing learning-based methods for McSplit focus on improving branching heuristics, which essentially involves deciding the “best” matching vertex pair to branch out, assuming that choosing different matching vertex pairs may lead to different bound reductions and thus reach the pruning condition at different speeds. They all use the bounding heuristic of McSplit that estimates the upper bound based on ${\sum }_{⟨V_l,U_l⟩\in P_{GH}}\min (|V_l|,|U_l|)$ (see Equation 1).

We consider the McSplit algorithm or any of its extensions McSplit+RL, McSplit+LL, and McSplit+DAL as an agent. Instead of reaching a search tree leaf as early as possible, the goal of our agent is to prune branches as early as possible. Thus, unlike existing methods where an action is to choose the best matching vertex pair, an action in our method is to decide whether to employ a new and tighter upper bound to prune a branch earlier. However, there are two major challenges in designing a learning-based bounding heuristic in this setting: (1) How to design an efficient algorithm that can provide a tighter upper bound than the original bound of McSplit? (2) How to design the reward and value function that can accurately predict when a pruning condition can be met under new and tighter bounds? Addressing these two challenges are the key to enhancing the overall performance of the algorithm. We discuss our approach below in detail.

We begin by proposing a novel upper bound for MCIS, which is tighter than the bound of McSplit and can be used to reduce the search space for BnB algorithms based on McSplit. The intuition behind this novel upper bound is simple. Given a bidomain $⟨V_l,U_l⟩$, we derive an upper bound for maximum common subgraphs between $G[V_l]$ and $H[U_l]$ based on their degree sequences, not merely the sizes of $|V_l|$ and $|U_l|$ as used by $\min (|V_l|,|U_l|)$ in McSplit. This is because the degree sequence of a graph can provide more useful structural information than computing the size of the small graph.

Let $M^{\ast }(G,H)$ denote a maximum-cardinality mapping between two graphs, $G$ and $H$. An independent set is a set of pairwise non-adjacent vertices. Based on degree sequences, we derive the following (recall that degree sequences are monotonically increasing).

Since computing the new bound requires additional computational time compared to McSplit bound, it is essential to determine where the new bound can be most effectively utilized during the search - particularly in areas where there is a high likelihood of pruning branches. To address this, we propose incorporating a reinforcement learning agent into a learning-based framework. This agent will dynamically decide when to apply the proposed tighter bound, aiming to maximize both the efficiency and effectiveness of the pruning process.

We denote power sets by $𝒫(\cdot )$. Let $\varphi$ be a property of bidomains, e.g., given a bidomain $⟨V_l,U_l⟩$, $\varphi$ may hold if $|V_l|$ or $|U_l|/|V_l|$ is smaller than a threshold. Then a $\varphi$-activation function is defined as $\lambda :𝒫(V(G))\times 𝒫(V(H))\to \{active,inactive\}$ such that $\lambda (V^{\prime },U^{\prime })=active$ if $⟨V^{\prime },U^{\prime }⟩$ satisfies the property $\varphi$. At each branching step, $P_{GH}$ contains a subset of active bidomains $P_{GH}^{†}=\{⟨V_l,U_l⟩\in P_{GH}\mid \lambda (V_l,U_l)=active\}$.

The reward for an action on $P_{GH}$ is based upon the reward for each active bidomain $⟨V_l,U_l⟩\in P_{GH}$. This is because the estimated bound gap between the bound of McSplit and the new bound for $P_{GH}$ depends on the estimated bound gaps for its active bidomains. Thus, we define the reward for a bidomain as the bound gap between the bound of McSplit and the new bound.

The value function of a bidomain $⟨V_l,U_l⟩$ maintains a score $S(V_l,U_l)$, which is initialized to 1 and is then averaged with the previous score each time to capture the historical information. Let $\alpha \in [0,1]$. When $\alpha$ is close to $1$, more weight is given to recent bound reductions (short-term), whereas when $\alpha$ is close to $0$, the bound reductions over the entire history (long-term) are given more weight.

The value function for the set of bidomains maintains a score $S(P_{GH})$ for $P_{GH}$ which reflects the accumulated rewards of its active bidomains.

At each branching step, the algorithm checks the following condition to decide whether to compute the new bounds:

The intention of the above condition is to predict whether computing the new bound can lead to prune the branch. Thus, if the condition is satisfied, the new bound is computed for each active bidomain, and the reward and value scores are updated; otherwise the algorithm uses the bound of McSplit without any changes on rewards and value scores.

We evaluate our approach on multiple standard benchmark datasets for maximum common subgraph detection. The Images-PR15 dataset [22] features a single large target graph (4,838 vertices) and 24 pattern graphs (4-170 vertices), creating 24 test pairs generated from segmented images. The more comprehensive Images CVIU11 dataset [5] offers 6,278 graph pairs, combining 43 pattern graphs (22-151 vertices) with 146 target graphs (1,072-5,972 vertices). Its counterpart, Meshes CVIU11 [5], provides 3,018 pairs using 6 pattern graphs (40-199 vertices) and 503 target graphs (208-5,873 vertices). For larger-scale testing, the LV dataset [16] contains 2,352 pairs (49 patterns, 48 targets, 10-6,671 vertices), while the LargerLV extension [16] increases this to 3,430 pairs (49 patterns of 10-128 vertices, 70 targets of 138-6,671 vertices). We also include the Scalefree dataset [26, 21] (100 pairs with targets of 200-1,000 vertices and patterns at 90% target size) and the SI dataset [26, 21] (1,170 pairs with targets of 200-1,296 vertices and patterns at 20-60% target size). Finally, the Phase dataset [15] contributes 200 Erdos-Rényi graph pairs (pattern size 30, target size 150), providing a controlled random graph benchmark.

We begin by evaluating our method against the state-of-the-art McSplit algorithm and its variants. For each of these baseline approaches McSplit [16], McSplit+RL [12], McSplit+LL [27], and McSplit+DAL [13], we develop enhanced versions (McSplit+DSB, McSplit+RL+DSB, McSplit+LL+DSB, and McSplit+DAL+DSB) by integrating our proposed bound calculation method. Since McSplit and its variations have shown a considerable advantage over other methods for solving the MCIS problem, such as maximum clique algorithms and constraint programming, we focused our experiments on McSplit and its extensions.

Our experimental evaluation uses all benchmark graph pairs described previously, with a strict 1800-second (30-minute) time limit per instance. We classify problem instances into three categories based on solution time: easy (solved within 10 seconds), moderate (solved between 10 seconds and 1800 seconds), and hard (unsolved within the time limit). This categorization enables detailed analysis of performance across different difficulty levels.

A comprehensive comparative analysis reveals that McSplit+DSB outperforms McSplit by successfully solving a greater number of moderate instances, achieving a notable 3.41% improvement. This enhancement is visually demonstrated in Figure 3, which compares the performance of McSplit and McSplit+DSB over a 1800-second time frame. The y-axis represents the number of solved instances, while the x-axis denotes the time in seconds. The graph employs dotted lines to indicate the time taken to find the maximum common subgraph (i.e., the optimal solution) and solid lines to represent the time required to exhaustively explore the entire search space. The results clearly illustrate that the integration of the proposed bound significantly boosts the number of solved instances within the McSplit framework. Furthermore, the inclusion of this bound not only accelerates the discovery of the optimal solution but also reduces the overall time needed to verify and complete the search process. The 3.41% improvement refers to instances solved within a fixed time limit, rather than overall running time. Although it may seem modest, this consistent improvement across diverse instances highlights the generality of our approach.

Additionally, Figure 4(a) provides a comparative analysis of the number of cases solved by McSplit and McSplit+DSB in logarithmic scale. The Y-axis shows the number of branches taken by the McSplit+DSB, while the X-axis shows number of branches taken by McSplit. Each point $(y_1,x_1)$ represents a single instance, where $y_1$ is the branch count with DSB and $x_1$ is the count without it. A reference line $y=x$ is included in the plot for comparison. Points below this line indicate that our method reduced the number of branches needed, while points above suggest an increase. As seen in the plots, all the data points lie on or below the $y=x$ line, highlighting the overall efficiency of our method underscoring the computational advantages of the proposed bound. These findings collectively highlight the effectiveness of McSplit+DSB in enhancing both the speed and efficiency of the maximum common subgraph problem.

Next, we assess the impact of integrating the proposed bound into the machine learning extensions of McSplit, namely McSplit+RL [12], McSplit+LL [27], and McSplit+DAL [13]. Although the bound leads to a similar number of solved instances across these methods, its true value lies in the substantial reduction of computational effort. As illustrated in Figure 4(b), Figure 4(c), and Figure 4(d), the bound dramatically decreases the number of branches explored in moderate cases, with the majority of solved instances exhibiting a branch ratio greater than one. This indicates that the proposed bound calculation consistently explores fewer branches than its counterparts, enhancing efficiency.

However, Figure 4(b), Figure 4(c), and Figure 4(d) also reveals a few outlier points that falls above the $y=x$ line, meaning the original algorithm (without DSB) explores fewer branches. This phenomenon occurs because, in certain cases, early pruning disrupts the learning process of dynamic vertex selection models like McSplit+RL. These models rely on iterative refinement of vertex selection, and pruning initial branches can hinder this refinement, altering the selection process in subsequent iterations. In contrast, McSplit, which employs a static degree-based vertex selection method (as shown in Figure 4(a)), remains unaffected by such disruptions. This nuanced behavior highlights the trade-offs involved in integrating the bound with machine learning extensions, emphasizing its benefits in reducing search complexity while acknowledging its occasional interference with dynamic learning mechanisms.

In this experiment, we evaluate how closely our proposed bound approximates the theoretical limit of bound tightness based on bidomains alone. While even tighter bounds are possible in principle by considering relationships between vertices from different bidomains, such approaches run the risk of becoming too expensive to improve overall performance.

For a given bidomain $⟨V_l,U_l⟩\in P_{GH}$, the exact upper bound or the ultimate bound reduction is computed by determining the maximum common subgraph of the induced subgraphs $G[V_l]$ and $H[U_l]$. We refer to this ideal bound calculation as the oracle. Our objective is to compare the deviations of both the proposed bound and the McSplit bound from this oracle. To facilitate this comparison, we introduce McSplit+Oracle, a variant of the McSplit algorithm that replaces its standard bound calculation with the oracle’s method of computing the MCS for each matching partition as follows:

where $McSplit(G[V_l],H[U_l])$ returns the maximum common subgraph of the induced subgraphs $G[V_l]$ and $H[U_l]$.

Figure 3 visually contrasts the bound differences between McSplit+Oracle and McSplit (represented by red bars) and McSplit+DSB and McSplit (represented by blue bars). The comparison between the red and blue bars allows us to measure the correlation between McSplit+DSB and McSplit+Oracle. Notably, the red and blue plots align closely at $x=0$ and $x=1$, indicating strong agreement in McSplit+DSB and McSplit+Oracle. However, as $x$ increases beyond 1, both plots exhibit a noticeable decline.

Crucially it shows that in virtually all cases where Oracle improves on the basic McSplit bound, DSB does as well, and in most of those cases by the same amount. These results highlight the effectiveness of the proposed bound in bridging the gap toward the ultimate bound reduction, offering a significant improvement over the baseline McSplit algorithm.

MCIS instances that remain unsolved by each algorithm and its branch sampling extension within the 1800-second time limit are categorized as hard instances. While these instances cannot be fully resolved within the given timeframe, identifying a larger common subgraph during this period remains highly valuable for practical applications [14]. Such partial solutions provide critical insights or approximations when exact solutions are out of reach, making them indispensable in real-world scenarios.

Table 2 compares our proposed methods against existing approaches on hard instances using the Larger Common Subgraph Rate, which quantifies the percentage of cases where our method identifies a larger common subgraph than its competitors. These larger subgraphs are subsequently used as lower bounds to prune more branches, significantly reducing computational time. The results in Table 2 demonstrate that our method consistently outperforms McSplit and its variants when the proposed bound calculation is applied to these difficult cases. In all other scenarios, both methods yield subgraphs of equal size. This performance gain highlights the proposed method’s enhanced pruning efficiency and its ability to navigate the search space more effectively. These advantages establish it as a robust and practical solution for tackling complex MCIS problems, particularly under stringent time constraints. By providing larger subgraphs in hard cases, our method underscores the importance of integrating bound calculations into MCIS search algorithms.

The frequency with which the new bound is computed depends on both the structure of the input graph pairs and the behavior of the learned model. In our experiments, we found that the new bound was activated in approximately 1.64% of the cases, with a standard deviation of 7.99%.