PaperlayerView exact revision on arXiv

Source-linked AI summary

MVGraph: Benchmarking LVLMs on Evidence Composition across Multi-View Visual Graph

Yingjie Zhu, Han Cheng, Xuefeng Bai, Youcheng Pan, Yang Xiang, Kehai Chen

arXiv:2610.12961v1cs.CVcs.CL

TL;DR

Existing evaluations largely test reasoning over a single graph, leaving underexplored queries that require aligning and combining evidence across interrelated views. MVGRAPH contains 72,000 instances spanning two scenarios and 37 graph-theoretic and diagnostic tasks, each validated so no individual view contains sufficient evidence to determine the answer. Across 15 LVLMs, multi-view graph reasoning remains challenging, with cross-view edge alignment and relation-level composition prominent weaknesses and temporal reasoning remaining difficult.

  • Problem

    Existing evaluations largely test reasoning over a single graph, leaving underexplored queries that require aligning and combining evidence across interrelated views.

    Source: §1 · p. 1

  • Method

    MVGRAPH contains 72,000 instances spanning two scenarios and 37 graph-theoretic and diagnostic tasks, each validated so no individual view contains sufficient evidence to determine the answer.

    Source: §1 · p. 2

  • Results

    Across 15 LVLMs, multi-view graph reasoning remains challenging, with cross-view edge alignment and relation-level composition prominent weaknesses and temporal reasoning remaining difficult.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    The evaluations identify relation-level alignment, faithful evidence composition, and temporal reasoning as important directions for improving multi-graph understanding.

    Source: §6 · p. 9

Abstract

from arXiv · show

We introduce MVGraph, a benchmark for evaluating large vision-language models (LVLMs) on multi-graph reasoning where the evidence required by a query is distributed across multiple interrelated visual graph views. Although such evidence commonly resides in source-specific graphs, temporal snapshots, or local observations, existing graph reasoning benchmarks remain confined to a single self-contained structure, assessing only graph perception and reasoning while leaving the alignment and composition of evidence across views underexplored. MVGraph comprises 8k instances spanning 8 \textit{graph-theoretic} tasks, abstracted from two multi-graph scenarios (partial and temporal graph views). Each problem is programmatically constructed and verified to be unsolvable from a single view. Beyond end-to-end evaluation, we decompose multi-graph reasoning into four complementary capabilities---Perception, Alignment, Composition, and Reasoning---and design 29 diagnostic tasks with 64k instances to probe each one, along with golden intermediate representations for evaluating the intermediate process. Across 15 LVLMs, we reveal the difficulty of multi-graph reasoning and identify cross-view edge alignment and relation-level composition as prominent bottlenecks through stage-oriented diagnostics. Meanwhile, temporal constraints and increasing view counts expose further capability boundaries. Code and data are available at https://github.com/AAAndy-Zhu/MVGraph.

1 INTRODUCTION

Multi-graph queries often require combining evidence distributed across interrelated views, while existing evaluations largely test reasoning over a single graph. MVGRAPH evaluates this setting and diagnoses the capabilities involved, finding persistent difficulties in cross-view alignment, composition, and temporal reasoning.

1 INTRODUCTION

  • Existing graph evaluations largely focus on perceiving and reasoning over one self-contained graph, leaving cross-view correspondence and evidence composition underexplored.Queries may depend on complementary source-specific graphs, temporal snapshots, or local observations.Source: §1 · p. 1
  • MVGRAPH contains 72,000 instances across two scenarios and 37 tasks, validated so no individual view alone provides sufficient evidence.The benchmark varies graph number and size, alignment ambiguity, dependency depth, heterogeneity, and irrelevant evidence.Source: §1 · p. 2
  • Its evaluation schema measures Perception, Alignment, Composition, and Reasoning, including progressive evaluation with verified outputs from preceding capabilities.This allows direct assessment of capabilities and resulting performance recovery.Source: §1 · p. 2
  • Across 15 LVLMs, multi-view graph reasoning remains challenging; diagnostics identify cross-view edge alignment and relation-level composition as weaknesses, with temporal reasoning and increasing view counts exposing further boundaries.Explicit structural evidence substantially improves several partial-view tasks, but temporal tasks remain challenging even with prepared structures.Source: §1 · p. 2
  • The benchmark combines graph-theoretic challenges and capability diagnostics with gold intermediate representations and programmatic checks of answer correctness and multi-view dependence.Its diagnostic schema is used to identify bottlenecks across 15 LVLMs.Source: §1 · pp. 2–3

