LineGraph2Road: Structural Graph Reasoning on Line Graphs for Road Network Extraction

Zhengyang Wei; Renzhi Jing; Yiyi He; Jenny Suckale

cs.CVFeb 26, 2026

LineGraph2Road: Structural Graph Reasoning on Line Graphs for Road Network Extraction

Authors: Zhengyang Wei, Renzhi Jing, Yiyi He, Jenny Suckale

Organizations: Stanford University, Stanford CA 94305, USA · Georgia Institute of Technology, Atlanta GA 30332, USA

Abstract

Extracting routable road networks from satellite imagery requires accurate topology recovery beyond pixel-level segmentation. Recent methods decompose the task into keypoint detection and connectivity prediction, but reliably inferring road connectivity under structural ambiguity remains challenging. Overpasses introduce non-planar crossings that can create false shortcuts, and occlusions break visual continuity, requiring long-range structural reasoning. We formulate road extraction as fully unobserved connectivity inference and construct a global but sparse Euclidean graph from detected keypoints to better leverage the long-term context. To improve link prediction, we transform this graph into its line graph and perform reasoning using a Graph Transformer. We propose an end-to-end pipeline that integrates vision-based segmentation, sparse graph construction, and structured inference. Our method explicitly models overpasses and uses topology-preserving vertex extraction to mitigate routing-critical errors. This approach achieves state-of-the-art performance on City-scale, SpaceNet, and Global-scale benchmarks in topology metrics including TOPO-F1 and APLS. In addition to quantitative gains, our method improves reconstruction of multi-level road structures crucial for real-world routing reliability. The code is available at: https://github.com/wzzzzzzy/LineGraph2Road.

Figures & tables

Figure 1: Challenges in road connectivity inference. (a) Visual ambiguity at overpasses, where roads overlap visually but remain topologically disconnected, and overpass detection alone cannot fully resolve the connectivity uncertainty; (b) occlusions from trees or buildings that interrupt the visual continuity of roads; (c) naive GNN reasoning on sparse graphs that may still produce erroneous connections without appropriate structural modeling.

Figure 2: Overview of our LineGraph2Road pipeline. During both training and inference, a satellite image is processed by the pre-trained SAM encoder [ 20 ] to extract feature maps, which are decoded into road masks. In training, the graph is constructed from a preprocessed candidate edge set (brown lines), while in inference, it is built from vertices extracted via Coupled NMS on the road mask. This graph is converted into a line graph and passed to a Graph Transformer [ 5 ] for binary node classification, determining the presence of links and yielding the final road network graph.

Figure 3: Comparison of graph connectivity strategies. (a) Local-only ( e.g . , SAM-Road [ 3 ] ) limits message passing to small subgraphs. (b) Fully-connected ( e.g . , Any2Graph [ 21 ] , RelationFormer [ 28 ] ) enables global reasoning but is computationally costly and structurally uninformed. (c) global but sparse Euclidean graph connects nearby nodes within a distance threshold, balancing global context, structural awareness, and efficiency.

	City-scale Dataset				SpaceNet Dataset
Methods	Prec.↑	Rec.↑	F1↑	APLS↑	Prec.↑	Rec.↑	F1↑	APLS↑
RoadTracer [ 3 ]	78.00	57.44	66.16	57.29	78.61	62.45	69.90	56.03
Sat2Graph [ 2 ]	80.70	72.28	76.26	63.14	85.93	76.55	80.97	64.43
TD-Road [ 14 ]	81.94	71.63	76.43	65.74	84.81	77.80	81.15	65.15
RNGDet [ 36 ]	85.97	69.78	76.87	65.75	90.91	73.25	81.13	65.61
RNGDet++ [ 9 ]	85.65	72.58	78.44	67.76	91.34	75.24	82.51	67.73

Table 1: Comparison with existing methods on City-scale and SpaceNet datasets.

	Global-Scale (In-Domain)
Methods	Prec.↑	Rec.↑	F1↑	APLS↑
Sat2Graph [ 2 ]	90.15	22.13	35.53	26.77
RNGDet [ 36 ]	79.89	40.72	52.59	49.43
RNGDet++ [ 9 ]	79.02	45.23	55.04	52.72
SAM-Road [ 3 ]	91.93	45.64	59.80	59.08
SAM-Road++ [ 10 ]	88.95	49.27	62.33	62.19

