图机器学习讲述关于《图神经网络理论》最新课程。

图网络(GNNs)的新变体层出不穷,但是却鲜有对图网络框架的理论分析。Kipf在2017年提出的GCN中,曾从图上的谱分析的角度给出了GCN的理论基础;近期也有日本研究者从图信号处理的角度,表明GNNs只是一个低频滤波器(arxiv.org/abs/1905.09550)。而本文尝试从图同构的角度出发,以Weisfeiler-Lehman Isomorphism Test (WL test)为基础,给出了GNNs表征能力的精彩理论分析,具体的贡献总结如下:

作者表明,在区别不同图结构时,GNNs最多只能取得和 WL test 一样效果,即,GNNs表征能力的上限是WL test;

作者也给出了构建GNNs的条件,满足这些条件后,GNNs的表征能力和 WL test一样强;

给出了GCN和GraphSAGE等传统图网络框架不能区分的网络结构;

建立了一个简单的框架GIN,并在理论上证明了其表征能力和 WL test一样强。

总结起来,全文需要回答两个关键性的问题:

  • GNNs表征能力的上限是什么?
  • 怎样的GNNs 框架设计才能达到最好的表征能力?
成为VIP会员查看完整内容
0
32

相关内容

图神经网络 (GNN) 是一种连接模型,它通过图的节点之间的消息传递来捕捉图的依赖关系。与标准神经网络不同的是,图神经网络保留了一种状态,可以表示来自其邻域的具有任意深度的信息。近年来,图神经网络(GNN)在社交网络、知识图、推荐系统、问答系统甚至生命科学等各个领域得到了越来越广泛的应用。

知识荟萃

精品入门和进阶教程、论文和代码整理等

更多

查看相关VIP内容、论文、资讯等

近年来,对图表示学习的研究激增,包括深度图嵌入技术、将CNNs泛化为为图结构数据和神经消息传递方法。图形神经网络(GNNs)和相关技术的发展已经在许多领域带来了最新的研究成果:化学合成、车辆路由、3d视觉、推荐系统、问答、连续控制、自动驾驶和社交网络分析。因此,在几乎所有顶级机器学习会议上,GNNs经常在增长最快的趋势和研讨会上名列前茅。

但是,什么是GNN呢? 快速在线搜索可以发现许多不同的定义。根据作者所假设的背景,这些定义可能大相径庭(甚至使用完全不同的术语)。这并非巧合:我们现在所认为的图神经网络的概念,都是在过去十年里从各种机器学习方向独立出现的。

在这次演讲中,我将尝试对GNNs提供一个“鸟瞰”的视角。在快速学习使用图表示学习的动机之后,我将从排列不变性和等变性的第一原则推导出GNN。通过这一视角,我将描述来自不同领域 (图嵌入、图信号处理、概率图模型和图同构测试)的研究人员是如何独立地得出本质上相同的GNN概念的。

这次演讲的目标听众是一般的计算机科学听众,不过一些关于机器学习的神经网络的基本知识也会很有用。我也希望经验丰富的GNN从业人员可以从我将呈现的分类中受益。

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

业界和学界对知识图谱的关注主要集中于两大领域,分别是知识图谱的构建和知识图谱的应用。前者聚焦于通过对结构化、非结构化数据的整合,实现统一形式的数据存储;后者则着眼于通过算法对海量知识图谱数据进行学习与挖掘,从而推理出新的知识,服务于具体行业应用。知识图谱推理在其中发挥了重要作用,被誉为知识图谱领域的皇冠。

CS224W图机器学习课程讲述了《知识图谱推理》最新进展PPT。

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

近年来,知识图谱(KG)的构建和应用得到了快速的发展。大量的KGs,如Freebase、DBpedia、YAGO和NELL,已经被创建并成功地应用于许多实际应用中,从语义解析和命名实体消歧到信息提取和问答。KG是由实体(节点)和关系(不同类型的边)组成的多关系图。每条边都表示为形式(头实体、关系、尾实体)的三个部分,也称为事实,表示两个实体通过特定的关系连接在一起,例如(AlfredHitchcock, DirectorOf, Psycho)。虽然在表示结构化数据方面很有效,但是这类三元组的底层符号特性通常使KGs很难操作。

