Definition
Graph classification is the task of predicting one label for each graph 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 , and a classifier on . 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 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.
Readout
The readout must be a permutation-invariant function of the multiset of node embeddings. The three simple choices keep different information:
- node embedding after the last layer (GIN concatenates the readouts of all layers)
- keeps counts and therefore graph size; injective on multisets with a suitable MLP (see Graph Isomorphism Network (GIN))
- keeps proportions only, invariant to graph size
- keeps per-channel extremes, i.e. "is there a node with property ?"
Learned readouts weight or order the nodes. Attention pooling computes , 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 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 nodes to clusters:
- row-wise softmax: each node spreads over the clusters
- features and dense weighted adjacency of the coarsened graph; repeated until one node is left
DiffPool's is dense, so memory grows as . Top- 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.
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 .
Worked example: three readouts of two graphs
| Readout | h_G1 | h_G2 | What 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 |
Benchmarks
| Dataset | Domain | Graphs | Classes | Avg nodes |
|---|---|---|---|---|
| MUTAG | nitro compounds, mutagenicity | 188 | 2 | 17.93 |
| PROTEINS | proteins, enzyme or not | 1,113 | 2 | 39.06 |
| NCI1 | chemical compounds, anti-cancer screen | 4,110 | 2 | 29.87 |
| D&D | protein structures | 1,178 | 2 | 284.32 |
| IMDB-BINARY | actor ego-networks, genre | 1,000 | 2 | 19.77 |
| REDDIT-BINARY | discussion threads | 2,000 | 2 | 429.63 |
| COLLAB | scientific collaboration ego-networks | 5,000 | 3 | 74.49 |
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)
- 1Outer loop: stratified 10-fold cross-validation. Each outer test fold is used once, only to report the score.
- 2Inner loop: on the 9 training folds, hold out a validation part and choose hyperparameters and the stopping epoch on it.
- 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.
- 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.
1import torch, torch.nn as nn, torch.nn.functional as F2from sklearn.model_selection import StratifiedKFold3from torch_geometric.datasets import TUDataset4from torch_geometric.loader import DataLoader5from torch_geometric.nn import GINConv, global_add_pool67ds = TUDataset("data/TU", name="PROTEINS") # 1,113 graphs, 3 node-label channels8y = ds.y.numpy()910class 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.x18 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 batch2122accs = []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}")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.