编辑推荐：
提出基于社区结构的图重连算法CBERR，通过分治策略优化全局特征对齐和局部有效电阻最小化，解决图神经网络中的过平滑、过挤压和未覆盖问题。实验证明其优于现有方法，且计算成本更低。
徐小燕|张玉达|李静|李志毅|张志国
中国广东省广州市增城区广州华立学院计算机工程学院，511300
摘要
图神经网络（GNNs）是处理图结构数据的先进技术，但其性能受到诸如过度平滑、过度压缩和覆盖不足等固有拓扑缺陷的限制。图重连作为一种有前景的解决方案应运而生，但现有方法往往过分强调连通性，忽视了社区复杂性，并且计算成本较高。为了解决这些问题，我们提出了CBERR，这是一种通过分而治之的方法来协同优化全局和局部图属性的新重连算法。CBERR包括两个互补的模块：（1）社区间特征对齐模块，通过基于节点相似性调整连接来增强全局特征结构的一致性；（2）社区内有效电阻最小化模块，通过贪婪的边更新来加强局部连通性并缓解过度压缩问题。
理论分析揭示了社区结构、谱间隙和有效电阻之间的内在关系，证明了CBERR设计的合理性。广泛的实验表明，CBERR在节点分类等任务上的表现优于现有的重连方法（如DIGL、FoSR、BORF、GTR、ComFy）。通过在子图层面操作，CBERR显著降低了计算成本，并确保了对大型图的可扩展性。这项工作推进了图结构学习理论，并为提高GNN性能提供了实用工具。未来的工作可以结合重叠社区检测和非贪婪优化以提高适应性。
引言
随着数字经济和信息技术的快速发展，图结构数据已成为越来越多领域中的常见数据类型[1]。图神经网络（GNNs）是一类专为图结构数据设计的深度学习模型[2]。它们已在许多图相关任务中实现了先进的性能，例如节点分类[3]、图分类[5]和链接预测[7]。具体来说，节点级任务关注单个节点，而图级任务则涉及对整个图结构的建模和分析。
尽管GNNs已广泛应用于物理[8]、生物学[10]和化学[11]等多个领域，但它们仍存在一些固有的局限性。大多数GNNs遵循消息传递范式[12]，通过迭代聚合来自局部节点邻域的信息来学习具有区分性的节点表示[13][14]。GNN的层数决定了每个节点聚合信息的邻域半径。因此，当GNN的层数较少（即网络深度小于图的直径）时，它可能无法捕获远距离节点的信息——这种现象称为“覆盖不足”[15]。相反，如果堆叠过多的层来建模长距离依赖性，GNNs往往会遇到两个关键问题：过度平滑[16]和过度压缩[18]。
过度平滑[19]发生在不同类别的节点嵌入变得无法区分时。相比之下，过度压缩是由于网络深度增加时每个节点的感受野内的节点数量呈指数级增长引起的。值得注意的是，过度压缩[20]与输入图的拓扑属性密切相关，大多数基于重连的方法通过修改图的连通性来增强节点间的信息传播[21]。
图重连[22]、图池化[23]和图结构学习[24]是文献中提出的解决过度平滑、过度压缩和覆盖不足问题的最相关的研究方向。具体而言，图重连是一种通过修改图的连通性来将原始图与用于消息传递的图分离的方法[25]；这种分离有助于提高GNN训练和推理的有效性，从而改善下游任务的性能。目前，已经开发出多种方法来缓解这三个问题。然而，传统的图重连方法仍然存在三个主要缺陷和挑战：
1.过度强调连通性而忽视其他关键因素。大多数图重连方法仅专注于优化图的连通性。它们的核心策略通常涉及缓解输入图中的瓶颈、减小图的直径[26]或增强图拓扑与节点特征之间的对齐[27]。然而，这种片面的连通性关注忽略了GNN性能所需的其他重要图属性，导致下游任务的改进效果不佳。
2.对图复杂性的考虑不足。现实世界中的图数据通常具有复杂的内在结构，例如具有不同语义属性的多样化社区划分或节点组。与将整个图视为一个均匀实体[28]相比，利用子图（例如社区级结构）的细粒度信息对于提高下游GNN任务的性能具有显著优势[29]。遗憾的是，大多数传统重连方法忽略了现实世界图的这种内在复杂性，导致无法捕捉到有价值的结构语义。
3.高计算成本和较差的可扩展性。许多先进的图重连方法集成了变压器[30]或扩散模型[31]等高级架构来优化图的连通性。然而，这些架构通常会产生大量的计算开销，表现为高时间复杂性和过度的内存消耗。更重要的是，这种沉重的计算负担使得这些方法在应用于大规模图数据（例如具有数百万个节点的工业级图）时几乎不可扩展[32]，从而严重限制了它们的实际应用价值。
为了解决这些挑战，我们提出了CBERR算法，这是一种具有三项关键创新的新图重连算法，具体如下：
1.保持局部性。我们的方法不是直接修改整个图，而是专注于从原始图的社区结构中派生的子图。这种设计不仅保留了图的内在局部性[33]，还保持了图的稀疏性——这对于高效的GNN计算至关重要。
2.增强全局连通性。我们的方法结合了社区划分和连通性调整：根据节点特征的相似性修改社区内和社区间的连通性。这种策略使算法能够在保持每个社区的局部结构特征的同时，提高整个图的全局连通性。
3.基于社区的有效电阻最小化。我们的方法关注社区级别的子图，使用总有效电阻作为衡量过度压缩的定量指标。通过策略性地向这些子图添加边，我们最小化了总有效电阻，从而缓解了GNN中的过度压缩问题。
概念分析揭示了基于社区的有效电阻与整体图谱间隙之间的内在关系。此外，广泛的实验结果表明，我们的CBERR方法优于基线模型以及该领域的其他先进图重连算法。
第2节回顾了相关工作并指出了我们的工作贡献。第3节详细介绍了CBERR算法的概念和框架。第4节描述了实验设置，第5节进行了消融研究并提供了比较分析。第6节总结了未来的研究方向。
图的基本概念
图的基础知识
用表示一个无向无权图，其中是节点集，是边集。用表示图的邻接矩阵，当节点和之间存在边时，为真，否则为假。用表示对角度矩阵，其中是节点的度数，是节点的度数。
在图社区检测的背景下，图的社区结构是指将节点集划分为个不重叠且穷尽的子集，使得对于所有，和都成立。同一社区内的节点...
我们提出的CBERR算法
受分而治之范式的启发，CBERR算法首先将整个图划分为语义上连贯的社区，然后迭代地重连子图。接着，它优化了社区内和社区间结构的特征-社区对齐，并通过最小化总有效电阻[46]进一步增强了特定社区的连通性。图1可视化了整个框架
实验设置
在本节中，我们通过实证展示了CBERR相比其他重连方法显著提高了GNN的性能。我们的评估选择了最经典的节点分类任务作为实验测试计划。
消融研究
在接下来的部分，我们将深入探讨CBERR算法的超参数设置和图数据修改结构。通过超参数设置和图数据结构的分析，我们可以再次验证我们算法的优越性。
结论
我们提出了CBERR，这是一种用于消息传递GNN的新图重连算法，它通过以社区为中心的分而治之框架平衡了全局连通性和局部结构。它整合了两个互补的模块：社区间特征对齐，根据节点特征的相似性自适应地调整连通性；以及社区内有效电阻最小化，加强局部消息传递的同时缓解过度压缩问题。
理论分析表明CBERR
CRediT作者贡献声明
徐小燕：概念化、项目管理、资源获取、软件开发、监督、撰写——原始草稿。张玉达：项目管理、数据整理、形式化分析、调查、方法论。
利益冲突声明
作者声明他们没有已知的竞争财务利益或个人关系可能影响本文所述的工作。
致谢和资金披露
本研究得到了广东省普通高等学校2024年青年创新人才项目“基于CDNG的潜在颠覆性技术识别模型与特征提取研究”（项目编号2024WQNCX068）、现代产业学院项目（广东省本科教学质量与教学改革项目的一个类别）“新一代信息技术产业学院”以及2023年学科...
徐小燕拥有信息科学硕士学位，目前担任广州华立学院计算机工程学院的讲师。她的研究重点是数据挖掘、深度学习和图神经网络。
