Chapter 13

Graph Convolutional Networks

MF learns embeddings from ratings alone; graph methods walk the interaction graph. GCNs merge the two — they learn user and item embeddings *on* the graph, where each node's embedding aggregates its neighbours' (message passing). Stack hops and an embedding absorbs information from items several hops away. LightGCN, the simplest effective GCN, is just weighted-mean aggregation with BPR — and the fact that it works so well is both the beauty and the warning of the approach.

Reading: ~62 min Interactive: 1 widgets Source: Polimi Recommender Systems 2024/25 — Graph Convolutional Networks · He, Deng, Wang, Li, Zhang & Wang, LightGCN (SIGIR 2020) · Shen, Wu, Zhang, Fu, Zhao, Zhang & Yang, How Powerful is Graph Convolution for Recommendation? GF-CF (CIKM 2021)

key

The big idea

Place embeddings on every node of the user–item graph. At each convolution hop, every node aggregates the embeddings of its neighbours and combines them with its own. After $h$ hops, each embedding incorporates information from its $h$ -hop neighbourhood. Predict $\hat r_{ui}=e_u^{(h)}\cdot e_i^{(h)}$ and back-propagate through the whole convolution stack. LightGCN strips away non-linearities and weight matrices, leaving only weighted-mean aggregation — the graph equivalent of a deep but linear model, and yet it outperforms most non-linear GCN variants on collaborative filtering.

01 · Embeddings on a graph

Graph convolution as message passing

Every node starts with a random embedding. At each hop, it aggregates its neighbours’ embeddings.

A GCN places a trainable embedding $e_u^{(0)}\in\mathbb{R}^K$ and $e_i^{(0)}\in\mathbb{R}^K$ on every user and item node. The core assumption — nodes close in the graph should have similar embeddings — is operationalised by the graph convolution (a.k.a. message passing):

Graph convolution

e_u^{(h)} = a\!\Big(e_u^{(h-1)};\;\lbrace e_i^{(h-1)} \mid (u,i)\in R^{+}\rbrace\Big),\qquad e_i^{(h)} = a\!\Big(e_i^{(h-1)};\;\lbrace e_u^{(h-1)} \mid (u,i)\in R^{+}\rbrace\Big).

At hop $h$ , a node’s new embedding is an aggregation function $a$ of its previous embedding (self-connection, optional) and its neighbours’ embeddings. This is exactly the random walk of Ch. 10 — but instead of propagating probability, we propagate learned vector representations. The simplest $a$ is the mean: a user’s embedding becomes the average of the items they rated, which is Asymmetric SVD (Ch. 8) expressed as a convolution — except here the item embeddings are learned, and through the convolution user embeddings depend on item embeddings depend on user embeddings, recursively.

key

Message passing is recursive

At hop 1 a user’s embedding absorbs the items they directly rated; at hop 2, the users who rated those items; at hop 3, items two hops away. Each convolution extends the receptive field by one hop — just like P³ in Ch. 10, but with learned rather than fixed weights.

02 · The simplest GCN that works

LightGCN

Weighted-mean aggregation, no self-connections, no non-linearities, BPR loss. That’s it.

LightGCN (He et al., 2020) is the minimal GCN for collaborative filtering. It removes activation functions, weight matrices, and self-loops, keeping only the weighted mean with symmetric degree normalisation:

LightGCN convolution

e_u^{(h)} = \sum_{i:(u,i)\in R^{+}} \frac{1}{\sqrt{d_u\,d_i}}\;e_i^{(h-1)},\qquad e_i^{(h)} = \sum_{u:(u,i)\in R^{+}} \frac{1}{\sqrt{d_u\,d_i}}\;e_u^{(h-1)}.

The factor $1/\sqrt{d_u d_i}$ is symmetric (same weight both directions) and dampens high-degree nodes. No self-connection means a node’s own previous embedding is excluded from its aggregation — which works better in practice for CF. In matrix form, with the normalised adjacency $\tilde G$ where $\tilde g_{xy}=g_{xy}/\sqrt{d_x d_y}$ :

LightGCN matrix form

E^{(h)} = \tilde G\,E^{(h-1)} = \tilde G^{\,h}\,E^{(0)},\qquad \hat r_{ui} = e_u^{(h)}\cdot e_i^{(h)}.

