写点什么

大规模图算法在京东广告的实践

2021 年 6 月 15 日

大规模图算法在京东广告的实践

京东的 9N 算法框架已经被广泛应用于推荐广告、搜索广告、以及其他的站内外广告场景。本文将为大家介绍如何实现大规模的图算法在京东广告场景的落地实践,主要内容包括:

  • 基础介绍

  • 9N GRAPH 工业化 End2End 算法解决方案

  • 算法建模:BVSHG

  • 未来展望

基础介绍

1. 电商推荐问题的特点


电商场景下推荐系统的问题特点:

  • 用户的行为少:电商是一个典型的货多人少的场景,用户行为非常稀疏,且具有“极度长尾效应”,这个效应我们后面会展开详细讲。

  • 商品的规模大:前面说了货多人少,整个平台的商品规模能达到数十亿,算上冷门商品及历史商品的话,甚至能到百亿规模。对于推荐问题来说,数十亿的候选商品集合实在是太大了。对于工程同学,算法同学都是一个不小的挑战。

  • 用户的需求识别难:电商不像新闻、媒体类的场景,这些场景的用户需求和反馈都是来自于线上,比如某某上了热搜,这种场景下,信息源来自线上,用户的反馈也会作用于线上,相对单纯一些;而电商场景,大家的购物需求的产生和具体消费其实是在线下的,比如今天家里做饭少了一瓶酱油,这种信息,线上系统很难感知到。

  • 用户的兴趣转移快:用户的购买行为完成后,兴趣会呈现不规则的快速转移,举个例子,有些用户买了一台电冰箱,按道理说这是一个大件儿,重复购买的周期很长,日常生活中不会有人每天都去看,都去购买的,但是中国消费者有个奇特的行为,叫做“我再回去看看买亏了没”,没事儿就回去刷一下商品看看价格。再举一个有意思的例子,用户买了一部手机,那是不是有可能购买手机壳、手机膜这种搭配呢?确实有不少消费者这么干的,但如果赶上 618 大促节,你会发现用户的上一个行为是去买手机,下一个兴趣就是关于如何买拖把和抹布,这就是用户兴趣以及时效性带来的挑战。

  • 热点更新快:尤其是现代电商网站每天有新品,每周有活动,每月有节日,半年一大促,用户对新品的交互行为更为稀疏,想要让模型和算法学到甚至能有预测能力,简直难上加难。

2. Why GRAPH?


刚刚介绍了电商推荐的问题和难处,我们回到推荐的本质上来思考这个问题,对于推荐系统来说,其中的重要参与方就是用户和商品,而推荐系统的本质就是在找用户和商品的关联性:

  • 以用户方来说:人与人之间存在天然的关系图谱,不论是显式的这种朋友亲属还是隐式的社交关联等等,相信很多偏社交属性的公司早就深入研究过人与人之间的图关系了;

  • 以商品方来说:商品本身的材质、属性、价格本身就存在关联,甚至是同品牌、店铺、竞品的关联关系等等,通常很多偏新闻和资讯类的公司早就已经构建了知识图谱。


能否将用户图和商品图连通起来,利用用户和商品关联性,构建成一张充满不同关系边的图?这就是一张简单的 U-I 二部图,如上所示。

9N GRAPH 工业化 End2End 算法解决方案


如何把这张 U-I 图在工业场景下完成落地和应用?我们实现了一整套 9N GRAPH 工业化端到端的算法解决方案,它不仅包含数据能力、算法框架、算法模型还有一系列的应用。


实现工业化场景的端到端学习,我们遇到了不少挑战,这里举几点出来:

  • 在数据和样本层面,我们遇到了超大规模的图样本生成及存储问题、图的在线服务以及服务内图信息时效性的问题。

  • 在训练框架层面:如何实现一个训练框架,以及大规模图如何在工业场景中训练,我们基于 9N Lite 框架进行了延伸开发,实现了 9N GL ( 即 Graph Learning )。

  • 算法建模层面:如何解决端到端建模以及主模型和图模型联合训练,我们提出了一个典型建模方法,最终也在业务场景上落地取得了收益。