Table 2: Comparison with existing methods on Global-Scale (In-Domain) dataset.

Figure 4: The visualized road network graph predictions of our method and other baseline methods on City-Scale dataset. (a) small roundabouts; (b) multi-lane highways with complex merges and curves; and (c) winding roads with irregular geometries.

Method	TP	FP	FN	Prec.	Rec.	F1
SAM-Road [ 3 ]	296	216	1734	57.81	14.58	23.29
SAM-Road [ 3 ] w/ Overpass	413	261	1617	61.28	20.34	30.55
Ours	440	200	1590	68.75	21.67	32.96
Ours w/ Overpass	740	208	1290	78.06	36.45	49.70

Table 5: Comparison of Overpass Detection Performance

Figure 5: The visualized road network graph predictions of our method and other baseline methods as well as the predicted overpass/underpass mask on City-Scale dataset, illustrating performance on overpass and underpass crossings.

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

Figure A.1 : NMS vs. Coupled NMS. (a) Situation that will happen in NMS strategies used in [ 3 , 10 ] . (b) How coupled NMS avoids this situation.

Figure B.1 : Process of generating candidate edge features. Intermediate points are interpolated between edge endpoints, and features are sampled at these points using a bilinear sampler. The sampled features are then concatenated and passed through an MLP to produce the final edge feature.

Figure E.1 : Pairwise similarity of bilinearly sampled features across nodes in the graph. (a) The overall similarity matrix shows the pairwise feature similarities for all nodes. (b) Node-wise similarity relative to node 31. (c) Node-wise similarity relative to node 40.

Figure E.2 : directly aggregating node representations from a GNN does not yield a structural representation for node sets

Figure F.1 : Overpass/underpass masks generation process

Figure F.2 : Pipeline for preprocessing the original road network graph into the final graph used for classification.

Figure G.1 : Additional visualizations showing the model’s ability to capture complex topologies, including overpasses(panels c–e). While some imperfections remain, the model often avoids false intersections and preserves overall road geometry better than existing methods.

Figure G.2 : Additional visualized road network graph predictions of our method and other baseline methods as well as the predicted overpass/underpass mask on City-Scale dataset, illustrating performance on overpass and underpass intersections.

Figure G.3 : Representative failure cases on the Global-scale dataset. (a) Missed roads due to occlusions from tunnels, vegetation, or tall buildings. (b) Incorrect or missing labels in the test set. (c) Missed detections of small unpaved or informal roads, reflecting domain shifts across diverse geographic regions.

Figure G.4 : Examples where our method successfully recovers connectivity for tree-occluded roads.

	City-scale Dataset				Global-scale(In-Domain)
Methods	Prec.↑	Rec.↑	F1↑	APLS↑	Prec.↑	Rec.↑	F1↑	APLS↑
SAM-Road [ 3 ]	90.47	67.69	77.23	68.37	91.93	45.64	59.80	59.08
SAM-Road++ [ 10 ]	88.39	73.39	80.01	68.34	88.95	49.27	62.33	62.19
Ours $5\times 5$	90.28	75.93	82.35	69.05	90.07	50.81	64.03	66.58
Ours $16\times 16$	91.09	75.44	82.37	68.88	90.54	51.12	64.43	67.69
Ours w/ overpass $5\times 5$	92.54	75.60	83.01	70.58	87.31	53.06	65.26	69.66

Appendix

Table 0.H.1 : Comparison with

5\times 5

and

16\times 16

sliding windows on City-scale and Global-scale datasets.

Method	City-scale Dataset	SpaceNet Dataset
SAM-Road	551.19 s	918.47 s
SAM-Road++	576.51 s	752.25 s
Our	283.97 s	115.87 s

Appendix

Table 0.I.2 : Total inference time comparison on City-scale and SpaceNet dataset

Threshold	Prec.↑	Rec.↑	F1↑	APLS↑
32	91.43	75.93	82.76	67.41
64	92.75	76.64	83.77	70.40
128	93.64	69.69	79.59	67.34

Appendix

Table 0.K.1 : Comparison between different threshold configurations.

