Chapter 10

Graph-Based Recommenders

Every recommender so far worked on matrices. A graph-based recommender redraws the problem: users and items become nodes, ratings become edges, and a recommendation is a random walk — start at a user, follow edges to items, to users, back to items, and rank where you land. The famous P³ method does this in three hops and reveals that item-based CF is a degree-normalised walk.

Reading: ~65 min Interactive: 1 widgets Source: Polimi Recommender Systems 2024/25 — Graph-Based Recommenders · Cooper, Lee, Radzik & Siantos, Random Walks in Recommender Systems (WWW 2014) · Paudel, Christoffel, Newell & Bernstein, Updatable, Accurate, Diverse, and Scalable Recommendations (ACM TIST 2017)

key

The big idea

Represent the collaborative data as a bipartite graph — users on one side, items on the other, an edge wherever a rating exists. A recommendation is the probability of landing on each item after a random walk that starts at the target user. Walk three hops (P³) and the item scores become $\Pi_I^{(3)} = \Pi_U^{(0)}\,P_{UI}\,P_{IU}\,P_{UI}$ , which simplifies to $\hat r_{ui} = \sum_j r_{uj}\,S_{ji}$ with $\hat R = R\,S$ — the familiar item-based CF form.

01 · Users + items = nodes

Graph representation of the URM

The rating matrix isn’t a table — it’s a bipartite graph. Drawing it that way unlocks random walks.

A graph $G=(N,E)$ is a set of nodes $N$ and edges $E$ . For collaborative filtering, nodes are users $U$ and items $I$ ; an edge $(u,i)\in E$ exists wherever the URM has a non-zero rating. This is a bipartite graph — two disjoint sets, edges only across — with $\lvert U\rvert+\lvert I\rvert$ nodes and as many edges as observed ratings.

Add item attributes (the ICM, Ch. 4) and you get a tripartite graph: $N=U\cup I\cup A$ , with edges $(u,i)$ from ratings and $(i,a)$ from content. This fuses collaborative and content signals into one graph — hybridisation by design (Ch. 9). The graph is written as an adjacency matrix $G\in\mathbb{R}^{\lvert N\rvert\times\lvert N\rvert}$ with $g_{xy}=1$ if edge $(x,y)$ exists. Ordering the nodes as [Users, Items] gives a clean block structure:

Adjacency matrix (collaborative)

G = \begin{bmatrix} 0 & R \\ R^\top & 0 \end{bmatrix},\qquad R\in\mathbb{R}^{U\times I},\;\; G\in\mathbb{R}^{(U+I)\times(U+I)}.

The graph is undirected — an edge means a rating, not a direction — but the transition matrix we build next is directional, because we normalise each row independently.

key

Same data, new lens

$G$ is just the URM stacked into a bigger matrix. The off-diagonal block structure forces every two-hop walk $U\to I\to U$ to land on a user, and every three-hop walk $U\to I\to U\to I$ to land on an item — which is exactly why P³ works: the $U\to I\to U\to I$ meta-path connects a user to items they haven’t rated, through users who share their taste.

02 · Walk the graph

Random walks and state probability

Start at a user, follow edges at random, and count how often you land on each item.

The core mechanism is a transition probability $p_{xy}$ — the chance of stepping from node $x$ to node $y$ in one hop. For an unweighted graph it is simply $p_{xy}=g_{xy}/d_x$ , where $d_x=\sum_y g_{xy}$ is the degree of node $x$ : every neighbour is equally likely. Collecting these into the block transition matrix:

Transition matrix (block form)

P = \begin{bmatrix} 0 & P_{UI} \\ P_{IU} & 0 \end{bmatrix},\qquad P_{UI} = \operatorname{diag}\!\Big(\tfrac{1}{d_u}\Big)R,\;\; P_{IU} = \operatorname{diag}\!\Big(\tfrac{1}{d_i}\Big)R^\top.

