Definition
Graph representation learning learns a map from the nodes, edges or whole graphs of to vectors in , 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 and, often, a feature matrix . 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 orderings. A model must give the same answer for all of them.
- a node-level encoder: permuting the input nodes permutes the output rows the same way (equivariance)
- a graph-level model: its output does not change at all (invariance)
An MLP applied to the flattened 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
Shallow embeddings make the encoder a table: with . 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 and an in–out parameter , moving between breadth-first and depth-first exploration. LINE (Tang et al., WWW 2015) fits first- and second-order proximity directly.
- (centre, context) pairs within a window on the sampled walks
- negative nodes drawn from a noise distribution
- node2vec's unnormalised weight for stepping to after arriving at from ; is the hop distance from to
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: parameters (346,624 for Cora at ), 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).
- the input features of node
- a permutation-invariant aggregator: sum, mean, max or attention-weighted sum
- message and update functions, shared by all nodes; this sharing makes the model equivariant and inductive
- , the symmetric-normalised adjacency with self-loops
After layers, depends on exactly the -hop neighbourhood of . The parameter count depends on the feature sizes, not on . 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 , which is proportional to : 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.
| Node | Degree | x | h(1) | h(2) | h(3) | h(6) |
|---|---|---|---|---|---|---|
| a | 2 | 1 | (1+1+1)/3 = 1 | (1+0.5+0.5)/3 = 0.667 | 0.472 | 0.163 |
| b, c | 3 | 1 | (1+1+1−1)/4 = 0.5 | (1+0.5+0.5−0.5)/4 = 0.375 | 0.260 | 0.090 |
| d, e | 3 | −1 | −0.5 | −0.375 | −0.260 | −0.090 |
| f | 2 | −1 | −1 | −0.667 | −0.472 | −0.163 |
| variance | 1 | 0.5 | 0.242 | 0.120 | 0.014 |
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.
1import numpy as np23def 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 walks1415def 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] += 123 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 SVD25 return U[:, :dim] * np.sqrt(S[:dim])2627# two communities of 50 nodes: p_in = 0.1, p_out = 0.0128rng = 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.T33adj = [np.flatnonzero(row) for row in A]34assert all(len(a) for a in adj)3536Z = walk_embeddings(adj, dim=4)37train = np.r_[0:5, 50:55] # 5 labelled nodes per class38cent = 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.99Use 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 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 ; transductive, featureless, parameters.
- ✓Message passing: with shared weights; layers see the -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.