论文笔记
🗒️笔记-图神经网络
00 分钟
2024-1-13
2024-5-13
type
status
date
slug
summary
tags
category
icon
password
😎
在做时空外延的时候发现大部分的文章都是GNN/GCN based的，感觉得学一下图神经网络相关的内容了，便找学长讨了一份资料，里面的内容确实不错，本篇是对其的理解。 更新：Transformer is a GNN, math in GCN, 图采样
 
 
A Gentle Introduction to Graph Neural Networks
What components are needed for building learning algorithms that leverage the structure and properties of graphs?
https://distill.pub/2021/gnn-intro/
A Gentle Introduction to Graph Neural Networks
从图(Graph)到图卷积(Graph Convolution)：漫谈图神经网络模型 (一) - SivilTaram - 博客园
笔者最近看了一些图与图卷积神经网络的论文，深感其强大，但一些Survey或教程默认了读者对图神经网络背景知识的了解，对未学过信号处理的读者不太友好。同时，很多教程只讲是什么，不讲为什么，也没有梳理清楚不同网络结构的区别与设计初衷(Motivation)。 因此，本文试图沿着图神经网络的历史脉络，从
从图(Graph)到图卷积(Graph Convolution)：漫谈图神经网络模型 (一) - SivilTaram - 博客园
https://www.cnblogs.com/SivilTaram/p/graph_neural_network_1.html
基于循环的图神经网络历史脉络图神经网络GNN不动点理论GNN的局限门控图神经网络GGNNRNN/GRU/LSTMGGNN逻辑GGNN的局限基于多层神经网络的图神经网络空域卷积消息传递网络MPNN图采样与聚合GraphSage图结构序列化PATCHY-SAN频域卷积傅里叶变换与拉普拉斯算子图上的傅里叶变换Spectral CNNChebNetGCN全图的表示基于统计的方法基于学习的方法采样加全连接全局结点可微池化图采样GraphSAGEFastGCNDropEdge

基于循环的图神经网络

历史脉络

  1. 起源于分子结构分类等严格意义上的图论问题
  1. 在图信号处理的基础上，提出了图上的基于频域(Spectral-domain)和基于空域(Spatial-domain)的卷积神经网络，但后续基于频域的工作相对较少，学界提出了很多基于空域图卷积的方式。
  1. 图表示学习(Represent Learning for Graph)同时也在发展，如Word2Vec与DeepWalk，进行深度学习图表示；TransE为知识图谱的分布式表示(Represent Learning for Knowledge Graph)奠定了基础。

图神经网络GNN

图：由若干个结点(Node)及连接两个结点的边(Edge)所构成的图形，用于刻画不同结点之间的关系
notion image
GNN通过迭代式更新所有节点的隐含状态来使得每一个节点能够感知到图上的其他节点：（下式中f为状态更新函数/局部转移函数【全局共享】，公式中的指的是与结点相邻的边的特征，指的是结点的邻居结点的特征，则指邻居结点在时刻的隐藏状态。）
notion image
即考虑到了：
  • 【邻边特征】相邻边的特征
  • 【节点特征】节点（自己&邻居）的特征
  • 【节点状态】邻居节点的状态
不断地利用当前时刻邻居结点的隐藏状态作为部分输入来生成下一时刻中心结点的隐藏状态，直到每个结点的隐藏状态变化幅度很小，整个图的信息流动趋于平稳。至此，每个结点都“知晓”了其邻居的信息。
notion image
之后采用另一个函数来满足下游任务（如分类、回归等）
notion image

不动点理论

notion image
不论是什么，只要是个压缩映射(contraction map，指变换后的新空间比原先空间要小)，经过不断迭代都会收敛到某一个固定的点，我们称之为不动点
notion image
Transformers are Graph Neural Networks | NTU Graph Deep Learning Lab
Engineer friends often ask me: Graph Deep Learning sounds great, but are there any big commercial success stories? Is it being deployed in practical applications? Besides the obvious ones–recommendation systems at Pinterest, Alibaba and Twitter–a slightly nuanced success story is the Transformer architecture, which has taken the NLP industry by storm. Through this post, I want to establish links between Graph Neural Networks (GNNs) and Transformers. I’ll talk about the intuitions behind model architectures in the NLP and GNN communities, make connections using equations and figures, and discuss how we could work together to drive progress.
Transformers are Graph Neural Networks | NTU Graph Deep Learning Lab
https://graphdeeplearning.github.io/post/transformers-are-gnns/
Transformers are Graph Neural Networks | NTU Graph Deep Learning Lab
上面的文章从Transformer is a GNN的角度来介绍，写的非常好，总结来说就是：
GNN中的将节点neighbourhood aggregation (or message passing)的过程中的sum/mean/max与Transformer中的attention mechanism（即以点积作为weight计算加权平均）的方式很像，都是聚合邻居的信息，叠得更深可以聚合到更多信息。
notion image

GNN的局限

