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

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

**Graph representation learning:** learns a map from the nodes, edges or whole graphs of $G=(V,E)$ to vectors in $\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\in\{0,1\}^{n\times n}$ and, often, a feature matrix $X\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!$ orderings. A model must give the same answer for all of them.

$$
f(PAP^\top,\,PX)=P\,f(A,X),\qquad g(PAP^\top,\,PX)=g(A,X)\quad\text{for every permutation matrix }P
$$

- $f$: a node-level encoder: permuting the input nodes permutes the output rows the same way (equivariance)
- $g$: a graph-level model: its output does not change at all (invariance)

An MLP applied to the flattened $A$ 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

> Figure: 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: $z_v=Z[v]$ with $Z\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 $p$ and an in–out parameter $q$, moving between breadth-first and depth-first exploration. LINE (Tang et al., WWW 2015) fits first- and second-order proximity directly.

$$
\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}
$$

- $\mathcal{D}$: (centre, context) pairs within a window on the sampled walks
- $n_k$: $K$ negative nodes drawn from a noise distribution
- $\alpha_{pq}(t,x)$: node2vec's unnormalised weight for stepping to $x$ after arriving at $v$ from $t$; $d_{tx}$ is the hop distance from $t$ to $x$

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\cdot d$ parameters (346,624 for Cora at $d=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).

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

- $h_v^{(0)}=x_v$: the input features of node $v$
- $\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
- $\hat A$: $\tilde D^{-1/2}(A+I)\tilde D^{-1/2}$, the symmetric-normalised adjacency with self-loops

After $k$ layers, $h_v$ depends on exactly the $k$-hop neighbourhood of $v$. The parameter count depends on the feature sizes, not on $n$. 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 $\hat A$, which is proportional to $\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.

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

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}

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

```python
import numpy as np

def random_walks(adj, walks_per_node=10, length=20, seed=0):
    """Uniform truncated random walks, as in DeepWalk."""
    rng = np.random.default_rng(seed)
    walks = []
    for _ in range(walks_per_node):
        for start in rng.permutation(len(adj)):
            w = [start]
            for _ in range(length - 1):
                w.append(rng.choice(adj[w[-1]]))
            walks.append(w)
    return walks

def walk_embeddings(adj, dim=16, window=5, neg=1.0):
    """Skip-gram with negative sampling ≈ factorising a shifted PMI matrix (Levy & Goldberg, 2014)."""
    n = len(adj)
    C = np.zeros((n, n))
    for w in random_walks(adj):
        for i, u in enumerate(w):
            for v in w[max(0, i - window):i] + w[i + 1:i + 1 + window]:
                C[u, v] += 1
    pmi = np.log(C * C.sum() / np.outer(C.sum(1), C.sum(0)) + 1e-12) - np.log(neg)
    U, S, _ = np.linalg.svd(np.maximum(pmi, 0))          # positive PMI, truncated SVD
    return U[:, :dim] * np.sqrt(S[:dim])

# two communities of 50 nodes: p_in = 0.1, p_out = 0.01
rng = np.random.default_rng(1)
y = np.repeat([0, 1], 50)
P = np.where(y[:, None] == y[None, :], 0.1, 0.01)
A = np.triu(rng.random((100, 100)) < P, 1)
A = A | A.T
adj = [np.flatnonzero(row) for row in A]
assert all(len(a) for a in adj)

Z = walk_embeddings(adj, dim=4)
train = np.r_[0:5, 50:55]                                  # 5 labelled nodes per class
cent = np.stack([Z[train[y[train] == c]].mean(0) for c in (0, 1)])
pred = np.argmin(((Z[:, None] - cent[None]) ** 2).sum(-1), 1)
print(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)

**Strengths**

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

**Limitations**

- Shallow embeddings are transductive: a new node needs retraining, and $n\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.

> **Homophily is an assumption:** Neighbourhood averaging helps when linked nodes tend to share labels, as in citation graphs. On heterophilous graphs (fraud rings, some web graphs, bipartite structures) averaging mixes opposite classes and can do worse than an MLP on the features alone. Raise $p_{\text{out}}$ in the figure to 0.2: the best accuracy over all $k$ is 79.2%, little above the 70.8% of the raw features.

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

- A. Its random walks never reach new nodes
- B. Its encoder is a lookup table with one free row per training node, so a new node has no parameters
- C. Skip-gram requires a fixed vocabulary of features
- D. It needs the graph Laplacian, which changes

**Answer:** B. Its encoder is a lookup table with one free row per training node, so a new node has no parameters — The encoder is $z_v=Z[v]$. Nothing maps a node's features or neighbourhood to a vector, so a new node needs new walks and further optimisation. A message-passing encoder computes $h_v$ from features and neighbours with shared weights, so it is inductive.

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

- A. It separates them after two layers
- B. It separates them only with max aggregation
- C. It gives both the same graph embedding, because 1-WL cannot tell them apart
- D. It separates them if the readout is a sum

**Answer:** C. It gives both the same graph embedding, because 1-WL cannot tell them apart — Every node in both graphs has degree 2 and two degree-2 neighbours, so 1-WL colour refinement stays uniform and the colour histograms match. Message passing is bounded by 1-WL whatever the aggregator or readout.

**Key points**

- 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 $z_u^\top z_v$; transductive, featureless, $n\cdot d$ parameters.
- Message passing: $h_v^{(k)}=\phi(h_v,\bigoplus_{u\in\mathcal{N}(v)}\psi(h_v,h_u))$ with shared weights; $k$ layers see the $k$-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.

---

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