为了解决这个问题,提出了一种新的研究方向——知识图谱嵌入。关键思想是嵌入KG的组件,包括将实体和关系转化为连续的向量空间,从而简化操作,同时保留KG的原有的结构。那些实体和关系嵌入能进一步应用于各种任务中,如KG补全、关系提取、实体分类和实体解析。

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

斯坦福大学的最新课程CS224W——图机器学习,主讲人是斯坦福大牛Jure Leskovec,他是斯坦福大学计算机学院的副教授,也是图表示学习方法 node2vec 和 GraphSAGE 作者之一。最新讲述了关于图神经网络模型总结,内容包括:

  • 深度学习基础 Basics of deep learning
  • 图深度学习 Deep learning for graphs
  • 图卷积网络 Graph Convolutional Networks and GraphSAGE

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

本文首先给出了一种学习节点信息卷积隐含层的图网学习算法。根据标签是附着在节点上还是附着在图上,研究了两种类型的GNN。在此基础上,提出了一个完整的GNN训练算法收敛性设计和分析框架。该算法适用于广泛的激活函数,包括ReLU、Leaky ReLU、Sigmod、Softplus和Swish。实验表明,该算法保证了对基本真实参数的线性收敛速度。对于这两种类型的GNN,都用节点数或图数来表征样本复杂度。从理论上分析了特征维数和GNN结构对收敛率的影响。数值实验进一步验证了理论分析的正确性。

https://arxiv.org/pdf/2012.03429.pdf

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

图神经网络(GNNs)是针对图信号的信息处理体系结构。它们已经被开发出来,并在本课程中作为卷积神经网络(CNNs)的推广来介绍,它被用来在时间和空间上处理信号。这句话听起来可能有些奇怪,这取决于你对神经网络(NNs)和深度学习的了解程度。CNN不就是NN的特例吗?GNN不也是这样吗?从严格意义上说,它们是存在的,但我们这门课的重点是涉及高维信号的大规模问题。在这些设置中,神经网络无法伸缩。CNN为信号在时间和空间上提供可扩展的学习。GNNS支持图信号的可扩展学习。

在本课程中,我们将在学习单特征和多特征GNN之前,介绍图卷积滤波器和图滤波器组。我们还将介绍相关的架构,如经常性的GNN。特别的重点将放在研究GNN的排列的等方差和图变形的稳定性。这些特性提供了一个解释的措施,可以观察到的良好性能的GNNs经验。我们还将在大量节点的极限范围内研究GNN,以解释不同节点数量的网络间GNN的可迁移性。

https://gnn.seas.upenn.edu/

Lecture 1: Machine Learning on Graphs 图机器学习

图神经网络(GNNs)是一种具有广泛适用性和非常有趣的特性的工具。可以用它们做很多事情,也有很多东西需要学习。在第一节课中,我们将回顾本课程的目标并解释为什么我们应该关注GNN。我们还提供了未来的预览。我们讨论了在可扩展学习中利用结构的重要性,以及卷积是如何在欧几里得空间中实现这一点的。我们进一步解释如何将卷积推广到图,以及随后将卷积神经网络推广到图(卷积)神经网络。

1.1 – Graph Neural Networks 图神经网络

在这门课程中,我希望我们能够共同完成两个目标。您将学习如何在实际应用程序中使用GNNs。也就是说,您将开发使用图神经网络在图上表述机器学习问题的能力。你将学会训练他们。你将学会评估它们。但你也会学到,你不能盲目地使用它们。你将学习到解释他们良好的实证表现的基本原理。这些知识将允许您确定GNN适用或不适用的情况。

1.2 Machine Learning on Graphs: The Why 图机器学习

我们关心GNN是因为它们使机器能够在图上学习。但我们为什么要关注图机器学习呢?我们在这里详述图机器学习的原因。它为什么有趣?我们为什么要关心这个?我们关心的原因很简单:因为图表在信息处理中无处不在。

1.3 – Machine Learning on Graphs: The How

在讨论了原因之后,我们来处理如何做。我们如何在图上进行机器学习?这个问题的答案很简单:我们应该使用神经网络。我们应该这样做,因为我们有丰富的经验和理论证据证明神经网络的价值。理解这些证据是本课程的目标之一。但在我们准备这么做之前,有一个潜在的阻碍因素:神经网络必须利用结构来实现可扩展。

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

