Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
A Partitioning Algorithm for Maximum Common Subgraph Problems
Authors: Ciaran McCreesh, Patrick Prosser, James Trimble
IJCAI 2017 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments show a speedup of more than an order of magnitude over the state of the art, and demonstrate that we can operate on much larger graphs without running out of memory. and We then present an empirical study of the algorithm, demonstrating that it improves the state of the art by more than an order of magnitude on the unlabelled variant of the problem, and showing that it can handle much larger instances than earlier constraint programming or clique approaches due to lower memory usage. |
| Researcher Affiliation | Academia | Ciaran Mc Creesh, Patrick Prosser, James Trimble University of Glasgow, Glasgow, Scotland EMAIL |
| Pseudocode | Yes | Algorithm 1: Finding a maximum common subgraph. and Algorithm 2: Replacement for lines 11 to 18 of Algorithm 1 to handle directed and edge-labelled cases. |
| Open Source Code | Yes | 1Source code, instances, experimental scripts and raw results are available at https://github.com/jamestrimble/ijcai2017-partitioning-common-subgraph |
| Open Datasets | Yes | Our first set of experiments uses a database of randomly-generated maximum common subgraph instances [Santo et al., 2003; Conte et al., 2007]. and We also ran the algorithms on a set of 5,725 larger instances used in recent studies of subgraph isomorphism [Kotthoff et al., 2016] and maximum common subgraph [Hoffmann et al., 2017]. |
| Dataset Splits | No | The paper mentions datasets like 'randomly-generated maximum common subgraph instances' and 'large subgraph isomorphism instances' but does not specify how these instances were partitioned into training, validation, or test sets for their experiments. |
| Hardware Specification | Yes | Experiments were performed on machines with dual Intel Xeon E5-2640 v2 CPUs and 64GBytes RAM. |
| Software Dependencies | Yes | Our algorithm was implemented1 in C++ and compiled using g++ 5.3.0. |
| Experiment Setup | Yes | Our Select Label Class function chooses a label class with the smallest max( G , H ), breaking ties by selecting a class containing a vertex in G with the largest degree. From the selected class, Select Vertex chooses a vertex in G with maximum degree. and if a time limit of 0.5 seconds per instance were imposed. and a timeout of 1,000 seconds. |