VisAdj: Learning Adjacency Matrices from Node-Link Images

Jiahao Xie; Guangmo Tong

Source-linked AI summary

VisAdj: Learning Adjacency Matrices from Node-Link Images

Jiahao Xie, Guangmo Tong

arXiv:2608.21825v1Aug 22, 2026cs.AIcs.CVcs.LG

TL;DR

Recovering adjacency matrices from node-link images is difficult because fixed KNN candidate selection and independent edge prediction do not adequately capture long-range connections or edge dependencies. VisAdj uses adaptive candidate sampling and a line-graph transformer for joint edge inference, and it consistently outperforms existing baselines across synthetic, road-network, and vessel-image benchmarks. The method improves both global and local graph-structure recovery, while challenging visual conditions remain a scope boundary where errors can still occur.

Problem
Recovering adjacency matrices from node-link images matters when original graph data are unavailable, but existing methods use rigid KNN candidate selection and independently predict edges without modeling structural dependencies.
Method
VisAdj adaptively selects a high-recall set of candidate node pairs and jointly infers their edges with a line-graph transformer that models interactions among incident edges.
Results
VisAdj consistently outperforms all baselines across datasets and metrics, including over 15% higher graph isomorphism rate and over 8% higher edge prediction F1 score across diverse benchmarks.
Takeaways & Limitations
VisAdj more faithfully recovers global and local graph structure across synthetic graphs, road networks, and vessel images, including long-range connections and ambiguous crossings.
Takeaways & Limitations
In densely connected regions with heavy crossings or visually ambiguous connections, VisAdj may still introduce incorrect shortcuts or miss weakly visible edges.

Abstract

from arXiv · show

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.

1 Introduction

Recovering adjacency matrices from node-link images restores graph structure needed by downstream algorithms when original graph data are unavailable. Existing approaches struggle with long-range connections, ambiguous crossings, rigid candidate selection, and independent edge prediction; VisAdj addresses these limitations with adaptive sampling and joint edge inference.

Motivation: Node-link images visualize relational structures, but unavailable original graph data make adjacency structures inaccessible to downstream graph algorithms and learning models.The problem is recovering adjacency matrices directly from rasterized visual observations.
Existing limitations: Fixed KNN candidate selection faces a radius trade-off: small neighborhoods miss long-range connections, while large neighborhoods admit spurious candidates.This limitation is especially problematic for complex node-link images with crossings and varied graph structures.
Existing limitations: Independent edge prediction ignores node-level and graph-level dependencies that constrain structurally consistent graph connectivity.The cited examples include node degree limits and global properties such as planarity.
VisAdj: VisAdj adaptively samples a high-recall set of candidate node pairs and jointly infers candidate edges with a line-graph transformer.The transformer treats edges as tokens and models interactions among incident edges.
Results: Over 15% higher graph isomorphism rate and over 8% higher edge prediction F1 score are reported across diverse benchmarks.VisAdj also enhances existing road network extraction pipelines as a plug-in graph reasoning module.

2 Related Work

Image-to-graph research includes specialized road-network extraction and more general graph reconstruction methods. These approaches use learned visual and relational modeling, with general methods addressing permutation ambiguity through matching or transport-based objectives.

Road network extraction: Road-network methods reconstruct graphs by predicting junction connectivity, iteratively growing graphs, or learning node and edge representations with vision foundation models.Examples include Sat2Graph, RNGDet++, SAM-Road, and SAM-Road++.
General image-to-graph methods: RelationFormer jointly predicts nodes and edges through set prediction and bipartite matching for end-to-end graph inference.Its approach avoids explicit post-processing.
General image-to-graph methods: Any2Graph uses an optimal transport-based loss to better align predicted and ground-truth graphs under permutation ambiguity.Both methods move toward unified image-to-graph modeling.

3 Preliminary

The task is to learn a mapping from node-link images to predicted nodes and adjacency matrices for underlying undirected, unweighted graphs. Training aligns predicted and ground-truth nodes spatially, allowing adjacency discrepancies to be optimized under the induced correspondence.

Problem formulation: Each node-link image represents an undirected, unweighted graph G=(V,A), where A is a binary adjacency matrix.The dataset contains paired images and graphs.
Problem formulation: The goal is to learn a mapping h from images to predicted node sets and adjacency structures.The predicted graph is written as (V̂,Â).
Training objective: Spatial matching aligns predicted nodes with ground-truth nodes and induces a consistent ordering for adjacency comparison.Node identities are defined by their spatial locations in the image.
Training objective: The training objective combines node-set error with adjacency discrepancy under the induced node correspondence.The edge term can use cross-entropy loss.

