基础信息

Title: A Gentle Introduction to Graph Neural Networks(blog)
Authors: Google Research

一篇发表在distill网站上的博客

什么是图

G = (V,E) V：顶点， E：连边
例如：分子图，社交图，图片、文字某种意义上也可以视为图

图上面可以定义什么问题？

第一，graph-level problem：例如，一个分子图里有几个苯环？
第二，node-level problem：例如，一个化学键断裂后，两端的原子分别和其余原子是否连接？
第三，edge-level problem：例如，图片编辑，将图片语义分割，判断各个成分之间的关系？

Graph类型数据给Neural Network带来的挑战

一方面，graph内部的信息包含：顶点，边，全局信息和连通性。其中顶点、边和全局信息都可以方便地用向量进行表示，而连通性如果用邻接矩阵表示，存储的代价很大，如果使用稀疏矩阵表示，则GPU计算效率很低。
另一方面，邻接矩阵的表示顺序相关，而实际上连通性顺序无关。
为解决这两个问题：可以使用邻接列表。

图神经网络GNN

GNN：一个图上所有属性的进行的一个优化变换，这些属性可以包括节点、边、全局信息等，该优化可以保持图对称信息
结构框架：消息传递网络MPNN，graph-in，graph-out

分类

  1. GCN
  2. GIN
  3. Graphormer
    …

Limitations & Future

后来我又自己读了一篇博客：Issues with graph neural networks: the cracks are where the light shines through。文中提到，CNN让图像处理从classical feature engineering转为differentiable feature learning，后者又称可微特征学习，即不需要专家知识设计特征，而是利用神经网络可导的性质让其自动学习数据中潜在的特征。归纳文章中总结的GNN的缺陷：
第一，expressivity表达能力不足。有文章[2]在理论上分析，发现像GCN这样的模型并不具有分析一些图结构的能力。为解决这一问题，Xu et al. 设计了graph isomorphism network(GIN)模型，该模型在许多问题上都取得了SOTA，与Weisfeiler-Lehman graph isomorphism test的表达能力近似相同。
第二，GNN的初始embedding包含的信息不足。例如，在小数据分子数据集上，GNN需要从头学习丰富的分子空间信息，导致其表现并不理想。可以使用预训练的方式缓解这个问题。
第三，过拟合。GNN的层数不能加的很深，原因是连续卷积的分子特征变得无法区分。（为什么呢？）Liu et al. [3]提出的工作提供了GNN模型过拟合原因的insight，并提出了加深GNN模型的方法。
第四，信息丢失。GNN的全局信息一般需要通过一个Pooling池化层，一般是各个节点的特征向量取最大值或是平均值，可能造成严重的信息丢失。针对这个问题，Navarin et. al. [4]提出了一种Pooling方法，可以近似任何连续且permutation无关的向量函数。
第五，感受野的局部性。和ECFP分子指纹的设计相似，大多数GNN都是基于邻域聚合的策略，这就限制了模型感受野的大小，导致距离较远的一些节点之间信息无法流动。而Transformer模型具有更广阔的模型感受眼，Ying et al. [5]提出了Graphormer模型，并在理论上证明GCN、GIN等模型是某种特殊情况下的Graphormer。

[1] Understanding Convolutions on Graphs(blog)
[2] Xu, Keyulu, et al. “How powerful are graph neural networks?.” arXiv preprint arXiv:1810.00826 (2018).
[3] Liu, Meng, Hongyang Gao, and Shuiwang Ji. “Towards deeper graph neural networks.” Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2020.
[4] Navarin, Nicolò, Dinh Van Tran, and Alessandro Sperduti. “Universal readout for graph convolutional neural networks.” 2019 International Joint Conference on Neural Networks (IJCNN). IEEE, 2019.
[5] Ying, Chengxuan, et al. “Do Transformers Really Perform Bad for Graph Representation?.” arXiv preprint arXiv:2106.05234 (2021).