近年来,人们对学习图结构数据表示的兴趣大增。基于标记数据的可用性,图表示学习方法一般分为三大类。第一种是网络嵌入(如浅层图嵌入或图自动编码器),它侧重于学习关系结构的无监督表示。第二种是图正则化神经网络,它利用图来增加半监督学习的正则化目标的神经网络损失。第三种是图神经网络,目的是学习具有任意结构的离散拓扑上的可微函数。然而,尽管这些领域很受欢迎,但在统一这三种范式方面的工作却少得惊人。在这里,我们的目标是弥合图神经网络、网络嵌入和图正则化模型之间的差距。我们提出了图结构数据表示学习方法的一个综合分类,旨在统一几个不同的工作主体。具体来说,我们提出了一个图编码解码器模型(GRAPHEDM),它将目前流行的图半监督学习算法(如GraphSage、Graph Convolutional Networks、Graph Attention Networks)和图表示的非监督学习(如DeepWalk、node2vec等)归纳为一个统一的方法。为了说明这种方法的一般性,我们将30多个现有方法放入这个框架中。我们相信,这种统一的观点既为理解这些方法背后的直觉提供了坚实的基础,也使该领域的未来研究成为可能。

概述

学习复杂结构化数据的表示是一项具有挑战性的任务。在过去的十年中,针对特定类型的结构化数据开发了许多成功的模型,包括定义在离散欧几里德域上的数据。例如,序列数据,如文本或视频,可以通过递归神经网络建模,它可以捕捉序列信息,产生高效的表示,如机器翻译和语音识别任务。还有卷积神经网络(convolutional neural networks, CNNs),它根据移位不变性等结构先验参数化神经网络,在图像分类或语音识别等模式识别任务中取得了前所未有的表现。这些主要的成功仅限于具有简单关系结构的特定类型的数据(例如,顺序数据或遵循规则模式的数据)。

在许多设置中,数据几乎不是规则的: 通常会出现复杂的关系结构,从该结构中提取信息是理解对象之间如何交互的关键。图是一种通用的数据结构,它可以表示复杂的关系数据(由节点和边组成),并出现在多个领域,如社交网络、计算化学[41]、生物学[105]、推荐系统[64]、半监督学习[39]等。对于图结构的数据来说,将CNNs泛化为图并非易事,定义具有强结构先验的网络是一项挑战,因为结构可以是任意的,并且可以在不同的图甚至同一图中的不同节点之间发生显著变化。特别是,像卷积这样的操作不能直接应用于不规则的图域。例如,在图像中,每个像素具有相同的邻域结构,允许在图像中的多个位置应用相同的过滤器权重。然而,在图中,我们不能定义节点的顺序,因为每个节点可能具有不同的邻域结构(图1)。此外,欧几里德卷积强烈依赖于几何先验(如移位不变性),这些先验不能推广到非欧几里德域(如平移可能甚至不能在非欧几里德域上定义)。

这些挑战导致了几何深度学习(GDL)研究的发展,旨在将深度学习技术应用于非欧几里德数据。特别是,考虑到图在现实世界应用中的广泛流行,人们对将机器学习方法应用于图结构数据的兴趣激增。其中,图表示学习(GRL)方法旨在学习图结构数据的低维连续向量表示,也称为嵌入。

广义上讲,GRL可以分为两类学习问题,非监督GRL和监督(或半监督)GRL。第一个系列的目标是学习保持输入图结构的低维欧几里德表示。第二系列也学习低维欧几里德表示,但为一个特定的下游预测任务,如节点或图分类。与非监督设置不同,在非监督设置中输入通常是图结构,监督设置中的输入通常由图上定义的不同信号组成,通常称为节点特征。此外,底层的离散图域可以是固定的,这是直推学习设置(例如,预测一个大型社交网络中的用户属性),但也可以在归纳性学习设置中发生变化(例如,预测分子属性,其中每个分子都是一个图)。最后,请注意,虽然大多数有监督和无监督的方法学习欧几里德向量空间中的表示,最近有兴趣的非欧几里德表示学习,其目的是学习非欧几里德嵌入空间,如双曲空间或球面空间。这项工作的主要动机是使用一个连续的嵌入空间,它类似于它试图嵌入的输入数据的底层离散结构(例如,双曲空间是树的连续版本[99])。

