Martin Grohe是一位计算机科学家,以其在参数化复杂性、数学逻辑、有限模型理论、图形逻辑、数据库理论和描述复杂性理论方面的研究而闻名。他是RWTH Aachen大学的计算机科学教授,在那里他担任离散系统逻辑和理论的主席。1999年,他获得了德国研究基金会颁发的海因茨·梅尔-莱布尼茨奖。他在2017年被选为ACM Fellow,因为他“对计算机科学中的逻辑、数据库理论、算法和计算复杂性的贡献”。

word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data 构建结构数据的向量嵌入理论

图和关系结构的向量表示,无论是手工制作的特征向量还是学习的表示,使我们能够将标准的数据分析和机器学习技术应用到结构中。在机器学习和知识表示文献中,广泛研究了产生这种嵌入的方法。然而,从理论的角度来看,向量嵌入得到的关注相对较少。从对已经在实践中使用的嵌入技术的调研开始,在这次演讲中,我们提出了两种理论方法,我们认为它们是理解向量嵌入基础的中心。我们将各种方法联系起来,并提出未来研究的方向。

典型机器学习算法需要将通常是符号数据表示为数字向量才能在结构化数据上计算。数据的向量表示从手工设计特征到学习表示,或者通过专用的嵌入算法计算,或者通过像图神经网络这样的学习架构隐式计算。机器学习方法的性能关键取决于向量表示的质量。因此,有大量的研究提出了广泛的矢量嵌入方法用于各种应用。这些研究大多是经验性的,通常针对特定的应用领域。考虑到主题的重要性,关于向量嵌入的理论工作少得令人惊讶,特别是当它表示超越度量信息(即图中的距离)的结构信息时。

本文的目的是概述在实践中使用的结构化数据的各种嵌入技术,并介绍可以理解和分析这些嵌入技术的理论思想。矢量嵌入的研究前景是笨拙的,由于不同的应用领域(如社会网络分析、知识图、化学信息学、计算生物学等)的推动,几个社区在很大程度上独立地研究相关问题。因此,我们需要有选择性,关注我们看到的共同想法和联系。

向量嵌入可以在关系数据的“离散”世界和机器学习的“可微分”世界之间架起一座桥梁,因此在数据库研究方面具有巨大的潜力。然而,除了知识图谱的二元关系之外,对关系数据的嵌入所做的工作相对较少。在整个论文中,我将试图指出关于向量嵌入的数据库相关研究问题的潜在方向。

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

相关内容

http://www.math.arizona.edu/∼hzhang/math574.html

随着信息技术的飞速发展,在各个领域产生了大量的科学和商业数据。例如,人类基因组数据库项目已经收集了千兆字节的人类遗传密码数据。万维网提供了另一个例子,它拥有由数百万人使用的文本和多媒体信息组成的数十亿Web页面。

本课程涵盖了现代数据科学技术,包括基本的统计学习理论及其应用。将介绍各种数据挖掘方法、算法和软件工具,重点在概念和计算方面。将涵盖生物信息学、基因组学、文本挖掘、社交网络等方面的应用。

本课程着重于现代机器学习的统计分析、方法论和理论。它是为学生谁想要实践先进的机器学习工具和算法,也了解理论原理和统计性质的算法。主题包括回归、分类、聚类、降维和高维分析。

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

图神经网络在图表示学习领域取得了显著的成功。图卷积执行邻域聚合,并表示最重要的图运算之一。然而,这些邻域聚合方法的一层只考虑近邻,当进一步启用更大的接受域时,性能会下降。最近的一些研究将这种性能下降归因于过度平滑问题,即重复传播使得不同类的节点表示无法区分。在这项工作中,我们系统地研究这一观察结果,并对更深的图神经网络发展新的见解。本文首先对这一问题进行了系统的分析,认为当前图卷积运算中表示变换与传播的纠缠是影响算法性能的关键因素。将这两种操作解耦后,更深层次的图神经网络可用于从更大的接受域学习图节点表示。在建立深度模型时,我们进一步对上述观察结果进行了理论分析,这可以作为过度平滑问题的严格而温和的描述。在理论和实证分析的基础上,我们提出了深度自适应图神经网络(DAGNN),以自适应地吸收来自大接受域的信息。一组关于引文、合著和共购数据集的实验证实了我们的分析和见解,并展示了我们提出的方法的优越性。

https://arxiv.org/abs/2007.09296

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

