图挖掘技术在京东广告流量风控上的应用与实践

背景介绍

京东的广告流量风控场景主要包含恶意点击流量、恶意曝光流量、恶意订单检测与识别。恶意流量产生的背后动机多种多样，作弊模式上存在不同形态，主要的几种动机比如有商家之间相互攻击竞争对手广告从而达到消耗对手广告预算，流量媒体渠道广告刷量从而获取更多分成收益，恶意爬虫流量主要为了获取商业信息，竞争对手对竞品商家恶意下单达到占商品库存，商家刷店铺点击访问量从而提升本店铺热度、搜索排名等各种欺诈动机。

在与欺诈群体攻防对抗过程中，欺诈者的作弊手法在不断的进行优化升级。从单个欺诈资源主体（例如账号、设备或者IP等）的作弊量大小可以划分为高频作弊模式和低频作弊模式，其中高频作弊模式是指欺诈者投入少量的资源主体，在单个资源主体上产生较大的欺诈流量，在资源主体维度上表现出聚集性，这种作弊欺诈方式比较容易被系统发现，可以通过频次策略对其防御。另外一种称作低频作弊模式，这种模式是指欺诈者通常投入大规模的资源主体，通过控制大量的资源主体来进行各种作弊欺诈活动，该作弊模式表现为单个资源主体的作弊量较少，统计特征不显著，与真实流量较为相似，仅从单个资源主体统计特征分析较难发现其中的作弊欺诈行为，但这种作弊模式的异常特征体现在多个资源主体之间的关联性，欺诈的资源主体在操作行为和主体属性上存在较强的一致关联特性，通常表现出行为的一致性或称作同步性，以及资源主体属性的聚集性，对这种低频欺诈群体识别的关键在于如何有效的建模资源主体间的关联，以及如何挖掘出资源主体之间行为的一致性、聚集性等关联特征。图是一种建模现实世界中实体以及实体之间关联关系的有效数学工具，图的基本元素是节点和边，其中节点代表实体，边代表实体之间的关系。图挖掘是通过捕捉实体之间的关联特征来挖掘有用信息的一门数据挖掘技术。结合京东广告流量面临的风控问题，下面我们来分享两个反欺诈领域优秀的图挖掘算法，并介绍如何利用图挖掘技术解决广告流量风控问题，以及我们在图挖掘算法平台化建设方面的一些工作。

图1： 相较于正常用户，欺诈用户间具有较强的关联性

图挖掘算法介绍

近些年在反欺诈领域涌现出较多的图挖掘算法，其中一类著名的无监督图算法称作稠密子图检测算法，代表算法有 Fraudar、HoloScope、D-cube、M-zoom等。这类算法的共同点是通过定义稠密度量指标，采用搜索策略进行度量指标优化，从而来检测大图中的稠密子图结构，最终达到识别出欺诈用户群体。这些算法主要适用于检测存在团伙、群体欺诈的风控场景（例如，群控设备攻击、群控模拟器欺诈、人工分布式群体欺诈等）。

01

Fraudar 算法介绍

Fraudar 算法出自KDD 2016 年的最佳论文，该算法设计之初是用于推特虚假粉丝、商品虚假评论检测等问题，属于一种稠密子图检测算法。算法的主要创新点包含可疑度指标定义， 提出了一种新颖的具有对抗欺诈者伪装的节点可疑度和子图的可疑度，并设计了一种能够快速计算出最大可疑度的子图检测算法。 Fraudar 算法是近些年来比较优秀的基于稠密子图检测的基础算法，下面将对该算法的细节进行展开介绍。

a.可疑度定义 

Fraudar 算法是一种针对二部图中的稠密子图检测算法，待检测图中的节点分为行节点（例如，表示用户）和 列节点（例如，表示目标）两类，边的可疑度定义为关于列节点（目标节点）入度的一个衰减函数的函数值，即当目标节点的入度越大，与之相关联的边权重值越小。节点可疑度定义为该节点关联的所有边的可疑度之和，子图平均可疑度定义为该子图边的可疑度之和除以子图所包含的节点总数。在用户店铺评论场景（图2）中，采用列节点入度降权定义边可疑度能够有效的降低用户与热门店铺评论所产生边的可疑度，进而降低包含热门店铺节点子图的可疑度，这样能够一定程度上降低对一些热门店铺的误召回。