The key insight: the parameters live only at hop 0 — $E^{(0)}$ is the only thing learned. The convolution $\tilde G^{\,h}$ is a fixed, deterministic diffusion of those base embeddings across the graph. Prediction uses the aggregated context $e_u^{(h)},e_i^{(h)}$ at the final hop, not the raw latent factors.

MF (Ch. 8)

Predict

\hat r_{ui}=x_u\cdot y_i

from learned embeddings. No graph structure — each embedding is independent.

LightGCN

Predict

\hat r_{ui}=e_u^{(h)}\cdot e_i^{(h)}

from graph-propagated embeddings. The graph is baked into the prediction through repeated convolution.

Hands-on

LightGCN propagation · embeddings diffuse at each hop

Random initial embeddings E⁰ are diffused through the normalised adjacency G̃ for h hops: E^(h) = G̃^h·E⁰. Watch nodes that share neighbours converge — and push h higher to see every embedding align toward the dominant (popularity) direction.

Hops h3

Embeddings after 3 hop(s) — K=2

Node	e₀	e₁	‖e‖
Alice	-0.083	-0.167	0.187
Bob	-0.059	-0.173	0.183
Carla	-0.085	-0.184	0.202
Dan	-0.025	-0.154	0.156
Eva	-0.058	-0.170	0.180
Finn	-0.053	-0.188	0.195
TopGun	0.013	0.081	0.082
MI	0.004	0.093	0.093
Inter	-0.003	0.105	0.105
Martian	0.007	0.064	0.064
Notting	-0.016	0.097	0.099
LoveAct	-0.007	0.105	0.105
Aveng	0.004	0.093	0.093
LaLa	-0.016	0.097	0.099

Bob scores · r̂ = e_u·e_i (hop 3)

1Martian-0.011

2TopGun-0.015

3Notting-0.016

4LaLa-0.016

5MI-0.016

6Aveng-0.016

7LoveAct-0.018

8Inter-0.018

TakeawayOnly E⁰ would be learned in a real LightGCN — the diffusion G̃^h has no parameters. Because G̃ = VΣVᵀ, propagating h times applies Σ^h, amplifying the dominant (popularity) singular directions and washing out niche taste. That is why more hops drift toward Top-Popular.

03 · The training loop

Training a GCN for recommendation

Init random embeddings, convolve h times, draw a BPR sample, predict, back-propagate — repeat.

The LightGCN training loop has four steps per iteration:

Initialise $E^{(0)}$ — random embeddings for all nodes.
Convolve $h$ times: $E^{(h)} = \tilde G^{\,h}\,E^{(0)}$ .
Sample a BPR triple $(u,i,j)$ with $(u,i)\in R^{+}$ and $(u,j)\notin R^{+}$ .
Predict $\hat r_{ui}=e_u^{(h)}\cdot e_i^{(h)}$ and $\hat r_{uj}=e_u^{(h)}\cdot e_j^{(h)}$ , and apply the BPR gradient to $E^{(0)}$ .

The gradient flows through the entire convolution stack back to $E^{(0)}$ . The loss is computed on the post-convolution embeddings $E^{(h)}$ , but the only parameters are the initial embeddings $E^{(0)}$ — the convolution $\tilde G^{\,h}$ has no learnable parameters. So training only decides which initial vectors, once diffused $h$ times through the graph, give good predictions.

key

Is it deep?

The lecture openly questions it. LightGCN has many hops ( $h=4,5$ ) but no non-linearities and no learned weights between them — it is essentially a linear diffusion plus a dot product, “a structure on which more complex methods can be built” rather than a deep model in the sense of Ch. 11.

04 · The price of convolution

Computational cost

GCN predictions are orders of magnitude more expensive than MF or item-CF.

The convolution $E^{(h)} = \tilde G\,E^{(h-1)}$ is one sparse matrix multiplication per hop, costing $O(\lvert R\rvert\,K)$ where $\lvert R\rvert$ is the number of edges (observed ratings) and $K$ the embedding size — $O(h\,\lvert U\rvert\lvert I\rvert\,K)$ over $h$ hops. Compare the cost of predicting a single $(u,i)$ pair:

Funk SVD / SVD++: $O(K)$ — one dot product.
Item-based KNN: $O(\lvert I\rvert^2)$ precomputation, then $O(\lvert I_{\text{rated}}\rvert)$ per prediction.
GCN (LightGCN): $O(h\,\lvert U\rvert\lvert I\rvert\,K) + O(K)$ — the convolution dominates, and it must be re-run whenever $E^{(0)}$ changes.

