Part 01
● 什么是图嵌入 ●
图嵌入是将图结构数据映射为低维稠密向量的过程,同时使得原图中拓扑结构相似或属性接近的节点在向量空间上的位置也接近,能够很好地解决图结构数据难以高效输入机器学习算法的问题。
对于图的表示和存储,最容易想到的是使用邻接矩阵的方式。对图中的每个节点进行编号,构造出一个

Part 02
● 基本概念 ●
概念1 图:
图表示为







概念2 同构图:
图

概念3 异构图:
图


概念4 一阶相似度:
如果连接两个节点的边的权重较大,则它们之间的一阶相似度越大。节点







概念5 二阶相似度:
如果两个节点邻近的网络结构越相似,则它们之间的二阶相似度越大。节点






图1 二阶相似度示意图
概念6 图嵌入:
给定输入图,以及预定义的嵌入维数,图嵌入是要在尽可能保留图属性的前提下,将图转换到维空间。依赖一阶相似度或高阶相似度量化图属性的保留程度,使用一个维向量或一组
Part 03
● 图嵌入算法分类 ●
在过去几十年,研究人员们提出了许多优秀的算法,在社交网络、通信网络等场景中被证明具有显著的效果。业界通常根据输出粒度的差异将这些图嵌入算法分为以下三类:
(1)节点嵌入
节点嵌入是最常见的类型,在低维空间中用向量对图中的每一个节点进行表示,“相似”节点的嵌入向量表示也是相似的。当需要对图中的节点进行分析,进而执行节点分类或节点聚类等任务时,通常会选择节点嵌入。
(2)边嵌入
在低维空间中用向量对图中的每一条边进行表示。边由一对节点组成,通常表示节点对关系。当需要对图中的边进行分析,执行知识图谱关系预测或链路预测等任务时,适合选择边嵌入。
(3)图嵌入
在低维空间中用向量对整个图进行表示,通常是分子或蛋白质这样的小图。将图表示为一个向量便于计算不同图之间的相似性,从而解决图分类问题。
不同的任务需求决定了选用的图嵌入算法,由于篇幅原因,这里节选出节点嵌入中的DeepWalk算法和Node2Vec算法来进行相对详细的学习。
Part 04
● 经典图嵌入算法 ●
1.DeepWalk算法
受自然语言处理领域中word2vec思想的启发,Perozzi等为了建立学习图中节点表示向量的模型,将节点与节点的共现关系类比于语料库中词与词的共现关系,提出了DeepWalk算法。通过随机游走的方式采集图中节点的邻居节点序列,相当于节点上下文的语料库,进而可以解决图中节点之间共现关系的提取问题。预先设置好节点序列的长度和起点,随机游走策略将会指导如何在邻居节点中确定下一个游走节点,重复执行该步骤,即可获得满足条件的序列,随机游走示意图如图2所示。
图2 随机游走示意图
将word2vec算法中的单词对应成图中的节点

为了更进一步学习节点的潜在特征表示,DeepWalk算法引入了映射函数

概率的计算同样需要参考word2vec算法中的skip-gram模型。
如图3所示,skip-gram模型包含两个关键的矩阵,一个是中心词向量矩阵

在随机游走过程中,不考虑采样序列中节点与节点的顺序关系,这能够更好地反映节点的邻近关系,同时减少了计算成本。
图3 skip-gram模型示意图
2.Node2Vec算法
在DeepWalk算法的基础上,研究者Grover A和Leskovec J提出了Node2Vec算法。Node2Vec算法对DeepWalk算法中通过随机游走生成节点序列的过程进行优化,定义参数



式中



图4 Node2Vec随机游走策略示意图
Node2Vec的随机游走策略是根据两个参数进行控制的,如图4所示。假设经过边











当游走采样从节点

(1) 当

(2) 当



(3) 当




也就是说,参数



Part 05
● 总结 ●
随着信息技术的快速发展,网络环境变得日益复杂,网络攻击频发,其中APT攻击呈高发态势,是企业需要关注的安全问题。事实上,APT攻击发生的基本环境——网络,本身就是一个由计算机等元素构成的网络结构,这也不难联想到使用图数据结构来表达这些元素间的关系,再将攻击检测问题转化为图中的节点、边或子图分类任务。图嵌入是一个丰富且极具研究空间的问题,如何提高模型训练效率、创新模型构造方法、将图嵌入的思想应用于更多的生产实践,企业需要通过更进一步的研究,才能找到更好的答案。
参考文献
[1]Xu M. Understanding graph embedding methods and their applications[J]. SIAM Review, 2021, 63(4): 825-853.
[2]Cai H, Zheng V W, Chang K C C. A comprehensive survey of graph embedding: Problems, techniques, and applications[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(9): 1616-1637.
[3]Goyal P, Ferrara E. Graph embedding techniques, applications, and performance: A survey[J]. Knowledge-Based Systems, 2018, 151: 78-94.
文章版权声明
1 原创文章作者:2502,如若转载,请注明出处: https://www.52hwl.com/53927.html
2 温馨提示:软件侵权请联系469472785#qq.com(三天内删除相关链接)资源失效请留言反馈
3 下载提示:如遇蓝奏云无法访问,请修改lanzous(把s修改成x)
4 免责声明:本站为个人博客,所有软件信息均来自网络 修改版软件,加群广告提示为修改者自留,非本站信息,注意鉴别









微信扫一扫
支付宝扫一扫