Solving Graph Homomorphism and Subgraph Isomorphism Problems Faster Through Clique Neighbourhood Constraints

Sonja Kraiczy, Ciaran McCreeshIJCAI 2021 · DOI

Introduction

Graph mapping problems—identifying valid mappings from a pattern graph to a target graph while preserving structural properties—are central to computational biology, chemistry, and network analysis. While Subgraph Isomorphism (SI) is well-studied and benefits from strong "all-different" constraints due to its injective nature, Graph Homomorphism (GH) and Locally Injective Homomorphism (LI) lack these pruning mechanisms. Consequently, solvers for these less-constrained variants often face an exponentially larger search space.

Examples of various graph mapping problems, including homomorphisms where multiple pattern vertices can map to a single target vertex.

Methodology: Clique Neighbourhood Constraints

The authors propose a novel filtering technique based on local structural invariants. The core insight is that in any graph homomorphism (excluding target graphs with self-loops), a $k$-clique in the pattern graph must map to a $k$-clique in the target graph.

The solver implements Clique Filtering by:

  1. Identifying the Invariant: Proving that a $k$-clique in the pattern must map to a $k$-clique in the target.
  2. Enforcing the Constraint: For every pattern vertex $v$, the solver calculates the maximum clique size in its neighborhood. $v$ can only map to a target vertex $w$ if $w$ is part of a clique at least as large.
  3. Optimizing Local Search: To maintain efficiency, the authors utilized a bit-parallel clique-finding algorithm. Despite the NP-completeness of the clique problem, its application to small local neighborhoods typically concludes in under 1ms, making it a highly effective preprocessing step.

Experimental Evaluation

The technique was integrated into the Glasgow Subgraph Solver and tested against a benchmark suite of 14,621 graph instances. The evaluation focused on three problem types: standard Graph Homomorphism, Locally Injective Homomorphism, and Subgraph Isomorphism.

Key Results

The addition of clique neighborhood constraints yielded dramatic performance improvements across the board:

  • Graph Homomorphism: Achieved a massive aggregate speedup of 803.5x, providing the first practical constraint programming approach for this problem class.
  • Locally Injective Homomorphism: Provided a 2.2x speedup and significantly increased the number of instances solved within a one-hour limit.
  • Subgraph Isomorphism: Even with existing injective constraints, clique filtering provided a 3.2x speedup.
Performance comparison for Locally Injective (LI) problems, showing that the addition of clique constraints (LI+Clq) consistently solves more instances faster over time.

Conclusion and Future Work

By leveraging "hard" local invariants to prune a "hard" global search, the authors demonstrated that structural filtering can bridge the performance gap between injective and non-injective graph mapping problems. While the technique is currently limited to graphs without self-loops, future research may explore other local invariants, such as graph coloring or treewidth, to further enhance solver efficiency.

Summary updated

BibTeX
@inproceedings{kraiczy2021solving,
  author = {Sonja Kraiczy and Ciaran McCreesh},
  title = {{Solving Graph Homomorphism and Subgraph Isomorphism Problems Faster Through Clique Neighbourhood Constraints}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/193},
}

Loading related content...

Figure