Graph Traversal for Recommendation Algorithms: Why Personalized PageRank Beats Brute-Force BFS

TL;DR.

• BFS over a user-item graph at query time is O(b^d): with a branching factor of 100 and depth 3, you're touching 1 million nodes per request.
• Personalized PageRank approximates the full reachability distribution via random walk with restart — multi-hop signal without full traversal.
• Collaborative filtering sees co-occurrence; graph traversal sees paths — and paths encode semantics that dot products cannot.
• In 2026, production recommenders combine offline PPR-based embeddings with online beam-search re-ranking; pure online BFS is a pre-2018 pattern.
• If you only remember one thing: your traversal algorithm determines what relationships your recommender can express, not just how fast it runs.

The standard framing of recommendation as a retrieval problem — embed users, embed items, find nearest neighbors — hides the structural question underneath it. That structure is a graph. Users connect to items they've interacted with. Items share edges through genres, creators, co-purchase signals, semantic similarity. Entities link to entities. The question is not whether you have a graph. The question is how you traverse it, and at what point in the serving pipeline. Most teams get this wrong in the same direction: they either ignore the graph and flatten everything into vectors, or they try to traverse it at query time with BFS and hit a latency wall they don't understand.

What Is Graph Traversal in the Context of Recommendation Algorithms?

Graph traversal for recommendations is the process of walking the edges of a user-item or entity-entity graph to identify candidates or compute relevance scores, where the path taken — not just the destination — is part of the signal. Unlike matrix factorization, which compresses co-occurrence into a fixed-dimension vector, traversal methods can follow typed edges through heterogeneous node types, encoding multi-hop reasoning: user liked artist, artist shares label with other artist, that artist's top track has high engagement from similar users.

The choice of traversal algorithm — BFS, DFS, random walk, Personalized PageRank, or learned graph neural network aggregation — determines the expressiveness of the signal, the latency budget required, and how gracefully the system handles cold-start nodes with few edges.

Why BFS Fails at Recommendation Scale

The intuitive move is to treat recommendation as graph reachability: given a user node, find all items reachable within k hops, score them, return the top-N. BFS is the natural algorithm for this. It's also wrong for any production system operating at scale.

The problem is the branching factor. In a typical user-item graph, a user might interact with 50-500 items. Each of those items is connected to hundreds of other users, who each have hundreds of items. At depth 1 you touch ~200 nodes. At depth 2 you touch ~40,000. At depth 3 you're at 8 million nodes — and you've blown your 30ms p50 budget before you've written a line of scoring logic. This isn't hypothetical; it's arithmetic. BFS at depth ≥ 2 over any graph with b > 50 is infeasible at online inference time for meaningful traffic.

There are two escape hatches that don't work: neighbor sampling and beam search. Neighbor sampling (randomly selecting k neighbors at each hop instead of all of them) reduces traversal cost but introduces high variance — you get a different result every call for the same user, and the results are biased toward high-degree nodes. Beam search (keeping only the top-k scoring nodes at each depth) requires a scoring function at intermediate nodes, which is circular if scoring is what you're trying to do. Both approaches patch the symptom without fixing the frame.

The right response is not to optimize BFS. It's to abandon online full-graph traversal entirely for candidate generation, and use a fundamentally different algorithm.

Personalized PageRank: The Production-Grade Alternative

Personalized PageRank (PPR) is the correct primitive for multi-hop relevance in recommendation graphs. Given a source node s, PPR defines a probability distribution π_s over all nodes in the graph: π_s(v) is the probability that an infinite-length random walk starting at s and teleporting back to s with probability α lands on v. Nodes with high π_s scores are structurally close to s in a way that accounts for all path lengths simultaneously, not just k-hop reachability.

The key property: PPR doesn't require you to traverse the full graph. The forward push algorithm (Andersen et al., 2006) and its successors like FORA (Wang et al., 2019) compute approximate PPR scores in sublinear time relative to graph size, touching only the nodes that contribute meaningfully to the source distribution. In practice this means you can compute PPR-based candidates for a user node in milliseconds even on graphs with hundreds of millions of edges.

Pinterest's production recommender is the canonical existence proof. PinSage (Ying et al., 2018) uses PPR-based neighborhood sampling as the foundation of its graph neural network training: instead of sampling fixed k-hop neighborhoods (which are expensive and high-variance), it samples neighborhoods weighted by PPR scores from each node. The result is a GNN that implicitly learns from the full multi-hop structure without ever touching the full graph. Pinterest ran this at 3 billion node scale.

The Teleport Probability α

