【导读】近年来,随着网络数据量的不断增加,挖掘图形数据已成为计算机科学领域的热门研究课题,在学术界和工业界都得到了广泛的研究。但是,大量的网络数据为有效分析带来了巨大的挑战。因此激发了图表示的出现,该图表示将图映射到低维向量空间中,同时保持原始图结构并支持图推理。图的有效表示的研究具有深远的理论意义和重要的现实意义,本教程将介绍图表示/网络嵌入的一些基本思想以及一些代表性模型。

关于图或网络的文献有两个名称:图表示和网络嵌入。我们注意到图和网络都指的是同一种结构,尽管它们每个都有自己的术语,例如,图和网络的顶点和边。挖掘图/网络的核心依赖于正确表示的图/网络,这使得图/网络上的表示学习成为学术界和工业界的基本研究问题。传统表示法直接基于拓扑图来表示图,通常会导致许多问题,包括稀疏性,高计算复杂性等,从而激发了基于机器学习的方法的出现,这种方法探索了除矢量空间中的拓扑结构外还能够捕获额外信息的潜在表示。因此,对于图来说,“良好”的潜在表示可以更加精确的表示图形。但是,学习网络表示面临以下挑战:高度非线性,结构保持,属性保持,稀疏性。

深度学习在处理非线性方面的成功为我们提供了研究新方向,我们可以利用深度学习来提高图形表示学习的性能,作者在教程中讨论了将深度学习技术与图表示学习相结合的一些最新进展,主要分为两类方法:面向结构的深层方法和面向属性的深层方法。

对于面向结构的方法:

  • 结构性深层网络嵌入(SDNE),专注于保持高阶邻近度。

  • 深度递归网络嵌入(DRNE),其重点是维护全局结构。

  • 深度超网络嵌入(DHNE),其重点是保留超结构。

对于面向属性的方法:

  • 专注于不确定性属性的深度变异网络嵌入(DVNE)。

  • 深度转换的基于高阶Laplacian高斯过程(DepthLGP)的网络嵌入,重点是动态属性。

本教程的第二部分就以上5种方法,通过对各个方法的模型介绍、算法介绍、对比分析等不同方面进行详细介绍。

1、Structural Deep Network Embedding

network embedding,是为网络中的节点学习出一个低维表示的方法。目的在于在低维中保持高度非线性的网络结构特征,但现有方法多采用浅层网络不足以挖掘高度非线性,或同时保留局部和全局结构特征。本文提出一种结构化深度网络嵌入方法,叫SDNE该方法用半监督的深度模型来捕捉高度非线性结构,通过结合一阶相似性(监督)和二阶相似性(非监督)来保留局部和全局特征。

2、 Deep recursive network embedding with regular equivalence

网络嵌入旨在保留嵌入空间中的顶点相似性。现有方法通常通过节点之间的连接或公共邻域来定义相似性,即结构等效性。但是,位于网络不同部分的顶点可能具有相似的角色或位置,即规则的等价关系,在网络嵌入的文献中基本上忽略了这一点。以递归的方式定义规则对等,即两个规则对等的顶点具有也规则对等的网络邻居。因此,文章中提出了一种名为深度递归网络嵌入(DRNE)的新方法来学习具有规则等价关系的网络嵌入。更具体地说,我们提出了一种层归一化LSTM,以递归的方式通过聚合邻居的表示方法来表示每个节点。

3、Structural Deep Embedding for Hyper-Networks

是在hyperedge(超边是不可分解的)的基础上保留object的一阶和二阶相似性,学习异质网络表示。于与HEBE的区别在于,本文考虑了网络high-oeder网络结构和高度稀疏性。

传统的基于clique expansion 和star expansion的方法,显式或者隐式地分解网络。也就说,分解后hyper edge节点地子集,依然可以构成一个新的超边。对于同质网络这个假设是合理地,因为同质网络地超边,大多数情况下都是根据潜在地相似性(共同地标签等)构建的。

