Expressiveness and Approximation Properties of Graph Neural Networks
Authors: Floris Geerts, Juan L Reutter
ICLR 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Characterizing the separation power of graph neural networks (GNNs) provides an understanding of their limitations for graph learning tasks. Results regarding separation power are, however, usually geared at specific GNN architectures, and tools for understanding arbitrary GNN architectures are generally lacking. We provide an elegant way to easily obtain bounds on the separation power of GNNs in terms of the Weisfeiler-Leman (WL) tests, which have become the yardstick to measure the separation power of GNNs. The crux is to view GNNs as expressions in a procedural tensor language describing the computations in the layers of the GNNs. Then, by a simple analysis of the obtained expressions, in terms of the number of indexes and the nesting depth of summations, bounds on the separation power in terms of the WL-tests readily follow. |
| Researcher Affiliation | Academia | Floris Geerts Department of Computer Science, University of Antwerp, Belgium floris.geerts@uantwerpen.be Juan L. Reutter School of Engineering, Pontificia Universidad Cat olica de Chile, Chile & IMFD, Chile jreutter@ing.puc.cl |
| Pseudocode | No | The paper describes mathematical concepts and formalisms but does not include pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any information or links regarding the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and focuses on mathematical analysis of GNN properties; it does not involve datasets or empirical training. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments or dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments, thus no hardware specifications are provided. |
| Software Dependencies | No | The paper focuses on theoretical analysis and does not specify any software dependencies with version numbers for empirical reproduction. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments or provide details about experimental setup or hyperparameters. |