Graph neural network

A graph neural network (GNN) is an artificial neural network whose computation incorporates the structure of a graph. In contrast with neural architectures defined on regular arrays, a GNN operates on entities connected by relations that need not form a fixed grid. Nodes usually represent the entities under analysis, while edges encode interactions, associations, or other pairwise relations. Features may be attached to either type of graph element, and some models additionally represent global properties of the graph.

Most contemporary GNNs repeatedly combine the representation of each node with information obtained from its neighbors. This mechanism is known as message passing. It provides a common mathematical description for architectures developed from spectral graph theory, recursive neural networks, and learned aggregation procedures.

Mathematical formulation

Let a graph be denoted by (G=(V,E)), where (V) is a set of nodes and (E) is a set of edges. Each node (v\in V) has an initial feature vector (x_v), and an edge from (u) to (v) may have an associated feature vector (e_{uv}). A message-passing network assigns each node a hidden state (h_v^{(k)}) at layer (k), with (h_v^{(0)}=x_v).

A general message-passing layer has the form

[ m_v^{(k)}

\operatorname{AGG}^{(k)} \left( \left{ \phi^{(k)} \left( h_v^{(k-1)},h_u^{(k-1)},e_{uv} \right) : u\in\mathcal{N}(v) \right} \right), ]

[ h_v^{(k)}

\psi^{(k)} \left( h_v^{(k-1)},m_v^{(k)} \right), ]

where (\mathcal{N}(v)) is the neighborhood of (v). The function (\phi^{(k)}) constructs messages, (\operatorname{AGG}^{(k)}) combines messages arriving from the neighborhood, and (\psi^{(k)}) updates the node state. Their parameters are commonly shared across nodes, allowing the same layer to operate on graphs with different numbers of vertices.

The aggregation function is invariant to permutations of the incoming messages. Consequently, relabeling the nodes produces the corresponding relabeling of node representations rather than changing the represented graph computation. This property is called permutation equivariance. For graph-level prediction, a readout function combines the final node states:

[ h_G

\operatorname{READOUT} \left( \left{ h_v^{(K)}:v\in V \right} \right). ]

A graph-level readout is permutation invariant because its output remains unchanged when node identifiers are reordered. Summation and learned set functions are common realizations of this requirement, although they differ in the distinctions they preserve between multisets of node states.

Historical development

Early neural models for relational data used recurrent computation to propagate states until reaching a fixed point. Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini presented a unified graph neural network formulation in the 2000s. Their framework assigned states to nodes and constrained the transition process so that repeated propagation converged to a stable representation.

A second line of development originated in spectral graph theory. Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun defined graph convolutions through filters acting on the eigenvectors of a graph Laplacian. Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst subsequently represented spectral filters with polynomial approximations, which localized computation and avoided an unrestricted eigendecomposition during each forward pass.

The graph convolutional network introduced by Thomas Kipf and Max Welling simplified this spectral construction to a first-order propagation rule. Its normalized adjacency operator combines each node with its neighbors while controlling changes caused by differences in node degree. The resulting model became a standard formulation for semi-supervised node classification.

In 2017, William L. Hamilton, Rex Ying, Jure Leskovec, and You Watanabe formulated GraphSAGE as an inductive family of neighborhood-aggregation networks. Rather than associating an independent trainable embedding with every node, GraphSAGE learned functions that generated embeddings from node attributes and sampled neighborhoods. The same learned functions could therefore be evaluated on nodes that were absent from the graph used during training.

Also in 2017, Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl introduced the message-passing neural network terminology in the context of molecular prediction. Their formulation treated several existing graph architectures as instances of a shared process consisting of learned messages, state updates, and a graph-level readout.

Principal computational forms

The graph convolutional network uses an adjacency matrix (A) augmented with self-connections. If (\widetilde{A}=A+I) and (\widetilde{D}) is its diagonal degree matrix, one layer is commonly written as

[ H^{(k+1)}

\sigma \left( \widetilde{D}^{-1/2} \widetilde{A} \widetilde{D}^{-1/2} H^{(k)}W^{(k)} \right). ]

Here, (H^{(k)}) contains node representations, (W^{(k)}) is a learned parameter matrix, and (\sigma) is a nonlinear activation function. The symmetric normalization reduces the dependence of representation magnitude on node degree.

A graph attention network replaces fixed normalized coefficients with coefficients computed from pairs of node representations. Attention remains restricted to graph neighborhoods, but different neighbors can make different learned contributions to the updated state. The softmax normalization used within each neighborhood makes these contributions relative to the other adjacent nodes.

