异质图探索-异配图上的GNN
背景介绍
同配图的同配性是原有很多GNN网络所共同遵循的假设，也是其在图节点表示学习上大放异彩的重要假设。相较于同配图所有的点和边之间都有相同的类型，异配图认为边相连的点之间的类别是不同的，或边之前存在不同的属性，因此也可以用异配度来度量一个图中异配的比例，而随着异配度比例的增高，原有在同配图上适用且效果较好的网络的泛化性极差，在某些情况下甚至比仅依靠于用节点分类作为特征的多层感知机的效果还差。
异配图也存在一定“异性相吸”的现实应用场景意义，如在社交场景下，我们倾向于和异性聊天；在蛋白质反应等生物化学领域，酸通常倾向于和碱发生反应，负离子也倾向于和正离子结合；与在线购买网络中的其他欺诈者相比，欺诈者更有可能与共犯建立联系。
因此，本文中我们探索了一些现有工作在异质图上的表现。
探索方法
GraphSAGE
GraphSAGE是比较经典的一个算法。本质上是sample图上的一部分节点，利用K次聚合周围节点的特征来生成每个节点的表示从而对每个节点分类。
如上图所示，该方法共搜索K轮，在原文设定中，K值为2，每轮将自己邻居上一轮节点聚合后的表示与自己上一轮的节点表示拼接生成新的表示。因此本质上最多只会利用两层节点的信息来表示某节点。但并不是利用两层所有的节点，而是通过超参固定sample某些节点（原文中设定为[25, 10]）。
邻居的聚合方式可能有多种（mean aggregator，max aggregator，LSTM aggregator），我们在这次实验中由于时间原因，实现了两种比较容易的mean和max pooling聚合器。
GPRGNN
GPR-GNN的主要结构主要分为两个部分，第一部分是一个单层的MLP神经网络。它主要的作用是做隐态特征提取。当输入矩阵X （node matrix） 进入到神经网络层之后，会得到一个变换之后的特征矩阵 H0,之后根据图拓扑去传播K步分别得到H1至Hk不同步数传播后的结果。然后把得到的不同步数的结果做一个线性组合，其对应的权重叫做GPR Weights，最后线性组合完成的结果就是最终的输出结果。
表达式中标注的红色参数就是需要学习的参数，而模型是采用端对端（end-to-end）的方式进行训练。逻辑为：在解释其功能中，前面的逻辑好像是专门针对node feature，而GPR Weights专门解决图传播的问题,如果实际上是end-to-end的训练，他们相互之间可以借由梯度信息同时得到节点特征和图传播，并同时受到节点特征和图传播的限制。
BernNet
理论介绍
图谱滤波器要么需要人为预先定义，要么就是直接学习，前者一般会限制网络的表达，使得网络仅能学习有限的图，后者则缺少解释性。因此作者创造性的提出了基于Bernstein多项式的BernNet。
这种方法使用K阶Bernstein多项式逼近滤波器，并且通过理论推导，验证了bernnet对于不同形式滤波器的拟合效果。
代码实现
我们定义了propagate函数，通过pgl的send_recv函数来计算拉普拉斯矩阵L与输入x的乘积以及(2I-L)与x的乘积；
propagate函数代码如下
< img src="https://img1.imgtp.com/2022/12/19/CC0QAo8s.png” style=”zoom: 67%;” />
bernnet传播过程核心代码如下：
模型训练
为了在各种不同的数据集上都能取得最佳表现，我们对模型中使用的超参数进行了网格搜索，代码如下：
实验结果
| Model | chameleon | cornell | texas | film | wisconsin | squirrel |
|---|---|---|---|---|---|---|
| GAT | 46.86±1.68 | 57.03±4.59 | 64.05±8.02 | 24.96±1.16 | 62.35±6.06 | 39.25±1.52 |
| GraphSAGE(Sum) | 53.62±3.69 | 64.05±5.68 | 71.62±6.42 | 31.38±2.85 | 72.74±3.96 | 31.29±2.05 |
| GraphSAGE(Max) | 61.11±3.32 | 61.35±6.40 | 68.65±4.39 | 32.21±2.74 | 70.20±6.37 | 45.84±5.77 |
| GPRGNN | 65.57±1.65 | 82.16±4.86 | 79.46±5.01 | 36.49±1.03 | 52.85±3.89 | 41.57±1.38 |
| Bernnet | 67.59±2.56 | 73.24±4.90 | 75.94±7.19 | 26.15±8.61 | 77.06±4.89 | 56.24±1.84 |
| MLP(in paper GPRGNN) | 46.72±0.46 | 91.36±0.70 | 92.26±0.71 | 38.58±0.25 | N/A | 31.28±0.27 |
遇到问题
- 一开始我们由于对问题不熟悉，直接使用了某个run的最好性能当作每个模型的性能，然后我们发现好几个模型在某些数据集上的性能甚至远超过H2GCN那篇论文中汇报的性能 => 因此，以后一定要首先完全明确问题定义再去跑结果，否则得出的结果可能是有问题的，从而得出的结论也是完全错误的。
- 在复现论文过程中，一定要仔细核对原始论文/代码仓库中的超参数，一开始我们将dropout rate的网格搜索范围定在[0.01,0.1]左右，结果怎么也调不上去，经过与bernnet代码仓库的比对我们发现，dropout最佳值为0.7左右，因此将网格搜索范围扩大到[0.1,0.9]之后，模型在0.7处取得最大值。
- 我们在复现H2GCN的时候，发现paddle中并没有稀疏矩阵，这在实现时带来了很大困难，甚至需要重写稀疏矩阵相关的功能，如乘法以及matrix和系数矩阵的转换等功能。最后因为时间原因我们并没有调通，这也给工作的完整性带来了一定的影响。
结论
- 对于我们实验的六个数据集而言，所有模型中GPRGNN和bernnet各在三个数据集上表现最好，这展现了两个模型都有很好的性能。
- 关于超参数的选择，对于bernnet而言，dropout rate会对结果造成很大影响。
总结
本次大作业我们实现了三类在异配图上性能较好的前沿模型GNN网络算法：GraphSAGE，GPRGNN和Bernnet。我们进行了较为充足的实验，详细将各个模型在各数据集上的性能进行了对比，通过小组间的交流，小组成员对图神经网络模型开发的整体流程有了较为深刻的了解和认识，同时彼此了解对方实现的模型。
在大作业的实现过程中，我们也有一些不足，例如由于时间原因，我们只在paddle上实现了已有的模型，没有充分加以改进，下一步我们将继续思考各模型的改进，以期望超过SOTA。
