Graph neural network

Also known as: GNN

On this page 7

A graph neural network (GNN) is a class of neural networks that operates directly on graph-structured data, learning a vector representation for each node, edge or whole graph by repeatedly exchanging information between connected nodes. Where a convolutional network assumes a regular grid of pixels and a recurrent network assumes a sequence, a GNN assumes only that entities are linked by relationships of arbitrary shape.

GNNs are used wherever the connections carry as much meaning as the entities themselves: molecules as atoms and bonds, social platforms as users and follows, road networks, citation graphs, knowledge graphs and fraud rings. Their defining property is permutation invariance: the output does not depend on the arbitrary order in which nodes are listed.

How message passing works in a graph neural network

Most graph neural networks follow the message passing framework, in which each layer updates every node by combining its own state with information from its neighbors. A single layer has three steps: each neighbor produces a message, the messages are combined by an aggregation function, and an update function merges the result with the node’s previous representation.

The aggregation must be order independent, so typical choices are sum, mean or maximum, or an attention-weighted sum. Stacking k layers lets information travel k hops, so after three layers a node’s representation reflects its three-hop neighborhood. For graph-level tasks such as predicting a molecular property, a readout function pools all node vectors into one graph vector.

The table below lists the main components of a message passing layer and the role each one plays.

ComponentRoleCommon choices
Message functionTransforms neighbor features into messagesLinear layer, small multilayer perceptron
Aggregation functionCombines messages without regard to orderSum, mean, max, attention
Update functionMerges aggregate with the node stateMultilayer perceptron, gated recurrent unit
Readout functionPools node vectors into a graph vectorSum or mean pooling, hierarchical pooling
Edge featuresEncode bond type, distance or relationEmbeddings added to messages
Components of a message passing layer

Main GNN architectures

GNN architectures differ mainly in how they weight and aggregate neighbors. The choice affects expressive power, scalability and how well the model handles nodes with very different numbers of connections.

ArchitectureAggregation ideaTypical strength
Graph convolutional network (GCN)Degree-normalized mean of neighborsSimple, fast semi-supervised node classification
GraphSAGESampled neighbors with learnable aggregatorLarge graphs and unseen nodes
Graph attention network (GAT)Learned attention weights per neighborNeighbors of unequal importance
Graph isomorphism network (GIN)Sum aggregation with a multilayer perceptronHigh expressive power for graph classification
Relational GCNSeparate weights per edge typeKnowledge graphs with typed relations
Graph transformerAttention over all nodes plus structural encodingsLong-range dependencies
Widely used GNN variants

The Weisfeiler-Lehman test sets a known ceiling on standard message passing: such networks cannot distinguish graphs that this classical isomorphism heuristic also fails to separate. GIN reaches that ceiling, and higher-order or subgraph-based models are needed to go beyond it.

Tasks a GNN can solve

A graph neural network can make predictions at three levels of a graph: individual nodes, pairs of nodes or edges, and entire graphs. The same message passing backbone serves all three, and only the output head and the training objective change.

Task levelQuestion answeredExample application
Node classificationWhat category does this node belong toFlagging fraudulent accounts
Link predictionShould an edge exist between two nodesProduct and friend recommendations
Graph classificationWhat property does the whole graph havePredicting molecular toxicity
Graph regressionWhat continuous value does the graph haveEstimating binding energy
Graph generationWhich new graph satisfies a goalProposing candidate molecules
Prediction levels and representative applications

Training can be transductive, where the whole graph including test nodes is visible during training, or inductive, where the model must generalize to new nodes or new graphs. Inductive settings are closer to production use and require architectures such as GraphSAGE that do not memorize node identities.

How GNNs compare with other neural network types

A GNN generalizes several familiar architectures by removing the assumption of fixed structure. An image can be viewed as a grid graph and a sentence as a chain graph, and a transformer’s self-attention behaves like message passing on a fully connected graph.

ArchitectureAssumed input structureNeighborhood definition
Convolutional neural networkRegular gridFixed spatial window
Recurrent neural networkOrdered sequencePrevious time step
TransformerSet of tokens with positionsAll tokens through attention
Graph neural networkArbitrary graphNodes linked by edges
Structural assumptions of common architectures

The practical difference is that a GNN uses explicit relational structure as an inductive bias. When the graph is meaningful, this bias improves sample efficiency; when the graph is noisy or arbitrary, it can mislead the model.

Limitations and practical pitfalls

The best-known limitation is over-smoothing: as layers are stacked, node representations converge toward one another and lose discriminative detail. For this reason most practical GNNs use only two to four layers, often with residual connections or normalization to delay the effect.

  • Over-squashing: information from an exponentially growing neighborhood is compressed into a fixed-size vector, which weakens long-range signals.
  • Scalability: full-graph training on billions of edges exceeds memory, so neighbor sampling or graph partitioning is required.
  • Heterophily: when connected nodes tend to differ, simple averaging of neighbors can hurt accuracy.
  • Leakage in link prediction: test edges left in the message passing graph inflate reported results.

The short version

Some data is best described as a web of connections: people who know each other, atoms held together by bonds, or stations linked by train lines. A graph neural network is a type of AI model built for connections.

It works by letting each point in the web listen to its neighbors a few times in a row. After several rounds, each point carries a summary of its surroundings, and the model uses those summaries to make predictions. Connections become part of what the model learns, not just the individual items.

Where it makes a difference

A payment processor wants to detect accounts that belong to coordinated fraud rings. Looking at each account alone, many fraudulent accounts appear normal: modest transaction amounts, ordinary login times and valid documents.

The data team builds a graph in which accounts, devices, cards and shipping addresses are nodes, and shared usage creates edges. A three-layer GraphSAGE model trained on confirmed fraud cases learns that accounts sharing devices and addresses with known fraudsters form suspicious clusters. Compared with the previous per-account gradient-boosting model, the GNN catches more fraud rings at the same false-positive rate, because it uses the relationships that fraudsters find hardest to hide.