When does a spectral prior help graph learning? Connectivity-loss estimation under road-network disruptions
1University of Science, Vietnam National University Ho Chi Minh City (VNU-HCM) · SELab
arXiv Preprint (cs.LG) & Zenodo Archival Release (v1.0.0)
Figure 1: Figure 1: ResiliRoad workflow separating intact spectral prior computation from GNN residual correction.
Residual GCN paired gain of 0.0391 [95% CI: 0.0151, 0.0662] on expanded 13-area panel
Statistically supported improvement under edge-betweenness targeted attacks
Amortized over 1,000 screened disruption scenarios per intact eigensolver setup
Paper Abstract
Rapid evaluation of many simultaneous road-link disruptions requires a useful compromise between exact spectral recomputation and local approximation. We estimated the relative loss of algebraic connectivity after multi-edge deletion using graph neural networks (GNNs) that learn a bounded correction to a first-order Fiedler sensitivity. The design was tested under independent, spatially clustered, and edge-betweenness-targeted failures, with graph-disjoint synthetic splits and zero-shot transfer to 13 OpenStreetMap (OSM) areas in six countries (48–1,259 nodes). GCN, GraphSAGE, and explicitly edge-aware MPNN backbones and analytical baselines isolated the residual prior. Across the expanded OSM panel, residual GCN improved spatial-failure MAE by 0.0391 (95% hierarchical interval 0.0151–0.0662), while residual GraphSAGE improved targeted-failure MAE by 0.0257 (0.0095–0.0446). Controlled sparse eigensolver scaling extended to 20,000 nodes and separated the one-time spectral setup from the amortized cost, achieving a 56× screening speedup.
Research Motivation
Screening thousands of multi-link road disruption scenarios via exact Laplacian eigendecomposition is computationally expensive at scale, while first-order Fiedler perturbation breaks down under finite multi-edge deletions, eigenvalue crossings, and disconnection. Rather than claiming a new GNN architecture universally wins, this study asks when a mathematical spectral prior helps graph learning and when it becomes a 'biased anchor' under distribution shift.
Guiding Research Questions
- RQ1RQ1: Does learning a bounded residual correction over a closed-form Fiedler sensitivity prior improve direct graph regression?
- RQ2RQ2: Does this advantage persist under spatially correlated or betweenness-targeted disruptions and geographic domain shift (zero-shot vs. leave-one-country-out)?
- RQ3RQ3: Which gains come from the explicit prior anchor versus Fiedler node features, coordinates, or edge-aware message passing?
- RQ4RQ4: Where does the residual estimator fail (calibration shrinkage), and how does its runtime scale up to 20,000 nodes?
Methodology & Architecture
Given an intact weighted graph G and removed edge set S, we estimate relative algebraic-connectivity loss y(G,S) = clip(1 - λ₂(G-S)/λ₂(G), 0, 1). We compute the first-order Fiedler edge-derivative sum ŷ_spec and train GCN, GraphSAGE, and Edge-MPNN backbones to predict a bounded residual ŷ_res = clip(ŷ_spec + tanh r_θ(G,S), 0, 1). We compare against a 12-mode truncated second-order perturbation baseline, Deep Sets, and summary MLPs across synthetic random geometric graphs and 13 OpenStreetMap networks across 6 Asian countries (Vietnam, Singapore, Malaysia, Thailand, Taiwan, Japan) using 10,000-resample area- and country-clustered hierarchical bootstraps.
Intact Road Graph G → Base Laplacian Spectrum (λ₂, Fiedler vector u₂) → Fast Analytical Prior ŷ_spec + Damaged Graph (G − S) with node/disruption features → 3-layer GNN Backbone (GCN / GraphSAGE / Edge-MPNN) with mean-max pooling → Bounded Residual Prediction ŷ = clip(ŷ_spec + tanh r_θ, 0, 1).
- · 13 Cached OpenStreetMap (OSM) Drivable Networks across 6 Asian Countries (HCMUS, VIASM, Da Nang, Can Tho, Da Lat, Singapore, Kuala Lumpur, George Town, Bangkok, Chiang Mai, Taipei, Kyoto, Tokyo; 48–1,259 nodes)
- · Graph-Disjoint Synthetic Random Geometric Graphs (35–65 nodes) & Planar Lattice Scaling Graphs (up to 20,000 nodes)
Mean Absolute Error (MAE) · Area/Country-Clustered 95% Hierarchical Bootstrap Intervals · Correction Calibration Regression Slope · Amortized Sparse CPU Runtime (ms)
Additional Figures from the Manuscript
Figure 2: Figure 2: Contrasting street morphologies among the 13 evaluated OpenStreetMap networks (HCMUS, Singapore, Kyoto).
Figure 3: Figure 3: Mechanistic diagnostics across eigengap tertiles, backbone architectures, and correction calibration slopes.
Figure 4: Figure 4: Sparse CPU runtime scaling from 1,000 to 20,000 nodes showing 56× amortized screening speedup.
Primary Contributions
- 01Formulated a bounded residual spectral GNN estimator combining closed-form Fiedler edge sensitivity with learned nonlinear corrections for simultaneous multi-edge deletions.
- 02Executed rigorous ablations across GCN, GraphSAGE, Edge-MPNN, 12-mode second-order perturbation, and topology transport proxies across 13 OSM regions in 6 countries.
- 03Identified and quantified the 'biased anchor' phenomenon via correction calibration slopes (dropping from 0.84–0.95 to 0.51–0.58 under targeted shift) and archived full reproducibility artifacts on Zenodo.
Analyzed Boundary Conditions
- ·In leave-one-area-out and spatial-cluster LOCO transfer, the spectral prior can act as a miscalibrated anchor when training and test failure calibrations diverge.
- ·Evaluates structural algebraic connectivity (λ₂) rather than dynamic traffic demand or congestion.
BibTeX Entry
@article{le2026spectral,
author = {Le, Van-Truong},
title = {When does a spectral prior help graph learning? Connectivity-loss estimation under road-network disruptions},
journal = {arXiv preprint arXiv:2609.11166},
year = {2026},
doi = {10.5281/zenodo.22307723}
}