从邀请朋友帮砍一刀,到双十一中的打折优惠,很多营销活动都在借助网络效应来提高营销效果。当用户之间存在互相影响时,营销活动的效果经常难以评估和优化。比如打折后当一个用户来买东西,很难区分他是本来就有需求,还是从朋友口中听说了最近在打折才来购买。这使得当网络效应存在时,营销活动的效果难以被评估和优化。
来自蚂蚁智能引擎技术团队的同学提出了一种全新的评估活动的方案,针对大规模的应用和活动优化做了针对性的改进。该内容已登上数据挖掘顶级会议 DASFAA。欢迎大家学习交流。
为了评估优化营销活动的效果,常用的做法是按城市、或是按好友关系聚类后,将用户分为 A/B 组,在对 A/B 组尝试不同的营销策略后,通过对比两组间用户活跃度,来评估不同策略的效果差异。实践中,在数十亿用户规模的关系网络上做这样的网络 A/B 实验困难重重。为此,蚂蚁智能引擎技术团队将这个方案和一个新方法结合了起来:本质上,通过预测哪些用户可能会互相影响,并将这些用户聚类到一起来提高对活动效果预估的精准度。
营销中的网络效应
在很多营销活动中,给一个用户提供优惠可能会影响多个用户的转化。这种转化,可能是像“帮砍一刀”中邀请好友来一同使用 app,也可能是用户买东西享受到折扣后,回家叫了亲朋好友一起来,店里的用户突然多了起来。
在支付宝,我们的一个活动会给用户发优惠券(左图中的红色),用户可以邀请朋友加入这个活动。所有加入的人,都会收到一张现金优惠券(右图中的红色)。当评估这样的活动效果时,如果不仔细设计 A/B 实验方案,经常会得到错误、甚至误导性很强的结论。
如果我们随机将用户分进 A/B 组(左图黄色、青色),在上述的活动中,就会发现 A/B 组转化的用户个数一样多。难道是我们的激励对用户没有吸引力?不!是活动的效果顺着用户之间的“关系”从实验桶“溢出”进了对照桶,使得对照桶的用户也被转化了。在这种情况下,用户维度的 A/B 实验错误地得出结论:活动没有任何效果。为了解决这个问题,常见的做法是使用网络 A/B 实验:将可能会互相影响的用户聚类后,以簇(一群用户)为单位进行 A/B 实验分组(右图黄色、青色)。当用户间的影响都发生在簇内时,网络 A/B 实验可以很好的评估活动效果。
网络A/B实验
最传统的做法是直接城市进行 A/B 实验,这样糙快猛的方案背后,因为样本量太小(全国仅几百城市),不容易得到统计学上置信的结论。业界也有按好友关系进行聚类的。但两个用户是否是好友,和他们在活动中是否会互相影响经常不相关。比如各类大 V 经常会有数百万的好友关系,但活动中很难真的影响这么多人,这使得聚类的效果经常很差。
虽然我们不知道没来的用户之间会怎样互相影响,但我们可以做一个模型来从已经参与过活动的用户身上学到哪些用户容易互相影响。基于这样的想法,我们提出了先使用 GNN 进行关系的预测,先预测出哪些用户会在当前活动上相互影响,再在这个预测得到的图上进行聚类的做法。在支付宝的活动中,这个做法显著提高了网络 A/B 实验的效果。
1)关系预测
为了预测用户间的影响关系,也就是当参加活动时,哪些用户之间会互相邀请,我们尝试了多种做法。深度神经网络(DNN)是最好想到的,但 DNN 很难消费用户间的历史关系特征。为此,我们进一步尝试了图神经网络 Graph Neural Network(GNN)来做关系的预测。
对比 DNN,GNN 主要就是加入了一步聚合操作。在第 k 次迭代时,对每个节点 v,使用一个聚合函数 AGG 来聚合所有邻居节点 u 和邻接边传来的信息,最后通过一个非线性的激活函数 σ。
在次基础上,我们可以使用 GNN 进行两个用户之间是否会产生关系的预测,网络结构如下:
GNN 输入包含节点A特征 、节点B特征、AB 之间历史关系的边特征三部分。在利用 GNN 学习到 A、B 节点的表示之后,加入边的特征,一起输给一个全连接 MLP 预测在本次活动中,两个用户之间是否会互相邀请。
为了更好的编码节点之间的位置信息,我们使用了 [1] 中的 node label 来有效利用子图各个节点距目标边距离的结构特征。这是一种节点上的结构特征:目标边附近子图中,每个节点均计算一个距目标边的距离,再将这个距离附加到节点的原始特征上。这个距离能区分出每个节点的结构角色,非常适合关系预测。比如:为了预测 x 和 y 是否会产生联系,“与x、y均有直接联系”和“只与x有联系”的两种节点显然起到了不同的作用。显式地将不同的结构角色区别出来,对边预测效果提升显著。
对需要预测的边,node label 对周围的节点进行了编码。如上图所示,在预测 xy 之间是否有边时,先计算周围每个节点到 x 和到 y 分别的距离,然后就可以套用公式得到一个唯一的编码,编码结果如上图左所示。
在我们的实验中,同样是进行边的预测,对比 DNN 和初版 GNN (NG-LP),加入了 Node Labeling 后 (NL-LP),边预测子任务的 AUC 显著提升。
2)关系聚类
我们在关系预测的结果上,过滤掉分数太低的边,然后对带权重的边,使用 GRAPE 引擎的分布式的 Louvain 算法进行关系边的聚类。Louvain 是一个对 Modularity Maximization 的近似算法,大概的思路就是通过迭代,在最大化每个 cluster 内边权重的同时,减少连接不同 cluster 边的权重。因为是一个迭代的算法,Louvain 可以高效的大规模图。比如我们在 GRAPE 集群的测试中,10 亿条边图的聚类大概需要 20 分钟,100 亿边时大概需要 4 小时。
通过使用不同的模型进行预测,不同的阈值过滤关系预测结果的边,以及调整 Louvain 参数,可以得到各种粒度的聚类结果。再将不同方案聚类后的簇随机分进 A/B 组,就得到了不同的网络 A/B 实验方案。
网络A/B实验方案评估
不同营销方案之间,营销活动效果的变化可以使用 average treatment effect(ATE)进行量化。在实际的网络 A/B 实验中,用户不可能同时进入 A 桶和 B 桶,也就是没办法获得真实的 ATE,只能使用实验组和对照组效果的差值,进行预估:
其中,q^ij是实验组 Q 的第 j 个簇中的第 i 个用户,c^ij 是对照组C的第 j 个簇中的第 i 个用户。M 和 N 分别表示 Q 和 C 中的用户数。
好的网络 A/B 实验方案,需要在控制方差(variance)小的同时,尽可能无偏差(bias)的预估营销活动效果。为了评估不同网络A/B实验方案的好坏,我们设计了 网络干扰程度(I 越小越好)指标来评估预估是否无偏。并使用了 18 年KDD一篇论文当中提到的方法来 预估方差(Var(Y) 越小越好)。方差越小时,实验的统计能力越强,估计的越有把握。
我们对比了如下方法:–Geo:按城市对用户进行聚类的经典方法。–Louvain:直接使用分布式 Louvain 进行聚类。因为大 V(热点)的存在,24小时后依然无法完成聚类。–HRLouvain:直接移除热点(度数大于θ的节点)后,使用 Louvain 进行聚类。–LinkLabel:边预测后,使用分布式 label propagation 进行聚类。–LinkLouvain:边预测后,过滤关系弱(邀请概率小于γ)的边后,用邀请概率为边权重,分布式 Louvain 聚类。–LinkLouvain UW:同 LinkLouvain,过滤边后,权重都设置为 1,然后用分布式 Louvain 聚类。
在我们百亿量级边,十亿量级节点的图上,LinkLouvain 很好的平衡了网络干扰程度和预估方差,并且能在 6 小时内完成聚类。产出的用户簇可以很好的用来进行网络 A/B 实验。
我们在支付宝的营销活动中,使用了基于 LinkLouvain(γ=0.5)的方案进行网络 A/B 实验,在实际的活动中,AA 组转化率差异在 0.2% 以内,检验功效符合预期,方便我们快速决策不同策略之间的差异。同时,在这个聚类的基础上,在每个簇内可以进行对应的算法优化,这帮助算法在活动期间,累积提升了 58% 的活动转化率。
展望
在过去几年中,营销活动变得越来越多,规模越来越大。如何设计合适的激励方式,让用户享受优惠,愿意尝试新功能,爱上新功能,是蚂蚁智能营销团队一直在做的事情。团队由一群技术爱好者,如 MIT TR35,ACM-ICPC 金牌,大数据竞赛全国冠军,阿里星们等组成,并且不断的在机器学习、数据挖掘的顶会们有论文的发表。有着很强的技术背景,我们为支付宝所有的大型营销活动(双十一、双十二、新春五福等)提供大规模的个性化推荐服务,影响着十亿级用户的支付、生活习惯。
欢迎加入我们的暑期实习项目(详情见海报),一起为世界带来微小而美好的改变!
