GCN原理及相关算法

Basic of GCN

GCN

• H(l+1) = f(A, H(l))

  • 聚合周围的邻接节点

• 解读（形式上）

  • 图的邻接矩阵，做了自环（加了I）

  • 然后做了对称归一化

    • 通过D^(1-1/2)

  • 再对整个输入特征进行聚合

    • 乘以H

GCN原理之spectral graph theory

properties of matrices related to A

• L = D-A
• Lsym = D^(-1/2) L D^(-1/2)

L是实对称阵，并且是半正定的

拉普拉斯矩阵

• 对称的
• 半正定的，lanmuda >0
• 每一行每一列的和都是0

拉普拉斯的二次型

• 二次型变换后，为定点和周围邻接点之前的差值平方和

LAPUL

GCN原理之fourier transform

什么是傅里叶变换

• 同一个事物在不同域之间不同的视角是什么样的？ 及在不同域之间如何变幻？

  • 通过FT变化变换域，可以快速计算对应多项式的值，一一对应相乘。

• 例子

  • f(x)

    • 比如声波

      • 把男声和女声分解在不同频段

        • 进行分解

    • 可以进行不同空间的分解

  • FFT(快速傅里叶变换)

    • 通过FT变化变换域，可以快速计算对应多项式的值，一一对应相乘。

图的傅里叶变换

• 图像的卷积

  • 比较规则的结构，可以特定结构的卷积核去做卷积

• 图的卷积

  • 很稀疏、不规则，因此无法直接做卷积

    • 在空间域做卷积很麻烦

      • 先做一个变换，做卷积，然后再做逆变换，变换回空间域

• 图上的傅里叶变换是什么

  • LX: 拉普拉斯矩阵 乘以 fetarue x 是什么？

    • x是feature，点上的一系列属性

  • 卷积是邻居的聚合

    • 通过LX，对每个点聚合它周围的邻居

      • 先对点和周围的邻居，进行一些交互，然后累加

  • 本质是：x乘以一个比

    • x乘以一个U^T，做变换

    • 然后对新的域，进行缩放

    • 再乘以U，做逆变换

      • 回原来的空间

Graph Convolution

已有：关于图的邻接矩阵的函数

• 输入是邻接矩阵
• 拉普拉斯矩阵

分解F(A)

• U lanmula U^T

如何得到聚合后的节点向量表示？

DeepWalk 随机游走

概念

• 随机生成图节点序列，进行游走，当成一个句子，然后对序列进行wordvec，参数max length

缺点

• 忽略权重
• 过于随机

node2vec： bias random walk

GraphSAGE(图采样算法）

希望采样后的子图是连通的

归纳式的图神经网络模型

思路

• aggregate

  • Mean

    • 类似于GCN中的节点更新方式

  • LSTM聚合

    • 更强的表达力，但是可能不对称
    • 可以通过打乱邻接点的顺序

  • Pooling Aggregator

    • 让所有邻接点通过一个全连接层

    • 然后做最大化池化

    • 优点

      • 可对称，可训练

• update

• readout

过程

• 先从一阶邻居选，再从二阶邻居选等

• 再从外到内更新节点

  • 比如求和周围的节点

参数是什么

训练目标

• 得到聚合函数，用于聚合邻接点信息，可以泛化

优点

• 减少计算量

• 泛化能力，减少过拟合

  • 利于推理阶段

缺点

• 多阶邻居的消息传递损失较大，因为有递减过程

PinSAGE

优点

• 可以通过虚拟节点，直接过去远处的非一阶邻居
• 加强信息的完整性

方法

• 通过多次随机游走，按游走经过的频率选取邻居，将邻居节点作为虚拟节点，直接连接中心节点

GAT

attention 1

• 通过0号和2号向量，经过一个函数得到一个权重，然后乘以2号向量，传到0号向量

分类

基于谱域的GNN

• GCN

基于空域的GNN

• GraphSAAGE
• GAT
• PinSAGE
• DeepWalk