精华内容
下载资源
问答
  • 图神经网络(Graph neural networks)综述

    万次阅读 多人点赞 2019-03-12 09:52:20
    论文链接:Graph Neural Networks:A Review of Methods and Applications Abstract:(Graph)数据包含着十分丰富的...图网络(Graph neural networks)是一种链接主义模型,它靠中节点之间的信息传递来捕捉...

    论文链接:Graph Neural Networks: A Review of Methods and Applications

    Abstract图(Graph)数据包含着十分丰富的关系型信息。从文本、图像这些非结构化数据中进行推理学习,例如句子的依赖树、图像的场景图等,都需要图推理模型。图网络(Graph neural networks)是一种链接主义模型,它靠图中节点之间的信息传递来捕捉图中的依赖关系。近年来,图卷积网络(Graph Convolutional network)和门控图网络(Gated graph neural network)在众多领域取得了重大的成功。

    Introduction

          图是一种结构化数据,它由一系列的对象(nodes)和关系类型(edges)组成。作为一种非欧几里得形数据,图分析被应用到节点分类、链路预测和聚类等方向。图网络是一种基于图域分析的深度学习方法,对其构建的基本动机论文中进行了分析阐述。

    卷积神经网络(CNN)是GNN起源的首要动机。CNN有能力去抽取多尺度局部空间信息,并将其融合起来构建特征表示。CNN只能应用于常规的欧几里得数据上(例如2-D的图片、1-D的文本),这些形式的数据可以被看成是图的实例化。随着对GNN和CNN的深入分析,发现其有三个共同的特点:(1)局部连接(2)权值共享(3)多层网络。这对于GNN来说同样有重要的意义。(1)局部连接是图的最基本的表现形式。(2)权值共享可以减少网络的计算量。(3)多层结构可以让网络捕获不同的特征。然而,从CNN到GNN的转变还面临这另一个问题,难以定义局部卷积核和池化操作。如下图所示:

    这也阻碍了CNN由传统欧几里得空间向非欧几里得空间的扩展。

     

    这另一个动机就是图表示(graph embedding),即如何将图中的节点、边和子图以低维向量的形式表现出来。受启发于表示学习(representation learning)和词嵌入(word embedding),图嵌入技术得到了长足的发展。DeepWalk基于表示学习,被认为是第一种图嵌入技术模型。还有基于SkipGram模型的random walk。以及node2vec,LINE和TADW等。然而以上的这些模型存在两个缺点:(1)图中节点之间不存在任何的参数共享,导致计算量与节点数量呈线性增长。(2)图嵌入技术缺乏泛化能力,导致不能处理动态图或推广至新的图。

    GNN相对于传统的神经网络来说也是存在优势的。标准的CNN和RNN网络不能处理图输入这种非顺序排序的特征表示。换句话说,图中节点的排序是没有规律可言的。如果非要用传统的CNN和RNN来处理图数据的话,只能遍历图中节点所有可能的出现顺序作为模型的输入,这对模型的计算能力来说是难以承受的。为了解决这个问题,GNN分别在每个节点上传播,忽略了节点之间输入的顺序。换而言之,GNN的输出是不随节点的输入顺序为转移的。另外,图中的边表示两个节点之间的依赖关系。在传统的神经网络中,这种依赖关系只能通过节点的特征表示来体现。GNN可以依赖周围的状态来更新节点的状态。最后是推理能力,与人类从日常经验中获取推理能力相似,GNN能够从非结构化数据(例如:场景图片、故事片段等)中生成图。与之对比的是,传统CNN和RNN能够从大量经验数据中生成完整的图片和文档,但并不能学习出这种推理图(reasoning graph)。

    论文的主要贡献有:

    • 提出一种统一的表现形式来展示不同模型中的不同传播步骤。
    • 详细介绍了几种主流方法在不同场景中的应用。
    • GNN面临的over-smoothing、scaling problems、dynamic graph和 non –structural data问题做出分析和展望。

    Model

    Graph Neural Networks

    在图中,每个节点的定义是由该节点的特征和相关节点来共同表示的。GNN的目标是训练出一个state embedding函数hv,该函数包含了每个节点的领域信息。

             

    hv是节点v的向量化表示,它可以被用来去预测该节点的输出ov(例如节点的标签)。f(*)被称为local transition function,它被所有的节点共享,并根据输入的领域信息来更新节点的状态。xv是节点v的特征表示,xco[v]是v节点上边的特征表示,hne[v]是该节点的状态,xne[v] 是节点v周围节点的特征表示。

    g(*)被称为local output function,它是用来产生节点的输出的。

                 

    H、O、X、XN为其推广形式,代表图中的所有对象的堆叠形式。

    Banach的fixed point提出以后,GNN中state的迭代计算过程可以表示如下:

                  

    Ht代表H的第t-th的状态,H(0)代表其动态方程的初始状态。

     对于一个GNN网络来说,其训练过程就是学习出函数f(*)和g(*)tv代表其一个有监督的节点,GNN的优化过程为:

                

    P代表图中所有有监督节点的数量。优化是基于梯度下降算法的,并且被表示如下:

    1. h被公式1迭代更新,直到T时间步。H(T)=H。
    2. 权重W的梯度通过loss计算得出。
    3. 进行梯度更新。

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

    1. 对于不动点隐藏状态的更新是十分低效的。如果放松对不动点的假设,论文中提出一种多层GNN可以得到节点及其邻域的稳定表示。
    2. GNN在迭代的过程中用相同的参数,然而大多标准网络在不同的网络层数使用不同的参数,
    3. 在原始的GNN中存在着一些无法有效建模的边缘信息特征。例如,在知识图谱中边代表这关系类型,不同边缘的消息传递应该根据他们的类型有所不同。怎么样去学习边缘的隐藏状态也是一个重要的问题。
    4. 如果把重点放在节点的表示而不是图上,就不适合使用不动点,因为不动点上表示的分布会变得非常平滑,且每个节点的信息量也会减少。

    Graph Types

       在原始的GNN中,模型的输入信息包含有监督的节点信息和无向的边。近年来,诸多类型的变种也层出不穷。

    Directed Graphs

       这第一种类型的变种就是,有向图(directed graphs)。传统的无向边可以看作是两个有向边组成的,表明两个节点之间存在着关系。然而,有向边相对与无向边来说能够表达更为丰富的信息。例如,在知识图谱中两个实体被一条边链接,但是第一个实体是第二个实体的父类,这就要求模型以不同的形式来对待父类和子类的信息传播过程。ADGPM模型用两种权重举证WP和WC来表达更加精确的结构信息。

         

    DA分别代表规范化的父类和子类的邻接矩阵。

    Heterogeneous Graphs

         在异构图中,包含有不同类型的几种节点。表现不同类型节点最简单的形式是,将类型用one-hot向量表示,然后与原始节点的特征向量进行拼接。GraphInception模型将metapath(是一种路径游走方式,与之对应的是完全随机选择游走)的概念引入到了异构图的传播中。我们可以对邻近节点进行分类,根据其节点的类型和其距离。对于每个邻近节点群,GraphInception将它作为一个同构图中的子图,并将来自于不同同构图的传播结果连接起来视为一个集合节点来表示。

     

    Graphs with Edge Information

      在图中,边也蕴含着丰富的信息,例如权重和边的类型等。有两种表示图的方式:(1)两个节点之间的边切割开成两条边,然后将边也转化成节点。(2)在传播过程中,不同的边上有不同的权值矩阵。

    Propagation Types

         在模型中,信息的传播步骤和输出步骤是获得节点或者边隐含状态的关键步骤。不同变种的GNN的聚合函数(用来聚合图中所有点的邻域信息,产生一个全局性的输出)和节点状态更新函数如下图所示:

    ConvolutionGCN将卷积操作应用到图结构的数据上,主要分为Spectral method 和 Spatial Method 两种方法。其目的都是对节点以及节点的邻近节点进行信息收集。

    Gate使用GRU或者是LSTM这种带有门控机制的网络,来增强信息在图结构中的长期的传播。

    AttentionGAT是一种图注意网络,它将注意力机制融入到了图传播的步骤中。GAT计算每个节点的隐藏状态,通过将 “attention” 机制应用到邻近节点上。

    Skip connection研究发现更深的网络层数可以帮助网络在节点的邻域节点上获取到更多的信息。但通过实验也发现深层网络也会在网络传播中带来噪声信息,随着网络层数的加深,网络还会出现退化。基于图像领域的启发,residual network和highway network 这些skip 模型能够有效的处理这一问题。

     

    Training Methods

    论文中还介绍了几种GNN的训练方法。比如GraphSAGE从节点的邻域聚合信息。FastGCN采用样本采样方法替代节点的所有邻域信息。这些训练方法,都使得模型的训练效率更加的高效。

     

    General Frameworks

    除了几种不同的GNN变种模型在论文中被介绍,几种图框架也被提出用来整合不同模型方法至单一框架中。MPNN(message passing neural network):统一了几种图神经网络和图卷积网络。NLNN(non-local neural network):统一了几种self-attention方法的图模型。GN(graph network):统一了包括MPNN、NLNN、和其他几种图网络模型。

    Message Passing Neural Networks

          MPNN网络包含两个阶段,message passing阶段和readout阶段。Message passing阶段在时间T步内发生,它被定义为message函数Mt和节点更新函数Ut。在时间T步内的节点隐状态通过Mt和Ut来产生t+1时刻节点的隐状态。

                             

    evw代表节点v到节点w上边的特征。Readout阶段可以被定义为对整个图计算特征向量。

                     

    T代表所有的时间步骤。具体的函数设置和方法选择可以进行调整,例如GGNN。

         

    Non-local Neural Networks

    NLNN网络被提出用来去捕获深度神经网络中存在的长期依赖问题。Non-local可以被推广成:

             

    i是输出位置的索引,j代表图中所有可能出现的位置的索引。函数f(*)被用来计算i和j节点之间的距离。g(*)代表输入节点隐状态的一个变化。最后计算出来的值被正则化。

    Graph Networks

    图网络的定义:一个图被定义成一个三元组的形式G=(U,H,E)。U代表一个全局属性,H代表图中所有节点的属性,E代表图中所有发射节点、接收节点和它们之间边的属性。

    图的设计有三个基本原则:

    1. Flexible representation :图中节点和边的属性可以被任何形式的数据来表示,不过比较常用的还是以向量或者是张量的形式来表达的。
    2. Gonfigurable with-block structure:GN中每个块都是可配置的,可以是不同的设置组合。
    3. Composable multi-block architectures:GN可以被组合成复杂的体系结构,这些架构如下图所示:

    APPLICATIONS

    图网络被广泛的应用于包括监督学习、半监督学习、无监督学习和强化学习等方向。论文中从三个不同的场景来分别阐述图网络的应用。(1)结构化场景:数据包含有很明确的关系结构,如物理系统、分子结构和知识图谱。(2)非结构化场景:数据不包含明确的关系结构,例如文本和图像等领域。(3)其他应用场景:例如生成式模型和组合优化模型。各个领域图网络的应用细节如下图所示:

     

    Structural Scenarios

         GNN被广泛的应用到包括应用物理、分子化学和知识图谱等领域。

    Non-structural Scenarios

       Image:在图像分类中,每个类别被视为图中的一个节点。

          Text在文本分类中,可以将文档或者句子看作成图中的一个节点(异构图)。然后使用文本GCN学习文档或者句子的向量化表示,作为节点的原始输入。如果将句子中的每个单词看成是图中的节点的话,那么GNN可以被用来解决序列标注问题,例如词性标注或者是命名实体识别。图网络还被拓展至许多NLP任务上,例如关系抽取和时间抽取等。

     

    GNN还可以被应用到许多其他情景中去。

    OPEN PROBLEMS

    1. 浅层结构:目前GNN还只能在较浅层的网络上发挥优势,随着层数的加深,网络会出现退化。
    2. 动态图:目前大多方法只能应用在静态图上,对于动态图还没有特别好的解决方案。
    3. 非结构化场景:还没有一个通用的方法来合理的处理非结构化数据。
    4. 扩展性:将图网络应用于大规模数据上仍然面临着不小的困难。

     

     

    展开全文
  • exec函数0 前言1 为什么需要图神经网络?2 图神经网络是什么样子的?3 图神经网络的几个经典模型与发展4 无监督的节点表示学习(Unsupervised Node Representation)5 Graph Pooling 参考知乎:...

    参考知乎: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上面是一个对图神经网络比较简单直观的感受与理解,实际其背后的原理逻辑还是比较复杂的。

    展开全文
  • 图神经网络/GCN 入门

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

    跳出公式,看清全局,图神经网络(GCN)原理详解

    GCN (Graph Convolutional Network) 图卷积网络解析

    Graph Convolution Network图卷积网络(一)训练运行与代码概览
    Graph Convolution Network图卷积网络(二)数据加载与网络结构定义
    Graph Convolution Network图卷积网络(三)嵌入其他网络结构

    AAAI 2020:速读8篇图神经网络论文,附下载

    用GCN来做图像处理,怎么建立像素之间的边,以及边上的权重。

    图像处理(四)图像分割(2)测地距离Geodesic图割
    原文:Geodesic Matting: A Framework for Fast Interactive Image and video segmentation and matting
    算法原理:基于测地距离的图像分割属于一种图论的分割算法。图论分割算法:即把图像上的每个像素点当做图的顶点,图的每个顶点有四个邻接顶点(每个像素点有四个邻接像素点,除边界点),每两个邻接像素点用相应的边连接,边的长度与两个像素点间的相似度有关(测地距离),而非采用简单的欧式距离作为边长(相邻像素点间的欧式距离为1)

    基于图论的图像分割

    基于图论的分割方法

    此类方法把图像分割问题与图的最小割(min cut)问题相关联。首先将图像映射为带权无向图G=<V,E>,图中每个节点N∈V对应于图像中的每个像素,每条边∈E连接着一对相邻的像素,边的权值表示了相邻像素之间在灰度、颜色或纹理方面的非负相似度。而对图像的一个分割s就是对图的一个剪切,被分割的每个区域C∈S对应着图中的一个子图。而分割的最优原则就是使划分后的子图在内部保持相似度最大,而子图之间的相似度保持最小。基于图论的分割方法的本质就是移除特定的边,将图划分为若干子图从而实现分割。目前所了解到的基于图论的方法有GraphCut、GrabCut和Random Walk等。
    还有一篇2010年文献《Geodesic graph cut for interactive image segmentation》结合了graph cut 算法和测地距离分割算法的优点,把两种算法结合起来,可克服两种算法存在的缺陷。

    用图神经网络来处理图像

    NeurIPS 2020 | IGNN图卷积超分网络: 挖掘隐藏在低分辨率图像中的高清纹理
    在NeurIPS 2020中,南洋理工大学、商汤和哈工大研究员联合提出了跨尺度的图卷积超分网络IGNN。近些年来,Non-local方法利用同尺度的自相似性先验在图像复原任务中取得了一些突破,如图片去噪。但对于图像超分辨任务,相同低分辨率 (LR) 的相似图像块融合无法让网络直接感知更高分辨率 (HR) 的图像纹理。

    针对上述问题,本文利用图像内部纹理跨尺度多次复现的特性找到与LR图像块对应的k个HR图像块,并动态地构建了LR-HR块的连接图。 基于该连接图,IGNN利用图卷积自适应地融合k个HR图像块,从而使图像内部高清纹理信息在超分中得到充分利用。IGNN在五个公开数据集上的性能表现均有显著提升

    Cross-Modality Attention with Semantic Graph Embedding for Multi-Label Classification —AAAI2020

    摘要:多标签图像和视频分类是计算机视觉中最基本也是最具挑战性的任务。主要的挑战在于捕获标签之间的空间或时间依赖关系,以及发现每个类的区别性特征的位置。为了克服这些挑战,我们提出将语义图嵌入的跨模态注意力机制用于多标签分类。基于所构造的标签图,我们提出了一种基于邻接关系的相似图嵌入方法来学习语义标签嵌入,该方法显式地利用了标签之间的关系。在学习标签嵌入的指导下,生成我们新颖的跨模态注意力图。在两个多标签图像分类数据集(MS-COCO和NUS-WIDE)上的实验表明,我们的方法优于其他现有的方法。此外,我们在一个大的多标签视频分类数据集(YouTube-8M Segments)上验证了我们的方法,评估结果证明了我们的方法的泛化能力。
    在这里插入图片描述
    Neural Graph Embedding for Neural Architecture Search —AAAI-2020
    作者:Wei Li, Shaogang Gong, Xiatian Zhu
    摘要:现有的神经体系结构搜索((NAS))方法往往直接在离散空间或连续空间中进行搜索,忽略了神经网络的图形拓扑知识。考虑到神经网络本质上是有向无环图(DAG),这会导致搜索性能和效率欠佳。在这项工作中,我们通过引入一种新的神经图嵌入(NGE)思想来解决这个限制。具体来说,我们用神经DAG表示神经网络的构建块(即cell),并利用图卷积网络来传播和建模网络结构的固有拓扑信息。这导致可与现有的不同NAS框架集成的通用神经网络表示。大量实验表明,在图像分类和语义分割方面,NGE优于最新方法。
    在这里插入图片描述

    RoadTagger: Robust Road Attribute Inference with Graph Neural Networks ----AAAI2020
    作者:Songtao He, Favyen Bastani, Satvat Jagwani, Edward Park, Sofiane Abbar, Mohammad Alizadeh, Hari Balakrishnan, Sanjay Chawla, Samuel Madden, Mohammad Amin Sadeghi
    摘要:从卫星图像中推断道路属性(例如车道数和道路类型)是一项挑战。通常,由于卫星图像的遮挡和道路属性的空间相关性,仅当考虑道路的较远路段时,道路上某个位置的道路属性才可能是显而易见的。因此,为了鲁棒地推断道路属性,模型必须整合分散的信息,并捕捉道路沿线特征的空间相关性。现有的解决方案依赖于图像分类器,无法捕获这种相关性,导致准确性较差。我们发现这种失败是由于一个基本的限制–图像分类器的有效接受范围有限。
    为了克服这一局限性,我们提出了一种结合卷积神经网络(CNNs)和图神经网络(GNNs)来推断道路属性的端到端体系结构RoadTagger。使用GNN允许信息在路网图上传播,消除了图像分类器的接收域限制。我们在一个覆盖美国20个城市688平方公里面积的大型真实数据集和一个综合数据集上对RoadTagger进行了评估。在评估中,与基于CNN图像分类器的方法相比,RoadTagger提高了推理的准确性。此外,RoadTagger对卫星图像的中断具有较强的鲁棒性,能够学习复杂的inductive rule来聚合道路网络上分散的信息。
    在这里插入图片描述

    展开全文
  • 原文地址 本篇文章是对论文“Wu Z , Pan S , Chen F , et al. A Comprehensive Survey on ...1. 什么是图神经网络? 2. 有哪些图神经网络? 3. 图卷积网络(Graph Convolution Networks,GCN) 4. 图注意力网络...

    原文地址

    本篇文章是对论文“Wu Z , Pan S , Chen F , et al. A Comprehensive Survey on Graph Neural Networks[J]. 2019.”的翻译与笔记。论文链接

    目录

    1. 什么是图神经网络?

    2. 有哪些图神经网络?

    3. 图卷积网络(Graph Convolution Networks,GCN)

    4. 图注意力网络(Graph Attention Networks)

    5. Graph Autoencoders

    6. Graph Generative Networks

    7. Graph Spatial -Temporal Networks

    8. 图神经网络的应用


    1. 什么是图神经网络?

    在过去的几年中,神经网络的成功推动了模式识别和数据挖掘的研究。许多机器学习任务,如目标检测、机器翻译和语音识别,曾经严重依赖手工的特征工程来提取信息特征集,最近被各种端到端的深度学习范式(例如卷积神经网络(CNN)、长短期记忆(LSTM)和自动编码器)彻底改变了。在许多领域中,深度学习的成功部分归因于快速发展的计算资源(如GPU)和大量训练数据的可用性,部分归因于深度学习从欧氏空间数据中提取潜在表示的有效性。

    尽管深度学习在欧氏空间中的数据方面取得了巨大的成功,但在许多实际的应用场景中的数据是从非欧式空间生成的,同样需要进行有效的分析。例如,在电子商务中,一个基于图的学习系统能够利用用户和产品之间的交互来做出非常准确的推荐。图数据的复杂性对现有的机器学习算法提出了重大挑战,这是因为图数据是不规则的。每个图都有一个大小可变的无序节点,图中的每个节点都有不同数量的相邻节点,导致一些重要的操作(例如卷积)在图像上很容易计算,但不再适合直接用于图域。此外,现有机器学习算法的一个核心假设是实例彼此独立(独立同分布,i.i.d.)。然而,对于图数据来说,情况并非如此,图中的每个实例(节点)通过一些复杂的链接信息与其他实例(邻居)相关,这些信息可用于捕获实例之间的相互依赖关系。

    近年来,人们对深度学习方法在图数据上的扩展越来越感兴趣。在深度学习的成功推动下,研究人员借鉴了卷积网络、循环网络和深度自动编码器的思想,定义和设计了用于处理图数据的神经网络结构,由此一个新的研究热点——“图神经网络(Graph Neural Networks,GNN)”应运而生,本篇文章主要对图神经网络的研究现状进行简单的概述。

    需要注意的是,图神经网络的研究与图嵌入(对图嵌入不了解的读者可以参考我的这篇文章《图嵌入综述》)或网络嵌入密切相关,图嵌入或网络嵌入是数据挖掘和机器学习界日益关注的另一个课题。图嵌入旨在通过保留图的网络拓扑结构和节点内容信息,将图中顶点表示为低维向量空间(低维稠密向量),以便使用简单的机器学习算法(例如,支持向量机分类)进行处理。许多图嵌入算法通常是无监督的算法,它们可以大致可以划分为三个类别,即矩阵分解、随机游走和深度学习方法。同时图嵌入的深度学习方法也属于图神经网络,包括基于图自动编码器的算法(如DNGR和SDNE)和无监督训练的图卷积神经网络(如GraphSage)。下图描述了图嵌入和图神经网络在本文中的区别。

    图嵌入综述

     

    2. 有哪些图神经网络?

    在本文中,我们将图神经网络划分为五大类别,分别是:图卷积网络(Graph Convolution Networks,GCN)、 图注意力网络(Graph Attention Networks)、图自编码器( Graph Autoencoders)、图生成网络( Graph Generative Networks) 和图时空网络(Graph Spatial-temporal Networks)。

    符号定义:

    3. 图卷积网络(Graph Convolution Networks,GCN)

    图卷积网络将卷积运算从传统数据(例如图像,结构化数据)推广到图数据(非结构化数据)。其核心思想是学习一个函数映射 f(.),通过该映射图中的节点v_i可以聚合它自己的特征(向量)x_i与它邻居的特征x_j(j \in N(v_i))来生成节点 v_i的新表示。图卷积网络是许多复杂图神经网络模型的基础,包括基于自动编码器的模型、生成模型和时空网络等。下图直观地展示了图神经网络学习节点表示的步骤。

    GCN方法又可以分为两大类,基于频谱(spectral-based)和基于空间(spatial-based)。基于频谱的方法从图信号处理的角度引入滤波器来定义图卷积,其中图卷积操作被解释为从图信号中去除噪声。基于空间的方法将图卷积表示为从邻域聚合特征信息,当图卷积网络的算法在节点层次运行时,图池化模块可以与图卷积层交错,将图粗化为高级子结构。如下图所示,这种架构设计可用于提取图的各级表示和执行图分类任务。

    在下面,我们分别简单介绍了基于频谱的GCN和基于空间的GCN。

    • Spectral-based Graph Convolutional Networks

    在大学里学过《数字信号处理》这门课程的朋友应该会记得,在这门课上我们通过引入傅里叶变换将时域信号转换到频域进行分析,进而我们完成一些我们在时域上无法完成的操作,基于频谱的图卷积网络的核心思想正是来源于此。

    在基于频谱的图神经网络中,图被假定为无向图,无向图的一种鲁棒数学表示是正则化(规范化)图拉普拉斯矩阵,即

                                               L = I_n - D^{-1/2}AD^{-1/2}

    其中,A为图的邻接矩阵,D为对角矩阵(度矩阵):

                                                      D_{ii} = \sum_{j}A_{i,j}

    正则化图拉普拉斯矩阵具有实对称半正定的性质。利用这个性质,正则化拉普拉斯矩阵可以分解为:

    ,其中:

    U是由L的特征向量构成的矩阵,\Lambda是对角矩阵,对角线上的值为L的特征值。正则化拉普拉斯矩阵的特征向量构成了一组正交基(U中的特征向量/每一列是正交的)。

    在图信号处理过程中,一个图的信号:

    是一个由图的各个节点组成的特征向量,x_i表示第i个节点。

    对图X的傅里叶变换由此被定义为:

    傅里叶反变换则为:

    其中,\hat{x}为傅立叶变换后的结果。

    为了更好地理解图的傅里叶变换,从它的定义我们可以看出,它确实将输入图信号投影到正交空间,在正交空间中,基由正则化图拉普拉斯矩阵L的特征向量构成。

    转换后得到的信号\hat{x}的元素是新空间(正交空间)中图信号的坐标,因此原来的输入信号可以表示为:

    正是傅里叶反变换的结果。(上式与U\hat{x}等价)

    现在我们可以来定义对输入信号X的图卷积操作了:

    其中,g \in R^{N}是我们定义的滤波器;\odot表示Hadamard product(对应位置元素相乘)。

    假如我们定义这样一个滤波器:

    那么我们的图卷积操作可以简化表示为:

    基于频谱的图卷积网络都遵循这样的模式,它们之间关键的不同点在于选择的滤波器不同。

    现有的基于频谱的图卷积网络模型有以下这些:Spectral CNN、Chebyshev Spectral CNN (ChebNet)、Adaptive Graph Convolution Network (AGCN)。

    基于频谱的图卷积神经网络方法的一个常见缺点是,它们需要将整个图加载到内存中以执行图卷积,这在处理大型图时是不高效的。

    • Spatial-based Graph Convolutional Networks

    模拟传统卷积神经网络对图像的卷积运算,基于空间的方法基于节点的空间关系定义图卷积。为了将图像与图关联起来,可以将图像视为图的特殊形式,每个像素代表一个节点,如下图a所示,每个像素直接连接到其附近的像素。通过一个3×3的窗口,每个节点的邻域是其周围的8个像素。这八个像素的位置表示一个节点的邻居的顺序。然后,通过对每个通道上的中心节点及其相邻节点的像素值进行加权平均,对该3×3窗口应用一个滤波器。由于相邻节点的特定顺序,可以在不同的位置共享可训练权重。同样,对于一般的图,基于空间的图卷积将中心节点表示和相邻节点表示进行聚合,以获得该节点的新表示,如图b所示。

    一种共同的实践是将多个图卷积层叠加在一起。根据卷积层叠的不同方法,基于空间的GCN可以进一步分为两类:recurrent-based和composition-based的空间GCN。recurrent-based的方法使用相同的图卷积层来更新隐藏表示(不停的循环),composition-based的方法使用不同的图卷积层来更新隐藏表示(串联)。下图说明了这种差异。

    • Comparison Between Spectral and Spatial Methods

    作为最早的图卷积网络,基于频谱的模型在许多与图相关的分析任务中取得了令人印象深刻的结果。这些模型在图信号处理方面有一定的理论基础。通过设计新的图信号滤波器,我们可以从理论上设计新的图卷积网络。然而,基于频谱的模型有几个缺点。我们从效率、通用性和灵活性三个方面来说明这一点。

    在效率方面,基于频谱的模型的计算成本随着图的大小而急剧增加,因为它们要么需要执行特征向量计算,要么同时处理整个图,这使得它们很难适用于大型图。基于空间的模型有潜力处理大型图,因为它们通过聚集相邻节点直接在图域中执行卷积。计算可以在一批节点中执行,而不是在整个图中执行。当相邻节点数量增加时,可以引入采样技术来提高效率。

    在一般性方面,基于频谱的模型假定一个固定的图,使得它们很难在图中添加新的节点。另一方面,基于空间的模型在每个节点本地执行图卷积,可以轻松地在不同的位置和结构之间共享权重。

    在灵活性方面,基于频谱的模型仅限于在无向图上工作,有向图上的拉普拉斯矩阵没有明确的定义,因此将基于频谱的模型应用于有向图的唯一方法是将有向图转换为无向图。基于空间的模型更灵活地处理多源输入,这些输入可以合并到聚合函数中。因此,近年来空间模型越来越受到关注。

     

    4. 图注意力网络(Graph Attention Networks)

    注意力机制如今已经被广泛地应用到了基于序列的任务中,它的优点是能够放大数据中最重要的部分的影响。这个特性已经被证明对许多任务有用,例如机器翻译和自然语言理解。如今融入注意力机制的模型数量正在持续增加,图神经网络也受益于此,它在聚合过程中使用注意力,整合多个模型的输出,并生成面向重要目标的随机行走。在本节中,我们将讨论注意力机制如何在图结构数据中使用。

    • Graph Attention Network(GAT)

    图注意力网络(GAT)是一种基于空间的图卷积网络,它的注意机制是在聚合特征信息时,将注意机制用于确定节点邻域的权重。GAT的图卷积运算定义为:

    其中α(·)是一个注意力函数,它自适应地控制相邻节点j对节点i的贡献。为了学习不同子空间中的注意力权重,GAT还可以使用多注意力:

    • Gated Attention Network(GAAN)

    门控注意力网络(GAAN)还采用了多头注意力机制来更新节点的隐藏状态。然而,GAAN并没有给每个head部分配相等的权重,而是引入了一种自注意机制,该机制为每个head计算不同的权重。更新规则定义为,

    其中 \phi _0(.),\phi_v(.)是反馈神经网络,而g_i^{k}是第k个注意力head的注意力权重.

    • Graph Attention Model(GAM)

    图形注意力模型(GAM)提供了一个循环神经网络模型,以解决图形分类问题,通过自适应地访问一个重要节点的序列来处理图的信息。GAM模型被定义为:

    其中,f_h(.)是一个LSTM网络,f_s(.)是一个step network,它会优先访问当前节点v_{t-1}优先级高的邻居并将它们的信息进行聚合。

    除了在聚集特征信息时将注意力权重分配给不同的邻居节点,还可以根据注意力权重将多个模型集合起来,以及使用注意力权重引导随机行走。尽管GAT和GAAN在图注意网络的框架下进行了分类,但它们也可以同时被视为基于空间的图形卷积网络。GAT和GAAN的优势在于,它们能够自适应地学习邻居的重要性权重。然而,计算成本和内存消耗随着每对邻居之间的注意权重的计算而迅速增加。

     

    5. Graph Autoencoders

    图自动编码器是一类图嵌入方法,其目的是利用神经网络结构将图的顶点表示为低维稠密向量。典型的解决方案是利用多层感知机作为编码器来获取节点嵌入,其中解码器重建节点的邻域统计信息,如positive pointwise mutual information (PPMI)或一阶和二阶近似值。最近,研究人员已经探索了将GCN作为编码器的用途,将GCN与GAN结合起来,或将LSTM与GAN结合起来设计图自动编码器。我们将首先回顾基于GCN的AutoEncoder,然后总结这一类别中的其他变体。

    目前基于GCN的自编码器的方法主要有:Graph Autoencoder (GAE)和Adversarially Regularized Graph Autoencoder (ARGA)

    图自编码器的其它变体有:

    Network Representations with Adversarially Regularized Autoencoders (NetRA)

    Deep Neural Networks for Graph Representations (DNGR)

    Structural Deep Network Embedding (SDNE)

    Deep Recursive Network Embedding (DRNE)

    DNGR和SDNE学习仅给出拓扑结构的节点嵌入,而GAE、ARGA、NetRA、DRNE用于学习当拓扑信息和节点内容特征都存在时的节点嵌入。图自动编码器的一个挑战是邻接矩阵A的稀疏性,这使得解码器的正条目数远远小于负条目数。为了解决这个问题,DNGR重构了一个更密集的矩阵,即PPMI矩阵,SDNE对邻接矩阵的零项进行惩罚,GAE对邻接矩阵中的项进行重加权,NetRA将图线性化为序列。

     

    6. Graph Generative Networks

    图生成网络的目标是在给定一组观察到的图的情况下生成新的图。图生成网络的许多方法都是特定于领域的。例如,在分子图生成中,一些工作模拟了称为SMILES的分子图的字符串表示。在自然语言处理中,生成语义图或知识图通常以给定的句子为条件。最近,人们提出了几种通用的方法。一些工作将生成过程作为节点和边的交替形成因素,而另一些则采用生成对抗训练。这类方法要么使用GCN作为构建基块,要么使用不同的架构。

    基于GCN的图生成网络主要有:

    Molecular Generative Adversarial Networks (MolGAN):将relational GCN、改进的GAN和强化学习(RL)目标集成在一起,以生成具有所需属性的图。GAN由一个生成器和一个鉴别器组成,它们相互竞争以提高生成器的真实性。在MolGAN中,生成器试图提出一个伪图及其特征矩阵,而鉴别器的目标是区分伪样本和经验数据。此外,还引入了一个与鉴别器并行的奖励网络,以鼓励生成的图根据外部评价器具有某些属性。

    Deep Generative Models of Graphs (DGMG):利用基于空间的图卷积网络来获得现有图的隐藏表示。生成节点和边的决策过程是以整个图的表示为基础的。简而言之,DGMG递归地在一个图中产生一个节点,直到达到某个停止条件。在添加新节点后的每一步,DGMG都会反复决定是否向添加的节点添加边,直到决策的判定结果变为假。如果决策为真,则评估将新添加节点连接到所有现有节点的概率分布,并从概率分布中抽取一个节点。将新节点及其边添加到现有图形后,DGMG将更新图的表示。

    其它架构的图生成网络主要有:

    GraphRNN:通过两个层次的循环神经网络的深度图生成模型。图层次的RNN每次向节点序列添加一个新节点,而边层次RNN生成一个二进制序列,指示新添加的节点与序列中以前生成的节点之间的连接。为了将一个图线性化为一系列节点来训练图层次的RNN,GraphRNN采用了广度优先搜索(BFS)策略。为了建立训练边层次的RNN的二元序列模型,GraphRNN假定序列服从多元伯努利分布或条件伯努利分布。

    NetGAN:Netgan将LSTM与Wasserstein-GAN结合在一起,使用基于随机行走的方法生成图形。GAN框架由两个模块组成,一个生成器和一个鉴别器。生成器尽最大努力在LSTM网络中生成合理的随机行走序列,而鉴别器则试图区分伪造的随机行走序列和真实的随机行走序列。训练完成后,对一组随机行走中节点的共现矩阵进行正则化,我们可以得到一个新的图。

     

    7. Graph Spatial -Temporal Networks

    图时空网络同时捕捉时空图的时空相关性。时空图具有全局图结构,每个节点的输入随时间变化。例如,在交通网络中,每个传感器作为一个节点连续记录某条道路的交通速度,其中交通网络的边由传感器对之间的距离决定。图形时空网络的目标可以是预测未来的节点值或标签,或者预测时空图标签。最近的研究仅仅探讨了GCNs的使用,GCNs与RNN或CNN的结合,以及根据图结构定制的循环体系结构。

    目前图时空网络的模型主要有:

    Diffusion Convolutional Recurrent Neural Network (DCRNN)

    CNN-GCN

    Spatial Temporal GCN (ST-GCN)

    Structural-RNN

     

    8. 图神经网络的应用

    • Computer Vision

    图形神经网络的最大应用领域之一是计算机视觉。研究人员在场景图生成、点云分类与分割、动作识别等多个方面探索了利用图结构的方法。

    在场景图生成中,对象之间的语义关系有助于理解视觉场景背后的语义含义。给定一幅图像,场景图生成模型检测和识别对象,并预测对象对之间的语义关系。另一个应用程序通过生成给定场景图的真实图像来反转该过程。自然语言可以被解析为语义图,其中每个词代表一个对象,这是一个有希望的解决方案,以合成给定的文本描述图像。

    在点云分类和分割中,点云是激光雷达扫描记录的一组三维点。此任务的解决方案使激光雷达设备能够看到周围的环境,这通常有利于无人驾驶车辆。为了识别点云所描绘的物体,将点云转换为k-最近邻图或叠加图,并利用图论进化网络来探索拓扑结构。

    在动作识别中,识别视频中包含的人类动作有助于从机器方面更好地理解视频内容。一组解决方案检测视频剪辑中人体关节的位置。由骨骼连接的人体关节自然形成图表。给定人类关节位置的时间序列,应用时空神经网络来学习人类行为模式。

    此外,图形神经网络在计算机视觉中应用的可能方向也在不断增加。这包括人-物交互、少镜头图像分类、语义分割、视觉推理和问答等。

    • Recommender Systems

    基于图的推荐系统以项目和用户为节点。通过利用项目与项目、用户与用户、用户与项目之间的关系以及内容信息,基于图的推荐系统能够生成高质量的推荐。推荐系统的关键是评价一个项目对用户的重要性。因此,可以将其转换为一个链路预测问题。目标是预测用户和项目之间丢失的链接。为了解决这个问题,有学者提出了一种基于GCN的图形自动编码器。还有学者结合GCN和RNN,来学习用户对项目评分的隐藏步骤。

    • Traffic

    交通拥堵已成为现代城市的一个热点社会问题。准确预测交通网络中的交通速度、交通量或道路密度,在路线规划和流量控制中至关重要。有学者采用基于图的时空神经网络方法来解决这些问题。他们模型的输入是一个时空图。在这个时空图中,节点由放置在道路上的传感器表示,边由阈值以上成对节点的距离表示,每个节点都包含一个时间序列作为特征。目标是预测一条道路在时间间隔内的平均速度。另一个有趣的应用是出租车需求预测。这有助于智能交通系统有效利用资源,节约能源。

    • Chemistry

    在化学中,研究人员应用图神经网络研究分子的图结构。在分子图中,原子为图中的节点,化学键为图中的边。节点分类、图形分类和图形生成是分子图的三个主要任务,它们可以用来学习分子指纹、预测分子性质、推断蛋白质结构、合成化合物。

    • Others

    除了以上四个领域外,图神经网络还已被探索可以应用于其他问题,如程序验证、程序推理、社会影响预测、对抗性攻击预防、电子健康记录建模、脑网络、事件检测和组合优化。

     

    展开全文
  • 从图嵌入算法到图神经网络

    千次阅读 多人点赞 2019-08-13 15:12:25
    图神经网络,广泛应用于社交关系、知识图谱、推荐系统、蛋白质分子建模,同样源自于对传统领域的创新,它的前身是图嵌入算法;而图嵌入算法又以图数据作为载体。这一关系,将贯穿本文始末,成为我们
  • 一、什么是图神经网络? 在过去的几年中,神经网络的成功推动了模式识别和数据挖掘的研究。许多机器学习任务,如目标检测、机器翻译和语音识别,曾经严重依赖手工的特征工程来提取信息特征集,最近被各种端到端的...
  • 本文将介绍基于图神经网络的知识图谱学习与计算以及基于图神经网络融合知识图谱信息的应用的研究进展。 1 知识图谱与图神经网络 近几年来,人工智能技术得到了飞速发展,其进展突出体现在以知识图谱(Knowledge ...
  • 什么是图神经网络

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

    万次阅读 2018-04-28 11:47:53
    通过这篇文章,您将了解神经网络的主要缺点,阅读完它后,您将知道神经网络的主要缺点,当您为当前的机器学习问题选择正确类型的算法时,您将有一个大致的指导原则。目录:1.为什么深度学习被如此大肆宣传(数据,...
  • 卷积神经网络架构

    万次阅读 多人点赞 2018-11-20 17:14:48
    卷积神经网络(conv)架构 卷积神经网络在图像分类数据集上有非常突出的表现,...卷积神经网络图: 共同点: 中每一个节点都代表一个神经元,没相邻两层之间的节点都有边相;输入输出的流程基本一致。 不同...
  • 数据结构的不规则性导致了图神经网络的最新发展。在过去的几年中,正在开发图神经网络的各种变体,其中之一就是图卷积网络(GCN)。GCN也被视为基本的图神经网络变体之一。 在本文中,我们将更深入地研究由Thomas ...
  • 卷积神经网络综述

    千次阅读 2019-02-25 14:51:38
    下面来简单介绍和归纳总结一下国内外卷积神经网络的结构,分析...卷积神经网络不仅具有传统神经网络的较好容错性、自适应性和较强自学习能力等优点,还具有自动提取特征、权值共享以及输入图像与网络结构结合良好...
  • 图神经网络综述

    万次阅读 2019-11-07 17:09:00
    文章目录 1 简介 1.1 GNN简史 1.2 GNN的相关研究 1.3 GNN vs 网络嵌入 ... 4 卷积网络 4.1 基于图谱的GCN 4.1.1 信号处理 4.1.2 基于谱的GCN方法 4.1.3 总结 4.2 基于空间...
  • 图神经网络(GNN)基础

    千次阅读 2020-03-26 16:02:43
    前言 现在很多的学习任务需要处理内在关系丰富的图结构数据,比如...图(graph)是一种数据结构,图神经网络(Graph Neural Network)是深度学习在图结构数据上的一些模型、方法和应用。常见的图结构由节点(node)和边(ed...
  • GCN—卷积神经网络理解

    千次阅读 多人点赞 2019-09-10 19:30:23
    文章目录一、CNN卷积二、GCN 卷积神经网络2.1 GCN优点2.3 提取拓扑空间特征的两种方式三、拉普拉斯矩阵3.1 拉普拉斯矩阵的谱分解(特征分解)3.2 如何从传统的傅里叶变换、卷积类比到Graph上的傅里叶变换及卷积...
  • A Survey on Graph Neural Networks for Knowledge Graph ...最近在看图谱补全相关的内容,现在比较多的方向是采用图嵌入的方式进行学习,这篇论文综述了图神经网络在补全上的应用,值得读一读 二级目录 三级目录 ...
  • 文章目录图神经网络1 游走类模型1.1 DeepWalk随机游走DeepWalk计算节点向量的方式:1.2 Node2VECnode2vec改进后的随机游走方式:1.3 LINE2 消息传递类模型2.1 GCN2.2 GAT2.3 GraphSageGraphSAGE 的采样方法:...
  • 浅析卷积神经网络

    万次阅读 多人点赞 2018-05-21 10:31:11
    今天想和大家分享的是卷积神经网络。随着人工智能发展,很多人都听说过机器学习、深度学习、卷积神经网络这些概念。但卷积神经网络,却不多人提起。那什么是卷积神经网络呢?简单的来说就是其研究的对象是...
  • 图像常用的神经网络方法优缺点及应用总结

    千次阅读 多人点赞 2021-04-13 19:12:38
    以下主要讨论神经网络的分类 1. 人工智能、机器学习与深度学习 人工神经网络(Artificial Neural Network,ANN)简称神经网络(NN),是基于生物学中神经网络的基本原理,在理解和抽象了人脑结构和外界刺激响应机制...
  • 基于卷积神经网络的人脸识别

    万次阅读 多人点赞 2020-07-06 16:59:22
    基于卷积神经网络的人脸识别的实现 利用opencv获取人脸,采集人脸数据,将收集到的人脸数据加载到内存,搭建属于自己的卷积神经网络,并用人脸数据训练自己的网络,将训练好的网络保存成模型,最后再用opencv获取...
  • 卷积神经网络优点

    万次阅读 2018-08-29 21:20:21
    卷积神经网络是在Hub等人对猫的视觉皮层中细胞的研究基础上,通过拟生物大脑皮层构而特殊设计的含有多隐层的人工神经网络。卷积层、池化层、激活函数是卷积神经网路的要组部分。卷积神经网络通过局部感受野、权重...
  • GNN (开源)通过图神经网络实现3d目标检测论文解读摘要介绍相关工作点云数据规则化处理点云直接处理图处理点云Point GNN在点云数据目标检测构建图下采样找寻周围临近点,并将编码临近点的信息为SiPoint GNN主体框架...
  • 会话序列推荐的应用,发自AAAI 2019,先放链接: blog:https://sxkdz.github.io/research/SR-GNN/ paper:https://arxiv.org/abs/1811.00855 code:https://github.com/CRIPAC-DIG/SR-GNN 会话推荐是指,对于一个...
  • 【2020 图神经网络综述】A Comprehensive Survey on Graph Neural Networks 文章转载于好我的朋友:大家可以关注他的博客: Memory逆光 博客地址:...
  • 图神经网络(GNN)总结

    千次阅读 2019-07-09 22:19:48
    1 简单的的参数介绍 G=(V,E,A)\mathcal { G } = ( V , E , A )G=(V,E,A) V(N个)是节点集合, 只描述了存在的节点 E是边集合, 只描述了存在的连接(边) A(NxN)是的邻接矩阵, 描述了节点之间的连接关系, 当对应的边...
  • SIGIR'19的一篇论文Neural Graph Collaborative Filtering(NGCF)介绍了用图神经网络(GNN)来增强协同过滤推荐系统的方法。今天我们来聊一聊下面几个话题: 什么是协同过滤?如何用协同过滤做推荐? NGCF是如何...
  • 论文笔记:GGNN (门控图神经网络)

    万次阅读 2019-04-13 18:15:32
    一个 G = (V, E), 节点v ∈ V中存储D维向量,边e ∈ E中存储D × D维矩阵, 目的是构建网络GGNN。 实现每一次参数更新时,每个节点既接受相邻节点的信息,又向相邻节点发送信息。 主要贡献 基于GRU提出了GGNN...
  • 1.用的分解和卷积来做文本匹配 https://www.aclweb.org/anthology/P19-1632.pdf 2.表示解决长文本关系匹配问题:腾讯提出概念交互算法 论文地址:https://arxiv.org/abs/1802.07459 相关数据资源:...
  • 4.循环图神经网络(GRN) 5.卷积图神经网络 A.基于频谱的ConvGNNs B.基于空间的CGNN C.图池化模型 D.理论方面的讨论 6.图自动编码器 A.网络嵌入 B.图生成 7.时空图神经网络 8.应用 A.数据集 B.基准和...
  • 卷积神经网络优点

    千次阅读 2020-02-01 19:10:38
    优点: 1.在卷积层所用的权重和偏置的参数较少,两个原因:...2. 具有平移不变性,即使图片中的目标位置平移到图片另一个地方,卷积神经网络仍然能很好地识别出这个目标,输出的结果也和原来未平移之前是一致的。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 43,359
精华内容 17,343
关键字:

图神经网络优点