图卷积神经网络
目录：
为什么有图卷积神经网络
自2012年以来，深度学习在计算机视觉以及自然语言处理两个领域取得了巨大的成功。 和传统方法相比，它好在哪里呢？
假设有一张图，要做分类，传统方法需要手动提取一些特征，比如纹理啊，颜色啊，或者一些更高级的特征。
然后再把这些特征放到像随机森林等分类器，给到一个输出标签，告诉它是哪个类别。
而深度学习是输入一张图，经过神经网络，直接输出一个标签。
特征提取和分类一步到位，避免了手工提取特征或者人工规则，从原始数据中自动化地去提取特征，是一种端到端（end-to-end）的学习。
相较于传统的方法，深度学习能够学习到更高效的特征与模式。
卷积神经网络很好，但是它研究的对象还是限制在Euclidean domains的数据。
什么是Euclidean data？
Euclidean data最显著的特征就是有规则的空间结构，比如图片是规则的正方形栅格，比如语音是规则的一维序列。
而这些数据结构能够用一维、二维的矩阵表示，卷积神经网络处理起来很高效。
但是，我们的现实生活中有很多数据并不具备规则的空间结构，称为Non Euclidean data。
比如推荐系统、电子交易、计算几何、脑信号、分子结构等抽象出的图谱。
这些图谱结构每个节点连接都不尽相同，有的节点有三个连接，有的节点有两个连接，是不规则的数据结构。
可以很明显的感受到，图有两个基本的特性：
一是每个节点都有自己的特征信息。
比如针对上图，我们建立一个风控规则，要看这个用户的注册地址、IP地址、交易的收货地址是否一样，如果这些特征信息不匹配，那么系统就会判定这个用户就存在一定的欺诈风险。
这是对图节点特征信息的应用。
二是图谱中的每个节点还具有结构信息。
如果某段时间某个IP节点连接的交易节点非常多，也就是说从某个IP节点延伸出来的边非常多，那么风控系统会判定这个IP地址存在风险。
这是对图节点结构信息的应用。
总的来说，在图数据里面，我们要同时考虑到节点的特征信息以及结构信息，如果靠手工规则来提取，必将失去很多隐蔽和复杂的模式，那么有没有一种方法能自动化地同时学到图的特征信息与结构信息呢？
——图卷积神经网络
什么是图卷积神经网络
图卷积神经网络（Graph Convolutional Network）是一种能对图数据进行深度学习的方法。
图卷积算子：
\[h^{(l+1)}_i = \sigma(\sum_{j \in N_i} \frac{1}{c_{ij}} h^{l}_j W^l_{R_j})\]上面给出的是图卷积算子的计算公式，设中心节点为i；
\(h^l_i\)：节点i在第l层的特征表达
\(c_{ij}\)：归一化因子，比如取节点度的倒数
\(N_i\)：节点i的邻居，包含自身
\(R_i\)：节点i的类型
\(W_{R_i}\)：\(R_i\)类型节点的变换权重参数
如何理解图卷积算法？我们看动图分三步去理解（注意不同颜色代表不同的权重）：
第一步：发射（send）每一个节点将自身的特征信息经过变换后发送给邻居节点。
这一步是在对节点的特征信息进行抽取变换。
第二步：接收（receive）每个节点将邻居节点的特征信息聚集起来。
这一步是在对节点的局部结构信息进行融合。
第三步：变换（transform）把前面的信息聚集之后做非线性变换，增加模型的表达能力。
图卷积神经网络具有卷积神经网络的以下性质：
1、局部参数共享，算子是适用于每个节点（圆圈代表算子），处处共享。
2、感受域正比于层数，最开始的时候，每个节点包含了直接邻居的信息，再计算第二层时就能把邻居的邻居的信息包含进来，这样参与运算的信息就更多更充分。
层数越多，感受域就更广，参与运算的信息就更多。
我们来看GCN这个模型框架，输入是一张图，经过一层一层计算变换，最后输出一张图。
GCN模型同样具备深度学习的三种性质：
1、层级结构（特征一层一层抽取，一层比一层更抽象，更高级）；
2、非线性变换 （增加模型的表达能力）；
3、端对端训练（不需要再去定义任何规则，只需要给图的节点一个标记，让模型自己学习，融合特征信息和结构信息。）
GCN四个特征：
1、GCN 是对卷积神经网络在 graph domain 上的自然推广。
2、它能同时对节点特征信息与结构信息进行端对端学习，是目前对图数据学习任务的最佳选择。
3、图卷积适用性极广，适用于任意拓扑结构的节点与图。
4、在节点分类与边预测等任务上，在公开数据集上效果要远远优于其他方法。
怎么用图卷积神经网络
下面分享一个我们在实际应用场景中的实验：
实验输入是一个验证数据构成的图数据，节点是验证事件以及事件相关的属性节点。
如IP，DeviceID，UA等节点。（我们总计用了30天的验证数据，每两个小时的数据构成一张图，共360张图。）
实验输出是对事件节点进行人机分类，正常或者异常。
实验细节
网络结构：
GCN(128)->GCN(64)->GCN(64)->Linear(2)
训练: Adam优化器, lr=0.001
参照基准: 以只能学习特征信息的GBDT做为基准, grid_search 搜索超参数，GBDT是目前最流行的浅层分类器。
我们用第一天的数据做训练，持续30天预测结果如下：
GCN模型的准确率衰减比较小，而GBDT的衰减很严重。可见，GCN模型的人机判别效果要好，鲁棒性好。
实验输出是对事件节点进行人机分类，正常或者异常。
论文阅读
##基于attention的半监督GCN
图卷积对图中节点的特征和图结构建模，
本文中作者首先移除图卷积中的非线性变换，发现在GCN中起关键作用的是传播层，而不是非线性感知层。
然后提出AGNN模型，在传播层引入attention机制，使中心节点特征的聚合过程中，对邻居节点的注意力产生差异。
模型在benchmark测试用的文献引用数据集上的效果优于其他state-of-the-art的方法。
并且，通过传播矩阵计算节点之间的关联强度，得到了一些更有趣的信息。在预测目标节点类别时，与预测类别相同的邻居节点将会在此过程中，承担了比其他邻居节点更重要的角色。
Graph Neural Network
回顾半监督GCN，交替叠加两次传播层和感知层， 模型第l层的隐含状态 \(H^{(l)} \in R^{(n×d_h)}\)。
\[H^{(1)} = ReLU((PX)W^{(0)})\] \[Z = f(X,A) = softmax((PH^{(1)})W^{(1)})\]其中，\(P=\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} , \tilde{A}=A+I\)。
非线性激活函数ReLU。参数\(W^{(0)}\)和\(W^{(1)}\)通过在所有标记样本集合L上，最小化损失函数，训练得到：
\[L=-\sum_{i \in L} \sum_{c=1}^{d_y} Y_{ic} lnZ_{ic}\]为了更好的理解GCN，作者将GCN中的非线性变换剔除，只保留传播层，称为GLN。这样GLN模型就是一个简单的线性模型。
\[Z = f(X,A) = softmax((P^2 X)W^{(0)}W^{(1)})\]与GCN中一样，\(P=\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}\)，权重矩阵\(W^{(0)}\)和\(W^{(1)}\)是最小化损失函数训练得出。
两个传播层只是简单的对邻居节点特征加权求平均，权重为节点的度，输出层也是一个线性分类器。
如此，分离出线性传播层和非线性感知层。GLN与其他方法的表现对比，如表2。
比较GCN和GLN，GLN的准确度甚至更高，这表明对提升模型表现至关重要的是传播层，而不是感知层。
其他不使用图卷积的方法对比，GLN模型在准确度上有明显差距。
基于这个结果，考虑使用attention机制，替换GLN中的线性传播。
AGNN
原始的GCN和其他图神经网络使用的是静态，无法自适应的传播法则。无法捕捉中心节点的哪个邻居节点对于中心节点的分类贡献更大。真实数据并非所有的边都是代表着相同的关联强度，其中必然有一些才是至关重要的。基于GLN的实验结果，提出了作用与邻居节点集合的attention机制，它可以学习到分类模型中，那些邻居与中心节点更相关，并相应的权衡他们的贡献。 AGNN第一层网络与原始GCN一样，参数矩阵将节点特征X转化为长度为的特征向量，激活函数使用ReLU。
在每个传播层加入参数化的注意力引导机制，参数为。
这样，对于节点i的输出向量为：
其中传播矩阵也是关于第l层状态和参数的函数。attention中的softmax函数是确保传播矩阵每行的和为1，代表邻居节点对中心节点的影响力总和为1。这样从节点j到i的注意力为 ：
计算节点i和节点j在第l层隐含状态的余弦距离，它捕捉了节点j到节点i的关联程度。注意力机制更倾向于选择那些与中心节
参考文献：
https://mp.weixin.qq.com/s?__biz=MzI2MDE5MTQxNg==&mid=2649687812&idx=2&sn=c287f48f04b4755577da8ce46c487582&chksm=f276c2d3c5014bc57aaa25c7c50d87ba6d46762d79e1aa5761325bed25955be578253811ff60&scene=21#wechat_redirect
https://mp.weixin.qq.com/s/608gphuB3TNM4t4wfBXR5g
https://blog.csdn.net/chichoxian/article/details/52760647
https://yq.aliyun.com/articles/277878
http://tech.ifeng.com/a/20171130/44784612_0.shtml
http://smart.huanqiu.com/roll/2016-06/9059499.html?agt=56
https://blog.csdn.net/mmc2015/article/details/49833713
https://blog.csdn.net/mmc2015/article/details/49777447
https://zhuanlan.zhihu.com/p/45624929
https://mp.weixin.qq.com/s?__biz=MzI2MDE5MTQxNg==&mid=2649687812&idx=2&sn=c287f48f04b4755577da8ce46c487582&chksm=f276c2d3c5014bc57aaa25c7c50d87ba6d46762d79e1aa5761325bed25955be578253811ff60&scene=21#wechat_redirect
https://mp.weixin.qq.com/s?__biz=MzI2MDE5MTQxNg==&mid=2649687693&idx=1&sn=1dc186d11b7c802ef518b32785c78e4a&chksm=f276c35ac5014a4cfb7d8fa6eb636ba011c99f519f6079512370fbfcc2cd5a37a739de72a7f2&scene=21#wechat_redirect