4、** Deep variational network embedding in wasserstein space**

大多数现有的嵌入方法将节点作为点向量嵌入到低维连续空间中。这样,边缘的形成是确定性的,并且仅由节点的位置确定。但是,现实世界网络的形成和发展充满不确定性,这使得这些方法不是最优的。为了解决该问题,在本文中提出了一种新颖的在Wasserstein空间中嵌入深度变分网络(DVNE)。所提出的方法学习在Wasserstein空间中的高斯分布作为每个节点的潜在表示,它可以同时保留网络结构并为节点的不确定性建模。具体来说,我们使用2-Wasserstein距离作为分布之间的相似性度量,它可以用线性计算成本很好地保留网络中的传递性。此外,我们的方法通过深度变分模型隐含了均值和方差的数学相关性,可以通过均值矢量很好地捕获节点的位置,而由方差可以很好地捕获节点的不确定性。此外,本文方法通过保留网络中的一阶和二阶邻近性来捕获局部和全局网络结构。

5、Learning embeddings of out-of-sample nodes in dynamic networks

迄今为止的网络嵌入算法主要是为静态网络设计的,在学习之前,所有节点都是已知的。如何为样本外节点(即学习后到达的节点)推断嵌入仍然是一个悬而未决的问题。该问题对现有方法提出了很大的挑战,因为推断的嵌入应保留复杂的网络属性,例如高阶邻近度,与样本内节点嵌入具有相似的特征(即具有同质空间),并且计算成本较低。为了克服这些挑战,本文提出了一种深度转换的高阶拉普拉斯高斯过程(DepthLGP)方法来推断样本外节点的嵌入。DepthLGP结合了非参数概率建模和深度学习的优势。特别是,本文设计了一个高阶Laplacian高斯过程(hLGP)来对网络属性进行编码,从而可以进行快速和可扩展的推理。为了进一步确保同质性,使用深度神经网络来学习从hLGP的潜在状态到节点嵌入的非线性转换。DepthLGP是通用的,因为它适用于任何网络嵌入算法学习到的嵌入。

成为VIP会员查看完整内容
0
181

相关内容

清华大学是中国乃至亚洲最著名的高等学府之一。其前身即1911年利用美国退还庚子赔款之退款在北京设立之清华学堂,1912年中华民国成立后改为清华学校,1928年北伐后由国民政府改制为国立清华大学。对日抗战期间西迁昆明,与北京大学、南开大学合组国立西南联合大学。1946年迁返北平复校。

现实网络由多种相互作用、不断进化的实体组成,而现有的研究大多将其简单地描述为特定的静态网络,而没有考虑动态网络的演化趋势。近年来,动态网络的特性跟踪研究取得了重大进展,利用网络中实体和链接的变化来设计网络嵌入技术。与被广泛提出的静态网络嵌入方法相比,动态网络嵌入努力将节点编码为低维密集表示,有效地保持了网络结构和时间动态,有利于处理各种下游机器学习任务。本文对动态网络嵌入问题进行了系统的研究,重点介绍了动态网络嵌入的基本概念,首次对现有的动态网络嵌入技术进行了分类,包括基于矩阵分解的、基于跃格的、基于自动编码器的、基于神经网络的等嵌入方法。此外,我们仔细总结了常用的数据集和各种各样的后续任务,动态网络嵌入可以受益。在此基础上,提出了动态嵌入模型、大规模动态网络、异构动态网络、动态属性网络、面向任务的动态网络嵌入以及更多的嵌入空间等现有算法面临的挑战,并提出了未来可能的研究方向。

成为VIP会员查看完整内容
0
72

题目: A Survey on Dynamic Network Embedding

简介:

