《Mathematics》：Beyond Graph Diameter: Structural Determinants of Long-Range Information Propagation in Message-Passing Neural Networks
编辑推荐：
消息传递神经网络（Message-Passing Neural Networks, MPNNs）通过迭代邻域聚合传播信息，使得长程信息交换依赖于网络深度和图结构。本研究探究图直径（graph diameter）是否足以表征有效信息传播，以及哪些拓扑性质可提供额
消息传递神经网络（Message-Passing Neural Networks, MPNNs）通过迭代邻域聚合传播信息，使得长程信息交换依赖于网络深度和图结构。本研究探究图直径（graph diameter）是否足以表征有效信息传播，以及哪些拓扑性质可提供额外的解释性信息。研究人员建立了一个数学框架，用于区分有限深度可达性（finite-depth reachability）与通信冗余（communication redundancy），并给出形式化结果，证明具有相同直径的图可以表现出根本不同的连通性（connectivity）、割点结构（articulation-point structures）和路径冗余（path redundancy）。研究人员在路径图（path）、环图（cycle）、Erd?s–Rényi图、网格图（grid）和杠铃图（barbell）上开展了控制实验，采用标签复制任务（label-copying task）以及具有2、4、6和10个消息传递层的MPNNs。研究人员将图级结构度量与传播准确率进行相关性分析，并辅以针对性的节点移除实验。结果表明，直径相当的图可以表现出显著不同的传播性能。平均最短路径长度（average shortest-path length）和聚类系数（clustering coefficient）与准确率仅呈弱关联，而割点（articulation points）和边连通度（edge connectivity）则表现出更强的关联。移除高介数中心性（betweenness centrality）节点对若干图拓扑产生了最大的准确率下降，进一步证明了结构性关键通信通路的重要性。综合理论与实证结果，研究人员表明仅凭图直径无法完整表征MPNNs中的有效信息传播。消息传递深度决定了理论可达性，而有效的长程传播还额外依赖于图拓扑，特别是通信冗余、结构瓶颈、连通性以及替代路径的可用性。
**研究背景与问题**
消息传递神经网络（Message-Passing Neural Networks, MPNNs）通过迭代的邻域聚合机制学习图结构数据的表示，已被广泛应用于社交网络、推荐系统、计算机视觉、计算生物学和科学机器学习等领域。然而，MPNNs的局部消息传递机制存在固有局限：来自图中远距离节点的信息只有在经过足够多的传播步数后才能影响目标节点，因此长程交互任务对传统MPNNs构成严峻挑战。已有研究表明，简单堆叠传播层并不一定能提升模型利用远距离信息的能力——图卷积可被解释为拉普拉斯平滑（Laplacian smoothing），重复传播使节点表示趋于相似，即过平滑（over-smoothing）现象；此外，图神经网络的表达能力随深度增加可能呈指数级丧失。更近期的综述将过挤压（over-squashing）和信息瓶颈列为现代图神经网络最根本的局限之一。过挤压是指随着消息传播，来自越来越大感受野的信息必须被压缩到固定维度的节点表示中，当长程依赖经过狭窄的结构瓶颈时尤为严重。后续研究进一步将过挤压与图拓扑联系起来，发现图瓶颈与离散曲率相关，曲率引导的图重连（graph rewiring）可缓解此类瓶颈；从信息论视角，过挤压可被解释为消息传播过程中的信息收缩，并与图扩展性相关。Di Giovanni等人系统研究了网络宽度、深度和图拓扑在MPNN过挤压中的作用，将传播困难与节点间的大通勤时间（commute time）联系起来——这一视角超越了普通最短路径距离，因为通勤时间还反映了图中替代路径的可用性和结构。Black等人则用有效电阻（effective resistance）刻画过挤压，该图论量捕捉了连接两个节点的多条路径的集体贡献。这些研究共同表明，长程信息传播受制于比成对距离更为复杂的拓扑因素。
尽管取得了上述进展，图直径（graph diameter）——即任意两节点间最大最短路径距离——作为一个简单且广泛可解释的全局距离属性，其作为有效消息传播独立预测因子的作用尚未得到系统性的关注。图直径提供了图最大空间范围的直观描述，人们可能因此预期直径更大的图对浅层MPNNs构成更大困难。然而，这种解读忽略了一个事实：具有相同直径的图可能拥有根本不同的连通模式、路径冗余、瓶颈、聚类结构和扩展性质。直径本身是否为有效信息传播提供有意义的解释力，以及其影响如何与拓扑和网络深度交互，因此需要控制性研究来回答。本研究旨在系统探究图直径是否为MPNNs中有效信息传播的有意义预测因子，并通过控制合成图族（包括路径图、环图、网格图、Erd?s–Rényi图和杠铃图）变化图结构和消息传递深度，利用标签复制任务评估信息传播。研究的贡献在于提供了一个控制性的理论与实证分析，区分基于距离的可达性与通信结构，并考察具有可比距离特征的图如何因连通性、路径冗余和结构瓶颈的差异而表现出不同的传播行为。该研究补充了现有基于拓扑的过挤压分析，专门检验图直径作为长程信息传播解释性描述符的局限性。
**关键技术方法**
本研究聚焦于五类合成图（路径图、环图、网格图、Erd?s–Rényi随机图和杠铃图），使用NetworkX库生成图实例。采用基于图卷积网络（Graph Convolutional Networks, GCNs）的MPNN架构，评估了2、4、6和10个消息传递层的模型深度。标签复制任务中，源节点被赋予二元标签，其余节点特征初始化相同且不含标签信息，目标节点仅基于L轮消息传递后的表示预测源节点标签。训练使用交叉熵损失函数和Adam优化器，学习率设为指定值，训练250个epoch。图级结构度量包括图直径、平均最短路径长度、聚类系数、边连通度和割点数量；节点级度量包括度和介数中心性。采用Pearson相关性分析评估结构度量与传播准确率的关系，并进行针对性的节点移除实验（移除低度节点、高度节点、高介数节点或割点）。此外，研究进行了距离控制分析，仅保留节点移除前后最短路径距离不变的源–目标对，采用精确McNemar检验评估配对二分类结果。固定随机种子用于图生成、源节点选择、标签分配、目标节点混洗、训练–测试划分和模型初始化，以确保可重复性。
**研究结果**
**图直径本身不能解释传播性能**：具有可比直径的图根据其拓扑表现出显著不同的传播行为，这一效应在比较路径图、网格图、环图和杠铃结构时最为明显。这些图可以构造出相似的距离特性，但在源–目标距离增加时的准确率并不等效。
**感受野限制的实验验证**：在二、四、六和十个消息传递层的MPNNs上评估标签复制任务，随着源–目标距离增加测量信息传播准确率。在所有图拓扑上，层数更多的模型能在更大距离上更准确地传播信息。当传播距离超过网络层数时，准确率明显下降，这与k层MPNNs的k跳限制一致，与Proposition 1的理论预测相符。
**结构鲁棒性比平均距离度量更具信息性**：对于十层MPNN，平均准确率与平均最短路径长度仅呈弱正相关（Pearson r = 0.239, p = 0.310），与聚类系数的相关性也较弱（Pearson r = 0.344, p = 0.137）。相比之下，结构鲁棒性度量与准确率表现出更强的关系。对于十层MPNN，割点数量与平均准确率呈负相关（Pearson r = ?0.523, p = 0.018），边连通度与平均准确率呈正相关（Pearson r = 0.432, p = 0.057）。对于二层MPNN，这一模式更为显著：割点数量与平均准确率呈强负相关（Pearson r = ?0.775, p = 0.001），边连通度呈强正相关（Pearson r = 0.680, p = 0.001）。
**节点移除实验与结构瓶颈**：对每种图拓扑考虑五种设置：原始图、移除低度节点、移除高度节点、移除高介数节点和移除割点。原始图的准确率范围为0.60至0.71，路径图初始准确率最低，网格图最高。移除低度节点在所有四种图拓扑上降低准确率，但降幅一般较小（0.01至0.03），路径图除外。移除高度节点产生更依赖拓扑的效应：杠铃图和网格图准确率分别下降0.05和0.07，而路径图和Erd?s–Rényi图分别小幅上升0.02和0.01。在无限制干预分析中，移除高介数节点后观察到最大的准确率差异：杠铃图和网格图准确率分别下降0.10和0.16，Erd?s–Rényi图下降0.07，路径图仅下降0.01。移除割点也与传播准确率变化相关，但效应因拓扑而异：Erd?s–Rényi图下降0.08，网格图下降0.03，路径图下降0.02，杠铃图上升0.02。在距离控制分析中，当源–目标距离保持不变时，大多数干预条件下传播准确率变化很小或没有变化，且没有任何配对比较达到统计显著性。路径图中高介数节点和割点移除后观察到的大差异应谨慎解读，因为分别仅有四个和两个距离保持不变的源–目标对可用于比较。总体而言，距离控制分析表明，在解释结构节点移除后的传播性能变化时，应考虑源–目标距离。
**讨论与结论**
本研究并未使用有效电阻、通勤时间、离散曲率或基于雅可比的敏感性度量等既定指标直接量化过挤压。因此，割点、边连通度、介数相关干预与传播准确率之间的观察关系不应被解读为过挤压的直接测量，而是表明这些拓扑性质与信息传播性能之间的关联。虽然这些观察与过挤压文献中提出的假设一致，但并未建立所研究结构性质与过挤压本身之间的因果 relationship。
第一组实验结果表明，图直径单独而言通常是信息传播性能的弱预测因子。信息传播受多种拓扑性质影响而非仅由直径决定。图直径仅代表任意节点对之间的最大最短路径距离，捕捉的是极端全局距离属性，并不反映图的整体通信结构。路径图是特殊情况，因为信息只能沿单一轨迹传播。因此，传播性能似乎不仅取决于节点间的最大距离，还取决于图中替代通信路径的可用性。增加MPNN层数后，结果说明在超过对应k跳限制的某一距离k后准确率显著下降，这与Proposition 1一致，即L层MPNN只能依赖距离至多L的顶点所起源的节点特征。因此，图2中观察到的经验传播边界反映的是局部消息传递架构的根本理论局限，而非实验设置的伪影。此外，即使来自理论感受野内节点的信息，随着通过连续层聚合也可能日益被压缩，这种压缩与过挤压相关机制一致，可能导致有效传播降低。
实验结果表明不同类别的拓扑度量与传播性能表现出显著不同的关系。平均最短路径长度与平均准确率仅呈弱相关，因为该度量不捕捉通信是否受结构瓶颈约束或是否有替代传播路径可用。聚类系数与平均准确率也仅呈弱相关，因为更高的聚类系数增加了相邻节点间的局部连接密度，但不一定改善图中远距离区域之间的通信。相比之下，割点数量与平均准确率强相关。割点数量越多，表明存在越多结构关键瓶颈，图区域间的通信可能依赖于此。根据Menger定理，被割点分隔的图区域通过结构受限的通信路径集连接。在MPNN中，这可能要求来自多个节点的信息通过有限通信结构聚合，可能增加信息压缩和过挤压的易感性。边连通度在十层配置中与平均准确率呈中等正相关，在二层配置中呈更强正相关。更大的边连通度意味着图区域间存在更多边不相交通信路径，信息可通过多条替代路线传播而非集中在少数关键边上，这与更大通信冗余可能降低拓扑诱导信息瓶颈易感性的假设一致。
第二组实验结果表明，节点度单独而言对传播相关性的信息有限，而针对高介数节点和割点的干预与传播性能的较大变化相关。移除低度节点可能仅有限影响传播性能，如果足够的替代通信路径仍然可用。路径图的例外具有结构意义，因为端点移除改变了本就只有单一信息流路径的拓扑中可用的源–目标配置。移除高度节点的影响强烈依赖于拓扑：在杠铃图和网格图中，移除高度节点导致准确率明显下降，可能因为这些节点提供了大量通信路径，在维持高效信息传播中起重要作用；其移除可能降低连通性、增加结构瓶颈并限制替代传播路径的可用性。路径图和Erd?s–Rényi图的准确率仅有可忽略的增加，因为路径图几乎所有节点具有相同度值（端点除外），移除高度节点要么移除几乎所有内部节点破坏图结构，要么对图拓扑无影响；Erd?s–Rényi图通常表现出更均匀的度分布，不依赖少数高度节点。这表明度本身不是节点对传播重要性的可靠指标——一个节点可能有许多邻居但在图中并不处于全局关键位置。移除高介数节点似乎对整体准确率影响最强。介数中心性度量的是经过给定顶点的最短通信路径比例，移除高介数节点同时消除了大量可用于信息传播的最短路线。若干图族中观察到的显著准确率下降提供了经验证据，表明全局通信位置比纯局部连通性度量（如度）更重要。如上所述，割点数量与标签复制任务的平均准确率强相关。移除割点以拓扑依赖的方式影响传播性能：杠铃图准确率上升，其余图拓扑普遍下降。在多数情况下，割点代表关键通信瓶颈，其移除断开图的部分并减少替代传播路径的可用性，信息流因此更受限，导致传播性能降低。杠铃图的行为表明割点的作用取决于周围拓扑。杠铃图移除割点后准确率表观增加应谨慎解读：移除割点可能断开图并消除先前需要跨瓶颈通信的困难源–目标配置，剩余评估集可能因此包含结构上更容易的传播任务，所以移除后更高的准确率不一定表明全局信息传播改善。
距离控制分析提供了补充视角：当源–目标距离保持不变时，大多数干预条件下传播准确率变化很小或没有变化，且没有配对比较达到统计显著性。这表明在解释无限制节点移除实验中观察到的准确率差异时，应考虑源–目标距离和干预诱导的连通性变化。综合而言，实验结果与第2节开发的数学框架一致。Proposition 1以有限深度可达性解释了观察到的传播边界，Proposition 2证明直径单独无法表征通信结构。割点和边连通度观察到的更强关联，以及若干图族中移除高介数节点后更大的准确率变化，表明有效信息传播不仅取决于信息必须传播多远，还取决于可用通信路径的结构和冗余性。在研究实验设置范围内，通信冗余和瓶颈相关度量因此提供了超越纯距离图度量的补充解释信息。
本研究的局限在于所有实验均在合成图族上进行。虽然合成图提供了隔离拓扑性质影响的控制设置，但实证发现不应假定自动推广到真实世界图数据集。未来工作应研究观察到的图拓扑与传播性能之间的关系是否在更复杂的真实世界网络中持续存在。
结论部分指出，综合理论和实验结果，距离相关的图属性单独而言无法完整表征消息传递神经网络中的信息传播。数学分析确立了消息传递深度决定理论可达性，而具有相同直径的图在连通性和通信冗余方面可能显著不同。实验结果补充了这一分析，表明直径相当的图仍可能表现出显著不同的传播性能。在所研究的图族和实验设置中，平均最短路径长度和聚类系数与传播准确率仅呈弱关联，而割点和边连通度表现出更强的关系。在无限制节点移除实验中，移除高介数节点与若干图拓扑中相对较大的传播准确率下降相关。然而，额外的距离控制分析表明，当源–目标距离保持不变时，大多数干预条件表现出很小或没有变化，且没有配对比较达到统计显著性。这些发现表明，结构干预结果应结合干预诱导的距离和连通性变化来解读。因此，结果支持理论可达性与有效信息传播之间的区分：源–目标距离决定了信息交换所需的最小消息传递深度，但满足该深度要求并不保证有效传输。一旦节点理论可达，传播性能可能额外取决于可用通信路径的拓扑，包括其冗余性、连通性和结构瓶颈的存在。这些结构条件与过挤压文献中讨论的机制一致；然而，本研究并未直接量化过挤压。未来工作应使用更直接的信息传输和瓶颈严重程度度量来研究这些关系，包括基于曲率的量、有效电阻、通勤时间和基于雅可比的敏感性度量。此类分析可阐明距离、连通性和通信冗余如何共同影响信息传播，并支持拓扑感知图神经架构的开发。一个进一步的展望是将该框架扩展到量子与混合量子–经典图学习，特别是通过控制比较研究类似经典MPNNs中观察到的拓扑诱导通信限制是否也在量子图模型中出现，以及它们如何与信息编码、电路深度、纠缠结构和测量策略交互。
