本次论文研读系列推文来自知识图谱硕士课程课堂展示。其中来自数据科学、管理科学与工程、保密管理等专业13位同学选择了知识图谱相关的前沿论文进行精读。我们将从KG construction，KG representation以及综述三个专题进行成果展示。本期展示主题为综述。
摘要：
图形是一种重要的数据表示形式，它出现在各种各样的现实世界场景中。有效的图形分析使用户能够更深入地了解数据背后的内容，从而可以使许多有用的应用程序受益，例如节点分类，节点推荐，链接预测等。然而，大多数图形分析方法都面临着高昂的计算和空间成本。图嵌入是解决图分析问题的一种有效而高效的方法。它将图数据转换为低维空间，其中图结构信息和图属性得到最大程度的保留。在本次调查中，我们对图嵌入的文献进行了全面回顾。我们首先介绍图嵌入的正式定义以及相关概念。之后，我们提出了两种图嵌入分类法，它们对应于不同图嵌入问题设置中存在的挑战以及现有工作如何在其解决方案中解决这些挑战。最后，总结了图嵌入在计算效率、问题设置、技术和应用场景等方面的四个未来研究方向。
关键词：分类学；任务分析；电子邮件；玩具制造业；二维显示；机器学习
![论文精讲 | 图嵌入的综合调查：问题、技术和应用]( "论文精讲 | 图嵌入的综合调查：问题、技术和应用")
论文标题：
A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications
会议：
IEEEE2018
论文地址：
Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications | IEEE Journals & Magazine | IEEE Xplore
———————————————————————————————
01定义
图可以理解为一个代数系统，本文对图及其不同的特点加以介绍。
系统G(V, E)，节点v∈V，边e∈E，节点类型映射fv: V→Tv， 边类型映射fe: E→Te。
系统Ghomo(V, E)，在图的定义基础上增加约束：| Tv | = | Te | = 1。
系统Ghete(V, E)，在图的定义基础上增加约束：| Tv | + | Te | > 2。
系统Gknow(V, E)，在图的定义基础上增加约束：有向图，对于一条知识三元组，节点表示实体h和t，边代表h→t方向的一条关系r。在图嵌入的过程当中，两个节点之间的一阶相似度和二阶相似度常被用作图嵌入属性的量化描述。
s(1)ij，表示节点vi和vj之间边eij的权重，即Aij（A为邻接矩阵），权重越高节点间越相似。
s(2)ij，表示vi的邻居节点s(1)i和vj的邻居节点s(1)j的相似度。s(2)ij=cosine(s(1)i , s(1)j)。
根据节点是否带权，是否有向，输入的方式会有些不同。带权：节点间权重越大，嵌入时距离越近。
1. 同质图中只有图的结构信息，如何保留连接中的模式信息；
![论文精讲 | 图嵌入的综合调查：问题、技术和应用]( "论文精讲 | 图嵌入的综合调查：问题、技术和应用")
应用场景：社区问答、多模态网络、知识图谱、通用异质图结构。
常见辅助信息类型：标签、属性、节点特征、信息传播路径信息、知识库。
前提：输入数据在相对低维流型(manifold)中节点/边带有辅助信息。
特征矩阵X∈R|V|×N，并得到(Xi, Xj)之间相似度矩阵S，利用S构造图。
2. 生成节点的邻接矩阵嵌入时保持图的结构(其它所有图的类型共有的问题)。
Note：如何理解“低维流型”？人工智能领域的一个基本想法就是：自然界中同一类别的高维数据(例如图像)，往往集中在某个低维流形附近——流型分布定律。所谓“流型结构”是来自拓扑几何和微分几何的基本概念，本质上就是很多的欧式空间粘贴在一起构成的抽象空间。从非结构化数据进行输入的过程中，由于特征矩阵的样本点空间R|V|×N就只有这两个维度，因此输入数据需要基于“包含有效信息的维度不能太高”这一假设，否则人工进行降维的过程中，极可能丢失一些有意义的信息。
任务驱动(因具体任务的不同，输出嵌入的形式会有所不同)
嵌入类型：节点嵌入；边嵌入；混合嵌入；整张图嵌入。
研究难点：如何对成对节点相似性进行定义、学习和抽取。
2. 将“节点对”特征嵌入，对比节点对之间的特性 / 预测边的存在性。
Note: 下图给出了“社区嵌入”的一个示意（来源：Cavallari S, Zheng V W, Cai H, et al. Learning community embedding with community detection and node embedding on graphs[C]//Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. 2017: 377-386.）
所谓“社区”，是表示的彼此之间有密集连接的一系列节点簇，社区嵌入就是把这些密接节点嵌入到低维空间中来。
混合嵌入的输出目标是很灵活的，由于不同的子结构具有异质性，嵌入不同种类的子结构到同一个空间里面去的时候，异质信息的融合就又是一个问题了。
下图给出了图嵌入的5类技术方法，每种方法各有利弊。
1. 要保留的图的属性可以被解释为成对的节点相似性；
2. 因此，相似性较大而节点嵌入距离远的情形出现，会进行惩罚。
不足：基于随机游走的算法每次只能考虑一条路径的上下文信息，而且采样比较麻烦；
1. 给定某一节点的前提下，最大化其邻居的概率分布；
(来源：Xu M. Understanding graph embedding methods and their applications[J]. SIAM Review, 2021, 63(4): 825-853.)
思想：节点嵌入得足够好时，图中原本有边的地方，生成边概率越大。
思想：节点嵌入后计算得到的相似度，接近于原始节点计算出来的相似度。
3.4 图内核（Graph-kernel）的思想方法
思想：一个复杂的图可以被拆成各种基础子结构（原子结构）。
1. Graphlet (图当中非同构的不可再分单元)；
2. 子树模式 (认为图当中的某个序列可能反映在一棵抽象的树结构上，从而将计算节点概率分布的时间复杂度降低)；
3. 随机游走路径 (将错综复杂的网络结构平铺成一系列包含潜在语义的序列状结构)。
1. 考虑节点语义，图的结构直接用嵌入节点的距离表示；
2. 节点的语义信息，可通过生成式模型，从节点属性中检测。
4.1.1 基于节点嵌入的应用
1. 节点分类；
2. 节点聚类；
3. 节点推荐/提取/评分。
4.1.2 基于边嵌入的应用
1. 边的预测；
2. 三元组分类。
4.1.3 基于边嵌入的应用基于整图或者子结构嵌入的应用
1. 图的分类；
2. 可视化。
Note: 这里说的可视化，并不仅仅是指学习使用echarts等这样的工具可视化，而是将嵌入后的结果凸显在一个低维可视空间（如二维、三维图，或者通过在二维图上引入节点颜色深浅、节点大小等方面，在二维图上反映更多信息），通过这种可视化，直观地辅助人理解图嵌入的效果，协助人进行数据分析。
4.2 图嵌入的未来研究
1. 运算效率问题
2. 输入、输出方面进一步的探讨
3. 图嵌入技术方法的进一步研究
4. 图结构在更多基础上的应用问题
Note：第1点“运算效率”，不仅仅是在于对图嵌入的算法进行优化，还在于计算设备在处理图结构的时候，能够更加高效进行处理（例如：硬件层面合理组织存储空间，减少因图矩阵稀疏性带来的存储碎片空间）
—
THE END
指导老师：洪亮
图文：杜文添
编辑：龙雨荷
原文始发于微信公众号（珞珈大数据）：论文精讲 | 图嵌入的综合调查：问题、技术和应用
免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉。
点赞
https://cn-sec.com/archives/1532932.html
复制链接
复制链接
-
左青龙
- 微信扫一扫
-
-
右白虎
- 微信扫一扫
-
评论