图 2：用户评论店铺所形成的二部图，图中有用户和店铺两类节点，其中边的权重依赖于列节点（店铺节点）的入度。例如店铺A的入度为2，则与店铺A关联的边的权重为 1/log（2+5 ）=0.51，店铺B的入度为1，则与店铺B关联的边的权重为，1/log（1+5）=0.55，店铺C的入度为4，则与店铺C关联的边的权重为，1/log（4+5）=0.45，图中用边的粗度表示边对应的权重值，入度列节点越高与之关联的边权重值越低。

b.贪心搜索寻优

采用贪心策略寻找具有最大平均可疑度的子图，首先初始化图中边的权重，计算出节点的可疑度，然后找到可疑度最小的节点并从图中删除该节点，删除操作会导致与被删除节点相关联的节点可疑度发生改变，这时需要重新计算相关节点的可疑度进行更新，并记录当前剩余子图的平均可疑度，这样迭代执行节点删除以及记录删除后剩余子图的平均可疑度这种操作，直到删除所有的节点，最后回溯迭代删除过程，找到整个删除过程中剩余子图平均可疑度最大的子图并输出，图 3 给出一个简单示例。

图3：左边为一个用户-店铺评论二部图，用户集合{u0,u1,u2,u3} 与 店铺集合{s0,s1,s2} 形成的子图平均可疑度为0.768最大，该子图在整个大图中最稠密，由红色虚线框出 。右图描述了逐步迭代删除二部图中用户和店铺节点时剩余子图的平均可疑度随着节点删除操作的变化趋势，可以看出当删除节点集{u6,s5,u5,u4,s4,s3}后对应的剩余子图平均可疑度达到最大，之后继续删除会使得剩余子图的平均可疑度变小。

0 2

D-Cube 算法介绍

D-Cube 算法是一种稠密子张量检测算法，以图的视角一个高阶张量对应一个k-均匀超图，所以该算法可以看作是一种针对 k-均匀超图的稠密子图挖掘算法，相较于 Fraudar 算法仅适用挖掘二部图中的稠密子图，D-Cube 算法能够从 k-均匀超图中挖掘稠密的高阶子图，可以支持从更高的数据维度来进行问题建模。例如在店铺欺诈评论检测场景中，欺诈者出于任务约束以及资源约束，会尽可能多的用他们控制的用户账号对目标店铺集进行虚假评论，当然同时也会存在大量的正常用户账号在一组热门店铺都有过评论，这时除了欺诈用户节点与他们的目标店铺节点会形成稠密子张量外，存在正常用户节点与一些热门店铺节点也会形成稠密子张量，所以仅仅从用户-店铺两个维度来建模用户评论店铺交互过程并采用稠密子张量检测，这种建模方法较难准确的召回真正的欺诈用户。那么如何辨别出真正的欺诈用户的评论？从更高阶的信息维度分析，欺诈用户群体在产生恶意评论时往往在时间维度上存在聚集性，所以在建模时可以增加时间维度的信息，比如采用用户-店铺-时间三个维度构成的 3 阶张量建模来捕捉欺诈用户群体在时间维度的聚集性，这样能够从更高的信息维度辨别出真实的欺诈用户群体，如图 4 展示的一个简单示例。

图 4：图左边描述的是采用用户-店铺两个维度建模时 用户和店铺评论关系矩阵（或 2 阶张量），图右边为采用用户-店铺-时间三个维度建模用户在何时评论店铺这种关系所对应的3 阶张量表示，可以看出如果用用户-店铺两个维度建模时，正常用户群体和欺诈用户群体都存在形成的稠密子张量块的情况，其中蓝色块标出的为正常用户形成的，红色块标出的为欺诈用户形成的。当采用用户-店铺-时间三个维度建模，在考虑到时间维度时正常用户形成的 3 阶张量子块是稀疏的，而欺诈用户群体形成的 3 阶张量子块是稠密的。

