Graph neural network

What it is

A graph neural network is an artificial neural network designed for graph-structured inputs, that is, data that arrives as a set of nodes plus the edges connecting them^[1]. A 2018 review describes graph neural networks as neural models that capture the dependence of a graph via message passing between its nodes^[2]. The term therefore names a family of architectures rather than one fixed model.

How it works

The nodes of a graph have no natural order: relabelling them does not change the graph. Graph architectures are therefore usually permutation equivariant, so that reordering the input reorders the output in the same way, and graph-level tasks use permutation-invariant readout functions that give the same answer whatever the ordering^[1].

Most modern graph networks use message passing. Each node's representation is updated from its own features together with an aggregate of messages from its neighbours^[1]. The aggregation operator is permutation invariant, typically a sum, a mean or a maximum^[1]. Because each layer pulls in one more ring of neighbours, every layer extends the receptive field of a node by one hop^[1].

A small example makes this concrete. Take a graph in which each node is a person and each edge a friendship. In the first layer a node's vector is updated from its own attributes plus, say, the mean of its friends' vectors. In the second layer the same operation runs on those results, so the node now indirectly sees friends of friends. Stack enough layers and a node's representation can depend on a large part of the graph; the readout function then turns the whole set of node vectors into a single vector for the graph.

Where it came from

Scarselli and colleagues published "The Graph Neural Network Model" in 2009, formulating the model recursively^[1]. In the same year Micheli proposed a convolutional construction for graphs^[1]. The ideas were taken up widely later: GCN, by Kipf and Welling in 2017, is a first-order approximation of a local spectral filter^[1]; GraphSAGE, by Hamilton and colleagues in 2017, introduced inductive representation learning for large graphs^[1]; and GAT, by Velickovic and colleagues in 2018, added attention coefficients to weight the importance of neighbours^[1].

Why it matters

The 2018 review notes that variants such as the graph convolutional network, graph attention network and graph recurrent network demonstrated breakthrough performance on many deep learning tasks^[2]. It proposes a general design pipeline for GNN models, systematically categorizes their applications, and poses four open problems for future research^[2]. Surveying the applications in one place matters for a field with many architectures: it shows which kinds of tasks the same underlying machinery is being asked to serve.

Limits

Standard message-passing graph networks have a ceiling on what they can tell apart: their expressive power is no greater than the Weisfeiler-Leman graph isomorphism test^[1]. Depth brings its own problems. Oversmoothing makes node representations converge and become indistinguishable in deep graph networks^[1], and oversquashing compresses long-range dependencies into a fixed-size representation, creating a bottleneck^[1].