大规模异构图召回在美团到店推荐广告的应用

美团到店引荐广告团队在图神经网络的长时刻落地实践中，考虑剖析了场景的特色与应战，针对性地进行了模型规划，并经过大规划练习东西及线上布置优化屡次成功落地，带来了线上收入提高。本文首要介绍了大规划图召回技能在美团到店广告场景下的实践经验，包含模型规划思路、模型迭代历程、大规划练习东西以及线上布置功能优化等，希望为从事相关作业的读者带来一些启发。

1. 引言

美团到店引荐广告技能部服务于到店餐饮、休娱亲子、丽人医美等很多本地生活服务商家。其间，召回环节作为引荐广告体系的第一个环节，承担着从海量产品中寻觅优质候选的角色，是算法优化的核心问题之一。

引荐体系中经典的召回范式有两类：依据标签构建倒排索引的显式召回和依据模型端到端建模用户爱好的隐式召回。在隐式召回中，前史交互行为建模关于精确描写用户爱好非常要害。电商场景中，用户与商家、产品之间的交互联系适合经过图网络来表达。相较于传统模型，图神经网络能够构建用户与产品间的多种交互联系，然后凭借高阶网络结构的传递性合理扩大用户行为的丰厚度，将用户行为、用户根底特色和产品的内容特色等各种异质信息在一致的结构中进行交融，带来更大的作用空间。

美团到店引荐广告算法团队和NLP中心常识核算团队环绕图技能在引荐广告的运用进行了密切的协作，取得了线上作用的显著提高。本文首要介绍探究进程以及相关的实践经验。

2. 图神经网络简介

图作为包含节点自身和节点间边联系的调集，广泛存在于真实世界的多种场景中，例如交际网络中人与人之间的交际联系图、引荐体系中用户与产品的交互图等。图神经网络能捕捉节点和边的特征及其之间的拓扑联系，对图结构数据有很好的建模作用。引荐体系中常用的图神经网络模型能够分为两大类：依据图游走的办法和依据图卷积的办法。

依据图游走的办法：传统神经网络模型拿手处理欧式空间的数据，但难以建模图结构中包含的杂乱拓扑联系。因而，早期的研究者们提出了经过游走办法从图结构数据上采样序列，然后运用传统神经网络模型处理的直接计划，其间以DeepWalk^[1]，Node2vec^[2]等作业为典型代表。如下图1所示，这类办法侧重于在图中选用既定的游走策略生成节点序列，再运用NLP领域中的Skip-Gram模型练习得到每个节点的向量表征。

依据图卷积的办法：从图上采样序列进行建模的方法简略直接，但因为从原始图结构到序列的转换进程中存在信息丢掉，其作用存在较大的局限性，因而怎么将图结构直接建模到神经网络中成为了图神经网络研究的要害问题。研究者们结合谱域图上信号的傅里叶变换，界说了图上的卷积操作，并经过一系列的简化将谱图卷积和神经网络联系起来。

2017年Thomas等人提出的GCN^[3]是其间的代表作之一。图2为图结构至单层GCN公式的演化，其间A~\tilde{A}A~和D~\tilde{D}D~别离为参与自环的邻接矩阵及节点度矩阵，$X$为图节点特征矩阵，$W$为GCN模型的可练习参数，\sigma为激活函数（例如ReLU），$H$为图节点特征经过单层GCN网络后的输出特征。

GCN从整图的视点动身，打通了原始图结构和神经网络之间的壁垒，但巨大的核算量使其难以运用到大规划场景中。比较之下，GraphSAGE^[4]从图上节点的视点，提出了依据采样的音讯传递范式，使得图神经网络在大规划图上的高效核算变得可行。GraphSAGE中的SAGE指 SAmple and aggreGatE，即采样和聚合。下图3展现了GraphSAGE的采样聚合进程。图中左侧展现了对节点A运用两层采样器采样其一阶和二阶街坊，图中右侧展现了将采样得到的一阶二阶街坊的特征经过对应的聚合函数进行聚合，得到节点A的表征，然后能够运用A的表征核算包含节点分类、链接猜测及图分类在内的多种图相关的任务。