The cost is in the convolution, not the dot product

Every time a batch of BPR samples is drawn, the full $h$ -hop convolution must re-run, because $E^{(0)}$ was updated by the previous gradient step. For large catalogues this forces small batches or impractical training times. The slides show GCN prediction as $O(h\,\lvert U\rvert\lvert I\rvert\,K)$ versus $O(K)$ for MF.

05 · The singular-value amplifier

Popularity bias in GCN

Repeated convolution amplifies the dominant singular values of the adjacency — which encode popularity.

Using the SVD of the normalised adjacency $\tilde G = V\Sigma V^\top$ , the $h$ -hop convolution becomes:

GCN SVD form

E^{(h)} = \tilde G^{\,h}\,E^{(0)} = \big(V\Sigma V^\top\big)^h\,E^{(0)} = V\,\Sigma^{\,h}\,V^\top\,E^{(0)}.

Each convolution raises the singular values to the power $h$ — a spectral amplifier. Large singular values (the “easy”, strongly popularity-based signals) are amplified; small singular values (fine-grained, niche taste) are attenuated toward zero. This is the same oversmoothing we saw with random walks in Ch. 10, now stated spectrally: more hops focus the model on the dominant eigenstructure — which is popularity, because popular items have high degree and thus large singular values. GCNs drift toward Top-Popular as $h$ grows.

key

The fix: filter functions

Instead of $\Sigma^{\,h}$ , apply a filter function $f(\Sigma)$ that can attenuate low frequencies (popularity) and amplify high frequencies (niche). A high-pass filter suppresses the dominant singular values; a band-pass keeps the middle range. This turns the convolution from a pure random walk into a tuned spectral propagation.

06 · Graph filters meet item-CF

Graph-Filter Collaborative Filtering

Take the spectral insight from GCN, skip the iterative training, and build a fast item-based CF model.

GF-CF (Shen et al., 2021) asks: rather than training an iterative GCN with filter functions, can we compute the item–item similarity directly with spectral filtering? Yes:

Normalise the URM: $\hat r_{ui} = r_{ui}/\sqrt{d_u d_i}$ — the same normalisation as LightGCN.
Truncated SVD: $\tilde R \simeq U_K\,\Sigma_K\,V_K^\top$ — keep the top- $K$ singular values/vectors, as in PureSVD (Ch. 8).
Compute similarity: $S = (\tilde R^\top \tilde R + \alpha D_I)^{-1/2}\,V_K\,V_K^\top\,D_I^{1/2}$ .

GF-CF applies the spectral-filtering idea analytically — no gradient descent, no per-batch convolution. The catch: $S$ is dense, so $O(\lvert I\rvert^2)$ storage and slow prediction (like EASE-R in Ch. 11), and KNN is awkward because many neighbours are non-zero.

Advantages

Fast (analytic SVD, no training loop). Very effective. Flexible — the degree-matrix exponents are tunable.

Disadvantages

Dense similarity matrix (high memory, slow prediction). KNN sparsification is hard — too many non-zero neighbours.

07 · Exam intel

What the exam tests

Write the graph-convolution update $e_u^{(h)}=a(e_u^{(h-1)};\lbrace e_i^{(h-1)}\rbrace)$ ; explain LightGCN’s weighted mean with $1/\sqrt{d_u d_i}$ ; describe the training loop (init → convolve → BPR → dot-product predict → gradient on $E^{(0)}$ ); compare GCN cost $O(h\lvert U\rvert\lvert I\rvert K)$ with MF’s $O(K)$ ; explain why $\Sigma^h$ amplifies popularity; and describe GF-CF as an analytical spectral item-CF.

Worked question — where do the parameters live?

LightGCN uses weighted-mean aggregation with $1/\sqrt{d_u d_i}$ and no self-connections. (a) Write the update for $e_u^{(h)}$ . (b) Why is the normalisation symmetric? (c) After training, predicting $\hat r_{ui}$ — where do the learned parameters live, in the convolution or in $E^{(0)}$ ? (d) One disadvantage vs Funk SVD?

