acceptodds
Under review as a conference paper at ICLR 2027

Visual Graph Har(d)ness: From Perception to Reasoning in Vision-Language Models

Abstract

We introduce Visual Graph Harness (VGH), a comprehensive benchmark for evaluating graph understanding and reasoning in vision-language models (VLMs) from graph images. Unlike text-based graph benchmarks, VGH requires models to first perceive and interpret graph structure from visual input before performing graph computations. The benchmark covers a broad spectrum of capabilities, ranging from fine-grained graph perception tasks, such as determining node and edge existence and counting nodes and edges, to higher-level algorithmic reasoning tasks, including shortest-path computation, graph diameter, connected components, maximum clique, minimum vertex cover, maximum independent set, traveling salesman, and chordless cycle. VGH includes real-world graphs across diverse domains, including knowledge graphs, route maps, social networks, and commutative diagrams from topology. Commutative diagrams introduce additional visual challenges, such as mathematical notation, repeated node labels, and multiple edge types. For each graph, we construct multiple visualization variants by systematically varying the layout and semantic content of node and edge labels while preserving the underlying graph structure. This design enables controlled analysis of whether model performance depends on the graph structure itself or on properties of its visualization, such as layout or semantic information contained in node and edge labels. Beyond task accuracy, VGH therefore supports fine-grained evaluation of visual graph perception, algorithmic reasoning, semantic sensitivity, robustness to visualization changes, and consistency across related graph tasks

Primary area:
datasets and benchmarks
Keywords:
Benchmark, Vision-Language Models, Graph

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_6P7pOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The Visual Graph Harness (VGH) is a comprehensive benchmark designed to systematically assess the graph comprehension and reasoning performance of vision–language models (VLMs) when processing graph-structured visual inputs. In contrast to text-based graph benchmarks, VGH necessitates that models first visually perceive and interpret the underlying graph structure prior to executing any graph-based computations. The benchmark encompasses a broad range of tasks, from fine-grained perceptual tasks such as node and edge existence detection and counting, to complex algorithmic reasoning tasks including shortest-path computation, maximum clique, and traveling salesman problems. VGH includes real-world graphs from diverse domains such as knowledge graphs, route maps, social networks, and commutative diagrams from topology, with the latter introducing additional visual challenges including mathematical notation and multi-edges. For each graph, multiple visualization variants are generated by systematically manipulating layout parameters and label semantics while maintaining an invariant underlying graph topology. This design enables controlled experiments to disentangle whether model performance is driven primarily by structural information or by visualization-specific attributes. Beyond task accuracy, VGH supports fine-grained evaluation across several dimensions, including visual graph perception, algorithmic reasoning, semantic sensitivity, and robustness to visualization changes.

Critical strengths
  1. The paper addresses a timely, increasingly important topic as vision-language models (VLMs) rapidly advance and see broad real-world deployment. Despite the progress in VLMs, their ability to reason over structured, graph-based visual inputs remains critically underexplored. VGH addresses this gap at a critical juncture by providing the community with a structured evaluation framework for the systematic assessment and guidance of the development.

  2. The manuscript is well motivated and clearly delineates a key limitation of existing graph benchmarking protocols, specifically their dependence on textual graph representations that effectively circumvent the visual perception component of the task. The problem formulation is methodologically grounded: by constraining models to first infer graph structure from images prior to executing subsequent reasoning procedures, VGH defines a more realistic and challenging evaluation paradigm that more closely approximates conditions encountered in real-world deployment.

  3. The systematic generation of multiple visualization variants for each graph—modulating layout parameters and label semantics while preserving the underlying topology—constitutes a deliberate experimental design that enables the separation of topology-driven comprehension from sensitivity to superficial visual cues, a distinction that is largely neglected in most existing benchmarks.

