导读
图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。
关于图的论述起源于经典的柯尼斯堡 (Konigsberg) 问题，最早的文字记载出现在欧拉 1736 年的论著中。经过几个世纪的发展，对图论及相关算法的研究和应用已经取得了长足的进展。
背景
在现实世界中，从实体的图（像路网、电网和互联网等）到虚拟的图（像微博、朋友圈和通讯录等），图的存在形式各有不同。
在反作弊应用中，网络中实体（如账户、设备、IP 等）都可以用节点表示，而这些节点在业务中的关联可以用边表示。除了团伙作弊外，单个流量黑产方的资源相对有限和固定，行为上也会表现出孤立性和聚集性等特点。图算法在图的基础上刻画节点与边的各种特征。
图算法在反作弊的团伙挖掘和异常检测领域有广泛应用。
相比经典的图算法，如连通子图、标签传播算法和 louvain 算法等，图卷积神经网络算法不仅可以刻画图中的结构信息，还能对节点自身的特征进行有效的信息抽取和分析，能大幅提升识别效果。
它的算法思想是基于节点的局部邻居及其自身特征信息对节点进行表示学习 (Node Representation Learning)，本质上是通过神经网络对聚合节点及其邻居节点的特征信息做非线性变换。
商业中台反作弊团队通过 AI 技术升级和黑产持续对抗，打击广告作弊行为，保护广告主利益免受侵害。本文主要介绍商业策略技术团队使用连通子图、标签传播算法、 louvain 算法和图卷积神经网络算法挖掘广告作弊行为的探索实践。
图算法简介
图 (Graph) 是表示对象与对象之间关系的方法，图有两个要素：
- 对象又称节点 (Node)、顶点 (Vertex)、实体 (Entity)，它描述的是具体的一个事物。
- 关系又称边 (Edge) 它描述的对象之间的关系。
我们一般用这样的形式来表示一张图：
V 表示节点的集合，E 表示边集合。
在反作弊领域，有以下几个常用的图算法。
1.连通子图算法
连通图 (Connected Graphs) 指图内任意两个节点间，总能找到一条路径连接它们，否则，为非连通图 (Disconnected Graphs)。也就是说，如果图中包含岛 (Island)，则是非连通图。如果岛内的节点都是连通的，这些岛就被称为一个部件（Component，有时也叫 Cluster）。连通子图算法就是找到所有的 Cluster。
图 1 包含三个 Cluster 的非连通图
2.标签传播算法
标签传播算法[1]是一种基于标签传播的局部社区划分。
算法迭代过程：对于网络中的每一个节点，在初始阶段，标签传播算法对于每一个节点都会初始化一个唯一标签。每一次迭代都会根据与自己相连的节点所属的标签改变自己的标签，更改的原则是选择与其相连的节点中所属标签最多的社区标签为自己的社区标签，这就是标签传播的含义。随着社区标签不断传播，最终连接紧密的节点将有共同的标签。
3.Louvain 算法
Louvain 算法[2] 是基于模块度的社区发现算法，其优化目标是最大化整个社区网络的模块度。模块度的物理含义是社区内节点的连边数与随机情况下的边数之差，它的取值范围是 [−1/2,1)，其定义如下：
其中 m 为图中边的总数量，ki 表示所有指向节点i的连边权重之和，kj 同理。Aij 表示节点 i,j 之间的连边权重。ci 表示节点i所属的社区。
算法迭代过程：最开始，每个原始节点都看成一个独立的社区，社区内的连边权重为 0。
**步骤 1：**算法扫描数据中的所有节点，针对每个节点遍历该节点的所有邻居节点，衡量把该节点加入其邻居节点所在的社区所带来的模块度的收益。并选择对应最大收益的邻居节点，加入其所在的社区。这一过程化重复进行直到每一个节点的社区归属都不在发生变化。
**步骤 2：**对步骤 1 中形成的社区进行折叠，把每个社区折叠成一个单点，分别计算这些新生成的“社区点”之间的连边权重，以及社区内的所有点之间的连边权重之和。用于下一轮的步骤 1。
4.图卷积神经网络算法
图卷积神经网络算法[3] (GCN) 是一类非常强大的用于图数据的神经网络架构。在作用上类似 CNN，是一种从图数据结构中提取特征的提取器。
GCN 的每一层卷积仅处理一阶邻域的信息，通过叠加若干层卷积可实现多阶领域的信息传递，对图拓扑结构和顶点的属性信息进行学习来得到任务结果。可用于节点分类、图分类和边预测等，而不含顶点信息的 GCN 学习的作用相当于 Graph Embedding 仅对图的拓扑结构进行学习。
下图是没有经过任何训练得到的 二维表征，仅用随机初始化的两层 GCN，就能够生成得到网络中节点的有用特征。这些二维表征保存了图中节点的相对近邻性。
图 2 GCN 特征表征
假设有一批图数据，其中有 N 个节点 (node)，每个节点都有自己的特征。设这些节点的特征组成一个 N×D 维的矩阵 X，然后各个节点之间的关系也会形成一个 N×N 维的矩阵 A，称为邻接矩阵 (adjacency matrix)。X 和 A 便是 GCN 模型的输入。
GCN 的每一个卷积层的传播规则如下:
其中：
-
是 
的度矩阵，即 
； -
是无向图 G 的邻接矩阵加上自连接（每个顶点和自身加一条边），
是单位矩阵； -
是第 l 层的激活单元矩阵，
； -
是每一层的参数矩阵；
是无向图 G 的邻接矩阵加上自连接（每个顶点和自身加一条边），
是单位矩阵；
是第 l 层的激活单元矩阵，GCN 的完整理论涉及到空间域卷积、谱图卷积、傅里叶变换和 Laplacian 算子，这里不再详细展开。
以上四种图算法的优缺点和适用的场景总结如下：
| 图算法 | 优点 | 缺点 | 适用的场景 |
|---|---|---|---|
| 连通子图算法 | 输入同样的图连接可以得到最大规模的团伙 | 噪音数据会带来误杀，为了保证准确率会牺牲较多的覆盖 | 适合建立的边关系比较可靠的场景 |
| 标签传播算法 | 算法执行效率高 | 聚合结果不稳定 | 适合半监督聚类的场景 |
| Louvain 算法 | 效率和稳定性均较好 | 适合层次聚类的场景 | |
| 图卷积神经网络算法 | 考虑的信息更多，算法准确率更高 | 原始的 GCN 算法不易实现分布式计算 | 适合考虑节点特征的场景 |
图算法在广告反作弊场景的应用
1. 图算法应用的框架
图算法在 58 广告反作弊场景的应用框架如下图 3 所示。
图 3 图算法应用框架
首先使用外部行为数据建图。然后应用连通子图、标签传播算法和 louvain 等无监督图算法得到聚集的簇。这些无监督算法得到的聚合结果经规则过滤和抽样校验，得到高准确率的黑白标签数据，其中的黑标签数据可直接作为黑名单应用到线上。
无监督算法经过规则过滤和校验的黑白标签数据作为 GCN 算法的样本，结合输入的节点外部特征和黑白标签数据的原始图结构信息，训练 GCN 模型，迭代样本、特征和模型参数，调节模型效果。最终 GCN 模型的分类结果得到的黑标签数据可直接作为黑名单应用到线上。
应用框架如此设计的原因在于，反作弊样本不易收集，并且黑产作弊手段持续变化和升级。通过无监督的图算法挖掘出作弊数据，经过筛选可作为 GCN 的样本，加入节点特征，训练有监督模型后，可召回更多作弊数据。
2. 建图
建图是应用图算法的基础，这依赖对业务的理解。我们使用用户的行为数据作为数据源。如果在同一个时间窗口，两个用户使用了同一个 IP，就可以将这个用户和 IP 关联到一起，这样就构建了一个二部图，节点就是用户和 IP，边就是二者之间的关系。在建图过程中，我们使用第三方数据和自建数据过滤掉基站 IP 等公共 IP，防止用户被误关联。
3. 无监督图算法
由于使用多天全站行为数据建图后有几亿节点和几十亿边关系，使用单机版实现的图算法来处理这些数据是不现实的，因此我们借助 Spark GraphX 来实现连通子图算法、标签传播算法和 louvain 算法。
Spark GraphX 是一个分布式图处理框架，它是基于 Spark 平台针对图计算和图挖掘提供了简洁、易用、丰富的接口，极大的方便了对分布式图处理任务的需求。
图的分布式或者并行处理其实是把图拆分成很多的子图，然后分别对这些子图进行计算，计算的时候可以分别迭代进行分阶段的计算，即对图进行并行计算。
借助 neo4j 来作图，如下图是使用连通子图算法得到的其中一个异常簇：
图 4 异常簇示例
为绕过反作弊系统，作弊团伙不断切换 IP 和账户，但因为 IP 资源的有限性，作弊团伙使用过的帐户和 IP 会不可避免的产生一些关联。
如下图是抽取的其中一个簇的行为示例，同颜色的表示使用同一资源，这个簇在不断点击 58 的广告页面，并且在短时间内不断切换 IP、cookie、useragent 等资源以绕过反作弊系统，可以认为这个簇是一个作弊团伙。
图 5 团伙行为明细示例
标签传播算法在标签传播过程中，当邻居节点所属的最多标签出现多个时，会随机选择标签，导致聚类结果不稳定。这里考虑节点的度数，节点的度数越高则节点的重要性越高，重要性程度高的节点通常更加容易影响到重要性程度低的节点。
标签传播算法和 louvain 算法的挖掘结果格式与连通子图算法的挖掘结果格式类似，算法的结果均为用户和 IP 聚合后的簇。无监督图算法得到的结果并不能直接使用，需要引入业务经验进行验证并打标签。分别使用连通子图算法、标签传播算法和 louvain 算法得到聚合簇，然后通过以下两种方式给节点打标签：
-
基于簇的统计特征计算簇的风险分，根据风险分对整个簇打标签。
-
与积累的黑白名单关联给节点打标签。将过滤后的结果在验证集合上计算准确率、召回率等指标，根据要求的准确率来调节过滤阈值，然后将黑标签数据作为黑名单作用到线上。
4. 使用 GCN 算法
GCN 需要输入节点和边关系构造邻接矩阵，并输入节点特征和节点标签。使用连通子图算法的结果，经规则过滤和人工抽样验证后得到高准确率的黑白标签数据。由于 GCN 需要使用顶点的特征信息，原始的图结构包含用户和 IP 两类顶点，需要将所有顶点转换为相同的类型。我们的做法是如果两个用户出现在同一个 IP 上，则这两个用户建立一条边关系，这样所有顶点类型均变为了用户。
转化后的数据作为 GCN 的数据集，共 40.3 万个顶点，312 万条边，每个顶点包含 53 维特征，共有两个类别，正负样本比例 2:1。从中选取 30 万个顶点作为训练集合，10.3 万个顶点作为验证集合。
模型使用双层图卷积神经网络，并在中间加入 dropout 层，激活函数采用 ReLU 函数，使用 ADAM 优化器，交叉熵损失函数。如下图是网络结构示意图：
图 6 GCN 网络结构图
借助 TensorFlow实现 GCN， 经过参数调节和多轮迭代，GCN 在训练集上准确率 98.9%，召回率 96%，在验证集上准确率 98.4%，召回率 93%。
使用 t-SNE 算法对顶点向量降到 2 维，可视化如下图，可见 GCN 得到的向量能较好的将同类的顶点聚集到一起，不同类的顶点区分开。
图 7 GCN 得到的向量降维显示
5. 验证挖掘结果
我们选取两千个节点作为测试集，使用 xgboost 作为 baseline 模型，多个算法的分类结果对比如下：
| 模型 | 准确率 | 相对 baseline 模型的新增召回率 |
|---|---|---|
| baseline 模型 | 95.3% | - |
| 连通子图算法＋过滤规则 | 95.1% | 15.5% |
| 标签传播算法＋过滤规则 | 96.4% | 12.1% |
| louvain 算法＋过滤规则 | 96.8% | 13.4% |
| GCN算法 | 98.2% | 20.3% |
从分类结果来看，在保证 95% 以上准确率的基础上，图算法相对于原有的模型，均有高于 10% 的新增召回，其中 GCN 模型由于考虑了更多的信息，准确率和召回率比其他模型效果更佳。
总结和展望
结合 58 广告反作弊业务场景，我们应用了连通子图算法、标签传播算法、louvain 算法和 GCN 算法，取得了不错的效果。实践表明，图卷积神经网络算法对图的结构信息和图节点的特征进行有效的抽取和分析，能够大幅提高反作弊识别效果。
在今后的工作中，我们会考虑使用更多维度的行为数据建图，并在图结构中考虑边的权重。会根据业务特点，有针对性的改进基础的连通子图算法、标签传播算法和 louvain 算法。
作者简介
韦贞乐：商业生态与智能发展中心-商业技术部-策略技术部算法高级开发工程师，负责58同城广告反作弊工作。
马 建：商业生态与智能发展中心-商业技术部-策略技术部算法高级开发工程师，负责58同城广告反作弊工作。
—参考文献—
[1] Raghavan U N , Albert, Réka, Kumara S . Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E, 2007, 76(3):036106.
[2] Blondel V D , Guillaume J L , Lambiotte R , et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics Theory & Experiment, 2008, 2008(10):0-0.
[3] Kipf T N , Welling M . Semi-Supervised Classification with Graph Convolutional Networks[J]. 2016.