9N GRAPH 的整体方案如右图所示,它包含 6 个层次,图中暗黄色的部分包含图学习的多元化,图的探索和创新,是我们还在进行中的部分,其他颜色部分已经在提供稳定服务了,其中浅黄色是在线工程团队帮助我们一起建设的在线图服务。

1. 9N GRAPH 数据 &样本

① 如何实现大规模的图样本生成及存储问题?



通过对电商场景的用户行为进行分析,我们发现:行为数据呈现“极度长尾效应”,换句话说是“旱的旱死,涝的涝死”。像图中呈现的,在 99 分位数之上的用户行为居然差不多等于剩下的所有用户行为之和。

这种现象,对于传统的深度学习来讲,其实很不友好,传统的深度学习建模方法,和训练策略比较适用于中高活跃的用户,他们的行为数据较多,但又不过分集中,在多轮迭代的训练方式下,数据利用效果好。

反过来看,对于 99 分位数之上的那些极度活跃用户,他们的行为数据过于丰富 ( 比如单日浏览了好几百个上千个商品 ),在工业场景上通常会因为工程性能问题做出截断,导致仅有少数最近期的行为信息参与在线预估,反而会导致建模失真,效果不佳。


对于长尾用户,他们的行为稀疏,甚至还有不少的噪声,建模较难,数据利用的效果也很差。

我们希望用图的方式,解决这两类数据失真的问题:

  • 对于极度活跃用户:我们通过图的方式记录下来他的行为,在进行预估时,通过各种采样的方法,让采出来的信息不像截断那样仅包含最近期的,还有大量长期的信息。

  • 对于长尾用户:通过图的方式进行不同层面的信息抽取,增加泛化能力,增强对长尾用户的建模能力。


以最简单 U-I 二部图为例,我们将用户大量的历史行为,通过 U-I 关系抽取模块,建立起图关系数据差不多有 400TB 左右;又通过训练日志进行 label 处理,两者进行关联后,形成图训练样本,通常能达到 800-1000TB;然后送入到模型训练框架中,进行主模型和图模型的联合训练。


② 如何解决图服务及信息时效性问题?


高实时的信息可以带来不小的效果提升,因此在线的服务中除了需要包含历史长期的图信息外,还要对最近期的信息有感知,所以我们设计并实现了一套秒级别更新的在线服务。如上图所示,上面一条通路是包含数月信息的长期图信息,下面的这一条通路是秒级别的实时信息更新,最终打造成了一个高时效性的图数据服务系统。

2. 9N Lite 算法框架 Overview


接下来看如何实现一个训练框架,以及大规模图如何在工业场景中训练问题。


我们在介绍大规模图训练前,先介绍下 9N ( 即九数 ) 算法框架整体,因为图训练也是基于这一套实现的。


九数算法框架是一个使用 Tensorflow 作为后端计算引擎的、深度定制的、支持弹性扩展和高性能推理服务的算法框架。它基于广告精排的任务特点研发的,支持了数年来京东广告的高速迭代发展。它包含四大基础设施:


  • 模型数据流:流批一体、离在线一体化的高性能数据流系统

  • 算子库:解决了特征系统及多模态、多业务的高性能实现

  • 核心训练框架:支持了多种业务场景,9N Lite 中不仅支持了复杂的有监督深度学习,还额外扩展支持了 9N RL 强化学习、9N OL 在线学习、9N FL 联邦学习、9N GL(图学习)。

  • NormGuard ( 一站式模型管理、检测、推送平台 ):是模型管控中心,也是一站式模型检测及推送中心,还支持了模型指标的异常检测等等。

3. 9N GRAPH End2End 训练


如右图所示,从下向上看,整个 9N GL 框架做了多个层级的模块抽象,通过 subgraph 的方式,抽象出了训练日志相关的子图结构,通过 unify interface 抽象出了各种图算子,通过 encoder 抽象了多种信息聚合方式;


整个 9N GL 将外部数据与样本关联的图信息抽象成了 SubGraph,支持多种不同形式的 SubGraph,不仅可以支持数据样本级别,甚至可以直接关联到在线检索系统甚至图引擎。


9N GL 也支持多种方式的主模型+图模型训练模式,多阶段训练以及端到端联合训练。



