本文是发表在KDD会议上的一篇文章，以大规模可学习图卷积神经网络为研究内容，作者来自于华盛顿大学。在笔者看过的很多graph embedding的论文中，华盛顿大学出现过很多次，看来在该领域华盛顿大学很优秀呀。言归正传，我将从以下三个方面，相关工作、模型算法、实验设计进行总结阐述。
1. 相关工作
众所周知，深度学习领域，卷积神经网络CNN功能强大，无论是在图像识别，自然语言处理，机器翻译等领域，都有很出彩的表现。大规模减少权值参数的同时，避免了人工特征提取。然而，传统卷积核是应用在网格样式(grid-like)的数据上，图片也是由一个个规则的像素矩阵构成的。因此，规则卷积需要网格化数据。其实，网格数据在一定程度上，是一种特殊类型的图数据。
当面对现实世界中普遍存在的网络结构样式的图数据时，由于每个节点的邻居节点数目不同，邻居节点之间没有自然的顺序关系，强大的CNN神器要想在graph上发挥作用，受到严重的限制。图数据的应用主要在于节点分类问题，基于图中网络关系和节点自身特征对节点进行分类预测。传统的方法是进行graph embedding等操作，这也是一个重要的研究领域。
1.1 GCN图卷积神经网络
借鉴谱图卷积理论，图卷积神经网络GCN被提出，并且在cora等引文网络的数据集上取得了显著的效果。GCN网络的层间前向传播规则，也是GCN的核心原理（详见另一篇笔记），如下所示：
在该公式中，是对角化的节点度矩阵，
是加入自环连接的邻接矩阵，
是训练过程中进行学习的各层参数。本质上讲，GCN并不是严格意义上的卷积网咯，它只是借鉴卷积计算思想的聚合操作，将节点的邻居节点信息“卷积”到节点自身，在此过程中，邻居节点的地位是相等的，简而言之，只是做了算数平均。而且，
对于一个特定的网络而言，是固定的，不可训练的。和CNN通过学习局部滤波器权重，自动提取特征相比逊色不少。GCN不可训练的聚合操作限制了图数据中CNN的特征提取能力。
1.2 GATs图注意力机制
注意力机制需要在节点和其邻居节点间进行额外操作，也会带来存储和计算资源的消耗问题。GCN中的算数平均聚合用特征向量加权和取代。公式如下：
注意力机制之前没有接触过，会作为一篇笔记进行专门总结，到时候这部分再更新。
2. 模型算法
本文的算法创新点主要在于以下两个方面，可学习的图卷积层和针对大图的子图训练策略。
为了充分利用CNN的规则卷积核进行空间平移从而自动提取特征的优点，需要将网络结构的图数据转化为网格数据。首先要解决的两个问题是节点邻居数标准化和邻居节点顺序的选择。本文作者是这样进行解决的，如图所示：
第一次看到这个构建过程，觉得既简单又巧妙，该例子不仅蕴含着最大化降采样原理，还有1d卷积核的应用，这里k取4，k是一个超参数，k的选取很重要，一般k 的选择，考虑节点的平均度数以及分类任务的复杂性。在三个特征维度上选择每一维选最大的四个值进行组合，所以这里的节点并不是真是邻居节点特征，是经过加工之后的，有max-pooling的感觉，不仅解决了树木标准化为4们还按照大小顺序排好序。节点特征向量是三维，视为三个通道channel，由于只有一个橘色节点，因此batch_size为1，卷积核kennel对应的也是三通道，filter个数是4，即
但是这样的解决方法是有前提的，每个节点的邻居节点个数足够多（保证基本大于k且基本均匀，对于非常稀疏的大量孤立节点存在的网络,k取得值很小，邻居节点间特征传播没有意义）。一般对CNN来讲，深度卷积的效果可能更好一点，但是，GCN的层数一般是2-3层，层数过高，会造成过拟合。
结合图卷积网络，构造可学习的图卷积，在DCNN之前增加了一个图嵌入层（graph embedding）,将高维图数据（节点特征）低维度表示，,不经过激活函数，则还是特征表示。同时，
和
，并且
实现了节点特征从高维空间降低维空间的映射。
大规模网络数据的子图训练，借鉴随机抽样，裁剪补丁的思想，通过裁剪大图获得用于训练的小图。子图选择算法我们通过下图直观理解，算法步骤如下：
1.随机采样，得到初始节点（图中三个橘色节点）
2.广度优先搜索，为子图迭代扩充邻居节点
3.$N_m$每次迭代可置不同值（第一次5个蓝色节点，第二次7个一蓝色节点为中心绿色邻居节点）
4.初始节点和迭代搜索到的节点，总共15个节点，作为训练的子图样本
综上所述，本文提出的模型算法流程应该是这样子滴：
如图所示，图数据的研究，无论是节点分类还是链路预测等应用，归根结底，都是由其本质特征决定的，即相较于传统的一维数据、图像数据、文本数据，图数据不仅具有节点甚至边的自身特征，还有节点间的网络关系。不同于graph-embedding常用的node2vec先做特征衍生，再跑机器学习模型的做法，图深度学习将特征提取和模型训练合并进行。子图选择算法尤其适用于具有若干社区，社区间联系稀疏，社区内关系紧密的情况 。GCN在本文模型中仅仅作为embedding降维的工具，这个工作node2vec也可以进行，不过时间效率可能不及GCN。最关键的步骤就是黄色部分，实现了非欧到欧式空间的网格化抽象转化，以及邻居节点的统一有序排列。为直接应用CNN的可行性提供基础。这样做还有一个好处，我们知道图深度学习，按照目前GCN的做法，隐藏层只有两到三层，层数增加之后，带来的过拟合现象，同时，GCN隐藏层的作用本质上是将邻居节点信息卷积到当前节点上，随着隐藏层加深，所有节点会最终被同质化为同一个节点，使得模型退化，即图深度学习并不“深”。但是按照本文的做法，最后用传统卷积神经网络做，相当于一个标准的一维卷积问题(1d-cnn)，原理上讲，不存在上述这个问题，设计深层模型应该没有问题。这里仅是笔者猜测，没有做实验论证，以后有时间补上。
3.实验设计
本文的实验数据集如下图所示，采用经典的引用网络数据集Cora，Ci'te'se'r以及Pubmed，前两个数据集节点数只有两三千，特征维数上千，这种情况一般是embedding之后表示学习的结果，比如Cora的特征就是文本数据关键词one-hot编码后的结果，文中指出是bag-of-word文档表示后得到的特征向量。从Degree一列可以看出，网络中节点的度数不低，平均或最高（由于论文作者没有阐述该列含义，此处为笔者猜测）节点度数4-6个，网络不是特别稀疏。
我们注意到，在实验设置的时候，有Transductive和Inductive之分，Transductive是转化学习，是指在训练过程中，无标签节点的网络结构和特征向量是已知的，是一个半监督学习的过程；Inductive是归纳学习，是指训练过程中，测试样本是不存在的，包括待测节点的特征向量和网络结构，这篇文章的PPI数据集就属于这种情况，作者在切分训练集验证集测试集时，直接按照子图切分的，也就是说测试过程是在一个新的图上进行的。之前看的一篇文章《Revisiting Semi-Supervised Learning with Graph Embedding》中就这两个问题进行了一些描述，等下次再写，这里不赘述了。个人感觉，Inductive和动态网络的节点分类问题还不太一样，动态网络是指网络中节点可以随时进出，这部分动态进出的节点并不是孤立的一个子图，所以不能把这部分工作当作是动态检测的参考案例。
Transductive部分的三个数据集都采用了GCN作为embedding层进行降维，然后各自分别堆叠2，1，1层LGCLs(就是网格化接1d-cnn)，最后用全连接分类器做预测。对于Inductive，作者采用子图方式训练，网络结构基本不变。主要是embedding,k,dropout,L2正则化的参数设置上，根据问题规模进行相应调整。
作者还对网格化过程的模型中，k值选择的科学性进行研究，经过实验，他认为k的选择应当比平均节点度数大一点（由此我们推出前文数据集表格中的degree是指图的平均节点度数）。但具体值仍然需要是通过实验来选择。
好了，就说到这里了，第一次写论文笔记，一些不到位的地方，欢迎大家批评指正。
作者原创，欢迎交流，如需转载请先联系作者。
