The Expressive Power of Path-Based Graph Neural Networks
Authors: Caterina Graziani, Tamara Drucks, Fabian Jogl, Monica Bianchini, Franco Scarselli, Thomas Gärtner
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | To empirically evaluate our findings, we design PAIN (PATH ISOMORPHISM NETWORK), a family of GNN architectures with expressive power equivalent to PATH-WL (cf. Remark 5.1). We evaluate PAIN on three datasets designed for studying the expressivity of GNNs and on two real-world benchmark datasets. |
| Researcher Affiliation | Academia | 1Department of Information Engineering and Mathematics, University of Siena, Siena, Italy 2RUML, TU Wien, Vienna, Austria 3CAIML, TU Wien, Vienna, Austria. |
| Pseudocode | No | The paper provides a formal definition of PATH-WL (Definition 3.2) with mathematical notation, but it does not present pseudocode or a clearly labeled algorithm block in a code-like format. |
| Open Source Code | Yes | Our code can be found at https://github.com/ocatias/Expressive Path GNNs and https://github. com/tamaramagdr/synthetic-pain. |
| Open Datasets | Yes | To study the expressivity of the PAIN family, we use the synthetic datasets EXP (Abboud et al., 2021), SR (Balcilar et al., 2021) and CSL (Murphy et al., 2019). Additionally, for real-world evaluation, we use ZINC (G omez-Bombarelli et al., 2018; Sterling & Irwin, 2015) and OGBG-MOLHIV (Hu et al., 2020; Wu et al., 2018). |
| Dataset Splits | Yes | For CSL, we perform stratified 5-fold cross validation with a 3:1:1 split. |
| Hardware Specification | Yes | We conduct our experiments on servers equipped with an RTX-3080 GPU and Intel Core i7-10700KF/i9-11900KF CPU. |
| Software Dependencies | No | The paper mentions software used: 'We use Py Torch (Paszke et al., 2019) and Py Torch Geometric (Fey & Lenssen, 2019)'. However, specific version numbers for these software dependencies are not provided, which is required for reproducibility. |
| Experiment Setup | Yes | For EXP and SR, we closely follow the experimental setup of Michel et al. (2023). We use an untrained PAIN with a two-layer LSTM to compute 16-dimensional embeddings. We use Euclidean normalization on the input for the LSTM and consider two representations the same if the Euclidean distance is below = 10 5. Analogous to Michel et al. (2023), for SR we restrict the path length to four due to computational considerations and use path length five for EXP. All presented results are repeated over five seeds. We use a one-layer 0-PAIN for EXP and a one-layer 1-PAIN for SR. For CSL, we perform stratified 5-fold cross validation with a 3:1:1 split. We train a small PAIN model with an embedding dimension of 16. We train 500 epochs with a fixed learning rate of 10 5. We perform ablations for different values of the path length {1, . . . , 6}, number of layers n {1, 2}, and distance encoding depth d {0, 1, }. On ZINC we train a five-layer 1-PAIN with path length three and embedding dimension 128. As common on ZINC, we train with an initial learning rate of 10 3 that we halve whenever the validation metric does not increase for 20 epochs. The training stops after the learning rate dips below 10 5 or after 1 000 epochs. On OGBG-MOLHIV it is folklore knowledge that smaller networks perform better. We thus train a one-layer 1-PAIN with path length two, which is the same path length as used by Michel et al. (2023). To further avoid over-fitting we use a dropout rate of 0.5. As is common on this dataset we train with a fixed learning rate 10 3 for a fixed number of 100 epochs. |