Jarvis' Blog 成功的路上并不拥挤, 因为坚持的人不多

GNNs: Graph Neural Networks

2019-03-07
Jarvis
Post

Title: Graph Neural Networks: A Review of Methods and Applications

1. Introduction

图 (graph) 是一种对节点 (node)边 (edge) 进行建模的结构, 这种结构的研究主要聚焦于节点分类, 链接预测和聚类上. 图神经网络 (graph neural networks, GNNs) 则是图与神经网络的一种结合, 同时也是神经网络的一种推广 (从结构化数据到非结构化数据). GNNs 的想法来源于以下几个方面:

  • 卷积神经网络 (CNN). CNN 的特点在于局部连接, 共享权重, 多层结构.
  • 图嵌入 (graph embedding). 学习使用低维向量表示图节点, 边和子图.

GNNs 的特点:

  • 忽略节点的输入次序. 即 GNNs 的输出不依赖于输入节点的顺序.
  • 通过求邻居节点状态的加权和来更新节点的状态
  • 可以探索神经推理 (reasoning), 这是 CNN 难以做到的.

本文的目的是对不同的 GNNs 模型做一个较为全面的综述, 并对相关应用做一个系统的分类.

第2节介绍 GNNs 的各种网络结构, 第3节介绍 GNNs 在结构化数据和非结构化数据上的应用, 第4节本文提出了四个 GNNs 中开放性的问题以供未来的研究参考, 第5节做一个总结.

2. Models

在 2.1 节介绍原始的 GNNs 结构及其局限性. 在 2.2 节给出集中变体以解决原始 GNNs 中的问题. 在 2.3 节给出三种一般性的框架: message passing neural network (MPNN), non-local neural network (NLNN) 和 graph network (GN). 以下是符号表

记号 描述
维欧氏空间
标量, 向量, 矩阵
矩阵转置
维单位矩阵
卷积
图中的节点数
图中的边数
节点 的邻点集
节点 在时间 的向量
节点 的隐藏状态
节点 在时间 的隐藏状态
节点 的边的特征
标签为 的边的特征
节点 的输出
sigmoid 函数
非线性函数
逐点乘法
向量拼接

2.1 GNNs

GNNs 的概念首先在[1]中提出, 把神经网络进行拓展以处理图中的数据. GNNs 的目标是学习图中每个节点的隐藏状态嵌入 (state embedding) , 这个隐藏状态包含了该节点的邻节点的信息. 节点 的隐藏状态 是一个 维的向量, 可以用于产生该节点的输出标签 . 令 是一个方程, 称为局部变换方程 (local transition function), 在所有节点中共享, 用于根据邻居节点的输入来更新节点状态. 令 局部输出函数 (local output function), 产生节点输出. 公式表示如下

其中函数 中的四个参数分别表示节点 的特征, 边的特征, 状态和邻节点的状态.

Reference

  1. The graph neural network model
    F.Scarselli, M.Gori, A.C.Tsoi, M.Hagenbuchner, G.Monfardini
    [Link]. In IEEE TNN 2009, vol.20, no. 1, pp. 61–80, 2009.

Content