PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Maksim Utushkin, Andrei Ovsiannikov, Alexander D'yakonov

arXiv:2608.27413v1cs.IRcs.LGcs.SI

TL;DR

Production-scale friend recommendation must handle massive graphs, weak user attributes, and temporal leakage without unaffordable embedding or sampling costs. The paper combines multi-hash user IDs with timestamp-sorted CSR and binary-search sampling in an end-to-end GNN ranker, achieving online gains over a strong baseline while operating on a 194M-user, 28B-edge graph.

  • Problem

    Massive, weak-content, dynamic social graphs make trainable user IDs, graph storage, and temporally correct neighbor sampling difficult to support at production scale.

  • Method

    The system uses multi-hash user ID embeddings and binary-search temporal neighbor sampling over timestamp-sorted CSR within a GATv2 ranking pipeline.

  • Results

    +16% friend additions from recommendations and +0.28% total content-feed time were observed in an online A/B test.

  • Takeaways & Limitations

    Together, the two design choices cover the production-scale representation and temporal-sampling challenges the authors found hardest to get right.

  • Takeaways & Limitations

    GNN embeddings are refreshed offline on a fixed schedule, creating staleness between refreshes and a cold window for new or inactive users.

Abstract

from arXiv · show

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. We 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 and temporal neighbor sampling. 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 our graph. We integrate multi-hash as the primary node representation, reducing the ID-embedding table size by more than 98 percent while preserving ranking quality. Temporal neighbor sampling is well understood in principle, but existing implementations scan full adjacency lists, which is a non-starter for users with tens of thousands of friends. We implement timestamp-sorted CSR storage with binary search, reducing the per-node temporal sampling cost from $O(deg(v) + k)$ to $O(\log(deg(v)) + k)$. Beyond these components, we show that this combination scales and yields measurable production impact. On a graph with 194M users and 28B edges, offline ablations isolate each design choice's contribution. In an online A/B test, our system increases friend additions from recommendations by 16 percent and unique friend adders by 11.5 percent over a strong production baseline. We release our framework for distributed training and inference on large temporal graphs.

1 Introduction

The paper develops a production-scale GNN ranker for friend recommendation by addressing graph scale, weak node content, and temporal leakage. Multi-hash IDs and binary-search temporal sampling reduce infrastructure costs while retaining measurable online gains.

  • System constraints: 194M users and 28B edges make graph storage, sampling, and temporal correctness central engineering constraints.A full 200M × 256 float32 ID table would require approximately 205 GB, while naive temporal scans bottleneck high-degree users.
  • Design choices: Multi-hash ID embeddings reduce the ID-embedding table from >200 GB to 2 GB (<1%) while matching the quality of a full |V | × d table.The shared table trades exact identifiability for bounded hash collisions.
  • Design choices: Temporal neighbor sampling uses timestamp-sorted CSR and binary search, achieving O(log du+K) cost instead of O(du + K) and eliminating a ≈2.5× training-time overhead.The timestamp order is reused across training epochs and embedding refreshes without re-sorting.
  • System implementation: The end-to-end pipeline combines CSR storage, decoupled CPU sampling, GPU training, and offline embedding refresh on a single 8-GPU host.The graph occupies approximately 225 GB and includes 28B edges.
  • Evaluation: +16% friend additions and +11.5% unique adders were achieved over a strong production baseline in an online A/B test.Offline ablations isolate the contribution of each design choice.
  • Release: The framework releases training and inference components for refreshing GNN embeddings over large timestamped CSR graphs.The release includes the multi-hash embedding layer and native temporal neighbor sampler.

2 Problem Formulation

The task ranks upstream friend candidates for users using impression-conditioned labels and time-consistent graph information. Training uses a binary-classification objective while the downstream production ranker consumes the GNN score as a feature.

  • 2.1 Graph and task: The friendship graph is an undirected graph whose nodes are active users and whose timestamped edges record mutual friendships.Users are reindexed into a contiguous integer range for CSR indexing and hashing.
  • 2.1 Graph and task: Friend recommendation uses a two-stage funnel: upstream candidate generation followed by ranking across product surfaces.Candidate generation combines behavioral counters, Adamic–Adar, and learned retrieval.
  • 2.1 Graph and task: The ranking model scores each user–candidate pair (u, v) for v in an upstream candidate set C_u.The system ranks friend candidates only and is separate from content-feed ranking.
  • 2.2 Training objective: Training examples come from recommendation impressions represented as (u_i, v_i, y_i, τ_i).The impression timestamp τ_i accompanies the outcome label y_i.
  • 2.2 Training objective: Labels are positive for friend additions, negative for no-action impressions and explicit hide events.The downstream gradient-boosted ranker uses impression-conditioned labels of the same form.
  • 2.2 Training objective: The GNN is trained as binary classification with standard cross-entropy loss.Its score is consumed as a feature by a downstream gradient-boosted ranker.
  • 2.2 Training objective: The score f(u, v; τ) uses only information available up to impression time τ.This prevents future information from entering the prediction.