A state probability vector $\Pi\in\mathbb{R}^{\lvert N\rvert}$ tracks where the walker is. Start at user $u$ with $\Pi^{(0)}$ one-hot at $u$ ; each hop updates $\Pi^{(h)} = \Pi^{(h-1)}\,P$ , a distribution that always sums to 1. After $h$ hops, $\Pi^{(h)}_k$ is the probability of being at node $k$ . To recommend, read off the item nodes and rank them highest-first.

Hands-on

Random walk on the bipartite URM graph

Start at a user and take h degree-normalised hops. Hop 0 sits on the start user; hop 1 spreads evenly over their rated items; hop 2 re-focuses on users who share those items; hop 3 lands on candidate items. The ranking is the P³ recommendation — odd hops reach items, even hops do not.

Hops3

Item state probability at hop 3

1MI0.148

2Inter0.148

3Aveng0.148

4TopGun0.135

5LoveAct0.128

6Notting0.103

7LaLa0.103

8Martian0.085

TakeawayExactly three hops (U→I→U→I) is the first walk that reaches new items, and its item scores equal item-based CF on the degree-normalised URM. Even hops land back on users; pushing the hop count up diffuses the mass toward popularity (oversmoothing).

Formal Definition 10.1 — transition & state

For an undirected, unweighted graph the transition probability is $p_{xy}=g_{xy}/d_x$ with degree $d_x=\sum_y g_{xy}$ . The state after $h$ hops is $\Pi^{(h)}=\Pi^{(0)}\,P^h$ . For recommendation, the predicted score of item $i$ for user $u$ is the item-node probability $\hat r_{ui}=\Pi^{(h)}_{U+i}$ , ranked descending.

03 · Three hops: U→I→U→I

P³ and the hidden CF connection

The magic of exactly three hops: it decomposes into an item–item similarity that looks strikingly familiar.

Why three? One hop ( $U\to I$ ) just lists the user’s own rated items — no discovery. Two hops ( $U\to I\to U$ ) lands on users, not items. Three hops ( $U\to I\to U\to I$ ) reaches items the user hasn’t seen, through a user who shares their taste. The slides put the optimal hop count at 3 (sometimes 5, rarely 7); beyond that, oversmoothing washes out personalisation and the walk drifts to popularity. Because $P$ is block-structured, its powers alternate between blocks:

P³ block structure

P^3 = \begin{bmatrix} 0 & P_{UI}\,P_{IU}\,P_{UI} \\ P_{IU}\,P_{UI}\,P_{IU} & 0 \end{bmatrix}.

Starting from a user, we only need the upper-right block, $\Pi_I^{(3)} = \Pi_U^{(0)}\,P_{UI}\,P_{IU}\,P_{UI}$ . The inner product $P_{IU}\,P_{UI}$ is an item–item similarity:

P³ item similarity

S_{ij} = (P_{IU}\,P_{UI})_{ij} = \sum_{u\in U}\frac{r_{ui}\,r_{uj}}{d_i\,d_j}.

This is cosine similarity with degree normalisation instead of the L2 norm. For implicit interactions (binary $r_{ui}\in\lbrace 0,1\rbrace$ ), $d_i=\sum_u r_{ui}$ is the item’s popularity, and $S_{ij}$ equals cosine similarity on the binary URM — without shrinkage. The full chain gives $\hat r_{ui} = \sum_j (P_{UI})_{uj}\,S_{ji}$ , i.e. $\hat R = P_{UI}\,S \propto R\,S$ — the same form as item-CF (Ch. 5) and SLIM (Ch. 6).

key

All roads still lead to R·S

Item-CF (Ch. 5), SLIM (Ch. 6), PureSVD (Ch. 8), and now P³ (Ch. 10) all compute $\hat R = R\,S$ . The difference is only in how $S$ is obtained: a cosine over columns, a learned regression, a low-rank projection, or three hops of degree-normalised propagation.

04 · Two knobs on P³

P³α and RP³β

Two refinements that alter the transition probabilities to control popularity bias.

