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

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

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

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

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

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

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

相关内容

回答大规模知识图谱上的复杂逻辑查询是一项基本而又具有挑战性的任务。在本文中,我将概述如何使用向量空间嵌入在知识图谱中执行逻辑推理。首先,我将讨论预测一对实体之间关系的知识图谱补全方法:通过捕获与实体相邻的关系类型来考虑每个实体的关系上下文,并通过一种新的基于边的消息传递方案进行建模;考虑关系路径捕获两个实体之间的所有路径;通过一种可学习的注意力机制,自适应地整合关系上下文和关系路径。其次,我们还将讨论QUERY2BOX,这是一个基于嵌入的框架,用于推理使用and、or和存在操作符进行的大量且不完整的KGs中的任意查询。

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

实体交互预测在许多重要的应用如化学、生物、材料科学和医学中是必不可少的。当每个实体由一个复杂的结构(即结构化实体)表示时,这个问题就变得非常具有挑战性,因为涉及到两种类型的图:用于结构化实体的局部图和用于捕获结构化实体之间交互的全局图。我们注意到,现有的结构化实体交互预测工作不能很好地利用图的唯一图模型。在本文中,我们提出了一个图的神经网络图,即GoGNN,它以分层的方式提取了结构化实体图和实体交互图中的特征。我们还提出了双重注意力机制,使模型在图的两个层次上都能保持相邻的重要性。在真实数据集上的大量实验表明,GoGNN在两个有代表性的结构化实体交互作用预测任务上的表现优于最先进的方法:化学-化学交互作用预测和药物-药物交互作用预测。我们的代码可以在Github上找到。

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

题目: Beyond Triplets: Hyper-Relational Knowledge Graph Embedding for Link Prediction

摘要: 知识图谱(KGs)嵌入的是一个强大的工具,能够预测KGs缺失的链接。现有的技术通常将KG表示一个三元组集合,每个三元组(h, r, t)通过关系r将两个实体h和t联系起来,并从这样的三元组中学习实体/关系嵌入,同时保留这样的结构。然而,这种三元组的表示过分简化了存储在KG中的数据的复杂性,尤其是超关系的事实,其中每个事实不仅包含基本三元组(h r t),还有相关的键-值对(k、v)。尽管最近有一些技术试图通过将超关系事实转换为n元表示来学习这些数据(即一组没有三元组组的键值对)。由于它们不知道三元组结构,导致了次优模型,三元组结构是现代KGs的基本数据结构,保留了链接预测的基本信息。为了解决这个问题,我们提出了HINGE,一个超相关KG嵌入模型,它直接从KG学习超相关事实。HINGE不仅捕获了在三元组中编码的KG的主要结构信息,而且还捕获了每个三元组及其相关键-值对之间的相关性。我们在KG预测任务大量的实验显示了优越性。特别是,HINGE不仅始终优于仅从三元组学习的KG嵌入方法,而且始终优于使用n元表示从超关系事实学习的方法。

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

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

摘要:

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

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

摘要 近年来,使用结构化数据建模的图神经网络(GNNs)取得了巨大的成功。然而,大多数的GNN都是针对同构图设计的,在同构图中,所有的节点和边都属于同一种类型,使得它们无法表示异构结构。在这篇论文中,我们提出了一种异构图 Transformer(HGT)结构来对web级的异构图进行建模。为了对异构性进行建模,我们设计了节点类型和边类型的相关参数来描述每个边上的异构注意力程度,从而使HGT能够维护不同类型节点和边的特定表示。为了处理动态异构图,我们在HGT中引入了相对时间编码技术,该技术能够捕获具有任意持续时间的动态结构依赖关系。针对网络规模图数据的处理问题,设计了高效、可扩展的小批量图数据采样算法HGSampling。在拥有1.79亿个节点和20亿个边的开放学术图上进行的大量实验表明,所提出的HGT模型在各种下游任务上的性能始终比所有最先进的GNN基线高9-21%。