9N GL 中的 API 设计相对简单易用,主要包含有几个层次的训练接口:

  • 图结构的点、边设计,支持多种行为类型,属性类型

  • 图的采样方法种类包含有随机、带权、Meta-Path 等等

  • 图算法层面包含有常见的 GNN 和 Graph  Embedding 两大类

左侧是一段实例代码,仅需简单的函数调用,即可完成图解析,图邻居获取等操作。

4. 图在推荐、电商场景的典型 End2End 建模思路


接下来,向大家介绍一下图在推荐、广告场景中的典型端到端建模思路。


以 CTR 模型为例,在信息源部分引入用户和商品的交互图结构化信息,通过图的统一操作接口获取出建模所需要的图特征,然后经过特征编码器编码为常见的 id 类特征,后续可以通过一系列的 Graph Encoder 获取到用户、商品的高阶关系表征。


此外,在异构图网络中,我们可以对不同语义空间进行节点信息聚合,来捕捉到用户的潜在行为意图。

当然,以上是一个常见的 End2End 联合建模、联合训练的思路。接下来的部分,给大家详细介绍我们提出的一个具体模型 BVSHG 是如何做的。

BVSHG

1. BVSHG:业界常见图算法 Graph Embedding


我们在详细介绍 BVSHG 模型之前,还是先来看一下业界常见的图算法和图应用。


首先是 Graph Embedding 类算法,顾名思义,GE 类的算法本质上就是将低阶特征进行 Embedding 化,业界常用的有 DeepWalk、Node2Vec、LINE、EGES,他们的思路大同小异,如下图举例来说:

  • 将用户的行为序列按某种标准拆分

  • 将拆分后的 item 构建一张同质图

  • 在图上随机游走,生成不同的游走序列/游走词

  • 按不同应用送入到类似于 Skip-Gram 的结构中


但这种做法通常适用于无监督学习,其监督信号与最终目标通常不一致,只适用于多阶段训练。也没有充分发掘高阶的潜在关联关系。

2. BVSHG:业界常见图算法 Graph Neural Network


我们再来看下 GNN 系列的常见算法和模型。


主要有这几类:U-I 二部图、用户 session 图、社交网络、知识图谱。


在建模中也通常是围绕 U-U、U-I、I-I 三大类关系进行特征及属性关系挖掘。但他的好处是可以结合最终建模的目标进行端到端学习。

3. BVSHG:Multi-behavior Multi-view Session-based Heterogeneous GNN


以上的两类建模适用场景不同,我们在其中发现存在一些不足,如:

  • 朴素的 U-I 关系图中并没有充分利用 Side Information(如商品的类别,商品的品牌、商家店铺等等)

  • U-I 之间的关系类型很丰富,不仅仅是常见的点击、购买关系,在用户与商品的长期交互中,往往存在加购、分享、打赏、点赞、收藏等等。

  • 常见的 Session-Based Transformer 建模,并没有考虑 Item 间丰富的关联关系,也没有考虑 session 之间的关系。

  • 针对我们之前跟大家提及的“极度长尾效应”,不同用户的行为序列长短差距很大,在工业化场景下,出现的效果与性能 Trade-off 难题。


而我们非常贪心地希望既要对短期用户行为序列建模,又要对长期用户商品交互信息的多视图抽取,还要在一定程度上解决序列化建模带来的性能挑战。


作为成年人,想全都要!因此我们提出了 BVSHG,即 Multi-behavior Multi-view Session-based Heterogeneous GNN 建模方式。它的大致示意图如下,左侧为图信息的构建,右侧为图建模方式图,接下来我们会分部分详细讲讲。


① BVSHG:Long-term Multi-Behavior Session Heterogeneous Graph



首先,我们重点讲讲如何构建的这一张长期用户多种行为 session-based 异构图。


这是一张多元异构图,在图中你可以看到至少 4 类节点,比如红色的 User 节点,蓝色的 Item 节点,黄色的 Category 节点,绿色的 Brand 节点等等。


此外,构图时,我们采用了用户和商品、类目、品牌之间复杂的交互关系,比如上方的这个白色框中描述的是我们构建图时候用了用户的长期浏览 session 关系,比如 session1 中包含 item 序列,对应的 category 序列,对应的 brand 序列;


