Node classification

Predict a label for each node from its features and the graph; on Cora's Planetoid split (140 train labels, 500 val, 1,000 test) a 2-layer GCN scores 81.5% against 68.0% for label propagation, and both rely on homophily.

8 min read885 wordscore0 viewsupdated 2026-10-21

Definition

Node classification is the task of predicting a class yvy_v for every node vv of a graph G=(V,E)G=(V,E) with node features X∈RN×FX\in\mathbb{R}^{N\times F}, when only a subset VL⊂VV_L\subset V 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 CC classes for each node: an N×CN\times C 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.

Transductive: one graph, masked labels??????■ train label · ◆ val · ○ testtest: features + edges used, label hiddenviolet dashed = cross-class · h = 11/13 ≈ 0.85Inductive: test graphs are unseen⋮shared WPPI: train on 20 graphs, val 2,test on 2 unseen · 121 labels, micro-F1new graphCora, Planetoid public split (transductive)X 2708 × 1433A: 5,429 edges2-layer GNNf(X, A)logits 2708 × 7softmax per nodeCE on 140 trainselect on 500 valaccuracy on1,000 test nodesEvery forward pass runs on all 2,708 nodes; the masks only decide which labelsenter the loss (140 = 20 per class × 7) and which predictions are scored.Never tune on the test mask: pick epochs and hyperparameters on the 500 val nodes.
fig.Left: transductive. One graph; squares are the labelled train nodes, diamonds validation and circles test. Test nodes still contribute their features and edges to every forward pass. Two of the 13 edges cross classes, so the edge homophily is 11/13 ≈ 0.85. Right: inductive. Weights learned on training graphs are applied to an unseen graph. Bottom: the Cora pipeline, where the masks only choose which rows enter the loss and the metric.

Training is ordinary Categorical cross-entropy, but summed over the labelled rows only. The GNN fθf_\theta still runs on the full graph:

L(θ)=−1∣VL∣∑i∈VL∑c=1CYic log⁡Y^ic,Y^=softmax⁡ ⁣(fθ(X,A))\mathcal{L}(\theta)=-\frac{1}{|V_L|}\sum_{i\in V_L}\sum_{c=1}^{C}Y_{ic}\,\log\hat Y_{ic},\qquad \hat Y=\operatorname{softmax}\!\big(f_\theta(X,A)\big)
VLV_L
the train mask, e.g. 140 of Cora's 2,708 nodes
YicY_{ic}
one-hot label of node ii
fθ(X,A)f_\theta(X,A)
any GNN, e.g. a 2-layer GCN, applied row-wise after message passing; output N×CN\times C 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:

FU(t+1)=(D−1AF(t))U,FL=YL⟹FU=(I−PUU)−1PUL YLF^{(t+1)}_U=\big(D^{-1}AF^{(t)}\big)_U,\quad F_L=Y_L\qquad\Longrightarrow\qquad F_U=(I-P_{UU})^{-1}P_{UL}\,Y_L
P=D−1AP=D^{-1}A
random-walk transition matrix; DD is the degree matrix
U, LU,\ L
unlabelled and labelled node index sets
FUF_U
FvcF_{vc} is the probability that a random walk from vv first hits a labelled node of class cc

Both label propagation and GCN-style averaging assume that neighbours tend to share a label. The usual measure is the edge homophily ratio:

h=∣{(u,v)∈E: yu=yv}∣∣E∣h=\frac{\big|\{(u,v)\in E:\ y_u=y_v\}\big|}{|E|}
hh
fraction of intra-class edges; h≈1/Ch\approx1/C is what random edges with balanced classes give

Cora, Citeseer and PubMed have hh 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.

