Scaling GNNs for Friend Recommendation: Multi-Hash Embeddings and Temporal Neighbor Sampling

Forum topic · 小凯 · 2026-08-30

Summary

A paper by Maksim Utushkin, Andrei Ovsiannikov, and Alexander D'yakonov (arXiv:2608.27413) presents a scalable end-to-end graph neural network (GNN) ranking system for friend recommendation on production social graphs with hundreds of millions of users and tens of billions of edges. The system relies on two key design choices: multi-hash ID embeddings and temporal neighbor sampling. Multi-hash embeddings reduce the trainable ID embedding table size by over 98%, avoiding full embedding tables that exceed 200 GB, while preserving ranking quality. Temporal neighbor sampling uses timestamp-ordered CSR storage with binary search, reducing per-node temporal sampling cost from O(deg(v) + k) to O(log(deg(v)) + k). On a graph with 194 million users and 28 billion edges, online A/B testing showed a 16% increase in friend-add recommendations and an 11.5% increase in unique friend adders compared to strong production baselines.

Paper Overview

Field: Machine Learning Authors: Maksim Utushkin, Andrei Ovsiannikov, Alexander D'yakonov Published: 2026-08-27 arXiv: 2608.27413

Abstract

Friend recommendation is inherently graph-structured: the relevance of a potential connection depends on multi-hop social context rather than user attributes alone. However, deploying message-passing GNNs on a production-scale social graph with hundreds of millions of users and tens of billions of edges requires addressing numerous modeling and systems challenges. The authors present a scalable end-to-end GNN ranking system for production social graphs, focusing on two design choices that are critical in this setting:

Multi-hash ID embeddings: Multi-hash embeddings are common for high-cardinality features, but industrial GNN systems typically either ignore trainable IDs or accept full embedding tables, exceeding 200 GB for this graph. Integrating multi-hash embeddings reduces the ID embedding table size by more than 98% while maintaining ranking quality.
Temporal neighbor sampling: Implemented with timestamp-ordered CSR storage and binary search, this reduces the temporal sampling cost per node from O(deg(v) + k) to O(log(deg(v)) + k).

Results

On a social graph with 194 million users and 28 billion edges, online A/B testing demonstrated that the system:

Increases friend-add recommendations by 16%
Increases unique friend adders by 11.5%

compared to strong production baselines.

Source: arXiv:2608.27413