Definition
Node classification is the task of predicting a class for every node of a graph with node features , when only a subset is labelled. The standard semi-supervised benchmark is the Planetoid split of Cora, Citeseer and PubMed from Yang, Cohen and Salakhutdinov, "Revisiting Semi-Supervised Learning with Graph Embeddings" (ICML 2016). Kipf and Welling's Graph Convolutional Network (GCN) (ICLR 2017) made it the default GNN test.
The input is one graph. The output is a distribution over classes for each node: an matrix. A paper's topic, a user's community, a protein's function and a transaction's fraud flag are all node labels. Nodes are not independent samples. A node's neighbours carry evidence about its label, and the model must use them without depending on node order or on a fixed number of neighbours.
Before GNNs, the two baselines were feature-only classifiers that ignore edges and graph-only methods that ignore features. Label propagation (Zhu and Ghahramani, 2002; Zhu, Ghahramani and Lafferty, ICML 2003) spreads the known labels along edges. Shallow embeddings such as DeepWalk feed a random-walk embedding into a logistic regression (see Graph representation learning). A GNN combines both sources: it aggregates neighbour features and is trained on the labelled nodes only.
Setups: transductive and inductive
In the transductive setting there is one graph. Training sees the features and edges of every node, test nodes included; only the test labels are hidden. Planetoid uses 20 labelled nodes per class (140 on Cora), 500 validation nodes and 1,000 test nodes. In the inductive setting the test nodes, or whole test graphs, are absent during training. On PPI the model trains on 20 graphs and is tested on 2 graphs it never saw. Inductive models such as GraphSAGE must therefore learn a function of features and neighbourhood rather than a value per node.
Training is ordinary Categorical cross-entropy, but summed over the labelled rows only. The GNN still runs on the full graph:
- the train mask, e.g. 140 of Cora's 2,708 nodes
- one-hot label of node
- any GNN, e.g. a 2-layer GCN, applied row-wise after message passing; output logits
A 2-layer GNN gives each labelled node a 2-hop receptive field. The gradient therefore reaches the features of unlabelled nodes within two hops of a label. This is how 140 labels train a model that predicts 2,708 nodes.
Label propagation and homophily
Label propagation uses no features. Every unlabelled node repeatedly takes the average label distribution of its neighbours, and the labelled nodes are reset to their one-hot labels after each step. The fixed point is the harmonic solution:
- random-walk transition matrix; is the degree matrix
- unlabelled and labelled node index sets
- is the probability that a random walk from first hits a labelled node of class
Both label propagation and GCN-style averaging assume that neighbours tend to share a label. The usual measure is the edge homophily ratio:
- fraction of intra-class edges; is what random edges with balanced classes give
Cora, Citeseer and PubMed have of about 0.81, 0.74 and 0.80. The WebKB graphs (Texas, Wisconsin, Cornell), Actor, Chameleon and Squirrel sit around 0.1 to 0.3. These heterophilous graphs link nodes of different classes. There, averaging neighbours mixes in the wrong classes, and an MLP on the features alone often beats a GCN. H2GCN (Zhu et al., NeurIPS 2020) keeps the ego embedding separate from the neighbour aggregate and uses 2-hop neighbours. GPR-GNN (Chien et al., ICLR 2021) learns signed weights for each propagation step.
| Dataset | Nodes | Edges | Features | Classes | Edge h | Label prop. | GCN | GAT |
|---|---|---|---|---|---|---|---|---|
| Cora | 2,708 | 5,429 | 1,433 | 7 | 0.81 | 68.0 | 81.5 | 83.0 |
| Citeseer | 3,327 | 4,732 | 3,703 | 6 | 0.74 | 45.3 | 70.3 | 72.5 |
| PubMed | 19,717 | 44,338 | 500 | 3 | 0.80 | 63.0 | 79.0 | 79.0 |
Other settings and their metrics
- GCN config
- 2 layers, 16 hidden units, dropout 0.5, L2 5·10⁻⁴, Adam lr 0.01, up to 200 epochs with early stopping on validation loss
- PPI (inductive)
- 24 protein graphs: 20 train, 2 val, 2 test; 121 binary labels per node, so the metric is micro-F1; GAT reaches 0.973
- Reddit (inductive)
- 232,965 posts linked by shared commenters, label = subreddit; GraphSAGE splits by time, not at random
- ogbn-arxiv
- 169,343 papers, 40 subject classes; time split: train up to 2017, val 2018, test 2019 onwards; accuracy
- ogbn-proteins
- 112 binary function tasks; split by species; metric is ROC-AUC averaged over tasks
- Splits matter
- Shchur et al. (2018) showed that GNN rankings change across random splits; report mean ± std over many splits and seeds
Worked example: label propagation on 5 nodes
Edges 1–2, 1–3, 2–3, 3–4, 4–5. Node 1 is labelled A and node 5 is labelled B. The true labels are A for nodes 1–3 and B for 4–5, so 4 of the 5 edges are intra-class and . Track , starting from , with synchronous updates.
| Node | Neighbours | t = 1 | t = 2 | t = 3 | t = ∞ (exact) | Prediction |
|---|---|---|---|---|---|---|
| 2 | 1, 3 | 0 | 0 | 0.083 | 1/8 = 0.125 | A ✓ |
| 3 | 1, 2, 4 | 0 | 0.167 | 0.167 | 1/4 = 0.25 | A ✓ |
| 4 | 3, 5 | 0.5 | 0.5 | 0.583 | 5/8 = 0.625 | B ✓ |
The exact values solve , , . Node 3 has three neighbours and only one of them leads toward B, so it ends at 1/4. If edge 3–4 were replaced by 2–5, node 2 would rise from 0.125 to 0.4, close to the wrong side. Label propagation has no features to fall back on, so the edges alone decide.
1import torch, torch.nn.functional as F2import torch_geometric.transforms as T3from torch_geometric.datasets import Planetoid4from torch_geometric.nn import GCNConv5from torch_geometric.nn.models import LabelPropagation6from torch_geometric.utils import homophily78data = Planetoid("data", "Cora", transform=T.NormalizeFeatures())[0] # public split9print(int(data.train_mask.sum()), int(data.val_mask.sum()), int(data.test_mask.sum())) # 140 500 100010print(homophily(data.edge_index, data.y, method="edge")) # ~0.811112acc = lambda pred, m: (pred[m] == data.y[m]).float().mean().item()13lp = LabelPropagation(num_layers=50, alpha=0.9) # features unused14print("label prop", acc(lp(data.y, data.edge_index, mask=data.train_mask).argmax(1), data.test_mask))1516class GCN(torch.nn.Module):17 def __init__(self, d, h, c):18 super().__init__()19 self.c1, self.c2 = GCNConv(d, h), GCNConv(h, c)20 def forward(self, x, ei):21 x = F.dropout(x, 0.5, self.training)22 x = F.relu(self.c1(x, ei))23 x = F.dropout(x, 0.5, self.training)24 return self.c2(x, ei)2526model = GCN(data.num_features, 16, 7)27opt = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)28best_val = test_at_best = 0.029for epoch in range(200):30 model.train(); opt.zero_grad()31 out = model(data.x, data.edge_index) # all 2,708 nodes, every step32 F.cross_entropy(out[data.train_mask], data.y[data.train_mask]).backward()33 opt.step()34 model.eval()35 with torch.no_grad():36 pred = model(data.x, data.edge_index).argmax(1)37 if (v := acc(pred, data.val_mask)) > best_val: # select on val, never on test38 best_val, test_at_best = v, acc(pred, data.test_mask)39print("GCN", test_at_best) # about 0.81| Aspect | Transductive | Inductive |
|---|---|---|
| Test nodes at training time | present: features and edges used, labels hidden | absent (new nodes or whole new graphs) |
| Typical benchmarks | Cora, Citeseer, PubMed, ogbn-arxiv | PPI, Reddit (time split) |
| What can be learned | also per-node parameters (DeepWalk, node2vec) | only a function of features and neighbourhood |
| Typical models | GCN, GAT, label propagation | GraphSAGE, GAT, GCN with sampling |
Check yourself
In the Planetoid setting on Cora, what does a GCN see during training?
Check yourself
A graph has edge homophily h = 0.15 with 3 balanced classes, and the node features are informative. Which baseline should you expect to be strongest?
Remember
- ✓One graph, few labels: the loss covers only , while the GNN runs on all nodes; Planetoid uses 20 labels per class, 500 val and 1,000 test nodes.
- ✓Transductive: test nodes' features and edges are visible during training. Inductive (PPI, Reddit): test nodes or graphs are unseen, so the model must be a function of neighbourhoods.
- ✓Label propagation () uses only edges; on Cora it scores 68.0% against 81.5% for GCN and 83.0% for GAT.
- ✓Edge homophily predicts whether smoothing helps: Cora 0.81, but 0.1 to 0.3 on WebKB, Actor, Chameleon and Squirrel, where MLPs often win.
- ✓Metrics: accuracy for single-label tasks, micro-F1 for multi-label (PPI), ROC-AUC for ogbn-proteins; report mean ± std over splits and seeds.
- ✓Tune on validation only, and check strong baselines such as MLP plus label propagation (Correct and Smooth).