1. 论文介绍
论文标题：It Takes a Graph to Know a Graph: Rewiring for Homophily with a Reference Graph
论文发表：刚发表到Arixv，2025年5月
论文领域：图神经网络，图重连技术
论文代码：https://github.com/harel147/REFine
论文背景：
2. 论文摘要
图神经网络（GNNs）擅长分析图结构数据，但在异亲图上存在困难，其中连接的节点往往属于不同的类。虽然这一挑战通常是通过专门的GNN架构来解决的，但在这种情况下，图形重新布线仍然是一种未充分探索的策略。我们提供了连接边缘同态性、GNN嵌入平滑度和节点分类性能的理论基础，激发了增强同态性的需求。在此基础上，我们引入了一个重布线框架，该框架使用参考图增加了图的同态性，并从理论上保证了重布线图的同态性。为了扩大适用性，我们提出了一种标签驱动的扩散方法，用于从节点特征和训练标签构造同态参考图。通过大量的仿真，分析了原始图和参考图的同态性对重布线图同态性和下游GNN性能的影响。我们在11个实际数据集上对我们的方法进行了评估，结果表明，该方法优于现有的重布线技术和异亲图专用GNN，在保持高效性和可扩展性的同时提高了节点分类精度。
3. 相关介绍
3.1 背景介绍
本文建立了边缘同质性、图上学习的 GNN 嵌入的平滑度和 GNN 性能之间的理论和经验联系。
理论分析表明，在低同质关系的图中，允许准确分类的学习节点嵌入在图上无法平滑。这会与 GNN 的消息传递机制产生冲突，在许多情况下，GNN 倾向于沿图结构平滑嵌入。
为了系统地控制图的同质率，采用来源于流形学习领域的扩散过程。通过利用未充分利用的信息（节点特征和节点标签）来构建同质图作为参考。
本文提出了几种类型的图同质度量来衡量图中标签相关性的不同方面，包括：边同质性，节点同质性，类同质性，邻居节点同质性。特别关注边同质率，是最简单和最常见的度量，量化了连接具有相同标签的节点的边的比比例。
目前研究领域处理异质图结构的GNN架构：MixHop通过聚合多跳邻居的信息来扩展GNN，GPRGNN引入了广义PageRank权重的自适应学习机制，H2GCN通过引入高阶连接模式来进一步完善消息传递，CAGNN使用共享混合器自适应地整合邻居信息。
整个图的边同质率可以定义为
3.2 使用参考图来控制同质率
实验研究显示出，GNN在同质图上的表现优于异质图，这是标准GNN架构导致的。
迪利克雷能量，该度量捕获了嵌入在整个图结构中变化的平滑程度，其中小值表示连接节点之间的小变化（平滑度），大值表示连接节点之间的大变化（波动度）。
GNN 中的信息传递机制倾向于产生平滑的节点嵌入。GNN 本质上会降低平滑度项$tr(Z^T, LZ)$，这并不总是有益的，并且可能导致过度平滑。
定理1：
上面的公式的不等式的右侧为线性可分离嵌入的平滑度的下限。较高的同质性导致较小的下限，使 GNN 更容易产生平滑和线性可分离的嵌入。相反，在异性图中，增加的下界增加了消息传递引起的平滑可能损害线性可分离性的风险。
图的同质性越大，GNN学习线性可分离、因而更有效的节点嵌入的潜力就越大。
4. 增强同质性的图重连框架
定义参考图为Gr=（v，Er），通过基于Er的边来添加或删除k条边来修改边集，定义了E(k)
其中Sk是k条边的随机子集，k>0表示添加边，k<0表示删除边。
4.1 添加边
定义命题
所以有，
当满足条件时，基于参考图的边加法在期望中提高了同质性。
4.2 删除边
当k<0的时，图重连g(k)是通过删除从 ℰ∩ℰ_r^c 随机选择的|k|边获得。
当满足条件时，基于参考图的边删除，提高了期望同质性。
4.3 真实世界数据集上进行验证
使用边添加进行重新连线对康奈尔数据集的影响，其中每列表示使用不同的 $g_{r,p}$ 具有不同同质性（由不同 p 值控制）的重新布线。
边删除对Cora数据集的影响
当满足条件时，去除边会增加同质性（红线下方的绿线），否则会降低。然而，较高的同质性并不总是能提高 GCN 性能，因为可能会发生过度挤压。
5. 图重连算法
假设特征空间提供了与标签一致的有意义的相似性度量，则基于特征亲和力的参考图应该是同性的。我们的关键思想是将节点特征与训练标签相结合，以构建一个参考图，该参考图不仅是同性的，而且可以推广到未标记的节点。
本文引入扩散方法，通过由完全可用的节点特征 𝐗 构建的图，将标签信息传播到未标记的节点，从而“完成”缺失的标签。该方法捕获特征和标签之间的共享结构，从而产生比大多数情况下仅由其构 𝐗 造的参考图具有更高的同质性。
本图重连算法的步骤：
- 对原始图进行聚类
- 基于节点特征和节点标签对每一个聚类进行构建一个参考图
- 在每一个聚类上，基于参考图来进行图重连操作
- 通过连接聚类之间的边，来构造一个连接性更强的图
构建参考图Gr的第一步是基于节点特征向量构建亲和矩阵WD，对于i，j ∈ {1,2,..n}，d(,)是距离度量，ϵ是控制亲和率尺度的超参数。
其次，使用标准的内核归一化手段，对亲和率矩阵进行归一化操作，得到数据核D。所以可以计算对角线矩阵D1，其对角线元素由WD的总和组成，使用它来获得中间矩阵D’，计算另一个由于D' 和D2组成的对角矩阵，使用归一化步骤
对于基于节点标签的亲和性矩阵，定义一个二进制矩阵
同样，$W_p$可以基于具有标签亲和力的图回归的连续标签来构造，使用应用于$W_D$的相同归一化对矩阵$W_p$进行归一化。产生标签核P。
对于上述的P和D的乘积，$\tau = PDP$，是一个以标签为驱动的扩散过程，包含三个步骤：使用可用标签在类内传播；通过所有节点的节点特征相似性传播；最终通过标签传播。
所以可以根据 $\tau$ 来定义参考图的边集合，因为$\tau$的元素是连续的，所以可以将其裁剪来获得与未加权图的邻接矩阵相对应的二进制矩阵。首先计算$\tau$的每一行的平局值。给出公式得到
$$\mu_i = \frac{1}{n}\sum_{j=1}^n\tau(i,j) $$
依据该平均值$\mu$可以得到裁剪的内核
可扩展性
因为本算法依赖于核操作，其计算成本巨大而不适应大型图。为了确保可扩展性，使用METIS算法来将图g聚类为N个子类。$N=\frac{|V|}{c}$，C是聚类大小，为超参数。每个集群$g_l$根据其参考图独立重新连接，最终通过合并所有的连接聚类来重建整个图，同时保留原始图的聚类间的边。
REFine算法伪代码为
6. 实验设置
6.1 基础实验
对比算法：SDRF，FoSR，BORF算法，
节点分类任务的实验数据为
因为算法是基于同质性的，所以对于异质图来说也有很大的帮助，算法在异质图神经网络框架的上的意义，采用框架 MixHop，H2GCN，GPRGNN，OrderedGNN，和本算法基于标准的GNN（GCN，GATv2，APPNP三个）的图重连算法。实验数据如下
6.2 消融实验
1，同质性和算法的提升
发现同质率越低的数据，本算法加入后对GNN的测试准确度提升越大。
2，只使用训练标签来做亲和性矩阵
即是意味着$\tau = P$使用来替代$\tau = PDP$，测试准确率随着 |k| 增加而下降，从实验发现仅使用训练标签而不考虑数据时对未标记节点的泛化能力有限。
数据为
3，聚类大小超参数
较大的聚类大小会导致性能有所提高，运行时间增加。
7. 总结
主要是针对异质图的图重连算法，使用三个技术的组合，METIS聚类降低整个图的计算量为一个个的小图；使用亲和矩阵来构建参考图；聚类之间的图重连算法。
8. 个人感悟
图重连算法开始向异质图来做，通用领域的baseline已经够高了，找图神经网路的子方向来挖掘。