精华内容
下载资源
问答
  • 图神经网络ppt

    2019-04-16 23:45:33
    入门图神经网络的好资源,了解GNN的基本原理,训练方法,以及其各种变体的应用。入门图神经网络的好资源,了解GNN的基本原理,训练方法,以及其各种变体的应用。入门图神经网络的好资源,了解GNN的基本原理,训练方法,以及其...
  •   最近在学习图神经网络相关知识,一起来拆书:《深入浅出图神经网络:GNN原理解析》,这本书从原理、算法、实现、应用四个维度详细讲解了图神经网络。接下来打算结合书本内容和相关知识做个专题记录分享,今天先跟...

    前言

    最近在学习图神经网络相关知识,一起来拆书:《深入浅出图神经网络:GNN原理解析》,这本书从原理、算法、实现、应用四个维度详细讲解了图神经网络。接下来打算结合书本内容和相关知识做个专题记录分享,今天先跟大家聊聊关于图的一些基础知识。

    为什么要研究图?

    在过去的几年中,神经网络的成功推动了模式识别和数据挖掘的研究。许多机器学习任务,如目标检测、机器翻译和语音识别,曾经严重依赖手工的特征工程来提取信息特征集被各种端到端的深度学习范式(例如卷积神经网络(CNN)、长短期记忆(LSTM)和自动编码器)彻底改变了。

    尽管深度学习在欧氏空间中的数据方面取得了巨大的成功,但在许多实际的应用场景中的数据是从非欧式空间生成的,同样需要进行有效的分析。图数据的复杂性对现有的机器学习算法提出了重大挑战,这是因为图数据是不规则的。每个图都有一个大小可变的无序节点,图中的每个节点都有不同数量的相邻节点,导致一些重要的操作(例如卷积)在图像上很容易计算,但不再适合直接用于图域。

    近年来,人们对深度学习方法在图数据上的扩展越来越感兴趣。很多数据都是图结构,例如社交网络、经济网络、生物医学网络、信息网络(互联网网站、学术引用)、互联网、神经网络。而网络是它们的通用语言,因此具备极大的研究价值。在深度学习的成功推动下,研究人员借鉴了卷积网络、循环网络和深度自动编码器的思想,定义和设计了用于处理图数据的神经网络结构,由此衍生出一个新的研究热点——“图神经网络(Graph Neural Networks,GNN)”本篇文章就从图的概述入手开始我们的GNN之路。

    1.1 图的基本定义

    图(G)定义为(V,E) ,记为G=(V,E) 。
    其中: V是顶点(Vertex)的非空有限集合,记为V(G);E是无序集V&V的一个子集,记为E(G) 。
    将顶点集合为空的图称为空图。其形式化定义为:
    在这里插入图片描述

    1.1.1 图的基本类型

    • 有向图与无向图 (边是否有方向)
    • 非加权图与加权图(边是否有权重)
    • 连通图与非连通图(是否有孤立顶点)
    • 二部图 (任意边均从属于其2个子图)
      在这里插入图片描述
      在这里插入图片描述

    1.1.2 邻居和度

    在这里插入图片描述
    邻居:与顶点A相连接的顶点B和顶点C都是A的邻居
    度:顶点A的边的数量(包括出度2与入度1)

    1.1.3 子图与路径

    子图:设G=(V,E)是一个图,若V’是V的子集,E’是E的子集,且E’中的边所关联的顶点均在V’中,则G’=(V’,E’)也是一个图,并称其为G的子图(Subgraph)。
    路径:从顶点V1到顶点V2的边的数目,最少的路径成为顶点的距离
    在这里插入图片描述在这里插入图片描述

    • 无向图的路径
      在无向图G中,若存在一个顶点序列vp,vi1,vi2,…,vim,vq,使得(vp,vi1),(vi1,vi2),…,(vim,vq)均属于E(G),则称顶点vp到vq存在一条路径(Path)。

    • 有向图的路径
      在有向图G中,路径也是有向的,它由E(G)中的有向边<vp,vi1>,<vi1,vi2>,…,<vim,vq>组成。

    • 路径长度
      路径长度定义为该路径上边的数目。

    • 简单路径
      若一条路径上除了vp和vq可以相同外,其余顶点均不相同,则称此路径为一条简单路径。
      如图G2中顶点序列vl,v2,v3,v4是一条从顶点v1到顶点v4的长度为3的简单路径;顶点序列v1,v2,v4,v1,v3是一条从顶点v1到顶点v3的长度为4的路径,但不是简单路径;

    • 简单回路或简单环(Cycle)
      起点和终点相同(vp=vq)的简单路径称为简单回路或简单环(Cycle)。
      如图G2中,顶点序列v1,v2,v4,v1是一个长度为3的简单环;有向图G1中,顶点序列v1,v2,v1是一长度为2的有向简单环。

    • 有根图和图的根
      在一个有向图中,若存在一个顶点v,从该顶点有路径可以到达图中其它所有顶点,则称此有向图为有根图,v称作图的根。

    1.2 图的存储与遍历

    1.2.1 邻接矩阵与关联矩阵

    K阶邻居:V1通过k条边到达顶点V2,V2为V1的k阶邻居
    邻接矩阵:N个顶点组成的2维度关系矩阵
    关联矩阵:N个顶点与M条边组成的2维度关系矩阵。关联矩阵M(D)=(mij)n×ε的元素mij定义为:
    在这里插入图片描述
    在这里插入图片描述
    上图的邻接矩阵和关联矩阵分别是:
    在这里插入图片描述在这里插入图片描述

    1.2.2 图的遍历

    图的遍历:从某顶点出发,沿着图中的边对所有顶点访问一次且仅访问一次。
    包括深度优先(DFS)与广度优先(BFS)

    • 深度优先遍历(deep first traverse)
      所谓深度优先就是以纵向优先的方式遍历节点。我们从当前节点curr出发,如果当前节点被访问过,就返回,否则将该节点标记为访问过的节点,然后在递归访问当前节点的所有邻接节点。
     function traverse(Node node){    //递归方式实现的深度优先遍历
                  if(node.isVisited){    //如果当前节点已经被访问过
                      return;            //这个是递归出口
                  }
                  node.isVisited=true;   //将当前节点置为已经访问
                  for(var i=0;i<node.brother.length;i++){
                      traverse(node.brother[i]);   //访问当前node的所有邻接节点
                  }
                  return;       //结束
              }
    
    • 广度有限遍历(broad first traverse)
      所谓的广度优先指的是从当前节点curr出发,将该节点标记为已经访问过的节点,然后在依次访问curr的没有被访问的邻接节点,然后在依次访问邻接节点的邻接节点,直到所有的节点被访问。
    function bft(Node node){
    	var queue=[],temp; //队列结构,是待访问的节点队列,这些节点被排了顺序,按顺序被访问
                 queue.push(node); //初始化队列结构
                 while(queue.isNotEmpty())//当队列不为空的时候
                    temp=queue.shift();            //取得当前的节点元素
                    temp.isVisited=true;           //将当前节点置为已经访问
                    for(var i=0;i<temp.brother.length;i++){
                        if(!temp.brother[i].isVisited){   //如果当前节点的邻接节点没有被访问过
                            queue.push(temp.brother[i]);  //将这个邻接节点加入待访问队列
                        }
                    }}
    

    ==1.3 图数据的应用场景 ==

    比起传统的信息存储和组织模式,图数据库能够很清晰揭示复杂的模式,尤其在错综复杂的社交,物流,金融风控行业效果更为明显。

    百花齐放的图数据库,有Operational 图数据库、RDF图数据库、多模式图数据、分析及大图数据库,图数据库的关注度越来越多,并且大都是有持续在更新。

    1.图数据类型
    1). 同构图:图中的节点类型与关系类型都仅有1种,如万维网
    2). 异构图:图中的节点类型与关系类型都多余1种,关系复杂,更贴近现实
    3). 属性图:相对异构图,对数据添加属性(标签与属性)
    4). 非显示图:数据之间没有显示地定义关系。

    2.图的应用例:
    1). 社交网络(人与人)
    2). 电子购物(人与物)
    3). 化学分子(元素与元素)
    4). 交通网络(站点之间)
    5). 电路设计图(元器件间)

    3.GNN的分类任务:
    * 节点分类:如通过引用网络对论文节点分类
    * 边分类及预测:如预测社交网络中的2人关系,并进行推荐
    * 图分类、表示、生成任务:如药物分子的分类,酶的分类等

    总结

    本次分享回顾了关于图的基本概述以及用于描述图的最基本的属性。下一篇文章我们将给出详细的Python 示例,从代码的角度深入理解图的定义、图的存储和图的性质:

    结束

    更多内容请关注从今天开始种树
    关注知识图谱与大数据公众号,获取更多内容。
    在这里插入图片描述

    展开全文
  • 图神经网络GNN 原理 详解 (一)

    千次阅读 多人点赞 2020-03-30 18:06:31
    图神经网络(GNN) 一.背景 图神经网络的概念首先由 Gori 等人(2005)[16] 提出,并由 Scarselli 等人(2009)[17] 进一步阐明。这些早期的研究以迭代的方式通过循环神经架构传播邻近信息来学习目标节点的表示,...

    图神经网络(GNN)

    一.背景

    图神经网络的概念首先由 Gori 等人(2005)[16] 提出,并由 Scarselli 等人(2009)[17] 进一步阐明。这些早期的研究以迭代的方式通过循环神经架构传播邻近信息来学习目标节点的表示,直到达到稳定的固定点。该过程所需计算量庞大,而近来也有许多研究致力于解决这个难题。在本文中,图神经网络代表的是所有用于图数据的深度学习方法。
    在这里插入图片描述
    受到卷积网络在计算机视觉领域所获巨大成功的激励,近来出现了很多为图数据重新定义卷积概念的方法。这些方法属于图卷积网络(GCN)的范畴。Bruna 等人(2013)提出了关于图卷积网络的第一项重要研究,他们基于谱图论(spectral graph theory)开发了一种图卷积的变体。自此,基于谱的图卷积网络不断改进、拓展、进阶。由于谱方法通常同时处理整个图,并且难以并行或扩展到大图上,基于空间的图卷积网络开始快速发展

    二.图的概念和基础

    2.1 图论介绍

    图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。在这里插入图片描述
    世界中很多的信息之间的联系,都可以使用图这种抽象的数学方式来进行表示,如下就是表示互联网之间关系的连接图。
    在这里插入图片描述

    2.2 图论基本研究对象-----图

    图(Graph)是表示物件与物件之间的关系的数学对象,是图论的基本研究对象。一个不带权图中若两点不相邻,邻接矩阵相应位置为0,对带权图(网),相应位置为∞。
    对于一个拥有n个顶点的无向连通图,它的边数一定多于n-1条。若从中选择n-1条边,使得无向图仍然连通,则由n个顶点及这 n-1条边(弧)组成的图被称为原无向图的生成树。

    2.3 图的定义

    二元组的定义

    图G是一个有序二元组(V,E),其中V称为顶集(Vertices Set),E称为边集(Edges set),E与V不相交。它们亦可写成V(G)和E(G)。
    E的元素都是二元组,用(x,y)表示,其中x,y∈V。

    三元组的定义

    图G是指一个三元组(V,E,I),其中V称为顶集,E称为边集,E与V不相交;I称为关联函数,I将E中的每一个元素映射到在这里插入图片描述 。如果e被映射到(u,v),那么称边e连接顶点u,v,而u,v则称作e的端点,u,v此时关于e相邻。同时,若两条边i,j有一个公共顶点u,则称i,j关于u相邻。

    2.4 分类

    有/无向图

    如果给图的每条边规定一个方向,那么得到的图称为有向图。在有向图中,与一个节点相关联的边有出边和入边之分。相反,边没有方向的图称为无向图。在这里插入图片描述

    单图

    一个图如果任意两顶点之间只有一条边(在有向图中为两顶点之间每个方向只有一条边);边集中不含环,则称为单图。

    三.GNN(基于循环结构) 的理论基础------不懂点理论

    要想搞懂GNN,那就必须知道什么是不动点理论。

    GNN的理论基础是不动点(the fixed point)理论,这里的不动点理论专指巴拿赫不动点定理(Banach’s Fixed Point Theorem)

    3.1 巴拿赫不动点定理

    定义

    巴拿赫不动点定理,又称为压缩映射定理或压缩映射原理,是度量空间理论的一个重要工具。它保证了度量空间的一定自映射的不动点的存在性和唯一性,并提供了求出这些不动点的构造性方法。这个定理是以斯特凡·巴拿赫命名的,他在1922年提出了这个定理。

    定理内容

    设(X,d)为非空的完备度量空间。设T:X→X为X上的一个压缩映射,也就是说,存在一个非负的实数q<1,使得对于所有X内的x和y,都有: [1]

    那么映射T在X内有且只有一个不动点x(这就是说,Tx=x)。更进一步,这个不动点可以用以下的方法来求出:从X内的任意一个元素x0开始,并定义一个迭代序列xn=Txn-1,对于n= 1,2,3,……。这个序列收敛,且极限为x。以下的不等式描述了收敛的速率:
    在这里插入图片描述
    等价地:
    在这里插入图片描述

    在这里插入图片描述
    满足以上不等式的最小的q有时称为利普希茨常数。
    注意对于所有不同的x和y都有d(Tx,Ty) < d(x,y)的要求,一般来说是不足以保证不动点的存在的,例如映射T: [1,∞) → [1,∞),T(x) =x+ 1/x,就没有不动点。但是,如果空间X是紧的,则这个较弱的假设也能保证不动点的存在。
    当实际应用这个定理时,最艰难的部分通常是恰当地定义X,使得T实际上把元素从X映射到X,也就是说,Tx总是X的一个元素。

    在GNN中的操作

    首先我们用 F 表示若干个 f 堆叠得到的一个函数,也称为全局更新函数,那么图上所有结点的状态更新公式可以写成:

    在这里插入图片描述
    不动点定理指的就是,不论H0是什么,只要 F 是个压缩映射(contraction map),H0经过不断迭代都会收敛到某一个固定的点,我们称之为不动点。

    3.2 什么是压缩映射?

    定义

    设(X, ρ)为距离空间,T是X 到 X中的映射,如果存在数a (0<a<1),使得对所有的x,y∈X都有ρ(Tx, Ty)≤a*ρ(x, y),则称T是压缩映射,压缩映射也称为利普希茨映射。

    那么既然 f 是由 神经网络实现的,如何保证它是一个压缩映射呢?

    3.3 用前馈神经网络实现 压缩映射

    一种实现方法可以是把每个邻居结点的特征、隐藏状态、每条相连边的特征以及结点本身的特征简单拼接在一起,在经过前馈神经网络后做一次简单的加和。
    在这里插入图片描述
    那我们如何保证 f 是个压缩映射呢,其实是通过限制 fH 的偏导数矩阵的的惩罚项大小,这是通过一个对雅可比矩阵(Jacobian Matrix)的惩罚项(Penalty)来实现的。

    什么是雅克比矩阵?

    在这里插入图片描述
    在这里插入图片描述
    (图片来自网络)

    四.GNN的训练流程

    3.1 流程 步骤

    在这里插入图片描述
    (图片来自网络)

    从将图输入到GNN中到得到输出结果 主要可以分为两步:第一步是传播(propagation)过程,即节点表示随时间的更新过程;第二步是输出(output)过程,即根据最终的节点表示得到目标输出(如每个节点的类别)的过程。在这两步中,传播过程要更为重要,其设计也要受到一定的约束(要保证整个图上的状态映射是一个压缩映射(contraction map))。在展开图中,传播过程对应于从 [公式][公式]的更新过程(注意, [公式] 并不是确定的,而是对应于整个图的状态到达不动点的时刻),不同时间步的连接则由图中的连接来决定(可以是有向的,也可以是无向的)。

    传播过程

    在这里插入图片描述

    输出过程

    在这里插入图片描述

    GNN 的训练

    GNN的学习是通过Almeida-Pineda算法实现的。该算法的特点在于,首先通过传播过程使整个图收敛,然后在收敛解上计算相应的梯度。这样,我们就无需存储梯度计算过程所需的中间状态了。但是,必须保证整个图的映射是压缩的,以保证传播过程有一个收敛解。
    在这里插入图片描述

    五. GNN 的 不足

    实验结果表明GNN对于结构化数据的建模十分有效,但仍然存在着诸多的不足。

    1. 对于不动点隐藏状态的更新是十分低效的
    2. GNN在迭代的过程中用相同的参数,然而大多标准网络在不同的网络层数使用不同的参数
    3. 在原始的GNN中存在着一些无法有效建模的边缘信息特征。例如,在知识图谱中边代表这关系类型,不同边缘的消息传递应该根据他们的类型有所不同。怎么样去学习边缘的隐藏状态也是一个重要的问题
    4. 如果把重点放在节点的表示而不是图上,就不适合使用不动点,因为不动点上表示的分布会变得非常平滑,且每个节点的信息量也会减少。
    展开全文
  • 入门图神经网络的好资源,了解GNN的基本原理,训练方法,以及其各种变体的应用。通俗易懂,讲解全面。入门图神经网络的好资源,了解GNN的基本原理,训练方法,以及其各种变体的应用。通俗易懂,讲解全面。
  • 长文详解图神经网络

    千次阅读 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论文解读

    
    整理不易,还望给个在看!
    
    展开全文
  • 最通俗易懂的图神经网络(GCN)原理详解

    万次阅读 多人点赞 2019-12-05 16:39:10
    gcn原文(Multi-layer Graph Convolutional Network (GCN) with first-order filters) GCN问世已经有几年了(2016年就诞生了),但是这两年尤为火爆。本人愚钝,一直没能搞懂这个GCN为何物,最开始是看清华写的一篇...

    gcn原文(Multi-layer Graph Convolutional Network (GCN) with first-order filters)

    GCN问世已经有几年了(2016年就诞生了),但是这两年尤为火爆。本人愚钝,一直没能搞懂这个GCN为何物,最开始是看清华写的一篇三四十页的综述,读了几页就没读了;后来直接拜读GCN的开山之作,也是读到中间的数学部分就跪了;再后来在知乎上看大神们的讲解,直接被排山倒海般的公式——什么傅里叶变换、什么拉普拉斯算子等等,给搞蒙了,越读越觉得:“哇这些大佬好厉害,哎我怎么这么菜!”。

    就这么反反复复,尝试一次放弃一次,终于慢慢有点理解了,慢慢从那些公式的里跳了出来,看到了全局,也就慢慢明白了GCN的原理。今天,我就记录一下我对GCN“阶段性”的理解。

    GCN的概念首次提出于ICLR2017(成文于2016年):

    一、GCN 是做什么的

    在扎进GCN的汪洋大海前,我们先搞清楚这个玩意儿是做什么的,有什么用。

    深度学习一直都是被几大经典模型给统治着,如CNN、RNN等等,它们无论再CV还是NLP领域都取得了优异的效果,那这个GCN是怎么跑出来的?是因为我们发现了很多CNN、RNN无法解决或者效果不好的问题——图结构的数据。

    回忆一下,我们做图像识别,对象是图片,是一个二维的结构,于是人们发明了CNN这种神奇的模型来提取图片的特征。CNN的核心在于它的kernel,kernel是一个个小窗口,在图片上平移,通过卷积的方式来提取特征。这里的关键在于图片结构上的平移不变性:一个小窗口无论移动到图片的哪一个位置,其内部的结构都是一模一样的,因此CNN可以实现参数共享。这就是CNN的精髓所在。

    再回忆一下RNN系列,它的对象是自然语言这样的序列信息,是一个一维的结构,RNN就是专门针对这些序列的结构而设计的,通过各种门的操作,使得序列前后的信息互相影响,从而很好地捕捉序列的特征。

    上面讲的图片或者语言,都属于欧式空间的数据,因此才有维度的概念,欧式空间的数据的特点就是结构很规则。但是现实生活中,其实有很多很多不规则的数据结构,典型的就是图结构,或称拓扑结构,如社交网络、化学分子结构、知识图谱等等;即使是语言,实际上其内部也是复杂的树形结构,也是一种图结构;而像图片,在做目标识别的时候,我们关注的实际上只是二维图片上的部分关键点,这些点组成的也是一个图的结构。

    图的结构一般来说是十分不规则的,可以认为是无限维的一种数据,所以它没有平移不变性。每一个节点的周围结构可能都是独一无二的,这种结构的数据,就让传统的CNN、RNN瞬间失效。所以很多学者从上个世纪就开始研究怎么处理这类数据了。这里涌现出了很多方法,例如GNN、DeepWalk、node2vec等等,GCN只是其中一种,这里只讲GCN,其他的后面有空再讨论。

    GCN,图卷积神经网络,实际上跟CNN的作用一样,就是一个特征提取器,只不过它的对象是图数据。GCN精妙地设计了一种从图数据中提取特征的方法,从而让我们可以使用这些特征去对图数据进行节点分类(node classification)、图分类(graph classification)、边预测(link prediction),还可以顺便得到图的嵌入表示(graph embedding),可见用途广泛。因此现在人们脑洞大开,让GCN到各个领域中发光发热。

    二、GCN 长啥样,吓人吗?

    GCN的公式看起来还是有点吓人的,论文里的公式更是吓破了我的胆儿。但后来才发现,其实90%的内容根本不必理会,只是为了从数学上严谨地把事情给讲清楚,但是完全不影响我们的理解,尤其对于我这种“追求直觉,不求甚解”之人。

    下面进入正题,我们直接看看GCN的核心部分是什么样子:

    假设我们手头有一批图数据,其中有N个节点(node),每个节点都有自己的特征,我们设这些节点的特征组成一个N×D维的矩阵X,然后各个节点之间的关系也会形成一个N×N维的矩阵A,也称为邻接矩阵(adjacency matrix)。X和A便是我们模型的输入。

    GCN也是一个神经网络层,它的层与层之间的传播方式是:

    这个公式中:

    • A波浪=A+I,I是单位矩阵
    • D波浪是A波浪的度矩阵(degree matrix),公式为
    • H是每一层的特征,对于输入层的话,H就是X
    • σ是非线性激活函数

    我们先不用考虑为什么要这样去设计一个公式。我们现在只用知道:

    这个部分,是可以事先算好的,因为D波浪由A计算而来,而A是我们的输入之一。

    所以对于不需要去了解数学原理、只想应用GCN来解决实际问题的人来说,你只用知道:哦,这个GCN设计了一个牛逼的公式,用这个公式就可以很好地提取图的特征。这就够了,毕竟不是什么事情都需要知道内部原理,这是根据需求决定的。

    为了直观理解,我们用论文中的一幅图:

    上图中的GCN输入一个图,通过若干层GCN每个node的特征从X变成了Z,但是,无论中间有多少层,node之间的连接关系,即A,都是共享的。

    假设我们构造一个两层的GCN,激活函数分别采用ReLU和Softmax,则整体的正向传播的公式为:

    最后,我们针对所有带标签的节点计算cross entropy损失函数:

    就可以训练一个node classification的模型了。由于即使只有很少的node有标签也能训练,作者称他们的方法为半监督分类。

    当然,你也可以用这个方法去做graph classification、link prediction,只是把损失函数给变化一下即可。

    三、GCN 为什么是这个样子

    我前后翻看了很多人的解读,但是读了一圈,最让我清楚明白为什么GCN的公式是这样子的居然是作者Kipf自己的博客:http://tkipf.github.io/graph-convolutional-networks/ 推荐大家一读。

    作者给出了一个由简入繁的过程来解释:

    我们的每一层GCN的输入都是邻接矩阵A和node的特征H,那么我们直接做一个内积,再乘一个参数矩阵W,然后激活一下,就相当于一个简单的神经网络层嘛,是不是也可以呢?

    实验证明,即使就这么简单的神经网络层,就已经很强大了。这个简单模型应该大家都能理解吧,这就是正常的神经网络操作。

    但是这个简单模型有几个局限性:

    • 只使用A的话,由于A的对角线上都是0,所以在和特征矩阵H相乘的时候,只会计算一个node的所有邻居的特征的加权和,该node自己的特征却被忽略了。因此,我们可以做一个小小的改动,给A加上一个单位矩阵 I ,这样就让对角线元素变成1了。
    • A是没有经过归一化的矩阵,这样与特征矩阵相乘会改变特征原本的分布,产生一些不可预测的问题。所以我们对A做一个标准化处理。首先让A的每一行加起来为1,我们可以乘以一个D的逆,D就是度矩阵。我们可以进一步把D的拆开与A相乘,得到一个对称且归一化的矩阵 :。

    通过对上面两个局限的改进,我们便得到了最终的层特征传播公式:

    其中

    公式中的与对称归一化拉普拉斯矩阵十分类似,而在谱图卷积的核心就是使用对称归一化拉普拉斯矩阵,这也是GCN的卷积叫法的来历。原论文中给出了完整的从谱卷积到GCN的一步步推导,我是看不下去的,大家有兴趣可以自行阅读。

    四、GCN 有多牛

    在看了上面的公式以及训练方法之后,我并没有觉得GCN有多么特别,无非就是一个设计巧妙的公式嘛,也许我不用这么复杂的公式,多加一点训练数据或者把模型做深,也可能达到媲美的效果呢。

    但是一直到我读到了论文的附录部分,我才顿时发现:GCN原来这么牛啊!

    为啥呢?

    因为即使不训练,完全使用随机初始化的参数W,GCN提取出来的特征就以及十分优秀了!这跟CNN不训练是完全不一样的,后者不训练是根本得不到什么有效特征的。

    我们看论文原文:

    然后作者做了一个实验,使用一个俱乐部会员的关系网络,使用随机初始化的GCN进行特征提取,得到各个node的embedding,然后可视化:

    可以发现,在原数据中同类别的node,经过GCN的提取出的embedding,已经在空间上自动聚类了。

    而这种聚类结果,可以和DeepWalk、node2vec这种经过复杂训练得到的node embedding的效果媲美了。

    说的夸张一点,比赛还没开始,GCN就已经在终点了。看到这里我不禁猛拍大腿打呼:“NB!”

    还没训练就已经效果这么好,那给少量的标注信息,GCN的效果就会更加出色。

    作者接着给每一类的node,提供仅仅一个标注样本,然后去训练,得到的可视化效果如下:

    这是整片论文让我印象最深刻的地方。

    其他:

    1. 对于很多网络,我们可能没有节点的特征,这个时候可以使用GCN吗?答案是可以的,如论文中作者对那个俱乐部网络,采用的方法就是用单位矩阵 I 替换特征矩阵 X。
    2. 我没有任何的节点类别的标注,或者什么其他的标注信息,可以使用GCN吗?当然,就如前面讲的,不训练的GCN,也可以用来提取graph embedding,而且效果还不错。
    3. GCN网络的层数多少比较好?论文的作者做过GCN网络深度的对比研究,在他们的实验中发现,GCN层数不宜多,2-3层的效果就很好了

    补充图的一些基本知识

    图(Graph)

          图用G=(V, E)表示,V中元素为顶点(vertex),E中元素为边(edge)。图中边为无序对时为无向图,为有序对时为有向图。
          以下为一个无向图的例子。
    在这里插入图片描述

    邻居(Neighborhood)

          顶点 vi 的邻居 N(i) :
    在这里插入图片描述
          无向图中,如果顶点vi是顶点vj的邻居,那么顶点vj也是顶点vi的邻居。

    度矩阵(Degree)

         度矩阵是对角阵,对角上的元素为各个顶点的度。顶点vi的度表示和该顶点相关联的边的数量。
         无向图中顶点vi的度d(vi)=N(i)。

    在这里插入图片描述
         有向图中,顶点vi的度分为顶点vi的出度和入度,即从顶点vi出去的有向边的数量和进入顶点vi的有向边的数量。

    邻接矩阵(Adjacency)

         邻接矩阵表示顶点间关系,是n阶方阵(n为顶点数量)。
         邻接矩阵分为有向图邻接矩阵和无向图邻接矩阵。无向图邻接矩阵是对称矩阵,而有向图的邻接矩阵不一定对称。
    在这里插入图片描述
    注意,对于有向图,vivj是有方向的,即vi -> vj 。

    • Figure 2.1 的度矩阵和邻接矩阵如下:
      在这里插入图片描述
    • 下图中无向图G5 和有向图G6 的邻接矩阵分别为A1 和A2 。
      在这里插入图片描述

    参考:https://mp.weixin.qq.com/s/DJAimuhrXIXjAqm2dciTXg

    https://blog.csdn.net/luzaijiaoxia0618/article/details/104718146/

    展开全文
  • 从数据结构到算法:图网络方法初探 论文《Graph Neural Networks: A Review of Methods and Applications》 木牛马论文阅读笔记... 文章目录图神经网络(Graph Neural Networks,GNN)1. GNN起源1.1 动..
  • CNN卷积神经网络原理详解(上)

    万次阅读 多人点赞 2019-10-18 23:59:17
    CNN卷积神经网络原理详解(上)前言卷积神经网络的生物背景我们要让计算机做什么?卷积网络第一层全连接层训练 前言 卷积网络(convolutional network),也叫作卷积神经网络(convolutional neural network,CNN),是...
  • 本ppt详细介绍了卷积神经网络的起源背景、算法原理、算法的执行过程、以及CNN的应用场景
  • 《深入浅出图神经网络》GNN原理解析☄学习笔记(一)图的概述 文章目录《深入浅出图神经网络》GNN原理解析☄学习笔记(一)图的概述图的基本定义图的基本类型邻居和度子图与路径图的存储与遍历邻接矩阵和关联矩阵图...
  • 机器学习-预测之BP神经网络模型原理及实战

    万次阅读 多人点赞 2019-03-17 15:14:39
    BP神经网络模型
  • 入门图神经网络的好资源,了解GNN的基本原理,训练方法,以及其各种变体的应用。通俗易懂,讲解全面。入门图神经网络的好资源,了解GNN的基本原理,训练方法,以及其各种变体的应用。通俗易懂,讲解全面。
  • 该文档详细介绍了BP 神经网络算法原理以及详细推导流程,简洁明了,容易看懂,非常适合BP神经网络的初学者学习。
  • 【2020 图神经网络综述】A Comprehensive Survey on Graph Neural Networks 文章转载于好我的朋友:大家可以关注他的博客: Memory逆光 博客地址:...
  • 图像识别技术原理神经网络的图像识别技术

    万次阅读 多人点赞 2019-03-03 19:44:58
    图像识别技术是信息时代的一门...简单分析了图像识别技术的引入、其技术原理以及模式识别等,之后介绍了神经网络的图像识别技术和非线性降维的图像识别技术及图像识别技术的应用。从中可以总结出图像处理技术的应用...
  • 摘要 近年来,由于神经网络在模式识别和数据挖掘领域的应用和其易用性,神经网络已获得了巨大的普及。...在本文中,我们将研究图和GNN的定义和基础,并了解图神经网络的一些最新应用。 一、什么是
  • 【机器学习】RBF神经网络原理与Python实现

    万次阅读 多人点赞 2018-11-24 19:51:20
    【机器学习】RBF神经网络原理与Python实现一、LSSVM数学原理1. 感知机2. SVM3. LSSVM4. LSSVM与SVM的区别二、LSSVM的python实现参考资料 一、LSSVM数学原理 1. 感知机 SVM是从感知机发展而来。假设有m个训练样本{...
  • 人工神经网络原理图解

    千次阅读 2018-12-20 17:19:41
    神经网络是一种模仿动物或人类大脑的设计思路。虽然计算机有超强的计算能力但是只能线性的计算或处理简单的任务,并不能完成完成复杂的任务或者像人类一样模糊的认知(计算机只能做到0或1的绝对认知),比如这个动物...
  • 图神经网络/GCN 入门

    千次阅读 2019-11-12 22:18:46
    跳出公式,看清全局,图神经网络(GCN)原理详解 GCN (Graph Convolutional Network) 图卷积网络解析 Graph Convolution Network图卷积网络(一)训练运行与代码概览 Graph Convolution Network图卷积网络(二)数据...
  • 从图嵌入算法到图神经网络

    千次阅读 多人点赞 2019-08-13 15:12:25
    图神经网络,广泛应用于社交关系、知识图谱、推荐系统、蛋白质分子建模,同样源自于对传统领域的创新,它的前身是图嵌入算法;而图嵌入算法又以图数据作为载体。这一关系,将贯穿本文始末,成为我们
  • BP神经网络原理以及demo示例

    千次阅读 2017-04-02 14:23:09
    这几天突然对神经网络有兴趣了,就花了两三天的时间学习了一下BP神经网络。开门见山,先把github上的代码demo放上去,先了解一下他们是如何构建一个BP神经网络的。 然后就是一些我对BP神经网络的算法的一些总结。 #-...
  • 神经网络原理

    千次阅读 2018-09-17 10:57:39
    神经网络原理 神经网络的主要用途在于分类,那么整个神经网络分类的原理是怎么样的?我们还是围绕着损失、优化这两块去说。神经网络输出结果如何分类? 神经网络解决多分类问题最常用的方法是设置n个输出节点,...
  • 图神经网络综述】一文道尽GNN原理、框架和应用

    千次阅读 多人点赞 2020-08-05 00:06:03
    【2020 图神经网络综述】A Comprehensive Survey on Graph Neural Networks1. 摘要:2. 简介:2.1 为什么要用图表示数据:2.2 GNN与network embedding:2.3 GNN与Graph Kernel:2.4 一些符号表示: 论文地址:...
  • 所用的方法是梯度下降(Gradient descent):通过使loss值向当前点对应梯度的反方向不断移动,来降低loss。一次移动多少是由学习速率(learning rate)来控制的。
  • 一文看懂神经网络工作原理

    千次阅读 2018-12-14 14:10:52
    一文看懂神经网络工作原理     https://www.toutiao.com/a6634049434629980680/   现在谈人工智能已经绕不开“神经网络”这个词了。人造神经网络粗线条地模拟人脑,使得计算机能够从数据中学习。 机器学习...
  • 什么是图神经网络

    万次阅读 多人点赞 2020-08-05 10:25:32
    2019年可以说是图神经网络元年。01 什么是图神经网络?1. 图和属性图要了解图神经网络,首先要了解图。图是由节点和边组成的,如下图所示。一般图中的节点表示实体对象(比如一个用户、一件商品、一辆车、一张银行卡...
  • 图神经网络 | (6) 图分类(SAGPool)实战

    千次阅读 多人点赞 2020-02-03 17:06:54
    近期买了一本图神经网络的入门书,最近几篇博客对书中的一些实战案例进行整理,具体的理论和原理部分可以自行查阅该书,该书购买链接:《深入浅出的图神经网络》。 该书配套代码 本节我们通过代码来实现基于自注意...
  • YOLO—神经网络原理

    万次阅读 2018-08-25 10:19:47
    YOLO(You Only Look Once: Unified, Real-Time Object Detection),是Joseph Redmon和Ali Farhadi等人于2015年提出的基于单个神经网络的目标检测系统。在2017年CVPR上,Joseph Redmon和Ali Farhadi又发表的YOLO 2...
  • 图神经网络资源大集合~快来打包带走

    千次阅读 多人点赞 2020-10-17 22:14:21
    2020年最新图神经网络相关的论文 & 书籍 & 代码& 视频课程等学习资源集合书 & 综述1.《Deep Learning on Graphs》这本书是...
  • 《深入浅出图神经网络》GNN原理解析☄学习笔记(三)卷积神经网络 文章目录《深入浅出图神经网络》GNN原理解析☄学习笔记(三)卷积神经网络卷积与池化信号处理中的卷积单通道卷积多通道卷积池化卷积神经网络卷积...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 78,443
精华内容 31,377
关键字:

图神经网络原理