α is the single most consequential hyperparameter in PPR for recommendation. High α (0.8-0.9) means the walk returns to the source frequently — the resulting distribution is concentrated near the source node, biased toward direct neighbors. Low α (0.1-0.3) lets the walk diffuse further across the graph, capturing longer-range structural similarity. For cold-start recommendation where a user has few edges, low α helps: it lets signal from sparse local structure propagate further. For dense users with rich interaction history, higher α keeps recommendations personally relevant rather than drifting toward globally popular nodes.

Random Walk Methods and What They Actually Encode

DeepWalk (Perozzi et al., 2014) is the foundational paper in learned graph embeddings via traversal. The mechanism: sample fixed-length random walks from each node, treat each walk as a sentence over the node vocabulary, and train a Skip-Gram model (Word2Vec) on those sentences. Nodes that co-occur frequently in random walks end up with similar embeddings. The resulting vectors capture structural proximity — two nodes that are often reached from the same starting point will be close in embedding space, even if they share no direct edge.

Node2Vec (Grover & Leskovec, 2016) adds two hyperparameters to DeepWalk's random walk: p (return parameter) and q (in-out parameter). Together they let you tune the walk between BFS-like behavior (p < 1: high probability of returning to the previous node — samples local neighborhood densely) and DFS-like behavior (q < 1: high probability of exploring nodes not yet visited — samples farther structural equivalents). This distinction matters for heterogeneous recommendation graphs.

With p < 1 (BFS-biased): the walk captures homophily — nearby nodes in the graph tend to have similar embeddings, which is good for collaborative filtering signals (users with overlapping history get similar vectors).

With q < 1 (DFS-biased): the walk captures structural equivalence — nodes that play similar roles in the graph (e.g., "connector nodes" like genre hubs) get similar embeddings, even if they're far apart. This is good for cross-domain recommendation and catalog-side representations.

What Random Walk Embeddings Miss

Random walk methods have a fundamental limitation: they produce static embeddings. Once trained, the embedding for a node doesn't change when new edges are added. For a recommendation graph where user-item interactions arrive continuously, this means embeddings go stale. You either retrain on a schedule (expensive, introduces lag) or you accept that the model doesn't know about recent interactions. For cold-start nodes — users or items that appear after the last training run — random walk methods produce nothing at all.

This is exactly where graph neural networks take over.

Graph Neural Networks as Learned Traversal

GNNs frame graph traversal as a learned function. At each layer, a GNN aggregates representations from a node's neighbors and updates the node's own representation. After k layers, each node's embedding incorporates information from its k-hop neighborhood — without explicitly traversing all k hops. The traversal is implicit in the aggregation function.

GraphSAGE (Hamilton et al., 2017) is the most directly applicable architecture for recommendation at scale. It samples a fixed number of neighbors at each hop (rather than using all neighbors, avoiding the BFS branching problem), aggregates their features using a learned function (mean, LSTM, pooling), and concatenates the aggregated neighborhood representation with the current node representation. Crucially, GraphSAGE learns an inductive aggregation function — it can produce embeddings for nodes not seen during training, as long as those nodes have neighbor features. This directly addresses the cold-start problem that static random walk embeddings cannot handle.

For knowledge graphs with multiple edge types (user-rated-item, item-belongs-to-genre, item-created-by-artist), heterogeneous GNNs like HAN (Wang et al., 2019) and KGAT (Wang et al., 2019) extend the aggregation to type-specific attention. KGAT learns attention weights over different relation types in the knowledge graph, letting the model decide which paths (user → genre → item vs. user → collaborator → artist → item) are more predictive for a given user-item pair. The attention weights are also interpretable — which is why graph-based recommenders beat black-box matrix factorization on right-to-explain requirements now baked into EU AI Act compliance.

Path Semantics: Why the Route Matters

The deepest problem with flattening graphs to embeddings is that you lose path semantics. Consider a music recommendation graph:

• Path A: user → [listened to] → track X → [by] → artist → [also made] → track Y
• Path B: user → [listened to] → track X → [similar BPM to] → track Y
• Path C: user → [listened to] → track X → [co-purchased with] → track Y

All three paths terminate at track Y, and all three would register as "track Y is relevant to user." But they represent completely different recommendation rationales. Path A is an artist affinity signal. Path B is an audio feature signal. Path C is a behavioral co-occurrence signal. A recommender that conflates these under a single similarity score will produce recommendations that are numerically correct but semantically confused — the right item for the wrong reason, which means it fails to generalize when the graph changes.

Metapath-based traversal (Sun et al., 2011) formalizes this intuition. A metapath is a typed sequence of edge relations: User-[rated]-Movie-[directedBy]-Director-[directed]-Movie. By restricting random walks to follow specific metapaths, you generate embeddings that encode only the structural signal you care about. You can then combine embeddings from multiple metapaths with learned attention — which is exactly what MAGNN and HAN do.

