Appendix

In Appendix A, we introduce notations that we use throughout the rest of the appendix. B, we study the convergence of MPNNs and give the proof of Theorem 3.1. In Appendix C, we analyze generalization properties of MPNNs and prove our main contribution, Theorem 3.3 from Section 3. We give some details on the numerical experiments from Section 4 in Appendix D. For Let (χ, d) be a compact metric space. G the corresponding sampled graph. Based on the different version of degrees in Definition A.2, we define the corresponding three versions Next, we define the different norms used in our analysis.