cs.AIAug 22, 2026
SaveVisAdj: Learning Adjacency Matrices from Node-Link Images
Organizations: University of Delaware Newark, Delaware, USA
Abstract
Learning adjacency matrices from node-link images is a fundamental problem for recovering structured graph information from visual observations. Existing methods typically rely on fixed KNN-based heuristics for candidate edge selection and fail to capture dependencies among edges. To overcome these limitations, we propose VisAdj, a new framework for topology-aware adjacency prediction. VisAdj introduces an attention-sparse neighbor sampler to adaptively select a high-recall set of candidate node pairs and performs joint edge inference using a line-graph transformer that treats candidate edges as tokens and explicitly models dependencies among incident edges. Extensive experiments on synthetic graphs, road networks, and vessel images demonstrate that VisAdj consistently outperforms existing baselines by clear margins.
Figures & tables
Figure 1. Examples of node-link images and their underlying graphs. Orange lines denote ground-truth edges. Existing methods often miss long-range connections (orange dashed lines) and predict erroneous shortcut edges (red dotted lines) in visually ambiguous crossing regions. Three example node-link images are shown: a road network, a vessel network, and a general graph image. Each image contains visible nodes and links that correspond to an underlying graph structure.
Figure 2. Overview of VisAdj. Given an input node-link image, VisAdj first (#1) extracts local and global visual features using a vision foundation encoder, and (#2) detects graph nodes from a node likelihood map through peak extraction, non-maximum suppression, and soft-argmax refinement. It then (#3) enhances global features with learnable topology tokens to capture image-level structural context. Conditioned on the detected nodes, VisAdj (#4) applies ASNS to generate a sparse high-recall set of candidate edges, and (#5) represents these candidates as edge tokens for topology-aware reasoning with a line-graph transformer. The resulting edge logits are symmetrized and thresholded to obtain the predicted adjacency matrix. Overview of the VisAdj architecture. The pipeline contains five numbered modules: image encoding, node detection, global topology encoding, ASNS candidate edge generation, and topology-aware edge reasoning with a line-graph transformer.
| Dataset | Category | Image | #Train | #Val | #Test |
| Synthetic | Graph | RGB | 2763 | 395 | 788 |
| Toulouse | Road | Binary | 80357 | 11679 | 18998 |
| US-Cities | Road | RGB | 32740 | 1931 | 5730 |
| OCTA500 | Vessel | Grayscale | 11461 | 753 | 1505 |
Table 1. Dataset statistics.
| Graph-level Metrics | Subgraph-level Metrics (TOPO) | Element-level Metrics | ||||||
| Dataset | Method | GIR (%) | GED | Precision (%) | Recall (%) | F1 (%) | Edge-F1 (%) | Node-F1 (%) |
| Synthetic | G-SAM-Road++ | 43.17 (0.73) | 18.54 (2.24) | 56.79 (1.36) | 55.34 (1.08) | 56.06 (1.18) | 53.25 (1.24) | 92.23 (1.37) |
| G-RNGDet++ | 26.31 (1.53) | 19.81 (2.36) | 55.73 (1.31) | 45.85 (1.86) | 50.31 (1.67) | 44.64 (1.61) | 88.82 (1.58) | |
| Any2Graph | 53.79 (0.57) | 17.96 (1.67) | 57.35 (1.68) | 55.10 (1.43) | 56.20 (1.40) | 59.14 (1.58) | 92.69 (1.24) | |
| Sat2Graph | 20.91 (1.93) | 21.35 (1.85) | 51.42 (1.46) | 47.05 (1.57) | 49.14 (1.63) | 40.35 (1.59) | 88.46 (1.67) | |
| VisAdj | 73.02 (0.46) | 0.50 (0.42) | 98.78 (0.41) | 98.67 (0.49) | 98.72 (0.43) | 95.09 (1.25) | 99.23 (0.37) | |
Table 2. Main comparison results across all datasets. The best performance for each metric is highlighted in bold .
| Image encoder | Size (M) | GIR (%) | TOPO-F1 (%) |
| SAM-ViT-B ( 26 ) | 91 | 73.02 (0.46) | 98.72 (0.43) |
| SAM-ViT-L ( 26 ) | 308 | 75.38 (0.39) | 98.76 (0.42) |
| SAM-ViT-H ( 26 ) | 636 | 76.73 (0.41) | 98.81 (0.43) |
| SAM2-Hiera-S ( 38 ) | 46 | 74.87 (0.38) | 98.73 (0.41) |
| SAM2-Hiera-B ( 38 ) | 80.8 | 75.56 (0.35) | 98.78 (0.39) |
| SAM2-Hiera-L ( 38 ) | 224.4 | 78.08 (0.32) | 98.84 (0.38) |
Table 3. Performance of VisAdj with different image encoders on the Synthetic dataset.
Figure 3. Qualitative results. Each row presents one example, with columns showing the input image, ground-truth graph, and predictions from VisAdj, G-SAM-Road++, G-RNGDet++, Any2Graph, and Sat2Graph, respectively. Rows correspond to examples from the Synthetic, Toulouse, US-Cities, and OCTA500 datasets. Predicted nodes are shown as yellow dots, and predicted edges as orange line segments. A qualitative comparison table with four rows, one for each dataset. Each row shows an input image, the ground-truth graph, and predicted graphs from VisAdj, G-SAM-Road++, G-RNGDet++, Any2Graph, and Sat2Graph. VisAdj predictions generally match the ground-truth graph more closely, while baselines show more missing or spurious edges.
Figure 4. Representative failure cases. Each row presents one example, with columns showing the input image, ground-truth graph, and predictions from VisAdj, G-SAM-Road++, G-RNGDet++, Any2Graph, and Sat2Graph. Predicted nodes are shown as yellow dots, and predicted edges as orange line segments. Although VisAdj may still make incorrect adjacency decisions under dense crossings, cluttered backgrounds, or weak visual contrast, it generally produces better predictions than the baselines. Qualitative examples of failure cases where VisAdj makes incorrect graph connections. The examples include dense crossings or cluttered visual regions where multiple edge configurations are plausible, causing missed edges or incorrect shortcut edges.
| Method | ms/image | images/s | Speedup |
| G-SAM-Road++ | 88.18 | 11.34 | |
| G-RNGDet++ | 269.54 | 3.71 | |
| Any2Graph | 102.25 | 9.78 | |
| Sat2Graph | 147.93 | 6.76 | |
| VisAdj | 63.17 | 15.83 | – |
Table 4. Inference runtime on the US-Cities dataset with a batch size of 1 under the same settings. Speedup is computed as the latency ratio between each baseline and VisAdj.
Figure 5. Sensitivity analysis of key hyperparameters on Synthetic, Toulouse, US-Cities, and OCTA500 datasets. Sensitivity analysis of four key hyperparameters on different datasets.
| Variant | GIR | TOPO-F1 | Edge-F1 | Node-F1 (%) |
| Full | 73.02 (0.46) | 98.72 (0.43) | 95.09 (1.25) | 99.23 (0.37) |
| w/o LineGT | 54.43 (0.70) | 74.69 (0.38) | 72.63 (0.63) | 98.64 (0.25) |
| w/o ASNS | 63.11 (0.68) | 86.47 (0.65) | 85.35 (0.94) | 98.72 (0.41) |
| w/o Visual | 66.30 (0.57) | 90.75 (0.35) | 89.36 (0.43) | 98.82 (0.21) |
| w/o Spatial | 70.26 (0.53) | 95.68 (0.51) | 93.81 (0.74) | 99.07 (0.26) |
| w/o Topology | 68.59 (0.42) | 92.26 (0.81) | 90.68 (0.86) | 98.94 (0.19) |
Table 5. Ablation study on the Synthetic dataset. We assess five variants: 1) w/o LineGT: replace line-graph transformer (Eq. 7 ) with a standard graph transformer; 2) w/o ASNS: replace ASNS (Eq. 3 ) with KNN; 3) w/o Visual: remove visual features (Eq. 4 ); 4) w/o Spatial: remove spatial features (Eq. 5 ); 5) w/o Topology: remove global topology features (Eq. 6 ).
Figure 6. Road network extraction results on SpaceNet and US-Cities datasets. APLS is Average Path Length Similarity. Comparison results for real-world road network extraction on SpaceNet and US-Cities datasets.