Graph representation learning

Learning vectors for nodes, edges or graphs: shallow lookup tables trained on random walks (DeepWalk, node2vec), then message-passing GNNs that compute each vector from its neighbours, bounded by the 1-WL test.

8 min read946 wordscore0 viewsupdated 2026-10-21

Definition

Graph representation learning learns a map from the nodes, edges or whole graphs of G=(V,E)G=(V,E) to vectors in Rd\mathbb{R}^d, so that structure (who is connected to whom, and with what features) becomes geometry that a downstream model can use. Hamilton, Ying and Leskovec framed it as an encoder–decoder problem in "Representation Learning on Graphs: Methods and Applications" (IEEE Data Engineering Bulletin, 2017); Hamilton's book Graph Representation Learning (2020) covers the field.

The input is an adjacency matrix A∈{0,1}n×nA\in\{0,1\}^{n\times n} and, often, a feature matrix X∈Rn×fX\in\mathbb{R}^{n\times f}. The output is one of three things: a label per node (the topic of a paper in a citation graph), a score per node pair (will these two proteins interact?), or a label per graph (is this molecule toxic?).

Graphs resist ordinary networks. There is no grid, so there is no fixed neighbourhood to slide a convolution over. Degrees vary from 1 to thousands. Graphs differ in size. Most important, node order is arbitrary: the same graph can be written with any of n!n! orderings. A model must give the same answer for all of them.

f(PAP⊤, PX)=P f(A,X),g(PAP⊤, PX)=g(A,X)for every permutation matrix Pf(PAP^\top,\,PX)=P\,f(A,X),\qquad g(PAP^\top,\,PX)=g(A,X)\quad\text{for every permutation matrix }P
ff
a node-level encoder: permuting the input nodes permutes the output rows the same way (equivariance)
gg
a graph-level model: its output does not change at all (invariance)

An MLP applied to the flattened AA fails both tests. Earlier methods sidestepped the problem. Spectral clustering and Laplacian eigenmaps (Belkin and Niyogi, 2003) embed nodes with eigenvectors of the graph Laplacian. Graph kernels such as the Weisfeiler–Lehman subtree kernel (Shervashidze et al., 2011) compare graphs by counting substructures. Both give fixed features rather than learned ones.

Two families

Embed node v: look it up (shallow) or compute it from its neighbours (GNN)shallow: DeepWalk / node2vecabcdefrandom walk: a → b → d → e → cskip-gram, window 1: (a,b) (b,d) (d,e) (e,c)abcdefZ ∈ ℝ^(n × d), z_v = Z[v]n·d free parametersno node features usednew node → no row (transductive)message passing: GCN / GraphSAGE / GATabcacdabeh(2)h(1)xh_v(k) = UPDATE(h_v(k−1),AGG{h_u(k−1) : u ∈ N(v)})2 layers = 2-hop receptive fieldshared weights, uses X → inductivenode levelŷ_v = softmax(W h_v)e.g. Cora: 7 topics per paperedge levels(u,v) = σ(h_u · h_v)link prediction, KG completiongraph levelh_G = Σ_v h_v (readout)e.g. molecule → property
fig.The two families on one six-node graph. Left: a shallow method samples random walks, turns them into (centre, context) pairs and trains a lookup table Z with one free row per node. Right: a two-layer message-passing GNN computes node a from its neighbours b and c, which were computed from their own neighbours; the same weights serve every node. Bottom: the vectors feed node-, edge- or graph-level heads.

Shallow embeddings make the encoder a table: zv=Z[v]z_v=Z[v] with Z∈Rn×dZ\in\mathbb{R}^{n\times d}. The decoder says that nodes which co-occur on short random walks should have a large dot product. DeepWalk (Perozzi, Al-Rfou and Skiena, KDD 2014) runs uniform truncated walks and treats them as sentences for the skip-gram model of Word2Vec. node2vec (Grover and Leskovec, KDD 2016) biases the walk with a return parameter pp and an in–out parameter qq, moving between breadth-first and depth-first exploration. LINE (Tang et al., WWW 2015) fits first- and second-order proximity directly.