Critical weaknesses
  1. The writing requires substantial improvement throughout the manuscript. For instance, Figure 1 appears in the Introduction without any accompanying explanation, only to be briefly described later in the manuscript. Furthermore, the individual elements within Figure 1 are insufficiently explained, leaving readers without a clear understanding of what is being conveyed.

  2. Although the authors highlight the inclusion of real-world graphs as a key contribution, the paper fails to sufficiently demonstrate how challenging these real-world instances are in practice. Moreover, the real-world graphs presented appear to be simpler than the synthetic graphs already covered in the benchmark, which raises questions about the actual contribution and added value of their inclusion.

  3. When a model outputs an incorrect response, it is unclear whether the error arises from insufficient visual perception of the graph topology or from deficient algorithmic reasoning despite an accurately perceived graph representation. The benchmark lacks a principled procedure for disentangling these two sources of error.

Questions for authors

Besides the weaknesses, some questions are below:

  1. Could the authors provide further details on the real-world datasets, including how they were curated and their key statistics per graph?

  2. Could the authors provide further details evaluator? How it was designed/implemented? Perhaps, strict/ soft agreement consistency?

2 comments

We thank the reviewers for their feedback and for raising these concerns. Regarding the critical weaknesses:

  1. We have updated the organization of the paper; we hope these revisions make the paper clearer and address the reviewer feedback.

  2. We thank the reviewer for raising this point. Our motivation for including real-world graphs is not necessarily to introduce more structurally complex graphs, but to provide additional challenges and a more realistic evaluation setting: Real-world graphs contain meaningful semantic information that may introduce semantic priors and affect model performance. This allows us to investigate models' sensitivity to semantic information and its visual representation, as discussed in Section 4.2. Moreover, domains such as commutative diagrams introduce additional visual challenges, including mathematical notation, repeated node labels, and multiple edges. Including graphs from real-world distributions allows us to evaluate models in settings closer to practical applications, providing a better indication of how they may perform in real-world scenarios. Therefore, we believe real-world graphs complement synthetic graphs by introducing different challenges rather than necessarily increasing structural difficulty.

  3. We addressed this concern by adding a new diagnosis experiment in Section 4.1. We included an experiment using text-only graph representations as a baseline for evaluating graph understanding performance. Moreover, we added an analysis to investigate the underlying causes of failures in graph reasoning tasks and distinguish perception failures from reasoning failures.

Questions:

  1. We collected real-world graphs from two sources: GraphArena and topology textbooks. For GraphArena, we used the graphs provided in the original benchmark, with modifications to their labels and visualizations to support our evaluation settings. For commutative diagrams, we collected graphs from topology textbooks. The diagrams were manually extracted and converted into graph representations by a human annotator, and subsequently verified by a human reviewer to ensure the correctness of the extracted structures. We have also added a new table (Table 4) in the appendix to provide more detailed statistics about the benchmark, including the number of instances per task and domain.

  2. In the evaluators, we use a rule-based evaluation protocol for all tasks, consisting of response parsing followed by strict and soft accuracy evaluation. We initially defined a finite set of acceptable patterns based on the expected output formats: (1) a list of nodes, (2) a numerical value, or (3) a binary yes/no answer. After running the models, we observed additional response patterns and used AI assistance to identify valid variations not covered by the initial patterns. For example, when a task requested the size of a ChordlessCycle, some models returned a list of nodes instead of a number. We extended the parser to accept such responses and extract the corresponding numerical answer. We similarly expanded the patterns to handle different valid output formats, including node labels with mathematical notation in commutative diagrams. After parsing, we evaluate responses using task-specific deterministic evaluators. We report two metrics: strict accuracy, which measures whether the prediction is correct, and soft accuracy, which measures how close the prediction is to the correct answer. By definition, soft accuracy is always greater than or equal to strict accuracy, as a strictly correct response receives full credit under both metrics, while soft accuracy can additionally assign partial credit to incorrect responses.

Thank you for the response. Unfortunately, it came only a few hours before the deadline, which left little time for discussion. I believe the main concern requires restructuring the paper, which adding a few sentences cannot address. I also find it difficult to confirm a clear improvement from the new experiments in Section 4.1. I will therefore maintain my original rating.

