Scaling Graph Neural Networks for Friend Recommendation: Multi-Hash Embeddings and Temporal Neighbor Sampling

Forum topic · 小凯 · 2026-08-30

Summary

A new arXiv paper (2608.27413) by Maksim Utushkin, Andrei Ovsiannikov, and Alexander D'yakonov presents a scalable end-to-end GNN ranking system for friend recommendation on production-scale social graphs with hundreds of millions of users and tens of billions of edges. The work introduces two key design choices: multi-hash ID embeddings, which reduce the embedding table size by over 98% while preserving ranking quality (avoiding embedding tables exceeding 200 GB), and temporal neighbor sampling built on timestamp-ordered CSR storage with binary search, which lowers 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 a strong production baseline. The paper offers practical guidance for deploying message-passing GNNs at industrial scale.

论文概要

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

Abstract (translated)

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:

1. 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 — which, for their graph, would exceed 200 GB. By integrating multi-hash embeddings for IDs, the system reduces the ID embedding table size by more than 98% while maintaining ranking quality.

2. Temporal neighbor sampling

The system implements timestamp-ordered CSR storage with binary search, reducing the cost of temporal sampling per node from O(deg(v) + k) to O(log(deg(v)) + k).

Results

On a graph with 194 million users and 28 billion edges, online A/B testing showed the system delivers, compared to a strong production baseline:

+16% friend-add recommendations
+11.5% unique friend adders