2 RELATED WORK

Prior visual graph and multi-image benchmarks cover graph understanding, visual variation, and reasoning across images, but do not systematically address graph-theoretic problems requiring structure assembled across partial or temporal views. MVGRAPH targets these graph-specific demands through end-to-end challenges and stage-oriented diagnostics.

2 RELATED WORK

  • Visual graph benchmarks address graph-theoretic problems, perception, robustness, hallucination, isomorphism, and graph-edit tasks, but not systematic reasoning from complementary partial or ordered temporal views.Examples include VisionGraph (Li et al., 2024), VGCURE (Zhu et al., 2025), and GraphVerse (Sun et al., 2026).Source: §2 · p. 3
  • Multi-image benchmarks examine relations, temporal reasoning, multi-hop inference, and distributed evidence, but do not target recovering local graph topology and composing task-relevant structures.Examples include MIRB (Zhao et al., 2024), MUIRBENCH (Wang et al., 2025a), and VCBENCH (Wang et al., 2025b).Source: §2 · p. 3
  • MVGRAPH addresses this gap with graph-theoretic challenges and diagnostics of perception, alignment, composition, and reasoning when no individual view suffices.Its scope includes recurring or changing graph elements across views.Source: §2 · p. 3

3 MVGRAPH: BENCHMARK DESIGN AND CONSTRUCTION

MVGRAPH combines end-to-end graph-theoretic challenges with stage-oriented diagnostics in partial and temporal graph-view settings. Its task suite, instance construction, and validation are designed to test evidence assembly across interrelated views.

3 MVGRAPH: BENCHMARK DESIGN AND CONSTRUCTION

  • The benchmark pairs end-to-end graph-theoretic challenges with diagnostics of Perception, Alignment, Composition, and Reasoning in partial and temporal graph views.Partial views expose different portions of an underlying graph; temporal views depict successive states that must be interpreted in order rather than merged indiscriminately.Source: §3 · p. 3, Figure 2 · p. 4

3.1 TASK DESIGN

  • Eight graph-theoretic tasks cover topological sorting, maximum flow, bipartite matching, and Hamiltonian path across partial-view and temporal problem settings.Temporal tasks account for structural evolution, including changes to persistent nodes or matches, successive maximum-flow values, and time-respecting paths; they cannot be reduced to an indiscriminate union of observed edges. Diagnostics test perception, alignment, composition, and reasoning, including structure-prepared reasoning tasks.Source: §3.1 · p. 4

3.2 INSTANCE CONSTRUCTION

  • Instances use procedurally generated graphs and SmallPedia-derived topologies, with independently laid-out views and consistent entity identifiers across views.Question answers are computed from underlying graph records; multiple valid solutions are assessed with task-specific verifiers rather than exact match to one reference.Source: §3.2 · pp. 4–5

3.3 VALIDATION AND DATASET STATISTICS

  • Validation checks task-specific structural prerequisites, reference-answer consistency, valid solutions against task constraints, evidence necessity across required views, and whether rendered images retain intended graph elements with legible annotations.MVGRAPH comprises 37 evaluation tasks and 72,000 task-instance records, each involving 2–8 interrelated visual graph views.Source: §3.3 · p. 5

4 EXPERIMENTAL SETUP