Reviewer_yVHGOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces Visual Graph Harness, a benchmark for evaluating vision language models on graph understanding and reasoning from images. It includes graphs from multiple domains, such as knowledge graphs, route maps, social networks, and mathematical diagrams. The benchmark covers tasks from basic graph understanding to polynomial time and NP complete graph problems. The authors evaluate a range of open source VLMs. They analyze how performance changes with semantic label anonymization, visualization layout, and graph size. The main contribution is a benchmark with visualization variants and empirical analysis.

Critical strengths
  1. I appreciate the inclusion of commutative diagrams alongside knowledge graphs, route maps, and social networks. Mathematical notation, repeated labels, and multiple edges introduce challenges that are less visible in graphs with simple numeric labels. This broadens the benchmark's relevance to reading mathematical and scientific diagrams, where identifying the correct objects and their connections is essential.

  2. Reporting parsability, strict accuracy, and soft accuracy gives a more informative picture than exact accuracy alone. In particular, the gap between strict and soft scores on difficult tasks helps distinguish complete success from outputs that receive partial credit. This can make the benchmark useful for tracking progress when exact solutions remain rare.

Critical weaknesses
  1. The introduction contains very few references, and several claims about the limitations of existing benchmarks are not supported by citations where they are made. Although Section 2 discusses relevant work, the connection between prior findings and the proposed research gap could be clearer. VisionGraph studies visual structure perception [1], GITA examines layout augmentation and visual-textual integration [2], Visual Graph Arena evaluates reasoning across layouts [3], and Graph-to-Vision considers parsing and reasoning over visual graphs [4]. Explaining what these studies have established and what remains open would help readers assess VGH's additional contribution. The presentation also needs some care: Section 2 contains two largely repeated VLM benchmarking paragraphs, the introduction refers to Table 2 instead of Table 1 for the benchmark comparison, and a model comparison in Section 4.1 omits the model names. My concern here is primarily about the writing and organization of the paper. A clearer account of prior progress and VGH's contribution would make it substantially easier for a broader readership to understand the findings and draw useful insights from the benchmark.

  2. The diagnostic interpretation needs a clearer connection to what the evaluation directly measures. The graph understanding tasks offer useful perception-related probes, but their scores do not establish whether the structure needed for a particular reasoning answer was recovered correctly. The difference between understanding-task and reasoning-task accuracy therefore does not by itself isolate a reasoning deficit. Similarly, label anonymization changes visual complexity as well as semantic content. Section 4.2 acknowledges visual simplification as a possible explanation, but some statements still describe this comparison as quantifying reliance on semantic priors. A comparison using the gold graph structure as input, or a more careful statement of these interpretive limits, would strengthen the diagnostic contribution. At present, I find the evidence for the benchmark's diagnostic value less convincing than the evidence for its breadth of coverage.

[1] VisionGraph: Leveraging Large Multimodal Models for Graph Theory Problems in Visual Context. ICML 2024.

[2] GITA: Graph to Visual and Textual Integration for Vision-Language Graph Reasoning. NeurIPS 2024.

[3] Visual Graph Arena: Evaluating Visual Conceptualization of Vision and Multimodal Large Language Models. ICML 2025.

[4] Graph-to-Vision: Multi-graph Understanding and Reasoning using Vision-Language Models. arXiv 2025.

Questions for authors
  1. Could the authors clarify which limitations of existing visual graph benchmarks VGH specifically addresses, and connect those claims to the relevant findings in [1–4]? The discussion of graph reasoning over real-world diagrams in a recent survey [5] is also relevant here. VGH's layout variations, perception-related tasks, and graph reasoning tasks fit naturally within the survey's rendering–perception–inference (RPI) framework. Discussing this connection would help clarify how VGH builds on existing work and what additional coverage or diagnostic insights it provides.

  2. Which results support separating visual structure recovery errors from downstream reasoning errors? Could the authors provide or discuss a comparison using the gold graph structure as input, and clarify which conclusions about label semantics remain justified when anonymization also changes visual complexity?

  3. In Appendix E, the Minimum Vertex Cover prompt ends by requesting a maximum independent set. Is this a manuscript error, or was this wording used in the experiments? If it was used, how might it affect the corresponding results? This clarification matters for interpreting the task scores.

