 Benchmarks for the Subgraph Isomorphism Problem

# Benchmarks for the Subgraph Isomorphism Problem

### Composition of the archive:

• Benchmarks described in [ZDS2010] and [Sol2010]:
• scalefree (100 instances): Each instance is composed of a target graph (between 200 and 1000 nodes) and a pattern graph (90% of the nodes of the target graph). All graphs are scale-free networks that have been randomly generated using a power law distribution of degrees.
• LV (112 graphs coming from Valiente): These graphs have different properties (connected, biconnected, triconnected, bipartite, planar, ...) and have between 10 and 6671 nodes.
• si (1170 instances coming from the Graph Database): Each instance is composed of a target graph (between 200 and 1296 nodes) and a pattern graph (between 20% and 60% of the nodes of the target graph). There are bounded valence graphs and modified bounded valence graphs, 4D meshes, and randomly generated graphs.
• Benchmarks described in [DSHJS2011]:
• images-CVIU11 (44 pattern graphs and 146 target graphs): Pattern graphs have between 22 and 151 nodes and target graphs have between 1072 and 5972 nodes. All graphs have been generated from segmented images.
• meshes-CVIU11 (6 pattern graphs and 503 target graphs): Pattern graphs have between 40 and 199 nodes and target graphs have between 208 and 5873 nodes. All graphs have been generated from meshes modelling 3D objects.
• Benchmark described in [SDHJ2015]:
• images-PR15 (1 target graph and 24 pattern graphs): The target graph has 4838 nodes and the pattern graphs have between 4 and 170 nodes. All graphs have been generated from segmented images.
• Benchmark described in [GFMSS2014]:
• biochemical reactions (136 graphs): All graphs are directed bipartite graphs which have between 9 and 386 nodes and which describe biocheminal reaction networks coming from biomodels.net.
• Benchmark generated by Ciaran McCreesh and Patrick Prosser (200 instances): Random graph instances chosen to be close to the satisfiable-unsatisfiable phase transition---these instances are expected to be particularly challenging, despite their small size (pattern graphs have 30 vertices; target graphs have 150 vertices).

### Graph format:

Each graph is described in a text file. If the graph has n vertices, then the file has n+1 lines:
• The first line gives the number n of vertices.
• The next n lines give, for each vertex, its number of successor nodes, followed by the list of its successor nodes.

### Experimental Evaluation:

An experimental comparison of different subgraph isomorphism solvers is described in:
• Experimental Evaluation of Subgraph Isomorphism Solvers
Christine Solnon
Invited Talk at 12th IAPR International Workshop on Graph-based Representations in Pattern Recognition (GbR), LNCS, Springer
Paper (pdf)