从图结构数据中学习节点集的结构表示对于从节点角色发现到链接预测和分子分类的各种应用至关重要。图神经网络(GNNs)在结构表示学习方面取得了巨大的成功。然而:

大多数 GNN 受到 1-Weisfeiler-Lehman(WL)test 的限制,因此有可能为实际上不同的结构和图形生成相同的表示。 最近通过模仿高阶 WL tests 提出的更强大的 GNN 只关注全图表示,不能利用图结构的稀疏性来提高计算效率。 这篇文章提出了一类与结构相关的特征,称为距离编码(Distance Encoding,DE),以帮助 GNN 以比 1-WL test 更严格的表达能力来表示任意大小的节点集。DE 本质上捕获了要学习表示的节点集与图中每个节点之间的距离,其中包括与图相关的重要度量,如最短路径距离和广义 PageRank 得分。

此外,此文还提出了两个通用的 GNNs 框架来使用 DEs:

作为额外的节点属性 进一步作为 GNNs 中消息聚合的控制器 这两个框架仍然可以利用稀疏结构来保持处理大型图的可扩展性。

理论上,作者证明了这两个框架可以区分传统 GNN 经常失效的几乎所有规则图中嵌入的节点集。还严格分析了它们的局限性。 实验上,作者在6个真实网络上分别从节点结构角色预测、链路预测和三角形预测三个方面对这两个框架进行了实证评估。 结果表明,DE-assisted GNNs 的平均准确率比没有 DEs 的 GNNs 提高了15%,DE-assisted GNNs 的性能也明显优于专门为这些相应任务设计的其他最先进的基线。

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

相关内容

图卷积网络(Graph Convolutional Networks, GCNs)作为一种学习图结构数据的神经网络,在处理图数据分析问题上表现出了极大的人气,被用于如节点分类、图分类、链路预测、推荐等任务中。典型的GCN及其变体通常采用消息传递方式,其关键步骤是特征聚合,即一个节点在每个卷积层中聚合来自其拓扑邻居的特征信息。这样,特征信息通过网络拓扑结构传播到邻居节点表示中,然后通过学习所有节点嵌入表示用于下游任务如分类等,该学习过程是由部分节点标签来监督的。实际上,GCNs能够取得巨大的成功部分归功于它提供了一种拓扑结构和节点特征的融合策略来学习节点表示,而这种融合策略的学习训练过程由一个端到端的模型框架来监督。

这里我们首先思考了一个问题:作为端到端框架的GCNs,从拓扑结构和节点特征中真正学习和融合了什么样的信息? 在第二小节我们通过实验设计评估了GCNs融合拓扑结构和节点特征的能力。实验结果表明,GCNs在融合网络拓扑结构和节点特征上能力上与最理想的水平相差甚远。即使在一些简单的情况下(节点的特性/拓扑与节点标签的关联是非常明确的)GCN仍不能自适应地融合节点特性和拓扑结构并提取最相关的信息。而无法自适应学习到拓扑结构、节点特征与最终任务之间最相关的信息,可能会严重阻碍GCNs在分类任务中的表现能力,并且由于实际应用中图数据与任务之间的相关性往往非常复杂且不可知,因此自适应能力也是很重要的。

针对这些问题,我们提出了一种灵活地用于半监督节点分类的自适应多通道图卷积网络方案。其核心思想是同时学习基于节点特征、拓扑结构及其组合的节点嵌入,并依据特征与结构之间的相似性对标签预测的作用往往是互补的这一事实,采用设计的自适应融合机制来获取对分类任务最有帮助且最深层次的相关信息。

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

题目: Graph Structure of Neural Networks

摘要:

神经网络通常表示为神经元之间的连接图。但是,尽管已被广泛使用,但目前对神经网络的图结构与其预测性能之间的关系知之甚少。本文系统地研究了神经网络的图结构如何影响其预测性能。为此,开发了一种新的基于图的神经网络表示,称为关系图,其中神经网络的计算层对应于图结构每轮进行的消息交换。使用这种表示,我们表明:

(1)关系图的“最佳点”导致神经网络的预测性能大大提高;

(2)神经网络的性能大约是其关系图的聚类系数和平均路径长度的平滑函数;

(3)文中发现在许多不同的任务和数据集上是一致的;

(4)可以有效地识别最佳点;

(5)表现最佳的神经网络具有令人惊讶的类似于真实生物神经网络的图结构。

