一篇GNN综述的笔记。原文。
序
本文中用到的数学符号预定义如下。
GNN Design Pipeline
图设计流程大致分为以下四点
找到图结构
找到任务中的图结构，结构场景如分子，知识图等；非结构场景如为文本建立“词”图，或者为图像构建场景图。
确定图 type & scale
找出图后，要找出其类型以及尺度。
图通常分为
- 有向/无向图。
- 齐次/异构图。齐次，homogeneous，即图中节点和边具有相同的类型。异构，heterogeneous，即节点和边有着不同类型。
- 静态/动态图。static/dynamic graph。区别在于输入或是图的拓扑结构是否考虑时间变化。
上述的分类准则是正交的，也就是说可以将其排列组合而不冲突地定义图。还有一些因任务定义的图，例如超图 hypergraphs 和符号图 signed graphs。
至于图 scale，很难量化的定义小或者大，通常在其邻接矩阵难以被设备存储处理时称为大规模图，相应的处理该类问题是要考虑一些 sampling 方法。
设计loss
常见的任务如下
- node level。节点级任务包括：节点分类 node classification，节点回归 node regression，节点聚类 node clustering。
- edge level。边级任务包括：边分类 edge classification，链路预测 link prediction。
- graph level。图级别任务包括：图分类 graph classification，图回归 graph regression，图匹配 graph matching。
任务还可以从监督的角度分类
- supervised
- semi-supervised 。测试时，transductive 要求模型预测给定的未标记的标签，inductive 提供新的未标记标签来推断。
- unsupervised 没有标记数据，如clusting
为不同的任务设置loss，如分类任务的交叉熵损失。
模型搭建
模型搭建中需要使用计算模块，如
- propagation module：传播模块用于在节点之间传播信息，以便聚合的信息可以捕获特征和拓扑信息。其中convolution operator和recurrent operator 常用于聚合信息，skip connection跳过链接操作用于从节点历史表示中收集信息，缓解过平滑问题。
- sampling module：图很大时，需要通过 sampling 对图进行 propagation
- pooling nodule：当我们需要高级子图或图的表示时，需要 pooling 从节点中提取信息。
1 | Sampling：侧重于从大型图中选择子图或节点子集，以降低计算和存储开销，保持数据的代表性和信息丰富度。而Pooling：侧重于将整个图的局部信息整合成一个全局表示，通常是为了进行更高层次的图级任务。 |
GNN的搭建范式如下
计算模块
计算模块的概述如下
接下来我们将简介各部分
propagation-convolution opertor
图中的 convolution 来自CNN推广至图领域中，其主要分为 spectral 光谱方法和 spatial 空间方法。
spectral approaches
首先使用图傅里叶变换将图信号 x 变换至谱域，进行convolution，再使用逆变换得到结果，即
其中 U 是图 laplacian 矩阵的归一化后特征向量矩阵，计算方式如下。
convolution 的计算为
其中 UT g 是谱空间的滤波器。我们使用可学习的矩阵 gw 进行简化。
几种常见的谱方法
- spectral network：Spectral Networks and Locally Connected Networks on Graphs
- chebnet：Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
- GCN：Semi-Supervised Classification with Graph Convolutional Networks
- AGCN
- DGCN
- GWNN
spatial approaches
空间方法基于图拓扑直接在图上定义卷积。空间方法的主要挑战是定义具有不同大小邻域的卷积操作，并保持 CNN 的局部不变性。