精华内容
下载资源
问答
  • 图神经网络
    千次阅读
    2020-11-21 13:59:08

    参考知乎:https://zhuanlan.zhihu.com/p/136521625

    0 前言

    图神经网络有很多比较好的综述:

    1、Graph Neural Networks: A Review of Methods and Applications.
    2、A Comprehensive Survey on Graph Neural Networks
    3、Deep Learning on Graphs: A Survey

    更多的论文可以参考清华大学整理的GNN paper list

    1 图神经网络和以往深度学习的区别

    以往:随着机器学习、深度学习的发展,语音、图像、自然语言处理逐渐取得了很大的突破,然而语音、图像、文本都是很简单的序列或者网格数据,是很结构化的数据,深度学习很善于处理该种类型的数据
    1现实世界:并不是所有的事物都可以表示成一个序列或者一个网格,例如社交网络、知识图谱、复杂的文件系统等,也就是说很多事物都是非结构化的。
    2
    相比于简单的文本和图像,这种网络类型的非结构化的数据非常复杂,处理它的难点包括:

    • 图的大小是任意的,图的拓扑结构复杂,没有像图像一样的空间局部性
    • 图没有固定的节点顺序,或者说没有一个参考节点
    • 图经常是动态图,而且包含多模态的特征

    那么对于这类数据我们该如何建模呢?能否将深度学习进行扩展使得能够建模该类数据呢?这些问题促使了图神经网络的出现与发展。

    2 图神经网络的特点

    相比较于神经网络最基本的网络结构全连接层(MLP),特征矩阵乘以权重矩阵,图神经网络多了一个邻接矩阵。计算形式很简单,三个矩阵相乘再加上一个非线性变换。
    3因此一个比较常见的图神经网络的应用模式如下图,输入是一个图,经过多层图卷积等各种操作以及激活函数,最终得到各个节点的表示,以便于进行节点分类、链接预测、图与子图的生成等等任务。

    4上面是一个对图神经网络比较简单直观的感受与理解,实际其背后的原理逻辑还是比较复杂的。

    更多相关内容
  • 长文详解图神经网络

    千次阅读 2020-08-17 22:55:56
    因此,本文试图沿着图神经网络的历史脉络,从最早基于不动点理论的图神经网络(Graph Neural Network, GNN)一步步讲到当前用得最火的图卷积神经网络(Graph Convolutional Neural Network, GCN), 期望通过本文带给...

    点击上方,选择星标置顶,每天给你送干货

    阅读大概需要25分钟

    跟随小博主,每天进步一丢丢

    链接:https://zhuanlan.zhihu.com/p/108294485

    编辑:王萌 澳门城市大学(深度学习冲鸭公众号)

    本文仅作学术分享,若侵权,请联系后台删文处理

    作者最近看了一些图与图卷积神经网络的论文,深感其强大,但一些Survey或教程默认了读者对图神经网络背景知识的了解,对未学过信号处理的读者不太友好。同时,很多教程只讲是什么,不讲为什么,也没有梳理清楚不同网络结构的区别与设计初衷(Motivation)。

    因此,本文试图沿着图神经网络的历史脉络,从最早基于不动点理论的图神经网络(Graph Neural Network, GNN)一步步讲到当前用得最火的图卷积神经网络(Graph Convolutional Neural Network, GCN), 期望通过本文带给读者一些灵感与启示。

    • 本文的提纲与叙述要点主要参考了2篇图神经网络的Survey,分别是来自IEEE Fellow的A Comprehensive Survey on Graph Neural Networks[1] 以及来自清华大学朱文武老师组的Deep Learning on Graphs: A Survey[7], 在这里向两篇Survey的作者表示敬意。

    • 同时,本文关于部分图卷积神经网络的理解很多都是受到知乎问题[8]高赞答案的启发,非常感谢他们的无私分享!

    • 最后,本文还引用了一些来自互联网的生动形象的图片,在这里也向这些图片的作者表示感谢。本文中未注明出处的图片均为笔者制作,如需转载或引用请联系本人。


    一、历史脉络

    在开始正文之前,笔者先带大家回顾一下图神经网络的发展历史。不过,因为图神经网络的发展分支非常之多,笔者某些叙述可能并不全面,一家之言仅供各位读者参考:

    1. 图神经网络的概念最早在2005年提出。2009年Franco博士在其论文 [2]中定义了图神经网络的理论基础,笔者呆会要讲的第一种图神经网络也是基于这篇论文。

    2. 最早的GNN主要解决的还是如分子结构分类等严格意义上的图论问题。但实际上欧式空间(比如像图像 Image)或者是序列(比如像文本 Text),许多常见场景也都可以转换成图(Graph),然后就能使用图神经网络技术来建模。

    3. 2009年后图神经网络也陆续有一些相关研究,但没有太大波澜。直到2013年,在图信号处理(Graph Signal Processing)的基础上,Bruna(这位是LeCun的学生)在文献 [3]中首次提出图上的基于频域(Spectral-domain)和基于空域(Spatial-domain)的卷积神经网络。

    4. 其后至今,学界提出了很多基于空域的图卷积方式,也有不少学者试图通过统一的框架将前人的工作统一起来。而基于频域的工作相对较少,只受到部分学者的青睐。

    5. 值得一提的是,图神经网络与图表示学习(Represent Learning for Graph)的发展历程也惊人地相似。2014年,在word2vec [4]的启发下,Perozzi等人提出了DeepWalk [5],开启了深度学习时代图表示学习的大门。更有趣的是,就在几乎一样的时间,Bordes等人提出了大名鼎鼎的TransE [6],为知识图谱的分布式表示(Represent Learning for Knowledge Graph)奠定了基础。


    二、图神经网络(Graph Neural Network)

    首先要澄清一点,除非特别指明,本文中所提到的图均指图论中的图(Graph)。它是一种由若干个结点(Node)及连接两个结点的边(Edge)所构成的图形,用于刻画不同结点之间的关系。下面是一个生动的例子,图片来自论文[7]:


    状态更新与输出

    最早的图神经网络起源于Franco博士的论文[2], 它的理论基础是不动点理论。给定一张图 ,每个结点都有其自己的特征(feature), 本文中用表示结点v的特征;连接两个结点的边也有自己的特征,本文中用表示结点v与结点u之间边的特征;GNN的学习目标是获得每个结点的图感知的隐藏状态 (state embedding),这就意味着:对于每个节点,它的隐藏状态包含了来自邻居节点的信息。那么,如何让每个结点都感知到图上其他的结点呢?GNN通过迭代式更新所有结点的隐藏状态来实现,在时刻,结点的隐藏状态按照如下方式更新:

    上面这个公式中的 就是隐藏状态的状态更新函数,在论文中也被称为局部转移函数(local transaction function)。公式中的指的是与结点相邻的边的特征,指的是结点的邻居结点的特征,则指邻居结点在时刻的隐藏状态。注意 是对所有结点都成立的,是一个全局共享的函数。那么怎么把它跟深度学习结合在一起呢?聪明的读者应该想到了,那就是利用神经网络(Neural Network)来拟合这个复杂函数 。值得一提的是,虽然看起来 的输入是不定长参数,但在 内部我们可以先将不定长的参数通过一定操作变成一个固定的参数,比如说用所有隐藏状态的加和来代表所有隐藏状态。我们举个例子来说明一下:

    假设结点为中心结点,其隐藏状态的更新函数如图所示。这个更新公式表达的思想自然又贴切:不断地利用当前时刻邻居结点的隐藏状态作为部分输入来生成下一时刻中心结点的隐藏状态,直到每个结点的隐藏状态变化幅度很小,整个图的信息流动趋于平稳。至此,每个结点都“知晓”了其邻居的信息。状态更新公式仅描述了如何获取每个结点的隐藏状态,除它以外,我们还需要另外一个函数 来描述如何适应下游任务。举个例子,给定一个社交网络,一个可能的下游任务是判断各个结点是否为水军账号。

    在原论文中,又被称为局部输出函数(local output function),与 类似,也可以由一个神经网络来表达,它也是一个全局共享的函数。那么,整个流程可以用下面这张图表达:

    仔细观察两个时刻之间的连线,它与图的连线密切相关。比如说在 时刻,结点 1 的状态接受来自结点 3 的上一时刻的隐藏状态,因为结点 1 与结点 3相邻。直到 时刻,各个结点隐藏状态收敛,每个结点后面接一个 即可得到该结点的输出 

    对于不同的图来说,收敛的时刻可能不同,因为收敛是通过两个时刻-范数的差值是否小于某个阈值 来判定的,比如:


    三、实例:化合物分类

    下面让我们举个实例来说明图神经网络是如何应用在实际场景中的,这个例子来源于论文[2]。假设我们现在有这样一个任务,给定一个环烃化合物的分子结构(包括原子类型,原子键等),模型学习的目标是判断其是否有害。这是一个典型的二分类问题,一个训练样本如下图所示:

    由于化合物的分类实际上需要对整个图进行分类,在论文中,作者将化合物的根结点的表示作为整个图的表示,如图上红色的结点所示。Atom feature 中包括了每个原子的类型(Oxygen, 氧原子)、原子自身的属性(Atom Properties)、化合物的一些特征(Global Properties)等。把每个原子看作图中的结点,原子键视作边,一个分子(Molecule)就可以看作一张图。在不断迭代得到根结点氧原子收敛的隐藏状态后,在上面接一个前馈神经网络作为输出层(即函数),就可以对整个化合物进行二分类了。

    当然,在同构图上根据策略选择同一个根结点对结果也非常重要。但在这里我们不关注这部分细节,感兴趣的读者可以阅读原文。

    不动点理论

    在本节的开头我们就提到了,GNN的理论基础是不动点(the fixed point)理论,这里的不动点理论专指巴拿赫不动点定理(Banach's Fixed Point Theorem)。首先我们用 表示若干个 堆叠得到的一个函数,也称为全局更新函数,那么图上所有结点的状态更新公式可以写成:

    不动点定理指的就是,不论是什么,只要 是个压缩映射(contraction map),经过不断迭代都会收敛到某一个固定的点,我们称之为不动点。那压缩映射又是什么呢,一张图可以解释得明明白白:

    上图的实线箭头就是指映射 , 任意两个点 在经过 这个映射后,分别变成了 。压缩映射就是指,t;1。也就是说,经过 变换后的新空间一定比原先的空间要小,原先的空间被压缩了。想象这种压缩的过程不断进行,最终就会把原空间中的所有点映射到一个点上。

    那么肯定会有读者心存疑问,既然 是由神经网络实现的,我们该如何实现它才能保证它是一个压缩映射呢?我们下面来谈谈 的具体实现。


    四、具体实现

    在具体实现中, 其实通过一个简单的前馈神经网络(Feed-forward Neural Network)即可实现。比如说,一种实现方法可以是把每个邻居结点的特征、隐藏状态、每条相连边的特征以及结点本身的特征简单拼接在一起,在经过前馈神经网络后做一次简单的加和。

    那我们如何保证 是个压缩映射呢,其实是通过限制 对 的偏导数矩阵的大小,这是通过一个对雅可比矩阵(Jacobian Matrix)的惩罚项(Penalty)来实现的。在代数中,有一个定理是: 为压缩映射的等价条件是 的梯度/导数要小于1。这个等价定理可以从压缩映射的形式化定义导出,我们这里使用 表示 在空间中的范数(norm)。范数是一个标量,它是向量的长度或者模,是 在有限空间中坐标的连续函数。这里把 简化成1维的,坐标之间的差值可以看作向量在空间中的距离,根据压缩映射的定义,可以导出:

    推广一下,即得到雅可比矩阵的罚项需要满足其范数小于等于等价于压缩映射的条件。根据拉格朗日乘子法,将有约束问题变成带罚项的无约束优化问题,训练的目标可表示成如下形式:

    其中是超参数,与其相乘的项即为雅可比矩阵的罚项。


    模型学习

    上面我们花一定的篇幅搞懂了如何让 接近压缩映射,下面我们来具体叙述一下图神经网络中的损失 是如何定义,以及模型是如何学习的。

    仍然以社交网络举例,虽然每个结点都会有隐藏状态以及输出,但并不是每个结点都会有监督信号(Supervision)。比如说,社交网络中只有部分用户被明确标记了是否为水军账号,这就构成了一个典型的结点二分类问题。

    那么很自然地,模型的损失即通过这些有监督信号的结点得到。假设监督结点一共有 个,模型损失可以形式化为:

    那么,模型如何学习呢?根据前向传播计算损失的过程,不难推出反向传播计算梯度的过程。在前向传播中,模型:

    1. 调用 若干次,比如 次,直到 收敛。

    2. 此时每个结点的隐藏状态接近不动点的解。

    3. 对于有监督信号的结点,将其隐藏状态通过 得到输出,进而算出模型的损失。
      根据上面的过程,在反向传播时,我们可以直接求出 和 对最终的隐藏状态 的梯度。然而,因为模型递归调用了 若干次,为计算 和 对最初的隐藏状态 的梯度,我们需要同样递归式/迭代式地计算 次梯度。最终得到的梯度即为 和 对 的梯度,然后该梯度用于更新模型的参数。这个算法就是 Almeida-Pineda 算法[9]。之所以要求 为压缩映射,也是因为只有 为压缩映射时,AP 才能得到一个收敛的梯度。


    五、GNN与RNN

    相信熟悉 RNN/LSTM/GRU 等循环神经网络的同学看到这里会有一点小困惑,因为图神经网络不论是前向传播的方式,还是反向传播的优化算法,与循环神经网络都有点相像。这并不是你的错觉,实际上,图神经网络与到循环神经网络确实很相似。为了清楚地显示出它们之间的不同,我们用一张图片来解释这两者设计上的不同:

    假设在GNN中存在三个结点,,,相应地,在RNN中有一个序列。笔者认为,GNN与RNN的区别主要在于4点:

    • GNN的基础理论是不动点理论,这就意味着GNN沿时间展开的长度是动态的,是根据收敛条件确定的,而RNN沿时间展开的长度就等于序列本身的长度。

    • GNN每次时间步的输入都是所有结点 的特征,而RNN每次时间步的输入是该时刻对应的输入。同时,时间步之间的信息流也不相同,前者由边决定,后者则由序列的读入顺序决定。

    • GNN采用 AP 算法反向传播优化,而RNN使用BPTT(Back Propogation Through Time)优化。前者对收敛性有要求,而后者对收敛性是没有要求的。

    • GNN循环调用 的目标是得到每个结点稳定的隐藏状态,所以只有在隐藏状态收敛后才能输出;而RNN的每个时间步上都可以输出,比如语言模型。

    不过鉴于初代GNN与RNN结构上的相似性,一些文章中也喜欢把它称之为 Recurrent-based GNN,也有一些文章会把它归纳到 Recurrent-based GCN中。之后读者在了解 GCN后会理解为什么人们要如此命名。


    GNN的局限

    初代GNN,也就是基于循环结构的图神经网络的核心是不动点理论。它的核心观点是通过结点信息的传播使整张图达到收敛,在其基础上再进行预测。收敛作为GNN的内核,同样局限了其更广泛的使用,其中最突出的是两个问题:

    • GNN只将边作为一种传播手段,但并未区分不同边的功能。虽然我们可以在特征构造阶段()为不同类型的边赋予不同的特征,但相比于其他输入,边对结点隐藏状态的影响实在有限。并且GNN没有为边设置独立的可学习参数,也就意味着无法通过模型学习到边的某些特性。

    • 如果把GNN应用在图表示的场景中,使用不动点理论并不合适。这主要是因为基于不动点的收敛会导致结点之间的隐藏状态间存在较多信息共享,从而导致结点的状态太过光滑(Over Smooth),并且属于结点自身的特征信息匮乏(Less Informative)。

    下面这张来自维基百科[13]的图可以形象地解释什么是 Over Smooth,其中我们把整个布局视作一张图,每个像素点与其上下左右以及斜上下左右8个像素点相邻,这决定了信息在图上的流动路径。初始时,蓝色表示没有信息量,如果用向量的概念表达即为空向量;绿色,黄色与红色各自有一部分信息量,表达为非空的特征向量。在图上,信息主要从三块有明显特征的区域向其邻接的像素点流动。一开始不同像素点的区分非常明显,但在向不动点过渡的过程中,所有像素点都取向一致,最终整个系统形成均匀分布。这样,虽然每个像素点都感知到了全局的信息,但我们无法根据它们最终的隐藏状态区分它们。比如说,根据最终的状态,我们是无法得知哪些像素点最开始时在绿色区域。

    在这里笔者再多说几句。事实上,上面这个图与GNN中的信息流动并不完全等价。从笔者来看,如果我们用物理模型来描述它,上面这个图代表的是初始时有3个热源在散发热量,而后就让它们自由演化;但实际上,GNN在每个时间步都会将结点的特征作为输入来更新隐藏状态,这就好像是放置了若干个永远不灭的热源,热源之间会有互相干扰,但最终不会完全一致。


    六、门控图神经网络(Gated Graph Neural Network)

    我们上面细致比较了GNN与RNN,可以发现它们有诸多相通之处。那么,我们能不能直接用类似RNN的方法来定义GNN呢? 于是乎,门控图神经网络(Gated Graph Neural Network, GGNN) [10]就出现了。虽然在这里它们看起来类似,但实际上,它们的区别非常大,其中最核心的不同即是门控神经网络不以不动点理论为基础。这意味着:不再需要是一个压缩映射;迭代不需要到收敛才能输出,可以迭代固定步长;优化算法也从 AP 算法转向 BPTT。


    状态更新

    与图神经网络定义的范式一致,GGNN也有两个过程:状态更新与输出。相比GNN而言,它主要的区别来源于状态更新阶段。具体地,GGNN参考了GRU的设计,把邻居结点的信息视作输入,结点本身的状态视作隐藏状态,其状态更新函数如下:

    如果读者对GRU的更新公式熟悉的话,对上式应该很好理解。仔细观察上面这个公式,除了GRU式的设计外,GGNN还针对不同类型的边引入了可学习的参数。每一种 对应一个 ,这样它就可以处理异构图。

    但是,仔细对比GNN的GGNN的状态更新公式,细心的读者可能会发现:在GNN里需要作为输入的结点特征 没有出现在GGNN的公式中! 但实际上,这些结点特征对我们的预测至关重要,因为它才是各个结点的根本所在。

    为了处理这个问题,GGNN将结点特征作为隐藏状态初始化的一部分。那么重新回顾一下GGNN的流程,其实就是这样:

    • 用结点特征初始化各个结点的(部分)隐藏状态。

    • 对整张图,按照上述状态更新公式固定迭代若干步。

    • 对部分有监督信号的结点求得模型损失,利用BPTT算法反向传播求得和GRU参数的梯度。


    实例1:到达判断

    为了便于理解,我们举个来自论文[10]的例子。比如说给定一张图,开始结点 ,对于任意一个结点 ,模型判断开始结点是否可以通过图游走至该结点。同样地,这也可以转换成一个对结点的二分类问题,即可以到达和不能到达。下图即描述了这样的过程:

    图中的红色结点即开始结点,绿色结点是我们希望判断的结点,我们这里称其为结束结点。那么相比于其他结点,这两个结点具有一定特殊性。那我们就可以使用第1维为1来表示开始结点,第2维为1来表示结束结点。最后在对结束结点分类时,如果其隐藏状态的第1维被赋予得到了一个非0的实数值,那意味着它可以到达。

    从初始化的流程我们也可以看出GNN与GGNN的区别:GNN依赖于不动点理论,所以每个结点的隐藏状态即使使用随机初始化都会收敛到不动点;GGNN则不同,不同的初始化对GGNN最终的结果影响很大。


    实例2:语义解析

    上面这个例子非常简单形象地说明了GNN与GGNN的不同,由于笔者比较关注Semantic Parsing(语义解析)相关的工作,所以下面我们借用ACL 2019的一篇论文[11]来讲一下GGNN在实际中如何使用,以及它适用于怎样的场景。

    首先为不了解语义解析的读者科普一下,语义解析的主要任务是将自然语言转换成机器语言,在这里笔者特指的是SQL(结构化查询语言,Structured Query Language),它就是大家所熟知的数据库查询语言。这个任务有什么用呢?它可以让小白用户也能从数据库中获得自己关心的数据。正是因为有了语义解析,用户不再需要学习SQL语言的语法,也不需要有编程基础,可以直接通过自然语言来查询数据库。事实上,语义解析放到今天仍然是一个非常难的任务。除去自然语言与程序语言在语义表达上的差距外,很大一部分性能上的损失是因为任务本身,或者叫SQL语言的语法太复杂。比如我们有两张表格,一张是学生的学号与其性别,另一张表格记录了每个学生选修的课程。那如果想知道有多少女生选修了某门课程,我们需要先将两张表格联合(JOIN),再对结果进行过滤(WHERE),最后进行聚合统计(COUNT)。这个问题在多表的场景中尤为突出,每张表格互相之间通过外键相互关联。其实呢,如果我们把表格中的Header看作各个结点,表格内的结点之间存在联系,而外键可以视作一种特殊的边,这样就可以构成一张图,正如下图中部所示:

    论文[11]就是利用了表格这样的特性,利用GGNN来解决多表问题。下面我们先介绍一下一般的语义解析方法,再介绍[11]是如何将图跟语义解析系统联系在一起的。就笔者知道的而言,目前绝大部分语义解析会遵循Seq2seq(序列到序列,Sequence to sequence)的框架,输入是一个个自然语言单词,输出是一个个SQL单词。但这样的框架完全没有考虑到表格对SQL输出暗含的约束。比如说,在单个SELECT子句中,我们选择的若干Header都要来自同一张表。再举个例子,能够JOIN的两张表一定存在外键的联系,就像我们刚刚举的那个学生选课的例子一样。

    那么,GGNN该如何结合到传统的语义解析方法中去呢?在论文[11]中,是通过三步来完成的:

    1. 首先,通过表格建立对应的Graph。再利用GGNN的方法计算每个Header的隐藏状态。

    2. 然后,在Seq2seq模型的编码阶段(Encoding),用每个输入的自然语言单词的词向量对表格所有Header的隐藏状态算一个Attention,利用Attention作为权重得到了每个自然语言单词的图感知的表示。

    3. 在解码阶段(Decoding),如果输出的是表格中的Header/Table这类词,就用输出的向量与表格所有Header/Table的隐藏状态算一个分数,这个分数由提供的。实际上是一个全连接层,它的输出实际上是SQL单词与表格中各个Header/Table的联系程度。为了让SQL的每个输出都与历史的信息一致,每次输出时都用之前输出的Header/Table对候选集中的Header/Table打分,这样就利用到了多表的信息。

    最终该论文在多表上的效果也确实很好,下面放一个在Spider[12]数据集上的性能对比:


    七、GNN与GGNN

    GGNN目前得到了广泛的应用,相比于GNN,其最大的区别在于不再以不动点理论为基础,虽然这意味着不再需要迭代收敛,但同时它也意味着GGNN的初始化很重要。从笔者阅读过的文献来看,GNN后的大部分工作都转向了将GNN向传统的RNN/CNN靠拢,可能的一大好处是这样可以不断吸收来自这两个研究领域的改进。但基于原始GNN的基于不动点理论的工作非常少,至少在笔者看文献综述的时候并未发现很相关的工作。

    但从另一个角度来看,虽然GNN与GGNN的理论不同,但从设计哲学上来看,它们都与循环神经网络的设计类似。

    • 循环神经网络的好处在于能够处理任意长的序列,但它的计算必须是串行计算若干个时间步,时间开销不可忽略。所以,上面两种基于循环的图神经网络在更新隐藏状态时不太高效。如果借鉴深度学习中堆叠多层的成功经验,我们有足够的理由相信,多层图神经网络能达到同样的效果。

    • 基于循环的图神经网络每次迭代时都共享同样的参数,而多层神经网络每一层的参数不同,可以看成是一个层次化特征抽取(Hierarchical Feature Extraction)的方法。

    在下一篇中,我们将介绍图卷积神经网络。它摆脱了基于循环的方法,开始走向多层图神经网络。在多层神经网络中,卷积神经网络(比如152层的ResNet)的大获成功又验证了其在堆叠多层上训练的有效性,所以近几年图卷积神经网络成为研究热点。


    参考文献

    [1]. A Comprehensive Survey on Graph Neural Networks, arxiv.org/abs/1901.0059

    [2]. The graph neural network model, persagen.com/files/misc

    [3]. Spectral networks and locally connected networks on graphs, arxiv.org/abs/1312.6203

    [4]. Distributed Representations of Words and Phrases and their Compositionality, papers.nips.cc/paper/50

    [5]. DeepWalk: Online Learning of Social Representations, arxiv.org/abs/1403.6652

    [6]. Translating Embeddings for Modeling Multi-relational Data, papers.nips.cc/paper/50

    [7]. Deep Learning on Graphs: A Survey, arxiv.org/abs/1812.0420

    [8]. 如何理解Graph Convolutional Network(GCN)? zhihu.com/question/5450

    [9]. Almeida–Pineda recurrent backpropagation, wikiwand.com/en/Almeida

    [10]. Gated graph sequence neural networks, arxiv.org/abs/1511.0549

    [11]. Representing Schema Structure with Graph Neural Networks for Text-to-SQL Parsing, arxiv.org/abs/1905.0624

    [12]. Spider1.0 Yale Semantic Parsing and Text-to-SQL Challenge, yale-lily.github.io/spi

    [13]. wikiwand.com/en/Laplaci

    说个正事哈

    由于微信平台算法改版,公号内容将不再以时间排序展示,如果大家想第一时间看到我们的推送,强烈建议星标我们和给我们多点点【在看】。星标具体步骤为:

    (1)点击页面最上方深度学习自然语言处理”,进入公众号主页。

    (2)点击右上角的小点点,在弹出页面点击“设为星标”,就可以啦。

    感谢支持,比心

    投稿或交流学习,备注:昵称-学校(公司)-方向,进入DL&NLP交流群。

    方向有很多:机器学习、深度学习,python,情感分析、意见挖掘、句法分析、机器翻译、人机对话、知识图谱、语音识别等。

    记得备注呦

    推荐两个专辑给大家:

    专辑 | 李宏毅人类语言处理2020笔记

    专辑 | NLP论文解读

    
    整理不易,还望给个在看!
    
    展开全文
  • 图神经网络及其应用

    千次阅读 2020-09-06 21:45:06
    图神经网络允许创建一个端到端的机器学习模型,该模型同时被训练来学习图结构数据的表示并在其上拟合预测模型。图神经网络可以应用于从聚类或可视化到对图数据进行分类或回归的任务,它们还可以在节点或图级别学习...

    Graph Neural Networks and its applications

    摘要

    以图形形式构建的数据存在于生物化学、图像处理、推荐系统和社会网络分析等多个领域。利用预处理技术在图结构数据上训练机器学习模型有几种方法,但它们缺乏完全适应数据集和手头任务的灵活性。图神经网络允许创建一个端到端的机器学习模型,该模型同时被训练来学习图结构数据的表示并在其上拟合预测模型。图神经网络可以应用于从聚类或可视化到对图数据进行分类或回归的任务,它们还可以在节点或图级别学习表示。他们在半监督学习和有监督图分类方面取得了最新的成果。半监督学习是指当一个图包含一些带标签的节点,并将它们的标签扩展到图的其余节点,例如对Reddit帖子进行分类。有监督图分类或回归用于预测整个图或子图的某些属性的类或值。这项工作将探索一些最突出的图神经网络变体,并将其应用于两项任务:近似社区检测Girvan-Newman算法和编译代码段分类。

    引言

    数据结构如图存在于许多领域,如生物学、化学、图像处理、推荐系统和社会网络分析等等。由于图数据的高维性和非欧几里德特性,在机器学习模型中使用这些数据是困难的。多年来,通过对图结构数据进行总结或以简化的方式表示信息来训练机器学习模型的方法已经被使用。然而,这些方法被用作预处理步骤,而不是训练过程的一部分。图神经网络是一种最新的技术,它可以创建一个端到端的机器学习模型,同时训练它来学习图结构数据的表示并在其上拟合预测模型。

    图神经网络[1]通过在低维空间中嵌入图节点来学习图的表示。端到端的训练允许学习这种表示法,以反映当前问题感兴趣的图的结构属性。将节点表示为嵌入,通过从每个节点的邻居处聚合信息以迭代方式创建。这个过程的计算成本很高,因此现代实现通过限制迭代次数或使用采样技术来提高速度。这种节点嵌入表示可以用于下游机器学习,也可以在嵌入的同时进行训练。当任务需要在节点级进行分类或进行回归时,直接使用嵌入中每个节点的表示。当任务需要在图或子图级别对值进行分类或预测时,可以使用池技术来获得图或子图级别的表示。
    图神经网络最显著的改进版本将卷积神经网络的思想应用于图,因此被称为图卷积网络[2]。它们可以分为两大类,基于谱的方法和基于空间的方法。基于谱的方法依赖于图的邻接矩阵的特征分解,这使得它们不太适合处理大数据或泛化为不可见的数据。另一方面,基于空间的方法依赖于每个节点邻域的信息聚合,使得算法能够成批地处理图,从而能够处理大的图。

    在大图的半监督学习中,只有一小部分节点具有标签或目标值,其余的节点没有标记,已经获得了最新的性能。该任务包括为其余未标记的节点分配标签([2],[3])。蛋白质分析中的图分类和回归任务也有了突破[4]。这也是科学界对这一领域越来越感兴趣的原因之一,自2016年以来,出版物大幅增加。

    近年来,关于图神经网络在生物化学、计算机视觉、推荐系统、组合优化、流量优化、归纳逻辑和程序验证等领域的应用已经出现。图神经网络解决的主要任务可概括为节点(图)分类、节点(图)回归、链路预测、节点聚类、图划分和图形可视化

    本硕士论文的目标是将图神经网络模型应用于不同的问题,以创造一个新的解决方案。其目的是了解图神经网络在每种情况下是如何使用的。研究了两个问题:Girvan-Newmann算法逼近和编译码函数分类。它们对应于图神经网络成功完成的两个主要任务:图上节点的半监督学习和有监督图的分类。

    图神经网络是解决图相关问题的一种很有前途的方法,在许多领域有着广泛的应用。现在似乎是时候开始学习最新的模型了,因为它们在一些已经解决的任务上取得了最先进的性能。

    论文的组织结构如下:下一节将介绍图神经网络模型的主要模型、内部结构以及它们所解决的问题。然后,在第三部分,介绍了实验所遵循的方法。之后,第四节将对实验的实施进行概述,而在第五节中总结实验结果。最后,在第六部分给出了本文的结论。

    内容

    目前技术水平
    这一部分是几个来源的汇编,这些来源调查了最新的图形神经网络的进展,并给出了关于其内部的详细信息。部分文本摘自以下研究论文和调查:

    • Hamilton等人,图的表示学习:方法和应用[5]

    • Xu等人,图神经网络有多强大?[6]

    • Wu等,图神经网络综合研究[7]

    • Kipf等人,用图卷积网络进行半监督分类[2]

    • Li等人,门控图序列神经网络[8]

    许多数据可以用图形表示,这是一种数据结构,常用于生物化学、社交网络、推荐系统甚至计算机程序分析等领域。许多机器学习应用程序都是使用图结构数据来进行预测的。将图结构数据中的信息合并为机器学习模型的输入并不简单。图结构数据是高维和非欧几里德的,这是创建一个统一和通用的方法来使用它作为模型输入的主要障碍。图数据是不规则的,具有可变大小和可变邻域数。有许多方法可以通过使用摘要图统计、内核函数或手工工程特性将图形数据转换为机器学习模型的可用特征。这些方法在学习过程中缺乏适应性。

    图神经网络的思想是学习一个映射,将节点或整个子图嵌入到低维向量空间 R d R^d Rd中,目标是优化映射,使嵌入空间中的几何关系反映原始图的结构。以前的图形学习方法使用这种方法作为预处理步骤,使用固定和/或手工设计的参数。图神经网络将这种表示学习任务视为机器学习任务,使用数据驱动方法学习编码所需图结构的嵌入。
    本节将介绍图神经网络的主要进展,展示节点和整个子图的表示技术。

    1.概念

    图的定义:图定义为G=(V,E,A),其中V是节点集,E是边集,A是邻接矩阵。
    图可以与节点属性X相关联,其中 X ∈ R N × D X∈R^{N×D} XRN×D是一个特征矩阵, X i ∈ R D X_i∈R^D XiRD代表节点的特征向量。

    图结构数据被认为是非欧式的。在由图本身定义的空间中,表示节点的向量的范数没有一个明确的定义。因此,两个节点之间的距离必须根据其他一些标准来定义。通常,两个节点之间的距离计算为源节点和目标节点之间沿边的最短路径中存在的节点数。此外,基于节点属性计算的节点间相似度不需要符合节点距离(如前一句所定义)。

    2.原始模型

    图神经网络的概念首先由Gori等人(2005)[9]提出,然后由Scarselli等人发展。(2009年)[1]。在[5]和[6]中解释了图神经网络训练过程的良好和一般性定义。以下段落对它们进行了总结。

    图神经网络:GNNs利用图结构和节点特征Xv为v∈V学习一个节点hv或整个图hG的表示向量。现代GNN遵循邻域聚合策略,通过聚合相邻节点的表示来迭代更新节点的表示。经过k次聚合迭代后,节点的表示将捕获其k跳网络邻域内的结构信息。形式上,GNN的第k层是:

    在这里插入图片描述

    其中 h v ( k ) h_v^{(k)} hv(k)是第k次迭代/层节点v的特征向量。初始化包含 h v ( 0 ) = X v h_v^{(0)}=X_v hv(0)=Xv和N(v),其是与v相邻的一组节点。迭代聚合过程是计算密集型的。现代实现试图加速这种收敛过程,例如通过限制迭代次数或使用随机游动来处理邻域。为了保证收敛性,递归函数(组合和聚合的组合)必须是收缩映射。收缩映射缩小映射后两点之间的距离。GNN使用Almeida-Pineda算法[10]训练模型。其核心思想是运行传播过程以达到收敛点,然后在给定收敛解的情况下执行反向过程。

    有两种类型的任务使用GNNs:节点分类/回归和图分类/回归。节点分类或回归是指当每个节点v∈V有一个相关的标签或目标值 y v y_v yv,目标是学习v的一个表示向量 h v hv hv,使得v的标签或目标值可以预测为 y v = f ( h v ) y_v=f(h_v) yv=fhv。图分类或回归是当给定一组图{G1,…,GN}及其标签或目标值{y1,…,yN}时,目标是学习一个表示向量 h G h_G hG,它有助于预测整个图的标号或目标值 y G = f ( h G ) y_G=f(h_G) yG=fhG

    对于节点分类/回归,使用最终迭代的节点表示进行预测。对于图分类/回归,读出函数从最终迭代中聚合节点特征,以获得整个图的表示hG:

    在这里插入图片描述

    READOUT函数可以是简单的置换不变函数,例如求和,也可以是更复杂的图形级合并函数。

    AGGREGATE(k)(·)和COMBINE(k)(·)的选择至关重要。 在下一部分中,将说明该模型的主要演变。 主要思想是对这些最新模型使用了AGGREGATE(k)(·)和COMBINE(k)(·)的哪些选择。

    3.高级模型

    早期的模型试图通过迭代传播邻居信息来学习节点的表示,直到所有节点都达到收敛。这个过程是计算密集型的,所以最近有一些出版物试图降低这个过程的成本。大量的方法将计算机视觉领域中卷积网络的特性应用于图形数据。它们被称为图卷积网络(GCN)。

    图形卷积网络:
    Bruna等人(2013)[11]提出了第一个GCN模型,该模型基于谱图论开发了一种图形卷积的变体。关于基于谱的图卷积网络,还有其他一些出版物[12]。谱方法从图形信号处理的角度引入滤波器来定义图形卷积,其中图形卷积运算被解释为从图形信号中去除噪声。他们依靠拉普拉斯矩阵的特征分解。这样做的缺点是,图的任何改动都会导致特征根的变化,并且所学习的滤波器是与域相关的,因此它们不能应用于具有不同结构的图。

    另一种卷积方法是基于空间的卷积网络,请参见[3]和[13]。他们根据节点的空间关系定义图卷积。这些方法通过聚集邻居节点信息直接在图域中执行卷积。基于空间的图卷积采用节点及其邻居的聚合来为其获取新的表示形式。一种常见的做法是将多个图卷积层堆叠在一起。

    在可扩展性和并行化方面,频谱方法的成本随图形的大小呈指数增长,但它需要整个图形存储在内存中。因此,这些方法不适用于大规模数据或并行化体系结构。但是,空间方法通过聚集邻居属性在图域中执行卷积,因此它们可以处理大型图。可以对一批节点而不是整个图执行计算。当邻居的数量变得过多时,也可以使用采样技术。

    在模型的泛化方面,基于频谱的模型假定固定的图,并且不善于泛化为未知的图。空间方法没有此约束,因为它们的卷积是在本地执行的,并且卷积中使用的权重可以在不同位置之间共享。

    最后,谱方法仅限于在无向图上使用,而空间方法可以通过修改聚合函数来处理多源输入和有向图。与基于谱的模型相比,基于空间的模型在科学界引起了更多的关注。

    让我们看看基于空间的图卷积网络如何实现将迭代生成节点表示形式的算法。该算法取决于权重(也称为系数),稍后将使用随机梯度下降或等效算法进行更新。这些更新机制允许训练一个端到端模型,该模型包含图形生成(嵌入)的表示形式以及将使用嵌入作为其分类或回归任务输入的后续层。

    上一小节显示,可以将节点状态(其属性值)的更新形式化为节点状态和邻居节点状态聚合的函数:

    在这里插入图片描述

    其中W(k)是第l个神经网络层的权重矩阵,而σ(∆)是类似于ReLU的非线性激活函数。 必须对邻接矩阵A施加一些其他约束。首先,必须将其添加到标识I中,以便创建自循环并允许在更新中对节点属性进行计数。 其次,必须将A标准化。

    此功能正在图上实现Weisfeiler-Lehman算法,该算法用于检测同构。 它为每个节点分配一组唯一的功能,以唯一地描述其在图中的角色。 其工作方式如下:
    对于所有节点 v i ∈ G v_i∈G viG

    •获取相邻节点{ v j v_j vj}的特征{ h v j h_{v_j} hvj}

    •更新节点特征 h v i h_{v_i} hvi= hash( P j h v j P_j h_{v_j} Pjhvj),其中hash(·)是注入式哈希函数。

    •重复k步直到收敛。

    这种想法的变体符合本小节中所介绍的更高级的Graph神经网络模型的基础,即Graph卷积网络及其变体,例如GraphSage或称为GIN的Graph同构网络。
    图卷积网络模型使用在图的所有位置上共享的过滤器参数W(k):

    在这里插入图片描述

    其中j索引vi的相邻节点,而cij是边(vi,vj)的归一化常数。 此版本是原始Weisfeiler-Legman算法中使用的哈希函数的可微化和参数化变体。 通过适当的初始化(Glorot),此更新规则是稳定的。

    当训练模型对整个图或子图执行分类时,必须使用图池化模块。 使用池化模块的GCN在区分图形结构方面与Weisfeiler-Legman测试一样强大。 与CNN的池化层相似,图池化模块可以通过在卷积层之间进行下采样来轻松减少方差和计算复杂度。 平均,最大和总和池是实现它们的最常见方法。

    本小节的其余部分将介绍最众所周知的GCN模型的演变过程。

    消息传递神经网络(MPNN):MPNN模型将几个现有的图形卷积网络概括为一个称为消息传递神经网络的统一框架。 它包括两个阶段,消息传递阶段和读取阶段。 消息传递阶段实际上运行T步基于空间的图卷积。 图卷积运算通过消息函数Mt(·)和更新函数Ut(·)根据

    在这里插入图片描述

    读出阶段实际上是一个池操作,该池操作基于每个单独节点的隐藏表示来生成整个图的表示。 定义为

    在这里插入图片描述

    通过输出函数R(·),最终表示y’用于执行图级预测任务。作者[14]指出,通过假设Ut(·)和Mt(∆)的不同形式,其他一些图卷积网络也属于它们的框架。

    GraphSage:在[3]中引入了聚合函数的概念来定义图卷积。 聚合功能本质上是集合节点的邻居信息。 它必须是不变的节点顺序的排列,例如均值,总和和最大值。 图卷积运算定义为

    在这里插入图片描述

    GraphSave没有更新所有节点的状态,而是提出了一种批量训练算法,提高了大型图的可伸缩性。图形的学习过程包括三个步骤。首先,以固定大小的节点局部k-hop邻域作为样本。第二个节点通过聚合其中心节点的信息来获取其最终状态。最后,它使用中心节点的最终状态来进行预测和反向传播错误。假设第t跳处要采样的邻居数为st,则一批中GraphSage的时间复杂度为A。因此,计算成本随着t的增加呈指数级增加,这使得GraphSage无法拥有深层架构。然而,在实践中,作者发现t=2的GraphSage已经获得了很高的性能。

    门控图神经网络(GGNN):也称为GGNN,这种GNN采用门控递归单元(GRU)[15]作为递归函数,将递归减少到固定的步骤数。 GGNN的空间图卷积定义为

    在这里插入图片描述

    为了更新权重,GGNN使用时间反向传播(BPTT)来学习参数。 优点是它不再需要约束参数以确保收敛。 但是,BPTT训练的缺点是牺牲了时间和记忆效率。 对于大型图而言,这尤其成问题,因为GGNN需要在所有节点上多次运行递归函数,从而需要将所有节点的中间状态存储在内存中。

    GGN的其他类型是图注意网络,图自动编码器,图生成网络和图时空网络。

    图注意力网络类似于GCN,并寻求一种聚合函数来融合图中的相邻节点,随机游走和候选模型,以学习新的表示形式。 关键区别在于图注意力网络采用注意力机制,该机制将更大的权重分配给更重要的节点,walks或模型。 注意力权重与端到端框架内的神经网络参数一起学习。

    图自动编码器是一种无监督的学习框架,其目的是通过编码器学习低维的节点向量,然后通过解码器重建图形数据。图自动编码是学习图嵌入的一种常用方法,对于没有属性信息的平面图和属性图都是如此。对于平面图,许多算法直接对邻接矩阵进行预处理,要么构造一个具有丰富信息的新矩阵(即逐点互信息矩阵),要么将邻接矩阵输入到自动编码器模型中,同时捕获一阶和二阶信息。对于属性图,图自动编码器模型倾向于使用GCN作为编码器的构建块,并通过链路预测解码器重建结构信息。

    图生成网络旨在从数据中生成合理的结构。从根本上讲,生成给定图经验分布的图是一个挑战,主要是因为图是复杂的数据结构。为了解决这一问题,研究者们探索将生成过程分解为节点和边的交替形成,采用生成性对抗训练。图生成网络的一个很有前途的应用领域是化合物合成。在化学图中,原子被视为节点,化学键被视为边。其任务是发现具有一定化学和物理性质的新的可合成分子。

    图时空网络的目的是从时空图中学习不可见的模式,在交通预测、人类活动预测等许多应用中发挥着越来越重要的作用。例如,底层道路交通网络是一个自然图,其中每个关键位置都是一个节点,其交通数据被连续监控。通过建立有效的图时空网络模型,可以准确地预测整个交通系统的交通状况。图时空网络的核心思想是同时考虑空间依赖和时间依赖。目前的许多方法都是用gcn来捕获依赖关系,同时使用一些RNN或CNN来对时间依赖进行建模。

    4.图神经网络的替代方案

    图神经网络的替代品早在出现之前就存在了:摘要图统计、核函数和网络嵌入(矩阵分解和随机游走)。

    摘要统计旨在捕捉整个图的非常具体的特征,希望它们能使模型能够区分或预测值。最常见的是平均节点度、聚类系数和分类度。它们通常缺乏很多表示灵活性,并且无法正确捕获那些摘要统计信息没有反映的图结构的各个方面

    核函数允许从图结构中捕获更多的信号,然后可以用来构建强大的分类或回归算法。它们也被用于无监督的学习方法中。内核的缺点是,它们不适合于大规模的图,因为它们需要在内存中保存整个图。

    网络嵌入的目的是通过保留网络拓扑结构和节点内容信息,在低维向量空间中表示网络顶点。这种嵌入可以用于任何下游的浅层机器学习算法,例如分类、回归或聚类,就像GGN的输出一样。许多网络嵌入算法都是典型的无监督算法,它们可以大致分为三类:矩阵分解[16]、随机游动[17]和深度学习方法。

    5.图神经网络的应用

    最后,本节介绍了图神经网络及其变体的最重要应用。几个特定领域的应用程序都属于以下机器学习任务列表,GNN对这些任务显示出良好的效果:

    •节点分类/回归

    •图形分类/回归

    •图形生成

    •图形可视化

    •节点群集

    •链路预测

    计算机视觉:在这一领域,研究了场景图的生成、点云的分类和分割以及动作识别。在场景图生成中,对象之间的语义关系有助于理解视觉场景背后的语义。给定一幅图像,场景图生成模型检测和识别对象,并预测对象对之间的语义关系[18]。在点云分类与分割中,[19]的任务是通过图卷积网络来确定点云所描绘的对象的拓扑结构。在动作识别中,在图像(或视频)中识别出的人的关节被检测出来,他们之间的连接形成一个图,可以用时空神经网络对人的行为进行分类。

    推荐系统:基于图的推荐系统以项目和用户为节点。通过利用项目与项目、用户与用户、用户与项目以及内容信息之间的关系,基于图形的推荐系统能够产生高质量的推荐。推荐系统的关键是给用户打分。因此,它可以归结为一个链路预测问题。目标是预测用户和项目之间缺少的链接([20],[21],[22])。
    生物化学:用图神经网络对分子结构进行分类。节点代表原子,边代表化学键。节点分类、图形分类和图形生成是三个主要任务。例如学习分子指纹[23]、预测分子性质[14]和合成化合物[24]

    通信网络建模:通信网络依靠路由和路径优化来保证良好的服务水平。目前,网络运营商缺乏有效的网络模型,能够以有限的成本准确预测相关的端到端关键性能指标(KPI),如延迟或抖动。分析模型和数据包级模拟已用于生成KPI,但成本较高。图神经网络模型RouteNet[25]被提出作为一个有效的解决方案,产生延迟和抖动的估计精度与包级网络模拟器类似。

    程序验证:是图神经网络显示其潜力的另一个富有成果的领域([8],[26]和[27])。指令遵循一系列的执行顺序,包括循环、分支和对其他指令的调用。这种代码建模允许验证变量的正确使用(在释放内存缓冲区后避免使用)、变量名猜测和函数重命名,以正确理解代码功能。门控图序列神经网络[8]被称为GGNN,是利用门控递归单元和现代优化技术输出序列的图神经网络。当问题是图结构时,它们相对于纯粹基于序列的模型(如LSTMs)具有良好的归纳偏差。它们在应用于内存安全的程序验证方面实现了最先进的性能,将存储器的状态映射为一组输入图,并将其映射为数据结构的逻辑描述。例如,这可以用来验证程序中没有空指针取消引用。在[26]中,作者使用图来表示代码的语法和语义结构,并使用基于图的深度学习方法来学习对程序结构进行推理。他们将GGNN的修改版本应用于VarNaming(根据变量的用法预测变量的名称)和varususage(在给定的程序位置选择正确变量的原因)。最后,在[27]中给出了一种预测整个函数或子例程名称的方法,其中没有使用图神经网络方法,而是从抽象语法树生成嵌入。它用于代码片段预测语义属性。我们相信,图神经网络有很大的潜力来实现最先进的性能。

    社交网络分析:随着网络的迅速扩张,社交网络作为人们与人交往的主要方式之一,在过去的几年里被大量采用。图神经网络在社会网络分析中有许多直接的应用,如朋友或链接预测[28]、社区检测[2]等,如[5]和[29]所示。社会网络分析的主要任务之一是发现社区的过程,称为社区检测。Girvan-Newman算法[30]是一种基于聚类的社区检测方法,被认为是最强大的算法之一。提出了一种基于边介度的无向边图和未加权图的划分算法。该算法以最“介于”社区和社区之间的边缘为中心,通过将这些边缘从原始边缘中移除,逐步构建出社区和社区之间的边缘图表。那个边介度算法时间复杂度的最坏情况是O(m2n),稀疏图的时间复杂度是O(n3),m是边的个数,n是顶点的个数,它的缺点是非常耗时,不适合应用于现代社交网络。如[31]所述,许多作者致力于改进它,降低计算复杂性或从中提取有用的概念(见[32]和[33],[34],[35])。

    展开全文
  • 图神经网络的表示方法和使用案例

    千次阅读 2021-08-26 09:20:11
    由于图数据结构无处不在,图神经网络 (GNN) 越来越受欢迎。 图使我们能够对科学领域中的许多不同问题进行建模,例如(但不限于)生物学、社会学、生态学、视觉、教育、经济学等。此外,图表示使我们能够处理大规模的...

    由于图数据结构无处不在,图神经网络 (GNN) 越来越受欢迎。 图使我们能够对科学领域中的许多不同问题进行建模,例如(但不限于)生物学、社会学、生态学、视觉、教育、经济学等。此外,图表示使我们能够处理大规模的非结构化数据。

    在本文中,我将展示如何在分类、聚类和可视化等任务中使用简单的 GNN。 我将使用 GCN(图卷积网络)作为运行示例。 这应该提供一个很好的启发,将意识形态扩展到他们自己的领域。

    GNN 的正式表示方法

    任何GNN都可以表示为一个包含两个数学算子的层,即聚合函数和组合函数。使用MPNN(消息传递神经网络)框架可以最好地理解这一点。

    聚合

    如果我们考虑上面的一个例子图,聚合器函数专门用于结合邻域信息。更正式地说,聚合可以表示为;

    简单来说,第k层GNN层中节点v的邻域聚合是使用相邻节点u的激活,k-1层的hᵤ来表示的。 v 的邻居表示为 N(v)。 在第一层 k-1=0,回退到当前节点特征。 在第一层,我们简单地聚合相邻节点的初始特征。 在 GCN 的情况下,聚合器只是归一化度(degree)的平均值(每个消息都由 v 和 u 的度的乘积的平方根归一化)。 只要操作是顺序不变的(结果不会因打乱而改变),就可以想到各种聚合器,例如 max、mean、min 等。

    组合

    相邻节点信息与节点本身的组合在下面的等式中正式表示。

    这里可以使用不同的操作,例如连接、求和或wise pooling操作。不同的 GNN 架构依赖于不同的功能。例如 GCN 使用平均值,我们将在接下来讨论。

    在上图中,我们可以通过 X1/(sqrt(7×2)) 来聚合节点 1 到 6 的特征 X1 是节点 1 的特征,7、2 分别是节点 6 和 1 的度数。对于每个节点,我们都可以这样做。直观地,我们可以将其视为每个节点通过对其出度进行平均来将其消息传递给其他节点,并且他们通过对入度进行平均来接收其他人的消息。因此得名 MPNN(Message Passing Neural Network)。

    对于具有邻接矩阵 A 和具有特征 X 的度矩阵 D(degree matrix) 的图 G(V, E),这可以通过 D(-1/2)XAD(-1/2) 轻松实现。通常,邻接矩阵加上I(单位矩阵)以结合节点自身的特征。在这种情况下,A 表示为 Â (A-hat),而 D 被 D-hat 替换,其中 D-hat 对应于 A-hat。在这一点上,我们已经在几个矩阵运算中执行了聚合和组合。得到的矩阵被传递到一个可训练的可微函数 ɸ,它通常是一个 MLP(多层感知器),即神经网络。

    堆叠层

    我们讨论了 GNN 层中发生的事情,现在我们堆叠了几个这样的层。 这意味着我们对邻接矩阵进行了更多的乘法运算。 如果你熟悉随机游走,则 D^(-1)A 称为转移矩阵(跃迁矩阵)。 用于迭代幂次直到收敛以找到从给定节点到另一个节点的随机游走概率。 直观地说,我们添加的 GNN 层越多,聚合扩展的跳数就越多。 或者换句话说,在一层之后,我们有节点及其邻居的信息。 当我们再次这样做时,邻居(拥有他们的邻居)再次聚合。 因此有 2 跳,依此类推。

    PyTorch几何框架

    GNN 可以使用 pytorch 几何库轻松实现。你可以找到许多 GNN 的实现和一个消息传递类来使用你自己的自定义实现。 在以下链接中查看。

    https://pytorch-geometric.readthedocs.io/en/latest

    Cora 数据集

    我们将使用流行的 Cora 数据集,该数据集由 7 类以下的科学出版物组成。 它通过引文连接,引文代表节点之间的边,即研究论文。

    使用 networkx 的图形可视化产生了上面的图像。 我们可以看到很少有颜色聚集在一起,让我们减少特征的维度并进行更多探索。

    UMAP查看特征

    解释数据的一种简单方法是查看数据它们的联系方式。 UMAP 是一个非常有用的流形学习工具,它使我们能够做到这一点。

    我们可以看到一些类的未知,但它也没法完整的区分。以上操作的简化代码如下(文末完整代码);

    # essential imports that will be needed throughout the blog
    import torch
    import torch.nn.functional as F
    from torch_geometric.datasets import Planetoid
    from torch_geometric.nn import GCNConv
    import matplotlib.pyplot as plt
    import seaborn as sns
    import umap
    import networkx as nx
    import numpy as npdataset = 'Cora'
    path = "./"
    dataset = Planetoid(path, dataset, transform=T.NormalizeFeatures())
    data = dataset[0]embd = umap.UMAP().fit_transform(data.x.numpy())
    plt.figure(figsize=(10, 10))
    sns.scatterplot(x=embd.T[0], y=embd.T[1], hue=data.y.numpy(), palette=palette)
    plt.legend(bbox_to_anchor=(1,1), loc='upper left')
    

    我们肯定对所看到的不满意,所以让我们尝试 GCN 并查看可视化。 我的网络如下(我从pytorch几何库github示例修改);

    class Net(torch.nn.Module):
        def __init__(self):
            super(Net, self).__init__()
            self.conv1 = GCNConv(dataset.num_features, 16, cached=True)
            self.conv2 = GCNConv(16, 16, cached=True)
            
            self.fc1 = torch.nn.Linear(16, dataset.num_classes)    
        def forward(self):
            x, edge_index, edge_weight = data.x, data.edge_index,
                                              data.edge_attr
            x = self.conv1(x, edge_index, edge_weight)
            x = F.relu(x)
            x = F.dropout(x, training=self.training)
            x = self.conv2(x, edge_index, edge_weight)
            x = F.relu(x)
            x = F.dropout(x, training=self.training)
            x = self.fc1(x)
            
            return F.log_softmax(x, dim=1)
      
    

    我们可以使用以下代码进行训练;

    device = torch.device('cuda' if torch.cuda.is_available() else 'cpu')
    model, data = Net().to(device), data.to(device)
    optimizer = torch.optim.Adam([
        dict(params=model.conv1.parameters(), weight_decay=5e-4),
        dict(params=model.fc1.parameters(), weight_decay=5e-4),
        dict(params=model.conv2.parameters(), weight_decay=0)
    ], lr=0.01)
    def train():
        model.train()
        optimizer.zero_grad()
        F.nll_loss(model()[data.train_mask],
                       data.y[data.train_mask]).backward()
        optimizer.step()
    

    请注意,Conv layer 2 中缺少 L2 正则化,这是 GCN 的作者凭经验决定的(https://github.com/tkipf/gcn/issues/108)。

    可视化时,输出如下所示;

    我们可以看到不同的类之间有非常清晰的分离。 在这里,训练以 0.7800 的测试精度结束。 我们可以多操作一点吗? 让我们来看看。

    Embedding losses

    神经网络可以看作是连续的可微函数。 分类本质上是学习预测的决策边界。

    总之,如果我们强制网络有更好的边界,我们可以有更好的可视化。 这意味着,我们应该能够分别看到这些类。 如果我们可视化聚集簇的数据,这将特别有用。 我们可以做的一件简单的事情是;

    1. 要求 GNN 更紧密地嵌入相似的类
    2. 要求 GNN 进一步嵌入不同的类

    请注意,嵌入是网络的最终层输出或分类输出。 在这种情况下,我们可以使用点积作为距离的度量。 我们为这种损失准备如下数据点对;

    y_neg_pairs = []
    y_pos_pairs = []
    
    data_idx = np.arange(len(data.x))
    for idx1, y1 in enumerate(data.y[data.train_mask].cpu().numpy()):
        for idx2, y2 in enumerate(data.y[data.train_mask].cpu().numpy()):
            if idx1 > idx2 and y1!=y2:
                y_neg_pairs.append([idx1, idx2])
            if idx1 > idx2 and y1==y2:
                y_pos_pairs.append([idx1, idx2])
                
    y_neg_pairs = np.array(y_neg_pairs)
    y_pos_pairs = np.array(y_pos_pairs)
    

    我们的修正损失函数如下:

    model_out = model()[data.train_mask]
        y_true = data.y[data.train_mask]
        nllloss = F.nll_loss(model_out, y_true)    
    
    	#Negative loss
        disloss_neg = F.logsigmoid(-1 * (model_out[y_neg_pairs.T[0]]*model_out[y_neg_pairs.T[1]])).sum(-1).mean()
        
        #Positive loss
        disloss_pos = F.logsigmoid((model_out[y_pos_pairs.T[0]]*model_out[y_pos_pairs.T[1]])).sum(-1).mean()
        
        loss = 10 * nllloss - disloss_neg - disloss_pos
    

    现在我们的训练结束了,损失为0.7720,比之前稍差。让我们可视化并查看使用UMAP的GNN的输出。

    我们可以看到簇现在更好,噪音略小。 尽管我们的准确性较低,但我们有更好的聚类分离。 实际上,较小的测试损失是由于集群的不确定性。 我们可以看到一些点自信地位于错误的颜色簇中。 这主要是由于数据的性质。

    将想法扩展到无监督聚类

    当我们没有标签,只有特征和图时,我们如何扩展这个想法。 简单的想法是使用图拓扑将更近的节点嵌入得更近,反之亦然。 代替我们的正负对,我们可以将直接连接对和随机对分别作为正负对。 这在各个领域都显示出良好的效果 😊

    我希望你喜欢这篇文章,我相信这对你的研究也会有用!

    本文代码如下:https://gist.github.com/anuradhawick/bd2eb3f4e5f9c8030f8125d97dc686ac

    作者:Anuradha Wickramarachchi

    展开全文
  • 文章《A Comprehensive Survey on Graph Neural Networks》[1]提供了一个全面的图神经网络(GNNs) 概述,并且将最新的图神经网络分为四类,即递归图神经网络(RecGNNs)、卷积图神经网络(ConvGNNs)、图自动编码器(GAEs)...
  • 什么是图神经网络

    万次阅读 多人点赞 2020-08-05 10:25:32
    2019年可以说是图神经网络元年。01 什么是图神经网络?1. 图和属性图要了解图神经网络,首先要了解图。图是由节点和边组成的,如下图所示。一般图中的节点表示实体对象(比如一个用户、一件商品、一辆车、一张银行卡...
  • 图神经网络(Graph Neural Network,GNN)是一类能够从图结构数据中学习特征规律的神经网络,是解决图结构数据(非欧氏空间数据)机器学习问题的最重要的技术。 1 图神经网络的基础知识 图神经网络(Graph Neural...
  • 4本图神经网络中文书籍的比较

    千次阅读 2021-05-06 21:42:59
    《深入浅出图神经网络》、《图神经网络基础于前沿》和《图神经网络导论》三本书的比较
  • 图神经网络,这到底是个什么?

    千次阅读 多人点赞 2021-03-01 14:27:54
    摘要:图神经网络是一种基于图结构的深度学习方法。 1、什么是图神经网络 图神经网络(Graph Neu做ral Networks, GNNs)是一种基于图结构的深度学习方法,从其定义中可以看出图神经网络主要由两部分组成,即“图”...
  • 一文搞懂什么是图神经网络GNN【入门教程】

    万次阅读 多人点赞 2020-10-30 23:20:37
    图神经网络入门 枯燥公式先不看 个人感觉最开始如果就看公式的话,不如先举一个实例让大家了解。因为公式往往过于抽象难懂,而实例却形象容易被人记住。
  • 基于图神经网络的时空预测

    千次阅读 2021-01-08 15:18:19
    近年来,对图的深度学习方法研究逐渐兴起,研究人员借鉴卷积网络、循环网络和深度自动编码器的思想,设计了一种面向图的神经网络结构 —— 图神经网络(GNN),将图神经网络应用到时空回归分析中的模型,可以称之为...
  • 但是,目前基于图神经网络的知识图谱学习、计算与应用的研究都还相对较少,未来仍有巨大的发展空间,例如基于图神经网络的知识图谱自动构建、基于异质图神经网络的知识融合、基于元路径或图神经网络的知识图谱复杂...
  • 处理动态图的图神经网络

    千次阅读 2020-12-07 17:14:00
    汤吉良老师团队发表于2020年的SIGIR ...已有的图神经网络都是为静态图设计的,不能利用动态图(比如社交网络中新用户加入或者有新的关系时)中的信息(已被证明能够促进各种图分析任务,如社区发现、边预测等
  • 图神经网络(GNN)TensorFlow实现

    千次阅读 热门讨论 2020-05-07 14:38:09
    图神经网络的研究与图嵌入或网络嵌入密切相关,图嵌入或网络嵌入是数据挖掘和机器学习界日益关注的另一个课题。图嵌入旨在通过保留图的网络拓扑结构和节点内容信息,将图中顶点表示为低维向量,以便使用简单的机器...
  • 摘要 近年来,由于神经网络在模式识别和数据挖掘领域的应用和其易用性,神经网络已获得了巨大的普及。...在本文中,我们将研究图和GNN的定义和基础,并了解图神经网络的一些最新应用。 一、什么是
  • 在本综述中,我们对现有的图神经网络模型进行了详细的回顾,对应用进行了系统的分类,并提出了四个有待进一步研究的问题。 1. Introduction  图是一种数据结构,它为一组对象(节点)及其关系(边)建模。...
  • PyTorch图神经网络实践(五)链路预测

    万次阅读 多人点赞 2020-11-02 22:40:44
    链路预测是网络科学里面的一个经典任务,其目的是利用当前已获取的网络数据(包含结构信息和属性信息)来预测网络中会出现哪些新的连边。 本文计划利用networkx包中的网络来进行链路预测,因为目前PyTorch Geometric...
  • 基于图神经网络 链路预测

    千次阅读 2021-09-04 01:14:30
    【ICLR2020】基于图神经网络的归纳矩阵补全 [图表示学习] 1 链路预测问题文献总结 [图表示学习] 2 动态图(Dynamic Graph)最新研究总结(2020) [图表示学习]动态网络上的图神经网络 文献阅读总结:网络表示学习 ...
  • 图神经网络笔记(一)

    千次阅读 多人点赞 2019-03-07 20:00:10
    图神经网络(GNN)是一类基于深度学习的处理图域信息的方法。由于其较好的性能和可解释性,GNN 最近已成为一种广泛应用的图分析方法。 为什么有图卷积神经网络 本质上说,世界上所有的数据都是拓扑结构,也就是...
  • 图神经网络 | (1) 一文读懂图卷积GCN

    千次阅读 2020-02-01 12:22:51
    1. 图网络的分类 2. 卷积 3. 卷积 4. 卷积的通式 5. 参考文献 1. 图网络的分类 在最开始,我们先梳理一下经常被提到的几个术语的区别和联系,也就是Graph Embedding,Graph Neural Network和Graph ...
  • 图神经网络的池化操作

    千次阅读 2020-12-23 21:27:32
    图神经网络有两个层面的任务:一个是图层面(graph-level),一个是节点(node-level)层面,图层面任务就是对整个图进行分类或者回归(比如分子分类),节点层面就是对图中的节点进行分类回归(交通网络道路流量...
  • 随着人工智能的兴起,机器学习(ML)和深度学习(DL)得到了迅速发展,并应用于计算机视觉(CV)、自然语言处理(NLP)、推荐等诸多领域。一些研究已经发展出将ML/DL...本文将为ML/DL图网络的研究提供一些实用的数据集。 Yelp数
  • 图神经网络资源大集合~快来打包带走

    千次阅读 多人点赞 2020-10-17 22:14:21
    2020年最新图神经网络相关的论文 & 书籍 & 代码& 视频课程等学习资源集合书 & 综述1.《Deep Learning on Graphs》这本书是...
  • 图神经网络综述

    万次阅读 2019-06-14 17:09:03
    图神经网络概述第三弹:来自IEEE Fellow的GNN综述 原文地址https://www.jiqizhixin.com/articles/2019-01-07-8 图神经网络(GNN)热度持续上升,之前我们曾介绍了清华两篇综述论文,参见:深度学习时代的图...
  • 这是一篇在2020年发表在ICLR的论文,论文使用图神经网络从稀疏数据中学习连续时间偏微分方程,文章提出的模型主要创新点是允许任意空间和时间离散化,也就是说在求解偏微分划分网格时,网格可以是不均匀的,由于所...
  • 前言 在计算机视觉以及自然...图神经网络的出现为这些非欧几里得数据的处理提供了新的思路。 图(Graph) 图(graph)是数据结构和算法学中最强大的框架之一。图可以用来表现多种类型的结构或系统,在很多应用上都有...
  • 图神经网络(GNN)简介

    千次阅读 多人点赞 2020-10-06 09:22:55
    然后介绍了不同形式的Graph神经网络及其原理。它还涵盖了GNN可以做什么以及GNN的一些应用。 图论 首先,我们需要知道什么是是一种由两个部分组成的数据结构:顶点*和edge*。它用作分析对象和实体之间成对关系...
  • 异构图神经网络

    万次阅读 2020-05-03 13:55:27
    1. 摘要     异构图表示学习的目的是为每个节点寻求一个有意义的...尽管在同构图嵌入、属性图嵌入以及图神经网络等方面做了大量的工作,但很少有人能够有效地联合考虑异构结构(图)信息以及各节点的异构内容信息...
  • 去中心化的联邦图神经网络

    万次阅读 2021-12-14 17:35:20
    已有一些关于中心化联邦图神经网络的研究,中心服务器协调各个参与者从图结构数据中训练的GNN模型。 存在问题 中心服务器需要进行模型聚合操作,在很多跨领域场景下,这种中心服务器是不被接受的。因此,去中心化的...
  •   最近在学习图神经网络相关知识,一起来拆书:《深入浅出图神经网络:GNN原理解析》,这本书从原理、算法、实现、应用四个维度详细讲解了图神经网络。接下来打算结合书本内容和相关知识做个专题记录分享,今天先跟...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 365,946
精华内容 146,378
关键字:

图神经网络

友情链接: 11ee7d.zip