GNN General Introduction

Posted on | Edited on | In ,

Introduction

Graph Neural Network， 出现原因：CNN：基于欧式空间，如果按照CNN对图进行卷积，每个节点的邻接节点不一样->无法实现权重共享，但同时我们想从图中提取特征信息。
应用数据：社交网络，化学，图像，文本等等。

GNN 介绍

整个GNN的过程可以分成两个部分：特征计算和结果计算，即图中的 $f$ 和 $g$，$f$ 的思路和embedding很相似，就是对每一个节点生成一个描述它的feature，不同的是除了节点，边和整个图的feature也可以生成，$g$ 就是根据计算出的feature输出对应的结果，比如类别等。
写成公式就是：
$$
\begin{aligned}
x_n&=f_w(l_n,l_{co(n)},x_{ne(n)},l_{ne(n)})\o_n&=g_w(x_n,l_n)
\end{aligned}
$$
GNN Structure
$g$ 和CNN的FC层很相似没什么特殊的，GNN的重点也放在了feature $x_n$的计算上。

根据09年[1]提出的初始GNN的思路，$x_n$的计算方法其实是进行不断的更新直到收敛，所以把上面右图就是左图按照时间计算展开。

其实上面的初始GNN计算方法只确定了如何对每个节点计算feature，后来在它的基础上出现了各种边的计算方式，最终[2]总结并且把整个GNN模型整合在了一起。

GN Block

每一个GN Block中，$e_n, v_n, u$，$e_n$ 和 $v_n$ 分别代表了每条边和节点的对应属性，$u$ 是整张图的 global attribute，根据最后task的需要选择需要的属性进行输出。

GN propagate
整个前馈过程其实也只有两个部分：$\phi$作为更新函数(update)，$\rho$ 作为聚合函数(aggregate)，前者更新各种feature的值，后者将所需要的值聚合在一起用于后面进一步的更新。
下面这张图就是一个完整的GN Block的更新过程。
GN FULL

多个GN Block的问题，这两个都属于拥有多个GN Blocks时候的不同组合方法，像自编码器和RNN循环时通过的是同一个GN Block，只是GRNN会多加隐层，也可以将不同结构的GN Blocks组合在一起使用。
GNs

GNN 分类

其实GNN的诞生过程非常的混乱，不同的人提出的东西各式各样，虽然论文[2]给了整个GNN一个通用的模型，但是里面的细节变化导致GNN有了各种各样的类别，清华的survey[3]里给了我们一个详细的分类如下图：
GN category

在这里我做了一个更加简单一点的分类方式，把整个GNN分成两类，第一类是按照结构来说：
GN blocks
第一张图就是一个完整的GN Block的更新过程，根据这个更新过程又产生许多变化：比如最典型的MPNN(Message Passing Neural Network)[4]，它是基于RNN提出的思想，把Edge的更新看作一个隐层，训练之后参与节点的更新。

第二类是按照更新和聚合方法来说：
GN category2
这张图还是清华的survey整理的，就用GCN拿出来当个例子，一般来说更新函数都默认是一个神经网络，但是就像前面提出的，我们希望能实现权值共享，所以GCN定义了全新的卷积方式解决邻接节点不同时的权值共享问题，于此同时和CNN一样，不同的卷积核可以提取不同的特征，利用不同卷积核的GCN更新也可以最终计算出一个高维度包含不同特征的feature。

工具

pytorch：geometric

tensor flow: graph_nets

相关论文

清华的综述[3]还整理了GNN的论文列表。

论文列表

问题

  1. 浅层结构
    GNN的收敛 -> $f$ 是一个压缩映射 -> 层数高梯度消失
  2. 算力

GNN Visualization

论文：Graph-structured representations for visual question answering[7]
Question Answering

GNN for Dynamic Graph

论文一：EvolveGCN[5]
前提：所有的图都是随着时间动态连续变化的。
没有考虑位置关系，利用RNN的思想加入隐层记录前时刻的特征值。
Application: Link prediction & Edge classification
EvolveGCN

论文二：Predicting Citywide Crowd Flows in Irregular Regions Using Multi-View Graph Convolutional Networks[6]
STG: spatio-temporal graph

  1. Convolutional networks over graphs
  2. Spatial graph convolutional network
    $$
    w_{ij}=\begin{cases}
    exp(-\frac{dis(ij)^2}{2\theta}) &\text{if dis(ij)$\lt$ k}\
    0 &\text{otherwise}
    \end{cases}
    $$

STG

Node Importance and Influence

论文：DeepInf: Social Influence Prediction with Deep Learning[8]
Node Importance

Reference

[1] Monfardini, G., Ah Chung Tsoi, Hagenbuchner, M., Scarselli, F., & Gori, M. (2008). The Graph Neural Network Model. IEEE Transactions on Neural Networks, 20(1), 61–80.

[2] Battaglia, P. W., Hamrick, J. B., Bapst, V., Sanchez-Gonzalez, A., Zambaldi, V., Malinowski, M., … Pascanu, R. (2018). Relational inductive biases, deep learning, and graph networks, 1–40.

[3] Zhou, J., Cui, G., Zhang, Z., Yang, C., Liu, Z., & Sun, M. (2018). Graph Neural Networks: A Review of Methods and Applications, 1–20.

[4] Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., & Dahl, G. E. (2017). Neural Message Passing for Quantum Chemistry.

[5] A. Pareja et al., “EvolveGCN : Evolving Graph Convolutional Networks for Dynamic Graphs,” 2018.

[6] J. Sun, J. Zhang, Q. Li, X. Yi, and Y. Zheng, “Predicting Citywide Crowd Flows in Irregular Regions Using Multi-View Graph Convolutional Networks,” vol. 14, no. 8, pp. 1–11, 2019.

[7] D. Teney, L. Liu, and A. Van Den Hengel, “Graph-structured representations for visual question answering,” in Proceedings - 30th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, 2017, vol. 2017–Janua, pp. 3233–3241.

[8] J. Qiu, J. Tang, H. Ma, Y. Dong, K. Wang, and J. Tang, “DeepInf: Social Influence Prediction with Deep Learning,” 2018.