Skip to content
AI.info

Recommender systems

Graph-Based Recommendation and Random Walks

Model recommendation as movement across user-item and heterogeneous graphs, including random walks, path semantics, popularity, and graph construction choices.

By the end you can

Graphs make relational assumptions explicit

Users, items, sessions, creators, categories, queries, purchases, citations and knowledge entities can all be nodes in a recommender graph. Random walks and diffusion methods propagate preference through the edges between them. But the graph is something a team designed, not the world itself. Whoever chose the edge types, their direction, their weights, the time window, the deletion policy and the degree normalization also chose which relations get to be influential.

Taobao's recommender covers one billion users and two billion items. In 2018 Alibaba published how the graph under it is built. Behaviour is first cut into sessions, and the cut is a choice with a number on it: "Empirically, the duration of the time window is one hour." A directed edge is drawn between two items only if they were accessed consecutively. The edge weight is the transition frequency. The logs reach back three months, around 600 billion entries after anti-spam filtering. The graph is then cut into subgraphs of around 50 million nodes each, and around 150 billion random-walk sequences are generated over it.

None of that was discovered. Every line of it is a declaration. And the same paper says outright what the construction cannot reach: a newly updated item has no embedding learnable from the item graph.

Every edge a team declined to draw is a relation the walk can never follow, so the graph's omissions shape preference as much as its links do.

Case

Pixie at 60 milliseconds, PinSage at 67% hit-rate

Pinterest published operating figures for a random-walk recommender in 2017. Pixie walks an object graph of 3 billion nodes and 17 billion edges. A single server handled 1,200 recommendation requests per second at 60 milliseconds. Graph pruning added a further 58 percent improvement. X runs a smaller version of the idea, keeping an in-memory user-to-post interaction graph and generating candidates by traversing it.

Those numbers say the walk can be served. What the walk bought was measured separately, on the same company's graph. PinSage ran random-walk-based graph convolutions over 2 billion pins, 1 billion boards and over 18 billion edges. Pinterest reported the offline result in 2018: "PinSage with our new importance-pooling aggregation and hard negative examples achieves the best performance at 67% hit-rate and 0.59 MRR, outperforming the top baseline by 40% absolute (150% relative) in terms of the hit rate and also 22% absolute (60% relative) in terms of MRR." The production A/B test reported 10-30% improvements in repin rate over the Annotation- and Visual-embedding-based recommendations.

A walk is a retrieval policy. Its stopping rule is a product choice.

Visual

A graph-recommendation anatomy

Most of a graph recommender is decided before anything runs. What counts as a node. What an edge means. How much a year-old edge still counts. The first three stages below have published values attached to them in Alibaba's Taobao system: an edge exists between two items only where they were accessed consecutively, the weight is the transition frequency, the session that bounds the edge is one hour long, and the logs behind the whole graph reach back three months. Propagation then does the retrieving. Because it walks a path, the candidate arrives with its explanation attached. That is a different claim from the claim that the path justifies the recommendation.

FigureProcess · 5 steps
  1. 1

    Nodes

    Define users, items, sessions, entities, and aggregations at appropriate granularity.

  2. 2

    Edges

    Encode interactions, similarity, compatibility, ownership, or semantic relations.

  3. 3

    Weights and time

    Control frequency, recency, confidence, and direction.

  4. 4

    Propagation

    Use random walks, personalized PageRank, diffusion, or path scoring.

  5. 5

    Candidate and explanation

    Retrieve reachable items and preserve the supporting relation path.

Analogy

A transit network built from past service

On a transit map, the busiest stations hold the most routes partly because earlier planners already favored them. A random walk over that map keeps returning to the same hubs. That is not a metaphor's licence. It is a property of the scoring function, and it is the stated reason PathSim was built in 2011 to measure similarity a different way: "For example, the path count and random walk-based similarity always favor objects with large degrees, and the pairwise random walk-based similarity favors concentrated objects that the majority of the links goes to a small portion of objects." Recommender graphs behave the same way once exposure has created degree.

Every line on the transit map means one thing, though. A recommender graph mixes purchases, views, authorship and citation into edges that look identical.

Connectivity is evidence shaped by past policy, not a neutral map of preference.

Example

Two typed paths, two different answer sets, on one DBLP graph

Ask one network which venues are similar to DASFAA and you get two different answers. Which answer you get depends on the typed path the query is allowed to walk. The network is DBLP — over 710K authors, 1.2M papers and 5K venues — and the measurement is PathSim's, from 2011. The paper opens against untyped propagation: "Objects of different types and links carry different semantic meanings, and it does not make sense to mix them to measure the similarity without distinguishing their semantics."

  • Graph construction: The network is typed before any query runs. Authors, papers and venues are different kinds of node across over 710K authors, 1.2M papers and 5K venues, so a query has to declare which relation it is following.
  • Path semantics: Under the venue-paper-author-paper-venue path, the top-4 venues similar to DASFAA are DASFAA, DEXA, WAIM and APWeb. Under the venue-paper-term-paper-venue path they are DASFAA, Data Knowl. Eng., ACM Trans. DB Syst. and Inf. Syst. Same graph, same query, different evidence.
  • Degree effect: On the DBIS subset (464 venues, top-5000 authors), the query PKDD under the meta path CAC returned high-visibility venues from Personalized PageRank. KDD, ICDE, VLDB and SIGMOD took ranks 2-5 of its top-10 list.
  • Temporal issue: Mixing periods has a count attached, published in 2023. On Yelp, for test instances in year Y5, LightGCN produced 1,103 items released after the test instance across its top-20 lists once training data ran to year Y10. For test year Y7 it produced 1,360.
  • Explanation risk: A displayed path reads as the reason for the recommendation. But PathSim's own measurement shows the reason changes with the path the walk was permitted. The author route and the term route are not two views of one underlying fact.

