GLSearch: Maximum Common Subgraph Detection via Learning to Search
Authors: Yunsheng Bai, Derek Xu, Yizhou Sun, Wei Wang
ICML 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments on synthetic and real-world graph pairs demonstrate that our model learns a search strategy that is able to detect significantly larger common subgraphs than existing MCS solvers given the same computation budget. |
| Researcher Affiliation | Academia | 1Department of Computer Science, University of California, Los Angeles, California, USA. |
| Pseudocode | Yes | Algorithm 1 Branch and Bound for MCS. We highlight in green boxes the two places that will be replaced by GLSEARCH. |
| Open Source Code | No | The paper mentions that 'More details can be found in the supplementary material' multiple times, but does not explicitly state that the source code for their methodology is provided or available there, nor does it provide a direct link to a code repository. |
| Open Datasets | Yes | Each synthetic dataset consists of 50 randomly generated pairs labeled as generation algorithm number of nodes in each graph . BA , ER , and WS refer to the Barab asi-Albert (BA) (Barab asi & Albert, 1999), the Erd os-R enyi (ER) (Gilbert, 1959), and the Watts Strogatz (WS) (Watts & Strogatz, 1998) algorithms, respectively. NCI109 consists of 100 chemical compound graph pairs whose average graph size is 28.73. |
| Dataset Splits | No | The paper does not explicitly provide specific training/validation/test dataset splits with percentages, sample counts, or clear methodologies for partitioning the data. |
| Hardware Specification | Yes | We run all experiments with Intel i76800K CPU and one Nvidia Titan GPU. |
| Software Dependencies | No | The models were implemented with the Py Torch and Py Torch Geometric libraries (Fey & Lenssen, 2019). |
| Experiment Setup | Yes | For I-PCA, NEURALMCS and GLSEARCH, we utilize 3 layers of Graph Attention Networks (GAT) (Velickovic et al., 2018) each with 64 dimensions for the embeddings. The initial node embedding is encoded using the local degree profile (Cai & Wang, 2018). We use ELU(x) = α(exp(x) 1) for x 0 and x for x > 0 as our activation function where α = 1. For training, we set the learning rate to 0.001, the number of training iterations to 10000, and use the Adam optimizer (Kingma & Ba, 2015). |