(a) $e_u^{(h)} = \sum_{i:(u,i)\in R^{+}} \tfrac{1}{\sqrt{d_u d_i}}\,e_i^{(h-1)}$ .
(b) Symmetric normalisation weights user→item and item→user edges equally and dampens high-degree users and items alike; empirically it beats asymmetric alternatives.
(c) Only in $E^{(0)}$ . The convolution $\tilde G$ has no learnable parameters — it is fixed by the graph. The gradient back-propagates through $\tilde G^{\,h}$ to update the initial embeddings.
(d) Cost: $O(h\lvert U\rvert\lvert I\rvert K)$ per batch vs $O(K)$ for Funk SVD — plus the $\Sigma^h$ popularity bias.

Traps: thinking each hop learns its own embeddings (only $E^{(0)}$ is learned; $E^{(h)}$ is derived); confusing message passing (vectors) with random walks (scalars); forgetting LightGCN deliberately drops the self-connection; and treating GF-CF as plain item-CF (it uses spectral filtering on the normalised URM).

08 · Exam · past papers

Past-paper questions

Past paper FT-Feb26 · GCN idea, LightGCN aggregation, training (~6 pts)

Q. Describe the main idea of GCNs and the role of nodes and edges in recommendation; the aggregation mechanism of LightGCN; how LightGCN is trained, including the objective.

Model answer. Idea, nodes & edges. A GCN learns node embeddings by repeatedly aggregating information from graph neighbours (message passing). On the bipartite graph the nodes are users and items and the edges are observed interactions, so a $k$ -layer GCN lets an embedding absorb its $k$ -hop neighbourhood. LightGCN aggregation. It drops the feature-transform matrices and non-linear activations of a standard GCN, keeping only symmetric-normalised neighbour averaging, $e_u^{(k+1)}=\sum_{i\in N(u)}\tfrac{1}{\sqrt{\lvert N(u)\rvert\,\lvert N(i)\rvert}}\,e_i^{(k)}$ (symmetrically for items), and combines layers as $e_u=\sum_k \alpha_k e_u^{(k)}$ . Training. Only the layer-0 embeddings are parameters, learned by minimising the BPR loss $-\sum_{(u,i,j)}\ln\sigma(e_u\cdot e_i - e_u\cdot e_j)+\lambda\lVert E^{(0)}\rVert^2$ , with score $\hat r_{ui}=e_u\cdot e_i$ .

Past paper Practice Exam 2 · Message passing, averaging, prediction (5 pts)

Q. The concept of message passing in GCNs (2); how LightGCN performs message passing with simple average aggregation (1); how predictions are computed from LightGCN embeddings (2).

Model answer. Message passing. At each layer every node receives its neighbours’ current embeddings and aggregates them into its new embedding; after $k$ layers a node integrates its $k$ -hop neighbourhood. LightGCN aggregation. Pure symmetric-normalised averaging with no weight matrix or non-linearity, $e_u^{(k+1)}=\sum_{i\in N(u)}\tfrac{1}{\sqrt{\lvert N(u)\rvert\,\lvert N(i)\rvert}}\,e_i^{(k)}$ . Prediction. Combine the per-layer embeddings $e_u=\sum_k\alpha_k e_u^{(k)}$ , $e_i=\sum_k\alpha_k e_i^{(k)}$ , then score by dot product $\hat r_{ui}=e_u\cdot e_i$ and rank.

09 · Self-check

Three questions before you move on

In LightGCN, which parameters are learned and what is fixed?

Why does repeated graph convolution amplify popularity bias?

Why is a GCN's prediction cost O(h|U||I|K) much higher than Funk SVD's O(K)?

10 · Recap

One-screen summary

Chapter 13 — load-bearing ideas

Convolution = neighbourhood aggregation: $e_u^{(h)}=a(e_u^{(h-1)};\lbrace e_i^{(h-1)}\rbrace)$ . LightGCN uses the weighted mean $\sum_i \tfrac{1}{\sqrt{d_u d_i}}\,e_i^{(h-1)}$ — no self-connection, no non-linearity.
Only $E^{(0)}$ is learned: $E^{(h)}=\tilde G^{\,h}E^{(0)}$ with $\tilde G$ fixed; predict $\hat r_{ui}=e_u^{(h)}\cdot e_i^{(h)}$ and train with BPR.
Cost and bias: $O(h\lvert U\rvert\lvert I\rvert K)$ per batch vs $O(K)$ for MF; the $\Sigma^h$ amplification pushes toward popularity and attenuates niche signals.
GF-CF: truncated SVD on the normalised URM + spectral filtering gives an analytic item–item similarity — fast, but dense and hard to KNN-sparsify.