该方法为神经体系结构的设计和对神经网络的一般理解开辟了新的方向。

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

我们讨论关于图神经网络(GNNs)的两个基本问题。首先,我们证明了几个重要的图属性是不能由完全依赖于局部信息的GNN计算的。这样的GNN包括标准的消息传递模型,以及更强大的空间变体,利用本地图结构(例如,通过消息的相对方向,或本地端口排序)来区分每个节点的邻居。我们的处理包括一种新的图论形式主义。其次,我们为消息传递GNN提供了第一个依赖数据的泛化边界。该分析明确地说明了GNN的局部置换不变性。我们的边界比现有的基于VC维的GNN保证更紧,并且可与递归神经网络的Rademacher边界相媲美。

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

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

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

【导读】Graph Neural Network(GNN)由于具有分析图结构数据的能力而受到了广泛的关注。本文对Graph Neural Network进行了简要介绍。它涵盖了一些图论,以便于理解图和分析图时遇到的问题。然后介绍了不同形式的Graph神经网络及其原理。它还涵盖了GNN可以做什么以及GNN的一些应用。

图论

首先,我们需要知道什么是图。图是一种由两个部分组成的数据结构:顶点和edge。它用作分析目标和实体之间成对关系的数学结构。通常,将图定义为G =(V,E),其中V是一组节点,E是它们之间的边。

图通常由邻接矩阵A表示。如果图具有N个节点,则A的维数为(N x N)。人们有时会提供另一个特征矩阵来描述图中的节点。如果每个节点都有F个特征,则特征矩阵X的维数为(N x F)。

为什么图难以分析?

首先,在欧几里得空间中不存在图,这意味着它无法用我们熟悉的任何坐标系表示。与其他类型的数据(例如波,图像或时间序列信号)相比,这使得图数据的解释更加困难(“文本”也可以视为时间序列),可以轻松地将其映射为2-D或3-D欧几里德空间。

其次,图没有固定的形式。为什么?看下面的例子。图(A)和图(B)具有完全不同的结构和外观。但是,当我们将其转换为邻接矩阵表示形式时,两个图具有相同的邻接矩阵(如果不考虑边的权重)。那么我们应该考虑这两个图是相同还是不同?

最后,一般来说,图很难直观地显示出来以供人类解释。我不是在谈论像上面的例子这样的小图。我说的是涉及数百或数千个节点的巨型图。它的维数很高,节点密集地分组在一起,甚至使人难以理解图。因此,为该任务训练机器是具有挑战性的。以下示例显示了对集成电路中逻辑门进行建模的图。

Example of a giant graph: circuit netlist. Figure from J. Baehr et. al. “Machine Learning and Structural Characteristics of Reverse Engineering”

为什么要使用图?

人们选择使用图的原因可以归纳为以下几点:

  1. 图提供了一种更好的方式来处理诸如关系和交互之类的抽象概念。它们还提供了直观的视觉方式来思考这些概念。图也构成了在社会环境中分析关系的自然基础。
  2. 图可以通过将问题简化为更简单的表示形式来解决更复杂的问题,或者从不同的角度将问题转换为表示形式。
  3. 图论和概念用于研究和建模社交网络,欺诈模式,功耗模式,病毒性以及在社交媒体中的影响力。社交网络分析(SNA)可能是图论在数据科学中最著名的应用。

传统图分析方法

传统方法主要基于算法,例如:

  1. 搜索算法,例如BFS,DFS
  2. 最短路径算法,例如Dijkstra算法,最近邻居
  3. 生成树算法,例如Prim算法
  4. 聚类方法,例如高度连接的组件,k均值 这种算法的局限性在于,在应用该算法之前,我们需要以一定的置信度获得图的先验知识。换句话说,它对我们研究图本身没有任何意义。最重要的是,没有办法执行图级别分类。

图神经网络

所谓的图神经网络是一种可以直接应用于图的神经网络。它为节点级别,边缘级别和图级别的预测任务提供了一种方便的方法。

文献中主要有三种类型的图神经网络:

  1. 递归图神经网络
  2. 空间卷积网络
  3. 谱卷积网络

GNN的直觉是,节点自然是由其邻居和连接定义的。为了理解这一点,我们可以简单地想象一下,如果删除节点周围的邻居和连接,则该节点将丢失其所有信息。因此,节点的邻居和与邻居的连接定义了节点的概念。

