Graph Neural Networks – Theory, Architectures and Real-World Applications

Most machine learning algorithms assume data is tabular — a fixed-length feature vector for each observation, with no inherent relationship structure between observations. This assumption is violated by a large and growing class of real-world problems: fraud detection in payment networks (where fraud patterns emerge from transaction relationships, not just individual transaction features), drug discovery (where molecule properties depend on how atoms are bonded), social recommendation (where user preferences are shaped by social connections), and supply chain optimisation (where a disruption propagates through a network of dependencies). Graph Neural Networks, developed and refined between 2016 and 2023, provide a principled way to learn from data with relational structure. This guide covers the theory, the major architectures, the key tasks, and the practical considerations for applying GNNs to real problems.

Graph Data — Terminology and Representation

A graph G consists of a set of nodes V (also called vertices) and a set of edges E connecting pairs of nodes. Nodes and edges can each carry feature vectors: node features (the attributes of each entity — a user’s age, account tenure, and transaction history in a fraud graph) and edge features (the attributes of each relationship — the transaction amount and time in the same fraud graph). Graphs can be directed (edges have a direction: A follows B on Twitter does not imply B follows A) or undirected (friendship in Facebook is symmetric). Graphs can also be heterogeneous, containing multiple types of nodes and edges — a knowledge graph with Person, Company, and Location nodes connected by WORKS_AT, LOCATED_IN, and FOUNDED_BY edges.

In practice, a graph is represented computationally as an adjacency matrix A (an n×n matrix where A[i][j] = 1 if there is an edge from node i to node j) and a node feature matrix X (an n×d matrix where each row is the d-dimensional feature vector for one node). For large, sparse graphs, the adjacency is stored as an edge index — a list of (source, target) pairs — rather than a dense matrix, since most real-world graphs have far fewer edges than the n² possible pairs.

GNN Architectures — From GCN to GAT

The landscape of GNN architectures is large but not chaotic — most architectures are variants on a single core idea called message passing, and they differ primarily in how they aggregate messages from neighbours and how they weight different neighbours’ contributions.

Graph Convolutional Networks (GCN) — proposed by Kipf and Welling (2017) — are the simplest and most widely studied GNN. A GCN layer computes a new representation for each node by averaging the features of its neighbours (including itself), then passing the result through a linear transformation and a non-linearity. The averaging is normalised by the degree of both the node and its neighbours, preventing high-degree nodes from dominating. GCN is transductive — it cannot make predictions for nodes that were not seen during training — and works best on homophilic graphs where connected nodes tend to have the same label.

GraphSAGE (Hamilton et al., 2017) addressed GCN’s transductive limitation by introducing inductive learning: rather than learning embeddings for specific nodes, GraphSAGE learns aggregation functions that generalise to unseen nodes. It samples a fixed number of neighbours at each layer rather than using all of them, making it scalable to graphs with millions of nodes. The aggregation function can be mean (equivalent to GCN), LSTM over a random permutation of neighbours, or max pooling over transformed neighbour features. GraphSAGE is the practical choice for production graph ML systems where the graph evolves and new nodes appear continuously.

Graph Attention Networks (GAT) — Veličković et al. (2018) — replace the fixed symmetric aggregation of GCN with learned attention weights. Each node learns to assign different importance to different neighbours, computed as a function of both nodes’ features. The attention mechanism allows the model to focus on structurally important or informationally relevant neighbours and ignore noisy ones. GAT is particularly effective on heterophilic graphs (where connected nodes have different labels) and in domains where the strength of relationships varies significantly across edges.

Graph Isomorphism Networks (GIN) — Xu et al. (2019) — are theoretically motivated: they are provably the most expressive class of GNN in terms of distinguishing non-isomorphic graphs. GIN uses a sum aggregation (rather than mean or max) and a multi-layer perceptron to update node representations. The theoretical analysis showed that sum aggregation is strictly more powerful than mean or max for distinguishing graph structures. GIN is the preferred architecture for graph-level classification tasks like molecular property prediction.

GNN Tasks — Node, Edge, and Graph Level

GNN applications fall into three levels, corresponding to whether the prediction target is a single node, a pair of nodes (an edge), or the entire graph. The architecture and training setup differ across these levels, but the message-passing backbone is the same.

Node classification assigns a label to each node. Examples: classifying Twitter accounts as human or bot; labelling research papers by field in a citation network; identifying fraudulent accounts in a payment network. The GNN learns a node embedding for each node, and a classifier head (a linear layer followed by softmax) maps the embedding to a class probability. Training uses cross-entropy loss on labelled nodes. Semi-supervised node classification — where only a small fraction of nodes are labelled — is a particularly common setup and one where GNNs have a strong advantage over tabular models, because they can propagate label information through the graph structure.

Link prediction predicts whether an edge should exist between two nodes. Examples: recommending friends on a social network; predicting interactions between drugs and proteins in a pharmacological network; identifying missing facts in a knowledge graph. The standard approach is to learn node embeddings with a GNN, then score candidate edges using a similarity function (dot product, Hadamard product, concatenation + MLP) applied to the two endpoint embeddings. Training uses binary cross-entropy on observed positive edges and sampled negative edges.

Graph classification assigns a label to an entire graph. Examples: predicting whether a molecule is toxic; classifying a computer program by its functionality using its call graph; detecting communities of bots in social network subgraphs. This requires a readout (global pooling) operation that aggregates all node embeddings into a single graph-level embedding — typically global mean pooling, global sum pooling, or hierarchical pooling. The graph embedding is then passed to a classifier.

Practical Challenges and Limitations

Over-smoothing is the fundamental depth limitation of GNNs. As the number of message-passing layers increases, each node aggregates information from an exponentially growing neighbourhood. After k layers, every node has a representation that incorporates information from all nodes within k hops. On typical real-world graphs (small-world graphs with average path lengths of 5–7), just 4–5 layers are sufficient to mix information from almost every node — making all node representations converge to similar values. This is why effective GNNs in practice rarely exceed 3–4 layers, despite the success of much deeper networks in image and text domains. Techniques to mitigate over-smoothing include residual connections (preserving the original node features alongside aggregated representations), dense connections, and jumping knowledge networks (JK-Nets) that combine representations from all layers.

Scalability is the second major challenge. Full-batch training on large graphs requires storing the entire adjacency and all node features in GPU memory simultaneously, which is infeasible for graphs with millions of nodes. Mini-batch training with neighbour sampling (as in GraphSAGE) is the standard solution, but it introduces approximation error and requires careful tuning of the sampling budget. Cluster-GCN partitions the graph into clusters and trains on one cluster at a time, preserving most intra-cluster edges at the cost of losing inter-cluster information. GraphSAINT samples subgraphs using random walks, edges, or nodes, and has shown strong performance at billion-edge scale.

✦ SUMMARIZE THIS ARTICLE WITH AI

ChatGPT Perplexity Claude Grok

The neural network foundations that GNNs build on — MLP, attention mechanisms, and backpropagation — are covered in our Neural Network Architectures guide. The attention mechanism central to GAT is explained in our Transformers and Attention guide. Anomaly detection applications on graph-structured data are in our Anomaly Detection guide. Recommendation systems that use graph-based collaborative filtering are covered in our Recommendation Systems guide.