The Logical Expressiveness of Graph Neural Networks
Authors: Pablo Barceló, Egor V. Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, Juan Pablo Silva
ICLR 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We perform experiments with synthetic data to empirically validate our results. The motivation of this section is to show that the theoretical expressiveness of ACR-GNNs, as well as the differences between ACand ACR-GNNs, can actually be observed when we learn from examples. We perform two sets of experiments: experiments to show that ACR-GNNs can learn a very simple FOC2 node classifier that AC-GNNs cannot learn, and experiments involving complex FOC2 classifiers that need more intermediate readouts to be learned. We implemented our experiments in the Py Torch Geometric library (Fey & Lenssen, 2019). Besides testing simple AC-GNNs, we also tested the GIN network proposed by Xu et al. (2019) (we consider the implementation by Fey & Lenssen (2019) and adapted it to classify nodes). Our experiments use synthetic graphs, with five initial colors encoded as one-hot features, divided in three sets: train set with 5k graphs of size up to 50-100 nodes, test set with 500 graphs of size similar to the train set, and another test set with 500 graphs of size bigger than the train set. We tried several configurations for the aggregation, combination and readout functions, and report the accuracy on the best configuration. Accuracy in our experiments is computed as the total number of nodes correctly classified among all nodes in all the graphs in the dataset. |
| Researcher Affiliation | Academia | Pablo Barcel o IMC, PUC & IMFD Chile Egor V. Kostylev University of Oxford Mika el Monet IMFD Chile Jorge P erez DCC, UChile & IMFD Chile Juan Reutter DCC, PUC & IMFD Chile Juan-Pablo Silva DCC, UChile |
| Pseudocode | No | No pseudocode or clearly labeled algorithm block was found in the paper. |
| Open Source Code | Yes | All our code and data can be accessed online at https://github.com/juanpablos/ GNN-logic |
| Open Datasets | Yes | We also tested ACand ACR-GNNs on the Protein-Protein Interaction (PPI) benchmark (Zitnik & Leskovec, 2017). |
| Dataset Splits | Yes | Our experiments use synthetic graphs, with five initial colors encoded as one-hot features, divided in three sets: train set with 5k graphs of size up to 50-100 nodes, test set with 500 graphs of size similar to the train set, and another test set with 500 graphs of size bigger than the train set. |
| Hardware Specification | No | No specific hardware details (e.g., GPU/CPU models, memory) used for running experiments are provided. The paper only mentions 'a GPU' in general terms of GNNs being run on them. |
| Software Dependencies | No | The paper mentions 'Py Torch Geometric library (Fey & Lenssen, 2019)' but does not specify a version number. |
| Experiment Setup | Yes | In every case we run up to 20 epochs with the Adam optimizer. |