现实世界的网络由各种相互作用和不断发展的实体组成,而大多数现有研究只是将它们描述为特定的静态网络,而没有考虑动态网络的发展趋势。近来,在跟踪动态网络特性方面取得了重大进展,它利用网络中实体和链接的变化来设计网络嵌入技术。与静态网络嵌入方法相比,动态网络嵌入致力于将节点编码为低维密集表示形式,从而有效地保留了网络结构和时间动态特性,这对众多下游机器学习任务是有益的。在本文中,我们对动态网络嵌入进行了系统的调查。特别是,描述了动态网络嵌入的基本概念,特别是,我们首次提出了一种基于现有动态网络嵌入技术的新分类法,包括基于矩阵分解的方法,基于Skip-Gram的方法,基于自动编码器,基于神经网络和其他嵌入方法。此外,我们仔细总结了常用的数据集以及动态网络嵌入可以带来的各种后续任务。之后,我们提出了现有算法面临的几个挑战,并概述了促进未来研究的可能方向,例如动态嵌入模型,大规模动态网络,异构动态网络,动态属性网络,面向任务的动态网络嵌入和更多的嵌入空间。

成为VIP会员查看完整内容
0
43

【导读】近年来,随着网络数据量的不断增加,挖掘图形数据已成为计算机科学领域的热门研究课题,在学术界和工业界都得到了广泛的研究。 但是,大量的网络数据为有效分析带来了巨大的挑战。 因此激发了图表示的出现,该图表示将图映射到低维向量空间中,同时保持原始图结构并支持图推理。 图的有效表示的研究具有深远的理论意义和重要的现实意义,本教程将介绍图表示/网络嵌入的一些基本思想以及一些代表性模型。

关于图或网络的文献有两个名称:图表示和网络嵌入。我们注意到图和网络都指的是同一种结构,尽管它们每个都有自己的术语,例如,图和网络的顶点和边。挖掘图/网络的核心依赖于正确表示的图/网络,这使得图/网络上的表示学习成为学术界和工业界的基本研究问题。传统表示法直接基于拓扑图来表示图,通常会导致许多问题,包括稀疏性,高计算复杂性等,从而激发了基于机器学习的方法的出现,这种方法探索了除矢量空间中的拓扑结构外还能够捕获额外信息的潜在表示。因此,对于图来说,“良好”的潜在表示可以更加精确的表示图形。但是,学习网络表示面临以下挑战:高度非线性,结构保持,属性保持,稀疏性。

深度学习在处理非线性方面的成功为我们提供了研究新方向,我们可以利用深度学习来提高图形表示学习的性能,作者在教程中讨论了将深度学习技术与图表示学习相结合的一些最新进展,主要分为两类方法:面向结构的深层方法和面向属性的深层方法。

对于面向结构的方法:

  • 结构性深层网络嵌入(SDNE),专注于保持高阶邻近度。
  • 深度递归网络嵌入(DRNE),其重点是维护全局结构。
  • 深度超网络嵌入(DHNE),其重点是保留超结构。

对于面向属性的方法:

  • 专注于不确定性属性的深度变异网络嵌入(DVNE)。
  • 深度转换的基于高阶Laplacian高斯过程(DepthLGP)的网络嵌入,重点是动态属性。

本教程的第二部分就以上5种方法,通过对各个方法的模型介绍、算法介绍、对比分析等不同方面进行详细介绍。

1、Structural Deep Network Embedding

network embedding,是为网络中的节点学习出一个低维表示的方法。目的在于在低维中保持高度非线性的网络结构特征,但现有方法多采用浅层网络不足以挖掘高度非线性,或同时保留局部和全局结构特征。本文提出一种结构化深度网络嵌入方法,叫SDNE该方法用半监督的深度模型来捕捉高度非线性结构,通过结合一阶相似性(监督)和二阶相似性(非监督)来保留局部和全局特征。

2、 Deep recursive network embedding with regular equivalence