4 Methodology

VisAdj reconstructs adjacency matrices through a staged pipeline that detects nodes, enriches global topology context, adaptively selects candidate edges, and jointly reasons over edge dependencies.

Image Encoding: VisAdj encodes node-link images with a vision foundation model, producing local and global feature streams for node localization and edge reasoning.The local stream preserves fine-grained geometric cues, while the global stream captures long-range context.
Node Detection: Nodes are detected from a dense likelihood map using peak extraction, non-maximum suppression, soft-argmax refinement, and local descriptor sampling.The resulting descriptors encode visual and geometric features around each node.
Global Topology Encoding: Learnable topology tokens aggregate image-level patterns and propagate structural context back to spatial features for candidate selection and adjacency reasoning.The topology tokens are discarded after enriching the spatial feature map.
Sparse Candidate Edge Generation: ASNS adaptively selects a sparse, high-recall set of candidate node pairs instead of relying on fixed KNN-based candidate generation.Compatibility scores are computed between nodes and converted with entmax to support sparse selection.
Topology-Aware Edge Reasoning: A line-graph transformer jointly infers candidate connectivity by modeling interactions among edges alongside visual and geometric evidence.Candidate edges are represented as tokens, and the resulting edge logits are symmetrized and thresholded into the predicted adjacency matrix.
Training: Training uses a decaying teacher-forcing schedule and distance-filtered spatial matching to supervise edge reasoning while shifting toward predicted-node conditioning.Inference performs node detection first, then edge reasoning using only predicted node coordinates.

5.1 Experimental Settings

VisAdj is evaluated across diverse graph-image datasets against four representative graph-inference baselines using graph-, subgraph-, and element-level metrics under standardized training conditions.

Datasets: The evaluation spans synthetic graphs, road networks, and vessel networks, covering varied graph structures and visual styles.The synthetic data include planar and non-planar, tree and non-tree graphs, with crossings and long-range connections.
Baselines: VisAdj is compared with G-SAM-Road++, G-RNGDet++, Any2Graph, and Sat2Graph.These baselines represent rule-based construction, sequential graph growing, and end-to-end graph prediction paradigms.
Metrics: Graph-level evaluation uses Graph Isomorphism Rate and Graph Edit Distance to measure exact reconstruction and global structural similarity.GED is computed with a 300-second timeout per sample and averaged over test samples.
Metrics: TOPO Precision, Recall, and F1 evaluate local topological consistency within induced 2-hop neighborhoods.These metrics are intended to be more robust than exact graph-level measures to small node or edge errors.
Metrics: Node-F1 measures spatially matched node detection, while Edge-F1 measures connectivity accuracy over matched node pairs.Matching uses a 4-pixel threshold for Toulouse and an 8-pixel threshold for other datasets.
Training: All models share the SAM-ViT-B vision backbone, train for up to 200 epochs with early stopping, and report means and standard deviations over three runs.Trainable modules are optimized with AdamW.

5.2 Main Results and Analysis

VisAdj achieves the strongest reported graph-recovery performance across datasets and metrics, with gains concentrated in edge reasoning. Qualitative and runtime analyses show stronger behavior under visual ambiguity and efficient inference, while failures remain under dense crossings and weak contrast.

