阿里KDD2017：大規模圖計算對展示廣告的行為預測

機器之心專欄

作者：楊紅霞（阿里集團）、Yada Zhu (IBM Watson)、Jingrui He (亞利桑那州立大學)

在 2017 國際知識發現與數據挖掘大會（KDD）全球論文投稿中，阿里集團和螞蟻金服共有 5 篇論文被大會收錄，本次被收錄論文涵蓋深度學習、大規模圖計算、商品智能排序等多個研究領域，基於真實的業務場景或數據樣本，文中部分方法結論已經在業務中運用。如深度學習語義建模研究中提出了一種新的文本語義編碼演算法 conv-RNN，該模型在參考了較為常用的文本語義編碼模型循環神經網路與卷積神經網路的同時，進行了進一步的文本語義編碼優化，實現更為精準的文本分類和問答匹配並已應用於阿里智能音響「天貓精靈」。

KDD 的英文全稱是 Knowledge Discovery and Data Mining，即知識發現與數據挖掘，由美國計算機協會 ACM 下的數據挖掘分會舉辦，是國際數據挖掘領域的頂級會議。KDD 2017 共吸引全世界 1144 篇論文投遞，收錄 216 篇，包括清華、中科院、阿里在內的中國大陸學術界和工業界共被收錄 25 篇。

本文介紹了阿里被 KDD 2017 接收的論文《Local Algorithm for User Action Prediction Towards Display》。

論文地址：https://drive.google.com/file/d/0B_QtfVz5m-4_MkZpd1VIRUZSWm8/view

我們解決的問題

用戶行為建模在計算廣告中是至關重要的，它通過跟蹤用戶的在線行為建立用戶的產品，然後根據用戶的興趣和需求提供相關的廣告。準確的模型將導致更高的定位精度，從而提高廣告效果。直觀上，類似的用戶往往對展示的廣告具有類似的行為（例如，展示，點擊，轉換）。

然而，據我們所知，以前的工作沒有太多明確地調查各種類型的用戶行為的相似之處，並且將它們納入廣告響應目標和預測中，主要是由於問題規模過大。為彌合這一差距，本文中，我們使用二分圖來表示歷史用戶行為，其中包括用戶節點和廣告客戶活動節點，以及過去反映各種類型的用戶- 廣告營銷活動交互的邊。

基於這種表示，我們研究了用戶行為建模和動作預測的隨機步行本地演算法，其計算複雜度僅取決於輸出群集的大小，而不是整個圖形。我們的目標是通過利用歷史用戶-用戶 (user-user)，廣告系列活動 (campaign- campaign) 和用戶-活動 (user-campaign) 交互來改善行為預測。

特別地，我們提出了伴隨 ADNI 演算法的二分圖 AdvUserGraph。ADNI 將 NIBBLE 演算法擴展到 AdvUserGraph，並且能夠將由感興趣的用戶組成的本地群集發現到特定的廣告客戶活動。我們還提出了 ADNI 的兩個擴展，提高了效率。所提出的演算法的性能表現在合成數據和世界領先的需求側平台（Demand Side Platform），表明它們在預測極少數事件的有效性。

大規模圖計算本地演算法的意義

今天，存在無數的應用程序，需要對某些類型的大型圖表進行分析，例如社交網路，蛋白質相互作用網路，共同作者網路等，甚至全球網路估計至少包含 47.4 億頁。因此，即使是中等大網路的分析也是數萬個頂點的數量級，構成重大挑戰。處理這些問題的一種方法是將這些網路劃分成更小，更易管理的部件，並行處理。然而，在這些網路之一中建立最優聚類頂點的 NP 完整問題已經在十多年了。

分割大圖確實是一個計算上的重要問題：存在很少的方法可以在接近甚至 O(n2) 或 O(m) 的時間內對 n 個頂點和 m 個邊緣進行分割。近年來的一個突破是圖形分割的局部方法的出現，實現了邊緣數量接近線性的時間複雜性。這些方法中的第一種是通過稱為 NIBBLE[1] 的局部聚類演算法來實現的。NIBBLE 可以最大限度地減少無向未加權圖的聚類質量公制切割電導。給定一個起始頂點，它可以證明在時間上靠近該頂點的簇 (O(2blog6m)/?4)，其與輸出簇的大小成比例。尋找一個與其大小成正比的時間段是本身非常有價值的常式，作者展示了如何使用 NIBBLE 作為一個子常式，從大圖中重複刪除小簇，以獲得近似線性的時間圖分區演算法。後來使用 PageRank 向量擴展了 NIBBLE，並且表明，通過單個 PageRank 向量的掃描可以得到具有 cut conductance 為?的切割。

凸面優化已經成為不同領域的圖形建模越來越流行的方式。然而，隨著數據集越來越複雜，經典的凸優化通常由於缺乏可擴展性而失敗。最近 [2] 提出了 Network Lasso，並開發了一個快速，可擴展和分散式的解算器，並在圖形相關問題中看到幾個成功的應用。NIBBLE 和 PageRank NIBBLE 都是本地演算法，它可以找出包含或靠近給定頂點的解決方案，而無需查看整個圖形。本地演算法的運行時間，當查詢非空本地簇時，輸出簇的大小几乎是線性的。

模型的構成

我們首先把問題抽象成二分圖: user nodes & adv/campaign nodes，

這二者邊的建立，可以是 impression, click and/or conversion，一般情況下 impression 的數量遠遠大於 click，遠遠大於 conversion，但是這三者帶來的價值卻正好是相反的，及 value(impression)

Inverse document frequency (idf) 定義如下:

最終 tf-idf 的定義如下：

基於這個圖定義，我們提出了 NIBBLE 演算法的變形和兩個延展，並證明了計算時間最多 O((k/γ?k+1)logm/?)。

實驗結果

在 AUC，CVR 和 ROI 的結果上，我們都大幅度的超過了之前的 state-of-arts，並為全球第二大的競價平台帶來了數以百萬計的美金收益。

參考文獻

[1] D. Spielman and S. Teng. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM Journal of Computation, 42:1–26, 2013.

[2] D. Hallac, J. Leskovec, and S. Boyd. Network lasso: Clustering and optimiza- tion in large graphs. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD"15, pages 387–396, 2015.

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！