谱先验在图学习中何时有益？道路网络中断下的连通性损失估计

# 光谱先验何时有助于图学习？道路网络中断下的连通性损失估计
来源：https://arxiv.org/html/2609.11166
Van-Truong Le\*附属机构：信息技术学院，胡志明市科学大学，附属机构：越南胡志明市国立大学，附属机构：\*通讯作者：[[email protected]](mailto:[email protected])附属机构：电子邮箱：[[email protected]](mailto:[email protected])附属机构：ORCID：0009-0008-7015-7392 (https://orcid.org/0009-0008-7015-7392)

###### 摘要

评估大量同时发生的路段中断需要精确的光谱重计算与局部近似之间找到有用的折衷。我们使用图神经网络（GNN）估计了多边删除后代数连通性的相对损失，这些网络学习对一阶Fiedler灵敏度的有界校正。该设计在独立、空间聚类和边介数针对性故障下进行了测试，使用了图不相交的合成分割，并在六个国家的13个OpenStreetMap（OSM）区域（48–1,259个节点）上进行了零样本迁移。GCN、GraphSAGE和显式边感知MPNN主干网络以及分析基线隔离了残余先验。对于扩展的OSM分析，不确定性使用了区域聚类分层引导，种子嵌套在区域内。在整个扩展的OSM面板上，残余GCN将空间故障MAE提高了0.0391（95%分层区间0.0151–0.0662），而残余GraphSAGE将针对性故障MAE提高了0.0257（0.0095–0.0446）。边MPNN残差差异为正但不精确。二阶扰动仅将一阶MAE提高了0.0028–0.0053。在独立或空间迁移下，校正斜率从0.84–0.95下降到针对性迁移下的0.51–0.58（针对GCN/GraphSAGE），直接量化了系统先验误差周围的残差收缩。匹配的逐机制留一国OSM到OSM迁移结果好坏参半：残余GCN将针对性故障MAE提高了0.0622（0.0169–0.1153），但恶化了空间点估计；相同的符号模式出现在联合训练中。受控的稀疏特征值求解器可扩展至20,000节点，并将一次性光谱设置与摊销成本分离。在有限的地理聚类内，这些结果将光谱残差描述为一种潜在有用但领域敏感的归纳偏差，并将其适用性限定于结构连通性而非危险或交通流预测。代码、缓存网络和可复现工件永久存档于 doi:10.5281/zenodo.22307723 (https://doi.org/10.5281/zenodo.22307723)。开发仓库在 GitHub (https://github.com/lee-vtruong/ResiliRoad) 上提供。

关键词：代数连通性；Fiedler向量；图神经网络；空间网络；基础设施鲁棒性；领域偏移。

## 1引言

道路网络是空间嵌入的复杂网络，其链路损失会破坏访问路径并改变系统范围的连通性。当规划者必须筛选多种多链场景时，穷尽的精确评估会变得成本高昂。相反，一阶扰动快速且可解释；然而，其局部线性可能在有限删除、特征值交叉和断开连接下失效。这种张力激发了混合估计器的产生，该估计器保留已知的光谱方向，并仅学习其非线性误差。

代数连通性是拉普拉斯特征值中第二小的那个，是一个全局结构量\[2 (https://arxiv.org/html/2609.11166#bib.bib2),3 (https://arxiv.org/html/2609.11166#bib.bib3)\]。它不衡量旅行需求、拥塞、容量或恢复能力。此处更窄的目标是快速结构压力测试：给定一个完整的加权图和一组被移除的边，估计其相对的代数连通性损失。这一区别很重要，因为运输鲁棒性也常使用系统旅行时间、容量损失、可达性和修复轨迹来定义\[7 (https://arxiv.org/html/2609.11166#bib.bib7),8 (https://arxiv.org/html/2609.11166#bib.bib8),14 (https://arxiv.org/html/2609.11166#bib.bib14)\]。

本研究提出四个问题。研究问题1：学习Fiedler近似之上的残差是否能改进直接图回归？研究问题2：这种优势在相关中断和地理领域偏移下是否持续存在？研究问题3：哪些收益来自于显式先验、Fiedler节点特征、坐标或邻接感知消息传递？研究问题4：估计器在哪里失败，其运行时如何扩展？

核心论点并非是新的图神经网络（GNN）架构是否胜出，而是*数学信息的光谱先验在分布偏移下何时有助于图学习，何时成为有偏的锚点*，即一个系统性的、有误校准的分析起始值，而学习到的校正未能将其撤销。贡献包括：（i）用于同时边删除的有界残差光谱构造；（ii）受控的特征、GCN/GraphSAGE/边-MPNN、二阶和可靠性上下文消融；（iii）在六个国家的13个缓存OpenStreetMap（OSM）网络上进行的三种中断过程；（iv）合成到真实的零样本和地理不相交的OSM迁移；（v）区域聚类分层推断、校准、特征间隙和校正诊断；以及（vi）分离特征值求解器设置、摊销光谱评估和仅更新成本的基准测试。重要的是，迁移实验揭示了一个局限性：一旦有OSM训练数据可用，残差先验并非普遍优越。

## 2相关工作

### 2.1复杂网络的光谱鲁棒性

Fiedler引入了代数连通性作为图不变量\[2 (https://arxiv.org/html/2609.11166#bib.bib2)\]；后来的研究将拉普拉斯光谱与扩张、连通性、同步性和鲁棒性联系起来\[3 (https://arxiv.org/html/2609.11166#bib.bib3),4 (https://arxiv.org/html/2609.11166#bib.bib4),6 (https://arxiv.org/html/2609.11166#bib.bib6)\]。容量加权光谱分析也被用于诊断运输网络的脆弱性\[16 (https://arxiv.org/html/2609.11166#bib.bib16)\]。对于一个简单的特征值，跨一条边的Fiedler坐标的平方差提供了关于其权重的导数\[5 (https://arxiv.org/html/2609.11166#bib.bib5)\]。这样的导数解释了无穷小的灵敏度，而当前的任务包括几个有限的边删除。残差模型专门针对缺失的交互和高阶项，而非取代光谱分析。

### 2.2道路网络中断

道路鲁棒性取决于图表示和中断过程。对经验城市网络的多粒度分析表明，结构结论可能随表示方式而改变\[9 (https://arxiv.org/html/2609.11166#bib.bib9)\]。基于流或容量的链路指标解决功能性影响\[7 (https://arxiv.org/html/2609.11166#bib.bib7),8 (https://arxiv.org/html/2609.11166#bib.bib8)\]，而关键场景优化则搜索破坏性链路组合\[10 (https://arxiv.org/html/2609.11166#bib.bib10)\]。与危险无关的研究比较了随机、局部化和针对性的多链路故障\[13 (https://arxiv.org/html/2609.11166#bib.bib13)\]；对苏黎世的时间分析也证明了过程依赖的鲁棒性\[12 (https://arxiv.org/html/2609.11166#bib.bib12)\]。随机道路图模型允许进行受控的拓扑实验\[11 (https://arxiv.org/html/2609.11166#bib.bib11)\]。我们的空间聚类机制属于这种压力测试传统，但它是几何代理，而非经验危险模型。

近期证据使得规模和任务定义尤为重要。Jana等人\[18 (https://arxiv.org/html/2609.11166#bib.bib18)\]使用基于边的GNN在中断后对关键路段进行排序，直接启发了基于学习的快速筛选。他们的输出是边排序，而我们的是图级别的光谱损失估计。Boeing和Ha\[19 (https://arxiv.org/html/2609.11166#bib.bib19)\]模拟了178个国家中8000多个城市地区的24亿次出行，确立了一个远超我们13个社区网络的经验规模。Zang等人\[20 (https://arxiv.org/html/2609.11166#bib.bib20)\]使用多粒度GNN预测降雨下的动态交通韧性；他们的动态、功能性目标与我们静态的结构性目标是互补的。综述区分了连通性、鲁棒性、脆弱性和基于恢复的韧性，并警告不要将它们视为同义词\[17 (https://arxiv.org/html/2609.11166#bib.bib17),15 (https://arxiv.org/html/2609.11166#bib.bib15),21 (https://arxiv.org/html/2609.11166#bib.bib21)\]。

### 2.3图学习与分析先验

GCN聚合局部邻域信息，并在节点级别具有置换等变性\[22 (https://arxiv.org/html/2609.11166#bib.bib22)\]。GraphSAGE提供了归纳聚合主干\[23 (https://arxiv.org/html/2609.11166#bib.bib23)\]；GIN研究了邻域聚合的表达极限\[26 (https://arxiv.org/html/2609.11166#bib.bib26)\]，而注意力和消息传递框架则揭示了替代的节点/边交互\[25 (https://arxiv.org/html/2609.11166#bib.bib25),24 (https://arxiv.org/html/2609.11166#bib.bib24)\]。Deep Sets提供了一种不沿边传播的不变替代方案\[27 (https://arxiv.org/html/2609.11166#bib.bib27)\]。图网络也被用作可学习的物理模拟器\[28 (https://arxiv.org/html/2609.11166#bib.bib28)\]，说明已知结构和学习到的校正可以共存。此处声称的新颖性并非有界残差学习本身：混合模型和物理引导模型通常学习围绕分析组件的差异\[1 (https://arxiv.org/html/2609.11166#bib.bib1)\]，而\[28 (https://arxiv.org/html/2609.11166#bib.bib28)\]中的可学习物理引擎学习用于模拟和控制的交互动力学。网络科学的贡献更为具体。我们保留闭合形式的Fiedler边导数作为可审计的图级别锚点，通过实验将其与仅提供u2作为节点特征分离开来，并测试其有限的多边误差相对于特征间隙、断开连接、故障几何和地理偏移的表现。然后，校正校准使得未能覆盖锚点的失败可衡量，而不是将混合模型视为不透明的精度工具。边感知建模特别相关，因为中断作用于链路。Jana等人\[18 (https://arxiv.org/html/2609.11166#bib.bib18)\]编码了用于边排序的道路线图，Almeida等人\[29 (https://arxiv.org/html/2609.11166#bib.bib29)\]报告了用于骨干网负载预测的边感知注意力。本研究转而询问一个简单的节点消息传递估计器是否在跨领域时受益于显式的光谱先验。最近关于城市边移除的JCN工作使用扩散传输\[30 (https://arxiv.org/html/2609.11166#bib.bib30)\]，将代数连通性置于几种合理的网络功能代理之中。

## 3问题表述与方法

令\(G=(V,E,w)\)为一个连通的无向加权图，其组合拉普拉斯矩阵为\(L=D-A\)，特征值满足\(0=\lambda_1 \leq \lambda_2 \leq \cdots\)。对于中断的边\(S \subseteq E\)，目标是

\(y(G,S) = \operatorname{clip}\!\left(1 - \frac{\lambda_2(G-S)}{\lambda_2(G)}, 0, 1\right)\)。(1)
因此，断开的受损图有\(y=1\)。如果\(u_2\)是单位Fiedler向量且\(\lambda_2\)是简单的，则边灵敏度为

\(\frac{\partial \lambda_2}{\partial w_{ij}} = (u_{2,i} - u_{2,j})^2\)。(2)
分析预测对完整图的导数求和：

\(\widehat{y}_{\mathrm{spec}} = \operatorname{clip}\!\left(\frac{\sum_{(i,j) \in S} w_{ij} (u_{2,i} - u_{2,j})^2}{\lambda_2(G)}, 0, 1\right)\)。(3)
每个受损图提供归一化的邻接矩阵和节点特征：完整度、失败边关联、绝对归一化Fiedler坐标以及两个归一化坐标。三个48单元GCN层馈入均值-最大图池化和一个两层头。直接模型预测\(y\)；残差模型预测

\(\widehat{y}_{\mathrm{res}} = \operatorname{clip}\!\left(\widehat{y}_{\mathrm{spec}} + \tanh r_{\theta}(G,S), 0, 1\right)\)。(4)
有界校正将容量集中在有限删除误差上，但也可能继承先验的领域特定偏差。

为了确定在更高阶分析模型之外是否需要学习，一个截断扰动基线保留了12个最低的拉普拉斯模式：

\(\Delta \lambda_2^{(2)} = u_2^\top \Delta L u_2 + \sum_{k \neq 2} \frac{\|u_k^\top \Delta L u_2\|^2}{\lambda_2 - \lambda_k}\)。(5)
对于边\(S\)的删除，\(\Delta L = -\sum_{(i,j) \in S} w_{ij} (e_i - e_j)(e_i - e_j)^\top\)。二阶连通性估计为\(\lambda_2 + \Delta \lambda_2^{(2)}\)，并使用公式(1)转换为相对损失，采用与一阶估计相同的\([0,1]\)裁剪。对于每个图，在评估前固定了十二个模式，并未根据测试性能进行调优。\(k=1\)项消失是因为\(\Delta L \mathbf{1} = 0\)；数值上，保留的模式在修正和中排除了\(k=2\)。我们还记录了相对特征间隙\(\gamma = (\lambda_3 - \lambda_2)/\lambda_2\)，它衡量与下一个模式的接近程度，但未提供给任何学习器。

图1 (https://arxiv.org/html/2609.11166#S3.F1)总结了完整的ResiliRoad工作流程。

图1：ResiliRoad工作流程。精确的受损图特征分解仅用于构建标签。完整的Fiedler向量产生一个可选的节点特征和显式的一阶先验；选定的GNN主干学习有界校正。替代文本：一个流程图将完整的道路图分为精确标签分支和快速光谱先验分支。受损的邻接矩阵和节点特征输入到选定的GNN主干网络，其残差被添加到光谱估计中。

消融矩阵包含具有所有特征、无Fiedler特征和无坐标的直接和残差GCN；Deep Sets和汇总统计MLP是非GCN基线。另一个可靠性上下文残差将先验、归一化失败计数、密度和图大小附加到预测头。它不使用受损连通性或任何标签衍生的标志。作为更强的架构控制，GraphSAGE在每个学习变换之前将每个节点状态与归一化的邻域聚合连接起来。其直接和残差变体使用与GCN相同的特征、池化、优化器、分割和停止规则。边感知MPNN则在每个完整的候选链路上形成\(m_{ij} = \phi(h_i, h_j, e_{ij})\)，其中\(e_{ij}\)包含归一化电导、反电导长度、失败边指标和归一化的\((u_{2,i} - u_{2,j})^2\)。三个层中，传入消息的平均值更新节点状态。保留失败链路作为候选允许