GraphSAGE等依据音讯传递范式的图神经网络办法，其间心节点能聚合到的特征规划取决于其采样的街坊阶数。在运用这类图神经网络练习时，除了运用节点的固有特征作为模型输入外，咱们还能够给每个节点参与独立可练习的向量参数，然后更好的学习到高阶街坊的相关性。

除了上述提到的办法外，图神经网络领域作为研究抢手之一，近年来不断涌现出GAT^[5]、FastGCN^[6]、GIN^[7]等优异算法，并在Pinterest^[8]、阿里巴巴^[9]、腾讯^[10]等公司的大规划引荐场景落地取得良好作用。

3. 事务场景及应战

到店引荐广告事务在流量侧首要覆盖美团/群众点评双侧的信息流广告、详情页广告等多种事务场景（如下图4所示），供应侧包含了餐饮、丽人医美、休闲娱乐、成婚、亲子等不同广告主品类，且每一个品类下包含商户、团单、泛产品等不同的引荐候选类型。

事务中召回模型建模面对以下两大应战：

a. 同场景反应数据稀少：传统序列行为建模计划依靠用户在同场景的反应数据构造正负样本进行模型练习，但用户在引荐广告场景的交互行为比较稀少，据统计超越一半的活跃用户在近90天内无广告点击行为，超越40%的广告产品在近一个月没有被点击。怎么处理反应数据稀少导致的用户爱好描写不精确、长尾产品学习不充分是咱们面对的一大应战。

b. LBS事务中不同时空场景下的爱好描写：到店事务中，用户在不同时刻、空间下的阅读行为，往往有着完全不同的偏好。例如一个用户作业日在公司邻近，或许感爱好的便是一次便利的作业餐；在假日的家中，则会想找一个风趣的遛娃去处。但传统的图神经网络缺乏对用户恳求时刻和所处方位的实时感知才能。因而怎么从图包含的丰厚信息中发掘出匹配当时时空场景的候选调集，同样是一大应战。

针对以上事务特色和应战，咱们规划了依据全场景数据高阶联系的大规划异构图建模，凭借全场景丰厚的行为数据优化稀少问题；并进一步强化时空信息感知，描写用户在不同时空上下文中的爱好。

4. 图召回技能在引荐广告的演进

4.1 依据全场景数据高阶联系的大规划异构图建模

团队之前的召回模型仅经过用户在广告场景的行为构造正负样本进行练习，这种方法提高了练习数据与猜测场景的一致性，但也不可防止地产生用户爱好描写不精确、长尾产品引荐作用较差等问题。特别是召回作为引荐体系最上游环节，决议了全链路作用优化上限，咱们希望凭借图神经网络包含的强壮表达才能，依据用户在全场景的行为数据全面描写用户爱好和产品信息。

如图5所示，图网络别离产出用户（User）和产品（Item）的隐式表征（Embedding），经过间隔相似度衡量用户对候选广告的潜在爱好。在图神经网络的选型上，咱们运用带Attention结构的GAT^[5]，使得街坊信息的贡献度能够依据其对源节点的重要性自适应调理，抑制误点击等带来的噪声；运用Jumping Knowledge Network^[11]，依据节点的衔接性自助调整其聚合网络规划，防止抢手节点因为其广泛的衔接性聚合规划过大丢掉了个性化信息。

全场景数据建模：为了全面发掘用户的爱好偏好，咱们经过全场景行为数据构建了超大规划异构图网络进行建模。此处的全场景涵盖全事务（查找、引荐、广告），全方位（主页、产品详情页、团单详情页）和全产品类型（商户、团单、泛产品等）。异构图包含用户（User）和产品（Item）两种类型节点，并经过三种类型的边进行衔接：User点击Item边、Item一起点击边以及Item同店铺边。