[5] When Vision Meets Graphs: A Survey on Graph Reasoning and Learning. IJCAI 2026, Survey Track.

4 comments

We thank the reviewers for their feedback and for raising these concerns. Regarding the critical weaknesses:

  1. We have updated the organization of the paper and included references for the claims in the introduction; we updated the related work section to address the concerns and corrected the mismatch in references. We hope these revisions make the findings clearer and more robust.

  2. To address these concerns, we added 2 more experimental settings:

    (a) We ran the graph understanding tasks without the graph image and with the graph as textual input. This experiment analyzes the underlying cause of the error and determines if it was due to perception error or reasoning. The details and analysis are added in Section 4.1

    (b) We included another visualization (gold visualization) in which the node names are removed, but the graph structure is preserved. We have revised the claims throughout the paper, particularly in Sections 3.3 and 4.2, to clarify that these comparisons measure model sensitivity to label representation rather than directly quantifying reliance on semantic priors. We have also extended the analysis to include unlabeled graph representations and explicitly discuss the interpretive limitations of these comparisons

Questions:

Q2) We added one experiment to investigate the distinction between visual perception and graph reasoning, in Section 4.1 (Figure 3), where we provide models with the ground-truth graph structure as textual input instead of the graph image. This comparison allows us to examine whether models can solve the same reasoning tasks when the visual perception requirement is removed. We categorize the outcomes based on model correctness across the two representations, distinguishing cases where models succeed only with textual input, fail with both representations, or succeed only with visual input. Regarding label semantics, we agree that anonymization changes both the semantic content and visual complexity of node and edge labels. Therefore, the observed performance differences cannot be attributed exclusively to semantic priors. Our results demonstrate that model performance is sensitive to label anonymization, with the magnitude and direction of this sensitivity varying across models, tasks, and graph domains. However, they do not isolate whether these differences arise from semantic information, visual simplification, or their interaction. We have revised the manuscript to clarify this limitation and avoid interpreting the observed differences as a direct quantification of reliance on semantic priors.

Q3) Thanks for checking the manuscript diligently. There was a manuscript error in the prompts, and we corrected the prompt in the manuscript.

Q1) We thank the reviewer for this question and for pointing us to the survey [5]. Below we summarize what each prior work established, what remains open, and what VGH adds. We have revised Section 2 accordingly.

What prior work established:

  • VisionGraph [1] renders the synthetic graphs of NLGraph with a single, manually adjusted layout and numeric node identifiers. It reports node and edge recognition separately from task accuracy and finds that all LMMs perceive graph structure poorly, which it links to weak downstream problem solving. This link is correlational: since the same graphs are never given as text, individual failures cannot be attributed to perception or to reasoning. Most of its metrics score only exact or step-verified correctness.

  • GITA [2] builds GVLQA from NLGraph graphs with numerically relabeled nodes. It shows that visual and textual inputs are complementary: vision helps on tasks such as Cycle and BGM, while text is stronger on sequence-type tasks (TS, SP, HP). It also shows that layout augmentation of the training data greatly improves a fine-tuned vision-only model. Layout variation there is a training tool; it is not used to test the zero-shot robustness of off-the-shelf VLMs to different renderings of the same graph. Its real-world experiments use k-hop subgraphs for node classification and link prediction rather than algorithmic graph reasoning, and all metrics are exact match.

  • Visual Graph Arena [3] tests generalization across layouts by training on one layout (e.g., Kamada-Kawai) and testing on another (planar). Fine-tuned vision models and frontier LLMs largely fail, while humans are near-perfect. Its graphs are synthetic, unlabeled, and limited to 8-9 nodes, and there is no comparison with text input.

  • Graph-to-Vision [4] moves to realistic diagrams (knowledge graphs, flowcharts, mind maps, route maps) in a multi-graph setting. Its questions are open-ended, and GPT-4o scores answers on a 1-5 scale along parsing, reasoning-consistency, and instruction-accuracy dimensions. It does not vary layouts, anonymize labels, or compare with a text baseline.