鉴于图表示学习领域的发展速度令人印象深刻,我们认为在一个统一的、可理解的框架中总结和描述所有方法是很重要的。本次综述的目的是为图结构数据的表示学习方法提供一个统一的视图,以便更好地理解在深度学习模型中利用图结构的不同方法。

目前已有大量的图表示学习综述。首先,有一些研究覆盖了浅层网络嵌入和自动编码技术,我们参考[18,24,46,51,122]这些方法的详细概述。其次,Bronstein等人的[15]也给出了非欧几里德数据(如图或流形)的深度学习模型的广泛概述。第三,最近的一些研究[8,116,124,126]涵盖了将深度学习应用到图数据的方法,包括图数据神经网络。这些调查大多集中在图形表示学习的一个特定子领域,而没有在每个子领域之间建立联系。

在这项工作中,我们扩展了Hamilton等人提出的编码-解码器框架,并介绍了一个通用的框架,图编码解码器模型(GRAPHEDM),它允许我们将现有的工作分为四大类: (i)浅嵌入方法,(ii)自动编码方法,(iii) 图正则化方法,和(iv) 图神经网络(GNNs)。此外,我们还介绍了一个图卷积框架(GCF),专门用于描述基于卷积的GNN,该框架在广泛的应用中实现了最先进的性能。这使我们能够分析和比较各种GNN,从在Graph Fourier域中操作的方法到将self-attention作为邻域聚合函数的方法[111]。我们希望这种近期工作的统一形式将帮助读者深入了解图的各种学习方法,从而推断出相似性、差异性,并指出潜在的扩展和限制。尽管如此,我们对前几次综述的贡献有三个方面

  • 我们介绍了一个通用的框架,即GRAPHEDM,来描述一系列广泛的有监督和无监督的方法,这些方法对图形结构数据进行操作,即浅层嵌入方法、图形正则化方法、图形自动编码方法和图形神经网络。

  • 我们的综述是第一次尝试从同一角度统一和查看这些不同的工作线,我们提供了一个通用分类(图3)来理解这些方法之间的差异和相似之处。特别是,这种分类封装了30多个现有的GRL方法。在一个全面的分类中描述这些方法,可以让我们了解这些方法究竟有何不同。

  • 我们为GRL发布了一个开源库,其中包括最先进的GRL方法和重要的图形应用程序,包括节点分类和链接预测。我们的实现可以在https://github.com/google/gcnn-survey-paper上找到。

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

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

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

课程大纲:

  • 传统卷积神经网络
  • 谱图图卷积
  • 空间图卷积
  • 总结
成为VIP会员查看完整内容
0
189
小贴士
相关论文
Yuwei Cao,Hao Peng,Jia Wu,Yingtong Dou,Jianxin Li,Philip S. Yu
5+阅读 · 1月21日
Huihui Liu,Yiding Yang,Xinchao Wang
11+阅读 · 2020年12月10日
Invariance-Preserving Localized Activation Functions for Graph Neural Networks
Luana Ruiz,Fernando Gama,Antonio G. Marques,Alejandro Ribeiro
4+阅读 · 2019年11月5日
HaarPooling: Graph Pooling with Compressive Haar Basis
Yu Guang Wang,Ming Li,Zheng Ma,Guido Montufar,Xiaosheng Zhuang,Yanan Fan
3+阅读 · 2019年9月25日
Wei-Lin Chiang,Xuanqing Liu,Si Si,Yang Li,Samy Bengio,Cho-Jui Hsieh
9+阅读 · 2019年8月8日
Jindou Wu,Yunlun Yang,Chao Deng,Hongyi Tang,Bingning Wang,Haoze Sun,Ting Yao,Qi Zhang
6+阅读 · 2019年3月28日
Towards Scalable Spectral Clustering via Spectrum-Preserving Sparsification
Yongyu Wang,Zhuo Feng
4+阅读 · 2018年10月11日
Keyulu Xu,Weihua Hu,Jure Leskovec,Stefanie Jegelka
17+阅读 · 2018年10月1日
Nicole Novielli,Daniela Girardi,Filippo Lanubile
3+阅读 · 2018年3月17日
Top