为了增强全场景数据包含的丰厚信息在各个场景间有用传递，同时区分出用户在广告场景独有的爱好特色。咱们在图构建进程中将广告场景和非广告场景的同个Item建模为不同节点，同享相同的非广告特征，但带有广告标识的节点会额外添加广告专属的特征。这样模型在练习进程中既能经过同享的特征搬迁非广告场景的信息，也能学习到用户在广告场景独有的爱好偏好。图构建完成后包含数亿节点、百亿边。

图裁剪与噪声抑制：上文提到的异构图因为涵盖了用户在全场景的行为数据，数据规划庞大，给实践落地带来了巨大的算力和功能应战。咱们发现在图的拓扑结构中，各个节点的度分布极不均匀，部分抢手节点的街坊个数可达几十万，因为练习进程中每个节点只采样固定个数的街坊参与核算，过多的街坊引进了许多噪声数据，也带来了不必要的资源开销。依据图数据背后的事务理解，咱们对原始拓扑结构进行合理裁剪。

具体来说：关于“User点击Item边”，保存行为时刻较近的topN条出边；关于“Item一起点击边”，保存边权重较高的topN条出边。图裁剪后，节点数量保持不变，边数量削减46%，练习内存开销下降30%，并带来了约0.68%的离线Hitrate作用提高。

动态负样本采样：因为广告商户在整体商户中占比较小，全场景行为数据的引进导致练习样本空间增大了一个数量级，这进一步加重了SSB（Sample Selection Bias）问题，负样本采样策略成为影响模型作用的要害因素。常见的随机负采样方法因为Hard Negative样本量不足，导致模型在实践猜测时泛化性较差。而静态负样本采样策略，例如LBS场景下常见的依据间隔、类目构建负样本，虽然能够取得必定作用提高，但通用性较差，策略装备繁琐，无法依据用户爱好搬迁自适应迭代。

以不同等级的城市为例，用户关于间隔、类目的偏好程度不同，需求设置不同的阈值。因而，咱们提出一种依据半监督学习的迭代式练习范式，将前一轮模型输出的商户Embedding经过KMeans进行聚类，在正样本所在的聚类调集中采样得到Hard Negative，参与到下一轮的练习样本中，依此步骤循环，引导模型不断“自我提高”。

试验发现，跟着迭代次序的添加，离线方针的边沿收益会收窄；考虑到练习速度与收益的平衡，线上咱们选用2轮迭代的方法。该优化比较随机负采样带来了约4.66%的离线Hitrate作用提高；比较静态负样本策略（如依据间隔、类目的采样）带来了约1.63%的离线Hitrate作用提高。

上述3个优化点的迭代在多个主广告位落地，并在衡量广告营收的RPS（Revenue Per Search）方针提高约5%~10%。

4.2 强化时空信息感知的端到端异构图建模

在LBS的事务中，时空信息是影响用户爱好的重要因素。用户通常具有安稳的长时刻爱好，但也会遭到当时时空信息影响而呈现出多变的短期爱好。因而，咱们在4.1节介绍的全场景异构图建模的根底上进行晋级。依据长时刻爱好安稳、短期爱好多变的特色，咱们选用针对性措施别离建模时空信息对长短期爱好的影响。

如下图9所示，咱们经过时空子图描写用户在不同时空场景下的长时刻爱好偏好，经过多因子协同激活的序列建模描写用户在短期时空场景下的爱好演化。值得注意的是，区别于将异构图预练习Embedding作为静态特征引进的两阶段练习方法，咱们将模型各部分在相同的优化方针下进行一阶段端到端练习，防止优化方针不一致带来的作用丢掉。

时空子图构建及多视角交融：用户在不同的时空下表现出不同的爱好，举例来说，一个用户或许在作业日的办公室订购咖啡，而在休息日的健身房参与运动。仅运用大局视角下的图模型提取用户大局爱好，容易丢掉用户在不同时空的爱好差异。传统图模型计划经过大局信息取得用户一致的爱好表征，无法精确描写用户在不同时空场景下爱好差异。

