Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited
Authors: Nils M. Kriege
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We verify experimentally that walk-based kernels reach or even surpass the accuracy of Weisfeiler-Leman kernels in real-world classification tasks. 5 Experimental evaluation We experimentally verify the hypotheses that have originated from our theoretical results. |
| Researcher Affiliation | Academia | Nils M. Kriege Faculty of Computer Science, University of Vienna, Währinger Straße 29, 1090 Vienna, Austria Research Network Data Science @ Uni Vienna, Kolingasse 14 16, 1090 Vienna, Austria nils.kriege@univie.ac.at |
| Pseudocode | Yes | Algorithm 1: Generalized ℓ-walk node kernel Input: Graph G = (V, E), parameters ℓand α. Output: Kernel matrices K(i) and ˆ K(i) storing ki and ˆk+WL i for i ℓ, respectively. 1 A adjacency matrix of G G 2 w 1; w+ w 3 for i 1 to ℓdo 4 w Aw 5 w+ w+ + w 6 forall (u, v) V (G G) do 7 K(i) uv wuv 8 ˆK(i) uv e α(w+ uu+w+ vv 2w+ uv) Eq. (3) 9 wuv ˆK(i) uv (WL expressiveness) |
| Open Source Code | Yes | Our code is publicly available at https://github.com/nlskrg/node_centric_walk_kernels. |
| Open Datasets | Yes | We tested on widely-used graph classification benchmarks datasets of the TUDATASETS repository [32] representing graphs from different domains. MUTAG, NCI1, NCI109 and PTC-FM represent small molecules, ENZYMES and PROTEINS are derived from macromolecules, and COLLAB and IMDBBIN are social networks. All used datasets are publicly available. |
| Dataset Splits | Yes | We report mean prediction accuracies and standard deviations obtained by 10-fold nested cross-validation repeated 10 times with random fold assignment. Within each fold all necessary parameters were selected by cross-validation based on the training set. |
| Hardware Specification | Yes | All experiments were performed on an Intel Xeon E5-2690v4 machine at 2.6GHz with 384 GB of RAM. |
| Software Dependencies | No | We implemented the node-centric ℓ-walk graph kernel as well as all baselines in Java. We performed classification experiments with the C-SVM implementation LIBSVM [6]. However, specific version numbers for Java or LIBSVM are not provided. |
| Experiment Setup | Yes | For the Weisfeiler-Leman subtree kernel (WL), the ℓ-step random walk kernel (RW) as well as NCW and NCWWL we chose the iteration number and walk length from {0, . . . , 5} by cross-validation. For RW, λi = 1 for i {0, . . . , ℓ} was used. For NCW and NCWWL, we selected α from {0.01, 0.1, 1, 1000} and β from {0, 0.5, 1}. |