P³α raises the transition probabilities to a power $\alpha$ before normalising: $P_{UI} = \operatorname{diag}(1/D_U)\,R^{\alpha}$ , and likewise $P_{IU}$ from $(R^\top)^{\alpha}$ . When $\alpha>0$ , small probabilities are attenuated — weak connections are damped more than strong ones. This sharpens the walk toward high-weight paths, but also amplifies popularity bias: popular items have larger rating columns, and the power exaggerates the gap.

RP³β attacks popularity directly, dividing the similarity by the destination item’s degree raised to $\beta$ :

RP³β similarity

S_{ij} = \frac{1}{d_j^{\,\beta}}\sum_{u\in U}\frac{r_{ui}^{\alpha}\,r_{uj}^{\alpha}}{d_i^{\alpha}\,d_j^{\alpha}}.

The extra $1/d_j^{\beta}$ penalises recommending a hugely popular item. With $\beta>0$ the walker is pushed away from over-popular destinations, increasing diversity. Together, $\alpha$ (edge-strength attenuation) and $\beta$ (popularity penalty) are two independent knobs on the precision–diversity trade-off.

P³ (baseline)

Standard 3-hop walk. Item–item

S_{ij}=\sum_u r_{ui}r_{uj}/(d_i d_j)

. Works well, but favours popular items that collect more paths.

P³α + RP³β

\alpha

attenuates weak connections;

\beta

penalises high-degree items. Combined, they control how much the walk follows the crowd.

Formal Definition 10.2 — P³α & RP³β

P³α. Power the rating matrix, $R^{\alpha}$ , before degree-normalising the transition matrix.

RP³β. The item similarity is $S_{ij}=d_j^{-\beta}\sum_u r_{ui}^{\alpha} r_{uj}^{\alpha}/(d_i^{\alpha} d_j^{\alpha})$ .

Both $\alpha,\beta$ are tuned on validation (Ch. 3). Typical ranges: $\alpha\in[0.5,2]$ , $\beta\in[0,1]$ .

05 · Attributes & infinite walks

Side information and the steady state

Adding attributes opens new meta-paths — and infinite walks converge to a page-rank-like steady state.

Adding attribute nodes $A$ (the tripartite graph $N=U\cup I\cup A$ ) lets the walker follow a new 3-hop meta-path, $U\to I\to A\to I$ : from a user to an item they rated, to that item’s attributes, and finally to other items sharing those attributes. That is a pure content-based recommendation, discovered through the same machinery. The catch: not every meta-path ends on an item. Paths that end on attribute or user nodes are dead ends for recommendation, so we modify $P$ at the relevant hop to drop edges that lead off-target — a form of meta-path control.

The slides also discuss the steady state (stationary distribution): the vector $\Pi$ satisfying $\Pi = \Pi\,P$ . For a bipartite graph the walk does not converge to a single point — it cycles between the two sides (a periodic Markov chain, period 2). To force convergence, random walk with restart adds a teleport probability $1-\gamma$ back to the start user:

Random walk with restart

\Pi = \gamma\,\Pi\,P + (1-\gamma)\,\Pi^{(0)}.

At $\gamma=0$ it is 100% restart (just the user’s own profile); as $\gamma\to 1$ it is a pure unrestricted walk. The restart parameter is a personalisation knob: lower $\gamma$ anchors the walker near the user. Solving for $\Pi$ exactly needs a linear system, which is expensive — so in practice truncated walks (P³, P⁵) are used instead.

Too many hops = oversmoothing

As $h$ grows, the walker diffuses across the whole graph and the state probability approaches the node-degree distribution — the recommendation becomes Top-Popular in graph clothing. For a bipartite graph the walk never settles on its own: it alternates between the user and item sides forever, so a recommendation needs either a fixed odd hop count or the restart trick.

06 · Exam intel

What the exam tests