In practice this means your recommendation system can expose why it made a recommendation at a path level, not just a feature attribution level. "We recommended this track because you follow this artist" is derivable from path semantics. "We recommended this because your embedding is close in vector space" is not.

Offline vs Online: Where Traversal Actually Happens in 2026

The architecture pattern that works at production latency is a two-stage pipeline where offline traversal feeds online ranking.

Offline: Compute PPR Embeddings or GNN Representations

Run PPR from every active user and item node in your graph on a scheduled cadence (hourly to daily depending on graph update frequency). Store the resulting top-K candidates per node in a key-value store indexed by node ID. Alternatively, train a GraphSAGE or PinSage-style GNN offline and cache the resulting embeddings. Both approaches do the expensive graph work offline, so online serving sees only a lookup.

The critical implementation detail: PPR must be recomputed incrementally when the graph changes, not from scratch. Incremental PPR algorithms (Zhang et al., 2016) propagate score changes only through the subgraph affected by new edges. For a graph receiving millions of new edges per hour, this is the difference between a real-time system and a batch system with a 24-hour lag.

Online: Beam Search Re-Ranking over Retrieved Candidates

Given offline-retrieved candidates (100-1000 nodes), online re-ranking with a lightweight beam search over a shallow 1-2 hop expansion is feasible. At this scale, the graph is already pruned to a manageable subgraph around the query user. A beam of width 50-100, expanded 1 hop, touches at most a few thousand nodes — well within a 10ms latency budget. This online expansion captures recency: interactions that arrived since the last offline PPR computation (minutes or hours ago) appear in the 1-hop neighborhood and influence ranking.

The resulting pipeline: offline PPR/GNN for broad candidate generation → vector ANN for deduplication and semantic filtering → online 1-hop beam search for recency injection → pointwise or pairwise ranker. Each stage has a clearly defined latency budget. None of them do full BFS.

What This Means for Cold-Start

The traversal algorithm choice directly determines your cold-start story. A new user or item with zero edges is unreachable by any traversal from existing nodes. Static embeddings (DeepWalk, Node2Vec) produce nothing. PPR from a source with no edges collapses to the global PageRank distribution — which is just a popularity ranker.

The only traversal approach that handles day-zero cold start without manual feature engineering is an inductive GNN that operates on node features rather than graph structure alone. GraphSAGE with item content features (title, genre, audio embeddings, description embeddings) can produce a meaningful embedding for a new item from its features, without any interaction edges. The aggregation function learned from existing well-connected nodes generalizes to new nodes with similar feature profiles.

This is the reason knowledge graph augmentation matters for cold-start: even a brand-new item has structured metadata — it belongs to a genre, has a creator, has a release year. These attributes are edges in a knowledge graph. An inductive GNN can traverse those attribute edges to produce a non-trivial embedding even before the first user interaction. The synthetic clone approach extends this further: you model the new user's feature vector as similar to an existing known-user cluster, then use that cluster's PPR distribution as a warm-start prior.

Where to Start

If you're building a graph-based recommender for the first time, don't start with a GNN. Start with PPR.

1. Build the graph. User-item interaction edges are the minimum. Add item-attribute edges (genre, creator, tag) if you have them. Keep the schema simple — two or three edge types maximum. A graph with clear semantics beats a graph with 20 relation types where half are noise.

2. Implement approximate PPR offline. Use an existing library (NetworkX for small graphs, PyG or DGL for larger, or a custom forward-push implementation for production). Run PPR from every active user node, store the top-500 candidates per user in Redis or DynamoDB. Measure offline compute time. This is your baseline retrieval system.

3. Measure recall against your existing retrieval. Take the top-500 PPR candidates per user and compute recall@K against held-out interactions. Compare to your current item-item similarity or collaborative filtering baseline. PPR will typically win on long-tail users and lose on dense users (where CF has abundant signal). Understanding where PPR wins tells you which user segments benefit most from graph traversal.

4. Add a GNN only when cold-start recall is the bottleneck. If your main recall problem is on new users and new items, layer in a GraphSAGE-style inductive model trained on item content features. Use PPR-based neighborhood sampling (not fixed-k-hop sampling) to control training cost. Don't train a GNN end-to-end from scratch until you have at least 1M interaction edges — below that, collaborative filtering and PPR together usually dominate.

5. Wire online 1-hop expansion last. After offline retrieval and ranking are working, add the online expansion step to inject recency. This is the last thing to optimize because it's the hardest to debug and the least impactful until you have users whose behavior changes faster than your offline recomputation cadence.

The traversal algorithm isn't an implementation detail. It's the architectural decision that determines what your recommender can know about a user from their history, and what it can infer about a new user with no history at all. Getting this right is the difference between a recommender that handles your P99 cold-start users and one that silently serves them popularity lists forever.