其核心是：通过结点信息的传播使整张图达到收敛，在其基础上再进行预测。收敛作为GNN的内核，同样局限了其更广泛的使用。
  1. 【边的学习不够彻底】相比于其他输入，边对结点隐藏状态的影响实在有限。并且GNN没有为边设置独立的可学习参数，也就意味着无法通过模型学习到边的某些特性。
  1. 【全局共享导致节点状态光滑】不动点的收敛会导致结点之间的隐藏状态间存在较多信息共享，从而导致结点的状态太过光滑(Over Smooth)，并且属于结点自身的特征信息匮乏(Less Informative)。
GNN后的大部分工作都转向了将GNN向传统的RNN/CNN靠拢，可能的一大好处是这样可以不断吸收来自这两个研究领域的改进。但基于原始GNN的基于不动点理论的工作非常少，至少在笔者看文献综述的时候并未发现很相关的工作。

门控图神经网络GGNN

RNN/GRU/LSTM

⭐
RNN/GRU/LSTM

GGNN逻辑

  • 【GRU模块】GGNN不再以不动点理论为基础，即f不再被强制要求为压缩映射
notion image
  • 【异构图学习】除了GRU式的设计外，GGNN还针对不同类型的边引入了可学习的参数。每一种edge 对应一个，这样它就可以处理异构图。
  • 【融入节点特征】GGNN将结点特征作为隐藏状态初始化的一部分。
    • 用结点特征初始化各个结点的(部分)隐藏状态。
    • 对整张图，按照上述状态更新公式固定迭代若干步。
    • 对部分有监督信号的结点求得模型损失，利用BPTT算法反向传播求得和GRU参数的梯度。

GGNN的局限

  1. 【初始化影响很大】GNN依赖于不动点理论，所以每个结点的隐藏状态即使使用随机初始化都会收敛到不动点；GGNN则不同，不同的初始化对GGNN最终的结果影响很大。
  1. 【RNN的串行成本】两种基于循环的图神经网络在更新隐藏状态时不太高效。如果借鉴深度学习中堆叠多层的成功经验，我们有足够的理由相信，多层图神经网络能达到同样的效果。但每一次循环也可以看作是一次hierarchical feature extraction的方法。

基于多层神经网络的图神经网络

区分于传统CNN，图神经网络的难点在于处理邻居节点不固定上，因此本质是想找到适用于图的可学习卷积核。常见思路是：
  1. 提出一种方式把非欧空间的图转换成欧式空间。
  1. 找出一种可处理变长邻居结点的卷积核在图上抽取特征

空域卷积

  • GCN中通过级联的层捕捉邻居的消息，层与层之间的参数不同
  • GNN通过级联的时间来捕捉邻居的消息；可以视作层与层之间共享参数

消息传递网络MPNN

notion image
notion image
【缺陷】卷积操作针对的对象是整张图，也就意味着要将所有结点放入内存/显存中，才能进行卷积操作

图采样与聚合GraphSage

Graph Sample and Aggregate
利用采样(Sample)部分结点的方式进行学习
notion image
  1. 【随机采样】在图中随机采样若干个结点，结点数为传统任务中的batch_size。对于每个结点，随机选择固定数目的邻居结点(这里邻居不一定是一阶邻居，也可以是二阶邻居)构成进行卷积操作的图。
  1. 【聚合节点信息】将邻居结点的信息通过函数聚合起来更新刚才采样的结点。
      2. notion image
  1. 【计算采样结点处的损失】
      • 如果是无监督任务，我们希望图上邻居结点的编码相似
      • 如果是监督任务，即可根据具体结点的任务标签计算损失。

图结构序列化PATCHY-SAN

主要针对于图分类问题，将图结构转换成了序列结构，然后直接利用卷积神经网络在转化成的序列结构上做卷积
【转换的难点】需要保持图同构的性质（不同方法产生的序列应当相似）、邻居节点的连接关系（保持节点之间的距离关系，如邻居的阶数等）
notion image
notion image
  1. 【结点选择】根据人为定义的规则（如度、邻居度等）为系欸但指定排序，排序结束后，取出前n个节点作为整个图的代表
  1. 【邻居节点构造】以1中选出来的结点为中心，得到其一阶邻居与二阶邻居，排序选出前k个邻居，构成n个有序团
  1. 【图规范化】按照每个团中的结点顺序将团转成固定长度的序列，再将他们依次拼接，即可得到长度为(k+1)*n的全图序列（每个k+1不足时需要padding），再使用1D CNN进行建模、完成任务

频域卷积

主要利用的是图傅里叶变换(Graph Fourier Transform)实现卷积。简单来讲，它利用图的拉普拉斯矩阵(Laplacian matrix)导出其频域上的的拉普拉斯算子，再类比频域上的欧式空间中的卷积，导出图卷积的公式。相比于空域卷积而言，频域卷积更加具有理论基础。
当卷积核很大时，可以考虑使用快速傅里叶变换来减小卷积操作的时间开销。

傅里叶变换与拉普拉斯算子

notion image

图上的傅里叶变换

