大規(guī)模圖算法在京東廣告的實(shí)踐
分享嘉賓：張澤華 京東 算法工程師
編輯整理：王文婧
出品平臺：DataFunTalk
導(dǎo)讀：京東的9N算法框架已經(jīng)被廣泛應(yīng)用于推薦廣告、搜索廣告、以及其他的站內(nèi)外廣告場景。本文將為大家介紹如何實(shí)現(xiàn)大規(guī)模的圖算法在京東廣告場景的落地實(shí)踐，主要內(nèi)容包括：
基礎(chǔ)介紹
9N GRAPH工業(yè)化End2End算法解決方案
算法建模：BVSHG
未來展望
01
基礎(chǔ)介紹
1. 電商推薦問題的特點(diǎn)
電商場景下推薦系統(tǒng)的問題特點(diǎn)：
用戶的行為少：電商是一個(gè)典型的貨多人少的場景，用戶行為非常稀疏，且具有“極度長尾效應(yīng)”，這個(gè)效應(yīng)我們后面會展開詳細(xì)講。
商品的規(guī)模大：前面說了貨多人少，整個(gè)平臺的商品規(guī)模能達(dá)到數(shù)十億，算上冷門商品及歷史商品的話，甚至能到百億規(guī)模。對于推薦問題來說，數(shù)十億的候選商品集合實(shí)在是太大了。對于工程同學(xué)，算法同學(xué)都是一個(gè)不小的挑戰(zhàn)。
用戶的需求識別難：電商不像新聞、媒體類的場景，這些場景的用戶需求和反饋都是來自于線上，比如某某上了熱搜，這種場景下，信息源來自線上，用戶的反饋也會作用于線上，相對單純一些；而電商場景，大家的購物需求的產(chǎn)生和具體消費(fèi)其實(shí)是在線下的，比如今天家里做飯少了一瓶醬油，這種信息，線上系統(tǒng)很難感知到。
用戶的興趣轉(zhuǎn)移快：用戶的購買行為完成后，興趣會呈現(xiàn)不規(guī)則的快速轉(zhuǎn)移，舉個(gè)例子，有些用戶買了一臺電冰箱，按道理說這是一個(gè)大件兒，重復(fù)購買的周期很長，日常生活中不會有人每天都去看，都去購買的，但是中國消費(fèi)者有個(gè)奇特的行為，叫做“我再回去看看買虧了沒”，沒事兒就回去刷一下商品看看價(jià)格。再舉一個(gè)有意思的例子，用戶買了一部手機(jī)，那是不是有可能購買手機(jī)殼、手機(jī)膜這種搭配呢？確實(shí)有不少消費(fèi)者這么干的，但如果趕上618大促節(jié)，你會發(fā)現(xiàn)用戶的上一個(gè)行為是去買手機(jī)，下一個(gè)興趣就是關(guān)于如何買拖把和抹布，這就是用戶興趣以及時(shí)效性帶來的挑戰(zhàn)。
熱點(diǎn)更新快：尤其是現(xiàn)代電商網(wǎng)站每天有新品，每周有活動(dòng)，每月有節(jié)日，半年一大促，用戶對新品的交互行為更為稀疏，想要讓模型和算法學(xué)到甚至能有預(yù)測能力，簡直難上加難。
2. Why GRAPH？
剛剛介紹了電商推薦的問題和難處，我們回到推薦的本質(zhì)上來思考這個(gè)問題，對于推薦系統(tǒng)來說，其中的重要參與方就是用戶和商品，而推薦系統(tǒng)的本質(zhì)就是在找用戶和商品的關(guān)聯(lián)性：
以用戶方來說：人與人之間存在天然的關(guān)系圖譜，不論是顯式的這種朋友親屬還是隱式的社交關(guān)聯(lián)等等，相信很多偏社交屬性的公司早就深入研究過人與人之間的圖關(guān)系了；
以商品方來說：商品本身的材質(zhì)、屬性、價(jià)格本身就存在關(guān)聯(lián)，甚至是同品牌、店鋪、競品的關(guān)聯(lián)關(guān)系等等，通常很多偏新聞和資訊類的公司早就已經(jīng)構(gòu)建了知識圖譜。
能否將用戶圖和商品圖連通起來，利用用戶和商品關(guān)聯(lián)性，構(gòu)建成一張充滿不同關(guān)系邊的圖？這就是一張簡單的U-I二部圖，如上所示。
如何把這張U-I圖在工業(yè)場景下完成落地和應(yīng)用？我們實(shí)現(xiàn)了一整套9N GRAPH工業(yè)化端到端的算法解決方案，它不僅包含數(shù)據(jù)能力、算法框架、算法模型還有一系列的應(yīng)用。
實(shí)現(xiàn)工業(yè)化場景的端到端學(xué)習(xí)，我們遇到了不少挑戰(zhàn)，這里舉幾點(diǎn)出來：
在數(shù)據(jù)和樣本層面，我們遇到了超大規(guī)模的圖樣本生成及存儲問題、圖的在線服務(wù)以及服務(wù)內(nèi)圖信息時(shí)效性的問題。
在訓(xùn)練框架層面：如何實(shí)現(xiàn)一個(gè)訓(xùn)練框架，以及大規(guī)模圖如何在工業(yè)場景中訓(xùn)練，我們基于9N Lite框架進(jìn)行了延伸開發(fā)，實(shí)現(xiàn)了9N GL ( 即Graph Learning )。
算法建模層面：如何解決端到端建模以及主模型和圖模型聯(lián)合訓(xùn)練，我們提出了一個(gè)典型建模方法，最終也在業(yè)務(wù)場景上落地取得了收益。
9N GRAPH的整體方案如右圖所示，它包含6個(gè)層次，圖中暗黃色的部分包含圖學(xué)習(xí)的多元化，圖的探索和創(chuàng)新，是我們還在進(jìn)行中的部分，其他顏色部分已經(jīng)在提供穩(wěn)定服務(wù)了，其中淺黃色是在線工程團(tuán)隊(duì)幫助我們一起建設(shè)的在線圖服務(wù)。
1. 9N GRAPH數(shù)據(jù)&樣本
① 如何實(shí)現(xiàn)大規(guī)模的圖樣本生成及存儲問題？
通過對電商場景的用戶行為進(jìn)行分析，我們發(fā)現(xiàn)：行為數(shù)據(jù)呈現(xiàn)“極度長尾效應(yīng)”，換句話說是“旱的旱死，澇的澇死”。像圖中呈現(xiàn)的，在99分位數(shù)之上的用戶行為居然差不多等于剩下的所有用戶行為之和。
這種現(xiàn)象，對于傳統(tǒng)的深度學(xué)習(xí)來講，其實(shí)很不友好，傳統(tǒng)的深度學(xué)習(xí)建模方法，和訓(xùn)練策略比較適用于中高活躍的用戶，他們的行為數(shù)據(jù)較多，但又不過分集中，在多輪迭代的訓(xùn)練方式下，數(shù)據(jù)利用效果好。
反過來看，對于99分位數(shù)之上的那些極度活躍用戶，他們的行為數(shù)據(jù)過于豐富 ( 比如單日瀏覽了好幾百個(gè)上千個(gè)商品 )，在工業(yè)場景上通常會因?yàn)楣こ绦阅軉栴}做出截?cái)?，?dǎo)致僅有少數(shù)最近期的行為信息參與在線預(yù)估，反而會導(dǎo)致建模失真，效果不佳。
對于長尾用戶，他們的行為稀疏，甚至還有不少的噪聲，建模較難，數(shù)據(jù)利用的效果也很差。
我們希望用圖的方式，解決這兩類數(shù)據(jù)失真的問題：
對于極度活躍用戶：我們通過圖的方式記錄下來他的行為，在進(jìn)行預(yù)估時(shí)，通過各種采樣的方法，讓采出來的信息不像截?cái)嗄菢觾H包含最近期的，還有大量長期的信息。
對于長尾用戶：通過圖的方式進(jìn)行不同層面的信息抽取，增加泛化能力，增強(qiáng)對長尾用戶的建模能力。
以最簡單U-I二部圖為例，我們將用戶大量的歷史行為，通過U-I關(guān)系抽取模塊，建立起圖關(guān)系數(shù)據(jù)差不多有400TB左右；又通過訓(xùn)練日志進(jìn)行l(wèi)abel處理，兩者進(jìn)行關(guān)聯(lián)后，形成圖訓(xùn)練樣本，通常能達(dá)到800-1000TB；然后送入到模型訓(xùn)練框架中，進(jìn)行主模型和圖模型的聯(lián)合訓(xùn)練。
② 如何解決圖服務(wù)及信息時(shí)效性問題？
高實(shí)時(shí)的信息可以帶來不小的效果提升，因此在線的服務(wù)中除了需要包含歷史長期的圖信息外，還要對最近期的信息有感知，所以我們設(shè)計(jì)并實(shí)現(xiàn)了一套秒級別更新的在線服務(wù)。如上圖所示，上面一條通路是包含數(shù)月信息的長期圖信息，下面的這一條通路是秒級別的實(shí)時(shí)信息更新，最終打造成了一個(gè)高時(shí)效性的圖數(shù)據(jù)服務(wù)系統(tǒng)。
2. 9N Lite 算法框架 Overview
接下來看如何實(shí)現(xiàn)一個(gè)訓(xùn)練框架，以及大規(guī)模圖如何在工業(yè)場景中訓(xùn)練問題。
我們在介紹大規(guī)模圖訓(xùn)練前，先介紹下9N ( 即九數(shù) ) 算法框架整體，因?yàn)閳D訓(xùn)練也是基于這一套實(shí)現(xiàn)的。
九數(shù)算法框架是一個(gè)使用Tensorflow作為后端計(jì)算引擎的、深度定制的、支持彈性擴(kuò)展和高性能推理服務(wù)的算法框架。它基于廣告精排的任務(wù)特點(diǎn)研發(fā)的，支持了數(shù)年來京東廣告的高速迭代發(fā)展。它包含四大基礎(chǔ)設(shè)施：
模型數(shù)據(jù)流：流批一體、離在線一體化的高性能數(shù)據(jù)流系統(tǒng)
算子庫：解決了特征系統(tǒng)及多模態(tài)、多業(yè)務(wù)的高性能實(shí)現(xiàn)
核心訓(xùn)練框架：支持了多種業(yè)務(wù)場景，9N Lite中不僅支持了復(fù)雜的有監(jiān)督深度學(xué)習(xí)，還額外擴(kuò)展支持了9N RL強(qiáng)化學(xué)習(xí)、9N OL在線學(xué)習(xí)、9N FL聯(lián)邦學(xué)習(xí)、9N GL（圖學(xué)習(xí)）。
NormGuard ( 一站式模型管理、檢測、推送平臺 )：是模型管控中心，也是一站式模型檢測及推送中心，還支持了模型指標(biāo)的異常檢測等等。
3. 9N GRAPH End2End 訓(xùn)練
如右圖所示，從下向上看，整個(gè)9N GL框架做了多個(gè)層級的模塊抽象，通過subgraph的方式，抽象出了訓(xùn)練日志相關(guān)的子圖結(jié)構(gòu)，通過unify interface抽象出了各種圖算子，通過encoder抽象了多種信息聚合方式；
整個(gè)9N GL將外部數(shù)據(jù)與樣本關(guān)聯(lián)的圖信息抽象成了SubGraph，支持多種不同形式的SubGraph，不僅可以支持?jǐn)?shù)據(jù)樣本級別，甚至可以直接關(guān)聯(lián)到在線檢索系統(tǒng)甚至圖引擎。
9N GL也支持多種方式的主模型+圖模型訓(xùn)練模式，多階段訓(xùn)練以及端到端聯(lián)合訓(xùn)練。
9N GL中的API設(shè)計(jì)相對簡單易用，主要包含有幾個(gè)層次的訓(xùn)練接口：
圖結(jié)構(gòu)的點(diǎn)、邊設(shè)計(jì)，支持多種行為類型，屬性類型
圖的采樣方法種類包含有隨機(jī)、帶權(quán)、Meta-Path等等
圖算法層面包含有常見的GNN和Graph Embedding兩大類
左側(cè)是一段實(shí)例代碼，僅需簡單的函數(shù)調(diào)用，即可完成圖解析，圖鄰居獲取等操作。
4. 圖在推薦、電商場景的典型 End2End 建模思路
接下來，向大家介紹一下圖在推薦、廣告場景中的典型端到端建模思路。
以CTR模型為例，在信息源部分引入用戶和商品的交互圖結(jié)構(gòu)化信息，通過圖的統(tǒng)一操作接口獲取出建模所需要的圖特征，然后經(jīng)過特征編碼器編碼為常見的id類特征，后續(xù)可以通過一系列的Graph Encoder獲取到用戶、商品的高階關(guān)系表征。
此外，在異構(gòu)圖網(wǎng)絡(luò)中，我們可以對不同語義空間進(jìn)行節(jié)點(diǎn)信息聚合，來捕捉到用戶的潛在行為意圖。
當(dāng)然，以上是一個(gè)常見的End2End聯(lián)合建模、聯(lián)合訓(xùn)練的思路。接下來的部分，給大家詳細(xì)介紹我們提出的一個(gè)具體模型BVSHG是如何做的。
1. BVSHG：業(yè)界常見圖算法 Graph Embedding
我們在詳細(xì)介紹BVSHG模型之前，還是先來看一下業(yè)界常見的圖算法和圖應(yīng)用。
首先是Graph Embedding類算法，顧名思義，GE類的算法本質(zhì)上就是將低階特征進(jìn)行Embedding化，業(yè)界常用的有DeepWalk、Node2Vec、LINE、EGES，他們的思路大同小異，如下圖舉例來說：
將用戶的行為序列按某種標(biāo)準(zhǔn)拆分
將拆分后的item構(gòu)建一張同質(zhì)圖
在圖上隨機(jī)游走，生成不同的游走序列/游走詞
按不同應(yīng)用送入到類似于Skip-Gram的結(jié)構(gòu)中
但這種做法通常適用于無監(jiān)督學(xué)習(xí)，其監(jiān)督信號與最終目標(biāo)通常不一致，只適用于多階段訓(xùn)練。也沒有充分發(fā)掘高階的潛在關(guān)聯(lián)關(guān)系。
2. BVSHG：業(yè)界常見圖算法 Graph Neural Network
我們再來看下GNN系列的常見算法和模型。
主要有這幾類：U-I二部圖、用戶session圖、社交網(wǎng)絡(luò)、知識圖譜。
在建模中也通常是圍繞U-U、U-I、I-I三大類關(guān)系進(jìn)行特征及屬性關(guān)系挖掘。但他的好處是可以結(jié)合最終建模的目標(biāo)進(jìn)行端到端學(xué)習(xí)。
3. BVSHG：Multi-behavior Multi-view Session-based Heterogeneous GNN
以上的兩類建模適用場景不同，我們在其中發(fā)現(xiàn)存在一些不足，如：
樸素的U-I關(guān)系圖中并沒有充分利用Side Information（如商品的類別，商品的品牌、商家店鋪等等）
U-I之間的關(guān)系類型很豐富，不僅僅是常見的點(diǎn)擊、購買關(guān)系，在用戶與商品的長期交互中，往往存在加購、分享、打賞、點(diǎn)贊、收藏等等。
常見的Session-Based Transformer建模，并沒有考慮Item間豐富的關(guān)聯(lián)關(guān)系，也沒有考慮session之間的關(guān)系。
針對我們之前跟大家提及的“極度長尾效應(yīng)”，不同用戶的行為序列長短差距很大，在工業(yè)化場景下，出現(xiàn)的效果與性能Trade-off難題。
而我們非常貪心地希望既要對短期用戶行為序列建模，又要對長期用戶商品交互信息的多視圖抽取，還要在一定程度上解決序列化建模帶來的性能挑戰(zhàn)。
作為成年人，想全都要！因此我們提出了BVSHG，即 Multi-behavior Multi-view Session-based Heterogeneous GNN 建模方式。它的大致示意圖如下，左側(cè)為圖信息的構(gòu)建，右側(cè)為圖建模方式圖，接下來我們會分部分詳細(xì)講講。
① BVSHG：Long-term Multi-Behavior Session Heterogeneous Graph
首先，我們重點(diǎn)講講如何構(gòu)建的這一張長期用戶多種行為session-based 異構(gòu)圖。
這是一張多元異構(gòu)圖，在圖中你可以看到至少4類節(jié)點(diǎn)，比如紅色的User節(jié)點(diǎn)，藍(lán)色的Item節(jié)點(diǎn)，黃色的Category節(jié)點(diǎn)，綠色的Brand節(jié)點(diǎn)等等。
此外，構(gòu)圖時(shí)，我們采用了用戶和商品、類目、品牌之間復(fù)雜的交互關(guān)系，比如上方的這個(gè)白色框中描述的是我們構(gòu)建圖時(shí)候用了用戶的長期瀏覽session關(guān)系，比如session1中包含item序列，對應(yīng)的category序列，對應(yīng)的brand序列；
下方的框中，描述的是我們采用了用戶的長期復(fù)雜行為數(shù)據(jù)，比如User1分享了Item4，也就分享了對應(yīng)的類目C3和對應(yīng)的品牌B3；
在右側(cè)的圖中，可以看出來，U1對I1、I2、I3都有瀏覽邊連接，但是對于I4有share 分享邊鏈接，U2對I3有AddCart加購邊鏈接。而圖中的I1、I2、I3之間由于存在同一個(gè)session內(nèi)，有共同出現(xiàn)的關(guān)系，有共現(xiàn)邊。
右側(cè)中間的圖描述的是User跟類目之間的邊情況，右下方的圖描述的是用戶和品牌之間的邊的情況。
在此特別說明的是，我們只有一張包含多種節(jié)點(diǎn)、多種行為邊的異構(gòu)大圖，右側(cè)的三個(gè)小圖，是在大圖中截取的一小段示意圖。
當(dāng)然了，在構(gòu)建這張大圖的時(shí)候，我們也有一些超參數(shù)需要調(diào)節(jié)，比如session切分的時(shí)間準(zhǔn)則，通常采用30min作為gap，但是并不是最優(yōu)。
② BVSHG：Multi-Behavior Sample
這一頁我們的模型分為三個(gè)部分：
傳統(tǒng)主模型部分，包含有UserFeature、ItemFeature、ContextFeature經(jīng)過像DCN等經(jīng)典結(jié)構(gòu)后，計(jì)算出一個(gè)Embedding
圖模型輸出一個(gè)Embedding
短期用戶session信息經(jīng)過Transformer輸出一個(gè)Embedding
將上述3個(gè)Embedding Concat在一起，最終經(jīng)過MLP輸出pCTR。
我們先重點(diǎn)介紹紅框中的部分，這部分是我們的TargetUser從我們的大圖中采樣找到的交互過的Item，排成一個(gè)list，用作target user的一種表達(dá)，也可以簡單理解為1階鄰居。
對于 target user，我們首先采用 Behavior-Weighted Random Sample 的方式采樣得到他的一跳 item 鄰居，具體而言，該采樣方式通過業(yè)務(wù)自定義的行為權(quán)重，對用戶的不同行為類型的鄰居節(jié)點(diǎn)進(jìn)行加權(quán)的隨機(jī)采樣。而對于 target item 以及第一次采樣得到的 user 的一跳 item 鄰居，我們采用同質(zhì)采樣（Homogeneous Sample）的方式，從圖中得到相同類型的鄰居節(jié)點(diǎn)。
③ BVSHG：Multi-View Attention-Based Item SAGE
現(xiàn)在，我們重點(diǎn)介紹BVSHG的精髓，Multi-View信息的抽取和Attention玩法。
對應(yīng)到上方的I1，我們在大圖中，找到I1的i-i關(guān)系表征，也找到I1對應(yīng)的類別C的c-c關(guān)系表征，同理，我們也找到了I1對應(yīng)的品牌B的b-b關(guān)系表征，這三段向量與I、C、B構(gòu)建出相應(yīng)的Attention 變換后concat在一起，形成一個(gè)O。
同理，I2、I3到In形成O2、O3到On
同理，TargetItem It形成Ot，將O1~On的向量與Ot進(jìn)行Attention計(jì)算。
④ BVSHG：Transformer-based Short-term Behavior Modeling
上圖的紅色框中，我們?nèi)匀唤栌肨ransformer對用戶的短期行為local session進(jìn)行序列關(guān)系的抽取，用來提取短期興趣。
我們的BVSHG的思路大致介紹完畢了，模型結(jié)構(gòu)雖然復(fù)雜，但是建模思路比較清晰容易理解。
4. 業(yè)務(wù)效果
我們將BVSHG模型在京東推薦廣告的精排場景進(jìn)行了實(shí)驗(yàn)，模型的點(diǎn)擊消費(fèi)有相應(yīng)上漲。當(dāng)然模型結(jié)構(gòu)也可以作為拋磚引玉，圖表征信息與主模型可以采用多種方式進(jìn)行交互作用，End2End訓(xùn)練。
5. 圖算法的其他玩法
我們再來看看我們嘗試過的其他圖算法的玩法：
我們借助實(shí)時(shí)圖，建立了User Item之間的二部圖，并實(shí)時(shí)更新圖內(nèi)點(diǎn)邊關(guān)系，從中發(fā)掘出了連通的節(jié)點(diǎn)簇，我們以最大團(tuán)、正則化割構(gòu)成更加合理的興趣簇的分類標(biāo)準(zhǔn)。
在工業(yè)化場景上，很多時(shí)候，數(shù)據(jù)中是存在缺失和錯(cuò)誤的，我們利用了U-I、U-C的事實(shí)圖，兩者進(jìn)行聯(lián)合修正，對數(shù)據(jù)做了增強(qiáng)和清洗。
04
未來展望，我們最近一年在圖上玩了不少花樣，但總起來看，還有兩個(gè)點(diǎn)我們還有很強(qiáng)的興趣繼續(xù)探索：
AutoML on Graph，由于我們構(gòu)建一張圖，進(jìn)行聯(lián)合建模的試驗(yàn)調(diào)試成本高，尤其是在超參的調(diào)試上耗費(fèi)了不少人力，亟待一個(gè)可以解放人力的超參調(diào)整方法，我們后續(xù)希望借助AutoML的方法用資源換人力加快實(shí)驗(yàn)迭代速度。
基于圖的強(qiáng)化學(xué)習(xí)，開篇我們找到了推薦系統(tǒng)的本質(zhì)問題是在解決用戶和商品之間的關(guān)聯(lián)關(guān)系，但這種關(guān)聯(lián)關(guān)系既有短期的、也有長期的，但業(yè)務(wù)評價(jià)標(biāo)準(zhǔn)更多是短期內(nèi)能帶來多少點(diǎn)擊、多少商品購買，很難對長期的獎(jiǎng)勵(lì)進(jìn)行評估和建模，我們目前正在結(jié)合RL的方法，對用戶長期購物路徑、對京東購物的喜好性分析、品牌影響力分析等等問題進(jìn)行嘗試中。
我們一系列關(guān)于廣告、推薦算法的探索及工程實(shí)踐將不止于圖，9N AI團(tuán)隊(duì)后續(xù)也會嘗試通過開源或分享的方式進(jìn)一步與同行更好地交流和互相學(xué)習(xí)。