Solving Subgraph Isomorphism with an AllDifferent-based Filtering algorithm

LAD is a program (in C) for solving the subgraph isomorphism problem, the goal of which is to decide if there exists a copy of a pattern graph in a target graph. It can be used to solve induced or partial subgraph isomorphism problems. The user may specify additional compatibility relationships among the nodes. LAD is distributed under the CeCILL-B FREE SOFTWARE LICENSE.

Download:

Version 3 (January 2016): PathLAD (described in a paper presented at LION 2016) for both directed and undirected graphs
Version 2 (June 2013): Improved version for both directed and undirected graphs and for labelled graphs
Version 1: Basic version for non directed graphs

References

The algorithm used by LAD to solve the subgraph isomorphism problem is described in:
Christine Solnon: AllDifferent-based Filtering for Subgraph Isomorphism. Artificial Intelligence, 174(12-13):850-864, August 2010, Elsevier.
Draft version of the paper (pdf) ScienceDirect
PathLAD is described in:
Lars Kotthoff, Ciaran McCreesh, and Christine Solnon: Portfolios of Subgraph Isomorphism Algorithms. To appear in Learning and Intelligent OptimizatioN Conference (LION 10), 2016
Paper (pdf)

Experimental results

Here are some experimental results obtained on different benchmarks. We compare results obtained with 3 different solvers:

LAD is our solver;
Vflib is a C++ graph matching library, developed at Mivia Lab of the University of Salerno;
Abscon is a generic Constraint Programming solver developped in Java by C. Lecoutre and S. Tabary. We consider here the variant which maintains Arc Consistency and which chooses variables with respect to the minDom heuristic.

Results are given for the partial subgraph isomorphism problem. For the scalefree benchmark, we consider the problem of finding all solutions to an instance (as these instances have very few solutions); for other benchmarks, we consider the problem of finding the first solution (or proving inconsistency). For every instance, we have limited the CPU time to one hour on a 2.26 GHz Intel Xeon E5520. For each benchmark and each solver, we report the number of solved instances within this CPU time limit as well as the average CPU time per solved instance.

Experimental results on the scalefree benchmark

Graphs of this benchmark are scale-free networks that have been randomly generated using a power law distribution of degrees. There are 100 instances such that target graphs have between 200 and 1000 nodes and pattern graphs have 90% of the nodes of the target graphs.

Solver	Number of solved instances	Average CPU time per solved instance
LAD	100	3.0
Vflib	16	72.5
Abscon	81	594.9

Experimental results on the LV benchmark

This benchmark is obtained from the first 50 graphs of the database of Larrosa and Valiente. These graphs have different properties (connected, biconnecetd, triconnected, bipartite, planar, ...) and have between 10 and 128 nodes. Using these graphs, we have generated 793 instances of the subgraph isomorphism problem by considering all couples of graphs that are not trivially solved.

Solver	Number of solved instances	Average CPU time per solved instance
LAD	728	12.8
Vflib	468	73.7
Abscon	662	54.3

Experimental results on the bvg/m4D benchmark

This benchmark contains 900 instances coming from the Graph Database. It contains instances with bounded valence graphs and modified bounded valence graphs (with valence in {3,6,9}). The number of nodes of the target graphs is in {200, 400, 800}, and the pattern graphs have between 20% and 60% of the nodes of the target graphs. It also contains instances with quadri-dimensional meshes (with rho in {0, 0.2, 0.4, 0.6}). The number of nodes of the target graphs is in {256, 625, 1296}, and the pattern graphs have between 20% and 60% of the nodes of the target graphs.

Solver	Number of solved instances	Average CPU time per solved instance
LAD	900	1.07
Vflib	882	0.12
Abscon	890	40.60

Experimental results on the rand benchmark

This benchmark contains 270 random instances coming from the Graph Database. It contains instances with randomly generated graphs such that the uniform probability of adding an edge is in {0.01, 0.05, 0.1}. The number of nodes of the target graphs is in {200, 400, 600}, and the pattern graphs have between 20% and 60% of the nodes of the target graphs.

Solver	Number of solved instances	Average CPU time per solved instance
LAD	190	287.8
Vflib	3	1735.9
Abscon	183	409.5

Acknowledgements

Many thanks to Yves Deville and Thierry Excoffier for enriching discussions, to Vianney le Clement for first patches and to Jean-Christophe Luquet for having implemented a preliminary version of this algorithm. This work was done in the context of project SATTIC (ANR grant Blanc07-1_184534).