{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T18:51:12Z","timestamp":1779389472333,"version":"3.53.1"},"reference-count":55,"publisher":"Springer Science and Business Media LLC","issue":"13-14","license":[{"start":{"date-parts":[[2024,7,1]],"date-time":"2024-07-01T00:00:00Z","timestamp":1719792000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,5]],"date-time":"2024-07-05T00:00:00Z","timestamp":1720137600000},"content-version":"vor","delay-in-days":4,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100012990","name":"Universit\u00e0 degli Studi di Siena","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100012990","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soft Comput"],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Graph neural networks (GNNs) are a broad class of connectionist models for graph processing. Recent studies have shown that GNNs can approximate any function on graphs, modulo the equivalence relation on graphs defined by the Weisfeiler\u2013Lehman (WL) test. However, these results suffer from some limitations, both because they were derived using the Stone\u2013Weierstrass theorem\u2014which is existential in nature\u2014and because they assume that the target function to be approximated must be continuous. Furthermore, all current results are dedicated to graph classification\/regression tasks, where the GNN must produce a single output for the whole graph, while also node classification\/regression problems, in which an output is returned for each node, are very common. In this paper, we propose an alternative way to demonstrate the approximation capability of GNNs that overcomes these limitations. Indeed, we show that GNNs are universal approximators in probability for node classification\/regression tasks, as they can approximate any measurable function that satisfies the 1-WL-equivalence on nodes. The proposed theoretical framework allows the approximation of generic discontinuous target functions and also suggests the GNN architecture that can reach a desired approximation. In addition, we provide a bound on the number of the GNN layers required to achieve the desired degree of approximation, namely <jats:inline-formula><jats:alternatives><jats:tex-math>$$2r-1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mi>r<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where <jats:italic>r<\/jats:italic> is the maximum number of nodes for the graphs in the domain.<\/jats:p>","DOI":"10.1007\/s00500-024-09676-1","type":"journal-article","created":{"date-parts":[[2024,7,5]],"date-time":"2024-07-05T08:02:22Z","timestamp":1720166542000},"page":"8527-8547","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["On the approximation capability of GNNs in node classification\/regression tasks"],"prefix":"10.1007","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7367-4354","authenticated-orcid":false,"given":"Giuseppe Alessio","family":"D\u2019Inverno","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Monica","family":"Bianchini","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maria Lucia","family":"Sampoli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Franco","family":"Scarselli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,7,5]]},"reference":[{"key":"9676_CR1","doi-asserted-by":"crossref","unstructured":"Abboud R, Ceylan \u0130\u0130, Grohe M, Lukasiewicz T(2020) The surprising power of graph neural networks with random node initialization. arXiv preprint arXiv:2010.01179","DOI":"10.24963\/ijcai.2021\/291"},{"key":"9676_CR2","unstructured":"Alon U, Yahav E (2020) On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.05205"},{"key":"9676_CR3","doi-asserted-by":"crossref","unstructured":"Angluin D (1980) Local and global properties in networks of processors (extended abstract). In: Proceedings of the 12th annual ACM symposium on theory of computing. Association for Computing Machinery, New York, pp 82\u201393","DOI":"10.1145\/800141.804655"},{"key":"9676_CR4","unstructured":"Azizian W, Lelarge M (2020) Expressive power of invariant and equivariant graph neural networks. arXiv preprint arXiv:2006.15646"},{"key":"9676_CR5","first-page":"1","volume":"2010","author":"N Bandinelli","year":"2010","unstructured":"Bandinelli N, Bianchini M, Scarselli F (2010) Learning long-term dependencies using layered graph neural networks. Proc IJCNN 2010:1\u20138","journal-title":"Proc IJCNN"},{"key":"9676_CR6","unstructured":"Barcel\u00f3 P et\u00a0al (2020) The logical expressiveness of graph neural networks. In: Proceedings of the 8th international conference on learning representations (ICLR 2020)"},{"key":"9676_CR7","unstructured":"Battaglia P et\u00a0al (2018) Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01261"},{"key":"9676_CR8","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1109\/72.950127","volume":"12","author":"M Bianchini","year":"2001","unstructured":"Bianchini M, Gori M (2001) Theoretical properties of recursive neural networks with linear neurons. IEEE Trans Neural Netw 12:953\u2013967","journal-title":"IEEE Trans Neural Netw"},{"key":"9676_CR9","unstructured":"Bodnar C et al (2021a) Weisfeiler and Lehman go topological: message passing simplicial networks (PMLR), pp 1026\u20131037"},{"key":"9676_CR10","unstructured":"Bodnar C et al (2021b) Weisfeiler and Lehman go cellular: CW networks. Adv Neural Inf Process Syst 34:2625\u20132640"},{"key":"9676_CR11","unstructured":"Bouritsas G, Frasca F, Zafeiriou S, Bronstein MM (2020) Improving graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2006.09252"},{"key":"9676_CR12","unstructured":"Brugiapaglia S, Liu M, Tupper P (2020)Generalizing outside the training set: when can neural networks learn identity effects? arXiv preprint arXiv:2005.04330"},{"key":"9676_CR13","doi-asserted-by":"publisher","first-page":"1756","DOI":"10.1162\/neco_a_01510","volume":"34","author":"S Brugiapaglia","year":"2022","unstructured":"Brugiapaglia S, Liu M, Tupper P (2022) Invariance, encodings, and generalization: learning identity effects with neural networks. Neural Comput 34:1756\u20131789","journal-title":"Neural Comput"},{"key":"9676_CR14","unstructured":"Bruna J, Zaremba W, Szlam A, LeCun Y (2014) Spectral networks and locally connected networks on graphs. In: Proceedings of ICLR 2014"},{"key":"9676_CR15","unstructured":"Dell H, Grohe M, Rattan G (2018) Lov\u00e1sz meets Weisfeiler and Leman. arXiv preprint arXiv:1802.08876"},{"key":"9676_CR16","unstructured":"D\u2019Inverno GA, Brugiapaglia S, Ravanelli M (2023)Generalization limits of graph neural networks in identity effects learning. arXiv preprint arXiv:2307.00134"},{"key":"9676_CR17","unstructured":"Garg V, Jegelka S, Jaakkola T (2020) Generalization and representational limits of graph neural networks. In: Proceedings of ICML 2020 (PMLR), pp 3419\u20133430"},{"key":"9676_CR18","unstructured":"Gilmer J, Schoenholz SS, Riley PF, Vinyals O, Dahl GE (2017) Neural message passing for quantum chemistry. In: Proceedings of ICML 2017 (PMLR), pp 1263\u20131272"},{"key":"9676_CR19","doi-asserted-by":"crossref","unstructured":"Gori M, Monfardini G, Scarselli F (2005) A new model for learning in graph domains. In: Proceedings of IJCNN 2005, vol 2, pp 729\u2013734","DOI":"10.1109\/IJCNN.2005.1555942"},{"key":"9676_CR20","first-page":"13481","volume":"30","author":"W Hamilton","year":"2017","unstructured":"Hamilton W, Ying Z, Leskovec J (2017) Inductive representation learning on large graphs. Adv Neural Inf Process Syst 30:13481","journal-title":"Adv Neural Inf Process Syst"},{"key":"9676_CR21","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0893-6080(91)90009-T","volume":"4","author":"K Hornik","year":"1991","unstructured":"Hornik K (1991) Approximation capabilities of multilayer feedforward networks. Neural Netw 4:251\u2013257","journal-title":"Neural Netw"},{"key":"9676_CR22","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/0893-6080(89)90020-8","volume":"2","author":"K Hornik","year":"1989","unstructured":"Hornik K, Stinchcombe M, White H (1989) Multilayer feedforward networks are universal approximators. Neural Netw 2:359\u2013366","journal-title":"Neural Netw"},{"key":"9676_CR23","doi-asserted-by":"crossref","unstructured":"Jegelka S (2022) Theory of graph neural networks: representation and learning. arXiv preprint arXiv:2204.07697","DOI":"10.4171\/icm2022\/162"},{"key":"9676_CR24","unstructured":"Keriven N, Peyr\u00e9 G (2019) Universal invariant and equivariant graph neural networks. In: Advances in neural information processing systems (NeurIPS 2019)"},{"key":"9676_CR25","unstructured":"Kiefer S (2020) Power and limits of the Weisfeiler\u2013Lehman algorithm. Ph.D. thesis, Dissertation, RWTH Aachen University"},{"key":"9676_CR26","unstructured":"Kiefer S, McKay BD (2020) The iteration number of colour refinement. In: Proceedings of the 47th international colloquium on automata, languages, and programming (ICALP 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"key":"9676_CR27","unstructured":"Kipf TN, Welling M (2017) Semi-supervised classification with graph convolutional networks. In: Proceedings of ICLR 2017"},{"key":"9676_CR28","doi-asserted-by":"crossref","unstructured":"Krebs A, Verbitsky O (2015) Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth. In: Proceedings of the 30th annual ACM\/IEEE symposium on logic in computer science (IEEE), pp 689\u2013700","DOI":"10.1109\/LICS.2015.69"},{"key":"9676_CR29","first-page":"12","volume":"2","author":"AA Lehman","year":"1968","unstructured":"Lehman AA, Weisfeiler B (1968) A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsiya 2:12\u201316","journal-title":"Nauchno-Technicheskaya Informatsiya"},{"key":"9676_CR30","unstructured":"Li Y et\u00a0al (2015) Gated graph sequence neural networks. arXiv preprint arXiv:1511.05493"},{"key":"9676_CR31","unstructured":"Li Y, Tarlow D, Brockschmidt M, Zemel R (2015) Gated graph sequence neural networks. arXiv preprint arXiv:1511.05493"},{"key":"9676_CR32","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N Linial","year":"1992","unstructured":"Linial N (1992) Locality in distributed graph algorithms. SIAM J Comput 21:193\u2013201","journal-title":"SIAM J Comput"},{"key":"9676_CR33","unstructured":"Loukas A (2019) What graph neural networks cannot learn: depth vs width. arXiv preprint arXiv:1907.03199"},{"key":"9676_CR34","unstructured":"Maron H, Ben-Hamu H, Shamir N, Lipman Y (2018) Invariant and equivariant graph networks. arXiv preprint arXiv:1812.09902"},{"key":"9676_CR35","first-page":"472","volume":"32","author":"H Maron","year":"2019","unstructured":"Maron H, Ben-Hamu H, Serviansky H, Lipman Y (2019) Provably powerful graph networks. Adv Neural Inf Process Syst 32:472","journal-title":"Adv Neural Inf Process Syst"},{"key":"9676_CR36","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1109\/TNN.2008.2010350","volume":"20","author":"A Micheli","year":"2009","unstructured":"Micheli A (2009) Neural network for graphs: a contextual constructive approach. IEEE Trans Neural Netw 20:498\u2013511","journal-title":"IEEE Trans Neural Netw"},{"key":"9676_CR37","doi-asserted-by":"crossref","unstructured":"Morris C et\u00a0al (2019) Weisfeiler and Lehman go neural: higher-order graph neural networks. In: Proceedings of the AAAI conference on artificial intelligence, vol\u00a033, pp 4602\u20134609","DOI":"10.1609\/aaai.v33i01.33014602"},{"key":"9676_CR38","doi-asserted-by":"crossref","unstructured":"Naor M, Stockmeyer L (1993) What can be computed locally?. In: Proceedings of the 25th annual ACM symposium on theory of computing. Association for Computing Machinery, New York, pp 184\u2013193","DOI":"10.1145\/167088.167149"},{"key":"9676_CR39","unstructured":"Puny O, Ben-Hamu H, Lipman Y (2020) From graph low-rank global attention to 2-FWL approximation. CoRR https:\/\/arxiv.org\/abs\/2006.07846"},{"key":"9676_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/sdata.2014.22","volume":"1","author":"R Ramakrishnan","year":"2014","unstructured":"Ramakrishnan R, Dral PO, Rupp M, Von Lilienfeld OA (2014) Quantum chemistry structures and properties of 134 kilo molecules. Sci Data 1:1\u20137","journal-title":"Sci Data"},{"key":"9676_CR41","doi-asserted-by":"crossref","unstructured":"Rossi A et al (2018) Inductive\u2013transductive learning with graph neural networks. In: Proceedings of IAPR workshop on artificial neural networks in pattern recognition. Springer, New York, pp 201\u2013212","DOI":"10.1007\/978-3-319-99978-4_16"},{"key":"9676_CR42","doi-asserted-by":"publisher","first-page":"2864","DOI":"10.1021\/ci300415d","volume":"52","author":"L Ruddigkeit","year":"2012","unstructured":"Ruddigkeit L, Van Deursen R, Blum LC, Reymond J-L (2012) Enumeration of 166 billion organic small molecules in the chemical universe database GDB-17. J Chem Inf Model 52:2864\u20132875","journal-title":"J Chem Inf Model"},{"key":"9676_CR43","unstructured":"Sato R (2020) A survey on the expressive power of graph neural networks. arXiv preprint arXiv:2003.04078"},{"key":"9676_CR44","doi-asserted-by":"crossref","unstructured":"Sato R, Yamada M, Kashima H (2021) Random features strengthen graph neural networks. In: Proceedings of SDM21","DOI":"10.1137\/1.9781611976700.38"},{"key":"9676_CR45","doi-asserted-by":"crossref","unstructured":"Scarselli F et al (2009a) Computational capabilities of graph neural networks. IEEE Trans Neural Netw 20:81\u2013102","DOI":"10.1109\/TNN.2008.2005141"},{"key":"9676_CR46","doi-asserted-by":"crossref","unstructured":"Scarselli F et al (2009b) The graph neural network model. IEEE Trans Neural Netw 20:61\u201380","DOI":"10.1109\/TNN.2008.2005605"},{"key":"9676_CR47","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/S0893-6080(97)00097-X","volume":"11","author":"F Scarselli","year":"1998","unstructured":"Scarselli F, Chung Tsoi A (1998) Universal approximation using feedforward neural networks: a survey of some existing methods, and some new results. Neural Netw 11:15\u201337","journal-title":"Neural Netw"},{"key":"9676_CR48","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1016\/j.neunet.2018.08.010","volume":"108","author":"F Scarselli","year":"2018","unstructured":"Scarselli F, Tsoi AC, Hagenbuchner M (2018) The Vapnik\u2013Chervonenkis dimension of graph and recursive neural networks. Neural Netw 108:248\u2013259","journal-title":"Neural Netw"},{"key":"9676_CR49","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1109\/72.572108","volume":"8","author":"A Sperduti","year":"1997","unstructured":"Sperduti A, Starita A (1997) Supervised neural networks for the classification of structures. IEEE Trans Neural Netw 8:714\u2013735","journal-title":"IEEE Trans Neural Netw"},{"key":"9676_CR50","unstructured":"Veli\u010dkovi\u0107 P et\u00a0al (2018) Graph attention networks. In: Proceedings of ICLR 2018"},{"key":"9676_CR51","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1109\/TNNLS.2020.2978386","volume":"32","author":"Z Wu","year":"2020","unstructured":"Wu Z et al (2020) A comprehensive survey on graph neural networks. IEEE Trans Neural Netw Learn Syst 32:4\u201324","journal-title":"IEEE Trans Neural Netw Learn Syst"},{"key":"9676_CR52","unstructured":"Xu K, Hu W, Leskovec J, Jegelka S (2018) How powerful are graph neural networks?. In: Proceedings of the ICLR 2018"},{"key":"9676_CR53","doi-asserted-by":"crossref","unstructured":"You J, Gomes-Selman J, Ying R, Leskovec J (2021) Identity-aware graph neural networks. In: Proceedings of the conference on artificial intelligence (AAAI 21)","DOI":"10.1609\/aaai.v35i12.17283"},{"key":"9676_CR54","doi-asserted-by":"crossref","unstructured":"Zhang M, Li P (2021) Nested graph neural networks. Adv Neural Inf Process Syst 34:15734\u201315747","DOI":"10.1016\/j.neunet.2021.04.026"},{"key":"9676_CR55","doi-asserted-by":"crossref","unstructured":"Zhou X, Wang H (2021) The generalization error of graph convolutional networks may enlarge with more layers. Neurocomputing 424:97\u2013106. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0925231220317367","DOI":"10.1016\/j.neucom.2020.10.109"}],"container-title":["Soft Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-024-09676-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00500-024-09676-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-024-09676-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,27]],"date-time":"2024-11-27T11:11:38Z","timestamp":1732705898000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00500-024-09676-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7]]},"references-count":55,"journal-issue":{"issue":"13-14","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["9676"],"URL":"https:\/\/doi.org\/10.1007\/s00500-024-09676-1","relation":{},"ISSN":["1432-7643","1433-7479"],"issn-type":[{"value":"1432-7643","type":"print"},{"value":"1433-7479","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7]]},"assertion":[{"value":"15 January 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 July 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"Code has been made available in the GitHub repo .","order":6,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}]}}