What remains open:

Prior work establishes that VLMs struggle to perceive graph structure, that layout matters, and that visual and textual inputs are complementary. Three gaps remain: (i) algorithmic reasoning, with answers checked against ground truth, over real-world graph images that keep their original semantic labels; prior work uses synthetic or anonymized graphs [1-3] or open-ended questions scored by a judge [4]; (ii) controlled zero-shot evaluation of the same graph under different renderings and label conditions; (iii) a direct, per-instance way to separate perception failures from reasoning failures.

What VGH adds:

(i). Real-world, semantically labeled graphs at larger scale with algorithmic tasks. VGH covers knowledge graphs, route maps, academic and social networks, and a new commutative-diagram domain. Graphs have up to 50 nodes and keep their original labels. Tasks range from perception (NodeCheck, NodeCount, NodeDegree, EdgeCount) to polynomial-time and NP-complete reasoning. Commutative diagrams add mathematical notation, repeated node labels, and multi-edges, which none of [1-4] include.

(ii). Same-graph rendering variants, evaluated zero-shot. We hold the graph fixed and vary the layout (DOT vs. NEATO) and the label condition (original, anonymized, unlabeled). Whereas [3] studies layout shift on unlabeled synthetic graphs and [2] uses layouts for training augmentation, VGH measures the zero-shot sensitivity of VLMs to both layout and label representation on real graphs.

(iii). Deterministic, graded evaluation. All answers are checked against ground truth computed from the graph. We report parsability, strict accuracy, and soft accuracy. This avoids relying on an LLM judge [4] and gives partial credit on hard tasks, where exact accuracy cannot distinguish models (exact NP-complete accuracy is at most 13.3%, while soft accuracy reaches 27.3%).

(iv). Instance-level attribution of perception vs. reasoning failures (Sec. 4.1, Fig. 3). We provide the gold graph structure as text and compare it with the image condition, labeling each instance as a perception failure, a reasoning failure, or an inconsistency (correct from the image but wrong from text). This turns the perception-reasoning link that [1] argued by correlation into a direct per-instance measurement, and it complements the modality findings of [2]: we observe such inconsistencies in every model.

Q1) Connection to the RPI framework [5]:

We agree that VGH fits naturally within the Rendering-Perception-Inference framework of [5], and we have added this connection to Section 2. VGH varies the rendering (layout and label representation) while holding the graph fixed. It probes perception through graph-understanding tasks and commutative diagrams, which stress OCR, symbol recognition, and label-to-node binding, the bottlenecks [5] identifies for real-world diagrams. Its text-vs-image comparison (Sec. 4.1) locates each failure at the perception or inference stage, as [5] recommends.

We also acknowledge the limits of VGH under this view: rendering variation is limited to two Graphviz layouts, we do not study multi-image reasoning [4] or training-time interventions [2, 3], and a failure under both input conditions may still have a perception component.

Reviewer_yVHGOpenReview ↗

Response to authors

Thank you for the author's response. I think the revised manuscript has addressed my concerns and clarified the positioning of the article. I have no further questions. I am willing to adjust my assessment accordingly.

Reviewer_2HJNOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper introduces Visual Graph Harness (VGH), a benchmark for evaluating vision-language models (VLMs) on graph understanding and reasoning from graph images rather than textual serializations. VGH contains 8,251 real-world graphs (3–50 nodes) from knowledge graphs, route maps, social networks (drawn from GraphArena), plus a new commutative-diagram domain extracted manually from topology textbooks, which introduces mathematical notation, repeated node labels, and multiple edge types.

Critical strengths

The multi-variant design (layout × anonymization on identical underlying graphs) is a principled way to factor visualization and semantic content out of structural reasoning, and the commutative-diagram domain is a distinctive stress test.

