Graph Methods in Recommendations: How We Handle Large Interaction Graphs

Maxim Utushkin24 May 2025

Problem

A recommendations team at VK works with a graph of user interactions with VK Video plus friendship links between users: tens of millions of vertices and billions of edges after heavy trimming. Collaborative models such as two-tower pull embeddings of related users and items together only implicitly. They also need extra work to reuse data from the platform's other services. A graph model can address both, but at this size a convolution over all neighbors is unaffordable in training and inference.

Example from the article: an item that collects hundreds of thousands or millions of interactions, so computing one vertex output would need millions of input vertices.

Solution in brief

Treat recommendation as link prediction on a bipartite user-item graph and apply a graph attention network. Feed content embeddings and user features as inputs instead of trainable per-vertex embeddings, train with a ranking loss, and sample a fixed number of neighbors per convolution. Recompute embeddings on a schedule. In an online experiment time spent grew by 2%.

Questions this case answers
  • How to apply a graph neural network to a bipartite interaction graph with billions of edges and vertices of very high degree
  • How to keep neighbourhood aggregation affordable for vertices with millions of neighbours in training and serving
  • How to use a graph neural network on a user-item interaction graph with billions of edges
  • How to keep graph convolution affordable when some items have millions of interactions

Tools and methods

  • Graph Attention convolution — updates each vertex from its weighted neighbors
  • Heterogeneous graph — separate convolution per edge type (watch, friendship)
  • Neighbor sampling — caps the receptive field
  • Ranking loss — trains embeddings for the task they serve
  • Content embeddings and user features — model inputs
Continue reading — it's free

Google or a one-time email code. No password.