D-Cube 算法支持算术平均密度、几何平均密度、Suspiciousness 三种密度度量指标，三种指标的含义存在差异，需要根据具体的问题选择合适的指标度量。D-Cube 算法与 Fraudar 算法的寻优过程类似，不同点在迭代删除阶段，D-Cube 算法采用了剪枝加速技巧使得算法相较于 Fraudar 更快，同时 D-Cube 算法有对应的 Map-Reduce 实现版本，扩展性较好。

实践案例

随着互联网技术的发展，具备一定的规模黑产已发展成服务型的黑产协作平台，这些平台越来越多，他们组合成了一张庞大的黑灰产基础资源网络。营销广告流量面临着这些外部黑产攻击的挑战，我们不断探索如何将图挖掘技术在各种流量风控场景进行落地，并取得了较大的收益，例如在搜索广告恶意攻击检测、媒体渠道刷量检测、恶意订单检测、群体分布式爬虫检测、恶意搜索刷热度排名检测等多种风控场景上都有较为成功的图挖掘算法的应用落地，下面将简单分享其中两个关于广告流量恶意攻击检测的成功案例。

01

站外广告恶意流量检测

京东通过采买媒体渠道的广告流量来帮助商家提升营销效果，流量采买按CPC或者CPM计费，不良的媒体会存在刷广告流量来提升收益这种动机，这种刷量行为损害广告主的利益和京东平台的声誉。相较于京东主站内的流量，通过站内页面埋点能够收集到较为丰富的用户行为数据，比较容易开展恶意欺诈流量的识别检测工作，而站外收集到的用户行为数据相对较少，缺乏可利用的用户行为数据，仅使用用户稀疏的点击行为数据开展流量反欺诈工作相对较难，我们面临的挑战是如何在用户点击数据稀疏、可利用数据较少的条件下有效的识别欺诈流量？

经前期的调研分析发现站外不良媒体渠道的欺诈流量表现出同步性和聚集性，欺诈用户群体会针对一组特定的目标广告点位，在较为相近的时间段内进行批量点击操作。针对这种群体欺诈模式，我们利用图模型来建模用户点击广告这种交互行为。经过实验调参，我们最终选择出较为适合的两个维度用来构建用户广告点击交互二部图。欺诈者出于资源和任务的约束，每个欺诈用户会尽可能多在目标上进行攻击，进而在整个用户广告点击交互二部图中欺诈用户群体与其攻击目标之间会形成稠密的子图，我们采用Fraudar 算法对用户广告点击交互二部图进行稠密子图检测，并最终检测出可疑的欺诈用户群体，通过线下人工评估发现检测出的欺诈用户在用户行为统计量以及某些用户属性上存在一致性，同时识别出的这些用户流量在后期无对应的订单转化。统计了在营销大促期间的检测效果，图挖掘策略每天检测识别出约10万左右的欺诈用户，约50多万的站外欺诈点击流量，通过图挖掘技术有效对这种站外的群体团伙欺诈模式进行防范，保护广大广告主的利益和平台的声誉。

02

站内搜索广告恶意点击流量检测

站内搜索广告恶意点击流量产生的主要背景是存在一些商家通过攻击竞争对手的广告来达到消耗其广告预算、提升竞争对手的营销推广花费。前期通过案例分析和调研，我们发现市场上存在专门提供搜索流量服务的黑产平台，他们控制着大批量的用户账号，当有客户提交流量需求时，黑产平台控制的这些用户账号会在客户约定的时间段内，通过批量搜索关键词来攻击目标广告主的广告，从而完成指定的搜索点击流量任务，这些欺诈用户攻击目标广告在时间维度上表现出同步性，我们根据黑产欺诈用户攻击时表现出的这些异常特征，最终设计出四个与异常特征有关的维度来构建用户搜索广告点击交互场景下的四阶张量（或4-均匀超图）来对用户搜索广告点击行为进行建模，并采用 D-Cube 算法对该四阶张量进行稠密子张量挖掘。最终能够识别多个黑产欺诈用户群体，经过后期的人工验证发现这些欺诈用户的在京东站内的行为上存在一致性和时序规律性，存在明显的异常性。我们通过图挖掘技术有效的打击了这种黑产在搜索广告上的攻击行为，保护了平台生态健康发展。

算法平台化建设

