A Degeneracy Framework for Graph Similarity
Authors: Giannis Nikolentzos, Polykarpos Meladianos, Stratis Limnios, Michalis Vazirgiannis
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The proposed framework is evaluated on several benchmark datasets for graph classification. In most cases, the corebased kernels achieve significant improvements in terms of classification accuracy over the base kernels, while their time complexity remains very attractive. |
| Researcher Affiliation | Academia | Giannis Nikolentzos1, Polykarpos Meladianos2, Stratis Limnios1 and Michalis Vazirgiannis1 1 Ecole Polytechnique, France 2 Athens University of Economics and Business, Greece {nikolentzos, mvazirg}@lix.polytechnique.fr, pmeladianos@aueb.gr, stratis.limnios@inria.fr |
| Pseudocode | Yes | Algorithm 1 k-core Decomposition Algorithm 2 Core-based Kernel |
| Open Source Code | Yes | Code available at https://www.lix.polytechnique.fr/~nikolentzos/code/core_framework.zip |
| Open Datasets | Yes | We evaluated the proposed framework on standard graph classification datasets derived from bioinformatics and chemoinformatics (MUTAG, ENZYMES, NCI1, PTC-MR, D&D), and from social networks (IMDB-BINARY, IMDBMULTI, REDDIT-BINARY, REDDIT-MULTI-5K, REDDITMULTI-12K)1. Note that the social network graphs are unlabeled, while all other graph datasets come with vertex labels. 1The datasets and statistics are available at https://ls11-www.cs.tu-dortmund.de/staff/morris/graphkerneldatasets |
| Dataset Splits | Yes | To perform graph classification, we employed a C-Support Vector Machine (SVM) classifier and performed 10-fold cross-validation. The whole process was repeated 10 times for each dataset and each method. |
| Hardware Specification | Yes | as measured on a 3.4GHz Intel Core i7 with 16Gb of RAM. |
| Software Dependencies | No | All kernels were written in Python2. This statement provides the language and its major version but does not list specific library or solver versions, which are necessary for reproducible software dependencies. |
| Experiment Setup | Yes | The parameter C of the SVM was optimized on the training set only. All kernels were written in Python2. The parameters of the base kernels and their corresponding core variants were selected using cross-validation on the training dataset. We chose parameters for the graph kernels as follows. For the graphlet kernel, on labeled graphs, we count all connected graphlets of size 3 taking labels into account, while on unlabeled graphs, we sample 500 graphlets of size up to 6. For the Weisfeiler-Lehman subtree kernel, we chose the number of iterations h from {4, 5, 6, 7}. For the pyramid match kernel, the dimensionality of the embeddings d was chosen from {4, 6, 8, 10}, while the number of levels L was chosen from {2, 4, 6}. |