A Partitioning Algorithm for Maximum Common Subgraph Problems

Ciaran McCreesh, Patrick Prosser, James TrimbleIJCAI 2017 · DOI

TL;DR

This paper introduces MCSPLIT, a novel branch-and-bound algorithm for the Maximum Common Subgraph (MCS) problem. By employing a unique vertex labeling and partitioning approach, MCSPLIT dramatically reduces memory and computation requirements, achieving over an order of magnitude speedup on unlabelled instances compared to state-of-the-art methods and enabling the analysis of much larger graphs.

What Problem Does This Paper Address?

Determining the similarity or difference between two graphs is a fundamental problem with applications across various scientific domains, including molecular science, malware detection, and computer vision. The Maximum Common Subgraph (MCS) problem, specifically, aims to find the largest possible subgraph that is present in both input graphs. This problem is known to be NP-hard, making it computationally challenging, especially for large graphs. While previous research has explored constraint programming, mathematical programming, and reducing the problem to maximum clique, there remains a need for more efficient algorithms that can handle larger instances without succumbing to memory limitations.

Methods

The core contribution of this paper is the MCSPLIT algorithm, a new branch-and-bound approach for the MCS problem. MCSPLIT builds upon traditional constraint programming techniques but introduces a novel "compact domain store" and supporting inference algorithms. The algorithm works by iteratively building a mapping between vertices of the two input graphs, G and H.

Key aspects of the MCSPLIT algorithm include:

  • Vertex Labeling and Partitioning: MCSPLIT assigns labels to vertices based on their adjacency to already mapped vertices. This labeling scheme is crucial because it maintains an invariant: two vertices can only be mapped together if they share the same label. This effectively partitions the problem into smaller, independent subproblems.
  • Compact Domain Store: Instead of storing explicit domains for each variable (vertex), MCSPLIT uses a compact representation that exploits the disjoint nature of domains across label classes. This significantly reduces memory overhead.
  • Efficient Bounding: The algorithm calculates an upper bound on the size of the common subgraph at each step, allowing for effective pruning of the search space. This bound calculation is performed efficiently using a simple counting loop, leveraging the structure of the label classes.
  • Heuristics: The paper discusses heuristics for selecting label classes and vertices to branch on, aiming to guide the search towards promising solutions more quickly.

The paper also details extensions to handle variations of the MCS problem, including vertex and edge labels, directed graphs, and the requirement for the common subgraph to be connected.

Datasets

The paper evaluates MCSPLIT on several benchmark datasets:

  • Randomly-generated MCS instances: A set of 4,100 unlabelled, undirected instances with up to 50 vertices.
  • Labelled instances: A set of 8,140 labelled instances (vertex and edge labels) with up to 100 vertices. The labelling scheme used approximates the number of distinct labels to be 33% of the number of vertices.
  • Large subgraph isomorphism instances: A benchmark set of 5,725 larger instances, including real-world graphs and synthetically generated ones, with pattern graphs up to 900 vertices and target graphs up to 6,671 vertices.

The authors also mention using the original code from comparator programs, implying they are using established benchmark suites for these problems.

Key Insights and Ideas

  • The Power of Partitioning: The core insight is that by carefully labeling vertices based on their relationships to already mapped pairs, the problem can be effectively partitioned. This partitioning allows for a more structured and efficient search.
  • Memory Efficiency is Key: The paper highlights that a significant bottleneck in previous MCS algorithms is memory usage. MCSPLIT's compact domain store directly addresses this, enabling it to tackle much larger graphs.
  • Exploiting Domain Structure: The observation that domains in the MCS problem are either identical or disjoint (excluding the "unmapped" state) is a crucial insight. This property allows for a much simpler and faster bound calculation compared to traditional constraint programming approaches that might require more complex matching algorithms.
  • Heuristics Matter: The choice of branching heuristics significantly impacts performance, and the paper demonstrates that a specific heuristic (branching on the label class with the smallest max(|G|, |H|)) leads to substantial improvements.

Key Results

  • Order of Magnitude Speedup: For unlabelled, undirected MCS instances, MCSPLIT achieves over an order of magnitude speedup compared to the best existing constraint programming (CP-FC) algorithms.
  • Handling Larger Graphs: MCSPLIT demonstrates the ability to operate on much larger graphs without running out of memory, a significant advantage over previous methods.
  • Competitive Performance on Labelled Instances: While clique encodings remain slightly superior on some harder labelled instances, MCSPLIT is highly competitive and often outperforms other methods on easier instances.
  • Efficient Search Space Exploration: Experiments show a strong correlation between the number of recursive calls made by MCSPLIT and CP-FC, suggesting that MCSPLIT explores the search space more efficiently with lower constant factors.

Limitations and Future Work

  • Clique Encoding Superiority on Some Labelled Instances: The paper acknowledges that for certain labelled instances, particularly those requiring connected subgraphs, clique encodings can still outperform MCSPLIT.
  • Potential for Hybrid Approaches: The authors suggest that a hybrid algorithm, combining the strengths of MCSPLIT, k↓, and clique encodings, could be beneficial. This might involve switching between algorithms based on the problem size or characteristics.
  • Broader Applicability: The paper speculates that the partitioning domain store technique might be applicable to other graph-related problems beyond MCS, such as induced subgraph isomorphism.
  • Richer Labelling Schemes: MCSPLIT, in its current form, cannot handle certain complex labelling schemes, such as those used in temporal subgraph isomorphism.
  • Branching Heuristics: The authors believe there is further potential for improvement in branching heuristics, including exploring branching on both sides of the graph (G or H) or using heuristics to dynamically choose which graph to branch on.

Summary updated

BibTeX
@inproceedings{mccreesh2017partitioning,
  author = {Ciaran McCreesh and Patrick Prosser and James Trimble},
  title = {{A Partitioning Algorithm for Maximum Common Subgraph Problems}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/99},
}
Figure