下方的框中,描述的是我们采用了用户的长期复杂行为数据,比如 User1 分享了 Item4,也就分享了对应的类目 C3 和对应的品牌 B3;


在右侧的图中,可以看出来,U1 对 I1、I2、I3 都有浏览边连接,但是对于 I4 有 share 分享边链接,U2 对 I3 有 AddCart 加购边链接。而图中的 I1、I2、I3 之间由于存在同一个 session 内,有共同出现的关系,有共现边。


右侧中间的图描述的是 User 跟类目之间的边情况,右下方的图描述的是用户和品牌之间的边的情况。

在此特别说明的是,我们只有一张包含多种节点、多种行为边的异构大图,右侧的三个小图,是在大图中截取的一小段示意图。


当然了,在构建这张大图的时候,我们也有一些超参数需要调节,比如 session 切分的时间准则,通常采用 30min 作为 gap,但是并不是最优。


② BVSHG:Multi-Behavior Sample



这一页我们的模型分为三个部分:

  • 传统主模型部分,包含有 UserFeature、ItemFeature、ContextFeature 经过像 DCN 等经典结构后,计算出一个 Embedding

  • 图模型输出一个 Embedding

  • 短期用户 session 信息经过 Transformer 输出一个 Embedding


将上述 3 个 Embedding Concat 在一起,最终经过 MLP 输出 pCTR。


我们先重点介绍红框中的部分,这部分是我们的 TargetUser 从我们的大图中采样找到的交互过的 Item,排成一个 list,用作 target user 的一种表达,也可以简单理解为 1 阶邻居。


对于 target user,我们首先采用 Behavior-Weighted Random Sample 的方式采样得到他的一跳 item 邻居,具体而言,该采样方式通过业务自定义的行为权重,对用户的不同行为类型的邻居节点进行加权的随机采样。而对于 target item 以及第一次采样得到的 user 的一跳 item 邻居,我们采用同质采样(Homogeneous Sample)的方式,从图中得到相同类型的邻居节点。


③ BVSHG:Multi-View Attention-Based Item SAGE



现在,我们重点介绍 BVSHG 的精髓,Multi-View 信息的抽取和 Attention 玩法。


对应到上方的 I1,我们在大图中,找到 I1 的 i-i 关系表征,也找到 I1 对应的类别 C 的 c-c 关系表征,同理,我们也找到了 I1 对应的品牌 B 的 b-b 关系表征,这三段向量与 I、C、B 构建出相应的 Attention 变换后 concat 在一起,形成一个 O。


同理,I2、I3 到 In 形成 O2、O3 到 On


同理,TargetItem It 形成 Ot,将 O1~On 的向量与 Ot 进行 Attention 计算。


④ BVSHG:Transformer-based Short-term Behavior Modeling



上图的红色框中,我们仍然借用 Transformer 对用户的短期行为 local session 进行序列关系的抽取,用来提取短期兴趣。


我们的 BVSHG 的思路大致介绍完毕了,模型结构虽然复杂,但是建模思路比较清晰容易理解。

4. 业务效果


我们将 BVSHG 模型在京东推荐广告的精排场景进行了实验,模型的点击消费有相应上涨。当然模型结构也可以作为抛砖引玉,图表征信息与主模型可以采用多种方式进行交互作用,End2End 训练。

5. 图算法的其他玩法


我们再来看看我们尝试过的其他图算法的玩法:

  • 我们借助实时图,建立了 User Item 之间的二部图,并实时更新图内点边关系,从中发掘出了连通的节点簇,我们以最大团、正则化割构成更加合理的兴趣簇的分类标准。

  • 在工业化场景上,很多时候,数据中是存在缺失和错误的,我们利用了 U-I、U-C 的事实图,两者进行联合修正,对数据做了增强和清洗。

未来展望


未来展望,我们最近一年在图上玩了不少花样,但总起来看,还有两个点我们还有很强的兴趣继续探索:

  • AutoML on Graph,由于我们构建一张图,进行联合建模的试验调试成本高,尤其是在超参的调试上耗费了不少人力,亟待一个可以解放人力的超参调整方法,我们后续希望借助 AutoML 的方法用资源换人力加快实验迭代速度。

  • 基于图的强化学习,开篇我们找到了推荐系统的本质问题是在解决用户和商品之间的关联关系,但这种关联关系既有短期的、也有长期的,但业务评价标准更多是短期内能带来多少点击、多少商品购买,很难对长期的奖励进行评估和建模,我们目前正在结合 RL 的方法,对用户长期购物路径、对京东购物的喜好性分析、品牌影响力分析等等问题进行尝试中。


