Solving Hard Subgraph Problems in Parallel

Ciaran McCreeshIJCAI 2016

Abstract

Finding patterns within large-scale networks is a fundamental challenge in computational science, yet problems such as the maximum clique and subgraph isomorphism remain NP-hard. This paper, originally presented at IJCAI-16, details research into bridging the gap between theoretical complexity and practical performance. By integrating refined search heuristics, bit-level parallelism, and multi-core work-stealing strategies, we demonstrate significant speedups and improved robustness. A key finding is that parallel execution serves as a "safety net" against poor heuristic choices, effectively performing a discrepancy search that explores alternative branches of the search tree simultaneously.

1. Introduction

Graph-based pattern matching is essential in fields ranging from bioinformatics and chemoinformatics to computer vision. Two of the most prominent problems in this domain are the maximum clique problem—identifying the largest subset of vertices where every vertex is connected to every other—and subgraph isomorphism, which involves determining if a specific template graph exists within a larger target graph.

Despite their importance, these problems are computationally expensive. While many real-world instances can be solved relatively quickly, others exhibit exponential time complexity that challenges modern hardware. This research investigates how to leverage modern CPU features, specifically multi-core architectures and bit-level operations, alongside machine learning and algorithmic refinements to solve these "hard" instances more efficiently.

2. Methodology

2.1 Refined Heuristics and Branching

Traditional solvers often utilize "coloring-based" heuristics to estimate the potential size of a clique in a remaining subgraph. By assigning colors to nodes such that no two adjacent nodes share a color, the number of colors used provides an upper bound on the clique size. This research analyzed these heuristics and discovered that their effectiveness is maximized when branching on small color classes first. This approach aligns with the "smallest domain first" principle found in constraint programming, providing a more principled basis for search order than previously suggested in the literature.

2.2 Bit-Parallelism

To accelerate the filtering process—the pruning of the search space that occurs at every node of the search tree—the research employs bit-parallel operations. By representing graph adjacency matrices as bitsets, the CPU can process multiple nodes simultaneously within a single clock cycle using bitwise AND/OR operations. This significantly reduces the constant-factor overhead of the search process.

2.3 Parallel Tree Search and Work Stealing

Parallelization in this context is implemented via thread-parallelism using a work-stealing architecture. In this model, idle processors "steal" unexplored branches from the top of the search trees of busy processors. This ensures high CPU utilization and provides a mechanism for "safe" parallelization, where adding more cores is guaranteed not to degrade performance (avoiding common parallelism anomalies).

2.4 Algorithm Portfolios

Because graph structures vary wildly, no single filtering strategy is universally optimal. We utilized machine learning to create algorithm portfolios that predict the most effective filtering strategy for a given graph instance based on its structural features.

3. Experimental Setup and Datasets

The research was evaluated using standard benchmark suites for subgraph isomorphism and maximum clique problems. To push the limits of modern solvers, we introduced a new method for generating "really hard" random instances for subgraph isomorphism. By targeting the phase transition—the narrow parameter range where an instance transitions from being likely satisfiable to likely unsatisfiable—we created benchmarks that are orders of magnitude more difficult for state-of-the-art solvers than traditional random graphs.

4. Key Insights

4.1 Parallelism as a Safety Net

Perhaps the most significant insight is that parallel search provides more than just raw speed; it provides algorithmic robustness. In a sequential search, an early incorrect heuristic choice can lead the solver down a massive, fruitless branch. In a parallel environment, work-stealing from the top of the tree essentially performs a discrepancy search. While the primary thread might be stuck in a deep, difficult branch, parallel threads explore the alternative choices made at the top of the tree, effectively mitigating the cost of the initial heuristic error.

4.2 Constrainedness vs. Hardness

While phase transitions are useful for generating hard instances, the research found that "constrainedness"—a measure of how restricted the search space is—serves as a more accurate predictor of an instance's practical hardness. This allows for better tuning of solvers and more informed expectations regarding computation time.

5. Results and Conclusion

The resulting algorithms achieved substantial speedups on modern multi-core CPUs. Specifically, the subgraph isomorphism solver [McCreesh and Prosser, 2015a] combined bit-parallelism with a novel form of "backjumping" (intelligent backtracking) to outperform previous methods. This was achieved without the significant memory and computational overhead typically associated with maintaining complex conflict sets.

Future work focuses on extending these techniques to weighted graphs and the maximum common subgraph problem. We are currently investigating the use of Decision Diagrams to handle weighted instances and exploring the integration of "clause learning" from SAT solvers into graph search to learn from failures without losing high-level structural information.

Summary updated

BibTeX
@inproceedings{mccreesh2016solving,
  author = {Ciaran McCreesh},
  title = {{Solving Hard Subgraph Problems in Parallel}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure