图表示学习是一种把模型跟机器学习方法相结合的一类技术，当前比较热门的主要有两大类：图嵌入(Graph Embedding)和图神经网络(Graph Neutral Network)。图模型的应用非常广泛，如社交网络，通信网络。在安全领域图模型也有关越来越广泛的应用，比如黑灰产团伙挖掘、安全知识图谱、欺诈检测等等。
一、背景介绍
图表示学习是一种把模型跟机器学习方法相结合的一类技术，当前比较热门的主要有两大类：图嵌入(Graph Embedding)和图神经网络(Graph Neutral Network)。图模型的应用非常广泛，如社交网络，通信网络。
在安全领域图模型也有关越来越广泛的应用，比如黑灰产团伙挖掘、安全知识图谱、欺诈检测等等。真实的图或网络往往是高维的难处理的，为了对这种高维数据进行降维，图嵌入技术应运而生，图嵌入的本质是在尽量保证图模型的结构特性的情况下把高维图数据映射到低维向量空间。发展到现在图嵌入技术已经不仅仅是一种降维方法，与深度学习相结合后图嵌入技术可以具有更复杂的图计算与图挖掘能力。
黑灰产团伙挖掘是安全领域中图模型应用的一个典型场景。国内黑灰产的规模已逐渐形成了一个年产值达千亿元级别的庞大“黑金”利益链，并通过上中下游的严密分工构建起了一个密切协作的网络，严重威胁企业发展。如何揪出这些“地下黑产”，进而构建动态的预警机制成为所有企业和用户关注的话题。黑灰产团伙挖掘所面临的主要挑战是传统图挖掘方法很难有效的从图模型中提取全局特征，从而忽略潜在的关联关系，面对黑产动则十亿、百亿级的数据无能为力。我们看看从技术的角度看看图嵌入如何处理当前黑灰产团伙所面临的挑战。
二、图嵌入与社区发现相关技术介绍
图嵌入是图表示学习的一种，简单的来说就是把图模型映射到低维向量空间，表示成的向量形式还应该尽量的保留图模型的结构信息和潜在的特性。自从word2vec这个神奇的算法出世以后，导致了一波嵌入（Embedding）热，基于句子、文档表达的word2vec、doc2vec算法，基于物品序列的item2vec算法，基于图模型的图嵌入技术，无论是在引荐、广告还是反欺诈范畴，各互联网公司基于本身业务与嵌入结合的论文相继问世。
当前比较知名的图嵌入方法有DeepWalk[1]、Line[2]和Node2vec[3]，这些都是基于顶点对相似度的图表示学习，仅仅保留了一部分的图的特性。其实黑灰产团伙挖掘本质是图模型中的社区发现，而传统社区发现算法大都从图结构出发，只能考虑局部关联，对于某一顶点在整个图模型中的关联无能为力。那么我们就来看看图嵌入技术在社区发现的从“青铜”到“王者”的升级之路。也为我们黑灰产团伙挖掘等一些安全领域的图挖掘提供借鉴方法。
2.1 图嵌入（graph embedding）-DeepWalk
这里主要讲Deepwalk，该方法是嵌入技术中的代表，大部分图嵌入技术都是基于该方法的扩展。下图是图嵌入技术的通用流程。
图1 图嵌入流程
首先图1（a）中是用户行为，从知识图谱的角度可以抽象成图1（b）中的图模型。在当前推荐系统和安全领域都比较常见，而对于抽象的图模型如何利用图嵌入技术处理呢？首先， DeepWalk将随机游走得到的节点序列当做句子，从截断的随机游走序列中得到网络的部分信息，再经过部分信息来学习节点的潜在表示。该方法借助语言建模word2vec中的一个模型，skip-gram来学习结点的向量表示。将网络中的结点模拟为语言模型中的单词，而结点的序列（可由随机游走得到）模拟为语言中的句子，作为skip-gram的输入。可以看出在表示图模型中图嵌入技术有天然的优势，因为它本身把多维图模型映射到同一向量空间，顶点之间的关联关系可以通过顶点向量的相似度计算，任一顶点与其他顶点的潜在关系都可以很快的计算出来。
2.2 涉及相关技术简介
下面为了保证知识的全面性，介绍与社区发现的一些相关知识，但是通常大家对公式有一种本能的排斥，这里就不罗列公式了只说明一下。模块度是衡量社区划分质量的，把一个顶点划为哪个社区使得模块度最大就把它划归哪个，知道这里就可以。
顶点的近似性这个更好理解了，如果把顶点都变成向量了，那在图中相邻的顶点跟不相邻的顶点的区分在哪里？这就需要顶点对的近似性，一阶近似就是有直接边的近似度高，仅此而已。
二阶相似要复杂一些，就是考察两个顶点的邻居顶点有多少一样的顶点。非负矩阵可以当成一种降维方法，一个非负矩阵变成两个非负矩阵左边的不用管，看成是基矩阵，右边的才是表示矩阵。
给定一个网络G=（V,E）其中V表示网络中所有的顶点，E表示网络中所有边的集合。网络表示学习的目的就是找到映射：
使得每一个顶点都映射到一个d维的空间。
2.2.1模块度
Newman 在2003年的文献[4]中首次提出了modularity的定义，在论文中用来度量自己的社团检测算法的好坏。
这里直接给出最常用的模块度公式：
本质是：
2.2.2图嵌入中的近似性
定义1：一阶近似性表示网络顶点对之间的局部近似度，对于任意一条边（u,v），边的权重越大，u和v的一阶近似度也越大。
一阶近似性的数学公式如下：
定义2：二阶近似性表示一个结点对“上下文环境”下的结构相似度。
二阶近似性的数学公式如下：
如果想要详细理解这些公式，可以参考DeepWalk，Line等论文。
2.2.3非负矩阵分解
NMF(Non-negative matrix factorization)，即对于任意给定的一个非负矩阵V，其能够寻找到一个非负矩阵W和一个非负矩阵H，满足条件V=W*H，从而将一个非负的矩阵分解为左右两个非负矩阵的乘积。其中，V矩阵中每一列代表一个观测(observation)，每一行代表一个特征(feature)；W矩阵称为基矩阵，H矩阵称为系数矩阵或权重矩阵。这时用系数矩阵H代替原始矩阵，就可以实现对原始矩阵进行降维，得到数据特征的降维矩阵，从而减少存储空间。过程如下图所示：
图2 非负矩阵分解
对于非负矩阵理解到这就可以了，如果还想了解可以参考各大神的论文。
三、图嵌入技术在社区发现应用中的升级之路
最近两年图表示学习成为深度学习的新的热点，几乎成了万物皆可成图的现象，咱们先不讨论这样做是否合理，只是从技术的角度看看大牛们是如何利用图表示学习进行社区发现的。
3.1 图嵌入技术的“白银”
清华大学团队在AAAI2017年的文献[6]是最早的一篇利用图嵌入技术进行社区发现的文章。该论文的出发点是已有的图嵌入方法没有保存图模型中的社区特性，因此，很难适用社区发现方法。基于此，该文提出了一种基于模块度的非负矩阵分解的图嵌入模型。在图嵌入学习中不仅考虑了顶点对之间的相似特性，同时考虑了顶点与社区之间的相似度。
下面来看看该论文是怎么把社区信息融入到图表示学习中的。该文把图结构的信息分为微观结构信息和中观结构信息（mesoscopic structure）。这里所谓的微观结构信息指的是图模型上的一阶相似和二阶相似性，中观结构信息表示社区信息，那么在处理的过程中该文如果融合社区信息的呢？
下面这个公式就是该文的核心：
其实这个公式包含了一个部分，第一项：
的意思是图的邻接矩阵与该矩阵的非负矩阵分解的代价函数，目的就是一到一个好的非负矩阵分解，而非负矩阵分解是是图表示一种方法。第二项阵C是一个表示社区信息的辅助矩阵，那么很显示UCT表示的是图模型中的顶点与所有定义的社区之间的关联关系，我们所期望的是顶点的表示尽可能的跟社区指示信息想近，也就是：
第三项是是引入模块度的定义，也是在图嵌入的过程要保证社区特性。
选择完了目标函数，可以进行优化了吧，不过不幸的是该目标函数不是一个凸函数，无法利用凸优化直接进行计算。该文把目标函数拆分成四个子问题进行迭代计算，这里具体的优化方法就不详细写了，如果感兴趣的可以参考原文，思路很简单。
但是这种流程式的方法没有充分利用社区信息，流程化方法就是按如下步骤执行的方法。（1）运行社区发现方法，可以运行谱聚类。为每个顶点获得类标签（2）应用顶点嵌入，为每个顶点获得一个嵌入向量（3）聚类顶点嵌入向量，然后对每个社区进行高斯混合。然而，这种流水线方法缺乏统一的目标函数，因此很难用顶点嵌入来优化。
3.2 图嵌入技术中的“黄金”
由于顶点嵌入很好地保持了低维空间中的网络结构，所以它可以有效的改进社区发现的效果。社区嵌入的可能方法是直接对节点嵌入结果进行社区发现，从而为每个社区建立一个基于顶点嵌入向量的多变量高斯分布。也就是在GMM的基础上将社区发现和嵌入到一个单一的目标函数中。然而，这种方法也是次优的，因为大多数现有的顶点嵌入方法都不知道社区结构，这使得顶点嵌入向量对于接下来的社区发现不太好。基于此，Sandro Cavallari 等人在CIKM2017上提出了一种经典的社区表示学习方法[7]。在这篇文章中首次引入社区嵌入，社区嵌入可以描述其成员顶点在低维空间中的分布情况，所以不能简单的把社区看成一个向量，而是低维空间中的分布（高斯混合分布）。
一方面，顶点嵌入可以帮助改进社区发现，从而输出良好的社区以适应更好的社区嵌入，另一方面，社区嵌入可以通过引入一个社区感知高阶近似性来优化顶点嵌入。在这个指导下，提出了一个新的社区嵌入框架，如图3、4所示。
图3 社区感知的图嵌入方法
图4 社区感知的图表示框架
为了关闭循环，我们需要启用从社区发现和社区嵌入到顶点嵌入的反馈。因此，仅通过保持一阶邻近性，我们可能无法很好地区分其社区成员之间的差异。在闭环的基础上，对社区发现、社区嵌入和顶点嵌入进行了优化。需要考虑三种类型的顶点嵌入一阶近似、二阶近似和高阶近似。通常，有两种方法可以将不同类型的邻近性结合起来用于顶点嵌入：（1）首先分别优化这种近似表示的目标函数，然后将每个顶点的两个嵌入到一个长向量作为最终输出；（2）单个顶点嵌入，以同时保持一阶和二阶邻近性。
3.3 图嵌入技术中的“王者”
但是这里有一个问题就是所有的都是利用多变量高斯分布来拟合的。爱丁堡大学的Benedek Rozemberczki针对上文存的问题在文献[8]中提出了一种新的学习聚类信息的图嵌入方法。
该文章的思想是什么呢？按传统先上个公式。
最终的目的就是学习一种图嵌入的表示形式嘛，从似然函数的思路出发，就是估计这个图嵌入表示参数。这个公式中的 Ns(v) ，表示包含顶点v的一系列顶点序列，这里想要理解需要对word2vec有一定的认识。
f函数是顶点的embedding函数也就是顶点到低维向量空间的映射函数，去掉负号就是一个最大似然估计。作者认为上一个工作利用多变量高斯分布来表示分布概率并不合理，那么如何来找一个合理的分布函数P（|）是这个工作的核心。作者认为该分布函数必须满足两个性质：1 条件独立性（这个好像其他方法也满足）；2 顶点对在特征空间中表示的对称性。
满足性质1的话概率分布函数可以表示成：
针对性质2，作者选择了softmax函数：
整合性质1和性质2可以得到目标函数：
该目标函数第一项是把图数据映射到低维向量空间，第二项可以使相邻的顶点在表示空间中尽可能相近。但是这只是图表示的目标并没有包含社区和聚类信息。
下面看该论文是如何解决这个问题的，上公式：
最后一项就是顶点到社区中心的距离公式， 表示社区中心（聚类中心）。最后利用梯度下降法对目标函数进行优化，就是这么简单。
看着是不是还没有上面的高大上，不过有一些比较好的是对于参数 的选择给出了详细的方法，利用指数退火规则（exponential annealing rule）：
到了这里图嵌入技术在社区发现中已经相当完善，该技术不仅把社区信息引入到了最终的顶点向量表示中，同时还通过图向量表示来优化社区发现过程这是一个相互促进的过程。
那么从黑灰产团伙的角度来看这些图嵌入技术是否能改善传统社区发现方法呢。
第一，图嵌入技术能从整个图模型的全局视角来进行分析，尤其是在黑灰产团伙中局部关联中无法发现的潜在异常都可以通过图嵌入技术来解决；
第二，面对大规模图挖掘问题，图嵌入利器PythorchBigGraph现在可以快速的处理亿级数据的嵌入，传统的图挖掘在处理亿级图社区发现上依然是耗时耗力的。
四、结论
通过对图嵌入技术的说明，可以遇见在黑灰产团伙挖掘这种业务安全场景中，图嵌入技术是连接知识图谱和深度学习的桥梁，同时能提供一个全局视角来更清晰的洞察不同实体的潜在关联。但是通图嵌入技术解决了传统社区发现的一些问题，在安全领域图模型的规模已经突破10亿达到百亿级。同时业务安全中数据的更新频率很快，动态图嵌入技术的需求就提了出来，图嵌入技术最终要走向处理大规模图和动态图的方向。
五、参考文献
1 Perozzi B , Al-Rfou R , Skiena S . DeepWalk: Online Learning of Social Representations[J]. 2014.
2 Jian T, Meng Q, Wang M, et al. LINE: Large-scale Information Network Embedding[C]// International Conference on World Wide Web. 2015.
3 Grover A , Leskovec J . node2vec: Scalable Feature Learning for Networks[J]. 2016..
4 Newman M E J , Girvan M . Finding and Evaluating Community Structure in Networks[J]. Physical Review E, 2004, 69(2 Pt 2):026113..
5 https://blog.csdn.net/ztf312/article/details/80680263.
6 Wang X , Cui P , Wang J , et al. Community Preserving Network Embedding[C]// The 31st AAAI Conference on Artificial Intelligence. 2017..
7 Cavallari S , Zheng V W , Cai H , et al. Learning Community Embedding with Community Detection and Node Embedding on Graphs[C]// the 2017 ACM. ACM, 2017.
8 Rozemberczki B , Davies R , Sarkar R , et al. GEMSEC: Graph Embedding with Self Clustering[J]. 2018.