一、Graph Augmentation for GNNs

之前的假设：
Raw input graph = computational graph，即原始图等于计算图。

现在要打破这个假设，原因如下：

• 如果图过于稀疏：消息传递效率低下
• 如果图过于密集了：消息传递的开销太大
  • 如要点击查看某个名人的embedding，要汇聚其成千上万个追随者的信息，这个花销是很大的
• 如果图很大：难以将计算图拟合到CPU内存中

所以，原始输入图不太可能恰好是嵌入的最佳计算图。因此需要Graph Augmentation，改变解构使之适于嵌入。

---

1、Feature Augmentation

为什么我们需要特征增强?
(1)、输入图没有节点特征；如只有邻接矩阵的时候。

解决方案：

1. 为节点分配常量值
   如为每个节点都分配一个常数1，在一轮汇聚后，各节点就能学习到其邻居节点的个数。
   
2. 为节点分配唯一的IDs
   如为每个节点都分配one-hot编码
   
   该方法每个node的向量不一样，增加了模型的表达能力，但是花费的代价非常大，如one-hot编码的维度和节点数量一致

两种方式的对比：

	Constant node feature	One-hot node feature
表达能力	中等。所有的节点都是相同的，但GNN仍然可以从图结构中学习	高。每个节点都有唯一的ID，因此可以存储特定于节点的信息
归纳学习(推广到新的节点)	高。推广到新节点很简单:我们为它们分配恒定的特征，然后应用我们的GNN	低。不能泛化到新节点:新节点引入新ID, GNN不知道如何嵌入看不见的ID
计算成本	低。只有一维特征	高。O(|V|)维度特征，不能应用于大型图
使用范围	任何图	小图

为什么我们需要特征增强?
(2)、GNN很难学习某些结构

如：计算节点所处环的节点数

基于前面的GNN是不能够解答这个问题的，原因是这两个节点的计算图是一样的，学习出来的embedding大致类似

解决方案：
可以添加cycle count作为节点的特征，如下图；即开辟一个特征空间用于描述所需要的属性。

其他常用于数据增强的特征：

• Node degree
• Clustering coefficient
• PageRank
• Centrality

---

2、Structure augmentation

出发点： Augment sparse graphs(增强稀疏图)

1. Add virtual edges

   • 常见的方法：通过虚边连接2跳邻居
   • 如：将邻接矩阵$A$使用$A+A^2$代替
   • 实例：Bipartite graphs。
     使用2-hop的虚边将作者节点连接起来
     

2. Add virtual nodes
   增加一个虚拟节点，虚拟节点将于图中的所有节点相连接

   • 好处：
     1. 缩短节点之间的距离(均可两跳可达)
     2. 传递信息更多、更有效、更快
   • 

3、Node Neighborhood Sampling

回顾之前的GNN计算图，所有节点都用于消息传递，如下图：

新的想法：
随机的选取邻居节点的子集用于计算图的构建(用于信息传递)

例如，可以在给定的层中随机选择2个邻居来传递消息，如下图：

在大图中，随机采样邻居节点的子集用于信息传递能够减少计算图；但会丢失信息，即获得了效率但失去了一些表现力。

为了弥补，可以在下一层中，当我们计算嵌入时，对不同的邻居进行采样(即每一层都采样不同的邻居用于计算图的构建)，提升模型的鲁棒性。

该方法在实践中效果不错。