我们一系列关于广告、推荐算法的探索及工程实践将不止于图,9N AI 团队后续也会尝试通过开源或分享的方式进一步与同行更好地交流和互相学习。


嘉宾介绍:

张泽华

京东 | 算法工程师

毕业于中科院软件研究所,目前是京东 9N AI 负责人,京东广告大规模机器学习框架作者,九数商业分析平台研发负责人,负责京东广告算法创新工作,其创新算法广泛应用于京东推荐广告、搜索广告等场景。


本文转载自:DataFunTalk(ID:dataFunTalk)

原文链接:大规模图算法在京东广告的实践

2021 年 6 月 15 日 14:001007

评论

发布
暂无评论
发现更多内容

架构师训练营第二周总结

一剑

极客时间架构师训练营 - week2 - 作业1

jjn0703

极客大学架构师训练营

架构师训练营——Week2作业

Shawn

架构师训练营第2周作业

风吹

面试官:线程池如何按照core、max、queue的执行循序去执行?(内附详细解析)

一枝花算不算浪漫

jdk源码 线程池 Java 面试

LinkedList竟然比ArrayList慢了1000多倍?(动图+性能评测)

王磊

Java 数据结构 性能优化 性能 链表

认识依赖倒置原则(DIP)

极客大学架构师训练营 第二周作业

重学 Java 设计模式:实战享元模式「基于Redis秒杀,提供活动与库存信息查询场景」

小傅哥

设计模式 小傅哥 重构 代码坏味道 代码优化

软件开发:软件设计的基本原则

WANDEFOUR

极客大学架构师训练营

架构师训练营-课后作业-Week-2

Chasedreamer

一文讲透SpringMVC

知春秋

spring springmvc Servlet

Flink on Zeppelin (1)入门篇

章剑锋_Jeff

大数据 flink 流计算 Zeppelin

ARTS-Week Four

shepherd

Java algorithm

别教我女儿该怎么穿,教你儿子别去强奸

小天同学

教育 日常思考 个人感悟 自我保护

CDN百科第四讲 | 如何优雅地在云上“摆摊”——做直播带货,你不得不关注的技术

阿里云Edge Plus

CDN 边缘计算 直播 直播带货

极客时间架构师训练营 - week2 - 作业2

jjn0703

极客大学架构师训练营

【大厂面试05期】说一说你对MySQL中锁的理解?

NotFound9

Java MySQL 后端

架构师训练营第二周作业

一剑

小师妹学JVM之:JVM的架构和执行过程

程序那些事

Java JVM 「Java 25周年」 小师妹 性能调优

Websocket直播间聊天室教程 - GoEasy快速实现聊天室

GoEasy消息推送

直播 websocket 即时通讯 聊天室 弹幕

数字产品开发那些事

涛哥

产品开发 数字化

漫画 | 啊哈,给我一碗孟婆汤

码农神说

程序员 测试 互联网人 设计师

618 将至,融云通信云技术如何助力电商销售

Geek_116789

编译Spring5.2.0源码

CoderLi

Java spring 程序员 后端 Java 25 周年

学习总结-编程本质与架构设计原则

飞雪

ARTS-WEEK2

Allen

思维模型 - 组合式创新

石云升

思维模型 组合式创新 拆解组合

架构师训练营作业(二)

Glowry

极客大学架构师训练营

作为CEO你比员工厉害吗?

Neco.W

创业 创业者 CEO

为什么你的简历石沉大海,offer 了无音讯?

非著名程序员

程序员 程序人生 提升认知 简历优化 简历

架构师训练营第 2 周——学习总结

在野

极客大学架构师训练营

技术为帆,纵横四海- Lazada技术东南亚探索和成长之旅

技术为帆,纵横四海- Lazada技术东南亚探索和成长之旅

大规模图算法在京东广告的实践-InfoQ