Part01什么是图嵌入？图嵌入是将图结构数据映射成低维稠密向量的过程，同时使得向量空间中原图中具有相似拓扑结构或属性的节点位置也靠近，可以很好的解决问题图结构的数据很难有效地输入到机器学习算法中。对于图形表示和存储，最容易想到的方法是使用邻接矩阵。给图中的每个节点编号，构造一个矩阵，表示图中节点的个数。图中任意两个节点是否有边相连，决定了邻接矩阵中对应位置的值。这种表示方法非常容易理解和直观，但效率很低。因为真实场景中的图可能包含数以万计甚至更多的节点，而且大部分节点之间没有边连接，这会导致邻接矩阵非常稀疏。使用邻接矩阵来表示和存储图需要很高的计算和空间成本，而图嵌入算法可以有效地解决图分析问题。Part02●基本概念●概念一图：图表示为，其中表示一个节点，表示一条边。关联节点类型映射函数和边类型映射函数。表示节点类型的集合，表示边类型的集合。概念2同构图：graph，where。也就是说，所有的节点都属于一种类型，所有的边都属于一种类型。例如，在社交网络中的用户关注关系图中，只有一种节点类型的用户和一种边类型的关注关系。概念3异构图：其中或的图。也就是说，节点类型或边类型不止一种。例如，在学术网络的图结构中，存在论文、作者、会议等多种节点类型。边之间的关系包括作者与论文、论文与会议之间的创造性关系。论文之间的发表关系，论文与论文之间的引用关系等。概念4一阶相似度：如果连接两个节点的边的权重越大，则它们之间的一阶相似度就越大。节点与节点之间的一阶相似度表示为，其中是节点与节点之间边的权重。概念5二阶相似度：如果两个节点的相邻网络结构越相似，则它们之间的二阶相似度就越大。节点与节点之间的二阶相似度是的邻域与的邻域之间的相似度。如图1所示，由于有边连接节点f和节点g，节点f和节点g类似于一阶。虽然节点e和节点g没有边连接，但它们有四个相同的邻居节点，所以节点e和节点g是二阶相似的。图1二阶相似度示意图概念6Graphembedding：给定一个输入图和一个预定义的embedding维度，graphembedding就是将图变换到一个维度空间，同时尽可能的保留图的属性。依靠一阶相似度或高阶相似度来量化图属性的保留，图由一个维向量或一组维向量表示，每个向量表示图的一部分的嵌入，例如节点或边缘。Part03●图嵌入算法分类●在过去的几十年里，研究人员提出了许多优秀的算法，并在社交网络、通信网络等场景中被证明具有显着的效果。业界通常根据输出粒度的不同，将这些图嵌入算法分为以下三类：（1）节点嵌入节点嵌入是最常见的类型，图中的每个节点都由一个低维向量表示空间，“相似”节点的嵌入向量表示也相似。当需要分析图中的节点以执行节点分类或节点聚类等任务时，通常会选择节点嵌入。(2)Edgeembedding在低维空间中用一个向量表示图中的每条边。一条边由一对节点组成，通常表示节点对关系。当需要对图中的边进行分析，进行知识图关系预测或链接预测等任务时，适合选择边嵌入。(3)Graphembedding使用一个向量来表示低维空间中的整个图，通常是分子或蛋白质等小图。将图表示为向量，便于计算不同图之间的相似度，从而解决图分类问题。不同的任务需求决定了选择的图嵌入算法。由于篇幅原因，这里选择节点嵌入中的DeepWalk算法和Node2Vec算法进行比较详细的学习。Part04ClassicalGraphEmbeddingAlgorithm1.DeepWalkAlgorithm受到自然语言处理领域word2vec思想的启发，Perozzi等人。比较节点与语料库中单词的共现关系，以建立学习图中节点表示向量的模型。利用词的共现关系，提出了DeepWalk算法。通过随机游走收集图中节点的邻居节点序列，相当于节点上下文的语料库，进而可以解决提取图中节点之间的共现关系问题。节点序列的长度和起始点是预先设置好的。随机游走策略将指导如何在邻居节点中确定下一个游走节点。重复此步骤，得到满足条件的序列。随机游走的示意图如图2所示。图2随机游走示意图word2vec算法中的词对应图中的节点，词序列对应随机游走得到的节点序列。然后，对于随机游走，定义其优化目标函数，如公式所示。为了进一步学习节点潜在的特征表示，DeepWalk算法引入映射函数实现节点到图中维向量的映射，然后将问题转化为估计下式的可能性。概率的计算也需要参考word2vec算法中的skip-gram模型。如图3所示，skip-gram模型包含两个关键矩阵，一个是中心词向量矩阵，一个是背景词向量矩阵。这两个权重矩阵表示与不同角色的词相关联的词向量。.skip-gram是一种预测单词上下文的模型。它首先从语料库中学习单词之间的关系，然后利用这些关系来表达特定单词的上下文，即单词的向量表示。也就是说，在同一个序列中，两个词同时出现的频率越高，这两个词的向量表示就越相似。将这个思想应用到图上，定义其优化目标函数，如公式所示。在随机游走过程中，不考虑采样序列中节点之间的顺序关系，可以更好地反映节点的邻域关系，降低计算成本。图3skip-gram模型示意图2.Node2Vec算法研究人员GroverA和LeskovecJ在DeepWalk算法的基础上提出了Node2Vec算法。Node2Vec算法优化了DeepWalk算法中通过随机游走生成节点序列的过程，定义了参数和参数来指导每次随机游走是倾向于广度优先采样还是深度优先采样，因此具有很高的适应性。假设当前访问过该节点，则下一个访问节点的概率如公式所示。其中表示从节点到节点的转移概率，表示归一化常数。图4Node2Vec随机游走策略示意图Node2Vec的随机游走策略是根据两个参数控制的，如图4所示。假设通过边到达节点v，下一步访问节点x，令,是节点和之间的边权重。也就是说，当图为未加权图时，它直接决定了节点的转移概率。当图为加权图时，边权值的乘积决定了节点最终的转移概率。可以根据以下公式计算，其中是节点间的最短路径距离。当walksample从一个节点走到另一个节点，需要选择下一跳节点时，会出现以下三种情况。(1)届时，返回节点。(2)此时选择节点和该节点的公共相邻节点，如节点。(3)此时选择与该节点无关的节点的相邻节点，如节点或。也就是说，参数控制了返回上一跳节点的概率。该参数控制是探索网络的局部结构信息还是全局结构信息。DeepWalk模型实际上就是sum取1时的Node2Vec模型。Part05●小结●随着信息技术的飞速发展，网络环境日趋复杂，网络攻击事件频发，其中APT攻击是频繁发生，是企业需要关注的安全问题。实际上，APT攻击发生的基本环境——网络本身就是由计算机等元素组成的网络结构。不难想到用图数据结构来表达这些元素之间的关系，然后将攻击检测问题转化为图中的节点、边或子图分类任务。图嵌入是一个具有丰富研究空间的问题。如何提高模型训练效率，创新模型构建方式，将图嵌入的思想应用到更多的生产实践中，需要进一步研究，寻找更好的解决方案。回答。参考文献[1]XuM.Understandinggraphembeddingmethodsandtheirapplications[J].SIAMReview,2021,63(4):825-853.[2]CaiH,ZhengVW,ChangKCC.图嵌入综合综述：问题、技术与应用[J].IEEE知识与数据工程汇刊,2018,30(9):1616-1637.[3]GoyalP,FerraraE.图嵌入技术、应用和性能：综述[J]。基于知识的系统，2018，151：78-94。