3-class SBM, 60 nodes, avg degree ≈ 5 · colour = propagated Ŝ^K X■ labelled (train) · ● fill = prediction, ring = true class · dashed = errorviolet edges join different classesedges 152edge homophily h = 0.81labelled 6 · test 54 (all others)test accuracyfeatures only50.0%27/54 correctpropagated, K = 292.6%50/54 correctlabel propagation83.3%45/54 correctdashed tick = chance (1/3)LP: labels never reach 0classifier: nearest classcentroid of labelled nodesŜ = D̃^−½ (A+I) D̃^−½
colour nodes by
fig.A 3-class stochastic block model with 60 nodes, average degree about 5, and weak 6-d Gaussian features. All three predictors use the same nearest-centroid rule on the labelled nodes. Default (target h 0.80, 2 labels per class, K = 2): 152 edges with measured h = 0.81. Features alone get 27/54 = 50.0%, propagated features Ŝ²X get 50/54 = 92.6% and label propagation 45/54 = 83.3%. Set h to 0.20 (145 edges, h = 0.21): propagation drops to 21/54 = 38.9% and label propagation to 17/54 = 31.5%, below the unchanged 50.0% of the features. Back at h 0.80 with 1 label per class, label propagation falls to 25/57 = 43.9% while Ŝ²X reaches 55/57 = 96.5%.
DatasetNodesEdgesFeaturesClassesEdge hLabel prop.GCNGAT
Cora2,7085,4291,43370.8168.081.583.0
Citeseer3,3274,7323,70360.7445.370.372.5
PubMed19,71744,33850030.8063.079.079.0
Planetoid citation graphs and the public-split test accuracy (%) reported by Kipf and Welling (2017) and Veličković et al. (2018). Edges and h as usually quoted

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 h=0.8h=0.8. Track fv=Fv,Bf_v=F_{v,B}, starting from f2=f3=f4=0f_2=f_3=f_4=0, with synchronous updates.

NodeNeighbourst = 1t = 2t = 3t = ∞ (exact)Prediction
21, 3000.0831/8 = 0.125A ✓
31, 2, 400.1670.1671/4 = 0.25A ✓
43, 50.50.50.5835/8 = 0.625B ✓
f = P(class B). Each step averages the neighbours' values from the previous step; nodes 1 and 5 stay clamped at 0 and 1

The exact values solve f2=(0+f3)/2f_2=(0+f_3)/2, f3=(0+f2+f4)/3f_3=(0+f_2+f_4)/3, f4=(f3+1)/2f_4=(f_3+1)/2. 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.

python
1import torch, torch.nn.functional as F
2import torch_geometric.transforms as T
3from torch_geometric.datasets import Planetoid
4from torch_geometric.nn import GCNConv
5from torch_geometric.nn.models import LabelPropagation
6from torch_geometric.utils import homophily
7
8data = Planetoid("data", "Cora", transform=T.NormalizeFeatures())[0] # public split
9print(int(data.train_mask.sum()), int(data.val_mask.sum()), int(data.test_mask.sum())) # 140 500 1000
10print(homophily(data.edge_index, data.y, method="edge")) # ~0.81
11
12acc = lambda pred, m: (pred[m] == data.y[m]).float().mean().item()
13lp = LabelPropagation(num_layers=50, alpha=0.9) # features unused
14print("label prop", acc(lp(data.y, data.edge_index, mask=data.train_mask).argmax(1), data.test_mask))
15
16class 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)
25
26model = 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.0
29for epoch in range(200):
30 model.train(); opt.zero_grad()
31 out = model(data.x, data.edge_index) # all 2,708 nodes, every step
32 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 test
38 best_val, test_at_best = v, acc(pred, data.test_mask)
39print("GCN", test_at_best) # about 0.81
Transductive Cora with PyTorch Geometric: masks, edge homophily, a label-propagation baseline and a 2-layer GCN chosen on validation accuracy (not run here; requires torch and torch_geometric)
AspectTransductiveInductive
Test nodes at training timepresent: features and edges used, labels hiddenabsent (new nodes or whole new graphs)
Typical benchmarksCora, Citeseer, PubMed, ogbn-arxivPPI, Reddit (time split)
What can be learnedalso per-node parameters (DeepWalk, node2vec)only a function of features and neighbourhood
Typical modelsGCN, GAT, label propagationGraphSAGE, GAT, GCN with sampling
Transductive versus inductive node classification

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 VLV_L, 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 (FU=(I−PUU)−1PULYLF_U=(I-P_{UU})^{-1}P_{UL}Y_L) uses only edges; on Cora it scores 68.0% against 81.5% for GCN and 83.0% for GAT.
  • ✓Edge homophily hh 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).
← back to Deep Learning roadmap