1. 论文介绍
论文标题：Make Heterophily Graphs Better Fit GNN: A Graph Rewiring Approach
论文领域：图神经网络，图重连算法
论文发表：IEEE Transactions on Knowledge and Data Engineering 2024（TKDE）
论文背景：
2. 论文摘要
图神经网络（GNN）是用于建模图数据的流行机器学习方法。许多GNN在同图上表现良好，但在异图上表现不佳。最近，一些研究人员将注意力转向通过调整消息传递机制或扩大消息传递的接受域来设计用于异质图的GNN。与现有从模型设计角度缓解异质性问题的工作不同，我们建议从正交角度研究异质性图，通过重新连接图结构来减少异质性，使传统的GNN表现更好。通过全面的实证研究和分析，我们验证了重新布线方法的潜力。为了充分挖掘其潜力，我们提出了一种名为深度异质图重连（DHGR）的方法，通过添加同亲边和修剪异亲边来重连图。通过比较节点邻居的标签/特征分布的相似性来确定重新布线的详细方式。此外，我们为DHGR设计了一个可扩展的实现，以确保高效率。DHRG可以很容易地用作任何GNN的插件模块，即图预处理步骤，包括用于同质性和异质性的GNN，以提高它们在节点分类任务上的性能。据我们所知，这是研究异质图的图重连的第一项工作。对11个公共图数据集的广泛实验证明了我们提出的方法的优越性。
3. 相关介绍
传统图神经网络主要关注满足同质性属性（即大多数连接节点属于同一类别）的同质性图。
同质性（以及异质性）水平可以通过同质性比率（HR）进行测量，该指标被正式定义为每个连接节点对之间标签一致性的一致性平均值。
本文发现节点级别的同质率比率和节点的同质性的度会影响GCN在节点分类任务上的表现。
图重连算法通常包括两个阶段，即相似性学习和基于节点对之间学习到的相似性的图重连。其中，准则（即目标函数）的设计对于相似性学习阶段起着关键作用。
本文贡献
1，提出了一种新的图重连算法，通过减少异质图的异质率来让下游的GNN表现更好
2，提出使用邻居标签分布作为引导信号，通过全面实验来识别同亲性与异亲性边
3，设计了一个新的可学习的图重连算法DHGR，同时也设计了一个高效的scalable的训练算法。
4，在11个真实世界数据集上实验，基于DHGR的GNN获得了最好的效果
4. 从现实数据中的观察
本文发现存在着两个指标，节点级别的同质率和节点级别的同质度，和GNN的表现有着强相关。其中节点级别的同质率的计算是对于某一个节点，其邻居节点中相同标签类别的节点的占比。
然而，由于训练期间部分可观察到的标签，我们无法直接计算节点级别的同质性比率。所以，本文提出基于邻居节点的可观测的标签/特征分布。
节点同质性比率和节点度的影响
本文设计了一个对比实验，利用图重连算法重新去调整数据集的同质节点度和同质节点率，度k从5到25的范围，同质率p从0到1的范围。然后基于图重连算法的图拓扑来训练原生的GCN，再进行测试集测试的平均准确率。
从实验数据发现同性图和异性图都遵循相同的规律：当节点度数固定时，GCN的准确率会随着节点同性比例的增加而提升；当同性比例固定时，GCN的准确率则会随着节点度数的增加而提高。
总体而言，GCN的准确率几乎与节点同质性比率和节点度数呈单调变化关系。这促使我们采用图重连技术作为提升节点同质性比率和节点度数的有效手段。
节点邻居标签/特征的分布的影响
本文提出使用节点对之间边的关系极性，用于衡量邻居节点标签分布的差异性。考虑到不是所有的节点都有标签，同时提出邻居节点的特征分布的来作为补充。
目前为止有三类信号可以使用，原始的节点特征，标签分布，邻居节点的特征分布。
计算每个节点对与这些信号的相似性，并计算节点对相似性与图中边极性之间的互信息。互信息的计算工作为
使用上述的公式来计算各个特征之间的相似度，该相似度使用互信息来表示。
从图可以看出，邻居的标签分布相似性和邻居的特征分布与边极性之间的相关性，比原始节点特征相似性更强，且在大多数情况下，邻居的标签分布比邻居的特征分布具有更强的相关性。这一规律适用于同配图和异配图。
5. 深度异质图重连（DHGR）
DHGR首先学习一个相似性矩阵，表示基于邻居分布（即邻居的标签分布和特征分布）的每个节点对之间的相似性。然后进行图重连，对有高相似度的节点间增加边，对低相似度的节点间的边删除。整体架构为
5.1 基于邻居分布的相似度学习器
设计了一个图学习器来学习节点间相似度，只考虑出现在训练集上的（因考虑有标签的）。其中的有k跳邻居的标签分布$D_Y{(k)}$和节点分布$D_X$的公式为
其中M为最大的邻居阶，本文的M为{1，2}两种情况。然后对于每个节点，可以得到其邻居的观测标签分布向量和特征分布向量。
接下来计算每个节点对在标签分布和特征分布方面的余弦相似度，从而得到标签分布的相似度矩阵$𝑆_𝑌^{𝑡𝑟𝑎𝑖𝑛}$和特征分布的相似度矩阵$𝑆_𝑋$。
此外，通过使用掩码来限制邻居标签分布的使用条件。对于每一个节点，
其中$Mask_Y$是一个掩码向量，$N(v_i)$是节点的邻居节点集合，$V^{Train}$是训练集合中的节点。
相似性学习器的目标是基于邻居分布来学习节点对的相似性。可以根据每个节点的聚合特征来计算cos相似度
最后，使用$S_X$和$S_Y^{Train}$来进行训练学习器L。
5.2 DHGR的可伸缩版本
直接优化上述的目标函数是一个二次计算复杂度的任务，为了算法在大图上的可扩展性，设计了一个随机mini-batch的训练策略，随机选择 k1* K2个节点对，来优化相似度矩阵，通过 (K1 X K2)窗口大小多次迭代来实现。
基于学习到的相似度S的图重连算法，包含三个参数，K表示增加的边的最大的个数，$\epsilon$是相似度矩阵中可添加边的最小值阈值，$\Upsilon$是相似度矩阵中可删除边的最大值阈值。
5.3 整个算法的时间复杂度
相似度矩阵的算法复杂度是$O(Dk_1k_2)$，图重连算法的复杂度是$O(D|V|log(|V|)+K|V|+|E|)$
6. 实验设置
6.1 基础介绍
数据集主要是11个真实世界的数据集上，其中八个异质图和三个同质图，异质图为Chameleon，Squirrel，Actor，Cornell，Texas，Wisconsin，FB100，Flickr。同质图为Cora，CiteSeer，和PubMed。
基线模型：对于同质图任务，有五个GNN模型，GCN，GAT，GraphSage，APPNP和GCNII，对于异质图任务，选择2个GNN模型，GPRGNN和H2GCN。
横向对比，通过拿本算法和图结构学习中的LDS和IDGL算法对比，图重连算法的SDRF。
异质图数据集的表现
同质图上的表现
同时针对DHGR的表现，给出average gain的得分
其中M是GNN模型的集合，ACC是准确率，G是原始图和图重连后的图。
DHGR和其他图重连算法的比较
6.2 超参数的研究
DHGR下不同超参数设置的比较
K和e的影响
6.3 消融实验
考虑到DHGR利用了三种不同类型的信息（即原始特征、标签分布和特征分布），我们还通过将每种信息从DHGR中移除并设计三种变体，来验证每种信息的有效性。 DHGR\label_dist表示移除对邻居标签分布的使用（微调过程）
7. 总结
不同于之前的专注于过度挤压问题，而是专注于异质图的异质率，通过学习器的方式在已有的特征维度下和边的异质率之间建立联系实现图重连。
8. 个人感悟
新的角度下的图重连算法，比较有新意的。但总的来说是以实验和数据为核心，在理论层面较少。