L=− ⁣ ⁣∑(u,v)∈D[log⁡σ(zu⊤zv)+∑k=1Klog⁡σ(−zu⊤znk)],αpq(t,x)={1/pdtx=01dtx=11/qdtx=2\mathcal{L}=-\!\!\sum_{(u,v)\in\mathcal{D}}\Big[\log\sigma(z_u^\top z_v)+\sum_{k=1}^{K}\log\sigma(-z_u^\top z_{n_k})\Big],\qquad \alpha_{pq}(t,x)=\begin{cases}1/p & d_{tx}=0\\ 1 & d_{tx}=1\\ 1/q & d_{tx}=2\end{cases}
D\mathcal{D}
(centre, context) pairs within a window on the sampled walks
nkn_k
KK negative nodes drawn from a noise distribution
αpq(t,x)\alpha_{pq}(t,x)
node2vec's unnormalised weight for stepping to xx after arriving at vv from tt; dtxd_{tx} is the hop distance from tt to xx

Qiu et al. (WSDM 2018, NetMF) showed that DeepWalk with negative sampling implicitly factorises a log-transformed matrix of random-walk co-occurrences, so these methods are close cousins of spectral embeddings. Their weaknesses follow from the lookup table: n⋅dn\cdot d parameters (346,624 for Cora at d=128d=128), no use of node features, and no vector for a node that appears after training.

Message passing makes the encoder a function of the neighbourhood. Each layer updates every node from its own state and an aggregate of its neighbours' states. Gilmer et al. (ICML 2017) named the general form; the Graph Convolutional Network (GCN), GraphSAGE and the Graph Attention Network (GAT) are instances. The idea goes back to the graph neural network model of Scarselli et al. (IEEE TNN, 2009).

hv(k)=ϕ(hv(k−1), ⨁u∈N(v)ψ(hv(k−1),hu(k−1),euv)),GCN: H(k)=σ(A^ H(k−1)W(k))h_v^{(k)}=\phi\Big(h_v^{(k-1)},\ \bigoplus_{u\in\mathcal{N}(v)}\psi\big(h_v^{(k-1)},h_u^{(k-1)},e_{uv}\big)\Big),\qquad \text{GCN: } H^{(k)}=\sigma\big(\hat A\,H^{(k-1)}W^{(k)}\big)
hv(0)=xvh_v^{(0)}=x_v
the input features of node vv
⨁\bigoplus
a permutation-invariant aggregator: sum, mean, max or attention-weighted sum
ψ, ϕ\psi,\ \phi
message and update functions, shared by all nodes; this sharing makes the model equivariant and inductive
A^\hat A
D~−1/2(A+I)D~−1/2\tilde D^{-1/2}(A+I)\tilde D^{-1/2}, the symmetric-normalised adjacency with self-loops

After kk layers, hvh_v depends on exactly the kk-hop neighbourhood of vv. The parameter count depends on the feature sizes, not on nn. A trained model therefore applies to unseen nodes and to entirely new graphs.

Standard settings and results

DeepWalk
80 walks per node, length 40, window 10, d = 128 (Perozzi et al., 2014)
node2vec
10 walks per node, length 80, context 10, d = 128; p and q tuned by grid search (Grover and Leskovec, 2016)
Cora
2,708 papers, 5,429 citation links, 1,433 bag-of-words features, 7 classes; 140 training labels (5.2%)
Citeseer / PubMed
3,327 nodes, 4,732 edges, 6 classes / 19,717 nodes, 44,338 edges, 3 classes
Shallow vs GNN
test accuracy on Citeseer / Cora / PubMed: DeepWalk 43.2 / 67.2 / 65.3%, GCN 70.3 / 81.5 / 79.0% (Kipf and Welling, ICLR 2017)

The gap in the last row is mostly about features. DeepWalk sees only the links; GCN also sees each paper's words and propagates them along the links.

Over-smoothing

Each GCN layer is a step of Laplacian smoothing (Li, Han and Wu, AAAI 2018). A few steps average away noise inside a community. Many steps converge to the leading eigenvector of A^\hat A, which is proportional to d~v\sqrt{\tilde d_v}: every node's representation then depends only on its degree, whatever its class. This is why most GCNs use two or three layers, and why deeper models add residual connections, normalisation or jumping-knowledge readouts.

H(k) = Â^k X, Â = D̃^(−1/2)(A + I)D̃^(−1/2) · 24 nodes, p_in = 0.4, p_out = 0.05graph: ring = community, fill = sign/size of feature 1community 0community 159 edges, 6 between communities (rose)features after 2 rounds (scale ±0.87)+ = class centroids; x carries the ±0.7 signalnearest-centroid accuracy 100.0%separation 5.32separation = gap between centroids /mean distance to own centroid; no weights learned
fig.Weight-free message passing, H = Â^k X, on a 24-node graph with two communities (p_in = 0.4). Features are 2-D, with ±0.7 class signal on the first coordinate and unit noise. Default (p_out = 0.05: 59 edges, 6 between communities; k = 2): nearest-centroid accuracy goes from 70.8% at k = 0 to 100%, and the separation from 1.30 to 5.32. It peaks at 7.63 at k = 5, accuracy stays at 100% up to k = 12, falls to 87.5% at k = 16 and reaches 50.0% from k = 39. At p_out = 0.20 (30 of 83 edges cross) the best is 79.2% at k = 1. At p_out = 0 the components never mix and accuracy stays 100%.
NodeDegreexh(1)h(2)h(3)h(6)
a21(1+1+1)/3 = 1(1+0.5+0.5)/3 = 0.6670.4720.163
b, c31(1+1+1−1)/4 = 0.5(1+0.5+0.5−0.5)/4 = 0.3750.2600.090
d, e3−1−0.5−0.375−0.260−0.090
f2−1−1−0.667−0.472−0.163
variance10.50.2420.1200.014
Worked example: mean aggregation over the closed neighbourhood, h(k)_v = mean of h(k−1) over {v} ∪ N(v), on the diagram's graph (edges ab, ac, bc, bd, ce, de, df, ef) with x = +1 on {a, b, c} and −1 on {d, e, f}

The two bridge edges b–d and c–e leak signal across the cut. The sign survives, but the variance halves at each round, and in the limit every node takes the degree-weighted mean, here 0. One round already blurred the boundary nodes b, c, d and e the most.

How expressive is message passing?

The 1-dimensional Weisfeiler–Lehman (1-WL) test colours all nodes alike and then repeatedly recolours each node by its own colour plus the multiset of its neighbours' colours. Xu et al. (ICLR 2019) and Morris et al. (AAAI 2019) proved that no message-passing GNN distinguishes two graphs that 1-WL cannot. A GNN reaches the bound when its aggregator is injective on multisets, as sum is and mean and max are not; this is the design of the Graph Isomorphism Network (GIN).

The classic failure: a 6-cycle and two disjoint triangles. Every node has degree 2 with two degree-2 neighbours, so after any number of rounds both graphs have six nodes of one colour, and a GNN with featureless nodes maps them to the same vector. It cannot count the triangles. Graph transformers add positional encodings, and higher-order GNNs pass messages between tuples of nodes, to get past this limit.

python
1import numpy as np
2
3def random_walks(adj, walks_per_node=10, length=20, seed=0):
4 """Uniform truncated random walks, as in DeepWalk."""
5 rng = np.random.default_rng(seed)
6 walks = []
7 for _ in range(walks_per_node):
8 for start in rng.permutation(len(adj)):
9 w = [start]
10 for _ in range(length - 1):
11 w.append(rng.choice(adj[w[-1]]))
12 walks.append(w)
13 return walks
14
15def walk_embeddings(adj, dim=16, window=5, neg=1.0):
16 """Skip-gram with negative sampling ≈ factorising a shifted PMI matrix (Levy & Goldberg, 2014)."""
17 n = len(adj)
18 C = np.zeros((n, n))
19 for w in random_walks(adj):
20 for i, u in enumerate(w):
21 for v in w[max(0, i - window):i] + w[i + 1:i + 1 + window]:
22 C[u, v] += 1
23 pmi = np.log(C * C.sum() / np.outer(C.sum(1), C.sum(0)) + 1e-12) - np.log(neg)
24 U, S, _ = np.linalg.svd(np.maximum(pmi, 0)) # positive PMI, truncated SVD
25 return U[:, :dim] * np.sqrt(S[:dim])
26
27# two communities of 50 nodes: p_in = 0.1, p_out = 0.01
28rng = np.random.default_rng(1)
29y = np.repeat([0, 1], 50)
30P = np.where(y[:, None] == y[None, :], 0.1, 0.01)
31A = np.triu(rng.random((100, 100)) < P, 1)
32A = A | A.T
33adj = [np.flatnonzero(row) for row in A]
34assert all(len(a) for a in adj)
35
36Z = walk_embeddings(adj, dim=4)
37train = np.r_[0:5, 50:55] # 5 labelled nodes per class
38cent = np.stack([Z[train[y[train] == c]].mean(0) for c in (0, 1)])
39pred = np.argmin(((Z[:, None] - cent[None]) ** 2).sum(-1), 1)
40print(Z.shape, (pred == y).mean()) # (100, 4) 0.99
DeepWalk in closed form: random walks → window co-occurrences → positive PMI → truncated SVD (numpy, runs as is; prints (100, 4) 0.99)

Use when

  • +Shallow embeddings need only the edge list, scale to huge graphs with sampled walks, and give general-purpose vectors.
  • +Message passing uses node and edge features, is permutation-equivariant by construction, and generalises to unseen nodes and graphs.
  • +One message-passing template covers node, edge and graph tasks; only the head changes.

Avoid when

  • −Shallow embeddings are transductive: a new node needs retraining, and n⋅dn\cdot d parameters grow with the graph.
  • −Message passing over-smooths with depth and is at most as powerful as 1-WL.
  • −Neighbourhoods grow exponentially with depth, so full-batch training on large graphs needs sampling or clustering.

Check yourself

Why can DeepWalk not embed a node that joins the graph after training?

Check yourself

A message-passing GNN on featureless nodes is given a 6-cycle and two disjoint triangles. What happens?

Remember

  • ✓Goal: vectors for nodes, edges or graphs; models must be permutation-equivariant (node level) or invariant (graph level).
  • ✓Shallow embeddings (DeepWalk, node2vec, LINE): a lookup table trained so that random-walk co-occurrence means a large zu⊤zvz_u^\top z_v; transductive, featureless, n⋅dn\cdot d parameters.
  • ✓Message passing: hv(k)=ϕ(hv,⨁u∈N(v)ψ(hv,hu))h_v^{(k)}=\phi(h_v,\bigoplus_{u\in\mathcal{N}(v)}\psi(h_v,h_u)) with shared weights; kk layers see the kk-hop neighbourhood and transfer to new graphs.
  • ✓On Cora, GCN reaches 81.5% against DeepWalk's 67.2%, mostly because it uses the node features.
  • ✓Repeated averaging over-smooths: representations converge to a degree-only vector, so typical GNNs are 2–3 layers deep.
  • ✓Message-passing GNNs are at most as discriminative as the 1-WL test; sum aggregation (GIN) attains the bound.
← back to Deep Learning roadmap