Between Subgraph Isomorphism and Maximum Common Subgraph
Authors: Ruth Hoffmann, Ciaran McCreesh, Craig Reilly
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We perform our experiments on systems with dual Intel Xeon CPU E5-2640 processors with 64GBytes of RAM, running Ubuntu 14.04. Our algorithm was implemented in C++2, and source code was compiled using GCC 5.3.0. We used a timeout of 1,000 seconds for each instance. For comparison, we used the implementations of Ndiaye and Solnon (2011) and Mc Creesh et al. (2016). For datasets, we use the same 5,725 instances used in a recent work on portfolios of algorithms for subgraph isomorphism (Kotthoff, Mc Creesh, and Solnon 2016). |
| Researcher Affiliation | Academia | Ruth Hoffmann, Ciaran Mc Creesh, Craig Reilly University of Glasgow, Glasgow, Scotland ruth.hoffmann@glasgow.ac.uk and {c.mccreesh.1,c.reilly.2}@research.gla.ac.uk |
| Pseudocode | Yes | Algorithm 1: A bit-parallel algorithm for the k-less subgraph isomorphism problem. |
| Open Source Code | Yes | Our algorithm was implemented in C++2, and source code was compiled using GCC 5.3.0. 2https://github.com/ciaranm/aaai17-between-subgraph-isomorphism-and-maximum-common-subgraph-paper |
| Open Datasets | Yes | For datasets, we use the same 5,725 instances used in a recent work on portfolios of algorithms for subgraph isomorphism (Kotthoff, Mc Creesh, and Solnon 2016). ... All of these instances are available in a simple text format3. 3http://liris.cnrs.fr/csolnon/SIP.html |
| Dataset Splits | No | The paper mentions datasets used for experiments but does not provide specific details on training, validation, or test set splits, beyond implicitly using the full dataset for testing. |
| Hardware Specification | Yes | We perform our experiments on systems with dual Intel Xeon CPU E5-2640 processors with 64GBytes of RAM, running Ubuntu 14.04. |
| Software Dependencies | Yes | Our algorithm was implemented in C++2, and source code was compiled using GCC 5.3.0. |
| Experiment Setup | Yes | We used a timeout of 1,000 seconds for each instance. The algorithm performs a constraint-based search. We have a set D containing a variable Dv for each vertex in the pattern graph. Each variable has a domain containing one value for every vertex in the target graph. The algorithm is bit-parallel: each Dv is stored using bitset, and all graphs are stored as adjacency matrices. We pick the smallest domain (line 16) and try giving it each of its remaining values in turn. We use the value the ordering heuristic from the original algorithm; wildcards are treated as having degree zero, in an attempt to maximising the expected number of solutions remaining during search (Mc Creesh, Prosser, and Trimble 2016). We introduce a symmetry break (line 18) to try only a single wildcard value for each variable. |