GraphSAGE instead characterizes a layer through an explicit neighborhood aggregator and a transformation that combines the aggregated vector with the central node representation. Sampling limits the number of neighbors processed at each layer, making the computational graph less dependent on the maximum degree of the original graph. Sampling also introduces stochastic variation because only part of a large neighborhood may participate in a particular evaluation.

Models for heterogeneous or relational graphs assign different transformations to different edge types. This construction is used when the meaning of an edge is not exhausted by its endpoints, as in a knowledge graph containing several semantic relations. Temporal graph networks additionally associate events or edges with times, so the hidden state depends on both connectivity and event order.

Learning and prediction levels

Node-level learning associates an output with each vertex. A citation graph, for example, can represent documents as nodes and citations as directed edges, while the target variable denotes a document category. Information propagation permits labeled and unlabeled nodes to participate in the same computation, which connects many GNN formulations with semi-supervised learning.

Edge-level learning assigns a score or label to a pair of nodes. In link prediction, the score estimates whether an unobserved relation is compatible with the representations produced by the network. A decoder may compare endpoint embeddings directly or process them through an additional learned function.

Graph-level learning produces a single representation for an entire graph. Molecular property prediction commonly uses atoms as nodes and chemical bonds as edges, after which a permutation-invariant readout maps the node representations to a molecular representation. This setting distinguishes message passing within a molecule from pooling across the molecule.

Training generally minimizes an empirical loss by backpropagation. Supervised objectives compare predictions with observed targets, whereas self-supervised objectives derive training signals from the graph or its attributes. Mini-batch computation can involve sampled neighborhoods, induced subgraphs, or complete graphs, depending on the prediction level and the size of the data.

Expressive capacity

The expressive capacity of a message-passing GNN is constrained by the information available in local neighborhoods and by the invariances imposed by aggregation. Standard message-passing architectures have a close relationship to the one-dimensional Weisfeiler–Leman algorithm, which iteratively refines node colors according to neighboring color multisets. If that refinement cannot distinguish two graphs, a broad class of message-passing networks also assigns them indistinguishable graph representations when their initial features agree.

Injective aggregation and update functions preserve more distinctions between neighborhood multisets than non-injective alternatives. The graph isomorphism network was constructed around this observation and matches the distinguishing power of one-dimensional Weisfeiler–Leman refinement under its stated assumptions. Higher-order GNNs extend the computational units from individual nodes to tuples or substructures, thereby changing both expressive capacity and computational cost.

The number of message-passing layers determines the maximum topological distance over which information can directly propagate. After (K) layers, a node representation ordinarily depends on its (K)-hop neighborhood. Long-range dependence therefore requires greater depth, modified connectivity, hierarchical pooling, or an additional global communication mechanism.

Structural limitations

Repeated neighborhood averaging can cause oversmoothing as node representations become increasingly similar. The effect depends on the propagation operator, network depth, feature transformations, and graph topology. Residual connections and normalization alter the associated dynamics, but they do not remove the underlying tendency of repeated diffusion to reduce certain differences between nodes.

Oversquashing occurs when information from a rapidly expanding neighborhood must be compressed into a fixed-dimensional representation. Its severity is connected to graph bottlenecks and to the number of distant signals routed through a small set of edges. Graph rewiring and nonlocal communication change these routes by modifying the effective geometry used during propagation.

Many elementary GNN layers encode a form of homophilic bias because adjacent nodes repeatedly exchange and average representations. On a heterophilic graph, neighboring nodes frequently have different labels or attributes, so unmodified local smoothing can mix information that is not aligned with the prediction target. Architectures designed for this setting separate different neighborhood ranges or retain stronger distinctions between central and neighboring representations.

Graph size also affects computation because the receptive field can grow multiplicatively with depth. Full-batch propagation stores intermediate states for much of the graph, while neighborhood sampling reduces that requirement at the cost of sampling variance. Distributed execution introduces further dependence on how graph partitions divide edges, since messages crossing partition boundaries require communication between computational units.

Relation to graph signal processing

A node-feature matrix can be interpreted as a collection of signals defined over graph vertices. Under this interpretation, multiplication by a normalized adjacency matrix performs a local diffusion, while a graph Laplacian describes variation between connected vertices. Spectral GNNs construct filters as functions of the Laplacian, whereas spatial GNNs specify the same general class of local interactions directly through neighborhoods.

The distinction between spectral and spatial formulations is not absolute. Polynomial spectral filters are localized in the vertex domain, and many spatial propagation rules correspond to particular functions of a graph operator. Their practical differences arise from parameterization, assumptions about graph transferability, and the manner in which edge information enters the computation.