借助拉普拉斯算子，可以将图上的数据和信号转换到一个可以进行有效分析和处理的频域空间
notion image

Spectral CNN

notion image
  • 要计算拉普拉斯矩阵所有的特征值和特征向量，计算量巨大

ChebNet

应用切比雪夫多项式(Chebyshev polynomials)来加速特征矩阵的求解。
notion image

GCN

下面的视频把整个推导的数学过程写清楚了，关键就是使用Cheb Poly来对于计算卷积的过程进行加速，若需要使用，则需要满足特征值的值在[-1,1]内，而拉普拉斯矩阵使用度矩阵处理过后，能够满足特征值在[0,2]之内，再减去I即可满足要求。故构造了卷积核为的式子，代入化简之后即有GCN的hidden layer的表达式。
notion image
图卷积神经网络（GCN）的数学原理详解——谱图理论和傅立叶变换初探_哔哩哔哩_bilibili
图卷积神经网络（GCN）的数学原理详解——谱图理论和傅立叶变换初探共计4条视频，包括：1-warmup、2-spectral graph theory、3-fourier transformation等，UP主更多精彩视频，请关注UP账号。
图卷积神经网络（GCN）的数学原理详解——谱图理论和傅立叶变换初探_哔哩哔哩_bilibili
https://www.bilibili.com/video/BV1Vw411R7Fj/?spm_id_from=333.999.0.0
图卷积神经网络（GCN）的数学原理详解——谱图理论和傅立叶变换初探_哔哩哔哩_bilibili
notion image

全图的表示

前两章都是各个结点的表示，本章为全图的表示。图读出（ReadOut）操作，又称作graph coarsing/graph pooling，核心在于操作本身对结点顺序不敏感（同构图，图重构之后是等价的）

基于统计的方法

  1. 【直接压缩】在某一维中，采用平均(mean)，求和(sum)，取最大(max)等方式，将某一维度的信息量压缩了（数据的分布特性被完全抹除）。
  1. 【模糊直方图】类似直方图的方法来对每维数据分布进行建模，分开统计，平衡数据信息的压缩与增强。
    1. 预先定义几个高斯分布
    2. 对于任意特征值，求出其在各个高斯分布下的值
    3. 对该值进行归一化处理，最终得到一个多为的特征向量
    4. 再对该向量的每一个维度进行相应的运算
缺点：没法间接地、参数化地表示出结点到图的过程（得给出显式表达式）

基于学习的方法

采样加全连接

sample and FC
取固定数量的结点，通过全连接层得到图的表示
notion image
缺点：难以适用于规模差距很大的图（训练时见过的图只有几百个结点，但测试的图可能有上千个结点，很难进行泛化）

全局结点

global node
传统方法难点：
  1. 【寻找根节点】一般是根据domain knowledge来确定的
  1. 【结点差异化不明显】果直接用基于统计的方法对各个结点一视同仁，无法区别对待，如某些结点的信息更多，应该表达更多
故global node的思路是：
  1. 直接引入一个全局结点表示根节点
  1. 图中每个结一种特殊的边连接，最终拿这个结的表示作为图的表示

可微池化

notion image
differentiable pooling，可以实现层次化地获得图的表示。（不同于传统的”先通过GCN得到所有结点的表示，再通过方法汇总结点“）DiffPool可以同时完成结点聚类（soft clustering）与结点表示（node representation）
  1. 【结点表示】输入是各结点的隐藏状态，通过图上的传播，输出是传播后各个结点的表示
  1. 【结点聚类】输入是各结点的隐藏状态，输出是各结点属于不同聚类簇（预先定义好的）的概率
H为全图的隐状态矩阵，A为图的邻接关系，N为结点的个数，S为结点在各个聚类概率
H为全图的隐状态矩阵，A为图的邻接关系，N为结点的个数，S为结点在各个聚类概率
生成新子图的邻接关系如下：
notion image

图采样

对于GNN来说，其关键在于聚合邻居的信息，对应的式子如下：(其中A为邻接矩阵)
减少计算量，只采样部分邻居进行aggregation的计算
其关注点主要在于：
  1. 采样点是否是原图的无偏估计（下面都是无偏估计）
  1. 采样的方差越小越好（采样多次满足的方差）
对于下面三种方法的总结如下：
  • 无放回的均匀分布比有放回的采样更加稳定（方差更小）：
  • 有放回重要性采样比有放回均匀分布采样稳定：
  • 当k比较小时，有：

GraphSAGE

做了k次的无放回均匀分布采样，采样，其中为均匀分布
notion image

FastGCN

做的是有放回的采样：
  1. 有放回的均匀分布采样k次
    1. 有放回重要性采样（有权重取值）k次
        2. 使用拉格朗日乘子法可以得到当p(u)满足下面的式子时，整个方差最小（因为网络训练过程中会实时变化）

    DropEdge

    做n次伯努利采样，每次，
     
    上一篇
    笔记-计算机视觉
    下一篇
    笔记-软件工程
    评论
    Loading...