The experimental setup evaluates LVLMs on end-to-end graph-theoretic tasks and stage-oriented diagnostics using visual graph inputs or prepared textual structures. It uses exact-match-based metrics, with additional node and edge F1 for perception.

4 EXPERIMENTAL SETUP

  • Fifteen LVLMs are evaluated on eight end-to-end graph-theoretic tasks with thinking and no-thinking modes; seven thinking models take part in stage-oriented diagnostics.The evaluated models include locally deployed and API-accessed systems.Source: §4 · p. 5
  • End-to-end tasks and perception, alignment, and composition diagnostics use visual graph inputs, while reasoning diagnostics provide task-prepared textual structures and composition evidence.All evaluations are zero-shot.Source: §4 · p. 5
  • Perception is scored with exact-match accuracy and node and edge F1; other tasks use exact-match-based accuracy, with programmatic verifiers for tasks allowing multiple valid solutions.Set-valued answers are order-insensitive, while paths and temporal outputs must preserve order.Source: §4 · pp. 5–6

5 RESULTS AND ANALYSIS

Across end-to-end and diagnostic evaluations, current LVLMs struggle with multi-view graph reasoning, especially aligning edges and composing relations across views. Temporal constraints and growing view counts expose further difficulty.

5.1 END-TO-END GRAPH-THEORETIC PERFORMANCE

  • End-to-end performance remains far from saturated: GLM-5.3-Flash leads on average, while results vary across models and partial versus temporal graph settings.Strong Bipartite Matching results do not carry over to Stable Bipartite Matching, and Stable Topological Sorting remains difficult; Maximum-flow Change warrants caution because it asks for a transition rather than a numerical flow value.Source: §5.1 · p. 6
  • Thinking improves every model, with Qwen3.8-Flash rising from 2.6% to 50.4%, but gains vary substantially across models.Without thinking, accuracies cluster between 2.6% and 6.4%.Source: §5.1 · p. 6

5.2 DIAGNOSING THE FOUR CAPABILITIES

  • In thinking mode, no evaluated model exceeds 47% exact match at reconstructing multiple views, and node F1 consistently exceeds edge F1.Seven representative models were evaluated with thinking mode across diagnostics; the F1-to-exact-match gap indicates partial structure recovery without complete view reconstruction.Source: §5.2 · p. 7
  • Node alignment is consistently more accurate than edge alignment, and even the strongest model stays below 60% on view-specific edges.This gap persists despite consistent entity identifiers across views.Source: §5.2 · p. 7, Table 3 · p. 7
  • Models identify relevant views more reliably than they compose relations: Union Edge Count is less accurate than Union Node Count for every model.The strongest models remain below 75% on Union Edge Count; Temporal Path Composition is also markedly harder than Persistent Path.Source: §5.2 · pp. 7–8, Table 4 · p. 7
  • With prepared textual structures, several models solve partial-view challenges, but Stable Topological Sorting and Stable Bipartite Matching remain difficult.DeepSeek-Flash solves all such challenges in this condition despite performing substantially worse on image-based counterparts.Source: §5.2 · p. 8, Table 5 · p. 8

5.3 SCALING WITH THE NUMBER OF VIEWS.

  • As view counts grow, perception exact match generally declines, while composition degrades most for several locally deployed models.API-accessed models remain comparatively stable in composition, and aggregate alignment changes less consistently; Figure 6 defines Full, Single View, and Leave-One-Out conditions.Source: §5.3 · pp. 8–9, Figure 6 · p. 9

5.4 BENCHMARK VALIDATION

  • Programmatic checks verify generated answers against task constraints, while paired view ablations show Full outperforming Leave-One-Out and Single View.For the strongest model, omitting a view nearly halves accuracy; each instance uses the same selected view for the paired reduced-view conditions.Source: §5.4 · p. 9

6 CONCLUSION

MVGRAPH evaluates LVLM reasoning over evidence distributed across interrelated visual graph views. Its findings point to relation-level alignment, evidence composition, and temporal reasoning as important improvement directions.

