Graph classification

Graph classification predicts one label per graph: message passing gives node embeddings, a permutation-invariant readout (sum, mean, max or learned pooling) pools them into one vector, and an MLP classifies it.

8 min read962 wordscore0 viewsupdated 2026-10-21

Definition

Graph classification is the task of predicting one label yGy_G for each graph G=(V,E,X)G=(V,E,X) in a dataset of many separate graphs, for example "mutagenic or not" for a molecule or "which subreddit type" for a discussion thread. A GNN solves it with message passing over each graph, a readout that pools the node embeddings into a single vector hGh_G, and a classifier on hGh_G. Graph regression (predicting a number, as on QM9 or ZINC) uses the same pipeline with a different loss.

Three things make it harder than ordinary classification. Graphs in one dataset differ in size: a few nodes for a small molecule, hundreds for a protein or a Reddit thread. The nodes have no canonical order, so the output must not change when they are renumbered. And the label is a property of the whole structure, so information from every part of the graph has to reach one vector. Before GNNs, the standard method was a graph kernel, such as the Weisfeiler–Lehman subtree kernel (Shervashidze et al., JMLR 2011), with an SVM on top.

The node-level part is the same as in Node classification: any layer from Graph Convolutional Network (GCN), Graph Isomorphism Network (GIN) or Message Passing Neural Networks (MPNN) works. What is specific to graph classification is the readout, the way graphs are batched, and the evaluation.

Pipeline and batching

A mini-batch of BB graphs is stored as one large graph: a block-diagonal adjacency, stacked node features and a batch vector that maps each node to its graph. No edges cross graphs, so message passing on the union is the same as running it on each graph separately. No padding is needed, and each step's cost depends only on the total number of nodes and edges in the batch.

one label per graph: batch → message passing → readout per graph → classifier1. two graphs (filled = type A)012345678G1: 4 nodes, y = 0G2: 5 nodes, y = 12. batch = disjoint unionA: 9 × 9,block-diagonalX: 9 × FE: 18 directed(9 undirected)batch = [0 0 0 0 1 1 1 1 1]no edges between graphs, somessages never cross them3. K message-passing layersGCN / GIN / GAT ...shared weights,all graphs at onceH: 9 × d4. readout: pool the rows of H that share a batch idh0h1h2h3h4h5h6h7h8h_G1h_G2sum / mean / max (permutation-invariant)or attention, Set2Set, SortPool, DiffPool5. MLP on h_Gh_G: 2 × dlogits: 2 × CC = number ofclasses6. loss per graphcross-entropy vsy = [0, 1]BCE per task formulti-label (molpcba)B graphs in a batch → B predictions
fig.Two graphs (a 4-node triangle with a tail, label 0, and a 5-cycle, label 1) batched as one 9-node graph: a block-diagonal 9 × 9 adjacency with 18 directed edges and batch = [0 0 0 0 1 1 1 1 1]. Message passing gives H of shape 9 × d. The readout pools rows with the same batch id into h_G of shape 2 × d, and an MLP gives 2 × C logits for a per-graph cross-entropy loss.

Readout

The readout must be a permutation-invariant function of the multiset of node embeddings. The three simple choices keep different information:

hGsum=∑v∈Vhv,hGmean=1∣V∣∑v∈Vhv,(hGmax)j=max⁡v∈V (hv)jh_G^{\text{sum}}=\sum_{v\in V}h_v,\qquad h_G^{\text{mean}}=\frac{1}{|V|}\sum_{v\in V}h_v,\qquad \big(h_G^{\text{max}}\big)_j=\max_{v\in V}\,(h_v)_j
hvh_v
node embedding after the last layer (GIN concatenates the readouts of all layers)
sum\text{sum}
keeps counts and therefore graph size; injective on multisets with a suitable MLP (see Graph Isomorphism Network (GIN))
mean\text{mean}
keeps proportions only, invariant to graph size
max\text{max}
keeps per-channel extremes, i.e. "is there a node with property jj?"

Learned readouts weight or order the nodes. Attention pooling computes hG=∑vsoftmax⁡v ⁣(g(hv)) f(hv)h_G=\sum_v\operatorname{softmax}_v\!\big(g(h_v)\big)\,f(h_v), the form of PyG's AttentionalAggregation; Li et al. (2016) used a sigmoid gate in the same place. Set2Set (Vinyals, Bengio, Kudlur, ICLR 2016) runs an LSTM that attends over the nodes several times; Gilmer et al. used it in MPNN. SortPool, from DGCNN (Zhang et al., AAAI 2018), sorts the nodes by their last channel, keeps the top kk and applies a 1D convolution.