Readout	$N_{\text{sampled}}$	Prec. $\uparrow$	Rec. $\uparrow$	F1 $\uparrow$	APLS $\uparrow$
Original graph + concat MLP	2	91.81	73.34	81.35	65.72
Original graph + concat MLP	4	91.05	73.60	81.17	66.57
Original graph + dot product	4	92.38	70.38	79.60	61.13
Original graph + bilinear	4	91.29	74.04	81.57	67.51
Original graph + Hadamard MLP	4	90.51	74.50	81.54	67.33
SAM-Road [ 3 ]	–	90.47	67.69	77.23	68.37

Appendix

Table 0.L.1 : Comparison between line-graph reasoning and original-graph link-prediction readouts on the City-scale dataset. All variants use the same sparse candidate graph and visual feature setting.

Graph	Prec. $\uparrow$	Rec. $\uparrow$	F1 $\uparrow$	APLS $\uparrow$
8-NN w/ overpass	94.05	70.70	80.42	61.15
16-NN w/ overpass	92.83	74.06	82.16	67.33
SAM-Road local subgraph [ 3 ] w/ overpass	92.67	67.52	77.89	66.82
Ours w/ overpass	92.75	76.64	83.77	70.40

Appendix

Table 0.L.2 : Comparison with K-NN graph construction and the local-subgraph baseline on the City-scale dataset. All variants use

N_{\mathrm{sampled}}=4

and the overpass/underpass head.

Explore similar work

Distilled Roads: Generalisable Road Network Extraction Across Sensors, Resolutions, and Region
Aug 4, 2026Sanayya, Rakshith Sathish, Ashwathi NambiarRemote Sensing Image Segmentation Domain Generalization
SatSure Analytics India Pvt. Ltd., Bengaluru, India
RoadGIE: Towards A Global-Scale Aerial Benchmark for Generalizable Interactive Road Extraction
May 26, 2026Chenxu Peng, Chenxu Wang, Yimian Dai +3Image Segmentation Remote Sensing Image Segmentation
NKIARI, Shenzhen Futian · VCIP, CS, Nankai University · AAIS, Nankai University +1
DB SwinT: A Dual-Branch Swin Transformer Network for Road Extraction in Optical Remote Sensing Imagery
Mar 25, 2026Zongyang He, Xiangli Yang, Xian Gao +1Remote Sensing Image Segmentation
School of Information Science and Engineering, Chongqing Jiaotong University, Chongqing 400074, China · College of Information Engineering, Inner Mongolia University of Technology, Inner Mongolia Key Laboratory of Radar Technology and Application, Hohhot 010051, China

Aug 4, 2026J/K move · Enter open · S save

Distilled Roads: Generalisable Road Network Extraction Across Sensors, Resolutions, and Region

Sanayya, Rakshith Sathish, Ashwathi Nambiar

SatSure Analytics India Pvt. Ltd., Bengaluru, India

Remote Sensing Image Segmentation Domain Generalization

Open paper AskPDF arXiv

Road network segmentation from satellite imagery remains challenging due to large geographic variation in road appearance, occlusions, and domain shifts introduced by differing resolutions and sensors. Existing models, typically trained under narrow resolution--region combinations, generalise poorly to unseen environments such as rural settings, regions with distinct road materials, or imagery from new satellite platforms, often producing broken or disconnected predictions. Adapting these models to new domains usually requires retraining or fine-tuning, which is costly and risks catastrophic forgetting. In this work, we reframe global road extraction as a continual adaptation problem rather than an architectural one. Our framework combines cross-resolution knowledge distillation across a resolution-decreasing curriculum, multi-sensor training, and topology-aware supervision, yielding a single model that generalises across

0.3-1.0

m imagery from multiple satellite platforms across continents. On publicly available benchmarks, including City-Scale and Global-Scale, our model outperforms state-of-the-art results by up to

22

F1 points and

15

APLS points, while remaining the most efficient, with

3\times

faster inference. Our results suggest that improved robustness across diverse sub-meter satellite imagery can be achieved through targeted training strategies, such as data curricula, distillation, and topology-aware losses, rather than increasingly complex architectures.

Abstract

Explore similar work

Distilled Roads: Generalisable Road Network Extraction Across Sensors, Resolutions, and Region

RoadGIE: Towards A Global-Scale Aerial Benchmark for Generalizable Interactive Road Extraction

DB SwinT: A Dual-Branch Swin Transformer Network for Road Extraction in Optical Remote Sensing Imagery