Solving Subgraph Isomorphism Problems with LAD-filtering

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:

Reference

The algorithm used by LAD to solve the subgraph isomorphism problem is described in:

Experimental results

Here are some experimental results obtained on different benchmarks. We compare results obtained with 3 different solvers: 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.

SolverNumber of solved instancesAverage CPU time per solved instance
LAD1003.0
Vflib1672.5
Abscon81594.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.

SolverNumber of solved instancesAverage CPU time per solved instance
LAD72812.8
Vflib46873.7
Abscon66254.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.

SolverNumber of solved instancesAverage CPU time per solved instance
LAD9001.07
Vflib8820.12
Abscon89040.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.

SolverNumber of solved instancesAverage CPU time per solved instance
LAD190287.8
Vflib31735.9
Abscon183409.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).