考虑到这一点,我们然后给每个节点一个状态(x)来表示其概念。我们可以使用节点状态(x)产生输出(o),即有关概念的决策。节点的最终状态(x_n)通常称为“节点嵌入”。所有GNN的任务是通过查看其相邻节点上的信息来确定每个节点的“节点嵌入”。 我们将从图神经网络,循环图神经网络或RecGNN的经典版本开始。

递归图神经网络

正如原始GNN论文中介绍的那样,RecGNN是基于Banach不动点定理的假设而构建的。Banach不动点定理指出:(X,d)是一个完整的度量空间,而(T:X→X)是一个压缩映射。然后,T具有唯一的不动点(x ∗),对于任何x∈X,n→∞的序列T_n(x)收敛到(x ∗)。这意味着,如果我申请的映射T上X为ķ倍,X ^ K在几乎等于x ^(K-1),即:

RecGNN定义了一个参数化函数f_w:

其中L_N,l_co,x_ne,l_ne 表示当前节点的特征[n],节点的边缘[n],相邻节点的状态,与相邻节点的功能。(在原始论文中,作者将节点特征称为节点标签。这可能会造成一些混乱。)

An illustration of node state update based on the information in its neighbors. Figure from “The Graph Neural Network Model” 最终,在经过k次迭代之后,最终的节点状态将用于生成输出,以决定每个节点。输出函数定义为:

空间卷积网络

空间卷积网络的直觉类似于著名的CNN,后者主导着图像分类和分割任务的文献。要了解图像上的CNN,您可以查看这篇文章,其中详细说明了CNN。

简而言之,在图像上进行卷积的想法是对中心像素周围的相邻像素求和,该像素由参数化大小和可学习权重的滤波器指定。空间卷积网络通过将相邻节点的特征聚合到中心节点中采用了相同的思想。

Left: Convolution on a regular graph such as an image. Right: Convolution on the arbitrary graph structure. Figure from “A Comprehensive Survey on Graph Neural Networks”

谱卷积网络

与其他类型的GNN相比,这种类型的图卷积网络具有非常强大的数学基础。谱卷积网络建立在图信号处理理论的基础上。并通过简化和逼近图卷积。 通过Chebyshev多项式逼近 (Hammond et al。2011),图卷积可以简化为以下形式:

进一步简化后,GCN论文提出了一种2层神经网络结构,可以用以下等式描述:

其中A_head是原始图邻接矩阵A的预处理拉普拉斯算子。(有关数学的详细信息,请参见GCN论文。将需要大量的精力来进行充分说明。)

如果您有一些机器学习经验,则此公式看起来非常熟悉。这不过是常用的两个完全连接的层结构。但是在这种情况下,它确实可以用作图卷积。我将在下面说明为什么它可以执行图卷积。

Example of a graph with a feature assigned to each node. Figured by author

让我们考虑一下,我们有一个包含4个节点的简单图。如上图所示,为这些节点中的每个节点分配了一个特征矩阵。图邻接矩阵和特征矩阵很容易得出,如下所示:

Example of the adjacency matrix and feature matrix. Figure by author

注意,邻接矩阵的对角线故意更改为“ 1”,以为每个节点添加一个自环。当我们执行特征聚合时,这将包括每个节点本身的特征。 然后,我们执行A x X(为简单起见,我们先忽略A的拉普拉斯算子和权重矩阵W。)

Example of graph convolution by matrix multiplication. Figure by author

矩阵乘法的结果显示在最右边的矩阵中。让我们以第一个节点的结果功能为例。不难发现结果是[节点1]的所有特征之和,包括[节点1]本身的特征,并且[节点4]中的特征不包括在内,因为它不是[节点1]的邻居。。在数学上,仅当存在边时,图的邻接矩阵才具有值“ 1”,否则具有“ 0”。这使得矩阵乘法成为连接到参考节点的节点的特征之和。 因此,频谱卷积网络和空间卷积网络尽管是在不同的基础上开始的,但是它们共享相同的传播规则。 当前可用的所有卷积图神经网络共享相同的格式。他们都尝试学习通过该消息传递过程传递节点信息并更新节点状态的功能。 任何图神经网络可被表达为与消息传递神经网络(J. Gilmer et al. , 2017)的消息传递功能,节点更新功能和读出功能。

GNN可以做什么?

