Large-Scale Graph Retrieval for Meituan In-Store Advertising: Design, Optimization, and Deployment

1. Introduction

Meituan's in‑store recommendation ad system serves local‑life merchants (dining, beauty, entertainment, etc.). The recall stage selects high‑quality candidates from massive items and is a key optimization point. Implicit recall models user interest via historical interactions, and graph neural networks (GNNs) can capture multi‑type user‑item relations to enrich behavior representation.

2. Graph Neural Network Overview

GNNs model node and edge features together with graph topology. Two main families are used in recommendation:

Graph‑walk based methods such as DeepWalk[1] and node2vec[2] that sample sequences and train a Skip‑Gram model.

Graph‑convolution methods such as GCN[3] and GraphSAGE[4] that aggregate neighbor information directly. GCN suffers from high computation on large graphs, while GraphSAGE’s sampling makes large‑scale training feasible.

Subsequent advances (GAT[5], FastGCN[6], GIN[7]) have been deployed in large‑scale recommender systems at Pinterest[8], Alibaba[9] and Tencent[10].

3. Business Scenario and Challenges

The ad product covers information‑flow ads and detail‑page ads across many merchant categories. Two major challenges arise in recall modeling:

Sparse feedback in the same scenario : >50 % of active users have no ad clicks in the past 90 days, and >40 % of ad items receive no clicks in a month, leading to inaccurate interest modeling and poor long‑tail coverage.

Spatiotemporal interest variation : Users’ preferences differ across time and location (e.g., work‑day coffee vs. weekend gym). Vanilla GNNs cannot perceive these variations in real time.

To address these, a large‑scale heterogeneous graph that incorporates full‑scene behavior data and enhances spatiotemporal awareness is built.

4. Evolution of Graph Recall Technology

4.1 Large‑Scale Heterogeneous Graph Modeling with Full‑Scene Data

Previous recall models used only ad‑scene interactions, causing sparse interest signals and weak long‑tail performance. The new approach constructs a massive heterogeneous graph covering all business (search, recommendation, ads), all locations (home, item detail, group‑deal detail) and all item types (merchant, group‑deal, generic product). Nodes are Users and Items; edges include User→Item clicks, Item↔Item co‑clicks, and Item↔Item same‑shop. Ads‑specific Item nodes carry additional ad‑only features while sharing non‑ad features with their non‑ad counterparts, enabling knowledge transfer. The graph contains billions of edges.

Graph pruning and noise reduction : Top‑N recent outgoing edges are kept for User→Item, and top‑N highest‑weight edges for Item↔Item. This reduces edge count by 46 %, cuts training memory by 30 %, and improves offline hit‑rate by ~0.68 %.

Dynamic negative‑sample sampling : An iterative semi‑supervised scheme clusters merchant embeddings with K‑means, then draws hard negatives from the same cluster. Two iterations yield ~4.66 % offline hit‑rate gain over random negatives and ~1.63 % over static distance‑based negatives.

These optimizations together raise Revenue‑Per‑Search (RPS) by 5 %–10 % in major ad slots.

4.2 End‑to‑End Heterogeneous Graph Modeling with Enhanced Spatiotemporal Perception

Long‑term interests are relatively stable, while short‑term interests shift with time and location. Four sub‑graphs are built for each user: time‑only, space‑only, time‑&‑space, and global. All sub‑graphs share Item‑Item edges, which are stable across contexts.

During inference, embeddings from the four views are fused using the current time segment (morning, afternoon, evening, night) and Geohash‑based location. Multi‑view fusion adds ~3.65 % offline hit‑rate.

Multi‑factor collaborative activation incorporates temporal difference (current time vs. sequence time) and spatial difference (current location vs. sequence location) as activation factors for short‑term behavior sequences, while the graph‑derived long‑term interest vector provides a stable preference backbone. This design yields ~6.90 % offline hit‑rate improvement.

Overall, spatiotemporal enhancements contribute an additional ~10.55 % offline hit‑rate gain, and combined with previous steps raise online RPS by 10 %–15 %.

5. Performance Optimization and Deployment

A custom large‑scale GNN training framework was built on top of open‑source engines (Euler, DGL). It supports graph construction, feature extraction, and LBS‑specific operations such as dynamic location sampling. The largest deployed model handles hundreds of millions of nodes and tens of billions of edges.

For low‑latency online recall, node embeddings are pre‑computed offline and stored in a KV table, eliminating costly graph inference at request time. Online requests parallelly fetch embeddings and other features, resulting in less than 2 % increase in latency.

6. Summary

Graph neural networks effectively model high‑order relationships in large‑scale recommendation recall. The system integrates full‑scene heterogeneous graphs, graph pruning, dynamic negative sampling, and spatiotemporal sub‑graph fusion, achieving cumulative offline hit‑rate improvements of ~5.34 % and online RPS gains of 10 %–15 %.

References

[1] Perozzi, Bryan, Rami Al‑Rfou, and Steven Skiena. "DeepWalk: Online learning of social representations." KDD 2014.

[2] Grover, Aditya, and Jure Leskovec. "node2vec: Scalable feature learning for networks." KDD 2016.

[3] Kipf, Thomas N., and Max Welling. "Semi‑supervised classification with graph convolutional networks." ICLR 2017.

[4] Hamilton, Will, Zhitao Ying, and Jure Leskovec. "Inductive representation learning on large graphs." NeurIPS 2017.

[5] Veličković, Petar, et al. "Graph attention networks." ICLR 2018.

[6] Chen, Jie, Tengfei Ma, and Cao Xiao. "FastGCN: Fast learning with graph convolutional networks via importance sampling." ICLR 2018.

[7] Xu, Keyulu, et al. "How powerful are graph neural networks." ICLR 2019.

[8] Ying, Rex, et al. "Graph convolutional neural networks for web‑scale recommender systems." KDD 2018.

[9] Wang, Menghan, et al. "M2GRL: A multi‑task multi‑view graph representation learning framework for web‑scale recommender systems." KDD 2020.

[10] Xie, Ruobing, et al. "Improving accuracy and diversity in matching of recommendation with diversified preference network." IEEE Transactions on Big Data 2021.

[11] Xu, Keyulu, et al. "Representation learning on graphs with jumping knowledge networks." ICML 2018.

[12] Han, Haoyu, et al. "STGCN: a spatial‑temporal aware graph learning method for POI recommendation." ICDM 2020.

Code example

[3] Welling, Max, and Thomas N. Kipf. "Semi-supervised classification with graph convolutional networks." J. International Conference on Learning Representations. ICLR, 2017.
[4] Hamilton, Will, Zhitao Ying, and Jure Leskovec. "Inductive representation learning on large graphs." Advances in neural information processing systems 30 (2017).
[5] Velickovic, Petar, et al. "Graph attention networks." International Conference on Learning Representations. 2018.
[6] Chen, Jie, Tengfei Ma, and Cao Xiao. "FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling." International Conference on Learning Representations. 2018.
[7] Xu, Keyulu, et al. "How powerful are graph neural networks." International Conference on Learning Representations. ICLR, 2019.