A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests
Authors: Bohang Zhang, Guhao Feng, Yiheng Du, Di He, Liwei Wang
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our central result is to build a complete hierarchy of SWL with strictly growing expressivity. Concretely, we prove that any node-based subgraph GNN falls into one of the six SWL equivalence classes, among which SSWL achieves the maximal expressive power. We also study how these equivalence classes differ in terms of their practical expressiveness such as encoding graph distance and biconnectivity. In addition, we give a tight expressivity upper bound of all SWL algorithms by establishing a close relation with localized versions of WL and Folklore WL (FWL) tests. Overall, our results provide insights into the power of existing subgraph GNNs, guide the design of new architectures, and point out their limitations by revealing an inherent gap with the 2-FWL test. Finally, experiments demonstrate that SSWL-inspired subgraph GNNs can significantly outperform prior architectures on multiple benchmarks despite great simplicity. |
| Researcher Affiliation | Academia | 1National Key Laboratory of General Artificial Intelligence, School of Intelligence Science and Technology, Peking University 2School of EECS, Peking University 3Pazhou Lab 4Yuanpei College, Peking University 5Center for Data Science, Peking University. |
| Pseudocode | No | The paper describes the model mathematically but does not include explicit pseudocode or algorithm blocks. |
| Open Source Code | Yes | Our code will be released at https://github.com/subgraph23/SWL. |
| Open Datasets | Yes | We conduct experiments on three standard benchmark datasets: ZINC (Dwivedi et al., 2020), Counting Substructure (Zhao et al., 2022a; Frasca et al., 2022), and OGBG-molhiv (Hu et al., 2020). |
| Dataset Splits | Yes | The learning rate will be decayed by a factor of 0.5 when the MAE on validation set plateaus for 20 epochs (similar to Frasca et al., 2022). |
| Hardware Specification | Yes | All experiments are run on a single NVIDIA Tesla V100 GPU. |
| Software Dependencies | No | The paper mentions 'Pytorch (Paszke et al., 2019) and Pytorch Geometric (Fey & Lenssen, 2019)' but does not provide specific version numbers for these software dependencies. |
| Experiment Setup | Yes | Throughout all experiments, we set the number of layers L = 6, similar to Frasca et al. (2022). To constrain the parameter budget within 500k, the feature dimension of each layer is set to 96. The initial atom embedding, distance embedding, and edge embedding is also set to 96. The hyper-parameter max dis is set to 5. We adopt the Adam optimizer (Kingma & Ba, 2014) with an initial learning rate 0.001. The learning rate will be decayed by a factor of 0.5 when the MAE on validation set plateaus for 20 epochs (similar to Frasca et al. (2022)). The batch size is set to 128. |