图神经网络

推荐使用网址：https://www.dgl.ai/

介绍

  • 图：同数据结构中的图
    • 节点

    • 边


      image.png

  • 最终目的：
    尝试将图作为输入，插入到神经网络中

  • 为什么需要GNN
    因为我们生活中许多数据并不是欧式距离（图片，文本），而是非欧式距离（分子结构图）

    • 检测 分子 是否会突变
    • 生成 我们所需要的分子 （适用于解决新型冠状病毒药物的分子）

  • 需要解决的问题

    • 如何充分利用结构和关系去帮助我们的模型？
    • 图太大的情况下，怎么办？
    • 没有所有数据的标签应该怎么办？

  • 案例


    一种图
    • 带标注的节点远远小于无标签节点的个数
      • 选取一个未知标签的点
      • 随机选取 n 个邻接节点
      • 根据邻接节点的种类对无标签样本进行分类

  • 两种解决方法：

    • 将卷积的概念扩展到图上 --> 空间卷积
    • 使用信号处理的卷积方式 --> 谱卷积

路程图

  • 路程图


    路程图

任务，数据集以及基准

  • 任务：

    • 半监督节点分类
    • 回归
    • 图分类
    • 图表示学习
    • 链接预测

  • 数据集：

    • CORA：引用网络，2.7k nodes + 5.4k links
    • TU-MUTAG: 平均节点为18个的188个分子

  • 基准：


    实验结果1
实验结果2
实验结果3
实验结果4
实验结果5
实验结果6
实验结果7

基于空间的 GCN

  • 卷积：


    欧式卷积

  • 图卷积：


    图卷积
    • 聚合：用邻居特征更新下一层的 hidden state｛使用0， 2， 4节点更新3｝
    • 集合：把所有节点的特征集合起来代表整个图

  • 方法1：NN4G

    • NN4G 聚合图以及解释
    NN4G的聚合
    • 首先对输入层的各个节点做类似与 Embedding 的处理，得到 Hidden layer 0
    • 然后使用如图方式对节点进行更新得到下一层

  • NN4G 集合图以及解释

    NN4G的集合
    • 得到每一层的节点的均值
    • 对每层的均值再次进行加权处理得到最终结果

  • 方法2：DCNN(Diffusion-Convolution Neural Network)

    • DCNN 聚合图以及解释


      DCNN 聚合图
      • 以最下面的图为基准
      • 对于 Hidden state 0，计算出与所选节点距离为1的特征的和的平均，得到各个节点的特征H^0[H^0是由Hidden state 0所有节点组成的矩阵]{对于节点3，距离为1的节点有0， 2， 4}
      • 对于 Hidden sate 1，计算出与所选节点距离为2的特征的和的平均，得到各个节点的特征H^1[H^1是由Hidden state 1所有节点组成的矩阵]｛对于节点3，距离为2的节点有1， 3｝
      • 以此类推，可以得到多个上述的矩阵
      • 将得到的矩阵按照如图形式表示

    • DCNN 集合图以及解释

DCNN集合图

- 根据聚合得到的结果，将其表示出来
- 对各个特征进行加权得到最终结果【图中显示的是得到第一个节点的feature】

  • 方法3：DGC（Diffusion Graph Convolution）

    • 聚合方式与 DCNN 类似

    • DGC 集合图以及解释


      DGC集合图
      • 处理方式与 DCNN 不同，其将得到的结果进行累加
      • 然后对其进行加权，得到最终结果

  • 方法4：MoNET（Mixture Model Networks）

    • 方式
      • 定义一个节点距离的 度量

      • 使用权值相加(平均)代替简单的相加(平均)


        MoNET
      • u 是距离度量 u(x, y)指的是邻接点与自身节点组成的值
      • 根据 u 的值得到各个节点的权值

  • 方法5：GraphSAGE

    • 方式

      • 取样并且聚合
      • 可以使用转导设置与引导设置进行工作
      • 从邻居学习嵌入节点特征

    • 算法:


      GraphSAGE 算法

    • 过程：


      过程

  • 方法6：GAT

    • 步骤：


      步骤

    • 聚合


      聚合
      • 学习一个 f 计算所有节点的重要性
      • 使用图中公式更新所有的节点

  • 方法7：GIN(Graph Isomorphism Netwrk)

    GIN 可解释模型
    • 公式如图
    • 使用求和
    • 使用MLP代替第一层