关键词:图神经网络;异构信息网络;表示学习;图嵌入;图注意力

介绍

异构图通常对复杂的系统进行抽象和建模,其中不同类型的对象以各种方式相互交互。此类系统的一些常见实例包括学术图、Facebook实体图、LinkedIn经济图,以及广泛的物联网网络。例如,图1中的开放学术图(OAG)[28]包含五种类型的节点:论文、作者、机构、场所(期刊、会议或预印本)和字段,以及它们之间不同类型的关系。

在过去的十年中,人们对异构图[17]的挖掘进行了大量的研究。其中一个经典的范例就是定义和使用元路径来对异类结构进行建模,例如PathSim[18]和变元ath2vec[3]。最近,鉴于图神经网络(GNNs)的成功[7,9,22],[14,23,26,27]尝试采用GNNs来学习异构网络。然而,这些工作面临着几个问题:首先,它们大多涉及到为每种类型的异构图设计元路径,这需要特定的领域知识;其次,它们要么简单地假设不同类型的节点/边共享相同的特征和表示空间,要么为节点类型或单独的边类型保留不同的非共享权值,使它们不足以捕获异类图的属性;三是大多忽略了每一个(异构)图的动态性;最后,它们固有的设计和实现使得它们无法对web规模的异构图进行建模。

以OAG为例:首先,OAG中的节点和边可能具有不同的特征分布,如论文具有文本特征,而机构可能具有来自附属学者的特征,共同作者明显不同于引文链接;OAG一直在不断发展,例如:1)出版物的数量每12年翻一倍[4];2)KDD会议在1990年代更多地与数据库相关,而近年来更多地与机器学习相关;最后,OAG包含数亿个节点和数十亿个关系,使得现有的异构GNN无法扩展来处理它。

针对这些限制和挑战,我们建议研究异构图神经网络,其目标是维护节点和边类型依赖表示、捕获网络动态、避免自定义元路径和可扩展到web级图。在这项工作中,我们提出了异构图 Transformer(HGT)架构来处理所有这些问题。

为了处理图的异构性,我们引入了节点类型和边类型依赖注意力机制。HGT中的相互注意不是对每一个类型边参数化,而是根据其元关系三元组e=(s,t),即 s为节点类型,s与t之间的e的边类型,t的节点类型。图1展示了异构学术图的元关系。具体来说,我们使用这些元关系来对权重矩阵参数化,以计算每条边上的注意力。因此,允许不同类型的节点和边维护其特定的表示空间。同时,不同类型的连接节点仍然可以交互、传递和聚合消息,而不受其分布差异的限制。由于其架构的性质,HGT可以通过跨层传递消息来整合来自不同类型的高阶邻居的信息,这可以看作是软元路径。也就是说,即使HGT只将其单跳边作为输入,而不需要手动设计元路径,所提出的注意力机制也可以自动、隐式地学习和提取对不同下游任务重要的元路径。

为了处理图数据的动态特性,我们提出了相对时间编码(RTE)策略来增强HGT。我们不打算将输入图分割成不同的时间戳,而是建议将发生在不同时间的所有边作为一个整体进行维护,并设计RTE策略来对任何持续时间长度的结构性时间依赖关系进行建模,甚至包括不可见的和未来的时间戳。通过端到端训练,RTE使HGT能够自动学习异构图的时间依赖性和演化。

为了处理网络规模的图形数据,我们设计了第一个用于小批量GNN训练的异构子图采样算法HGSampling。它的主要思想是样本异构子图中不同类型的节点与类似的比例,由于直接使用现有的(均匀)GNN抽样方法,如GraphSage [7], FastGCN[1],和LADIES[29],结果在高度不平衡的关于节点和边缘的类型。此外,它还被设计成保持采样子图的密度以最小化信息的丢失。通过HGSampling,所有的GNN模型,包括我们提出的HGT,都可以在任意大小的异构图上进行训练和推断。