网络嵌入旨在保留嵌入空间中的顶点相似性。现有方法通常通过节点之间的连接或公共邻域来定义相似性,即结构等效性。但是,位于网络不同部分的顶点可能具有相似的角色或位置,即规则的等价关系,在网络嵌入的文献中基本上忽略了这一点。以递归的方式定义规则对等,即两个规则对等的顶点具有也规则对等的网络邻居。因此,文章中提出了一种名为深度递归网络嵌入(DRNE)的新方法来学习具有规则等价关系的网络嵌入。更具体地说,我们提出了一种层归一化LSTM,以递归的方式通过聚合邻居的表示方法来表示每个节点。

3、Structural Deep Embedding for Hyper-Networks

是在hyperedge(超边是不可分解的)的基础上保留object的一阶和二阶相似性,学习异质网络表示。于与HEBE的区别在于,本文考虑了网络high-oeder网络结构和高度稀疏性。 传统的基于clique expansion 和star expansion的方法,显式或者隐式地分解网络。也就说,分解后hyper edge节点地子集,依然可以构成一个新的超边。对于同质网络这个假设是合理地,因为同质网络地超边,大多数情况下都是根据潜在地相似性(共同地标签等)构建的。

4、 Deep variational network embedding in wasserstein space

大多数现有的嵌入方法将节点作为点向量嵌入到低维连续空间中。这样,边缘的形成是确定性的,并且仅由节点的位置确定。但是,现实世界网络的形成和发展充满不确定性,这使得这些方法不是最优的。为了解决该问题,在本文中提出了一种新颖的在Wasserstein空间中嵌入深度变分网络(DVNE)。所提出的方法学习在Wasserstein空间中的高斯分布作为每个节点的潜在表示,它可以同时保留网络结构并为节点的不确定性建模。具体来说,我们使用2-Wasserstein距离作为分布之间的相似性度量,它可以用线性计算成本很好地保留网络中的传递性。此外,我们的方法通过深度变分模型隐含了均值和方差的数学相关性,可以通过均值矢量很好地捕获节点的位置,而由方差可以很好地捕获节点的不确定性。此外,本文方法通过保留网络中的一阶和二阶邻近性来捕获局部和全局网络结构。

5、 Learning embeddings of out-of-sample nodes in dynamic networks

迄今为止的网络嵌入算法主要是为静态网络设计的,在学习之前,所有节点都是已知的。如何为样本外节点(即学习后到达的节点)推断嵌入仍然是一个悬而未决的问题。该问题对现有方法提出了很大的挑战,因为推断的嵌入应保留复杂的网络属性,例如高阶邻近度,与样本内节点嵌入具有相似的特征(即具有同质空间),并且计算成本较低。为了克服这些挑战,本文提出了一种深度转换的高阶拉普​​拉斯高斯过程(DepthLGP)方法来推断样本外节点的嵌入。 DepthLGP结合了非参数概率建模和深度学习的优势。特别是,本文设计了一个高阶Laplacian高斯过程(hLGP)来对网络属性进行编码,从而可以进行快速和可扩展的推理。为了进一步确保同质性,使用深度神经网络来学习从hLGP的潜在状态到节点嵌入的非线性转换。 DepthLGP是通用的,因为它适用于任何网络嵌入算法学习到的嵌入。

成为VIP会员查看完整内容
0
65

题目: A Survey on Network Embedding

摘要: 网络嵌入将网络中的节点分配给低维表示,有效地保持了网络结构。近年来,这一新兴的网络分析范式取得了很大的进展。本文首先对网络嵌入方法进行了分类,然后回顾了网络嵌入方法的发展现状,并指出了其未来的研究方向。我们首先总结了网络嵌入的动机。讨论了经典的图嵌入算法及其与网络嵌入的关系。随后,我们对大量的网络嵌入方法进行了系统的综述,包括结构和属性保持的网络嵌入方法、带边信息的网络嵌入方法和先进的信息保持的网络嵌入方法。此外,还综述了几种网络嵌入的评价方法和一些有用的在线资源,包括网络数据集和软件。最后,我们讨论了利用这些网络嵌入方法构建有效系统的框架,并指出了一些潜在的未来方向。