Example

Graph-specific failure modes

Degree gravity is a property of the graph. Path storytelling is a property of the people reading it. Both have been measured rather than merely asserted.

High-degree nodes pull walks toward themselves whatever the personalization does. Personalized PageRank is a personalized walk, and on the DBIS subset it still answered PKDD with KDD, ICDE, VLDB and SIGMOD at ranks 2-5 of its top-10. A convenient path, meanwhile, arrives looking like a justification. A 2019 lab study put a nutrition-recommender prototype in front of 30 people, ten per group. The median trust ratings of the placebic-explanation and real-explanation groups were alike, and both above the no-explanation group.

  • Degree gravity: Path count and random-walk similarity always favor objects with large degrees, in PathSim's own words, and the PKDD query is the worked case — KDD, ICDE, VLDB and SIGMOD at ranks 2-5 of a personalized walk's top-10 list.
  • Edge leakage: BPR, NeuMF, SASRec and LightGCN were rerun on MovieLens-25M, Yelp, Amazon-music and Amazon-electronic under leave-last-one-out splits. Every model recommended items released after the test instance. Adding future data shifted accuracy by magnitudes as high as 89.5%, in both signs and with no particular pattern.
  • Relation collapse: Beyond DASFAA itself, the two top-4 lists share no venue. An untyped edge would have compressed those two answers into one and hidden which relation produced it.
  • Disconnected cold items: Alibaba's Taobao paper says outright that a newly updated item has no embedding learnable from the item graph. Propagation cannot reach a node the construction has not yet connected.
  • Path storytelling: The placebic-explanation study concluded, descriptively and without statistical testing, that a placebic explanation moved perceived trust much as a real explanation did.

Steps

Typed evidence in a graph recommender

Nodes, edges, direction and time window are declarations rather than discoveries. They come first. Degree normalization, preserved time, inspected paths, and a comparison against non-graph alternatives make up the rest. Two of those steps have published instruments behind them rather than good intentions.

Step 2 has a named knob. RP3β, introduced in 2015, re-ranks the three-step random walk P3α. The team that later reran it independently describes the knob in one line: "Here, the outcomes of P3α are modified by dividing the similarities by each item's popularity raised to the power of a coefficient β." In those reruns the degree-discounted walk beat the 2018 neural model CMN on all four reported metrics on CiteULike-a (HR@5 0.8226 vs 0.8069, NDCG@5 0.7114 vs 0.6666, HR@10 0.8941 vs 0.8910, NDCG@10 0.7347 vs 0.6942) and on Pinterest (HR@5 0.7018 vs 0.6872, NDCG@5 0.5041 vs 0.4883, HR@10 0.8644 vs 0.8549, NDCG@10 0.5571 vs 0.5430). A popularity discount on an old walk, and it wins.

Step 3 has a count. The leakage study puts it in its own abstract: "Through carefully designed experiments, we show that all models indeed recommend future items that are not available at the time point of a test instance, as the result of data leakage." LightGCN is the graph model in its set. On Yelp it produced 1,103 such future items across its top-20 lists for year Y5 test instances once training data ran to year Y10. Point-in-time construction is what closes that. A stricter scoring rule over one static graph does not.

FigureProcess · 5 steps

  1. 1. Define graph semantics

    Document every node and edge type, direction, and time rule.

  2. 2. Normalize degree

    Compare raw, symmetric, and relation-aware propagation.

  3. 3. Preserve time

    Construct point-in-time graphs for training and evaluation.

  4. 4. Inspect paths

    Review head, tail, sensitive, and unexpected recommendation routes.

  5. 5. Compare alternatives

    Benchmark graph methods against item-item, factorization, and content sources.

Key idea

An explainable path is not a justified recommendation

A path can explain how evidence traveled through the model without proving that the relation should determine the user's choice. That gap has been measured on readers rather than on models.

In 2019 a small lab study put a nutrition-recommender prototype in front of 30 people, ten per group: no explanation, a placebic explanation, a real explanation. The median trust ratings of the placebic and real groups came out alike, both above the no-explanation group. That was reported descriptively, without statistical testing. The conclusion: "Our results indicate that placebic explanations for algorithmic decision-making may indeed invoke perceived levels of trust similar to real explanations."

A rendered walk is exactly the kind of object that study put in front of people.

Readability is what makes this failure hard to catch: a walk that renders cleanly invites a reviewer to accept the relation instead of asking whether it should have carried any weight.

Key idea

The graph gate

Use relational propagation only after node, edge, time and degree assumptions have survived direct inspection and ablation. The benchmark half of that rule bites, and there is a record of it biting.

In 2019 three researchers tried to reproduce 18 neural top-n recommendation algorithms from top conferences. Only 7 were reproducible with reasonable effort, and 6 of those 7 were beaten by simple heuristics. One of the 7 was a meta-path graph recommender, MCRec, published in 2018: "Table 3 shows that the traditional ItemKNN method, when configured correctly, outperforms MCRec on all performance measures." On MovieLens100k the correctly tuned ItemKNN returned PREC@10 0.3327 against MCRec's 0.3077, REC@10 0.2199 against 0.2061, and NDCG@10 0.2603 against 0.2363. That paper won best paper at RecSys 2019.

Ablation is the price of admission here: if nobody has removed the graph and measured what was lost, relational propagation is running on faith rather than on evidence.

Key takeaways