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
On the approximate realization of continuous mappings by neural networks
Funahashi, K.-I. (1989) · Neural Networks · doi:10.1016/0893-6080(89)90003-8 · Cited by 4,206
Nazuno, J. F. (2000) · Computación y Sistemas · Cited by 3,185
Neural networks — A comprehensive foundation
Wilusz, T. (1995) · Neurocomputing · doi:10.1016/0925-2312(95)90026-8 · Cited by 2,881
Hornik, K., Stinchcombe, M. B., & White, H. (1990) · Neural Networks · doi:10.1016/0893-6080(90)90005-6 · Cited by 2,136
A new model for learning in graph domains
Gori, M., Monfardini, G., & Scarselli, F. (2006) · Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005. · doi:10.1109/ijcnn.2005.1555942 · Cited by 2,075
Self-citationNeural networks and principal component analysis: Learning from examples without local minima
Baldi, P., & Hornik, K. (1989) · Neural Networks · doi:10.1016/0893-6080(89)90014-2 · Cited by 1,383
Generalization of back-propagation to recurrent neural networks
Pineda, F. J. (1987) · Physical Review Letters · doi:10.1103/physrevlett.59.2229 · Cited by 931
Supervised neural networks for the classification of structures
Sperduti, A., & Starita, A. (1997) · IEEE Transactions on Neural Networks · doi:10.1109/72.572108 · Cited by 666
On the problem of local minima in backpropagation
Gori, M., & Tesi, A. (1992) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.107014 · Cited by 658
Self-citationAn Introduction to Metric Spaces and Fixed Point Theory
Khamsi, M. A., & Kirk, W. A. (2001) · Wiley eBooks · doi:10.1002/9781118033074 · Cited by 620
Scarselli, F., & Tsoi, A. C. (1998) · Neural Networks · doi:10.1016/s0893-6080(97)00097-x · Cited by 571
Self-citationA general framework for adaptive processing of data structures
Frasconi, P., Gori, M., & Sperduti, A. (1998) · IEEE Transactions on Neural Networks · doi:10.1109/72.712151 · Cited by 481
Self-citationA learning rule for asynchronous perceptrons with feedback in a combinatorial environment
Almeida, L. B. (1990) · IEEE Press eBooks · Cited by 280
The problem of learning long-term dependencies in recurrent networks
Bengio, Y., Frasconi, P., & Simard, P. (2002) · IEEE International Conference on Neural Networks/IEEE ... International Conference on Neural Networks · doi:10.1109/icnn.1993.298725 · Cited by 246
Sequencing-by-hybridization revisited: the analog-spectrum proposal
Preparata, F. (2004) · IEEE/ACM Transactions on Computational Biology & Bioinformatics · doi:10.1109/tcbb.2004.12 · Cited by 181
A self-organizing map for adaptive processing of structured data
Hagenbuchner, M., Sperduti, A., & Tsoi, A. C. (2003) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2003.810735 · Cited by 180
Self-citationGraph Neural Networks for Ranking Web Pages
Scarselli, F., Yong, S. L., Gori, M., Hagenbuchner, M., Tsoi, A. C., & Maggini, M. (2005) · IEEE/WIC/ACM International Conference on Web Intelligence · doi:10.1109/wi.2005.67 · Cited by 124
Self-citationOn the problem of local minima in recurrent neural networks
Bianchini, M., Gori, M., & Maggini, M. (1994) · IEEE Transactions on Neural Networks · doi:10.1109/72.279182 · Cited by 57
Self-citationVapnik-Chervonenkis dimension of neural nets
Bartlett, P. L., & Maass, W. (2003) · Cited by 54
Recursive neural networks for processing graphs with labelled edges: theory and applications
Bianchini, M., Maggini, M., Sarti, L., & Scarselli, F. (2005) · Neural Networks · doi:10.1016/j.neunet.2005.07.003 · Cited by 45
Self-citationGraphical-Based Learning Environments for Pattern Recognition
Scarselli, F., Tsoi, A. C., Gori, M., & Hagenbuchner, M. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-27868-9_4 · Cited by 44
Self-citationA Comparison between Recursive Neural Networks and Graph Neural Networks
Massa, V. D., Monfardini, G., Sarti, L., Scarselli, F., Maggini, M., & Gori, M. (2006) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn.2006.246763 · Cited by 41
Self-citationBird, J., & Bird, J. (2005) · Routledge eBooks · doi:10.4324/9780080476018-38 · Cited by 33
Recursive Processing of Cyclic Graphs
Bianchini, M., Gori, M., Sarti, L., & Scarselli, F. (2006) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2005.860873 · Cited by 28
Self-citationDocument Mining Using Graph Neural Network
Yong, S. L., Hagenbuchner, M., Tsoi, A. C., Scarselli, F., & Gori, M. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-73888-6_43 · Cited by 26
Self-citationGeneralization ability of folding networks
Hammer, B. (2001) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.917560 · Cited by 26
Priestley, H. A. (1997) · doi:10.1093/oso/9780198501244.001.0001 · Cited by 20
Approximation capabilities of folding networks
Hammer, B. (1999) · Cited by 17
Graph Neural Networks for Object Localization
Monfardini, G., Massa, V. D., Scarselli, F., & Gori, M. (2006) · Use Siena air (University of Siena) · Cited by 14
Self-citationTwo connectionist models for graph processing: An experimental comparison on relational data
Uwents, W., Monfardini, G., Blockeel, H., Scarselli, F., & Gori, M. (2006) · Lirias · Cited by 12
Self-citationIto, Y. (1994) · Journal of Computational and Applied Mathematics · doi:10.1016/0377-0427(94)90183-x · Cited by 9
On the closure of the set of functions that can be realized by a given multilayer perceptron
Gori, M., Scarselli, F., & Tsoi, A. C. (1998) · IEEE Transactions on Neural Networks · doi:10.1109/72.728354 · Cited by 5
Self-citation
Cited by
Sorted by citations
A Comprehensive Survey on Graph Neural Networks
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. S. (2021) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2020.2978386 · Cited by 11,000
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-citationFormal Semantics for Kolmogorov-Arnold Network Representations of Operational GamesPreprint
Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.00826 · Cited by 5,932
A Comprehensive Survey on Graph Neural Networks
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. (2020) · UTS ePRESS (University of Technology Sydney) · Cited by 3,174
Multiscale Dynamic Graph Convolutional Network for Hyperspectral Image Classification
Wan, S., Gong, C., Zhong, P., Du, B., Zhang, L., & Yang, J. J. (2019) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2019.2949180 · Cited by 575
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