业界现已出现了一些结合时空信息的图表征学习方向的研究作业，如STGCN^[12]等。在相关作业的根底上，咱们从引荐广告的事务场景动身，依据用户行为对应的时刻和空间信息，从时刻、空间、时刻&空间、大局等4个视角构建子图，并经过多视角交融模块取得用户长时刻爱好。值得注意的是，一切子图同享Item2Item边，因为Item与Item的联系（好像店铺，一起点击等）较为安稳，不容易遭到时空变化的影响。

如下图10所示，当用户恳求到达时，从空间子图中取得用户在当时方位的爱好，从时刻子图中取得用户在多个时刻的爱好，从时刻&空间子图中取得用户在当时方位下多个时刻的爱好，并结合大局爱好及当时时刻，进行多视角交融。在实践中，咱们将时刻区分为早晨、下午、晚上、深夜等4个时刻段，将方位运用Geohash进行区分为多个地舆区域。据统计，每个用户的前史行为涉及到的时刻段和地舆区域均比较集中，并不会对存储空间形成过大的压力。时空子图的构建及交融带来了约3.65%的离线Hitrate提高。

多因子协同激活的用户序列建模：咱们将时刻信息（当时时刻与行为序列时刻的差值）、方位信息（当时方位与行为序列方位的差值）作为激活因子来激活短期行为序列，捕捉用户爱好随时空的搬迁趋势。此外，图神经网络输出的用户长时刻爱好向量，表现了用户在时刻、方位等维度较安稳的爱好偏好，也有利于从短期序列中提取出匹配当时时空场景的实时爱好。运用时空信息及用户长时刻爱好对用户短期行为序列进行激活时，涉及到多个因子协同激活的问题，业界常见的计划如下图11所示：

在美团LBS的事务场景中，各个激活因子之间或许会相互影响，例如时刻和地舆方位两种激活因子对行为序列激活的侧要点存在差异。为了让多因子激活发挥最佳作用，咱们结合离线方针挑选“多因子交融激活”模式。多因子协同激活的用户序列建模带来了约6.90%的离线Hitrate提高。

值得一提的是，图神经网络发掘的多阶联系能够丰厚用户序列的表达。这种多阶联系不只表现在产品和产品、用户和产品等粗粒度节点之间，也表现在时刻、方位、类目等细粒度特征之间。因而，咱们对特征产出流程进行了晋级改造，使图神经网络中的产品节点能够与用户行为序列在特征维度同享Embedding词典，并依据一致的优化方针端到端练习，帮助细粒度多阶信息更好地在图神经网络与用户序列间传递。

上述2个优化点的迭代在多个主广告位落地，并在衡量广告营收的RPS（Revenue Per Search）方针提高约5%。

5. 功能优化与运用

为了能够在大规划场景上线并进行实时召回，咱们针对模型的离线练习和在线布置进行了优化。

适配LBS场景的大规划图神经网络练习结构：跟着图神经网络在工业界的推行，开源社区涌现出一大批优异的图神经网络练习结构，如Euler、DGL等。咱们在开源结构的根底上，匹配公司内部大数据与机器学习渠道，研发出一套适配LBS场景的大规划图神经网络练习结构。该结构支持大规划图的构建、特征抽取等构图操作，并额外开发支持了包含“方位信息动态采样”在内的常见LBS图神经网络操作。经过该结构咱们已在多个事务场景落地线上模型，其间最大规划为亿等级节点、百亿等级边、带Side-information的图神经网络模型。

