Experimental Evaluation of Subgraph Isomorphism Solvers

Christine Solnon 1
1 M2DisCo - Geometry Processing and Constrained Optimization
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
Abstract : Subgraph Isomorphism (SI) is an NP-complete problem which is at the heart of many structural pattern recognition tasks as it involves finding a copy of a pattern graph into a target graph. In the pattern recognition community, the most well-known SI solvers are VF2, VF3, and RI. SI is also widely studied in the constraint programming community, and many constraint-based SI solvers have been proposed since Ullman, such as LAD and Glasgow, for example. All these SI solvers can solve very quickly some large SI instances, that involve graphs with thousands of nodes. However, McCreesh et al. have recently shown how to randomly generate SI instances the hardness of which can be controlled and predicted, and they have built small instances which are computationally challenging for all solvers. They have also shown that some small instances, which are predicted to be easy and are easily solved by constraint-based solvers, appear to be challenging for VF2 and VF3. In this paper, we widen this study by considering a large test suite coming from eight benchmarks. We show that, as expected for an NP-complete problem, the solving time of an instance does not depend on its size, and that some small instances coming from real applications are not solved by any of the considered solvers. We also show that, if RI and VF3 can solve very quickly a large number of easy instances, for which Glasgow or LAD need more time, they fail at solving some other instances that are quickly solved by Glasgow or LAD, and they are clearly outperformed by Glasgow on hard instances. Finally, we show that we can easily combine solvers to take benefit of their complementarity.
Document type :
Conference papers
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02086499
Contributor : Christine Solnon <>
Submitted on : Monday, April 1, 2019 - 1:33:11 PM
Last modification on : Monday, July 8, 2019 - 4:51:19 PM
Long-term archiving on : Tuesday, July 2, 2019 - 1:50:27 PM

File

paper.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02086499, version 1

Citation

Christine Solnon. Experimental Evaluation of Subgraph Isomorphism Solvers. 12th IAPR-TC-15 International workshop on Graph-Based Representation in Pattern Recognition, Jun 2019, Tours, France. pp.1-13. ⟨hal-02086499⟩

Share

Metrics

Record views

82

Files downloads

89