图网络的发展（简述）

简介：图(graph)是一个非常常用的数据结构，相比于网格状的数据结构，例如表格、图片等。它在现实世界中的表示形式非常的多，例如生活中的人类社交网络，蛋白体结构，国家内部的交通路网数据，知识图谱等，随着深度学习的发展，对于这些非结构化数据的建模引起了人们的重视，图学习成为了科研工作者关注的对象。图结构数据的学习越来越重要。

1.GCN 的首次提出与使用（SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS）

模型的主要贡献在于：

① 第一次使用谱图卷积（spectral graph convolutions） 的局部一阶近似，来确定卷积网络结构。 

② 模型在图的边数上进行了线性缩放。 

③ 模型学习通过卷积后的隐藏层表示，这些表示既能够编码局部图结构（就是想到与获取到了特征）、也能够编码节点特征（对于每一个节点，也得到了特征）。 通过大量的图结构数据的学习，和图中部分有标签的节点数据对GCN卷积神经网络结构模型的训练，使网络模型具备了对图中剩余无标签的数据的特征学习，促进了进一步分类的可能。

2. GAT (Graph Attention Networks,  ICLR 2018)

在该文中，作者提出了网络可以使用masked self-attention层解决了之前基于图卷积（或其近似）的模型所存在的问题（1.图中对于每一个点的邻居信息都是等权重的连接的，理论中每一个点的实际权重应该不同。这样可以避免噪声连接带来的问题）。因此，作者在GAT中，使用了attention机制，使得图中的每个节点可以根据邻节点的特征进行对应的区分和辨别，为其邻居对于自己信息的贡献进行分配不同的权值，避免了GCN可能出现的缺点。然后GAT也还有另一个优点，他能够无需使用预先构建好的图（即不需要事先就构造好对应的图结构）。这样的话，赋予了GAT可以解决一些基于谱的图神经网络中所具有的问题。最后的论文实验中，作者提出的GAT模型可以有效地适用于图类型的归纳学习和转导学习问题，相比于GCN具有了更好的结果（下图为对应的attention机制方式）。

总结起来：GAT相对于之前提出的方法的优点在于

① 与文章1的GCN结构是类似的，GAT也采用了局部网络的方式。这样带来的好处就是（主要是相对于GNN和GGNN等网络）训练GAT模型的时候我们不再需要去了解整个图结构的类型，图的构成样子了，我们仅仅需要去知道每个节点的邻节点即可。

② 同样的道理，GAT与GCN都有着各自不同的邻居节点信息更新方式。其中相对于GCN使用的的方法，GAT使用self-attention方式为每个节点的周围邻居节点分配权重，也就是说，GAT的节点更新方式的具体实例如图所示。从理论和实验中的结果都表明，这种attention分配权重的方式帮助了GAT能够有更好结果。通过attention的计算，GAT在计算新的节点表示时引入了一个权值矩阵，不再是一个0,1邻接矩阵。

3. GIN (Graph Isomorphism Networks， ICLR 2019 ）

本文的主要出发点就是GNN虽然有效，但是其存在很大的问题：

①.网络结构的设计上面，GNN模型的设计来自于经验，经验的多少直接影响了最后网络结构的好坏，②也就是所GNN为什么能够取得很好的模型效果同样的缺乏非常少的理论性的理解。使得学习和设计GNN结构变得很难。

同样的本文的贡献在于： ①证明了GNN在最好情况下和 Weisfeiler-Lehman (WL) test达到一样的效果。②文中提供了构建GNN的设计方式，这样才可以使得它和WL一样有效的方法。 ③文中分析了GCN和GraphSAGE模型的差异和相同点，最后这提出了种设计方式下的能够与WL test一样有效的GIN模型。

具体方法就是：本论文参照了WL test的方式，把主要的GNN模型实现过程拆分为三个步骤 主要步骤：

① Aggregate：当前节点的所有邻居如何整合 

② Combine：邻居和当前节点如何整合 

③ READOUT：所有的节点如何整合

图中展示的为通过实验分析得到的最后融合邻居信息的方式：得出了结论：

在aggregate的常用设置中，排名：sum > mean > max

全文总结：至此关于GNN结构的三篇开门的论文已经介绍完毕了，论文的主要贡献点和主要的思路已经列举出来了，这三个论文的学习对于后面的许多论文关于 GNN 论文的学习都是非常重要的，是它们的基础。希望大家能够有所收获。

参考文献：

[1] Kipf, T. N., & Welling, M. (2016). Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907.

[2] Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., & Bengio, Y. (2017). Graph attention networks. arXiv preprint arXiv:1710.10903.

[3] William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. Neural Information Processing Systems (NIPS), 2017.

[4] Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodol`a, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. arXiv preprint arXiv:1611.08402, 2016.

[5] Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2018). How powerful are graph neural networks?. arXiv preprint arXiv:1810.00826.

[6] Li, Qimai, Zhichao Han, and Xiao-Ming Wu. "Deeper insights into graph convolutional networks for semi-supervised learning." Thirty-Second AAAI Conference on Artificial Intelligence. 2018.