低推迟的在线核算流程：召回环节是广告引荐体系的第一个漏斗，需求在有限时刻内从全量候选广告中选出高质量子集传递给下流。鉴于子图查找、图卷积等杂乱操作对线上耗时的巨大应战，咱们提出了低推迟的在线核算流程优化计划：在4.2节介绍的模型中，图模型部分首要用来表征用户长时刻爱好，不受实时行为和恳求信息影响，因而，咱们将图节点Embedding离线核算好存入KV表中，防止图模型的在线推导成为耗时瓶颈；同时，在线恳求时并行处理图节点Embedding和其它特征的抽取进程。实践标明，经过以上优化召回环节线上耗时涨幅小于2%。

6. 总结与展望

图神经网络对图结构的数据有很好的建模才能，能充分利用图节点的高阶街坊信息，在大规划引荐体系的召回模块中展现出巨大潜力，业界头部公司均有结合各自事务特色的图模型落地实践^[8][9][10]。

本文介绍了大规划图召回技能在美团到店引荐广告的运用。依据对到店引荐广告场景特色的剖析，咱们在落地图召回技能时进行了对应的优化。在模型方面，为了处理广告反应数据稀少的问题，咱们将全场景的数据融入到图模型中丰厚用户爱好表达，并结合图裁剪和动态负样本采样技能，累计提高Hitrate约5.34%；为了加强对时空等LBS动态场景信息的感知，咱们经过时空子图模块描写用户在不同时空下的爱好，并进行多视角交融及长短期序列交融，累计提高约10.55%。合作离线练习及在线核算的功能优化，咱们成功在多个主广告位上落地，线上RPS累计提高10%~15%。

未来咱们还将在以下技能方向继续进行探究：

1. 多场景常识搬迁

到店广告场景很多，不同广告位保护不同的图召回模型带来的保护本钱较大。多场景的联合练习既能丰厚图数据，提高用户爱好的描写，又能将单个图召回模型运用到不同广告位，下降保护本钱。可是用户在不同广告位下的行为存在差异，数据交融不妥或许导致引进噪声，影响模型练习成果。怎么在模型规划中描写用户在不同广告位下行为的一起点和差异点，是需求要点考虑的内容。

2. 动态图技能

用户爱好跟着时刻空间不断发生着改变。动态图模型能够将时空等动态信息构建到图结构中，比较人为区分长时刻爱好与短期爱好，动态图能够更灵活地感知用户爱好的变化，更贴合LBS事务的特色。

7. 作者简介

• 齐裕、李根、少华、张腾、程佳、雷军，来自美团到店工作群/广告渠道技能部。
• 祥洲、梦迪、武威，来自美团渠道/查找引荐算法部NLP中心。

8. 参考资料

• [1] Perozzi, Bryan, Rami Al-Rfou, and Steven Skiena. “Deepwalk: Online learning of social representations.” Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 2014.
• [2] Grover, Aditya, and Jure Leskovec. “node2vec: Scalable feature learning for networks.” Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 2016.
• [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.
• [8] Ying, Rex, et al. “Graph convolutional neural networks for web-scale recommender systems.” Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining. 2018.
• [9] Wang, Menghan, et al. “M2GRL: A multi-task multi-view graph representation learning framework for web-scale recommender systems.” Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. 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.” International conference on machine learning. PMLR, 2018.
• [12] Han, Haoyu, et al. “STGCN: a spatial-temporal aware graph learning method for POI recommendation.” 2020 IEEE International Conference on Data Mining (ICDM). IEEE, 2020.

阅读美团技能团队更多技能文章合集

前端 | 算法 | 后端 | 数据 | 安全 | 运维 | iOS | Android | 测验

| 在公众号菜单栏对话框回复【2021年货】、【2020年货】、【2019年货】、【2018年货】、【2017年货】等要害词，可查看美团技能团队历年技能文章合集。

| 本文系美团技能团队出品，著作权归属美团。欢迎出于共享和沟通等非商业目的转载或运用本文内容，敬请注明“内容转载自美团技能团队”。本文未经许可，不得进行商业性转载或者运用。任何商用行为，请发送邮件至tech@meituan.com申请授权。