Research map / Vision-language and multimodal / Multimodal LLMs
VisionGraph: Leveraging Large Multimodal Models for Graph Theory Problems in Visual Context
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces VisionGraph, a visual graph theory benchmark (8 tasks, 5,902 problems) for LMMs, and a Description-Program-Reasoning (DPR) agent that combines small-model graph descriptions, code generation, and Python tool use with GPT-4V.
Problem
LMMs' ability to perceive graph structures and perform multi-step reasoning on visual graphs (graph theory problems) is underexplored.
Approach
A visual graph theory benchmark extending NLGraph with NetworkX-rendered graphs, plus a DPR chain that interleaves small-model graph description, algorithm-aware code generation, and external Python execution to boost GPT-4V's multi-step graph reasoning.
Key results
- GPT-4V (DPR) with Python achieves 63.07% average connectivity accuracy and 63.35% on cycle, and 20.31% on shortest path, versus 54.98% for GPT-4V 2-shot on connectivity.
- Fine-tuned Llava-v1.5-13b with graph understanding data improves cycle accuracy from 52.83 to 60.38 for connectivity-type tasks and edge correct rate, but all LMMs have high edge error rates.
- Node recognition: GPT-4V 0-shot reaches 81.15% on cycle and 100% on Hamilton path, while Gemini trails GPT-4V on most node and edge recognition metrics.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add DPR with external Python to GPT-4V (ablation) | GPT-4V · VisionGraph Connectivity Avg. | accuracy: 54.98(19.13) -> 63.07(53.09) | Helped |
| Add DPR with external Python to GPT-4V (ablation) | GPT-4V · VisionGraph Cycle Avg. | accuracy: 52.35(0.52) -> 63.35(35.07) | Helped |
| Add DPR with external Python to GPT-4V (ablation) | GPT-4V · VisionGraph Shortest Path Avg. | accuracy: 6.25 -> 20.31 | Helped |
| Add DPR to GPT-4V (ablation) | GPT-4V · VisionGraph Connectivity Avg. | accuracy: 38.81(13.74) -> 56.87(42.58) | Helped |
| Add DPR to GPT-4V (ablation) | GPT-4V · VisionGraph Cycle Avg. | accuracy: 49.21(0.52) -> 51.30(16.23) | Helped |
| Add DPR to GPT-4V (ablation) | GPT-4V · VisionGraph Shortest Path Avg. | accuracy: 3.12 -> 12.50 | Helped |
| Add Graph Understanding Data (ablation) | Llava-v1.5-13b · VisionGraph Connectivity Avg. | accuracy: 52.83 -> 60.38 | Helped |
| Add Graph Understanding Data (ablation) | Llava-v1.5-13b · VisionGraph Cycle Avg. | accuracy: 47.12 -> 53.93 | Helped |
| Add DPR to Llava-v1.5-13b (ablation) | Llava-v1.5-13b · VisionGraph Connectivity Avg. | accuracy: 52.83 -> 66.31 | Helped |
| Add DPR to Llava-v1.5-13b (ablation) | Llava-v1.5-13b · VisionGraph Cycle Avg. | accuracy: 47.12 -> 61.26 | Helped |
| Add DPR to Llava-v1.5-7b (ablation) | Llava-v1.5-7b · VisionGraph Connectivity Avg. | accuracy: 53.27 -> 63.88 | Helped |
| Add DPR to Gemini (ablation) | Gemini · VisionGraph Connectivity Avg. | accuracy: 55.52(14.01) -> 49.32(24.79) | Hurt |
Surprising findings
- Fine-tuned LLaVA-v1.5 models outperform GPT-4V on node and edge recognition despite being much smaller.
- Edge recognition error rates exceed correct rates for nearly all LMMs, indicating poor graphical perception.
Limitations
- Node counts capped at 25 for undirected and 20 for directed graphs, limiting graph complexity.
- Imbalanced task and difficulty distribution across the eight problem types.
- Results depend on closed commercial API versions that may change over time.
Experimental setup
Datasets: NLGraph VisionGraph training set
Benchmarks: VisionGraph
Metrics: accuracy correct rate error rate
Baselines: MiniGPT-4 BLIP-2 InstructBLIP LLaVA-v1.5 SPHINX InternLM-XComposer Qwen-VL Gemini Pro GPT-4V
Builds on: NLGraph LLaVA LLM agents
Closest papers by meaning
- GITA: Graph to Visual and Textual Integration for Vision-Language Graph Reasoning (NeurIPS 2024 · similarity 0.90)
- Visual Graph Arena: Evaluating Visual Conceptualization of Vision and Multimodal Large Language Models (ICML 2025 · similarity 0.90)
- VisioMath: Benchmarking Figure-based Mathematical Reasoning in LMMs (ICLR 2026 · similarity 0.90)
- Mario: Multimodal Graph Reasoning with Large Language Models (CVPR 2026 · similarity 0.90)
- MMFineReason: Closing the Multimodal Reasoning Gap via Open Data-Centric Methods (NeurIPS 2026 · similarity 0.89)
- AStar: Boosting Multimodal Reasoning with Automated Structured Thinking (AAAI 2026 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.