针对广告流量风控业务需求，结合前期的算法调研实践，我们优选了实践中较为有效的图挖掘算法，并对这些算法实现做了工程优化和平台化系统集成。目前初步设计出图挖掘算法平台的框架并在不断的进行优化和建设中，未来希望能够建设成为一个具有支持较多主流图挖掘算法的基础算法平台，能够支持 billion 量级、超大规模风控场景下的图挖掘应用需求，设计初期的图挖掘算法平台的架构（图5）。

图 5：图挖掘算法平台主要包含六层，从下到上依次为数据层（由业务数据封装成的数据日志接口组成），格式转化层（将业务数据适配成对应的图数据格式），核心算法层（集成多个图挖掘基础核心算法），调度与输出层（通过配置文件执行算法调度和数据输出），应用层（图挖掘检测结果应用到各个业务）。

01

Fraudar算法工程实现优化

为了解决开源Fraudar 算法Python 版本内存消耗多、处理速度较慢，无法处理大规模数据下的图挖掘问题，我们采用 C++对算法进行了重构，并对算法实现细节进行了一系列工程调优，最终取得了不错的优化效果，下面将针对一些工程优化点进行简单介绍。

a.基于共享叶节点的优先树

Fraudar 算法在进行最大平均可疑度子图寻优迭代过程中，需要逐步删除图中可疑度最小的结点以及更新相关节点的可疑度。为了提高删除和更新节点可疑度的计算效率，算法的作者提出了最小优先树的概念。最小优先树是一棵二叉树，以二部图中的节点可疑度作为叶结点的值，并用父节点记录其子节点中的最小值。这样从记录的全局最小值的根节点出发可以快速定位到该图中具有最小可疑度所对应的叶节点，然后将其从二部图中删除，并能够快速更新最小优先树。在Python版Fraudar算法实现中，查找最小可疑度节点的时间复杂度为 O(log?N )，更新的时间复杂度也为 O(log?N )。同时在大规模数据时，构建最小优先树会产生大量的内存消耗。为此我们在工程优化实现过程中提出一种基于共享叶节点的索引优先树。在构建最小优先树时省略优先树的叶节点，直接使用图内存中的节点可疑度数组的作为优先树的叶节点，从而复用数据减少拷贝，降低内存消耗。与此同时，优先树的非叶节点会直接存储当前最小可疑度对应的下标索引，从而在 O(1)的时间找到最小可疑度的节点的索引，进一步加速最小可疑度节点的检索效率。

图6.  基于共享叶节点的最小优先树，下面数组存储节点的可疑度，节点的eid与数组下标对应。优先树的父节点存储其两个子节点中可疑度小的节点eid。优先树的根节点即为当前可疑度最小的节点eid 。

b.索引压缩存储

为了进一步减少最小优先树的空间复杂度，利用非叶子节点存储有序的整型eid这一特性，对eid进行压缩存储。根据当前节点eid的值，压缩成使用8bit、16bit、24bit和32bit四种规格大小存储方式（图7），使非叶子节点的空间复杂度降低为优化前的一半。

图7： 索引压缩存储。 根据eid的值大小，从使用8bit、16bit、24bit、32bit压缩存储。

经过上述优化措施，Fraudar算法得到较大的性能提升，我们在自然搜索流量反欺诈项目中，相关场景图的规模为12.5 亿 节点，22.4 亿 边，一次迭代检测出最大可疑子图的耗时约 20分钟，相较于Fraudar算法的Python 版本，实现了5~8倍的加速效果，同时内存消耗仅为优化前的十分之一 ，整体取得了不错的优化效果，算法效率上能够满足当前流量风控业务的需求。

总结与展望

图是一种有效的关系建模工具，具有能够将信息结构化表示的特性，已经在许多相关领域广泛被使用，并在现代化机器学习中扮演重要的角色。近些年以图模型为基础的图挖掘技术在风控领域的应用被不断探索和创新，本文主要分享了一些风控领域的图算法以及图挖掘技术在流量风控领域的实践案例，希望能给大家未来的工作带来一些思考和借鉴，最后在面对大数据时代的挑战，未来如何有效的利用图对用户行为建模并进行欺诈检测以及如何设计出具有分布式、可扩展的无监督图挖掘算法是一个值得思考和发展的方向 。

本文作者：商业提升事业部  张帅、李杰