{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T16:23:53Z","timestamp":1790785433410,"version":"4.1.0"},"reference-count":46,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["NSF DMS 2031985"],"award-info":[{"award-number":["NSF DMS 2031985"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["KU 1446\/27-2"],"award-info":[{"award-number":["KU 1446\/27-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"crossref","award":["05M20 MaGriDo"],"award-info":[{"award-number":["05M20 MaGriDo"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100023863","name":"Munich Center for Machine Learning","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100023863","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["DFG-SPP-2298"],"award-info":[{"award-number":["DFG-SPP-2298"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["KU 1446\/31-1"],"award-info":[{"award-number":["KU 1446\/31-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["KU 1446\/32-1"],"award-info":[{"award-number":["KU 1446\/32-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["DFG-SFB\/TR 109"],"award-info":[{"award-number":["DFG-SFB\/TR 109"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["C09"],"award-info":[{"award-number":["C09"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002347","name":"Federal Ministry of Education and Research","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Bavarian Ministry of Science and the Arts"},{"DOI":"10.13039\/501100006114","name":"SMWK","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006114","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1937\/23"],"award-info":[{"award-number":["1937\/23"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM Journal on Mathematics of Data Science"],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We study the generalization capabilities of message passing neural networks (MPNNs), a prevalent class of graph neural networks. We derive generalization bounds specifically for MPNNs with normalized sum aggregation and mean aggregation. Our analysis is based on a data generation model incorporating a finite set of template graphons. Each graph within this framework is generated by sampling from one of the graphons with a certain degree of perturbation. In particular, we extend previous MPNN generalization results to a more realistic setting, which includes the following modifications: (1) We analyze simple random graphs with Bernoulli-distributed edges instead of weighted graphs, (2) we sample both graphs and graph signals from perturbed graphons instead of clean graphons, and (3) we analyze sparse graphs instead of dense graphs. In this more realistic and challenging scenario, we provide a generalization bound that decreases as the average number of nodes in the graphs increases. Our results imply that MPNNs with higher complexity than the size of the training set can still generalize effectively as long as the graphs are sufficiently large.<\/jats:p>","DOI":"10.1137\/24m1651526","type":"journal-article","created":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T03:06:16Z","timestamp":1750129576000},"page":"802-825","source":"Crossref","is-referenced-by-count":2,"title":["Generalization Bounds for Message Passing Networks on Mixture of Graphons"],"prefix":"10.1137","volume":"7","author":[{"given":"Sohir","family":"Maskey","sequence":"first","affiliation":[{"name":"Department of Mathematics, LMU Munich, 80333 Munich, Germany, and Munich Center for Machine Learning (MCML), 80539 Munich, Germany,."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9738-2487","authenticated-orcid":true,"given":"Gitta","family":"Kutyniok","sequence":"additional","affiliation":[{"name":"Department of Mathematics, LMU Munich, 80333 Munich, Germany, and Munich Center for Machine Learning (MCML), 80539 Munich, Germany,."},{"name":"Department of Physics and Technology, University of Troms\u00f8, 9019 Troms\u00f8, Norway, and German Aerospace Center (DLR), 82234 We\u00dfling, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ron","family":"Levie","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics, Technion\u2013Israel Institute of Technology, 32000 Haifa, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,6,17]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1016\/0047-259X(81)90099-3","volume":"11","author":"Aldous D. J.","year":"1981","journal-title":"J. Multivariate Anal."},{"key":"ref2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BFb0099420","volume-title":"\u00c9cole d\u2019\u00c9t\u00e9 de Probabilit\u00e9s de Saint-Flour XIII, 1983","author":"Aldous D. J.","year":"1985"},{"key":"ref3","doi-asserted-by":"crossref","first-page":"72","DOI":"10.4153\/S0008414X2000070X","volume":"74","author":"Backhausz \u00c1.","year":"2022","journal-title":"Canad. J. Math."},{"key":"ref4","doi-asserted-by":"crossref","first-page":"1801","DOI":"10.1016\/j.aim.2008.07.008","volume":"219","author":"Borgs C.","year":"2008","journal-title":"Adv. Math."},{"key":"ref5","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1109\/MSP.2017.2693418","volume":"34","author":"Bronstein M. M.","year":"2017","journal-title":"IEEE Signal Process. Mag."},{"key":"ref6","unstructured":"C. Cai and Y. Wang (2022), Convergence of invariant graph networks, in Proceedings of the 39th International Conference on Machine Learning, Proceedings of Machine Learning Research 162, PMLR, pp. 2457\u20132484."},{"key":"ref7","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1109\/TSP.2023.3242374","volume":"71","author":"Cervino J.","year":"2023","journal-title":"IEEE Trans. Signal Process."},{"key":"ref8","first-page":"1","volume":"25","author":"Cordonnier M.","year":"2023","journal-title":"J. Mach. Learn. Res."},{"key":"ref9","unstructured":"G. Corso, H. St\u00e4rk, B. Jing, R. Barzilay, and T. Jaakkola (2023), DiffDock: Diffusion steps, twists, and turns for molecular docking, in International Conference on Learning Representations, ICLR."},{"key":"ref10","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1038\/s41586-021-04086-x","volume":"600","author":"Davies A.","year":"2021","journal-title":"Nature"},{"key":"ref11","volume":"32","author":"Du S. S.","year":"2019","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref12","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"Erd\u00f6s P.","year":"1959","journal-title":"Publ. Math. Debrecen"},{"key":"ref13","doi-asserted-by":"crossref","first-page":"5680","DOI":"10.1109\/TSP.2020.3026980","volume":"68","author":"Gama F.","year":"2020","journal-title":"IEEE Trans. Signal Process."},{"key":"ref14","unstructured":"V. Garg, S. Jegelka, and T. Jaakkola (2020), Generalization and representational limits of graph neural networks,in Proceedings of the 37th International Conference on Machine Learning, Proceedings of Machine Learning Research 119, PMLR, pp. 3419\u20133430."},{"key":"ref15","unstructured":"J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl (2017), Neural message passing for quantum chemistry, in Proceedings of the 34th International Conference on Machine Learning, Proceedings of Machine Learning Research 70, PMLR, pp. 1263\u20131272."},{"key":"ref16","first-page":"1025","volume":"31","author":"Hamilton W. L.","year":"2017","journal-title":"Adv. Neural Inform. Process. Sys."},{"key":"ref17","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0378-8733(83)90021-7","volume":"5","author":"Holland P. W.","year":"1983","journal-title":"Soc. Netw."},{"key":"ref18","volume-title":"Relations on Probability Spaces and Arrays of Random Variables","author":"Hoover D. N.","year":"1979"},{"key":"ref19","first-page":"281","volume-title":"Exchangeability in Probability and Statistics","author":"Hoover D. N.","year":"1982"},{"key":"ref20","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1038\/s41586-021-03819-2","volume":"596","author":"Jumper J.","year":"2021","journal-title":"Nature"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"H. Kenlay, D. Thano, and X. Dong (2021), On the stability of graph convolutional neural networks under edge rewiring, in International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, pp. 8513\u20138517.","DOI":"10.1109\/ICASSP39728.2021.9413474"},{"key":"ref22","first-page":"2268","volume-title":"Advances in Neural Information Processing Systems","volume":"35","author":"Keriven N.","year":"2022"},{"key":"ref23","first-page":"21512","volume-title":"Advances in Neural Information Processing Systems","volume":"34","author":"Keriven N.","year":"2020"},{"key":"ref24","first-page":"41305","volume-title":"Advances in Neural Information Processing Systems","volume":"36","author":"Le T.","year":"2024"},{"key":"ref25","first-page":"64482","volume-title":"Advances in Neural Information Processing Systems","volume":"36","author":"Levie R.","year":"2024"},{"key":"ref26","first-page":"1","volume":"22","author":"Levie R.","year":"2021","journal-title":"J. Mach. Learn. Res."},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"G. Li, M. M\u00fcller, A. Thabet, and B. Ghanem (2019), DeepGCNs: Can GCNs go as deep as CNNs? in Proceedings of the IEEE\/CVF International Conference on Computer Vision (ICCV), pp. 9266\u20139275.","DOI":"10.1109\/ICCV.2019.00936"},{"key":"ref28","first-page":"3538","volume":"32","author":"Li Q.","year":"2018","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"key":"ref29","unstructured":"R. Liao, R. Urtasun, and R. Zemel (2021), A PAC-Bayesian approach to generalization bounds for graph neural networks, in International Conference on Learning Representations, ICLR."},{"key":"ref30","doi-asserted-by":"crossref","DOI":"10.1090\/coll\/060","volume-title":"Large Networks and Graph Limits","author":"Lov\u00e1sz L.","year":"2012"},{"key":"ref31","unstructured":"H. Maron, H. Ben-Hamu, N. Shamir, and Y. Lipman (2019), Invariant and equivariant graph networks, in International Conference on Learning Representations, ICLR, pp. 5485\u20135498."},{"key":"ref32","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/j.acha.2022.11.008","volume":"63","author":"Maskey S.","year":"2023","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"ref33","first-page":"35","volume-title":"Advances in Neural Information Processing Systems","author":"Maskey S.","year":"2022"},{"key":"ref34","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1038\/s41586-023-06735-9","volume":"624","author":"Merchant A.","year":"2023","journal-title":"Nature"},{"key":"ref35","unstructured":"C. Morris, F. Geerts, J. T\u00f6nshoff, and M. Grohe (2023), WL meet VC, in Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research 202, PMLR, pp. 25275\u201325302, https:\/\/proceedings.mlr.press\/v202\/morris23a\/morris23a.pdf."},{"key":"ref36","doi-asserted-by":"crossref","unstructured":"C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe (2019), Weisfeiler and Leman go neural: Higher-order graph neural networks, in Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33, AAAI, pp. 4602\u20134609, https:\/\/dl.acm.org\/doi\/10.1609\/aaai.v33i01.33014602.","DOI":"10.1609\/aaai.v33i01.33014602"},{"key":"ref37","unstructured":"H. NT and T. Maehara (2019), Revisiting Graph Neural Networks: All We Have Is Low-Pass Filters, preprint, https:\/\/arxiv.org\/abs\/1905.09550."},{"key":"ref38","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001","volume-title":"Random Geometric Graphs","author":"Penrose M.","year":"2003"},{"key":"ref39","first-page":"1702","volume":"33","author":"Ruiz L.","year":"2020","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref40","doi-asserted-by":"crossref","first-page":"3474","DOI":"10.1109\/TSP.2023.3297848","volume":"71","author":"Ruiz L.","year":"2021","journal-title":"IEEE Transactions on Signal Processing"},{"key":"ref41","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1109\/JPROC.2021.3055400","volume":"109","author":"Ruiz L.","year":"2021","journal-title":"Proceedings of the IEEE"},{"key":"ref42","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1109\/TNN.2008.2005605","volume":"20","author":"Scarselli F.","year":"2009","journal-title":"IEEE Transactions on Neural Networks"},{"key":"ref43","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1016\/j.neunet.2018.08.010","volume":"108","author":"Scarselli F.","year":"2018","journal-title":"Neural Netw."},{"key":"ref44","doi-asserted-by":"crossref","first-page":"688","DOI":"10.1016\/j.cell.2020.01.021","volume":"180","author":"Stokes J. M.","year":"2020","journal-title":"Cell"},{"key":"ref45","doi-asserted-by":"crossref","unstructured":"S. Verma and Z.L. Zhang (2019), Stability and generalization of graph convolutional neural networks, in Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, pp. 1539\u20131548.","DOI":"10.1145\/3292500.3330956"},{"key":"ref46","unstructured":"K. Xu, W. Hu, J. Leskovec, and S. Jegelka (2019), How powerful are graph neural networks? in International Conference on Learning Representations, ICLR, pp. 9104\u20139120."}],"container-title":["SIAM Journal on Mathematics of Data Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1651526","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:41:58Z","timestamp":1787326918000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1651526"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1137\/24M1651526"],"URL":"https:\/\/doi.org\/10.1137\/24m1651526","relation":{},"ISSN":["2577-0187"],"issn-type":[{"value":"2577-0187","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}