GNN解决的问题可以大致分为三类:

  1. 节点分类
  2. 链接预测
  3. 图分类 在节点分类中,任务是预测图中每个节点的节点嵌入。通常以半监督的方式训练此类问题,其中仅对部分图进行标记。节点分类的典型应用包括引文网络,Reddit帖子,Youtube视频和Facebook朋友关系。 在链接预测中,任务是了解图中实体之间的关系,并预测两个实体之间是否存在连接。例如,推荐系统可被视为链接预测问题,其中模型被赋予一组用户对不同产品的评论,任务是预测用户的偏好并调整推荐系统以根据用户推送更多相关感兴趣的产品。 在图分类中,任务是将整个图分类为不同的类别。它类似于图像分类,但是目标变为图域。有许多工业问题可以应用图分类,例如在化学,生物医学,物理学中,模型被赋予分子结构并被要求将目标分类为有意义的类别。它加快了对原子,分子或任何其他结构化数据类型的分析。

一些实际的应用

在了解了GNN可以执行哪种类型的分析之后,您一定想知道我可以对图进行哪些实际应用。好了,本节将为您提供有关GNN实际应用的更多见解。

自然语言处理中的GNN

GNN被广泛使用在自然语言处理(NLP)中。实际上,这也是GNN最初开始的地方。如果您中的某些人具有NLP经验,则必须考虑到文本应该是一种序列或时间数据,则可以由RNN或LTSM最好地描述。然而,GNN则从完全不同的角度解决了这个问题。GNN利用单词或文档的内部关系来预测类别。例如,引文网络尝试根据论文引文关系和其他论文中引用的词来预测网络中每篇论文的标签。它也可以通过查看句子的不同部分而不是像RNN或LTSM中那样的纯粹序列来构建语法模型。

计算机视觉中的GNN

许多基于CNN的方法已经在图像中的目标检测中达到了最新的性能,但是我们还不知道目标之间的关系。GNN在CV中的一种成功应用是使用图来建模基于CNN的检测器检测到的物体之间的关系。从图像中检测到目标后,将它们输入到GNN推理中以进行关系预测。GNN推断的结果是生成的图,该图对不同目标之间的关系进行建模。

Scene Graph Generation. Figure from D. Xu, Y. Zhu, C. B. Choy, and L. Fei-Fei, “Scene graph generation by iterative message passing,” in Proc. of CVPR, 2017

CV中另一个有趣的应用是根据图描述生成图像。这可以解释为几乎与上述应用相反。图像生成的传统方式是使用GAN或自动编码器生成文本到图像。从图到图像的生成不是使用文本来描述图像,而是提供了有关图像语义结构的更多信息。

Image generated from scene graphs. Figure from J. Johnson, A. Gupta, and L. Fei-Fei, “Image generation from scene graphs,” in Proc. of CVPR, 2018 我想分享的最有趣的应用是零样本学习(ZSL)。您可以找到这篇文章,以全面了解ZSL。总之,ZSL是想学给定的一类分类NO(目标类别的)训练样本。这是非常具有挑战性的,因为如果没有给出训练样本,我们需要让模型在逻辑上“思考”以识别目标。例如,如果给了我们三张图像(如下图所示),并告诉我们在其中找到“ okapi”。我们以前可能没有看过“okapi”。但是,如果我们还得到信息,“okapi”是一种有四只腿,斑马纹皮肤的鹿面动物,那么我们就不难确定哪个是“okapii”。典型的方法是通过将检测到的特征转换为文本来模拟这种“思考过程”。但是,文本编码彼此独立。很难对文本描述之间的关系进行建模。换句话说,图表示很好地模拟了这些关系。

Figure from X. Wang, Y. Ye, and A. Gupta, “Zero-shot recognition via semantic embeddings and knowledge graphs,” in CVPR 2018

其他领域的GNN

GNN的更多实际应用包括人类行为检测,交通控制,分子结构研究,推荐系统,程序验证,逻辑推理,社会影响预测以及对抗攻击。下面显示了对社交网络中人际关系建模的图表。GNN可用于将人们分为不同的社区群体。

结论

我们在本文中介绍了一些图论,并强调了分析图的重要性。人们总是将机器学习算法视为“ 黑匣子 ”。大多数机器学习算法仅从训练数据的特征中学习,但没有实际的逻辑可以执行。使用形,我们也许能够将一些“逻辑”传递给机器,并使其更自然地“思考”。

