图算法在数科安全集群上的应用

导读：数科安全集群是一个spark集群，承载日常大多数的数据计算，具有强大的安全性。集群具有丰富的资源，因此在spark集群上进行图计算是一个既安全又便利的选择。图计算通常分为归纳式学习和直推式学习两类，这两类算法具有不同的计算方式和部署逻辑。

归纳式学习（Inductive Learning），从训练集中归纳经验，之后应用于测试集。

直推式学习（Transductive Learning），从观测集中的训练点推广经验，应用到观测集中的测试点；意味着测试点本身是可观测到的，如果有新的测试点，就需要重新训练。

今天要介绍的主要内容是图算法在数科安全集群上的应用。全文主要分为四个部分：

Inductive类算法的部署

Inductive类常用算法

Transductive类常用算法

总结和展望

01Inductive类算法的部署

安全集群出于安全的考虑对开发环境有较多限制，因此，在已有hadoop和spark的基础上，接下来重点讨论不需要部署而能够使用的框架或计算方式。

1. 在Spark上运行pytorch框架

部署算法是将算法部署于集群中。Pytorch有专门的分布式模型的封装接口DistributedDataParallel，内部有一套参数同步方式，也可以通过调用dist.all_reduce等接口实现。Spark有专门的运行同步训练的RDD结构RDDBarrier。将二者结合，在RDDBarrier中运行分布式pytorch模型便可以实现在spark上运行pytorch框架。

具体代码如图，首先创建RDDBarrier，然后在mapPartition上可直接构建pytorch的同步框架。提交时带上pytorch包的python环境即可。

2. 在Spark上运行pyg图学习框架

① 采样服务器

Pyg是一个图学习框架，可以借助pytorch的分布式接口实现分布式训练，通过Pytorch的DistributedDataParallel实现训练参数的同步。

参考官方示例可以发现，在构建数据集时，需要把所有数据加载到单机上，因此，数据集的规模是需要单机能负载的。下面列举几种数据规模和的对应部署方式。

当每个节点能够完整读入顶点和边的信息时，直接使用DataLoader加载，相当于单机训练，后使用DistributedDataParallel同步参数。

当集群中节点难以完全存储，只有Driver端能读入完整的边关系和顶点属性时，则在Driver端调用NeighborLoader后分发给各个worker实现边采样边训练。

当Driver端也无法读入所有信息时，可以只读入完整的边关系，调用pyg的NeighborSampler对边进行采样。

当只有Driver能读入完整边信息时，采用NeighborSampler对边进行采样。

BlockManager：Spark的底层结构，负责RDD存储，数据存储在本地，需要时拉取其他节点上的数据。由于blockmanager在spark上是私有的，需要封装一个代理类再暴露给python。

简单的分布式数据库：借助blockmanager的思想实现一个简单的分布式数据库，如构建sqlite3，本地数据直接在sqlite中获取，非本地数据通过all_to_all或者scatter等pytorch操作抽取其他节点的数据。

② 图分割方式

如上的方法要求所有数据至少能存入一台机器尤其是边关系，但是当图结构巨大单机无法完全载入时，则必须采用分布式的解决方案，最直接的想法便是将图分割，分发到各executor中执行图采样和计算。

图分割有多种方式，但是大多都是做多次的s-t割，如Karger’s algorithm每次随机选取两个节点进行s-t分割。这些方式并没有原生的spark支持，metis和parMetis需要单独编译部署，因此并没有太多的使用。一种折中的方式是使用社区切分方法，借助LPA、Louvain、业务规则等一些无监督社区发现算法进行图分割。

③ 分布式图采样

使用社区切分可以将图的规模缩小但是分割不一定是均匀的。在Spark中GraphX的随机分割是均匀的，当单一节点放不下边关系时，可以借助spark的blockmanager，对分发到各executor的节点进行邻居采样，可直接借助GraphX的aggregateMessages在消息聚合时进行动态采样。可以将以上过程封装为采样层，每层运算前均需要调用一次采样层。其中，动态采样指的是每次采样固定长度的数据。

④ 预采样分发

之前的采样方式是逐层的方式，因此可以将采样和训练分离开。Pyg的采样服务器本质也是采取分离的方式的。因此可以避开复杂的底层逻辑，直接使用两轮join采样，将一个节点和他的邻居放在一起直接抽样好然后分发。

如下总结了常见的情况和对应的部署方式，前四个都是pyg支持的，最后一个是通用性最强的也是普遍采用的方式，只是速度上相较其他几种稍微慢些。

⑤ 回溯问题与预采样

在标签预测时，训练集的节点属性，节点间的关联关系以及节点的邻居属性都必须在标签状态时间之前获取，因此，需要为每个训练节点构建回溯子图，结合预采样分发的思路直接分发后调用pyg进行分布式训练。

02Inductive类常用算法

无监督学习只利用未标记的样本集，监督学习只利用标记的样本集进行学习，同时利用标记样本和未标记样本的是半监督学习。图算法在学习过程中由于邻居节点不一定包含标签信息因此属于半监督学习。传统机器学习的样本之间通常是独立的，而图学习的样本之间却是有联系的，所以图学习较传统机器学习更为复杂。

1. 矩阵分解类

该类型的方法特点是快速，但是对图中属性信息和结构信息融合比较困难。目前主要应用在属性较少的图上或者进行图结构的压缩的任务上。

① Deepwalk

Deepwalk和Node2vec都是基于矩阵分解类的，其中一个重要的模块是skip-gram。Skip-gram是对逐点互信息矩阵进行分解，其中W代表中心词，C为对应的上下文。

Deepwalk本质是在做共现矩阵的分解，走几步就是几个邻接矩阵的加和，所以分解过程和skip-gram的过程相同。当图上节点缺乏结构关系时，依旧可以通过属性分解的方式构建。对于没有结构关系的节点使用节点属性构建余弦相似度矩阵S，分解为H与H转置的乘积，而具有相邻关系的节点对应隐变量h也应该相近。

2. 编码器类

矩阵分解类很难融合图中节点的结构信息和属性信息，可以通过编码器对信息进行压缩后重构的方式融合信息，压缩后的编码即为embedding。编码器可以使用各种实现方式，非常自由，但是编码器很难获得k-hop的信息。

较为常见的方法是LINE，其通过余弦相似度还原边权重建模一阶相似度。二阶相似性采用word2vec的思路训练，上下文相似的节点也相似。di为当前节点i的所有边权重之和。最终通过拼接一阶相似度向量和二阶相似度向量得到最终的embedding。但是由于二者尺度和方向的差异，可能会对最终结果有影响，所以使用较少。

一阶建模节点之间的相似度，二阶相似度衡量的是节点的邻居节点集合的相关程度即邻接矩阵A每行之间的相关程度。SDNE通过深度自编码方式重构邻接矩阵A保留二阶相似度。一阶相似度采用隐藏层表示的距离来计算，所以最终的损失函数为一阶loss与二阶loss以及正则项的和。

将一阶和二阶信息放到一个解码器中很容易造成相互影响。因此回到LINE的思路，采用一个编码器和两个解码器的方式减少二者的影响同时也增加了训练参数。一阶信息的重构使用一阶邻域的属性信息做加权平均或者做元素级平均来重构，高阶信息可以通过重构邻接矩阵或者使用上下文向量的方式重构。

当需要考虑属性信息时，可以对属性信息重构将属性信息加入。高阶相似度和一阶相似度与SDNE相似。

同时还需要考虑拼接一致性的问题。通常假设相同节点在两个视图中的隐层表示比较接近，不同且不相邻节点应该远离。在拼接时可能会有不一致的问题比如尺度不一会导致一个视图的影响盖过另一个，或者方向不一导致结果减弱或者抵消。

3. GCN等深度网络类

首先介绍卷积的推广。卷积是在拉普拉斯算子的特征向量构成的空间上的操作。把函数映射到该空间就是对函数做傅里叶变换。卷积就是在该空间上的操作，可以保证频谱不变性。

图上的拉普拉斯矩阵通常是通过热传导方程推导的。对于一维和多维的情况推导如下，其中D表示节点的度矩阵。

迪利克雷能量用于衡量图上属性函数的震荡情况，一般由图上节点的梯度和来表示。

GCN的过程是首先构造图的拉普拉斯矩阵，计算拉普拉斯特征向量。将特征向量空间当作傅里叶空间，直接将属性映射到该空间即可。但是由于卷积核参数巨大，通常使用切比雪夫多项式进行近似。将cheby核限制在2阶就可以得到常用的GCN表达式。

