图算法在58广告反作弊的应用

来源：https://blog.51cto.com/u_14637492/2904980

背景

在现实世界中，从实体的图（像路网、电网和互联网等）到虚拟的图（像微博、朋友圈和通讯录等），图的存在形式各有不同。
在反作弊应用中，网络中实体（如账户、设备、IP等）都可以用节点表示，而这些节点在业务中的关联可以用边表示。除了团伙作弊外，单个流量黑产方的资源相对有限和固定，行为上也会表现出孤立性和聚集性等特点。图算法在图的基础上刻画节点与边的各种特征。
图算法在反作弊的团伙挖掘和异常检测领域有广泛应用。

相比经典的图算法，如连通子图、标签传播算法和louvain算法等，图卷积神经网络算法不仅可以刻画图中的结构信息，还能对节点自身的特征进行有效的信息抽取和分析，能大幅提升识别效果。
它的算法思想是基于节点的局部邻居及其自身特征信息对节点进行表示学习(Node Representation Learning)，本质上是通过神经网络对聚合节点及其邻居节点的特征信息做非线性变换。
商业中台反作弊团队通过AI技术升级和黑产持续对抗，打击广告作弊行为，保护广告主利益免受侵害。本文主要介绍商业策略技术团队使用连通子图、标签传播算法、louvain算法和图卷积神经网络算法挖掘广告作弊行为的探索实践。

为绕过反作弊系统，作弊团伙不断切换ip和账户，但因为ip资源的有限性，作弊团伙使用过的帐户和ip会不可避免的产生一些关联。
如下图是抽取的其中一个簇的行为示例，同颜色的表示使用同一资源，这个簇在不断点击58的广告页面，并且在短时间内不断切换ip、cookie、useragent等资源以绕过反作弊系统，可以认为这个簇是一个作弊团伙。


标签传播算法在标签传播过程中，当邻居节点所属的最多标签出现多个时，会随机选择标签，导致聚类结果不稳定。这里考虑节点的度数，节点的度数越高则节点的重要性越高，重要性程度高的节点通常更加容易影响到重要性程度低的节点。

标签传播算法和louvain算法的挖掘结果格式与连通子图算法的挖掘结果格式类似，算法的结果均为用户和ip聚合后的簇。无监督图算法得到的结果并不能直接使用，需要引入业务经验进行验证并打标签。分别使用连通子图算法、标签传播算法和louvain算法得到聚合簇，然后通过以下两种方式给节点打标签：
1）基于簇的统计特征计算簇的风险分，根据风险分对整个簇打标签。
2）与积累的黑白名单关联给节点打标签。
将过滤后的结果在验证集合上计算准确率、召回率等指标，根据要求的准确率来调节过滤阈值，然后将黑标签数据作为黑名单作用到线上。

4.使用GCN算法

GCN需要输入节点和边关系构造邻接矩阵，并输入节点特征和节点标签。使用连通子图算法的结果，经规则过滤和人工抽样验证后得到高准确率的黑白标签数据。由于GCN需要使用顶点的特征信息，原始的图结构包含用户和ip两类顶点，需要将所有顶点转换为相同的类型。我们的做法是如果两个用户出现在同一个ip上，则这两个用户建立一条边关系，这样所有顶点类型均变为了用户。

转化后的数据作为GCN的数据集，共 40.3万个顶点，312万条边，每个顶点包含53维特征，共有两个类别，正负样本比例2:1。从中选取30万个顶点作为训练集合，10.3万个顶点作为验证集合。
模型使用双层图卷积神经网络，并在中间加入dropout层，激活函数采用ReLU函数，使用ADAM优化器，交叉熵损失函数。如下图是网络结构示意图：

借助tensorflow实现GCN， 经过参数调节和多轮迭代，GCN在训练集上准确率98.9%，召回率96%，在验证集上准确率98.4%，召回率93%。
使用t-SNE算法对顶点向量降到2维，可视化如下图，可见GCN得到的向量能较好的将同类的顶点聚集到一起，不同类的顶点区分开。

图6 GCN网络结构图