A Theoretical Comparison of Graph Neural Network Extensions
Authors: Pál András Papp, Roger Wattenhofer
ICML 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study and compare different Graph Neural Network extensions that increase the expressive power of GNNs beyond the Weisfeiler-Leman test. We focus on (i) GNNs based on higher order WL methods, (ii) GNNs that preprocess small substructures in the graph, (iii) GNNs that preprocess the graph up to a small radius, and (iv) GNNs that slightly perturb the graph to compute an embedding. We begin by presenting a simple improvement for this last extension that strictly increases the expressive power of this GNN variant. Then, as our main result, we compare the expressiveness of these extensions to each other through a series of example constructions that can be distinguished by one of the extensions, but not by another one. We also show negative examples that are particularly challenging for each of the extensions, and we prove several claims about the ability of these extensions to count cliques and cycles in the graph. |
| Researcher Affiliation | Academia | 1Distributed Computing Group, ETH Z urich, Z urich, Switzerland. |
| Pseudocode | No | The paper describes algorithms verbally and with mathematical equations but does not include any explicitly labeled 'Pseudocode' or 'Algorithm' blocks. |
| Open Source Code | No | The paper does not contain any statements about making source code publicly available or links to a code repository. |
| Open Datasets | No | This is a theoretical paper and does not involve experiments with datasets, so there is no mention of training datasets or their availability. |
| Dataset Splits | No | This is a theoretical paper and does not involve experiments with datasets, so there is no mention of dataset splits (training, validation, test). |
| Hardware Specification | No | This is a theoretical paper and does not describe any computational experiments that would require hardware specifications. |
| Software Dependencies | No | This is a theoretical paper and does not describe any computational experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper and does not describe any computational experiments or hyperparameters. |