6 CONCLUSION

  • MVGRAPH evaluates structural evidence distributed across multiple interrelated visual graph views.Source: §6 · p. 9
  • Current LVLMs struggle to perceive graph structure, align edge relations, and compose evidence across views.Source: §6 · p. 9
  • Temporal reasoning remains difficult, and composition performance declines for several models as view counts grow.Source: §6 · p. 9

AI USE STATEMENT.

The authors report using ChatGPT for language polishing and manuscript clarity, while retaining responsibility for the final content.

AI USE STATEMENT.

A DETAILS OF DATASET CONSTRUCTION

The appendix outlines MVGRAPH construction and validation, illustrates task examples, and describes diagnostic task construction.

A DETAILS OF DATASET CONSTRUCTION

A.1 CONSTRUCTION PIPELINE

Instances combine ordered graph images into partial-view or temporal problems, with task-specific construction and output requirements. Graph structure and cross-view identity are represented explicitly.

A.1 CONSTRUCTION PIPELINE

  • Each instance uses 2–8 ordered images of graph views; the eight end-to-end tasks use two to four views, while MFC uses three or four ordered temporal snapshots.The order is retained for temporal questions.Source: §A.1 · p. 13
  • Each image renders a graph with node and edge sets, and the same node identifier marks an entity across views despite independently chosen positions.Models receive images for perception, alignment, and composition; reasoning diagnostics instead receive task-prepared textual structure or composition evidence.Source: §A.1 · p. 13
  • Tables 7 and 8 present examples of ten Alignment tasks and eight Composition tasks; for tasks with multiple valid solutions, each shows one valid answer, and long structured answers are abbreviated for readability.Source: Table 7 · p. 14, Table 8 · p. 14

A.2 GRAPH SOURCES AND VIEW GENERATION

The pipeline generates task-conditioned partial or temporal graph views, renders them as images, and derives questions and checked answers from the underlying structures. Construction checks enforce task-specific dependencies and solution validity.

A.2 GRAPH SOURCES AND VIEW GENERATION

  • Synthetic task generators tailor structures to each problem, including flow networks, bipartite matchings, Hamiltonian paths, and topological orders.Examples include Hall-deficient matching graphs and temporal snapshots whose answers minimize changes or reordering across time.Source: §A.2 · pp. 14, 16
  • Task-conditioned generators create partial views by distributing complementary structures across views, or temporal views by applying controlled changes to successive snapshots.Candidates are filtered with exact algorithms and task-specific constraints; graph-theoretic partial-view problems are validated before edge distribution.Source: §A.2 · pp. 15–16
  • SmallPedia contributes anonymized local topologies, with original images, entity names, and semantic question–answer pairs excluded.Static structures are partitioned into overlapping subgraphs; temporal structures retain the order of timestamped facts.Source: §A.2 · p. 16

A.3 GRAPH REPRESENTATION AND RENDERING

  • Rendered views use neutral node and relation labels, and each image contains 7–20 nodes with layouts computed independently from local graph structures.Maximum-flow edges display positive capacities; layouts failing applicable readability checks are regenerated.Source: §A.3 · p. 17

A.4 QUESTION AND ANSWER GENERATION

  • Task templates derive answers from graph data, using intersections and differences for alignment and task-specific structures or exact algorithms for composition and reasoning.For structure-prepared reasoning, the input makes task-relevant structures explicit; temporal snapshots remain ordered.Source: §A.4 · p. 17
  • Verifiers accept any feasible or optimal solution when a problem admits multiple correct outputs, rather than requiring an exact match to one reference.Checks include node coverage and precedence for topological orders, and validity and maximum cardinality for matchings.Source: §A.4 · p. 17

A.5 EVIDENCE NECESSITY AND VALIDATION

  • Cross-view dependence is checked by removing views and recomputing answers where applicable, with task-specific checks for dependencies that a universal leave-one-out test misses.For example, construction requires independent ordering constraints across views for TS and contributions from every view to MF values.Source: §A.5 · pp. 17–18

