Benchmarks for the Subgraph Isomorphism Problem

Download benchmarks

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:

• 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:

• 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)