DynamicGTR: Leveraging Graph Topology Representation Preferences to Boost VLM Capabilities on Graph QAs

AI summary

Overview

Research area: Vision-Language Models (VLMs) applied to graph-structured question answering (zero-shot graph QA), sitting at the intersection of computer vision, multimodal reasoning, and graph machine learning (arXiv category: Computer Vision).

Technical level: Intermediate. Readers should be comfortable with VLMs, prompt-based QA, graph algorithms, and basic classification-model training.

Scope: The paper proposes DynamicGTR, a framework that picks a different graph topology representation (GTR) for each graph question at inference time, balancing answer accuracy against response length, and shows it works on seven synthetic graph algorithm tasks plus six real-world link prediction and node classification datasets.

What This Paper Is About

VLMs can answer questions about graphs without any task-specific fine-tuning, but existing methods always show the graph to the model in one fixed format — either a fixed-style picture or a fixed text template such as an edge set or adjacency matrix. This "one-size-fits-all" choice ignores the fact that different models and different question types work better with different formats, producing wrong answers or needlessly long responses. The paper's goal is to learn which representation each question prefers and route the question to it automatically.

Key Contributions

1. A systematic investigation of existing fixed GTRs. The authors categorize current graph topology representations into Embedding, Textual, and Visual types, and summarize each one's characteristics, whether it needs an external encoder, and whether it requires extra training (Table 1).
2. The DynamicGTR framework. A method that adaptively assigns visual or language-based GTRs based on query-specific requirements and user preferences for accuracy versus brevity, without accessing VLM architecture or parameters, so it works with closed-source models.
3. The GTRP dataset as a side product. A GTR Preference dataset built from fixed probe data that maps each question to the GTRs with the highest Graph Response Efficiency, serving as a reference for revealing the mapping from task types to preferred GTRs.
4. Empirical validation. Results showing effectiveness on both synthetic graph algorithm QAs and real-world applications, plus generalizability across tasks and models.

Main Findings

• Graph Response Efficiency (GRE) with a tunable knob. GRE for a question q and representation r is defined as Acc_r(q) + α × Eff_r(q), where the accuracy term is log(1 + 100 × correctness_r(q)) with correctness in {0, 1}, and the efficiency term is −log(tok_r(q)), the negative log of average response token consumption. The hyperparameter α lets users shift weight from accuracy (α = 0) to brevity (larger α).

• Question types prefer different GTRs. Analysis of the GTRP dataset splits the seven tasks into three families: Perceptual-Intensive Tasks (Connectivity, Cycle Detection, Bipartite Graph Matching) favor visual GTRs; Edge-Weighted Tasks (Shortest Path, Maximum Flow) favor textual GTRs; and Ordered Decomposition Tasks (Hamilton Path, Topological Sorting) also favor textual GTRs.

• GTR preferences are model-specific. In Table 2, GPT-4o's top GTR for Connectivity is V_fdp at 92.3%, while Gemini-2.5 Pro's top choice is V_neato at 88.8%. For Shortest Path, GPT-4o's top-1 is T_set at 19.5% and Gemini-2.5 Pro's is T_list at 48.6%, showing the same task can prefer different representations in different models.

• In-domain gains in both accuracy and tokens (GPT-4o). DynamicGTR reaches 96.1% accuracy at 38.8 tokens on Connectivity, versus the strongest baseline GraphDPR at 94.3% accuracy and 412.2 tokens. On Cycle Detection it reaches 89.3% at 75.9 tokens versus GraphDPR's 68.7% at 626.4 tokens.

• Stronger results with Gemini-2.5 Pro. DynamicGTR hits 100% accuracy on Connectivity (12.9 tokens), Maximum Flow (1004.8 tokens), Bipartite Graph Matching (776.0 tokens), and Hamilton Path (254.6 tokens), and 99.3% on Cycle Detection (16.7 tokens).

• Out-of-domain transfer without retraining. On six real-world datasets spanning link prediction and node classification, GPT-4o + DynamicGTR improves ca-GrQC to 76.5% (143.2 tokens), ca-HepTh to 86.3% (183.4 tokens), ogbl-ppa to 54.4% (206.3 tokens), PolBlog to 71.9% (153.0 tokens), Cora to 64.5% (99.2 tokens), and ogbn-product to 40.1% (156.1 tokens), beating the base model, CoT, and GITA on both metrics. Gemini-2.5 Pro + DynamicGTR reaches 77.9%, 89.7%, 64.8%, 76.4%, 68.6%, and 51.9% respectively.

• No single GTR dominates (ablation). In Table 5, the Router achieves the highest average GRE of 1.67, compared to 1.16 (V_dot), 1.20 (V_neato), 1.13 (V_circo), 0.88 (V_fdp), 1.21 (V_sfdp), 1.05 (T_set), 1.07 (T_list), and 0.56 (T_mat).

• Rare choices drive most token savings in ordered decomposition tasks. For Topological Sorting and Hamilton Path, the less prevalent GTRs selected in rare (under 15%) cases contribute a majority (over 88%) of token savings.

• α behaves as designed (GPT-4o). On in-domain tasks, accuracy is 69.6 at α = 0, 69.5 at α = 0.5, and 69.3 at α = 1, while tokens fall from 290.8 to 212.0 to 209.9. Best baseline for comparison: 61.8 accuracy and 319.8 tokens.

• More probe trials help (GPT-4o). Raising k from 1 to 5 to 10 lifts in-domain accuracy from 62.4 to 66.2 to 69.5, and cuts tokens from 286.2 to 232.4 to 212.0.