Hierarchical pooling coarsens the graph in stages, much as a CNN pools an image. DiffPool (Ying et al., NeurIPS 2018) learns a soft assignment of nn nodes to m<nm<n clusters:

S=softmax⁡ ⁣(GNNpool(A,X))∈Rn×m,X′=S⊤ GNNembed(A,X),A′=S⊤ASS=\operatorname{softmax}\!\big(\mathrm{GNN}_{\text{pool}}(A,X)\big)\in\mathbb R^{n\times m},\qquad X'=S^{\top}\,\mathrm{GNN}_{\text{embed}}(A,X),\qquad A'=S^{\top}AS
SS
row-wise softmax: each node spreads over the mm clusters
X′, A′X',\ A'
features and dense weighted adjacency of the coarsened graph; repeated until one node is left

DiffPool's A′A' is dense, so memory grows as n2n^2. Top-kk methods (gPool in Graph U-Nets, Gao and Ji, ICML 2019; SAGPool, Lee et al., ICML 2019) instead score the nodes, keep the top fraction and take the induced subgraph. A virtual node joined to every node is a cheap alternative that gives every node a global summary at every layer. It is a standard option in the OGB baselines.

h_G = sum_v [a_v, d_v] · logistic regression on h_G · random 70/30 splitΣ_v a_v (number of A nodes)Σ_v d_v = 2|E|0102670task: countclass 1 if ≥ 8 nodes are type Areadouttraintestsum100.0%100.0%mean87.5%81.3%max67.9%60.4%majority class on test: 54.2%160 graphs, 6–30 nodes eachtrain 112 · test 48class 1 among test graphs: 26node features after one summessage-passing step:a_v = 1 if type A, d_v = Σ_u 1class 0class 1filled = train · ring = testdashed = decision line, p = 0.5points are jittered for display only; accuracy uses the exact readouts
task
readout
split
fig.160 synthetic graphs (6–30 nodes). Node features after one sum step are x_v = [a_v, d_v] (type A, degree); the readout gives a 2-D h_G and a logistic regression classifies it. Default (task count, random split): sum 100.0% train / 100.0% test, mean 81.3% test, max 60.4% (majority 54.2%). Task ratio: mean gets 97.9% test, max 54.2%. Task hub with the size split (train n ≤ 18, test n > 18): max stays at 100.0%, while sum falls from 89.4% train to 37.3% test, below the 65.3% majority.

The figure makes two points. No single readout is best: the task decides whether counts, proportions or extremes matter. A readout that only correlates with the label through graph size can also look good under a random split and then fail when the test graphs are larger. Sum readouts are the most exposed to this, because their values grow with ∣V∣|V|.

Worked example: three readouts of two graphs

Readouth_G1h_G2What differs
sum[2, 8][2, 10]2|E| (8 vs 10); the A count ties at 2
mean[0.5, 2.0][0.4, 2.0]fraction of A; mean degree ties at 2.0
max[1, 3][1, 2]max degree; 'has an A node' ties
Node features [a_v, d_v] (1 if type A; degree). G1: triangle 0-1-2 with tail 2-3, a = [1, 0, 1, 0], d = [2, 2, 3, 1]. G2: 5-cycle, a = [1, 1, 0, 0, 0], d = [2, 2, 2, 2, 2]

Benchmarks

DatasetDomainGraphsClassesAvg nodes
MUTAGnitro compounds, mutagenicity188217.93
PROTEINSproteins, enzyme or not1,113239.06
NCI1chemical compounds, anti-cancer screen4,110229.87
D&Dprotein structures1,1782284.32
IMDB-BINARYactor ego-networks, genre1,000219.77
REDDIT-BINARYdiscussion threads2,0002429.63
COLLABscientific collaboration ego-networks5,000374.49
TUDataset (Morris et al., 2020) graph-classification sets often used with GNNs

OGB graph-property datasets (Hu et al., NeurIPS 2020)

ogbg-molhiv
41,127 molecules, binary (HIV inhibition), ROC-AUC, scaffold split
ogbg-molpcba
437,929 molecules, 128 binary tasks with missing labels, average precision, scaffold split
ogbg-ppa
158,100 protein-association graphs, 37 classes (taxonomic groups), accuracy, split by species
Why OGB
fixed public splits and an evaluator per dataset, so papers report comparable numbers instead of each choosing its own folds

Social TU graphs have no node features. The usual fix is a one-hot degree or a constant feature. Without it, mean and max readouts see identical inputs (see Graph Isomorphism Network (GIN)). For imbalanced molecular tasks, accuracy is misleading: OGB uses ROC-AUC on molhiv and average precision on the much more skewed molpcba. Molecular property prediction covers the scaffold split.