我们证明了所提出的异构图Transformer在网络规模开放学术图上的有效性和效率,该开放学术图由1.79亿个节点和20亿个边组成,时间跨度从1900年到2019年,这是迄今为止在异构图上进行的规模最大、跨度最长的表示学习。此外,我们还检查领域特定的图表:计算机科学和医学学术图表。实验结果表明,与最先进的GNNs和专用的异构模型相比,在下游任务中HGT可以显著提高9-21%。我们进一步进行了案例研究,表明了所提出的方法确实能够自动捕获不同任务的隐式元路径的重要性。

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

题目: Group Representation Theory for Knowledge Graph Embedding

摘要: 最近,知识图谱嵌入已经成为一种流行的建模和推断缺失链接的方法。本文提出了一种知识图谱嵌入的群论观点,将以往的方法与不同的群作用联系起来。此外,利用群表示理论中的Schur引理,我们证明了最新的嵌入方法RotatE具有从任意有限阿贝尔群建立关系的能力

作者简介: Chen Cai,俄亥俄州立大学计算机科学与工程系博士。他的研究兴趣在于图表示学习和拓扑数据分析。

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

课程介绍: 最近,图神经网络 (GNN) 在各个领域越来越受到欢迎,包括社交网络、知识图谱、推荐系统,甚至生命科学。GNN 在对图形中节点间的依赖关系进行建模方面能力强大,使得图分析相关的研究领域取得了突破性进展。本次课程对比传统的卷积神经网络以及图谱图卷积与空间图卷积,从理论知识入手,并结合相关论文进行详细讲解。

主讲人: Xavier Bresson,人工智能/深度学习方面的顶级研究员,培训师和顾问。在“图深度学习”上的NeurIPS'17和CVPR'17(2019年顶级人工智能会议排名)上的演讲者,在剑桥,加州大学洛杉矶分校,布朗,清华,庞加莱,海德堡等地进行了30多次国际演讲。

课程大纲:

  • 传统卷积神经网络
  • 谱图图卷积
  • 空间图卷积
  • 总结
成为VIP会员查看完整内容
0
163
小贴士
相关论文
Heterogeneous Graph Transformer
Ziniu Hu,Yuxiao Dong,Kuansan Wang,Yizhou Sun
9+阅读 · 3月3日
Efficiently Embedding Dynamic Knowledge Graphs
Tianxing Wu,Arijit Khan,Huan Gao,Cheng Li
4+阅读 · 2019年10月15日
Domain Representation for Knowledge Graph Embedding
Cunxiang Wang,Feiliang Ren,Zhichao Lin,Chenxv Zhao,Tian Xie,Yue Zhang
5+阅读 · 2019年9月11日
Liang Yao,Chengsheng Mao,Yuan Luo
3+阅读 · 2019年9月7日
dynnode2vec: Scalable Dynamic Network Embedding
Sedigheh Mahdavi,Shima Khoshraftar,Aijun An
5+阅读 · 2018年12月6日
Sambaran Bandyopadhyay,Lokesh N,M. N. Murty
3+阅读 · 2018年11月19日
Joint Embedding of Meta-Path and Meta-Graph for Heterogeneous Information Networks
Lichao Sun,Lifang He,Zhipeng Huang,Bokai Cao,Congying Xia,Xiaokai Wei,Philip S. Yu
3+阅读 · 2018年9月11日
Mohammad Raihanul Islam,B. Aditya Prakash,Naren Ramakrishnan
4+阅读 · 2018年3月22日
Mohammad Mehdi Keikha,Maseud Rahgozar,Masoud Asadpour
3+阅读 · 2018年2月19日
Jiezhong Qiu,Yuxiao Dong,Hao Ma,Jian Li,Kuansan Wang,Jie Tang
15+阅读 · 2017年12月12日
Top