The DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
Computational Capabilities of Graph Neural Networks
Abstract
In this paper, we will consider the approximation properties of a recently introduced neural network model called graph neural network (GNN), which can be used to process-structured data inputs, e.g., acyclic graphs, cyclic graphs, and directed or undirected graphs. This class of neural networks implements a function tau(G,n) is an element of IR(m) that maps a graph G and one of its nodes n onto an m-dimensional Euclidean space. We characterize the functions that can be approximated by GNNs, in probability, up to any prescribed degree of precision. This set contains the maps that satisfy a property called preservation of the unfolding equivalence, and includes most of the practically useful functions on graphs; the only known exception is when the input graph contains particular patterns of symmetries when unfolding equivalence may not be preserved. The result can be considered an extension of the universal approximation property established for the classic feedforward neural networks (FNNs). Some experimental examples are used to show the computational capabilities of the proposed model.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Neural Networks: A Comprehensive Foundation
Haykin, S. (1998) · Cited by 30,070
Wu, Y., & Vapnik, V. N. (1999) · Technometrics · doi:10.2307/1271368 · Cited by 27,236
Multilayer feedforward networks are universal approximators
Hornik, K., Stinchcombe, M., & White, H. (1989) · Neural Networks · doi:10.1016/0893-6080(89)90020-8 · Cited by 21,728
Approximation by superpositions of a sigmoidal function
Cybenko, G. (1989) · Mathematics of Control, Signals, and Systems · doi:10.1007/bf02551274 · Cited by 13,883
The graph neural network model
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., & Monfardini, G. (2009) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2008.2005605 · Cited by 9,582
Self-citationMultilayer feedforward networks are universal approximators
HornikK., StinchcombeM., & WhiteH. (1989) · Neural Networks · doi:10.5555/70405.70408 · Cited by 9,266
Approximation capabilities of multilayer feedforward networks
Hornik, K. (1991) · Neural Networks · doi:10.1016/0893-6080(91)90009-t · Cited by 6,091
Modeling by shortest data description
Rissanen, J. (1978) · Automatica · doi:10.1016/0005-1098(78)90005-5 · Cited by 6,011
Powell, M. J. D. (1964) · The Computer Journal · doi:10.1093/comjnl/7.2.155 · Cited by 4,632 · cited 1×
“Hence, one can refer to a learning set as the pair where is a graph and is a set of pairs .”
BackgroundComputational Geometry--An Introduction.
Atallah, M. J., Preparata, F. P., & Shamos, M. I. (1986) · Mathematics of Computation · doi:10.2307/2008200 · Cited by 4,287
Flagged first, then by citations
Cited by
Sorted by citations
Items 201–224 of 224
Brain Connectivity: Exploring from a High-Level Topological Perspective
Sheng, W., Li, L., Han, S., Fan, Y., Wang, C., Tang, Q., Chen, Y., Cui, Q., & Chen, H. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-87358-5_2
He, S., Tang, H., Xia, L., Yan, H., & Wang, N. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.03346
Complex Data: Learning Trustworthily, Automatically, and with Guarantees
Oneto, L., Navarin, N., Biggio, B., Errica, F., Micheli, A., Scarselli, F., Bianchini, M., & Sperduti, A. (2021) · European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN) · doi:10.14428/esann/2021.es2021-6
Self-citationDiscovering Latent Representations of Relations for Interacting Systems
Lee, D., Oh, Y. J., & Lee, I. (2021) · IEEE Access · doi:10.1109/access.2021.3125335
Adaptive control and signal processing literature survey (No. 11)
(2009) · International Journal of Adaptive Control and Signal Processing · doi:10.1002/acs.1126
Graph Machine Learning for Design of High-Octane FuelsPreprint
Rittig, J. G., Ritzert, M., Schweidtmann, A. M., Winkler, S., Weber, J. M., Morsch, P., Heufer, K. A., Grohe, M., Mitsos, A., & Dahmen, M. (2022) · RWTH Publications (RWTH Aachen) · doi:10.18154/rwth-2024-02829
Starke, L., Hoppe, A. F., Sartori, A., Stefenon, S. F., & Leithardt, V. R. Q. (2022) · Research Square · doi:10.21203/rs.3.rs-2317227/v1
Starke, L., Hoppe, A. F., Sartori, A., Stefenon, S. F., & Leithardt, V. R. Q. (2023) · Research Square · doi:10.21203/rs.3.rs-2317227/v2
Zhang, Z., Zhu, G., & Qin, W. (2024) · IEEE Access · doi:10.1109/access.2024.3396209
Tabular affiliation extraction based on graph convolutional network
Yutong, Z., Li, Q., & Liu, S. (2024) · Journal of applied artificial intelligence. · doi:10.59782/aai.v1i1.265
SCL-DTI: Semi-Supervised Contrastive Learning for Drug-Target Interactions Prediction
Dong, J. (2024) · International Conference on Electronics and Devices, Computational Science (ICEDCS) · doi:10.1109/icedcs64328.2024.00094
Lin, W. (2025) · International Journal of Intelligent Information Technologies · doi:10.4018/ijiit.383644
Graph Neural Network Analysis Techniques for Power Flow Analysis
Tanolli, N. A. K., Raza, A., & Gulraiz, A. (2025) · International Conference on Emerging Technologies in Electronics, Computing and Communication (ICETECC) · doi:10.1109/icetecc65365.2025.11070259
Traffic prediction based on spatio-temporal feature embedding fusion and gate operation optimization
Geng, X., Zhang, F., Zhang, M., & Wang, H. (2025) · Neurocomputing · doi:10.1016/j.neucom.2025.131658
Park, J., Kim, H. Y., Kim, H., Shin, S., & Ryu, G.-A. (2026) · IEEE Access · doi:10.1109/access.2026.3664879
Kruse, M., Böhnke, D., & Neustock, J. (2026) · Procedia CIRP · doi:10.1016/j.procir.2025.09.047
Chen, Z., Xiong, Y., Fan, Y., & Zuo, R. (2026) · Applied Geochemistry · doi:10.1016/j.apgeochem.2026.106824
A method for the systematic generation of graph XAI benchmarks via Weisfeiler–Leman coloring
Fontanesi, M., Micheli, A., Podda, M., & Tortorella, D. (2026) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-026-01212-z · Cited by 2
NetMOS: Topology-Aware VoIP MOS Prediction via Attention-Recurrent GNNs
Ranaweera, S., He, Y., Jayawickrama, B. A., Wang, X., Liu, R. P., & Ni, W. (2026) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2026.3701762
Cross-Platform Performance Analysis of GNN-Based SAR-ATR on FPGAs
Rappa, F. M., & Goldman, A. (2026) · Escola Regional de Alto Desempenho de São Paulo (ERAD-SP) · doi:10.5753/eradsp.2026.30921
Graph networks as learnable physics engines for inference and control
Sanchez-Gonzalez, A., Heess, N., Springenberg, J. T., Merel, J., Riedmiller, M., Hadsell, R., & Battaglia, P. (2018) · arXiv · doi:10.48550/arxiv.1806.01242 · Cited by 387
Metadata
- Authors
- Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., & Monfardini, G.
- Affiliations
- University of Siena (IT)
- Hong Kong Baptist University (HK)
- University of Wollongong (AU)
- Venue
- IEEE Transactions on Neural Networks
- Published
- 2009-01
- Volume
- 20
- Issue
- 1
- Pages
- 81-102
- ISSN
- 1045-9227 (ISSN-L)
- 1941-0093
- OpenAlex
- W2150120952
- Cited by
- 225
- References
- 42
- Citations by year
- 2026: 8 · 2025: 16 · 2024: 25 · 2023: 20 · 2022: 32 · 2021: 34 · 2020: 25 · 2019: 17 · 2018: 8 · 2017: 2 · 2016: 1 · 2015: 3 · 2014: 7 · 2013: 8 · 2012: 4
- FWCI
- 7.93
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Neural Networks (publishedVersion)
- PubMed (publishedVersion)
- HKBU Institutional Repository (Hong Kong Baptist University) (submittedVersion)
- Research Online (University of Wollongong) (submittedVersion)
- Figshare (submittedVersion)
- Use Siena air (University of Siena) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Advanced Graph Neural Networks
- Physical Sciences › Computer Science › Artificial Intelligence › Neural Networks and Applications
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Graph Theory and Algorithms
- Keywords
- graph neural networks, universal approximation, approximation properties, graph symmetry, structured data, acyclic graphs, cyclic graphs, directed and undirected graphs
- MeSH terms
- Algorithms, Pattern Recognition, Automated, Neural Networks, Computer
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