作者简介: Peng Cui,清华大学计算机科学与技术系媒体与网络实验室副教授。

Jian Pei,现任加拿大大数据科学研究主席(Tier 1)和西蒙弗雷泽大学(Simon Fraser University)计算科学学院教授。他还是统计与精算科学系、科学院和健康科学院的副院士。他是数据科学、大数据、数据挖掘和数据库系统等领域的知名首席研究员。他的专长是为新的数据密集型应用开发高效的数据分析技术。他被公认为计算机械协会(ACM)的研究员,他为数据挖掘的基础、方法和应用做出贡献,并作为电气与电子工程师协会(IEEE)的研究员,为他的数据挖掘和知识发现做出贡献。

成为VIP会员查看完整内容
0
46

题目: Graph Neural Networks:A Review of Methods and Applications

简介: 许多学习任务需要处理图形数据,该图形数据包含元素之间的关系信息。对物理系统进行建模,学习分子指纹,预测蛋白质界面以及对疾病进行分类,都需要从图输入中学习模型。在诸如从文本和图像之类的非结构数据中学习的其他领域中,对提取结构的推理,例如句子的依存关系树和图像的场景图,是一个重要的研究课题,它也需要图推理模型。图神经网络(GNN)是连接器模型,可通过在图的节点之间传递消息来捕获图的依赖性。与标准神经网络不同,图神经网络保留一种状态,该状态可以表示来自其邻域的任意深度的信息。尽管已经发现难以训练原始图神经网络来固定点,但是网络体系结构,优化技术和并行计算的最新进展已使他们能够成功学习。近年来,基于图卷积网络(GCN)和门控图神经网络(GGNN)的系统已经在上述许多任务上展示了突破性的性能。在本综述中,我们对现有的图神经网络模型进行了详细的回顾,对应用程序进行了系统分类,并提出了四个未解决的问题,供以后研究。

作者简介: 周杰,教授,清华大学自动化系党委书记,教授,博士生导师。

成为VIP会员查看完整内容
0
284
小贴士
相关资讯
图神经网络(Graph Neural Networks,GNN)综述
极市平台
43+阅读 · 2019年11月27日
图数据表示学习综述论文
专知
29+阅读 · 2019年6月10日
图嵌入(Graph embedding)综述
人工智能前沿讲习班
315+阅读 · 2019年4月30日
清华大学图神经网络综述:模型与应用
机器之心
43+阅读 · 2018年12月26日
网络表示学习综述:一文理解Network Embedding
PaperWeekly
24+阅读 · 2018年8月14日
相关论文
A Survey on Bayesian Deep Learning
Hao Wang,Dit-Yan Yeung
38+阅读 · 2020年7月2日
Wenwu Zhu,Xin Wang,Peng Cui
18+阅读 · 2020年1月2日
Daokun Zhang,Jie Yin,Xingquan Zhu,Chengqi Zhang
4+阅读 · 2019年1月14日
Learning Graph Embedding with Adversarial Training Methods
Shirui Pan,Ruiqi Hu,Sai-fu Fung,Guodong Long,Jing Jiang,Chengqi Zhang
3+阅读 · 2019年1月4日
Deep Graph Infomax
Petar Veličković,William Fedus,William L. Hamilton,Pietro Liò,Yoshua Bengio,R Devon Hjelm
7+阅读 · 2018年12月21日
Jikai Chen,Hanjiang Lai,Libing Geng,Yan Pan
7+阅读 · 2018年4月17日
Uri Shaham,Kelly Stanton,Henry Li,Boaz Nadler,Ronen Basri,Yuval Kluger
7+阅读 · 2018年1月10日
Wenhan Xiong,Thien Hoang,William Yang Wang
18+阅读 · 2018年1月8日
Srinivas Ravishankar, Chandrahas,Partha Pratim Talukdar
6+阅读 · 2018年1月8日
Top