Main comparison results: VisAdj achieves the best results across all four datasets and evaluation metrics, consistently outperforming every baseline.On the Synthetic dataset, GIR rises from Any2Graph’s 53.79% to 73.02%.
Main comparison results: 19.23%: VisAdj’s Synthetic GIR improvement over the strongest baseline exceeds the corresponding standard deviations, supporting robustness across random seeds.Similar margins are reported on US-Cities and OCTA500.
Edge reasoning analysis: VisAdj’s largest gains occur in edge reasoning: Synthetic Edge-F1 increases from Any2Graph’s 59.14% to 95.09%, while OCTA500 rises from 77.66% to 90.27% over G-SAM-Road++.Node-F1 already exceeds 96% across datasets, with smaller differences between methods.
Encoder analysis: Stronger image encoders improve graph-level accuracy, with Synthetic GIR increasing from 73.02% using SAM-ViT-B to 76.73% using SAM-ViT-H and 75.56% using SAM2-Hiera-B.The gain from SAM2-Hiera-L to SAM3 is marginal, increasing GIR from 78.08% to 78.23%.
Qualitative analysis: VisAdj more closely matches ground-truth connectivity in cluttered, closely spaced, low-contrast, and partially occluded scenes than the compared baselines.It preserves long-range connections, recovers junction and branching structures, and suppresses implausible crossings or shortcuts.
Failure cases: VisAdj can still make incorrect adjacency decisions under dense crossings, cluttered backgrounds, or weak visual contrast, despite generally producing fewer errors than baselines.Observed errors include incorrect shortcuts and missed weakly visible edges.
Runtime efficiency: 63.17 ms: VisAdj has the lowest reported latency and highest throughput on US-Cities, processing 15.83 images per second and running 1.40×–4.27× faster than the baselines.The efficiency gain is attributed to sparse candidate selection with ASNS and incident-edge dependency modeling with LineGT.
Sensitivity analysis: VisAdj remains sensitive to hyperparameter choices, although α_ent = 1.5 and T_s = 30 provide generally strong and stable settings.Too-short teacher-forcing decay exposes edge reasoning to unreliable predicted nodes and degrades performance; increasing T_s from 30 to 40 yields marginal gains.

5.3 Ablation Study

The ablations show that VisAdj’s coordinated components are important, with explicit edge-dependency modeling and adaptive candidate selection producing the largest gains. Visual, spatial, and topology features also provide complementary signals for edge reasoning.

Overall ablation findings: Each ablated variant results in a performance drop, confirming that VisAdj relies on the coordinated design of all proposed modules.The study evaluates five variants, each modifying one component while keeping other settings identical to the full model.
Effect of edge-edge dependency modeling: Replacing LineGT reduces GIR from 73.02% to 54.43% and Edge-F1 from 95.09% to 72.63%.This removes explicit modeling of dependencies among incident candidate edges.
Effect of adaptive candidate selection: Replacing ASNS with fixed KNN selection reduces GIR from 73.02% to 63.11% and TOPO-F1 from 98.72% to 86.47%.The comparison keeps all other edge-reasoning modules unchanged.
Road-network evaluation: Figure 6 reports road-network extraction results on the SpaceNet and US-Cities datasets using APLS, or Average Path Length Similarity.The supplied figure passage identifies the datasets and metric but does not report the plotted values.
Effect of edge representations: Removing visual features reduces GIR to 66.30%, while removing spatial or global topology features lowers GIR to 70.26% and 68.59%, respectively.Visual continuity, geometric constraints, and image-level structural context provide complementary signals.

5.4 Application in Road Network Extraction

VisAdj is integrated into SAM-Road++ by replacing its graph reasoning module while leaving other components unchanged. The integration improves both TOPO-F1 and APLS on SpaceNet and US-Cities.

Integration protocol: VisAdj replaces SAM-Road++’s graph reasoning module while keeping all other pipeline components unchanged.This evaluates VisAdj within an existing road-extraction pipeline.
US-Cities results: On US-Cities, TOPO-F1 increases from 80.01% to 81.95% and APLS improves from 68.34% to 69.43%.APLS is the reported road-network metric in this comparison.
SpaceNet results: On SpaceNet, TOPO-F1 improves from 81.57% to 82.68% and APLS from 73.44% to 75.36%.The gains are reported after integrating VisAdj into SAM-Road++.

6 Conclusion and Future Work

The paper concludes that VisAdj reconstructs adjacency matrices by combining adaptive candidate generation with explicit edge-dependency modeling. Future work targets permutation invariance and broader visual graph-reconstruction settings.

Conclusion: VisAdj combines adaptive candidate edge generation with explicit edge-dependency modeling through a line-graph transformer.The framework is intended for adjacency reconstruction from node-link images.
Future work: Future work will explore a permutation-invariant VisAdj to decouple graph reasoning from node ordering.The paper also identifies broader visual inputs, including scene graphs, as a future application area.

GenAI Usage Disclosure

The authors used GenAI tools for code implementation, debugging, grammar checking, and sentence polishing, but not for dataset collection, processing, or annotation.

Disclosure: GenAI tools assisted with code implementation, debugging, grammar checking, and sentence polishing.The authors state that core concepts, methodologies, and experimental results were developed independently.
Disclosure: GenAI tools were not used in dataset collection, processing, or annotation.The authors reviewed GenAI-assisted content and take responsibility for it.