图信号处理以及基于谱的 GCN

  • 基本思想：


    基本思想
    • 图解：
      • 首先将图空间中的原始图与 Filte 都进行傅里叶转换，将其转换到傅里叶空间上
      • 然后对转换的结果进行相乘处理，得到傅里叶空间中的结果
      • 最后将得到的结果进行反傅里叶转换，将傅里叶空间中的结果转换到图空间中

  • 谱图理论：

    • 图：G = (V, E), N = |V|，其中V指的是节点，E指的是边，N为节点的个数
    • 邻接矩阵（权值矩阵）：A \in R^{N \times N},A_{i,j }= \begin{cases} 0 & 如果 e_{i,j} \notin E \\ w(i,j)& 其他 \\ \end{cases}
    • 本部分只考虑无向图 \rightarrow 邻接矩阵 A 是对称的
    • 度矩阵： D \in R^{N \times N}, 下面d(i)指的是邻接矩阵中第i行的和，D_{i,j }= \begin{cases} d(i) & 如果 i = j \\ 0 & 其他 \\ \end{cases}
    • 信号函数：f:C \rightarrow R^N, 比如 f(i)表示节点 i 的信号
      节点信号图

  • 图拉普拉斯定理

    • 图拉普拉斯 L = D - A, L \geq 0 \rightarrow 半正定

    • L 是对称的（对于无向图）

    • L = U \Lambda U^T （谱合成）

      L的表示

    • \Lambda = diag(\lambda_0, ..., \lambda_{N-1}) \in R^{N \times N}
      -U = [u_0, ..., u_{N-1}] \in R^{N \times N} \rightarrow 正交化

    • \lambda_l 是频率, u_l 是对应于 \lambda_l 的基

对于图拉普拉斯定理的一个图表示：

图例

  • 符号解释

    • D 为度数矩阵
    • A 为邻接矩阵
    • L = D - A
    • 根据得到的L计算出特征值与特征向量，即 \Lambda与 U

  • 图信号表示结果：


    图信号表示

  • 离散状态下的图理论：


    离散时间傅里叶基

  • 解释：【为什么 \Lambda是频率 u是基？】

    • 节点频率


      频率解释
    能量差推导

    • 特例


      特例
      • \lambda越大，说明某节点左右的信号之差越大

图的计算

  • 时域到频域的转换


    时域 到 频域

  • 频域到时域的转换


    频域 到 时域

Filter 的计算

  • 时域到频域的转换


    时域 到 频域

  • 频域到时域的转换


    频域 到 时域

反傅里叶转换

过程1

过程2

- 即需要学习一个 函数 g_\theta(*) ,函数不同得到的复杂度不同

存在的两个问题

  • 复杂度太大

  • 不是局部化

谱模型

  • ChebNet 【切比雪夫】


    ChebNet

    • 存在的问题：时间复杂度太大：O(N^2)

    • 解决方法：


      解决时间复杂度

      对上述参数进行更换


      更换结果

      在黄色箭头后对函数进行变换的目的是方便计算

最终计算方式：


公式推导1
公式推导2

  • GCN：
    公式推导：


    公式推导1
公式推导2

解决GCN中性能较低的方法： 使用DropEdge

总结

学习一个Filter的参数，即 g_\theta(*)中的\theta，可以选择多个Filter（类似于卷积中的多个 channel）

图生成

  • 基于VAE的模型：一步生成一整个图


    基于VAE的模型

  • 基于GAN的模型：一步生成一整个图


    基于GAN的模型

  • 基于自回归的模型：一步生成节点和边


    自回归

用于 NLP 的 GNN

  • Semanic Roles Labeling


    图解1
图解2
  • 事件检测
  • 文档时间戳
  • 命名实体识别
  • 关系提取
  • 知识图谱

总结

总结图
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。