# 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.

Source: https://www.mlfoundry.in/learn/graph-classification  
Section: Deep Learning › Graph Neural Networks (GNNs)  
Level: core · 8 min read · updated 2026-10-21

**Graph classification:** is the task of predicting one label $y_G$ for each graph $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 $h_G$, and a classifier on $h_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 $B$ 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.

> Figure: 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:

$$
h_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
$$

- $h_v$: node embedding after the last layer (GIN concatenates the readouts of all layers)
- $\text{sum}$: keeps counts and therefore graph size; injective on multisets with a suitable MLP (see **Graph Isomorphism Network (GIN)**)
- $\text{mean}$: keeps proportions only, invariant to graph size
- $\text{max}$: keeps per-channel extremes, i.e. "is there a node with property $j$?"

Learned readouts weight or order the nodes. Attention pooling computes $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 $k$ 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 $n$ nodes to $m<n$ clusters:

$$
S=\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
$$

- $S$: row-wise softmax: each node spreads over the $m$ clusters
- $X',\ A'$: features and dense weighted adjacency of the coarsened graph; repeated until one node is left

DiffPool's $A'$ is dense, so memory grows as $n^2$. Top-$k$ 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.

> Figure: 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|$.

## Worked example: three readouts of two graphs

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]

| 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

TUDataset (Morris et al., 2020) graph-classification sets often used with GNNs

| 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)**

1. Outer loop: stratified 10-fold cross-validation. Each outer test fold is used once, only to report the score.
2. Inner loop: on the 9 training folds, hold out a validation part and choose hyperparameters and the stopping epoch on it.
3. Retrain 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. Report 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.

> **Selecting on the test folds:** Many early papers reported the mean of the 10 **validation-fold** accuracies at the epoch that maximised that same mean. This selects on the data used for scoring, and so overstates accuracy. Errica et al. re-evaluated five GNNs under the protocol above. On D&D and PROTEINS, the structure-agnostic baseline matched or beat all of them. With 188 graphs (MUTAG), each fold has about 19 graphs, so one graph moves the fold accuracy by about 5 points, and standard deviations of 5–7 points are normal.

> **Check what the graph adds:** Always run the baseline that ignores edges. If an MLP on $\sum_v x_v$ is as good as the GNN, the labels depend on which node features occur, not on how the nodes are connected. Then a better architecture will not help, and a richer readout or richer features might. Check for size shortcuts as well: if the test graphs will be larger than the training graphs, split by size during development, as in the figure.

```python
import torch, torch.nn as nn, torch.nn.functional as F
from sklearn.model_selection import StratifiedKFold
from torch_geometric.datasets import TUDataset
from torch_geometric.loader import DataLoader
from torch_geometric.nn import GINConv, global_add_pool

ds = TUDataset("data/TU", name="PROTEINS")           # 1,113 graphs, 3 node-label channels
y = ds.y.numpy()

class Net(nn.Module):
    def __init__(self, d_in, d=64, layers=4, classes=2):
        super().__init__()
        mlp = lambda i: nn.Sequential(nn.Linear(i, d), nn.BatchNorm1d(d), nn.ReLU(), nn.Linear(d, d), nn.ReLU())
        self.convs = nn.ModuleList([GINConv(mlp(d_in if k == 0 else d)) for k in range(layers)])
        self.head = nn.Sequential(nn.Linear(d, d), nn.ReLU(), nn.Dropout(0.5), nn.Linear(d, classes))
    def forward(self, data):
        h = data.x
        for conv in self.convs:
            h = conv(h, data.edge_index)
        return self.head(global_add_pool(h, data.batch))  # one row per graph in the batch

accs = []
for tr, te in StratifiedKFold(10, shuffle=True, random_state=0).split(y, y):
    model = Net(ds.num_features)
    opt = torch.optim.Adam(model.parameters(), lr=0.01)
    for epoch in range(100):
        model.train()
        for b in DataLoader(ds[tr.tolist()], batch_size=32, shuffle=True):
            opt.zero_grad()
            F.cross_entropy(model(b), b.y).backward()
            opt.step()
    model.eval()
    with torch.no_grad():
        b = next(iter(DataLoader(ds[te.tolist()], batch_size=len(te))))
        accs.append((model(b).argmax(1) == b.y).float().mean().item())
print(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)

**Strengths**

- 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.

**Limitations**

- 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.

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

- A. Mean
- B. Max (or sum)
- C. Mean over the first k nodes
- D. Any readout gives the same result

**Answer:** B. Max (or sum) — Existence is a max: one node with a high "nitro" channel decides the label regardless of the molecule's size. A sum also works if the classifier learns a threshold at one. A mean dilutes one nitro group among many atoms, so the same group gives a smaller signal in a larger molecule.

**Question:** 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?

- A. Nothing; that is standard cross-validation
- B. The held-out folds are used both to select the model and to report its score, so the estimate is optimistic
- C. 10 folds are too many for small datasets
- D. Cross-validation cannot be used with GNNs

**Answer:** B. The held-out folds are used both to select the model and to report its score, so the estimate is optimistic — Model selection (here, the epoch) must use data that is not used to report the score. Nested CV, with an inner validation split inside each outer training set, gives an unbiased estimate. Errica et al. (ICLR 2020) showed that rankings change under the stricter protocol.

**Key points**

- 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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