A.6 DATASET ORGANIZATION AND SCALE

Dataset records retain rendered views, questions, answers, and structural metadata, while inference prompts specify the graph context and task-specific response format. Models receive images for end-to-end, perception, alignment, and composition tasks, but prepared graph facts for reasoning diagnostics.

A.6 DATASET ORGANIZATION AND SCALE

  • Each record stores rendered views, a question and gold answer, per-view graph structures, and instance-level metadata; models do not receive the underlying graph JSON in image-based evaluation.Structure-prepared reasoning instead supplies textualized structural evidence.Source: §A.6 · p. 19

B INFERENCE PROMPTS AND INSTRUCTIONS

  • Inference inputs combine shared stage instructions with sample-specific graph context, a task question, and an output requirement.Bracketed placeholders are instantiated per sample rather than shown literally.Source: B INFERENCE PROMPTS AND INSTRUCTIONS · p. 20

B.1 END-TO-END GRAPH-THEORETIC REASONING

  • End-to-end prompts ask models to solve graph-theoretic tasks from ordered graph images, including maximum flow, matching, and Hamiltonian paths.The prompts specify the task’s requested output, such as a JSON integer, list, or object.Source: §B.1 · p. 20
  • Temporal prompts require outputs across snapshots, such as selecting the largest flow increase or minimizing changes between consecutive matchings.Other temporal prompts ask for time-respecting Hamiltonian paths with nondecreasing image indices and all time steps used.Source: §B.1 · p. 20

B.2 PERCEPTION

  • Perception prompts ask models to reconstruct each image’s nodes and edge triples, preserving labels and including isolated nodes.The undirected variant emits each edge once; the directed variant preserves arrow direction.Source: §B.2 · p. 21

B.3 ALIGNMENT AND COMPOSITION

  • Alignment and composition prompts use partial-view or temporal preambles and request task-specific outputs for graph elements or composed evidence.The required JSON schema varies by task and is not uniformly a node list.Source: §B.3 · p. 21

B.4 REASONING

  • Reasoning prompts supply graph facts instead of images; partial-view tasks receive merged graphs, while temporal tasks retain ordered snapshots.The causal-edge task additionally receives composition evidence.Source: §B.4 · pp. 21–22

C.1 MAIN RESULTS

End-to-end results show low accuracy without thinking, substantial but uneven gains with thinking, and large differences across graph-theoretic tasks. Major challenges remain, while task-construction differences limit interpretation of static–temporal score gaps.

C.1 MAIN RESULTS

  • 1.9%–6.4% average accuracy across 14 models without thinking, with no correct answers on TS or STS and MFC as the main exception.MFC selects a consecutive snapshot pair rather than requiring models to output or justify flow values, so its scores do not necessarily demonstrate reliable flow computation.Source: §C.1 · p. 22
  • Every model evaluated in both settings improves average accuracy with thinking, including Qwen3.8-Flash from 2.6% to 50.4% and Gemma-4-12B-it from 5.6% to 20.5%.The magnitude varies considerably; comparisons are descriptive rather than size-controlled, and GLM-5.3-Flash lacks a corresponding no-thinking result.Source: §C.1 · p. 22
  • The two leading models score 95.0–97.0% on BM but only 8.0–16.0% on SBM, while retaining comparatively strong performance on THP.Static–temporal task pairs differ in construction, output requirements, or both, so these gaps are not an isolated measure of temporal reasoning.Source: §C.1 · pp. 22–23
  • Additional test-time reasoning yields large gains for some models and tasks, but major graph-theoretic challenges remain and motivate stage-oriented diagnostics.The reported scores also vary strongly by problem, including higher TS than STS scores for the two leading models.Source: §C.1 · pp. 22–23
Loading 2610.12961v1…