ResiliRoad
Spectral-Prior Residual Graph Learning for Road-Network Disruption Screening
A reproducible graph machine learning framework that combines analytical first-order Fiedler spectral sensitivity priors with residual GNNs (GCN, GraphSAGE, Edge-MPNN) to estimate road-network connectivity loss across 13 OpenStreetMap areas in 6 Asian countries, achieving a 56× screening speedup on 20,000-node networks.
The Technical Bottleneck
Infrastructure planners screening thousands of simultaneous multi-link road disruptions face a computational dilemma: recomputing the exact Laplacian algebraic connectivity (λ₂) via sparse eigensolvers takes >1.3 seconds per scenario at 20,000 nodes, whereas fast first-order Fiedler perturbation fails under finite edge deletions, disconnection, and eigenvalue crossings.
Why Existing Baselines Fail
Rather than claiming a new GNN architecture universally beats analytical physics, ResiliRoad investigates a fundamental scientific question: when does an explicit mathematical spectral prior help graph learning under distribution shift, and when does it become a 'biased anchor' that learned residual corrections fail to undo?
Core Formulation & Insight
We retain the closed-form Fiedler edge derivative sum ŷ_spec as an auditable graph-level anchor and train GCN, GraphSAGE, and Edge-Aware MPNN backbones to predict a bounded correction: ŷ_res = clip(ŷ_spec + tanh r_θ(G,S), 0, 1). We evaluate independent, spatial-cluster, and edge-betweenness-targeted disruptions across synthetic random geometric graphs and 13 OpenStreetMap networks in 6 countries using 10,000-resample area- and country-clustered hierarchical bootstraps.
Architectural Design
Separates the one-time intact-graph Laplacian eigendecomposition from fast per-scenario prior lookup and sparse GNN residual inference.
ResiliRoad pipeline combining intact-graph Fiedler sensitivity priors with bounded GNN residual corrections.
1. Intact Spectral Setup & Fiedler Anchor
Computes the second-smallest Laplacian eigenvalue λ₂(G) and unit Fiedler vector u₂ once for the intact road network, deriving edge sensitivities ∂λ₂/∂w_ij = (u_{2,i} − u_{2,j})².
2. Multi-Regime Disruption Simulation
Generates 1–8 simultaneous edge deletions under Independent random, Spatial-cluster (epicenter geometric midpoint), and Targeted (edge-betweenness centrality) regimes.
3. Residual GNN Backbones (GCN / GraphSAGE / Edge-MPNN)
Encodes damaged adjacency G − S and node features (intact degree, failed-edge incidence, |u₂|, normalized coordinates) through 3 message-passing layers and mean–max pooling to output tanh r_θ(G,S).
4. Hierarchical Bootstrap & Calibration Diagnostics
Computes 10,000-resample area-outer and country-outer 95% confidence intervals, 12-mode second-order perturbation controls, and regression calibration slopes.
Technical Stack & Systems Engineering
Implementation Highlights
- →Built automated OSMnx graph extraction and simplification pipelines freezing 13 real-world street networks across Vietnam, Singapore, Malaysia, Thailand, Taiwan, and Japan.
- →Implemented fairness-controlled architecture comparisons with identical parameter budgets, splits, and stopping rules across direct and residual variants.
- →Engineered a sparse CPU eigensolver and amortized screening benchmark scaling from 50 to 20,000 nodes.
Datasets & Protocol
Datasets & Corpora
- 13 OpenStreetMap Networks (HCMUS, VIASM, Da Nang, Can Tho, Da Lat, Singapore, Kuala Lumpur, George Town, Bangkok, Chiang Mai, Taipei, Kyoto, Tokyo; 48–1,259 nodes)
- Synthetic Random Geometric Graphs (35–65 nodes, 400–800 scenarios/mode/seed)
- Planar Road-Like Scaling Graphs (1,000 to 20,000 nodes, mean degree ≈ 4.2)
Evaluation Protocol
Evaluated 4 transfer protocols: (1) Graph-disjoint synthetic, (2) Zero-shot synthetic-to-OSM (5 areas & expanded 13 areas), (3) Leave-one-area-out (LOAO) OSM, and (4) 6-country Leave-one-country-out (LOCO) OSM transfer.
Tracked Evaluation Metrics
Reduced zero-shot OSM spatial-disruption MAE from 0.096 to 0.057 and accelerated 20,000-node disruption screening by 56× (1.30s → 23.17ms), while rigorously diagnosing when priors become biased anchors.
Paired improvement of 0.0391 [95% CI: 0.0151, 0.0662] across 13 OSM areas
Statistically supported gains under edge-betweenness attacks
56× faster than exact sparse eigendecomposition (amortized over 1,000 scenarios)
Quantifies residual shrinkage under targeted domain shift
Empirical Analysis & Interpretation
ResiliRoad demonstrates that mathematical priors and GNNs are most powerful when paired with diagnostic calibration checks: the Fiedler prior substantially improves zero-shot transfer and targeted LOCO screening, but can act as a biased anchor under certain spatial-cluster domain shifts.
Processed OpenStreetMap street topologies for HCMUS (Vietnam), Singapore, and Kyoto (Japan).
Log-log sparse CPU runtime scaling up to 20,000 nodes.
What This System Contributes
- 01Sole author: conceived the mathematical formulation, implemented the PyTorch/SciPy/OSMnx codebase, executed all 13-area and 20K-node experiments, and published the open-source Zenodo archive.
Boundary Conditions & Future Work
- ·Focuses on structural Laplacian algebraic connectivity (λ₂) rather than dynamic traffic flow assignment; LOCO precision is bounded by 6 country clusters.
When does a spectral prior help graph learning? Connectivity-loss estimation under road-network disruptions
Van-Truong Le