$\mathscr{N}$-WL: A New Hierarchy of Expressivity for Graph Neural Networks
Authors: Qing Wang, Dillon Ze Chen, Asiri Wijesinghe, Shouheng Li, Muhammad Farhan
ICLR 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We run experiments on synthetic and real-world datasets to empirically validate the theoretical properties of G3N. Table 2: Graph isomorphism tasks on EXP, SR25, graph8c and CSL are evaluated by counting the pairs of graphs which are indistinguishable. Substructure counting tasks are performed on the Random Graph dataset and evaluated by MSE. |
| Researcher Affiliation | Academia | School of Computing, Australian National University {qing.wang,dillon.chen2,asiri.wijesinghe}@anu.edu.au {shouheng.li,muhammad.farhan}@anu.edu.au |
| Pseudocode | No | No explicit pseudocode or algorithm block labeled as such was found. The model design is presented using mathematical equations and descriptive text. |
| Open Source Code | Yes | The code is available at https://github.com/seanli3/G3N. |
| Open Datasets | Yes | EXP (Abboud et al., 2021) consists of 600 pairs of nonisomorphic graphs (Gi, Hi) each encoding a propositional formula which is either satisfiable or not. The graphs are designed to be indistinguishable by 1-WL. SR251 (Balcilar et al., 2021) contains 15 strongly regular graphs, each with 25 nodes and indistinguishable by 3-WL. graph8c (Balcilar et al., 2021) contains all 11,117 connected non-isomorphic 8-node graphs, of which 312 pairs are indistinguishable by 1-WL and all are distinguishable by 3-WL. CSL was first introduced by Murphy et al. (2019) and commonly used to test graph expressiveness (Dwivedi et al., 2020). It consists of 10 isomorphism classes of 41 node 4-regular graphs which are almost all distinguishable by 3-WL. For counting graph substructures, we consider Random Graph (Chen et al., 2020). |
| Dataset Splits | Yes | For the TU datasets, we compared G3N against (1) three kernel methods RWK (Gärtner et al., 2003), WL-kernel (Shervashidze et al., 2011), and P-WL (Rieck et al., 2019); (2) five GNN models PATCHY-SAN (Niepert et al., 2016), DCNN (Atwood & Towsley, 2016), DGCNN (Zhang et al., 2018), GIN (Xu et al., 2019), and PPGN (Maron et al., 2019a). Mol HIV. We follow the train, validation and test split from Hu et al. (2020) and evaluate on the test score corresponding to the best validation score. |
| Hardware Specification | Yes | The experiments for this section were run on an RTX 3090 GPU. |
| Software Dependencies | No | No specific versions for software dependencies (e.g., Python, PyTorch, CUDA) are mentioned. Only mentions general libraries or frameworks without version numbers. |
| Experiment Setup | Yes | For the Random Graph dataset, all models are also restricted to a 30K parameter budget, consisting of 4 convolutional layers, sum readout, and a further 2 fully connected layers trained for up to 200 iterations with a fixed learning rate of 0.001. Learning terminates when error goes below 10-4. For the TU datasets... We fix t = 2, d = 2, hidden units of 128 and learning rate of 0.001 which is halved every 50 steps. ZINC. ...batch size 128 and 1000 epochs with initial learning rate of 10-3 which is halved when validation does not improve over after 20 steps and training is halted when the learning rate goes under 10-5. |