数据驱动的图神经网络框架用于预测单环与双环图拓扑指标

《Algorithms》：A Data-Driven Graph Neural Network Framework for Predicting Topological Indices of Unicyclic and Bicyclic Graphs

　　

拓扑指标提供图结构的数值描述，并支持化学信息学、网络设计和图挖掘中的图分析。本研究提出一个可复现的计算框架，该框架结合了受控循环图生成、保结构变换、六个经典拓扑指标的精确计算以及多输出图神经网络回归。该框架评估单环图与双环图的Wiener、Merrifield–Simmons、Hosoya、第一Zagreb、第二Zagreb和Randi'c指标。每个图使用稀疏连通性和节点级特征表示，这些特征编码度数、环成员资格、悬挂连通性、叶状态和归一化偏心率。图同构网络（GIN）联合预测六个指标，并与图卷积网络（GCN）、图注意力网络（GAT）以及基于描述符的回归基线进行比较。受控基准测试表明，非线性基于描述符的模型实现了最低的聚合误差，因为所提供的图级描述符包含关于图大小、度结构、分支和环复杂性的强先验信息。尽管GIN未达到最高的整体精度，但通过直接从稀疏连通性和节点级特征学习而无需固定的手工图级描述符向量，它提供了最强的图原生性能。所提出的替代模型并不能替代孤立小图的精确评估，在这些情况下精确计算仍然更合适。相反，其实际价值体现在对更大、更复杂图实例的重复评估中。为检验这一设定，一项计算压力实验在递增的环复杂度下评估稀疏多环图，并测量精确计算时间、超时频率、预测精度和摊销盈亏平衡点。结果表明，当组合指标计算变得足够昂贵且训练好的模型在多个结构相关的图查询中重复使用时，替代预测变得有利。对循环图的外部实验也表明，该框架可以通过仅修改图构建阶段而扩展到原始图生成器之外。

**论文解读：数据驱动的图神经网络框架用于预测单环与双环图拓扑指标**

**研究背景与问题**

拓扑指标是图论和化学信息学中描述图结构的重要数值工具，广泛应用于分子性质预测、网络设计及图挖掘等领域。经典指标如Wiener、Merrifield–Simmons、Hosoya、第一Zagreb、第二Zagreb和Randi'c指标能够刻画图的度数分布、分支模式及距离结构。单环图（圈秩为1）和双环图（圈秩为2）作为受控图族，在环状分子和限制连通性系统中具有代表性。尽管对这些图族已有精确公式和极值结果，但现有研究通常只针对单个指标或特定图族，缺乏一个统一且可复现的框架，将受控图生成、保结构变换、多种指标精确计算与数据驱动预测相结合。此外，当图规模增大时，某些指标（如Merrifield–Simmons和Hosoya指标）的精确计算涉及独立集和匹配的枚举，计算成本急剧上升，此时替代预测模型可能具有实用价值。然而，目前缺乏对“何时使用替代预测比精确计算更划算”的系统分析。因此，本研究旨在构建一个基准框架，系统地比较精确计算、基于描述符的回归和基于图原生的多输出学习在结构化循环图族上的性能，并明确替代推理在计算上变得有利的条件。

**研究内容与主要结论**

研究人员开发了一个完整的计算框架，包括：受控的单环和双环图生成器（通过顺序添加顶点和保结构变换丰富结构多样性）、六个拓扑指标的精确计算管线（采用BFS计算Wiener指标，递归记忆化枚举独立集和匹配）、图表示（稀疏边索引和节点特征，包括度、环成员、悬挂邻居数、叶状态和归一化偏心率）、以及多输出图神经网络（GIN）和基线模型（GCN、GAT、线性回归、MLP、随机森林）。在包含19,180个去重图（9,430个单环和9,750个双环）的基准上，评估了各模型的预测精度。结果表明，基于描述符的非线性模型（随机森林和MLP）取得了最低的聚合误差，因为手工设计的图级描述符（如阶数、度方差、叶数、环节点数等）蕴含了强烈的先验结构信息。GIN虽然未达到最高整体精度，但它是图原生模型中最强的，能够直接从稀疏连通性和节点级特征学习，无需固定的描述符向量。在更严格的父感知划分下，GIN的误差反而下降，而随机森林和MLP误差上升，显示GIN具有更强的泛化能力。指标层面的分析表明，度基指标（Zagreb和Randi'c）误差较低，而全局组合指标（Merrifield–Simmons和Hosoya）误差较高，这与GIN的1-WL表达力限制一致。压力实验在更大的稀疏多环图（阶数30–60，圈秩5–20）上显示，精确计算Hosoya指标的时间随圈秩显著增加（从0.9秒至13秒），而替代模型在约112次查询后即可实现盈亏平衡。外部循环图实验（200个图）验证了框架的可移植性，仅需修改图构建模块即可适用。