Draw the bipartite graph from a URM; write the adjacency matrix $G=[0\ R; R^\top\ 0]$ ; define the transition matrix $p_{xy}=g_{xy}/d_x$ ; propagate the state one hop; explain P³ and why it equals item-CF; and distinguish P³α (amplifies popularity) from RP³β (reduces it). Graders look for $\Pi^{(h)}=\Pi^{(h-1)}\,P$ , the alternating blocks of $P^3$ , and the identity $S_{ij}=\sum_u r_{ui}r_{uj}/(d_i d_j)$ as cosine on a degree-normalised URM.

Worked question — walk two hops by hand

Bipartite graph: $u_1$ connects to $i_1,i_2$ ; $u_2$ connects to $i_2,i_3$ . Node order $[u_1,u_2,i_1,i_2,i_3]$ . (a) Write $G$ and $P$ . (b) From $\Pi^{(0)}=[1,0,0,0,0]$ compute $\Pi^{(1)}$ and $\Pi^{(2)}$ . (c) At which hop do items reappear?

(a) Degrees $d_{u_1}=2,\,d_{u_2}=2,\,d_{i_1}=1,\,d_{i_2}=2,\,d_{i_3}=1$ . $P=D^{-1}G$ row-normalises the adjacency, so from $u_1$ you reach $i_1,i_2$ each with probability $\tfrac12$ .
(b) $\Pi^{(1)}=[0,0,\tfrac12,\tfrac12,0]$ (on items). Hop again: $i_1$ returns to $u_1$ (degree 1); $i_2$ splits to $u_1,u_2$ (degree 2). So $\Pi^{(2)}=[\tfrac34,\tfrac14,0,0,0]$ — entirely on users, with the item slots zero.
(c) Items reappear at every odd hop $(1,3,5,\dots)$ ; even hops land on users. P³ uses $h=3$ , the first hop that discovers new items rather than the user’s own.

Trap: an even-hop state has zero mass on every item — if your $\Pi^{(2)}$ has a non-zero item entry, you double-counted a degree.

07 · Exam · past papers

Past-paper questions

Past paper Exam 2020 · Graph-based recommender for implicit data (6 pts)

Q. Implement a collaborative recommender for an implicit dataset with a graph-based approach: the bipartite graph structure (1); the incidence/adjacency matrix (1); the jump probability between nodes (1); the steady-state probability with and without restart (2); and how to extend the graph for side information (1).

Model answer. Bipartite graph. Two disjoint node sets, users and items; an undirected edge $(u,i)$ exists iff $u$ interacted with $i$ — no user–user or item–item edges. Adjacency. The URM $R$ is the incidence structure; the full adjacency is $A=\big[\begin{smallmatrix}0 & R\\ R^\top & 0\end{smallmatrix}\big]$ . Jump probability. Row-normalise by degree, $P=D^{-1}A$ , so you move to each neighbour with probability $1/\deg(\cdot)$ . Steady state. Without restart, $\pi=\pi P$ converges to a degree/popularity distribution that has forgotten the seed; with restart (personalised PageRank), $\pi=(1-\alpha)P^\top\pi+\alpha\,e_{\text{seed}}$ teleports back to the seed with probability $\alpha$ , keeping the visit probabilities personalised. Side information. Add item- and/or user-attribute nodes and edges, turning the bipartite graph into a tri-/multipartite graph so walks pass through shared attributes — helping cold items.

Past paper FT-Sample · Hops and personalization (6 pts)

Q. Implicit ratings: the graph structure (1); the adjacency matrix (1); the transition matrix (1); how the number of hops relates to personalization (2); extending the graph to item and user attributes (1).

Model answer. Graph & adjacency. Bipartite user–item graph; symmetric adjacency $A=\big[\begin{smallmatrix}0 & R\\ R^\top & 0\end{smallmatrix}\big]$ . Transition. $P=D^{-1}A$ , each row a distribution over neighbours. Hops & personalization. A short walk stays in the seed user’s neighbourhood — highly personalised but narrow coverage; as hops grow the walk mixes toward the graph’s degree-based stationary distribution, becoming more popular/diverse but less personalised. The 3-hop walk $U\to I\to U\to I$ is the sweet spot used by P³. Side information. Add user- and item-attribute nodes/edges (multipartite graph) so walks traverse shared attributes as well as co-interactions.