GNN仍然是一个相对较新的领域,值得更多的研究关注。它是分析图数据的强大工具。但是,它不仅限于图中的问题。它可以很容易地推广到任何可以通过图建模的研究中。图建模是分析问题的自然方法。

参考链接:

https://medium.com/datadriveninvestor/an-introduction-to-graph-neural-network-gnn-for-analysing-structured-data-afce79f4cfdc

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

图神经网络是解决各种图学习问题的有效的机器学习模型。尽管它们取得了经验上的成功,但是GNNs的理论局限性最近已经被揭示出来。因此,人们提出了许多GNN模型来克服这些限制。在这次调查中,我们全面概述了GNNs的表达能力和可证明的强大的GNNs变体。

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

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

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

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

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

题目: How Powerful are Graph Neural Networks?

摘要: 图神经网络(GNNs)是一种有效的图表示学习框架。GNNs遵循邻域聚合方案,通过递归地聚合和转换邻域节点的表示向量来计算节点的表示向量。许多GNN变体已经被提出,并且在节点和图分类任务上都取得了最新的结果。然而,尽管GNNs给图形表示学习带来了革命性的变化,但是对于它们的表示性质和局限性的理解还是有限的。在这里,我们提出了一个理论框架来分析GNNs捕捉不同图形结构的表现力。我们的结果描述了流行的GNN变体,如图卷积网络和图年龄的辨别能力,并且表明它们不能学习辨别某些简单的图结构。然后,我们开发了一个简单的体系结构,它可以证明是GNNs类中最具表现力的,并且与Weisfeiler-Lehman图同构测试一样强大。我们在一些图形分类基准上实证验证了我们的理论发现,并证明我们的模型达到了最先进的性能。

作者简介: Keyulu Xu,麻省理工学院EECS系的研究生,也是CSAIL和机器学习小组的成员。他的兴趣是智力和推理理论。

WeiHua Hu,哈尔滨工业大学(深圳)助理教授。

成为VIP会员查看完整内容
0
32
小贴士
相关主题
相关资讯
图嵌入(Graph embedding)综述
人工智能前沿讲习班
232+阅读 · 2019年4月30日
CNN已老,GNN来了!清华大学孙茂松组一文综述GNN
全球人工智能
8+阅读 · 2018年12月26日
图神经网络综述:模型与应用
PaperWeekly
146+阅读 · 2018年12月26日
图上的归纳表示学习
科技创新与创业
11+阅读 · 2017年11月9日
相关论文
Pan Li,Yanbang Wang,Hongwei Wang,Jure Leskovec
6+阅读 · 8月31日
Hyper-SAGNN: a self-attention based graph neural network for hypergraphs
Ruochi Zhang,Yuesong Zou,Jian Ma
7+阅读 · 2019年11月6日
Auto-GNN: Neural Architecture Search of Graph Neural Networks
Kaixiong Zhou,Qingquan Song,Xiao Huang,Xia Hu
3+阅读 · 2019年9月10日
MR-GNN: Multi-Resolution and Dual Graph Neural Network for Predicting Structured Entity Interactions
Nuo Xu,Pinghui Wang,Long Chen,Jing Tao,Junzhou Zhao
5+阅读 · 2019年5月23日
Yue Yu,Jie Chen,Tian Gao,Mo Yu
4+阅读 · 2019年4月22日
Deep Node Ranking: an Algorithm for Structural Network Embedding and End-to-End Classification
Blaž Škrlj,Jan Kralj,Janez Konc,Marko Robnik-Šikonja,Nada Lavrač
3+阅读 · 2019年3月13日
Contextualized Non-local Neural Networks for Sequence Learning
Pengfei Liu,Shuaichen Chang,Xuanjing Huang,Jian Tang,Jackie Chi Kit Cheung
3+阅读 · 2018年11月21日
Dissecting Contextual Word Embeddings: Architecture and Representation
Matthew E. Peters,Mark Neumann,Luke Zettlemoyer,Wen-tau Yih
20+阅读 · 2018年8月27日
Petar Veličković,Guillem Cucurull,Arantxa Casanova,Adriana Romero,Pietro Liò,Yoshua Bengio
5+阅读 · 2018年2月4日
Jiezhong Qiu,Yuxiao Dong,Hao Ma,Jian Li,Kuansan Wang,Jie Tang
15+阅读 · 2017年12月12日
Top