**主要技术方法**

研究中使用了以下关键方法：1) 受控图生成器，通过从随机采样的环长度和核心类型构建单环和双环图，并施加保结构变换（如悬挂边迁移和悬挂子树重连）以增加多样性；2) 精确标签管线，对每个图计算六个指标，其中Merrifield–Simmons和Hosoya指标采用递归记忆化枚举算法；3) 图表示，采用PyTorch Geometric的稀疏边索引和节点特征矩阵，节点特征包括归一化度、环成员指示、悬挂邻居数、叶状态和归一化偏心率；4) 多输出GIN模型，包含三个消息传递层，隐藏维度64，全局和池化，预测六个指标；5) 基线模型包括线性回归、MLP和随机森林，使用手工描述符向量（平均度、度方差、叶数、环节点数、圈秩等）；6) 压力测试协议，在更大图上测量精确计算时间、超时频率和摊销盈亏平衡点。

**研究结果**

**整体预测性能**：所有模型在标准化的目标尺度上比较MAE和RMSE。随机森林和MLP的聚合误差最低，GIN在图原生架构中表现最佳，但不如描述符基线。GCN和GAT表现较弱。

**父感知划分下的性能**：采用父感知划分（每个原始图及其变换后代分配到同一子集）后，随机森林和MLP的误差增加（随机森林MAE增加32.75%，MLP的MAE增加但R2仍高），而GIN的MAE降低18.34%，RMSE降低15.76%，所有六个指标均改善。这表明GIN在避免父-变换重叠时泛化更强。

**指标维度性能**：GIN对度基指标（第一Zagreb、第二Zagreb、Randi'c）的MAPE较低（<5%），而对Merrifield–Simmons和Hosoya的MAPE较高（>10%）。这反映了这些指标对全局组合结构的依赖。

**图族和图阶的影响**：单环和双环图的误差分布相似，双环图稍宽。图阶的影响非单调，但最大阶区间（26–30）误差最高，尤其对组合指标。

**变换图上的性能**：GIN在原始图和变换图上的MAE、RMSE和MAPE几乎相同，表明模型对保结构变换稳定。

**外部循环图实验**：在200个循环图上，重复划分（10次种子）的插值性能良好，除Hosoya外所有指标R2>0.98；高阶留出实验显示，度基指标仍准确（R2>0.95），但Wiener、Merrifield–Simmons和Hosoya的R2下降，表明外推能力有限。

**压力测试**：在160个稀疏多环图上，所有图在300秒超时内完成精确标签。Hosoya指标的计算时间随圈秩增加而急剧上升（中位数从0.9秒到13秒）。MLP和随机森林的聚合性能优于GIN，但GIN在度基指标上表现良好（R2>0.97），对组合指标较差（Merrifield–Simmons R2=0.63，Hosoya R2=0.45）。摊销盈亏平衡分析显示，GIN、MLP和随机森林分别需要约112、111和114次查询即可抵消训练和标注成本。

**讨论与结论**

讨论部分指出，基于描述符的模型之所以占优，是因为手工特征提供了强先验信息；GIN则展示了图原生学习的优势，但受限于1-WL表达力。结论强调，该框架并非替代精确计算，而是在精确计算昂贵且查询量大的场景下提供替代方案。未来工作应扩展到更大更多样的图族，并研究更高阶架构以克服表达力限制。

（注：本文解读基于论文原文内容，未添加任何推测性信息。）