Past paper FT-Jan26 · Relation to item-CF; P³ vs P³α vs RP³β (7 pts)

Q. Implicit ratings: the graph structure (1); the transition matrix (1); how the model relates to item-based CF (2); the differences between P³, P³α and RP³β (3).

Model answer. Graph & transitions. Bipartite user–item graph; $P=D^{-1}A$ . Relation to item-CF. The 3-hop walk $I\to U\to I$ produces a matrix of landing probabilities between items — this is an item–item similarity, so scoring with it ( $\hat R\propto R\,S$ ) makes P³ a random-walk-derived item-based CF. P³ / P³α / RP³β. P³ is the plain 3-step walk, items scored by landing probability. P³α raises each transition probability to a power $\alpha$ before walking, sharpening (or damping) the influence of strong paths — a tunable hyper-parameter. RP³β takes P³α and re-ranks by dividing each item’s score by its popularity raised to $\beta$ , explicitly penalising popular items to counter popularity bias and improve the long tail.

Past paper Practice Exam 1 · Graph construction, state probability, PageRank (5 pts)

Q. How a user–item interaction graph is constructed (2); the concept of a state probability in a random walk (1); the PageRank algorithm and how it is used for recommendations (2).

Model answer. Graph construction. Nodes are users + items; add an edge for every observed interaction (the URM). The result is a bipartite graph with adjacency $A=\big[\begin{smallmatrix}0 & R\\ R^\top & 0\end{smallmatrix}\big]$ . State probability. The probability of being at a node after a number of random-walk steps; the vector evolves as $\pi_{t+1}=P^\top\pi_t$ . PageRank. The stationary distribution of a random walk with teleport, $\pi=(1-\alpha)P^\top\pi+\alpha\,v$ . For recommendation, use personalised PageRank — set the teleport vector $v$ to the target user’s items — then rank items by their stationary visit probability.

Past paper Practice Exam 4 · Random walks and side-information pitfalls (5 pts)

Q. How random walks find recommendations in a user–item graph (2); how to compute the state probability (1); how to incorporate side information, including potential problems (2).

Model answer. Random walks. Start at the target user and follow degree-normalised transitions $P=D^{-1}A$ ; the items reached most often (highest landing probability, typically via a 3-hop walk or RWR) are recommended. State probability. Iterate $\pi_{t+1}=P^\top\pi_t$ from the seed; $\pi_t(n)$ is the probability of being at node $n$ after $t$ steps. Side information & problems. Add attribute nodes and edges so walks traverse shared content. Problem: a popular attribute node has very high degree, so the walk funnels through it — diluting personalisation (over-smoothing) and amplifying popular items. The attribute edges must be weighted or normalised carefully.

08 · Self-check

Three questions before you move on

In a bipartite user–item graph, why does a 2-hop random walk not produce recommendations?

The P³ item–item similarity S_ij = Σ_u r_ui r_uj / (d_i d_j) is:

How does RP³β differ from P³α?

09 · Recap

One-screen summary

Chapter 10 — load-bearing ideas

Graph = URM: the bipartite graph $G=[0\ R; R^\top\ 0]$ ; recommendation is a random walk from a user, $\Pi^{(h)}=\Pi^{(0)}\,P^h$ with $p_{xy}=g_{xy}/d_x$ .
P³ = item-CF: the 3-hop walk gives $\Pi_I^{(3)}=\Pi_U^{(0)}\,P_{UI}\,S$ with $S_{ij}=\sum_u r_{ui}r_{uj}/(d_i d_j)$ — the same $\hat R=R\,S$ as Ch. 5/6/8.
Two knobs: P³α ( $\alpha$ attenuates small similarities, amplifies popularity); RP³β ( $\beta$ penalises high-degree items, improves diversity). Side information adds the $U\to I\to A\to I$ meta-path.
Even hops land on users; too many hops over-smooth to popularity; the bipartite walk is periodic, so it needs an odd hop count or restart $\gamma$ .