GNN系列 综述 GNN GCN GraphSAGE GAT 简单理解 及调优Trick
1. 图与GNN背景
1.1 图
图(graph)是一种数据结构，图神经网络(Graph Neural Network)应该是深度学习在图结构数据上的一些模型、方法和应用。常见的图结构由节点(node)和边(edge)构成，节点包含了实体(entity)信息，边包含实体间的关系(relation)信息。
图是用以表示实体及其关系的结构，记为 G=(V,E) 。图由两个集合组成，一是节点的集合 V ，一个是边的集合 E 。 在边集 E 中，一条边 (u,v)连接一对节点 u 和 v ，表明两节点间存在关系。
关系可以是无向的， 如描述节点之间的对称关系；也可以是有向的，如描述非对称关系。 图可以是 加权的 或 未加权的 。在加权图中，每条边都与一个标量权重值相关联。例如，该权重可以表示长度或连接的强度。 图可以是 同构的 或是 异构的 。在同构图中，所有节点表示同一类型的实体，所有边表示同一类型的关系。
现在许多学习任务都需要处理图结构的数据，比如物理系统建模(physics system)、学习分子指纹(molecular fingerprints)、蛋白质接口预测(protein interface)以及疾病分类(classify diseases)，这些都需要模型能够从图结构的输入中学习相关的知识。
在工业界的应用，主要是下图所示：
1.2 GNN起源
GNN起源于两种动机，一种动机来自于卷积神经网络(CNN)，另一种动机来自于图嵌入(graph embedding)。
第一种来源于CNN，CNN能够提取出多尺度的局部空间特征，并将它们进行组合来构建更加高级的表示(expressive representations)。如果深入研究CNN和图结构的特点，可以发现CNN的核心特点在于：局部连接(local connection)，权重共享(shared weights)和多层叠加(multi-layer)。这些同样在图问题中非常试用，因为图结构是最典型的局部连接结构，其次，共享权重可以减少计算量，另外，多层结构是处理分级模式(hierarchical patterns)的关键。然而，CNN只能在欧几里得数据(Euclidean data)，比如二维图片和一维文本数据上进行处理，而这些数据只是图结构的特例而已，对于一般的图结构，可以发现很难将CNN中的卷积核(convolutional filters)和池化操作(pooling operators)迁移到图的操作上。如下图，左图为图像，是比较明显的Euclidean数据，而右图为普通的graph结构。
另一种动机来源于图嵌入(embedding)，所谓嵌入，就是对图的节点、边或者子图(subgraph)学习得到一个低维的向量表示，传统的机器学习方法通常基于人工特征工程来构建特征，但是这种方法受限于灵活性不足、表达能力不足以及工程量过大的问题，词嵌入常见的模型有Skip-gram，CBOW等，图嵌入常见模型有DeepWalk，Node2Vec等，如上图，然而，这些方法方法有两种严重的缺点，首先就是节点编码中权重未共享，导致权重数量随着节点增多而线性增大，另外就是直接嵌入方法缺乏泛化能力，意味着无法处理动态图以及泛化到新的图。
1.3 GNN和传统NN的区别
首先，标准的神经网络比如CNN和RNN不能够适当地处理图结构输入，因为它们都需要节点的特征按照一定的顺序进行排列，但是，对于图结构而言，并没有天然的顺序而言，如果使用顺序来完整地表达图的话，那么就需要将图分解成所有可能的序列，然后对序列进行建模，显然，这种方式非常的冗余以及计算量非常大，与此相反，GNN采用在每个节点上分别传播(propagate)的方式进行学习，由此忽略了节点的顺序，相当于GNN的输出会随着输入的不同而不同。
另外，图结构的边表示节点之间的依存关系，然而，传统的神经网络中，依存关系是通过节点特征表达出来的，也就是说，传统的神经网络不是显式地表达中这种依存关系，而是通过不同节点特征来间接地表达节点之间的关系。通常来说，GNN通过邻居节点的加权求和来更新节点的隐藏状态。
最后，就是对于高级的人工智能来说，推理是一个非常重要的研究主题，人类大脑的推理过程基本上都是基于图的方式，这个图是从日常的生活经历中学习得到的。GNN尝试从非结构化数据比如情景图片和故事文本中产生结构化的图，并通过这些图来生成更高级的AI系统。
1.4 GNN分类
GNN的模型分类如下：
- 图卷积网络(Graph convolutional networks)和图注意力网络(graph attention networks)，因为涉及到传播步骤(propagation step)。
- 图的空域网络(spatial-temporal networks)，因为该模型通常用在动态图(dynamic graph)上。
- 图的自编码(auto-encoder)，因为该模型通常使用无监督学习(unsupervised)的方式。
- 图生成网络(generative networks)，因为是生成式网络。
2. GCN
GCN详情可见之前的博客：GNN系列 GCN简述 推导理解 及 DGL 源码解析
GCN按传播方式分类：
- 基于空间域或顶点域vertex domain(spatial domain)
- 基于频域或谱域spectral domain
通俗点解释即为：
- 空域: 直接在图片的像素点上进行卷积
- 频域: 对图片进行傅里叶变换后，再进行卷积。
3. GraphSAGE
GCN的基本思想： 把一个节点在图中的高纬度邻接信息降维到一个低维的向量表示。
GCN的优点： 可以捕捉graph的全局信息，从而很好地表示node的特征。
GCN的缺点： Transductive learning 直推式，需要把所有节点都参与训练才能得到node embedding，无法快速得到新node的embedding。
例如在现实生活中，对你影响最大就是亲朋好友，这些属于一阶邻居，然后可能你偶尔从他们口中听说一些他们的同事、朋友的一些故事，这些会对你产生一定的影响，这些人就属于二阶邻居。但是到了三阶，可能基本对你不会产生什么影响了，例如你听你同学说他同学听说她同学的什么事迹，是不是很绕口，绕口就对了，因为你基本不会听到这样的故事，你所接触到的、听到的、看到的，基本都在“二阶”的范围之内。
4. GAT
5. 调优Trick
5.1 边数据增强
如果边信息较少，使用图算法可能效果会较差；此时我们可以通过一些方法去构造边信息：
1. 如果我们发现这两个实体在行为上具有非常强的一个时间上的同步性，那么我们也会认为这两个实体之间有一个边的关联。
2. 基于实体Embedding表示，先对实体做Embedding表示，然后通过ANN的近似邻居的搜索把向量接近的节点去生成边。
可参考
Tong Zhao et al. “Data Augmentation for Graph Neural Networks” national conference on artificial intelligence (2020): n. pag.
利用边缘预测器预测每条边（无论存在与否）的概率，从而指导图数据的修改
5.2 Motif特征
CS224W https://web.stanford.edu/class/cs224w/index.html
在子图的基础上衍生出了网络基序（Network Motifs）的概念，所谓网络基序，可以理解为频繁出现的子图模式。两个关键词，一个是模式，一个是频繁。
5.3 模型
5.3.1 训练推理调优
1. 加权采样
GraphSAGE等算法设计之初并没有考虑有权图，在做邻居采样时采用的是随机选取的策略，并将节点特征等权重地聚合至中心节点。
从直觉上来说，邻居节点的边权重越高，对中心节点产生的影响也越重要。
对于社交网络这类有权图来说，随机采样地进行等权聚合势必会导致有效信息被稀释。
2. 推理剪枝
只保留了每个节点最大的TopK权重边，提升局部结构的同质性。
5.3.2 模型优化
Graph Contrastive Learning with Augmentations. NeurIPS 2020.
https://arxiv.org/pdf/2010.13902.pdf
graph 应用对比学习，与对其它类型数据（如图像、文本）应用的区别在于：
- 数据增强。CV 领域一般通过随机对图片进行裁剪、旋转等操作产生增强后的数据
- 对比层次。GNN 编码后我们可以同时得到节点级别 / 图级别的两个层次的表示
我们可以看出来：
• 数据扩充对图对比学习至关重要（引入图数据扩充很容易带来性能提升）
• 组合不同的扩充方式会带来更多的性能收益（对角线性能不佳）
6. 可解释性
可解释性在风控领域非常重要，无论是误杀的排查，还是将模型交付给这个业务方的可信度。 第一种是去统计挖掘的团伙的一些统计指标，如白用户的占比、平均等级等。
第二种是通过图结构/实体向量表征去做衍生特征例如在排查某个账号实体可以通过他的k阶的邻居节点，通过k阶邻居节点的信息去做统计，然后衍生节点的统计指标作为检验它的一个指标
第三种是一个通过聚集性信息去描述，通过图做无监督的学习最后的落脚点还是在聚集性上，所以如果我们把聚集性这个信息详细的描述出来，比如这个团伙中有百分之多少的成员具有某一类相同的特征，或者是这一个团伙中有百分之多少的账号，他在某个时间段内有相同的行为，这种类似的行为描述。
7. 工程化实现
https://github.com/Angel-ML/angel
Angel: a new large-scale machine learning system. National Science Review (NSR), 2017
https://cloud.tencent.com/developer/article/1689483
Ref
- https://zhuanlan.zhihu.com/p/75307407 GNN 综述
- https://zhuanlan.zhihu.com/p/76025331 GNN综述
- http://tkipf.github.io/graph-convolutional-networks/ GCN理解
- https://www.zhihu.com/question/54504471 GCN推导理解
- https://zhuanlan.zhihu.com/p/112277874 GCN
- https://zhuanlan.zhihu.com/p/78624225 GCN简单理解
- https://zhuanlan.zhihu.com/p/79637787 GraphSAGE理解
- https://zhuanlan.zhihu.com/p/76025331 GNN综述：Review of Methods and Applications
- https://jishuin.proginn.com/p/763bfbd5d071 GCN GraphSAGE GAT
