Computational Capabilities of Graph Neural Networks

By Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, Gabriele Monfardini. 2009

234 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Graph Learning, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Graph Learning

In Statistical Learning Theory

Citations in the corpus

Relational inductive biases, deep learning, and graph networks (2018, background): “…and structure their computations accordingly, have been developed and explored extensively for more than a decade under the umbrella of “graph neural networks” (Gori et al., 2005; Scarselli et al., 2005, 2009a; Li et al., 2016), but have grown rapidly in scope and popularity in recent years.”
How Powerful are Graph Neural Networks? (2018, background): “Not surprisingly, building blocks of GIN, e.g. sum aggregation and MLP encoding, also appeared in other models (Battaglia et al., 2016; Scarselli et al., 2009b; Duvenaud et al., 2015).”
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks (2018, background): “…GraphSAGE (Hamilton, Ying, and Leskovec 2017a), SplineCNN (Fey et al. 2018), and the spectral approaches proposed in (Bruna et al. 2014; Defferrard, X., and Vandergheynst 2016; Kipf and Welling 2017)—all of which descend from early work in (Merkwirth and Lengauer 2005) and (Scarselli et al. 2009b).”
Graph networks as learnable physics engines for inference and control (2018, methodology): “Our approach uses “graph networks” (GNs), a class of neural networks that can learn functions on graphs (Scarselli et al., 2009b; Li et al., 2015; Battaglia et al., 2016; Gilmer et al., 2017).”
A Comprehensive Survey on Graph Neural Networks (2019, background): “Scarselli et al. [107] prove that a RecGNN [15] can approximate any function that preserves unfolding equivalence up to any degree of precision.”
Graph Neural Networks: A Review of Methods and Applications (2018, background): “And [19] demonstrates the approximation properties and computational capabilities of graph neural networks.”
On the complexity of shallow and deep neural network classifiers (2014, background): “…functions), expanding the class of ap-proximable maps (e.g., to integrable functions), considering non–static networks (e.g., recurrent [10], recursive [11] and graph neural networks [12]), and providing upper bounds on the rate of approximation w.r.t. the number of neurons (e.g., see [13]).”
On the Complexity of Neural Network Classifiers: A Comparison Between Shallow and Deep Architectures (2014, unknown): “…extended in several ways, considering networks with very generic neurons (e.g., with analytic activation functions), expanding the class of approximable maps (e.g., to integrable functions [36]), or studying nonstatic networks (e.g., recurrent, recursive, and graph neural networks [37]–[39]).”
Multiscale Dynamic Graph Convolutional Network for Hyperspectral Image Classification (2019, methodology): “[57] made GNN trainable by a supervised learning algorithm for practical data.”
Generalization and Representational Limits of Graph Neural Networks (2020, methodology): “Graph neural networks (Scarselli et al., 2009; Gori et al., 2005), in their various incarnations, have emerged as models of choice for embedding graph-structured data from a diverse set of domains, including molecular structures, knowledge graphs, biological networks, social networks, and n-body pro”
Reinforcement Learning for Solving the Vehicle Routing Problem (2018, background): “The first is a set of graph embeddings [30] that can be used to encode structured data inputs.”
Neural networks for relational learning: an experimental comparison (2011, methodology): “More details can be found in [Gori et al., 2005, Scarselli et al., 2009b].”