3 Related Work

Related work spans social link prediction, industrial friend recommendation, scalable message passing, compact identifier embeddings, temporal graph learning, and end-to-end GNN platforms. This paper positions itself around production-scale ID representation and temporally efficient sampling.

  • Link prediction: Classical social link prediction forecasts future edges, whereas this system predicts acceptance among retrieved candidates using online product metrics.The paper distinguishes impression-conditioned acceptance from edge formation in the wild.
  • Industrial friend recommendation: Industrial friend-recommendation systems combine structural heuristics with learned embedding or GNN-based rankers.Examples include GraFRank, SSNet, and LiGNN across Snapchat, Xbox, and LinkedIn settings.
  • GNN architectures: Mainstream GNNs share message passing, while systems such as PinSage scale recommendation through neighborhood sampling.These models commonly assume rich node features or trainable per-node embeddings.
  • Compact identifier embeddings: Multi-hash and related methods compress high-cardinality identifier embeddings by mapping many identifiers into a smaller shared table.The trade-off is reduced exact identifiability in exchange for lower memory use.
  • Temporal graph learning: Temporal graph models avoid future interactions, while temporal-CSR systems address efficient dynamic-graph neighborhood sampling.This paper uses timestamp sorting plus binary search and measures its training-throughput effect for friend ranking.
  • Industrial GNN systems: Industrial platforms such as GiGL, GraphStorm, and LiGNN emphasize sampling, distributed training, and representation-refresh costs.The paper is complementary, focusing on two specific design decisions rather than presenting a full platform.

4 Method

The method combines feature and multi-hash ID inputs with a sampled-neighborhood GATv2 encoder, while temporal sampling restricts message passing to a leakage-safe history. Timestamp-sorted CSR and binary search make temporal sampling practical for high-degree users.

  • GNN encoder: The encoder uses stacked GATv2 convolutions and separate query and candidate heads to model role-specific representations.The two roles are scored by an inner product after projection.
  • Node representation: User features and multi-hash ID representations form the initial node embedding for the GNN.The multi-hash layer uses a shared table indexed by multiple independent hash functions, then concatenates and projects the retrieved rows.
  • Neighbor sampling: Neighbor sampling bounds each L-hop computation graph by O(K^L), preventing high-degree multi-hop neighborhoods from becoming unmanageable.This is needed because even two hops can reach tens of millions of nodes from one seed.
  • Temporal sampling: Temporal message passing uses the event timestamp and safety offset to exclude edges from the recent window [τ −∆, τ] and avoid future-edge leakage.The same cutoff is propagated across all L hops.
  • Temporal sampling: O(log d_u + K) replaces O(d_u + K) per temporal sampling call by binary-searching a timestamp-sorted CSR prefix.The optimized sampler samples uniformly from the valid prefix without scanning the full adjacency list or re-sorting during sampling.
  • Node representation: Multi-hash embeddings trade bounded hash collisions for a shared table much smaller than the infeasible |V| × d per-user table.Full collisions occur with probability (1/B)^k under a uniform hash family, while the projection can separate users with partial collisions.

5 Training and Inference System

The system separates CPU-side graph processing from GPU training and stores the graph in CSR for scalable neighborhood sampling. Periodic offline inference refreshes user embeddings that the online ranker consumes.

  • Training architecture: CPU-side sampling constructs serialized minibatches while GPU workers train the GNN on prepared message-passing blocks.The sampler and trainer communicate through a bounded queue.
  • Graph storage: The graph uses CSR arrays for vertex offsets, neighbor IDs, and timestamps aligned with those neighbors.Neighbor IDs and timestamps use 32-bit integers, while indptr uses 64-bit storage because the edge count exceeds 2^32.
  • Graph storage: The production graph occupies approximately 225 GB and fits in host RAM, allowing the entire graph to remain in process.The CSR representation is reused for temporal sampling and inference.
  • Inference and refresh: Inference periodically samples local neighborhoods, runs the trained encoder, and writes refreshed user embeddings for online ranking.The system does not track online cascades from new edges; it recomputes embeddings for a large active subset.

6 Experiments