Evaluation pitfalls

A sound protocol for TU-style datasets (after Errica et al., ICLR 2020)

  1. 1Outer loop: stratified 10-fold cross-validation. Each outer test fold is used once, only to report the score.
  2. 2Inner loop: on the 9 training folds, hold out a validation part and choose hyperparameters and the stopping epoch on it.
  3. 3Retrain the chosen configuration on the outer training folds several times (Errica et al. used 3 runs) and average the test scores, to reduce the effect of random initialisation.
  4. 4Report mean ± standard deviation over the outer folds, next to a structure-agnostic baseline (an MLP on summed node features) and, if possible, a WL kernel.
python
1import torch, torch.nn as nn, torch.nn.functional as F
2from sklearn.model_selection import StratifiedKFold
3from torch_geometric.datasets import TUDataset
4from torch_geometric.loader import DataLoader
5from torch_geometric.nn import GINConv, global_add_pool
6
7ds = TUDataset("data/TU", name="PROTEINS") # 1,113 graphs, 3 node-label channels
8y = ds.y.numpy()
9
10class Net(nn.Module):
11 def __init__(self, d_in, d=64, layers=4, classes=2):
12 super().__init__()
13 mlp = lambda i: nn.Sequential(nn.Linear(i, d), nn.BatchNorm1d(d), nn.ReLU(), nn.Linear(d, d), nn.ReLU())
14 self.convs = nn.ModuleList([GINConv(mlp(d_in if k == 0 else d)) for k in range(layers)])
15 self.head = nn.Sequential(nn.Linear(d, d), nn.ReLU(), nn.Dropout(0.5), nn.Linear(d, classes))
16 def forward(self, data):
17 h = data.x
18 for conv in self.convs:
19 h = conv(h, data.edge_index)
20 return self.head(global_add_pool(h, data.batch)) # one row per graph in the batch
21
22accs = []
23for tr, te in StratifiedKFold(10, shuffle=True, random_state=0).split(y, y):
24 model = Net(ds.num_features)
25 opt = torch.optim.Adam(model.parameters(), lr=0.01)
26 for epoch in range(100):
27 model.train()
28 for b in DataLoader(ds[tr.tolist()], batch_size=32, shuffle=True):
29 opt.zero_grad()
30 F.cross_entropy(model(b), b.y).backward()
31 opt.step()
32 model.eval()
33 with torch.no_grad():
34 b = next(iter(DataLoader(ds[te.tolist()], batch_size=len(te))))
35 accs.append((model(b).argmax(1) == b.y).float().mean().item())
36print(f"{100 * torch.tensor(accs).mean():.1f} ± {100 * torch.tensor(accs).std():.1f}")
GIN + sum readout on PROTEINS with stratified 10-fold CV (PyTorch Geometric 2.x; not run here; nested model selection omitted for brevity)

Use when

  • +One pipeline (message passing, readout, MLP) handles graphs of any size and node order.
  • +Batching as a disjoint union needs no padding and scales with the total edge count.
  • +Sum readout plus an expressive GNN can separate every pair of graphs that 1-WL separates.

Avoid when

  • −Flat readouts compress hundreds of nodes into one vector; hierarchical pooling helps but costs memory (DiffPool is dense) or drops nodes (top-k).
  • −Popular TU benchmarks are small and noisy, so differences of 1–2 points are usually within one standard deviation.
  • −Models can exploit graph size or feature counts and then fail on larger or differently distributed test graphs.

Check yourself

A dataset's label is 'the molecule contains at least one nitro group'. The node embeddings detect nitro groups. Which readout fits best?

Check yourself

A paper reports 10-fold CV accuracy, picking the epoch that maximises the mean accuracy over the 10 held-out folds. What is the problem?

Remember

  • ✓Graph classification predicts one label per graph: message passing, a permutation-invariant readout, then an MLP.
  • ✓Batches are disjoint unions: block-diagonal adjacency plus a batch vector; readout pools by batch id.
  • ✓Sum keeps counts and size, mean keeps proportions, max keeps extremes. Set2Set, attention, SortPool, DiffPool and top-k pooling learn the readout.
  • ✓TU datasets (MUTAG 188 graphs, PROTEINS 1,113, NCI1 4,110, …) are small: use stratified nested CV, report mean ± std, and compare with a structure-agnostic baseline.
  • ✓OGB (ogbg-molhiv: ROC-AUC, ogbg-molpcba: AP, ogbg-ppa: accuracy) fixes splits and evaluators for comparable results.
  • ✓Watch for size shortcuts: a readout that tracks |V| can collapse when the test graphs are larger.
← back to Deep Learning roadmap