The evaluation protocol is more diagnostic than standard accuracy-only benchmarks: parsability gates, strict vs. soft accuracy, response-bias ratios, graph-constraint violations, and ungrounded node hallucinations.

Critical weaknesses

The benchmark does not deliver its central promise of separating perception from reasoning. No textual/LLM baseline is run on the same graphs, so failures cannot be attributed to perception versus computation; the paper's "from perception to reasoning" framing is asserted, not measured. The abstract and introduction also promise evaluation of "consistency across related graph tasks," yet no consistency experiment appears anywhere.

The headline findings are descriptive and under-powered. "Scaling does not help" rests on single within-family comparisons (Qwen3-VL-8B 54.8 vs. 32B 49.7) without statistics; cross-model comparisons use a fixed token budget across tokenizers, a confound the authors themselves cite as ranking-distorting; and per-task, per-domain instance counts are unreported.

Questions for authors

See the above

1 comment

We appreciate the reviewer for their constructive comments; here are the updates to address your concerns:

We have updated the organization of the paper and included additional statistics and analyses to better support our claims. We hope these revisions make the findings clearer and more robust.

We ran an additional experiment using text-only graph representations as a baseline to evaluate graph-understanding performance. Moreover, we added an analysis to investigate the underlying causes of failures in graph reasoning tasks and distinguish perception failures from reasoning failures. While our initial consistency analysis focused on the relationship between graph perception and understanding tasks, we have revised it to examine cases where a model correctly solves a task when given a graph as an image but fails when the same graph is provided as text. The details of these experiments and analyses are included in Section 4.1.

"per-task, per-domain instance counts are unreported"

We have added a new table (Table 4) in the appendix that provides detailed benchmark statistics, including the number of instances for each task and domain

“comparisons use a fixed token budget across tokenizers, a confound the authors themselves cite as“

We acknowledge that using a fixed token budget across models with different tokenizers may introduce differences in the effective generation budget and potentially affect cross-model comparisons. We investigate this issue and measure the percentage of cases in which each model exceeds the allocated token budget, reported in the following table:

ModelGraph UnderstandingPolynomial-Time ReasoningNP-Complete Reasoning
Qwen3-VL-32B0.730.460.05
Qwen3-VL-8B0.220.210.18
InternVL-30B0.000.000.03
InternVL-14B0.160.130.49
InternVL-8B0.000.010.12
Gemma3-1B0.000.010.06
Gemma3n-E4B0.000.070.37
Gemma4-E4B0.884.657.57
LLaVA-13B0.1021.781.52
LLaVA-7B0.000.100.14
GLM-V-10B3.552.660.00
Molmo2-8B0.000.000.02
DeepSeekVL-Tiny0.000.000.71
MiniCPM0.9310.370.23

As shown in the table, the rate of exceeding the token budget is below 1% for most models across all three task categories. In particular, 11 out of 14 models exceed the budget in fewer than 1% of graph understanding cases, and 11 out of 14 models do so for NP-complete reasoning tasks. However, a few models show higher rates, particularly LLaVA-13B (21.78%) and MiniCPM (10.37%) on polynomial-time reasoning tasks, and Gemma4-E4B (7.57%) on NP-complete reasoning tasks. We inspected the responses from LLaVA-13B and observed that its high rate of exceeding the token budget was mostly associated with an end-of-sequence generation issue. In many cases, the model correctly generated a numerical answer but continued repeating the same answer instead of terminating the generation, until it reached the token limit. Therefore, these cases do not necessarily indicate that the allocated token budget was insufficient for solving the task, but rather reflect a failure to terminate generation properly.

These results suggest that the fixed token budget is unlikely to substantially affect the reported performance of most models, as the vast majority of their responses remain within the allocated budget. Nevertheless, we acknowledge that the budget may affect the performance of specific models with higher truncation rates. We will include this analysis in the revised paper and clarify this limitation when interpreting cross-model comparisons.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.