Generalization Analysis of Message Passing Neural Networks on Large Random Graphs
Authors: Sohir Maskey, Ron Levie, Yunseok Lee, Gitta Kutyniok
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We give empirical evaluations of our generalization bound in comparison to the PAC-Bayesian based bound [Liao et al., 2021] and the Rademacher complexity based bound [Garg et al., 2020]. We experiment on a synthetic dataset of 100K random graphs of 50 nodes, sampled from three different RGMs... |
| Researcher Affiliation | Academia | Sohir Maskey Ludwig-Maximilian University of Munich maskey@math.lmu.de Technion Israel Institute of Technology levieron@technion.ac.il Yunseok Lee Ludwig-Maximilian University of Munich ylee@math.lmu.de Gitta Kutyniok Ludwig-Maximilian University of Munich University of Tromsø kutyniok@math.lmu.de |
| Pseudocode | No | The paper provides mathematical definitions, theorems, and proofs but does not include any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The experiments are very simple which is why we decided to not include the code. |
| Open Datasets | No | We experiment on a synthetic dataset of 100K random graphs of 50 nodes, sampled from three different RGMs: the Erdös-Rényi model (ERM) with edge probability 0.4, a smooth version of a stochastic block model (SBM), based on the kernel K(x, y) = sin(2πx) sin(2πy)/2π + 0.25 on [0, 1]2, and a geometric graph with kernel K(x, y) = exp( |x y|2). The corresponding signals are given in Appendix D.2.1. |
| Dataset Splits | No | The paper mentions using a 'synthetic dataset of 100K random graphs' and refers to a 'training set T', but does not provide specific details on training, validation, or test splits such as percentages or sample counts. |
| Hardware Specification | No | The paper states, in its ethics checklist, that 'We did not perform training, i.e., the experiments were toy examples and not computation heavy', and does not provide specific details on hardware specifications such as GPU or CPU models. |
| Software Dependencies | No | For the MPNN we consider Graph SAGE [Hamilton et al., 2017] with mean aggregation, and number of layers T = 1, 2 or 3, implemented using Pytorch Geometric [Fey and Lenssen, 2019]. |
| Experiment Setup | Yes | For the MPNN we consider Graph SAGE [Hamilton et al., 2017] with mean aggregation, and number of layers T = 1, 2 or 3, implemented using Pytorch Geometric [Fey and Lenssen, 2019]. We consider a maximal hidden dimension of 128. In Appendix D we give more details and also consider synthetic data sampled from additional RGMs. To control the Lipschitz constants, we consider two learning settings. First, we train with weight decay regularization, which decreases the Lipschitz bounds, and second, we train with no regularization. |