2026· Annual Meeting of the Association for Computational Linguistics· pp. 10442-10462· 1 citation· 50 references
Computer Science
TL;DR
This work proposes MuSe, a novel multi-stage graph reasoning framework based on VLMs, where instead of processing entire graphs at once, MuSe incrementally samples and visualizes task-relevant subgraphs, enabling progressive reasoning.
Abstract
Graph-related tasks are traditionally addressed with Graph Neural Networks (GNNs) or graph transformers, but their task-specific training limits generalization. Large Language Models (LLMs) offer stronger generalization, yet encoding graphs as one-dimensional text struggles to capture multi-hop dependencies and two-dimensional topology. Vision-Language Models (VLMs) provide an alternative by visualizing graphs, but rendering large graphs in a single image causes clutter, occlusion, and distraction, hindering reasoning. We propose MuSe, a novel multi-stage graph reasoning framework based on VLMs. Instead of processing entire graphs at once, MuSe incrementally samples and visualizes task-relevant subgraphs, enabling progressive reasoning. The framework employs a two-stage training paradigm: supervised fine-tuning to acquire local sampling and reasoning skills, followed by reinforcement learning with GRPO to refine the sampling strategy and control dialog length. To support evaluation, we introduce LGVLQA, a new multimodal dataset with larger and more complex graph structures, addressing the scalability limitations of existing benchmarks. Experiments show that MuSe consistently out-performs leading LLM and VLM baselines, demonstrating improved structural understanding and reasoning ability. Our code and data are available at this url.
This work introduces Scene Graph Thinking (SaGe), a novel paradigm that enables fine-grained and structured visual reasoning through explicit scene-graph representations and proposes node-as-proxy graph rewards to consolidate efficient graph exploration.
Zhiwei Yang, Yuanchen Wu, Nan Zhang et al.· 1 citation
GraphVerse is introduced, a unified benchmark that jointly evaluates perception, visual reasoning, and text-based graph reasoning in MLLMs under both single-image and paired-image settings and proposes VGR-Score, a process-sensitive metric that evaluates reasoning quality beyond final-answer accuracy.
Yuanfu Sun, Yuanhang Ren, Kang Li et al.· 0 citations
A unified framework that embeds unstructured text into structured knowledge graphs, creating a heterogeneous network for flexible evidence retrieval, outperforming SOTA baselines in answer accuracy and reasoning fidelity while maintaining extremely low token costs and near real-time inference is proposed.
Vision-language models (VLMs) provide a unified representation space for textual and visual information, yet their potential as general-purpose backbones for graph-structured data remains largely unexplored. In practice, attributed graphs exhibit substantial modality heterogeneity: some graphs contain only textual node attributes, others only visual attributes, while still others provide both. Existing graph learning approaches are typically designed for fixed modality schemas, requiring separate models for different settings and limiting scalability and cross-graph generalization. To bridge this gap, we present OMG-VLM (One Model, Many Graphs with Vision-Language Models), a unified framework for learning over attributed graphs across heterogeneous modality schemas. OMG-VLM leverages a pretrained VLM as a shared backbone and introduces structure-aware graph adapters that integrate neighborhood information while remaining compatible with the VLM's native embedding space. This design enables effective learning over text-attributed, image-attributed, and multi-attributed graphs within a single model. Extensive experiments across diverse domains show that OMG-VLM consistently outperforms state-of-the-art GNN- and LLM-based baselines on attributed graph learning tasks such as node classification and link prediction, while exhibiting strong generalization to unseen graphs and varying modality schemas. The source code is available at https://github.com/Jo-eyang/OMG-VLM.
Jiayi Yang, Yifang Chen, Yuanfu Sun et al.· 0 citations
This work presents the first systematic survey of graph-assisted LLMs from the perspective of how graph structures mitigate LLMs’ limitations, and introduces a taxonomy spanning Graph-Assisted Knowledge Augmentation, Graph-Assisted Reasoning and Planning, and Graph-Assisted LLM Collaboration.
Haitong Luo, Fali Wang, Weiyao Zhang et al.· Annual Meeting of the Associ...· 2 citations
G-ReAct is a reasoning framework for deep search that organizes reasoning as state evolution over a fixed-topology query graph, transforming exploratory search driven by textual history into graph-guided reasoning under explicit constraints.
Shaoxiong Yang, Mengyuan Zhang, Shaojun Lin et al.· 0 citations