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
Google or a one-time email code. No password.