- 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
-
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.
-
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.
-
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
-
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.
-
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.
-
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:
-
Could the authors provide further details on the real-world datasets, including how they were curated and their key statistics per graph?
-
Could the authors provide further details evaluator? How it was designed/implemented? Perhaps, strict/ soft agreement consistency?
2 comments
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.
We thank the reviewers for their feedback and for raising these concerns. Regarding the critical weaknesses:
We have updated the organization of the paper; we hope these revisions make the paper clearer and address the reviewer feedback.
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.
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:
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.
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.