最近,人们对在非欧几里得空间中表示数据的方法(例如双曲或球面)越来越感兴趣,这些方法提供了对某些真实世界数据属性(例如无尺度、分层或循环)有用的特定归纳偏差。然而,流行的图神经网络目前仅限于通过欧几里得几何和相关的向量空间操作来建模数据。在这里,我们通过提出将图卷积网络(GCN)在数学基础上推广为常曲率空间的(乘积)来弥补这一差距。我们通过i)引入一种统一的形式,可以在所有常曲率几何之间平滑地插入,ii)利用陀螺质心坐标,推广了经典的欧几里德质心概念。当曲率从任何一边变为零时,我们这类模型平滑地恢复它们的欧几里得对应模型。根据其离散曲率,我们在非欧几里得行为的符号数据上的节点分类和失真最小化的任务表现优于欧几里得GCNs。

https://arxiv.org/abs/1911.05076

概述

图卷积网络 针对图像数据的卷积网络和深度学习的成功启发了对于共享参数与图形几何形状一致的图推广。Bruna等人(2014);Henaff等人(2015)是利用图上的局部谱滤波器在图傅里叶空间中开发频谱图卷积神经网络的先驱。然而,为了减少对拉普拉斯特征模式的图依赖,Defferrard等人(2016)利用Hammond等人(2011)的结果使用Chebyshev多项式近似卷积滤波器。所得到的方法(在附录A中讨论)在计算效率和精度和复杂性方面是优越的。此外,Kipf和Welling(2017)通过考虑一阶近似来简化这种方法,从而获得高可伸缩性。提出的图卷积网络(GCN)是通过对称归一化邻接矩阵来插值节点嵌入,而这种权值共享可以理解为一种有效的扩散式正则化器。最近的工作扩展了GCNs,实现了链接预测(Zhang & Chen, 2018)、图分类(Hamilton等,2017;和节点分类(Klicpera et al., 2019;Velickoviˇc et al .´, 2018)。

ML中的欧几里得几何。在机器学习(ML)中,由于各种原因,数据通常在欧几里得空间中表示。首先,有些数据本质上是欧几里得的,比如经典力学中三维空间中的位置。其次,直觉在这样的空间中更容易,因为它们拥有一个吸引人的矢量结构,允许基本的算术和丰富的线性代数理论。最后,许多感兴趣的量,如距离和内积在封闭公式中是已知的,可以在现有的硬件上非常有效地计算。这些操作是当今大多数流行的机器学习模型的基本构建模块。因此,欧几里得几何强大的简单性和效率已经导致许多方法实现了最先进的任务,如机器翻译(Bahdanau等,2015;wani et al., 2017),语音识别(Graves et al., 2013),图像分类(He et al., 2016)或推荐系统(He et al., 2017)。

黎曼ML 尽管取得了成功,但某些类型的数据(例如分层数据、无标度数据或球形数据)被证明可以更好地用非欧几里德几何表示(Defferrard et al., 2019;Bronstein等,2017;Nickel & Kiela, 2017;Gu et al., 2019),尤其带来了丰富的流形学习理论(Roweis & Saul, 2000;和信息几何(Amari & Nagaoka, 2007)。在活力操纵非欧几里得几何的数学框架被称为黎曼几何(Spivak, 1979)。虽然它的理论导致了许多强而优雅的结果,但它的一些基本量,如距离函数d(·,·),通常不能以封闭的形式提供,这对许多计算方法都是禁止的。

常曲率几何的代表性优势。在一般黎曼流形和欧几里得空间之间的一个有趣的权衡是由常截面曲率流形给出的。他们一起定义了所谓的双曲(负曲率),椭圆(正曲率)和欧几里得(零曲率)几何。正如下面和附录B中所讨论的,欧几里得空间在嵌入某些类型的数据(如树)时具有局限性,并且会产生很大的失真。在这些情况下,双曲空间和球面空间具有代表性的优势,为各自的数据提供了更好的归纳偏差。

双曲空间可以直观地理解为一棵连续树:球的体积随半径呈指数增长,类似于二叉树的节点数随深度呈指数增长(图1)。它的树状性质已经被数学研究了很长时间(Gromov, 1987;哈曼,2017;与欧几里得几何结构相比,它被证明能够更好地嵌入复杂网络(Krioukov et al., 2010)、无标度图和分层数据(Cho et al., 2019; Sala et al., 2018; Ganea et al., 2018b; Gu et al., 2019; Nickel & Kiela, 2018; 2017; Tifrea et al., 2019)。一些重要的工具或方法找到了它们的双曲线对应物,例如变分自编码器(Mathieu et al., 2019;、注意力机制(Gulcehre等,2018)、矩阵乘法、递归单位和多项logistic回归(Ganea等,2018)。

常曲率空间中的GCNs。在这项工作中,我们引入了一个扩展的图形卷积网络,它允许学习存在于具有任何曲率符号的常曲率空间(乘积)中的表示。我们通过将导出的统一陀螺框架与GCNs的有效性相结合来实现这一点(Kipf & Welling, 2017)。与我们的工作同时,Chami等人(2019年);Liu等人(2019)考虑了通过切线空间聚合在双曲空间中学习嵌入的图神经网络。他们的方法将在第3.4节中作更详细的分析。我们的模型更一般化,因为它在一个包含双曲空间的严格超集中产生表示。

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

随着开放科学和开放资源的双重运动将越来越多的科学过程带入数字领域,科学本身的元科学研究(包括数据科学和统计)出现了新的机会。未来的科学很可能看到机器在处理、组织甚至创造科学知识方面发挥积极作用。为了使这成为可能,必须进行大量的工程努力来将科学工件转化为有用的计算资源,并且必须在科学理论、模型、实验和数据的组织方面取得概念上的进展。本论文的目标是将数据科学的两大主要产物——统计模型和数据分析——数字化和系统化。使用来自代数的工具,特别是分类逻辑,在统计和逻辑的模型之间进行了精确的类比,使统计模型在逻辑意义上被视为理论的模型。统计理论,作为代数结构,服从机器表示,并配备了形式化不同统计方法之间的关系的形态。从数学转向工程,设计和实现了一个软件系统,用于以Python或R程序的形式创建数据分析的机器表示。表示的目的是捕获数据分析的语义,独立于实现它们的编程语言和库。

https://arxiv.org/abs/2006.08945

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

人类的视觉系统证明,用极少的样本就可以学习新的类别;人类不需要一百万个样本就能学会区分野外的有毒蘑菇和可食用蘑菇。可以说,这种能力来自于看到了数百万个其他类别,并将学习到的表现形式转化为新的类别。本报告将正式介绍机器学习与热力学之间的联系,以描述迁移学习中学习表征的质量。我们将讨论诸如速率、畸变和分类损失等信息理论泛函如何位于一个凸的,所谓的平衡曲面上。我们规定了在约束条件下穿越该表面的动态过程,例如,一个调制速率和失真以保持分类损失不变的等分类过程。我们将演示这些过程如何完全控制从源数据集到目标数据集的传输,并保证最终模型的性能。

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

题目: word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data

摘要:

图形和关系结构的向量表示,无论是手工制作的特征向量还是学习表示,都使我们能够将标准的数据分析和机器学习技术应用于这些结构。在机器学习和知识表示的文献中,对生成这种嵌入的方法进行了广泛的研究。然而,从理论的角度来看,向量嵌入的研究相对较少。在这篇论文中,我们从一个已经在实践中使用的嵌入技术的调查开始,提出了两个我们认为是理解向量嵌入基础的中心的理论方法。我们总结了各种方法之间的联系,并为未来的研究提出了方向。

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

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

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

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

对于面向结构的方法:

  • 结构性深层网络嵌入(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
205
小贴士
相关资讯
知识图谱嵌入(KGE):方法和应用的综述
专知
42+阅读 · 2019年8月25日
图嵌入(Graph embedding)综述
人工智能前沿讲习班
355+阅读 · 2019年4月30日
图卷积网络介绍及进展【附PPT与视频资料】
人工智能前沿讲习班
20+阅读 · 2019年1月3日
网络表示学习介绍
人工智能前沿讲习班
15+阅读 · 2018年11月26日
干货|基于图卷积网络的图深度学习
DataCanvas大数据云平台
7+阅读 · 2017年6月8日
相关论文
Ioannis Z. Emiris,Ioannis Psarros
3+阅读 · 2020年4月13日
Heterogeneous Graph Transformer
Ziniu Hu,Yuxiao Dong,Kuansan Wang,Yizhou Sun
18+阅读 · 2020年3月3日
Conceptualize and Infer User Needs in E-commerce
Xusheng Luo,Yonghua Yang,Kenny Q. Zhu,Yu Gong,Keping Yang
3+阅读 · 2019年10月8日
Daokun Zhang,Jie Yin,Xingquan Zhu,Chengqi Zhang
4+阅读 · 2019年1月14日
Graph Neural Networks: A Review of Methods and Applications
Jie Zhou,Ganqu Cui,Zhengyan Zhang,Cheng Yang,Zhiyuan Liu,Maosong Sun
66+阅读 · 2018年12月20日
dynnode2vec: Scalable Dynamic Network Embedding
Sedigheh Mahdavi,Shima Khoshraftar,Aijun An
9+阅读 · 2018年12月6日
Attributed Network Embedding for Incomplete Structure Information
Chengbin Hou,Shan He,Ke Tang
3+阅读 · 2018年11月28日
Towards Scalable Spectral Clustering via Spectrum-Preserving Sparsification
Yongyu Wang,Zhuo Feng
4+阅读 · 2018年10月11日
Mohammad Raihanul Islam,B. Aditya Prakash,Naren Ramakrishnan
4+阅读 · 2018年3月22日
Lizi Liao,Xiangnan He,Hanwang Zhang,Tat-Seng Chua
3+阅读 · 2017年5月14日
Top