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.
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:
- Identifying the Invariant: Proving that a $k$-clique in the pattern must map to a $k$-clique in the target.
- 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.
- 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.
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