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

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