• Routers transfer across VLMs. When Gemini-2.5 Pro's router is transferred to GPT-4o, average accuracy changes by −0.6 (versus +5.3 over the best non-DynamicGTR baseline) and tokens by −28.3 (versus −99.8 over that baseline).

Methodology in Plain English

1. Build a menu of representations. The authors define a zero-shot GTR pool R_ZS = {V_dot, V_neato, V_circo, V_fdp, V_sfdp, T_set, T_list, T_mat} — eight representations in total. Five are visual images produced with Graphviz layout algorithms from prior work, and three are text formats: edge set, adjacency list, and adjacency matrix. Selection follows three principles: Model-Agnostic (no reliance on VLM internals, so closed-source models work), Variety, and Effectiveness. Embedding-based GTRs are deliberately excluded because they need embedding spaces that are inaccessible for closed-source models.

2. Measure what works. Using a probe dataset of 7K graph QA pairs across seven algorithms, with graphs sampled from an Erdős–Rényi model (node count N in [3, 30], edge probability in [0.1, 0.7]) and answers verified by guaranteed algorithmic solutions, the authors run the VLM with each candidate representation, average over k trials, and compute GRE. The representation with the highest GRE becomes the question's label, producing the GTR Preference (GTRP) dataset.

3. Train a lightweight router. A DeBERTaV3-base classifier is trained on the GTRP dataset as a multi-label model over the eight GTRs. Training takes about 2.96 hours on one NVIDIA A100 GPU. At inference, the router reads the question and picks the GTR that the VLM Reasoner should use.

4. Evaluate inside and outside the training distribution. In-domain evaluation uses the GVLQA-BASE benchmark on seven algorithmic tasks; out-of-domain evaluation uses link prediction and node classification on graphs far larger than the probes, using n-hop node-surrounding sampled subgraphs per the locality principle. The tested VLMs are GPT-4o and Gemini-2.5 Pro (with LLaVA-OneVision-7B and Qwen3-VL-8B in the appendix), run three times each at temperature τ = 0.7.

Why This Matters

Impact on research. The paper reframes graph QA for VLMs as a representation-selection problem rather than a model-modification problem. Because GTRs act only at the input stage, the method needs no access to model architecture or parameters and therefore applies to black-box, state-of-the-art closed-source VLMs — a contrast with graph-aware VLM approaches (InstructGLM, GraphToken, GraphLLM, Gcoder) that require architectural changes or fine-tuning, and with toolkit-enhanced systems (StructGPT, Graph-Toolformer, GraphDPR) that are limited to rigid question types. The GTRP dataset also provides a reusable reference mapping task types to preferred representations.

Real-world applications (drawn from the paper's evaluations):

• Link prediction in collaboration networks (ca-GrQC, ca-HepTh) and a large-scale protein-protein interaction network (ogbl-ppa, 15K queries).
• Node classification in a politician blog network (PolBlog) and a citation network (Cora).
• Node classification on an extensive e-commerce dataset (ogbn-product, 15K queries).
• Network analysis and knowledge discovery more broadly, which the introduction cites as motivating domains.

Industry relevance. The GRE score makes accuracy-versus-cost trade-offs an explicit deployment decision: a latency- or budget-sensitive product can raise α, while an accuracy-sensitive one can set α to 0. The paper notes that changing user preference only requires updating α and recomputing GTR preferences from previously dumped probe results without further API cost, and that router retraining completes within 3 GPU-hours on one NVIDIA A100.

Future Directions

• Broadening the GTR pool. R_ZS contains eight hand-designed representations; the paper does not report exploring beyond that set, so discovering or generating additional representations is an open question.
• Improving edge-weighted and ordered-decomposition tasks. On these tasks the gains lean toward tokens rather than accuracy — for example 40.8% on Topological Sorting and 36.6% on Maximum Flow with GPT-4o — leaving headroom for accuracy-focused progress.
• Better cross-model routing. Transfer experiments show transferred routers can slightly underperform the native router, reflecting model-specific biases, so unifying preferences across VLMs is unresolved.
• Scaling behavior. Graphs probed had node counts in [3, 30]; although results transfer to much larger real-world graphs through n-hop sampled subgraphs, the paper does not report a systematic study of router behavior as graph size grows further.

Target Audience

Researchers and practitioners working on multimodal reasoning, graph machine learning, and LLM/VLM-based question answering — particularly those who need graph QA on closed-source models and care about controlling inference cost. The paper is also useful to engineers building network analysis, recommendation, bioinformatics, or knowledge-discovery systems who want a practical accuracy-versus-latency knob rather than a new model architecture.

Authors’ abstract

Vision-Language Models (VLMs) have emerged as versatile solutions for zero-shot question answering (QA) across various domains. However, enabling VLMs to effectively comprehend structured graphs and perform accurate, efficient QA remains challenging. Existing approaches typically rely on one single graph topology representation (GTR), such as fixed-style visual images or unified text descriptions. This ``one-size-fits-all'' strategy often neglects model-specific and task-specific preferences, resulting in inaccurate or over-lengthy responses to graph-related queries. To address this, we propose the $\mbox{DynamicGTR}$ framework, which dynamically selects the optimal GTR for each query during inference, thereby enhancing the zero-shot graph QA capabilities of VLMs with a customizable accuracy and brevity trade-off. Extensive experiments show that DynamicGTR not only improves VLM-based graph algorithm QA performance but also successfully transfers the experience trained from synthetic graph algorithm tasks to real-world applications like link prediction and node classification, without any additional training. Additionally, DynamicGTR demonstrates strong transferability across tasks, domains, and models, suggesting its potential as a flexible solution for broad graph scenarios.