专栏 | 阿里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.

本文为机器之心专栏，转载请联系本公众号获得授权。

✄------------------------------------------------

加入机器之心（全职记者/实习生）：hr@jiqizhixin.com

投稿或寻求报道：editor@jiqizhixin.com

广告&商务合作：bd@jiqizhixin.com

关注公众号：拾黑（shiheibook）了解更多

[广告]赞助链接：

四季很好，只要有你，文娱排行榜：https://www.yaopaiming.com/
让资讯触达的更精准有趣：https://www.0xu.cn/