Paper deep dive
VisAdj: Learning Adjacency Matrices from Node-Link Images
Jiahao Xie, Guangmo Tong
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 89%
Last extracted: 8/25/2026, 7:24:49 AM
Summary
The paper introduces VisAdj, a framework for learning adjacency matrices from node-link images. It addresses limitations of existing KNN-based heuristics by using an attention-sparse neighbor sampler (ASNS) for candidate selection and a line-graph transformer for joint edge inference that models dependencies among incident edges. The method improves graph isomorphism and edge prediction F1 scores on synthetic, road network, and vessel image datasets.
Entities (9)
Relation Signals (8)
VisAdj → uses → attention-sparse neighbor sampler
confidence 95% · VisAdj introduces an attention-sparse neighbor sampler to adaptively select a high-recall set of candidate node pairs
VisAdj → uses → line-graph transformer
confidence 95% · performs joint edge inference using a line-graph transformer that treats candidate edges as tokens
VisAdj → evaluatedon → road networks
confidence 90% · Extensive experiments on synthetic graphs, road networks, and vessel images
VisAdj → evaluatedon → vessel images
confidence 90% · Extensive experiments on synthetic graphs, road networks, and vessel images
VisAdj → improves → edge prediction F1 score
confidence 90% · and over 8% in edge prediction F1 score across diverse benchmarks
VisAdj → improves → graph isomorphism rate
confidence 90% · VisAdj improves the state of the art by over 15% in graph isomorphism rate
VisAdj → outperforms → SAM-Road
confidence 80% · VisAdj consistently outperforms existing baselines by clear margins... SAM-Road... rely on fixed KNN-based strategies
VisAdj → outperforms → RelationFormer
confidence 80% · VisAdj consistently outperforms existing baselines... RelationFormer... predict each edge independently
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2608.21825v1
- Canonical: https://arxiv.org/abs/2608.21825v1
Trouble viewing inline? Open PDF directly →
Full Text
74,204 characters extracted from source content.
Expand or collapse full text
VisAdj: Learning Adjacency Matrices from Node-Link ImagesDOI: X.XXXXXXXConference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NYISBN: 978-1-4503-X-X/2018/06Conference: Proceedings of the 35th ACM International Conference on Information and Knowledge Management; November 07–11, 2026; Rome, ItalyProceedings of the 35th ACM International Conference on Information and Knowledge Management (CIKM ’26), November 07–11, 2026, Rome, ItalyDOI: 10.1145/3799682.3840917ISBN: 979-8-4007-2539-5/2026/11CCS: Theory of computation Graph algorithms analysis Jiahao Xie email: jiahaox@udel.edu OrcID: 0009-0002-8716-6566 Affiliation: University of Delaware , Newark , Delaware , USA and Guangmo Tong email: amotong@udel.edu OrcID: 0000-0003-3247-4019 Affiliation: University of Delaware , Newark , Delaware , USA 2026; © c 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. Keywords: Learning, Adjacency Matrices, Edge reasoning, Node-Link Images †c-license: by 1. Introduction Node-link images are widely used to visualize relational structures (39; 24; 19; 46), such as road and vessel networks (Fig. 1), where the underlying graphs encode the semantic information of interest and the images serve primarily for human interpretation. However, in practice, the original graph data are often unavailable, leaving only rasterized images such as satellite photos and medical images. Consequently, the adjacency structures become inaccessible to downstream graph algorithms and learning models. This introduces the problem of recovering adjacency matrices from node-link images. Early attempts recover graphs from node-link images using hand-crafted heuristics (12), which are sensitive to visual variations. Recent road network extraction methods, such as SAM-Road (20) and SAM-Road++ (48), adopt learning-based pipelines but still rely on fixed KNN-based strategies to select candidate node pairs. This leads to an inherent limitation: a small neighborhood radius misses long-range connections, whereas a large radius admits many spurious candidates. Such designs are effective for road networks with relatively simple structures and limited crossings (Fig. 1(a)), but become less reliable for general node-link images, where the underlying graph structures may be more complex (Figs. 1(b)-1(c)). More general image-to-graph methods, such as RelationFormer (40) and Any2Graph (27), infer graph structures through learned relational reasoning, but still predict each edge independently based only on endpoint features, without considering structural dependencies among edges. In practice, edge dependencies come from both node-level and graph-level structural constraints: node degree limits the number of incident edges, and global graph properties (e.g., planarity in Fig. 1(a) and tree topology in Fig. 1(b)) impose additional topological restrictions. Ignoring such edge-edge interactions often results in ambiguous or inconsistent adjacency predictions, making edge inference the primary bottleneck in graph reconstruction. (a) (b) (c) 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. Contribution. We propose VisAdj, a new framework for reconstructing adjacency matrices from node-link images. VisAdj first encodes the input image into local and global visual features to support node detection and image-level structural understanding, with global features enhanced by learnable topology tokens. To overcome the rigidity of KNN-based candidate selection, VisAdj introduces an attention-sparse neighbor sampler to adaptively select a high-recall set of candidate node pairs. Furthermore, to address the limitation that existing methods ignore edge dependencies, VisAdj performs joint edge inference over candidate node pairs using a line-graph transformer, which treats edges as tokens and explicitly models interactions among incident edges for structurally consistent adjacency prediction. Experimentally, VisAdj improves the state of the art by over 15%15\% in graph isomorphism rate and over 8%8\% in edge prediction F1 score across diverse benchmarks, while also enhancing existing road network extraction pipelines as a plug-in graph reasoning module. Our code, dataset, and hyperparameter settings are available at https://github.com/Jiahao-Xie-86/VisAdj. 2. Related Work Road network extraction. A large body of work studies image-to-graph reconstruction in the context of road network extraction (36; 2; 41; 35). Sat2Graph (18) models road graphs by predicting connectivity between detected junctions using convolutional features over local neighborhoods. RNGDet++ (47) adopts an iterative graph-growing paradigm, progressively adding nodes and edges through region-of-interest sampling guided by historical maps. More recent approaches, such as SAM-Road (20) and SAM-Road++ (48), leverage vision foundation models to produce node and edge representations, which are subsequently converted into graph structures via post-processing. Despite their effectiveness on road datasets, these methods struggle to generalize to general node-link images because their graph reasoning modules are tailored to road-specific characteristics (e.g., planarity and local connectivity) and rely on fixed KNN-based methods for candidate edge selection. General image-to-graph methods. In addition to road networks, several methods aim to recover more general graph structures from images (5). For example, RelationFormer (40) introduces a transformer-based framework that jointly predicts nodes and edges using set prediction and bipartite matching, enabling end-to-end graph inference without explicit post-processing. Any2Graph (27) improves this paradigm by proposing an optimal transport-based loss to better align predicted and ground-truth graphs under permutation ambiguity. These approaches move toward unified image-to-graph modeling by jointly learning node and edge prediction. However, they predict each edge independently and lack explicit mechanisms to model structural dependencies among edges. In contrast, our framework overcomes these limitations by learning edge interactions and performing joint edge reasoning. 3. Preliminary We study the problem of recovering graph adjacency matrices from node-link images. Let ℐI denote the space of node-link images and G the space of undirected, unweighted graphs. Each image ∈ℐI provides a visualization of the underlying graph represented as G=(V,)∈G=(V,A) , where V denotes the node set and ∈0,1|V|×|V|A∈\0,1\^|V|×|V| is the corresponding adjacency matrix. Given a dataset D=(i,Gi=(Vi,i))i=1nD=\(I_i,G_i=(V_i,A_i))\_i=1^n, the goal is to learn a mapping h:ℐ→(V^,^)h:I→( V, A) that recovers the underlying adjacency structure. Since nodes are grounded in image space, node identities are defined by their spatial locations. During training, predicted nodes are aligned with ground-truth nodes via spatial matching, which induces a consistent ordering between V V and V. Under this correspondence, h is learned by minimizing the empirical loss ℒ(h)=1n∑i=1n[ℓnode(V^h(i),Vi)+ℓedge(^h(i),i)], (h)= 1n _i=1^n [ _node\! ( V_h(I_i),V_i )+ _edge\! ( A_h(I_i),A_i ) ], where ℓnode _node measures the difference between predicted and ground-truth node sets, and ℓedge _edge measures the discrepancy between predicted and ground-truth adjacency matrices under the induced node correspondence (e.g., cross-entropy loss). 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. 4. Methodology Given a node-link image I, VisAdj aims to recover the underlying graph by predicting a node set and an adjacency matrix, i.e., (V^(),^()) ( V(I),\, A(I) ). To this end, VisAdj follows a three-stage pipeline: 1) Image encoding: we encode I using a vision foundation model to obtain multi-scale features. 2) Node detection: the node set V^() V(I) is detected via node likelihood prediction. 3) Edge reasoning: based on V^() V(I), VisAdj aggregates image-level context with learnable topology tokens, adaptively selects candidate node pairs using an attention-sparse neighbor sampler (ASNS), and jointly infers connectivity by employing a line-graph transformer to model dependencies among edges and predict ^() A(I). The overall architecture of our framework is illustrated in Fig. 2, where the numbered blocks correspond to the main modules of VisAdj. In the following, we first detail the architecture and then describe the training strategy. 4.1. Architecture 4.1.1. Image Encoding Given an input node-link image ∈ℝH×W×3I ^H× W× 3 with resolution H×WH× W, we extract visual representations using a pretrained vision foundation model (1; 32) (e.g., SAM (26), SAM2 (38) and SAM3 (8)), as shown in block (#1) of Fig. 2. The encoder ℰEE_ θ_E first maps the input image to a backbone feature representation, which is further projected into two complementary feature streams (9): local _local =ℱL,L(ℰE())∈ℝHL×WL×DL, =F_L, θ_L (E_ θ_E(I) ) ^H_L× W_L× D_L, (1) global _global =ℱG,G(ℰE())∈ℝHG×WG×DG, =F_G, θ_G (E_ θ_E(I) ) ^H_G× W_G× D_G, where E θ_E denotes the parameters of the vision backbone. (HL,WL)(H_L,W_L) and (HG,WG)=(HL/λG,WL/λG)(H_G,W_G)=(H_L/ _G,W_L/ _G) denote the spatial resolutions of the local and global feature streams, respectively, and λG∈ℤ+ _G ^+ is the downsampling ratio. DL,DG∈ℤ+D_L,D_G ^+ are their corresponding feature dimensions. Both ℱL,LF_L, θ_L and ℱG,GF_G, θ_G are learnable feature representation modules parameterized by L θ_L and G θ_G (e.g., CNN (17)). The local feature stream retains higher spatial resolution and preserves fine-grained geometric cues that are important for accurate node localization. In contrast, the global stream aggregates features at a coarser spatial scale, enlarging the receptive field and capturing long-range context that is critical for subsequent edge reasoning. 4.1.2. Node Detection We detect graph nodes by estimating a dense node-likelihood map from localF_local, followed by peak extraction for node localization and feature sampling to obtain node descriptors. This node detection process is illustrated in block (#2) of Fig. 2. 1) Node likelihood prediction. We first predict a dense node-likelihood map over the image by applying a node prediction head ℋnode,NH_node, θ_N with parameters N θ_N to process localF_local: (2) ^=H,W[σ(ℋnode,N(local))]∈[0,1]H×W, M=U_H,W [σ (H_node, θ_N(F_local) ) ]∈[0,1]^H× W, where σ denotes the sigmoid function and H,WU_H,W is bilinear upsampling to the original image resolution. The resulting node-likelihood map M assigns each pixel a probability of being a graph node, providing dense spatial evidence for node existence. In practice, ℋnode,NH_node, θ_N is implemented as a convolutional predictor composed of CoordConv layers (33) followed by standard convolutions. 2) Peak extraction with subpixel refinement. Candidate nodes are extracted as local maxima in the predicted likelihood map. A pixel (x~,y~)∈ℤ2( x, y) ^2 is selected as a node candidate if ^[x~,y~]=max(u,v)∈r(x~,y~)^[u,v]and^[x~,y~]>τ, M[ x, y]= _(u,v) _r( x, y) M[u,v] M[ x, y]>τ, where r(x~,y~)N_r( x, y) denotes an r∈ℝ+r ^+-radius neighborhood around the pixel (x~,y~)( x, y), and τ∈[0,1]τ∈[0,1] is a confidence threshold. We apply non-maximum suppression (NMS) (22) to merge spatially nearby detections that correspond to the same node. To improve localization accuracy, we refine each detected peak using a differentiable soft-argmax operation. For a peak located at integer coordinates (x~,y~)( x, y), the subpixel-refined node coordinates are computed via (x,y)=∑(u′,v′)∈w(x~,y~)exp(^[u′,v′]/T)⋅(u′,v′)∑(u,v)∈w(x~,y~)exp(^[u,v]/T), (x,y)= _(u ,v ) _w( x, y) ( M[u ,v ]/T )·(u ,v ) _(u,v) _w( x, y) ( M[u,v]/T ), where w(x~,y~)N_w( x, y) denotes a local neighborhood of radius w∈ℝ+w ^+ and T∈ℝ+T ^+ is a temperature parameter controlling the sharpness of the localization. This procedure aggregates evidence from multiple pixels and yields node coordinates with continuous values, resulting in the final detected node set V^=(xi,yi)i=1N⊂ℝ2. V= \(x_i,y_i) \_i=1^N ^2. 3) Node descriptor extraction. For each detected node i, the refined coordinates are mapped to the local feature space (xiL,yiL)=(xi⋅WL/W,yi⋅HL/H)(x_i^L,y_i^L)= (x_i· W_L/W,\;y_i· H_L/H ). We extract a local node descriptor by bilinearly sampling localF_local at (xiL,yiL)(x_i^L,y_i^L): i=GridSample(local,(xiL,yiL))∈ℝDN, l_i=GridSample (F_local,(x_i^L,y_i^L) ) ^D_N, where DN∈ℤ+D_N ^+ is the node descriptor dimension. These descriptors encode visual and geometric features around each node and provide node-level representations for edge reasoning. 4.1.3. Edge Reasoning Having obtained the detected node set V^() V(I) and their local descriptors, we infer the adjacency matrix ^() A(I) by predicting edges over the detected nodes. Edge inference contains three stages: 1) global topology encoding, 2) sparse candidate edge generation, and 3) topology-aware edge reasoning. 1) Global topology encoding (block (#3) of Fig. 2). Edge connectivity in node-link images often depends on image-level structure, such as global layout and long-range connectivity. To incorporate such image-level context into edge reasoning, we introduce a transformer augmented with learnable topology tokens. Given the global feature map global∈ℝHG×WG×DGF_global ^H_G× W_G× D_G (Eq. 1), we flatten it into a sequence of spatial tokens and prepend KT∈ℤ+K_T ^+ learnable topology tokens topo∈ℝKT×DGZ_topo ^K_T× D_G. The resulting sequence is processed by a transformer parameterized by T θ_T concat=TransformerT[topo;Flatten(global)], _concat=Transformer_ θ_T [Z_topo\,;\,Flatten(F_global) ], where concat∈ℝ(KT+HGWG)×DGF_concat ^(K_T+H_GW_G)× D_G. Through self-attention, the topology tokens attend to all spatial tokens to aggregate image-level patterns, and subsequently propagate this global context back to every spatial token. Since topology tokens serve only as image-level topology carriers and have no spatial correspondence, we discard them after this interaction and retain the topology-enhanced spatial tokens, which are reshaped back into the global feature map: global′=Reshape(concat[KT:])∈ℝHG×WG×DG, _global =Reshape (F_concat[K_T:] ) ^H_G× W_G× D_G, The resulting feature map global′F_global encodes global structural context and is subsequently used to guide candidate edge selection and adjacency structure reasoning. 2) Sparse candidate edge generation (block (#4) of Fig. 2). Existing approaches typically produce candidate edges using fixed KNN-based methods (50; 43; 44), lacking adaptability to diverse node-link images. To address this limitation, we introduce an attention-sparse neighbor sampler (ASNS) that learns to select a high-recall set of candidate node pairs. For each detected node i, we first extract the global context i∈ℝDG g_i ^D_G by sampling global′F_global at the node location. Let Nh∈ℤ+N_h ^+ be the number of heads and d∈ℤ+d ^+ the output dimension of each head, with DN=Nh⋅dD_N=N_h· d. We compute a compatibility score between node i and j: sij=1Nh∑m=1Nh(qmi)⊤(kmj)d∈ℝ, s_ij= 1N_h _m=1^N_h (W_q^m l_i ) (W_k^m g_j ) d , where qm∈ℝd×DNW_q^m ^d× D_N and km∈ℝd×DGW_k^m ^d× D_G are learnable projections for the m-th head, with all parameters collected as S=qm,kmm=1Nh θ_S=\W_q^m,W_k^m\_m=1^N_h. Collecting all scores into ∈ℝN×NS ^N× N, we apply the entmax activation (37; 11): (3) =entmaxαent()∈ℝN×N, =entmax_ _ent(S) ^N× N, yielding a sparse attention distribution over potential neighbors for all nodes. The sparsity parameter αent∈[1,2] _ent∈[1,2] controls the degree of sparsity in the attention distribution, where larger values generally produce sparser outputs. For each node i, we retain the top-K∈ℤ+K ^+ neighbors according to i,:P_i,: to form a binary adjacency mask cand∈0,1N×NM_cand∈\0,1\^N× N. This learned mask focuses edge reasoning on a small set of plausible node pairs. 3) Topology-aware edge reasoning (block (#5) in Fig. 2). Given the candidate edge set defined by candM_cand, we infer the adjacency matrix by learning true edges from all candidates. Rather than predicting each edge independently, we formulate edge reasoning as a structured problem, where the existence of an edge depends not only on visual evidence and geometric constraints, but also on interactions with other edges. For each candidate node pair (i,j)(i,j), we construct an edge representation that integrates the following complementary features (3-a to 3-c) and jointly process all candidate edges using a line-graph transformer (3-d) that treats edges as tokens, enabling explicit modeling of edge dependencies. 3-a) Visual features. To capture visual cues associated with a potential connection between nodes i and j, we sample visual features along a smoothly curved path connecting their coordinates. Specifically, we model the path using a quadratic Bézier curve (13): ij(t) _ij(t) =(1−t)2(xi,yi)+2t(1−t)((xi,yi)+(xj,yj)2+ij) =(1-t)^2(x_i,y_i)+2t(1-t) ( (x_i,y_i)+(x_j,y_j)2+ δ_ij ) +t2(xj,yj),andij=MLPδ([i,j])∈ℝ2, +t^2(x_j,y_j), δ_ij=MLP_ θ_δ([ l_i, l_j]) ^2, where t∈[0,1]t∈[0,1] and ij δ_ij is a learned control offset representing a deviation relative to the midpoint between nodes i and j. We sample Nv∈ℤ+N_v ^+ evenly spaced interpolation points (xijn,yijn)=ij(nNv+1),n=1,…,Nv. (x_ij^n,y_ij^n)=c_ij\! ( nN_v+1 ), n=1,…,N_v. At each sampled location, we aggregate visual context within a rn∈ℤ+r_n ^+-radius neighborhood to obtain descriptors ijnn=1Nv\v_ij^n\_n=1^N_v, which are then processed by a transformer parameterized by vis θ_vis (4) vis=Transformervis(ijnn=1Nv)∈ℝDvis, f_vis=Transformer_ θ_vis (\v_ij^n\_n=1^N_v ) ^D_vis, where Dvis∈ℤ+D_vis ^+ denotes the visual feature dimension. This representation encodes stroke continuity and appearance consistency along the candidate connection. 3-b) Spatial features. For each candidate edge (i,j)(i,j), we encode geometric constraints using three spatial features: i) the normalized Euclidean distance dij=‖(xj,yj)−(xi,yi)‖2H2+W2∈[0,1]. d_ij= \|(x_j,y_j)-(x_i,y_i)\|_2 H^2+W^2∈[0,1]. i) the relative direction (5) ij=(xj−xi,yj−yi)‖(xj,yj)−(xi,yi)‖2∈ℝ2. _ij= (x_j-x_i,y_j-y_i)\|(x_j,y_j)-(x_i,y_i)\|_2 ^2. i) a path consistency score measuring the minimum normalized distance from other nodes k to the connection path ij(t)c_ij(t): oij=min1,mink∉i,jmint∈[0,1]‖(xk,yk)−ij(t)‖2‖(xj,yj)−(xi,yi)‖2∈[0,1]. o_ij= \1,\; _k∉\i,j\ _t∈[0,1] \|(x_k,y_k)-c_ij(t) \|_2\|(x_j,y_j)-(x_i,y_i)\|_2 \∈[0,1]. A large score oijo_ij indicates an unobstructed path, supporting the direct connectivity between i and j. The final spatial features are given by spatial=[dij,ij,oij]∈ℝ4 f_spatial=[d_ij,u_ij,o_ij] ^4. 3-c) Topology features. For each candidate edge (i,j)(i,j), we sample the topology-enhanced feature map global′F_global at the two endpoint locations to obtain global node descriptors (6) i=GridSample(global′,(xiG,yiG))∈ℝDG, g_i=GridSample (F_global ,(x_i^G,y_i^G) ) ^D_G, where (xiG,yiG)=(xi⋅WG/W,yi⋅HG/H)(x_i^G,y_i^G)=(x_i· W_G/W,\;y_i· H_G/H). j g_j is defined analogously. 3-d) Line-graph transformer for adjacency prediction. For each candidate edge (i,j)(i,j), we construct an edge-level representation ij∈ℝDE f_ij ^D_E with dimension DE∈ℤ+D_E ^+ by combining all the above features and positional encoding: ij=MLP1([spatial,vis,i,j])+MLP2([xi,yi,xj,yj]). f_ij=MLP_ θ_1 ([ f_spatial, f_vis, g_i, g_j] )+MLP_ θ_2 ([x_i,y_i,x_j,y_j] ). All candidate edges are collected into an edge-token tensor edge=ij∣cand[i,j]=1∈ℝ(NK)×DE. _edge= \ f_ij _cand[i,j]=1 \\;∈\;R^(NK)× D_E. We perform joint reasoning over these edge tokens by applying a line-graph transformer (LineGT), where attention is restricted to incident edges that share a common endpoint (6). This enables capturing structured interactions among adjacent edges, such as degree patterns, while avoiding interactions between unrelated pairs. Since ASNS retains at most K candidate neighbors for each of the N detected nodes, LineGT only needs to model interactions among a bounded number of incident candidate edges per node, resulting in complexity O(NK2)O(NK^2). After joint processing by LineGT with parameters line θ_line, each edge token is mapped to a scalar logit: (7) logits=MLP3(LineGTline(edge))∈ℝN×K. _logits=MLP_ θ_3 (LineGT_ θ_line (F_edge ) ) ^N× K. These logits are written back to a matrix logits∈ℝN×NA_logits ^N× N at the candidate locations indicated by candM_cand, while non-candidate entries are masked out and kept as non-edges. We then enforce symmetry and obtain the edge probability matrix via a sigmoid activation pred=σ(logits+logits⊤2)∈[0,1]N×N. _pred=σ ( A_logits+A_logits 2 )∈[0,1]^N× N. The final predicted adjacency matrix A is obtained by thresholding predA_pred with an edge threshold. 4.2. Training Training VisAdj involves two key objectives: i) establishing consistent correspondences between predicted and ground-truth nodes, and i) jointly optimizing node detection, sparse candidate edge generation, and final edge reasoning within a unified objective. In the following, we describe the training procedure in detail. Dataset preparation. To stabilize the early optimization of edge reasoning, we adopt a teacher-forcing strategy (4; 28), where edge prediction during training is conditioned on ground-truth nodes rather than detected nodes. This prevents early-stage node detection errors, including node omissions and inaccurate localization, from corrupting candidate generation and edge supervision. However, using ground-truth nodes throughout training may introduce a train-test discrepancy, since edge reasoning is conditioned on predicted nodes at inference time. To mitigate this discrepancy, we adopt a scheduled node-conditioning strategy that gradually exposes the edge reasoning module to predicted nodes during training. Let Vgt=(xjgt,yjgt)j=1NgtV^gt=\(x_j^gt,y_j^gt)\_j=1^N_gt denote the ground-truth node set and V^=(xi,yi)i=1N V=\(x_i,y_i)\_i=1^N denote the predicted node set. When the teacher-forcing strategy is used, we first perturb the ground-truth node coordinates by adding Gaussian noise: V~gt=(xjgt,yjgt)+ϵjj=1Ngt,ϵj∼(,σg2), V^gt= \(x_j^gt,y_j^gt)+ ε_j \_j=1^N_gt, ε_j (0, _g^2I), where σg∈ℝ+ _g ^+ is the noise standard deviation and Ngt∈ℤ+N_gt ^+ denotes the number of ground-truth nodes. At each training epoch e, the node set used for edge reasoning, which we denote as Vtrain=(xitrain,yitrain)i=1NtrainV_train=\(x_i^train,y_i^train)\_i=1^N_train, is sampled by Vtrain=V~gt,w.p.pe,V^,w.p. 1−pe,andpe=max(0,1−eTs), V_train= cases V^gt,&w.p.\,\,\,p_e,\\ V,&w.p.\,\,\,1-p_e, cases p_e= (0,1- eT_s ), where pe∈[0,1]p_e∈[0,1] represents the teacher-forcing probability and Ts∈ℤ+T_s ^+ denotes the number of epochs over which pep_e decays to zero. This schedule preserves stable edge supervision in early training and progressively shifts the conditioning distribution toward the inference-time setting, thereby reducing the train-test discrepancy. At inference time, ground-truth node coordinates are unavailable; VisAdj first detects the node set and then performs edge reasoning based only on the predicted node coordinates. Node Matching. Since the training node set used for edge reasoning may be unordered and may differ in cardinality from the ground truth, we establish correspondences based on spatial proximity using the Hungarian algorithm (7). Specifically, we compute a minimum-cost bipartite matching between VtrainV_train and VgtV^gt via (8) min∑i=1Ntrain∑j=1Ngtij‖(xitrain,yitrain)−(xjgt,yjgt)‖2, _X _i=1^N_train _j=1^N_gtX_ij \|(x_i^train,y_i^train)-(x_j^gt,y_j^gt) \|_2, s.t. ∑j=1Ngtij .t. \; _j=1^N_gtX_ij ≤1,∑i=1Ntrainij≤1,∑i=1Ntrain∑j=1Ngtij=min(Ntrain,Ngt) ≤ 1, _i=1^N_trainX_ij≤ 1, _i=1^N_train _j=1^N_gtX_ij= (N_train,N_gt) where ∈0,1Ntrain×NgtX∈\0,1\^N_train× N_gt denotes the binary matching matrix. After matching, only pairs whose distance is below the threshold τd∈ℝ+ _d ^+ are retained as valid correspondences. The resulting correspondences are used to construct ground-truth adjacency labels in the training node space, providing supervision for both candidate generation and edge prediction. Loss Functions. The training objective consists of three complementary losses to supervise three stages of the pipeline: node prediction, candidate generation, and edge reasoning. 1) Node mask loss. Node detection is supervised by minimizing the difference between the predicted node likelihood map M (Eq. 2) and the ground-truth M ℒnode(E,L,N)=λceℓce(^,)+λmseℓmse(^,), _node ( θ_E, θ_L, θ_N )= _ce\, _ce ( M,M )+ _mse\, _mse ( M,M ), where λce,λmse∈ℝ+ _ce, _mse ^+ are balancing weights. ℓce _ce denotes a weighted pixel-wise cross-entropy loss addressing foreground-background imbalance, and ℓmse _mse denotes the mean squared error measuring pixel-wise deviations between M and M. 2) Coverage Loss. The attention-sparse neighbor sampler outputs a sparse attention distribution i,:P_i,: (Eq. 3) over potential neighbors for each node. To encourage high-recall candidate generation, we supervise this distribution using a smoothed target derived from the ground-truth adjacency. For each matched training node i, the target distribution i∈ℝNtrainT_i ^N_train is defined as ij=(1−αs)[j∈gt(i)]|gt(i)|+αs1Ntrain−1,j≠i, _ij=(1- _s)\, I[j _gt(i)]|N_gt(i)|+ _s\, 1N_train-1, j≠ i, where gt(i)N_gt(i) denotes the ground-truth neighbor set mapped to the training node space via Eq. 8, I is the indicator function, and αs∈[0,1] _s∈[0,1] is a smoothing factor. The coverage loss is defined as the cross-entropy between predicted and target neighbor distributions: ℒcover(G,T,S)=−1Ntrain∑i=1Ntrain∑j=1,j≠iNtrainijlog(ij). _cover ( θ_G, θ_T, θ_S )=- 1N_train _i=1^N_train _j=1,\,j≠ i^N_trainT_ij (P_ij ). This loss encourages ASNS to assign non-negligible attention mass to all ground-truth neighbors of each node, thereby promoting high-recall candidate selection. 3) Edge loss. Edge reasoning is supervised by minimizing a focal loss defined on node-matched candidate adjacency entries. Let =(i,j)∣cand[i,j]=1C=\(i,j) _cand[i,j]=1\ denote the candidate edge set. For each candidate pair (i,j)∈(i,j) , we define pij=pred[i,j]p_ij=A_pred[i,j] if (i,j)(i,j) is a ground-truth edge after node matching, and pij=1−pred[i,j]p_ij=1-A_pred[i,j] otherwise. The edge loss is then defined as ℒedge(δ,vis,1,2,3,line)=−1||∑(i,j)∈αij(1−pij)γlog(pij) _edge ( θ_δ, θ_vis, θ_1, θ_2, θ_3, θ_line )=- 1|C| _(i,j) _ij(1-p_ij)^γ (p_ij) where αij _ij is set to αf _f for positive candidate edges and 1−αf1- _f for negative candidate edges. αf∈[0,1] _f∈[0,1] and γ∈ℝ+γ ^+ denote the balance and focusing parameters of focal loss (31), respectively. This formulation mitigates the severe class imbalance in graphs by down-weighting easy negative pairs and emphasizing hard edge decisions. Although the loss is applied per adjacency entry, edge probabilities are predicted jointly by the line-graph transformer, enabling structured dependencies among incident edges to be learned. Total loss. The overall objective of VisAdj is given by ℒtotal(E,L,N,G,T,S,δ,vis,1,2,3,line) _total ( θ_E, θ_L, θ_N, θ_G, θ_T, θ_S, θ_δ, θ_vis, θ_1, θ_2, θ_3, θ_line ) =λnode⋅ℒnode+λcover⋅ℒcover+λedge⋅ℒedge, = _node·L_node+ _cover·L_cover+ _edge·L_edge, where λnode,λcover,λedge∈ℝ+ _node, _cover, _edge ^+ are loss weights. Optimization scheme. The vision encoder is fine-tuned using Low-Rank Adaptation (LoRA) (23), while all remaining modules are trained from scratch. All trainable components are optimized jointly using the total loss ℒtotalL_total. Table 1. Dataset statistics. 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 5. Experiments 5.1. Experimental Settings 5.1.1. Dataset We evaluate VisAdj on four datasets spanning synthetic graphs, road and vessel networks. These datasets cover various graph types and visual styles. The detailed dataset statistics are summarized in Table 1 and each dataset is described below. 1) Synthetic Dataset: We construct a synthetic node-link image dataset to evaluate VisAdj under diverse graph structures and visual layouts. The underlying graphs are collected from the House of Graphs (10), covering planar/non-planar and tree/non-tree graphs. We generate graph layouts using the Fruchterman-Reingold and Kamada-Kawai algorithms (14; 25), and render them as RGB images at a resolution of 512×512512× 512. This dataset contains challenging structures such as frequent edge crossings and long-range connections, enabling evaluation beyond the regular patterns commonly observed in real-world networks. 2) Toulouse Dataset (3): The Toulouse dataset consists of binary road network images extracted from map imagery, with a resolution of 64×6464× 64. This dataset features a relatively clean visual appearance and mostly local connectivity, serving as a real-world benchmark for evaluating performance on well-structured sparse planar graphs. 3) US-Cities Dataset (18): US-Cities contains high-resolution satellite imagery from 20 U.S. cities. Following prior work (40), we extract overlapping 128×128128× 128 patches from the original 180 tiles of resolution 2048×20482048× 2048 to construct node-link images. Compared with Toulouse, this dataset contains more cluttered backgrounds, occlusions, and complex junctions, enabling more challenging evaluation on realistic large-scale road networks. 4) OCTA500 Dataset (29): OCTA500 is a retinal vessel imaging dataset that contains optical coherence tomography angiography scans with the corresponding vessel segmentation maps. We extract overlapping 256×256256× 256 patches from 500 scans with 6m×6m6\,m× 6\,m and 3m×3m3\,m× 3\,m fields of view to increase data diversity. This dataset is characterized by tree-like vessel graphs with fine-scale branches and low-contrast structures, making it suitable for evaluating graph recovery under noisy medical imaging conditions. Table 2. Main comparison results across all datasets. The best performance for each metric is highlighted in bold. 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) Toulouse G-SAM-Road++ 86.75 (0.51) 0.60 (0.14) 98.19 (0.35) 95.70 (0.46) 96.93 (0.41) 96.35 (0.32) 98.89 (0.29) G-RNGDet++ 77.66 (1.45) 0.75 (0.50) 95.12 (0.83) 94.52 (0.52) 94.82 (0.36) 91.24 (0.76) 98.67 (0.14) Any2Graph 93.45 (0.21) 0.13 (0.01) 98.26 (0.36) 97.53 (0.28) 97.89 (0.33) 98.87 (0.59) 99.31 (0.07) Sat2Graph 69.86 (1.73) 1.35 (0.29) 92.55 (0.77) 91.59 (0.35) 92.07 (0.58) 87.63 (0.79) 94.86 (0.56) VisAdj 94.38 (0.33) 0.11 (0.02) 98.33 (0.43) 98.15 (0.45) 98.24 (0.41) 99.15 (0.49) 99.60 (0.11) US-Cities G-SAM-Road++ 58.31 (1.13) 3.45 (0.31) 87.55 (0.82) 86.95 (0.86) 87.25 (0.85) 79.77 (1.17) 92.53 (0.90) G-RNGDet++ 48.74 (1.64) 5.69 (0.49) 79.63 (1.28) 80.03 (1.14) 79.83 (1.21) 72.04 (1.14) 90.20 (1.21) Any2Graph 55.64 (0.74) 3.86 (0.58) 86.07 (0.83) 85.38 (1.27) 85.72 (1.10) 76.94 (1.10) 91.84 (0.92) Sat2Graph 32.48 (1.13) 6.23 (0.23) 61.38 (0.65) 62.45 (0.84) 61.91 (0.73) 54.20 (0.43) 89.45 (0.95) VisAdj 68.57 (0.74) 0.57 (0.75) 93.86 (0.73) 93.06 (1.42) 93.46 (1.37) 88.54 (1.32) 96.68 (0.66) OCTA500 G-SAM-Road++ 51.76 (0.93) 3.12 (0.39) 81.91 (1.32) 82.76 (1.03) 82.32 (1.14) 77.66 (1.37) 91.25 (0.91) G-RNGDet++ 35.27 (1.48) 4.55 (0.53) 69.80 (1.48) 66.45 (1.18) 68.08 (1.31) 66.57 (1.46) 89.08 (1.11) Any2Graph 45.79 (1.27) 3.57 (0.17) 79.05 (1.17) 77.26 (1.56) 78.14 (1.32) 74.95 (1.72) 90.46 (0.92) Sat2Graph 27.15 (0.83) 6.54 (0.98) 56.42 (0.96) 55.84 (0.75) 56.13 (0.83) 49.09 (0.99) 86.28 (0.78) VisAdj 64.98 (0.59) 0.63 (0.50) 88.85 (0.75) 91.30 (0.64) 90.06 (0.72) 90.27 (0.81) 96.33 (0.64) 5.1.2. Baselines We compare VisAdj with four typical graph inference baselines, including G-SAM-Road++ (48), G-RNGDet++ (47), Any2Graph (27), and Sat2Graph (18). Here, G-SAM-Road++ and G-RNGDet++ denote the graph reasoning modules in SAM-Road++ (48) and RNGDet++ (47), respectively. These baselines cover complementary graph inference paradigms, including rule-based graph construction from visual predictions, sequential graph growing, and general end-to-end graph prediction. All baselines are implemented using their official codebases and adapted to the image-to-adjacency-matrix setting. 5.1.3. Evaluation Metrics We utilize the following metrics. 1) Graph-level metrics. We report Graph Isomorphism Rate (GIR) (21), which measures the percentage of predicted graphs that are exactly isomorphic to the ground-truth graphs. GIR is a strict metric and only counts a prediction as correct when the entire graph structure is perfectly reconstructed. We also report Graph Edit Distance (GED) (15), which quantifies global structural similarity via the minimum number of node and edge edit operations required to transform the predicted graph into the ground-truth graph. GIR and GED are computed using standard NetworkX implementations (16); for GED, we use a 300-second timeout per sample and report the mean over all test samples. 2) Subgraph-level metrics. We adopt TOPO Precision, Recall, and F1 score (18) to evaluate local topological consistency. For each matched node, TOPO compares the edge sets of the induced k-hop neighborhoods in the prediction and ground truth, where we set k=2k=2 in all experiments. Compared with exact graph-level metrics, TOPO metrics are more robust to small node or edge errors, and better reflect local structural correctness. 3) Element-level metrics. We report Node-F1 and Edge-F1 scores. Node-F1 evaluates node detection accuracy after spatial matching, where a predicted node is considered correct if it is matched to a ground-truth node within a distance threshold of 44 pixels for Toulouse and 88 pixels for other datasets. Edge-F1 measures pairwise connectivity accuracy over matched node pairs, isolating the quality of edge prediction from global graph-level correctness. 5.1.4. Training Settings To ensure a fair comparison, VisAdj and baselines use the same vision backbone, namely the SAM-ViT-B encoder. All models are trained for up to 200 epochs with early stopping based on validation performance. Each experiment is repeated three times with different random seeds, and we report the mean and standard deviation of all evaluation metrics. We optimize all trainable modules using AdamW (34). The initial learning rate is set to 1×10−31× 10^-3 for newly initialized modules and 1×10−41× 10^-4 for LoRA fine-tuning of the image encoder backbone. The learning rate follows a cosine decay schedule with a linear warmup of 10 epochs. The batch size is set to 96 and the training is conducted using Distributed Data Parallel (DDP) (30) on 4 NVIDIA L40S GPUs. For VisAdj, the key hyperparameters are set as follows. The entmax sparsity parameter is set to αent=1.5 _ent=1.5. The model uses KT=16K_T=16 topology tokens and a teacher-forcing decay length of Ts=30T_s=30. For candidate generation, VisAdj retains K=8K=8 neighbors on the Toulouse dataset and K=12K=12 neighbors on the other datasets. Detailed hyperparameter configuration can be found in our public GitHub repository. 5.2. Main Results and Analysis This section analyzes the comparative results and also presents sanity checks to validate that VisAdj works as designed. VisAdj consistently outperforms all baselines. As shown in Table 2, VisAdj achieves the best results across all four datasets and all evaluation metrics. On the Synthetic dataset, VisAdj improves the GIR from Any2Graph’s 53.79%53.79\% to 73.02%73.02\%, indicating a substantial improvement in recovering global graph structure. Similar gains are also observed on real-world data. For example, VisAdj achieves GIR scores of 68.57%68.57\% on US-Cities and 64.98%64.98\% on OCTA500, exceeding the strongest baseline, G-SAM-Road++, by clear margins. Beyond exact graph matching, VisAdj also achieves stronger local topological consistency, obtaining the highest TOPO-F1 scores on all datasets. For instance, VisAdj increases TOPO-F1 from G-SAM-Road++’s 82.32%82.32\% to 90.06%90.06\% on OCTA500. At the element level, VisAdj consistently delivers higher Edge-F1 scores, with Node-F1 exceeding 96%96\% across all datasets. These results collectively confirm that VisAdj recovers both global and local graph structure more faithfully than existing methods across various domains. In addition, the observed improvements are also substantially larger than the reported standard deviations. For instance, on the Synthetic dataset, VisAdj improves GIR by 19.23%19.23\% over the strongest baseline, while the corresponding standard deviations are below 0.6%0.6\%. Similar margins are also observed on US-Cities and OCTA500, supporting that the improvements are robust across random seeds. Performance gains mainly come from improved edge reasoning. According to Table 2, Node-F1 scores are already high across all methods and datasets, with relatively small variance between VisAdj and the baselines. In contrast, Edge-F1 exhibits substantially larger gaps. For example, VisAdj improves Edge-F1 from Any2Graph’s 59.14%59.14\% to 95.09%95.09\% on the Synthetic dataset, and from G-SAM-Road++’s 77.66%77.66\% to 90.27%90.27\% on the OCTA500 dataset. These results demonstrate that VisAdj achieves significantly stronger edge reasoning capability than existing methods, directly validating the core idea and design of our model. By incorporating the global structural context and jointly reasoning over candidate edges with a line-graph transformer, VisAdj produces more discriminative and structurally consistent edge predictions, which directly translates into improved graph-level correctness. Table 3. Performance of VisAdj with different image encoders on the Synthetic dataset. 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) SAM3 (8) 900 78.23 (0.27) 98.89 (0.35) 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. Stronger image encoders lead to better performance. Table 3 shows that VisAdj can benefit from stronger image encoders. Within the SAM-ViT family, increasing model capacity leads to steady improvements in graph-level accuracy: GIR increases from 73.02%73.02\% with SAM-ViT-B to 76.73%76.73\% with SAM-ViT-H. This trend indicates that larger encoders provide richer visual features that better support graph structure reasoning. Beyond model scale, replacing SAM with SAM2 further yields systematic gains. Under comparable sizes, SAM2-Hiera encoders consistently outperform their SAM-ViT counterparts. For example, GIR improves from 73.02%73.02\% using SAM-ViT-B to 75.56%75.56\% using SAM2-Hiera-B. These results echo the fact that SAM2 has stronger representation ability than SAM in general. However, the performance gains diminish as the representation ability of the image encoder increases. For example, replacing SAM2-Hiera-L with SAM3 only increases GIR from 78.08%78.08\% to 78.23%78.23\%. This suggests that once the image encoder offers sufficient representation capacity, visual encoding is no longer the primary bottleneck. Further performance improvements therefore depend more on graph structure reasoning. VisAdj enables robust graph reasoning under visual ambiguity. Fig. 3 qualitatively compares VisAdj with baselines. In visually challenging scenarios, such as cluttered backgrounds, closely spaced structures, and low-contrast vessel structures, the baselines often introduce spurious connections or miss true edges, indicating difficulty in inferring valid connectivity from local visual cues alone. In contrast, VisAdj consistently recovers adjacency structures that more closely match the ground-truth. On the synthetic dataset, VisAdj preserves long-range connections while suppressing implausible crossings. On road network images, it accurately recovers junction connectivity and road continuity, even when road segments are closely spaced or partially occluded. On OCTA500 vessel images, VisAdj correctly captures branching structures and vessel terminations while avoiding incorrect shortcuts. We further analyze representative failure cases in Fig. 4. VisAdj may still fail in densely connected regions with heavy edge crossings or visually ambiguous connections, where it may introduce incorrect shortcuts or miss weakly visible edges. However, even in these challenging cases, VisAdj generally produces fewer errors than the baselines, with more accurate node detection and fewer incorrect or missing edges, indicating stronger robustness under complex visual conditions. These qualitative results underscore the effectiveness of VisAdj in adjacency reasoning across diverse visual domains. 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. Method ms/image ↓ images/s ↑ Speedup ↑ G-SAM-Road++ 88.18 11.34 1.40×1.40× G-RNGDet++ 269.54 3.71 4.27×4.27× Any2Graph 102.25 9.78 1.62×1.62× Sat2Graph 147.93 6.76 2.34×2.34× VisAdj 63.17 15.83 – Runtime efficiency. We further evaluate inference efficiency on the US-Cities dataset with batch size 1 under the same evaluation settings. As reported in Table 4, VisAdj achieves the lowest latency and highest throughput among all compared methods, requiring only 63.1763.17 ms per image and processing 15.8315.83 images per second. Compared with G-SAM-Road++, Any2Graph, Sat2Graph, and G-RNGDet++, VisAdj is approximately 1.40×1.40×, 1.62×1.62×, 2.34×2.34×, and 4.27×4.27× faster, respectively. These results show that the proposed graph reasoning method improves effectiveness without sacrificing inference efficiency. The efficiency gain mainly comes from ASNS, which restricts edge prediction to a sparse set of plausible candidate pairs, and LineGT, which models dependencies only among incident candidate edges rather than performing dense all-pair interactions. Sensitivity analysis of four key hyperparameters on different datasets. Figure 5. Sensitivity analysis of key hyperparameters on Synthetic, Toulouse, US-Cities, and OCTA500 datasets. Sensitivity analysis of four key hyperparameters on different datasets. Analysis of sensitivity to key hyperparameters. We also analyze the sensitivity of VisAdj to four key hyperparameters: the entmax sparsity parameter αent _ent, the number of topology tokens KTK_T, the number of retained candidate neighbors K, and the teacher-forcing decay length TsT_s. The results are summarized in Fig. 5. 1) VisAdj is relatively robust to the sparsity parameter αent _ent, with αent=1.5 _ent=1.5 generally achieving the best GIR across datasets. This indicates that the model is not overly sensitive to the exact entmax sparsity level, as long as the attention distribution maintains a reasonable balance between sparsity and true-edge coverage. 2) For topology tokens, increasing KTK_T to 1616 clearly improves performance, while further increasing KTK_T only brings marginal gains. Since GIR becomes nearly saturated after KT=16K_T=16, we select KT=16K_T=16 to balance reconstruction accuracy and model size. 3) For Top-K candidate selection, a small K misses many true neighbors and leads to low edge recall, whereas a large K introduces many spurious neighbors and makes edge reasoning harder. Therefore, we set K=8K=8 for Toulouse and K=12K=12 for the other datasets, as the nodes in Toulouse road graphs contain fewer neighbors. 4) For the teacher-forcing decay length, a small TsT_s substantially degrades performance because edge reasoning is exposed to predicted nodes before node detection becomes reliable, leading to corrupted candidate generation and edge supervision. Increasing TsT_s improves training stability, but the gain from Ts=30T_s=30 to Ts=40T_s=40 is marginal. Therefore, we choose Ts=30T_s=30, which provides stable early edge supervision while allowing edge reasoning to adapt to predicted nodes sufficiently early during training. Taken together, the selected settings provide a practical trade-off while achieving strong and stable performance across datasets. 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). 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) 5.3. Ablation Study We conduct ablation studies on the Synthetic dataset to assess the contribution of key components in the VisAdj framework. Specifically, we evaluate five ablated variants, each modifying one component while keeping all other settings identical to the full model. 1) w/o LineGT: We replace the line-graph transformer (Eq. 7) with a standard graph transformer (49) that operates on node tokens. This variant removes the explicit modeling of edge-edge interactions among incident candidate edges and instead performs edge reasoning over node representations. 2) w/o ASNS: We replace the ASNS (Eq. 3) with fixed KNN-based candidate selection, while keeping all other modules unchanged. This variant directly compares learned adaptive candidate selection with fixed KNN selection under identical edge reasoning conditions. 3) w/o Visual: We remove the visual features (Eq. 4) sampled along candidate paths. 4) w/o Spatial: We remove the spatial features (Eq. 5) used for candidate edge representation. 5) w/o Topology: We remove the global topology-enhanced features (Eq. 6) for candidate edge representation. As shown in Table 5, each ablated variant results in a performance drop, confirming that the improvements of VisAdj rely on the coordinated design of all the proposed modules. 1) Effect of edge-edge dependency modeling. Among all components, LineGT has the largest impact. Replacing it with a standard graph transformer reduces GIR from 73.02%73.02\% to 54.43%54.43\% and Edge-F1 from 95.09%95.09\% to 72.63%72.63\%. This highlights the importance of explicitly modeling dependencies among incident candidate edges for globally consistent connectivity prediction. It also shows that edge-level structured reasoning is more effective than relying only on node-level graph reasoning for adjacency reconstruction. 2) Effect of adaptive candidate selection. ASNS also plays a critical role. Replacing ASNS with fixed KNN candidate selection reduces GIR from 73.02%73.02\% to 63.11%63.11\% and TOPO-F1 from 98.72%98.72\% to 86.47%86.47\%. This demonstrates that learned candidate generation is important for capturing long-range or visually ambiguous connections and for overcoming the limitations of fixed KNN neighborhoods. 3) Effect of edge representations. The remaining ablations validate the importance of visual, spatial, and topological features. Removing visual features reduces GIR to 66.30%66.30\%, showing that visual continuity cues along candidate paths help distinguish true edges from visually implausible connections. Removing spatial features or global topology features also leads to performance degradation, lowering GIR to 70.26%70.26\% and 68.59%68.59\%, respectively. This indicates that both geometric constraints and image-level structural context provide complementary signals for reliable edge reasoning. Comparison results for real-world road network extraction on SpaceNet and US-Cities datasets. 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. 5.4. Application in Road Network Extraction To evaluate practical applicability, we consider a real-world road network extraction scenario. This experiment follows the experimental protocol of SAM-Road++ (48) and assesses the effect of VisAdj on an existing road extraction pipeline. Specifically, we integrate VisAdj into SAM-Road++ by replacing its graph reasoning module with VisAdj, while keeping all other components unchanged. As shown in Fig. 6, SAM-Road++ already improves over SAM-Road, forming a strong baseline. Integrating VisAdj into SAM-Road++ further improves both TOPO-F1 and APLS on SpaceNet (42) and US-Cities datasets. On US-Cities, TOPO-F1 increases from 80.01%80.01\% to 81.95%81.95\%, and APLS improves from 68.34%68.34\% to 69.43%69.43\%. On SpaceNet, VisAdj also improves TOPO-F1 from 81.57%81.57\% to 82.68%82.68\% and APLS from 73.44%73.44\% to 75.36%75.36\%. These results show that VisAdj can be effectively integrated into real-world road extraction pipelines to improve both topological accuracy and path-level connectivity. 6. Conclusion and Future Work In this work, we propose VisAdj, a unified framework for reconstructing adjacency matrices from node-link images. VisAdj combines adaptive candidate edge generation with explicit modeling of edge dependencies via a line-graph transformer, substantially improving adjacency reasoning beyond existing approaches that rely on fixed KNN candidate selection and predict each edge independently. Future work will explore a permutation-invariant version (45) of VisAdj to decouple graph reasoning from node ordering and investigate broader application scenarios. Another promising direction is to extend VisAdj to more general visual inputs where graph structures are implicitly embedded, such as scene graphs. Acknowledgements. This project is supported in part by National Science Foundation under IIS-2144285 and IIS-2414308. GenAI Usage Disclosure During the preparation of this work, the authors used GenAI tools to help with code implementation and debugging. No GenAI tools were used in the collection, processing, or annotation of the datasets. GenAI tools were also used during the writing process to assist with grammar checking and sentence polishing. All core concepts, methodologies, and experimental results were developed independently by the authors. The authors have reviewed all GenAI-assisted content and take full responsibility for the accuracy and integrity of the work presented. References Awais et al. (2025) M. Awais, M. Naseer, S. Khan, R. M. Anwer, H. Cholakkal, M. Shah, M. Yang, and F. S. Khan Foundation models defining a new era in vision: a survey and outlook. IEEE Transactions on Pattern Analysis and Machine Intelligence 47 (4), p. 2245–2264. Cited by: §4.1.1. Bastani et al. (2018) F. Bastani, S. He, S. Abbar, M. Alizadeh, H. Balakrishnan, S. Chawla, S. Madden, and D. DeWitt Roadtracer: automatic extraction of road networks from aerial images. In Proceedings of the IEEE conference on computer vision and pattern recognition, p. 4720–4728. Cited by: §2. Belli and Kipf (2019) D. Belli and T. Kipf Image-conditioned graph generation for road network extraction. arXiv preprint arXiv:1910.14388 (). Cited by: §5.1.1. Bengio et al. (2015) S. Bengio, O. Vinyals, N. Jaitly, and N. Shazeer Scheduled sampling for sequence prediction with recurrent neural networks. Advances in neural information processing systems 28. Cited by: §4.2. Berger et al. (2025) A. H. Berger, L. Lux, S. Shit, I. Ezhov, G. Kaissis, M. J. Menten, D. Rueckert, and J. C. Paetzold Cross-domain and cross-dimension learning for image-to-graph transformers. In 2025 IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), p. 64–74. Cited by: §2. Cai et al. (2021) L. Cai, J. Li, J. Wang, and S. Ji Line graph neural networks for link prediction. IEEE Transactions on Pattern Analysis and Machine Intelligence 44 (9), p. 5103–5113. Cited by: §4.1.3. Cao et al. (2016) B. Cao, J. Wang, J. Fan, J. Yin, and T. Dong Querying similar process models based on the hungarian algorithm. IEEE Transactions on Services Computing 10 (1), p. 121–135. Cited by: §4.2. Carion et al. (2025) N. Carion, L. Gustafson, Y. Hu, S. Debnath, R. Hu, D. Suris, C. Ryali, K. V. Alwala, H. Khedr, A. Huang, et al. Sam 3: segment anything with concepts. arXiv preprint arXiv:2511.16719. Cited by: §4.1.1, Table 3. Carion et al. (2020) N. Carion, F. Massa, G. Synnaeve, N. Usunier, A. Kirillov, and S. Zagoruyko End-to-end object detection with transformers. In European conference on computer vision, p. 213–229. Cited by: §4.1.1. Coolsaet et al. (2023) K. Coolsaet, S. D’hondt, and J. Goedgebeur House of graphs 2.0: a database of interesting graphs and more. Discrete Applied Mathematics 325, p. 97–107. Cited by: §5.1.1. Correia et al. (2019) G. M. Correia, V. Niculae, and A. F. Martins Adaptively sparse transformers. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), p. 2174–2184. Cited by: §4.1.3. Das and Chanda (1997) A. K. Das and B. Chanda Adjacency matrix generation from the image of graphs: a morphological approach. Machine Vision and Applications 10 (1), p. 9–16. Cited by: §1. Farin (2014) G. Farin Curves and surfaces for computer-aided geometric design: a practical guide. Elsevier. Cited by: §4.1.3. Fruchterman and Reingold (1991) T. M. Fruchterman and E. M. Reingold Graph drawing by force-directed placement. Software: Practice and experience 21 (11), p. 1129–1164. Cited by: §5.1.1. Gao et al. (2010) X. Gao, B. Xiao, D. Tao, and X. Li A survey of graph edit distance. Pattern Analysis and applications 13 (1), p. 113–129. Cited by: §5.1.3. Hagberg et al. (2007) A. Hagberg, P. J. Swart, and D. A. Schult Exploring network structure, dynamics, and function using networkx. Technical report Los Alamos National Laboratory (LANL). Cited by: §5.1.3. He et al. (2016) K. He, X. Zhang, S. Ren, and J. Sun Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, p. 770–778. Cited by: §4.1.1. He et al. (2020) S. He, F. Bastani, S. Jagwani, M. Alizadeh, H. Balakrishnan, S. Chawla, M. M. Elshrif, S. Madden, and M. A. Sadeghi Sat2graph: road graph extraction through graph-tensor encoding. In European Conference on Computer Vision, p. 51–67. Cited by: §2, §5.1.1, §5.1.2, §5.1.3. He et al. (2022) Y. He, R. Garg, and A. R. Chowdhury Td-road: top-down road network extraction with holistic graph construction. In European Conference on Computer Vision, p. 562–577. Cited by: §1. Hetang et al. (2024) C. Hetang, H. Xue, C. Le, T. Yue, W. Wang, and Y. He Segment anything model for road network graph extraction. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, p. 2556–2566. Cited by: §1, §2. Hopcroft and Wong (1974) J. E. Hopcroft and J. Wong Linear time algorithm for isomorphism of planar graphs (preliminary report). In Proceedings of the sixth annual ACM symposium on Theory of computing, p. 172–184. Cited by: §5.1.3. Hosang et al. (2017) J. Hosang, R. Benenson, and B. Schiele Learning non-maximum suppression. In Proceedings of the IEEE conference on computer vision and pattern recognition, p. 4507–4515. Cited by: §4.1.2. Hu et al. (2022) E. J. Hu, Y. Shen, P. Wallis, Z. Allen-Zhu, Y. Li, S. Wang, L. Wang, and W. Chen LoRA: low-rank adaptation of large language models. In International Conference on Learning Representations, Cited by: §4.2. Jianu et al. (2014) R. Jianu, A. Rusu, Y. Hu, and D. Taggart How to display group information on node-link diagrams: an evaluation. IEEE Transactions on Visualization and Computer Graphics 20 (11), p. 1530–1541. Cited by: §1. Kamada and Kawai (1989) T. Kamada and S. Kawai An algorithm for drawing general undirected graphs. Information processing letters 31 (1), p. 7–15. Cited by: §5.1.1. Kirillov et al. (2023) A. Kirillov, E. Mintun, N. Ravi, H. Mao, C. Rolland, L. Gustafson, T. Xiao, S. Whitehead, A. C. Berg, W. Lo, et al. Segment anything. In Proceedings of the IEEE/CVF international conference on computer vision, p. 4015–4026. Cited by: §4.1.1, Table 3, Table 3, Table 3. Krzakala et al. (2024) P. Krzakala, J. Yang, R. Flamary, F. d’Alché-Buc, C. Laclau, and M. Labeau Any2graph: deep end-to-end supervised graph prediction with an optimal transport loss. Advances in Neural Information Processing Systems 37, p. 101552–101588. Cited by: §1, §2, §5.1.2. Lamb et al. (2016) A. M. Lamb, A. G. Alias Parth Goyal, Y. Zhang, S. Zhang, A. C. Courville, and Y. Bengio Professor forcing: a new algorithm for training recurrent networks. Advances in neural information processing systems 29. Cited by: §4.2. Li et al. (2024) M. Li, K. Huang, Q. Xu, J. Yang, Y. Zhang, Z. Ji, K. Xie, S. Yuan, Q. Liu, and Q. Chen OCTA-500: a retinal dataset for optical coherence tomography angiography study. Medical image analysis 93, p. 103092. Cited by: §5.1.1. Li et al. (2020) S. Li, Y. Zhao, R. Varma, O. Salpekar, P. Noordhuis, T. Li, A. Paszke, J. Smith, B. Vaughan, P. Damania, et al. PyTorch distributed: experiences on accelerating data parallel training. Proceedings of the VLDB Endowment 13 (12), p. 3005–3018. Cited by: §5.1.4. Lin et al. (2017) T. Lin, P. Goyal, R. Girshick, K. He, and P. Dollár Focal loss for dense object detection. In Proceedings of the IEEE international conference on computer vision, p. 2980–2988. Cited by: §4.2. Liu et al. (2026) J. Liu, D. Zhong, Y. Wang, Z. Yang, Z. Kang, G. Dong, Q. Zhan, P. Fang, and A. Liu Dual-pathway circuits of object hallucination in vision-language models. arXiv preprint arXiv:2605.13156. Cited by: §4.1.1. Liu et al. (2018) R. Liu, J. Lehman, P. Molino, F. Petroski Such, E. Frank, A. Sergeev, and J. Yosinski An intriguing failing of convolutional neural networks and the coordconv solution. Advances in neural information processing systems 31. Cited by: §4.1.2. Loshchilov and Hutter (2019) I. Loshchilov and F. Hutter Decoupled weight decay regularization. In International Conference on Learning Representations, Cited by: §5.1.4. Lu and Weng (2025) X. Lu and Q. Weng Deep learning-based road extraction from remote sensing imagery: progress, problems, and perspectives. ISPRS Journal of Photogrammetry and Remote Sensing 228, p. 122–140. Cited by: §2. Máttyus et al. (2017) G. Máttyus, W. Luo, and R. Urtasun Deeproadmapper: extracting road topology from aerial images. In Proceedings of the IEEE international conference on computer vision, p. 3438–3446. Cited by: §2. Peters et al. (2019) B. Peters, V. Niculae, and A. F. Martins Sparse sequence-to-sequence models. In 57th Annual Meeting of the Association for Computational Linguistics, ACL 2019, p. 1504–1519. Cited by: §4.1.3. Ravi et al. (2025) N. Ravi, V. Gabeur, Y. Hu, R. Hu, C. Ryali, T. Ma, H. Khedr, R. Rädle, C. Rolland, L. Gustafson, et al. Sam 2: segment anything in images and videos. In International Conference on Learning Representations, Vol. 2025, p. 28085–28128. Cited by: §4.1.1, Table 3, Table 3, Table 3. Saket et al. (2014) B. Saket, P. Simonetto, S. Kobourov, and K. Börner Node, node-link, and node-link-group diagrams: an evaluation. IEEE Transactions on Visualization and Computer Graphics 20 (12), p. 2231–2240. Cited by: §1. Shit et al. (2022) S. Shit, R. Koner, B. Wittmann, J. Paetzold, I. Ezhov, H. Li, J. Pan, S. Sharifzadeh, G. Kaissis, V. Tresp, et al. Relationformer: a unified framework for image-to-graph generation. In European conference on computer vision, p. 422–439. Cited by: §1, §2, §5.1.1. Tan et al. (2020) Y. Tan, S. Gao, X. Li, M. Cheng, and B. Ren Vecroad: point-based iterative graph exploration for road graphs extraction. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), p. 8907–8915. Cited by: §2. Van Etten et al. (2018) A. Van Etten, D. Lindenbaum, and T. M. Bacastow Spacenet: a remote sensing dataset and challenge series. arXiv preprint arXiv:1807.01232. Cited by: §5.4. Wang et al. (2024) S. Wang, J. Xie, Y. Wang, and G. Tong Query-decision regression for misinformation prevention in social networks. In International Conference on Computational Data and Social Networks, p. 48–60. Cited by: §4.1.3. Wang et al. (2025) S. Wang, J. Xie, Y. Wang, and G. Tong Data-driven decision making for social influence risk management. Risk Sciences 1, p. 100019. Cited by: §4.1.3. Xie and Tong (2025) J. Xie and G. Tong Advances in set function learning: a survey of techniques and applications. ACM Computing Surveys 57 (7), p. 1–37. Cited by: §6. Xie and Tong (2026) J. Xie and G. Tong VSAL: a vision solver with adaptive layouts for graph property detection. In Proceedings of the ACM Web Conference 2026, p. 798–809. Cited by: §1. Xu et al. (2023) Z. Xu, Y. Liu, Y. Sun, M. Liu, and L. Wang Rngdet++: road network graph detection by transformer with instance segmentation and multi-scale features enhancement. IEEE Robotics and Automation Letters 8 (5), p. 2991–2998. Cited by: §2, §5.1.2. Yin et al. (2025) P. Yin, K. Li, X. Cao, J. Yao, L. Liu, X. Bai, F. Zhou, and D. Meng Towards satellite image road graph extraction: a global-scale dataset and a novel method. In Proceedings of the Computer Vision and Pattern Recognition Conference, p. 1527–1537. Cited by: §1, §2, §5.1.2, §5.4. Ying et al. (2021) C. Ying, T. Cai, S. Luo, S. Zheng, G. Ke, D. He, Y. Shen, and T. Liu Do transformers really perform badly for graph representation?. Advances in neural information processing systems 34, p. 28877–28888. Cited by: §5.3. Zhang (2021) S. Zhang Challenges in knn classification. IEEE Transactions on Knowledge and Data Engineering 34 (10), p. 4663–4675. Cited by: §4.1.3.