由于GCN需要用到整个邻接矩阵，因此学习方式是transductive类的。但是因为GCN在每次聚合时只选择邻居节点，所以有工作如graphsage在GCN上做了改进可以实现inductive方式的学习。具体过程如下，主要的差别在于聚合操作，不再限制为加和而可以使用如means等方式。

GAT相较于graphsage增加了注意力，按照一定的权重聚合邻居的表示。GIN分析了GCN和GraphSage在聚合后无法保持单射的问题，使用MLP作为更新函数并加入了自身信息减少扰动。

4. 模型训练方式与评价

① 折叠式训练

将近邻的节点分层聚合，缩小网络规模，训练好后逐步打开，使用社区值初始化继续后续的训练直至收敛。这种方式速度快、易训练，有时单机就可以完成小规模的图训练。

② AUC与假设检验

验证模型是否有效需要进行假设检验。AUC是一种U的统计量，是非参数顺序统计量，具有渐进正态性。样本量越大，其正态性越好。不同的样本AUC是不具备可比性的。

③ IV值

除了对模型的有效性进行检验还要对模型的输出进行评估。模型输出的embedding或者得分对于下游任务是否有用？有多少用？也需要评估。IV值本质上是对称的KL散度，衡量分布差异的程度。

03Transductive类常用算法

Transductive是直推式算法，需要利用整个图的信息，只能预测图上已有的节点，不能预测未知节点信息。原始GCN就采用这种方式，需要对全图的邻接矩阵做归一化后进行卷积。transductive必须进行全图操作，由于仅同构图的边数量能达到几百亿的规模，节点的度更是服从指数型分布，于是经常会遇到内存不足的问题。

1. GraphX框架及优化经验

① 传播框架

目前的传播框架有两种：

Pregel：顶点接收上个超步传递来的信息，整合并修改顶点，设置顶点活跃状态，活跃节点传递消息给邻居，结束该阶段超步。

GAS：GAS是GraphLab提出的，将图消息传播抽象为Gather, Apply, Scatter三个阶段，Gather/Scatter只针对单条边，Gather的返回值由graphlab求和计算。

GraphX主要使用Pregel，也借鉴了GAS的部分思想。GraphX需要手动判断节点活跃与否，并不会自动设置节点的活跃状态。动态传播需要在传播消息时判断节点活跃状态，手动实现不活跃节点不传播。

② 相关优化

精度要求不高，可以将double换为float；若属性向量特别多，densevector换为SparseVector；每一轮迭代后需要及时unpersist。

2. 为GraphX增加参数学习能力

GraphX是没有参数学习能力的，我们需要构建一些参数并在节点之间同步。此时便可以利用blockmanager或者pytorch存储参数。根据具体业务设计loss求解参数。

3. 各类算法与相关应用

① 模式匹配

主要查找特定用户、反作弊、查找异常点等。通常使用的是graphframe，其中有一个motiffinding操作可以匹配一些模式。

② 标签传播

标签传播是比较常用的操作。Louvain是使用社区模块进行社区化衡量的标准，也适用于标签传播。标签衡量标准通常是依据业务自主设计的，传播方案也需要根据业务、数据类型做设计。一般采用衰减形式的传播或者归一化的传播并配合阈值。

③ 属性传播

属性传播主要用于补充缺失属性为后续模型或业务提供支持。常常采用的假设是同配假设即高纬度与高纬度节点相连接，相似节点相连接。这里的传播没有学习过程，不需要调节参数，因此数据集选择也不需要回溯。

④ 中心度计算

中心度计算是比较重要且常用的任务如pr, ppr, kcore, triangle, degree等，可以为后续任务提供信息。这里有一个基础理论即Perron-Frobenius定理，表示非负不可约矩阵一般等于强连通图，即谱半径为最大特征值，对应唯一的严格为正的特征向量。

在计算节点中心度之前会假设节点已经有一个中心度，可以通过邻居节点中心度的和来更新当前节点的中心度。鉴于以上定理，特征向量中心度就是直接求邻接矩阵最大特征值对应的特征向量，每一维对应各个节点的中心度。同时，也可以对特征向量中心度做归一化。

Pagerank系列的算法都是从特征向量中心度的基础上发展而来的，比如PageRank就是在归一化的特征向量中心度的基础上加了一个跳出机制，避免出度为0的节点的影响。

04总结展望