Experiments evaluate the proposed ranker against popularity, matrix factorization, and the previous production GNN system using temporally split impression data. Offline results report per-user ROC-AUC on held-out interactions.

  • Setup: The dataset uses a temporal split of impression timestamps, with the last three years used for training and binary labels.
  • Baselines: The evaluation compares Top-pop, MF, WalkGNN, and the proposed model, spanning non-learned, factorization, prior-production, and proposed rankers.WalkGNN is treated as the strongest production baseline.
  • Offline results: The proposed model adds the largest ROC-AUC increment by extending message passing to the full multi-hop neighborhood.The paper attributes this extension to the multi-hash and temporal-sampling choices examined in the ablations.
  • Metric: Offline ranking quality is measured as per-user ROC-AUC on held-out test interactions, with higher values indicating better performance.

6.4 Ablations

Ablations isolate input-representation and temporal-sampling choices while holding other configuration parameters fixed. Multi-hash preserves quality with far less memory, and binary-search temporal sampling avoids the cost of naive scans without changing quality.

  • Input representations: Multi-hash matches the full |V | × d embedding table while using less than 1% of its memory.The full table is used as an offline quality reference because it does not fit on a single host or serve directly.
  • Input representations: Structural signal alone outperforms tabular signal alone by a wide margin in friend ranking.
  • Hash-table size: B = 2^21 is selected for production because doubling the shared table at B = 2^22 changes quality only marginally.Quality increases monotonically across the sweep and has not flattened at 2^22.
  • Temporal sampling: The non-temporal model is 0.0371 ROC-AUC below the temporal version because it includes post-impression edges and leaks future information.
  • Temporal sampling: The binary-search temporal sampler reaches the same quality as naive temporal sampling while avoiding the naive scan’s approximately 2.5× slowdown.Both temporal samplers use the same pre-cutoff neighbor set N<τ(u).

6.5 System scalability

The deployed system fits the graph and trainable state across a single host while keeping serving latency near the production baseline. Online testing reports significant gains in direct friending and downstream content consumption.

  • Resource footprint: The 225 GB graph occupies host storage while the trainable parameter set fits on a single GPU because of multi-hash embeddings.
  • Online evaluation: The online treatment adds the GNN score to the previous production ranker in a two-week production-traffic A/B test.
  • Online results: +16.0% and +11.5% improve the two direct friending metrics, with both effects statistically significant at p < 0.01.
  • Online results: +0.28% increases total time spent in the content feed as a downstream effect reported by the experiment.
  • Serving cost: Ranker latency remains within noise of control because GNN scores are delivered through precomputed embeddings rather than request-time computation.

7 Discussion and Limitations

The system’s practical scope is shaped by cold-start users, offline GNN refreshes, and selective transfer to heterogeneous graphs. Periodic retraining and offline serving address operational constraints, while freshness and user representation remain bounded by the deployment setting.

  • Cold start and new users: Users joining after the training snapshot or inactive during training receive no direct learning signal from the multi-hash scheme.Periodic retraining on a fresh graph bounds the resulting cold window; upstream candidate generation serves these users between runs.
  • Non-real-time serving: Offline GNN embeddings avoid online multi-hop expansion and ranker latency, but become stale between scheduled refreshes.The paper considers this acceptable for slowly changing friendship signals, while continuously updated memory may better fit rapidly shifting interests.
  • Heterogeneous graphs: The temporal sampler transfers unchanged to heterogeneous graphs, while multi-hash representations apply selectively where node types lack strong content features.Each edge type can use timestamp-sorted CSR and binary-search cutoff queries with O(log du + K) cost.

8 Conclusion

The paper presents a production GNN ranking system for a 194M-user, 28B-edge graph built around multi-hash user representations and binary-search temporal sampling. In an online A/B test, it improved friend additions from recommendations by +16% and increased total content-feed time by +0.28%.

  • Conclusion: +16% friend additions from recommendations in an online A/B test, alongside +0.28% total time spent in the content feed.The released framework includes the temporal sampler, multi-hash embedding layer, and training and inference pipeline.
  • Conclusion: The system targets a huge graph with 194M users and 28B edges.Its two load-bearing design choices are multi-hash user-ID representations and binary-search-based temporal neighbor sampling.
  • Conclusion: The framework is released for teams building GNN rankers at industrial scale.The release covers native temporal sampling, multi-hash embeddings, and the training and inference pipeline.

GenAI Usage Disclosure

The authors used generative AI tools during manuscript preparation for language editing, alternative phrasings, structural feedback, and assistance with LaTeX snippets. The tools also assisted with selected runtime refactoring and training-launch scripts, while the core framework was written manually by the authors.

  • GenAI Usage Disclosure: Generative AI tools were used for language editing, alternative phrasings, structural feedback, and LaTeX-snippet assistance.
  • GenAI Usage Disclosure: The tools assisted with refactoring and adapting selected runtime components for open-source release.
  • GenAI Usage Disclosure: The tools assisted with writing parts of the training-launch scripts, while the core framework implementation was written manually by the authors.
Loading 2608.27413v1…