共计 8917 个字符，预计需要花费 23 分钟才能阅读完成。
美团到店举荐广告团队在图神经网络的长期落地实际中，思考剖析了场景的特点与挑战，针对性地进行了模型设计，并通过大规模训练工具及线上部署优化屡次胜利落地，带来了线上支出晋升。本文次要介绍了大规模图召回技术在美团到店广告场景下的实践经验，包含模型设计思路、模型迭代历程、大规模训练工具以及线上部署性能优化等，心愿为从事相干工作的读者带来一些启发。
1. 引言
美团到店举荐广告技术部服务于到店餐饮、休娱亲子、丽人医美等泛滥本地生存服务商家。其中，召回环节作为举荐广告零碎的第一个环节，承当着从海量商品中寻找优质候选的角色，是算法优化的外围问题之一。
举荐零碎中经典的召回范式有两类：基于标签构建倒排索引的显式召回和基于模型端到端建模用户趣味的隐式召回。在隐式召回中，历史交互行为建模对于精确刻画用户趣味十分要害。电商场景中，用户与商家、商品之间的交互关系适宜通过图网络来表白。相较于传统模型，图神经网络能够构建用户与商品间的多种交互关系，而后借助高阶网络结构的传递性正当裁减用户行为的丰盛度，将用户行为、用户根底属性和商品的内容属性等各种异质信息在对立的框架中进行交融，带来更大的成果空间。
美团到店举荐广告算法团队和 NLP 核心常识计算团队围绕图技术在举荐广告的利用进行了亲密的单干，取得了线上成果的显著晋升。本文次要介绍摸索过程以及相干的实践经验。
2. 图神经网络简介
图作为蕴含节点本身和节点间边关系的汇合，宽泛存在于真实世界的多种场景中，例如社交网络中人与人之间的社交关系图、举荐零碎中用户与商品的交互图等。图神经网络能捕获节点和边的特色及其之间的拓扑关系，对图构造数据有很好的建模成果。举荐零碎中罕用的图神经网络模型能够分为两大类：基于图游走的办法和基于图卷积的办法。
基于图游走的办法 ：传统神经网络模型善于解决欧式空间的数据，但难以建模图构造中蕴含的简单拓扑关系。因而，晚期的研究者们提出了通过游走办法从图构造数据上采样序列，而后应用传统神经网络模型解决的间接计划，其中以 DeepWalk[1]，Node2vec[2] 等工作为典型代表。如下图 1 所示，这类办法侧重于在图中采纳既定的游走策略生成节点序列，再应用 NLP 畛域中的 Skip-Gram 模型训练失去每个节点的向量表征。
基于图卷积的办法：从图上采样序列进行建模的形式简略间接，但因为从原始图构造到序列的转换过程中存在信息损失，其成果存在较大的局限性，因此如何将图构造间接建模到神经网络中成为了图神经网络钻研的关键问题。研究者们联合谱域图上信号的傅里叶变换，定义了图上的卷积操作，并通过一系列的简化将谱图卷积和神经网络分割起来。
2017 年 Thomas 等人提出的 GCN[3]是其中的代表作之一。图 2 为图构造至单层 GCN 公式的演变，其中 $\tilde{A}$ 和 $\tilde{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[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 申请受权。