Source-linked AI summary
Structurally Speaking: Motif-Oriented Graph Captioning through Bidirectional Graph-Text Translation
Hsiao-Ying Lu, Dongyu Liu, Kwan-Liu Ma
TL;DR
Graph captions should make topology interpretable through compact motifs rather than verbose edge lists, while retaining enough information for graph recovery. The paper introduces Structurally Speaking, a structured prompting protocol for bidirectional graph-text translation, and finds shorter, more motif-consistent captions with comparable recovery. The study is limited by its synthetic dataset, single model, small evaluation set, and approximate quality metrics.
Problem
Graph-captioning methods need to balance graph recoverability with concise, interpretable motif-level abstraction instead of relying on verbose edge enumeration.
Method
Structurally Speaking decomposes graph-caption translation into topology extraction, motif analysis, motif parsing, node assignment, edge construction, and graph recovery stages.
Results
Structurally Speaking produces shorter and more motif-consistent captions while maintaining comparable graph recovery, whereas direct prompting often relies on verbose edge enumeration.
Takeaways & Limitations
Explicit topology-to-motif reasoning guidance can improve the interpretability of LLM-generated graph captions without fine-tuning.
Takeaways & Limitations
The study uses a synthetic dataset, one LLM, and a small human-verified evaluation set, so results may not generalize to larger graphs, other graph families, or other models.
Abstract
from arXiv · showhide
Graph captions should help readers understand graph structure, rather than simply translate adjacency matrices into long textual edge lists. A useful graph caption abstracts connectivity into recognizable motifs, such as hubs, paths, cycles, cliques, and bridges, because these motifs provide compact structural units that are easier to read, compare, and recover. In this paper, we study motif-oriented graph captioning as a bidirectional graph-text translation task, where captions must both preserve enough topology for graph recovery and express the graph through concise motif-level descriptions. We show that direct prompting of GPT-5.1 often produces graph-recoverable captions by enumerating node-to-node connections, but these captions are verbose and can contain inconsistent motif interpretations. To address this gap, we introduce Structurally Speaking, a lightweight structured prompting protocol that guides translation between explicit connectivity and motif-level abstraction. Experiments on a synthetic motif-based dataset show that structured prompting produces shorter and more motif-consistent captions while maintaining comparable graph recovery. These results suggest that explicit topology-to-motif reasoning guidance can make LLM-generated graph captions more interpretable without model fine-tuning.
1 Introduction
The paper frames graph captioning as a bidirectional translation problem requiring both graph recovery and compact motif-level abstraction. Structurally Speaking addresses direct prompting’s verbose, inconsistent captions with structured topology-to-motif reasoning.
- 1 Introduction: Graph captions should abstract adjacency into recognizable motifs, including hubs, paths, cycles, cliques, bridges, and tails.These motifs provide compact structural units for understanding how local connections form larger graph patterns.
- 1 Introduction: Graph-caption quality requires both structural recoverability and motif-level compactness, because edge enumeration can preserve topology without yielding interpretable abstraction.Such captions may be verbose, difficult to read, or inconsistent in their motif interpretations.
- 1 Introduction: Direct prompting often produces graph-recoverable captions, but relies on explicit node-to-node descriptions and sometimes inaccurate or self-contradictory motif interpretations.This indicates a tendency toward edge enumeration rather than compact motif-level inference.
- 1 Introduction: Structurally Speaking guides graph-to-caption translation through neighborhoods and motif analysis, and caption-to-graph translation through motif parsing, node assignment, edge construction, and adjacency recovery.The protocol preserves enough topology for graph recovery while requiring motif inference from raw connectivity.
- 1 Introduction: On a synthetic motif-based dataset, structured prompting reduces verbosity and inconsistent motif inferences while maintaining comparable graph recovery without fine-tuning.The study evaluates this behavior using bidirectional cycle-consistency tests.
2 Related Work
Related work covers graph-to-text generation, topology serialization, graph reasoning, prompting, and graph-query systems. This paper distinguishes itself by studying motif-oriented captions of raw topology rather than primarily semantic graph text or representation formats.
- 2 Related Work: Prior graph-to-text work generates language from meaning representations, knowledge graphs, and scientific graphs, emphasizing fluency, factuality, planning, or grounding.The paper instead focuses on exposing compact structural abstractions from raw topology.
- 2 Related Work: Another research direction optimizes topology serialization, learned graph encodings, and broader graph transformation strategies for language models.These approaches address how graphs are represented for LLMs rather than the paper’s motif-oriented captioning objective.
- 2 Related Work: Related studies also examine graph reasoning, structured interfaces, reasoning generalization, and natural-language-to-graph-query systems.The paper positions motif-oriented raw-topology captioning alongside these broader graph-language directions.
3 Problem Formulation
The paper defines graph captioning as bidirectional translation between adjacency-based graphs and natural-language captions evaluated for recoverability and motif abstraction. It operationalizes motif-oriented captions through structural roles, perturbations, and controlled synthetic examples.
- 3 Problem Formulation: Graph-to-caption translation generates a caption from G = (V, E), while caption-to-graph translation reconstructs a graph ˆG from caption C.A high-quality caption must satisfy graph recoverability and motif abstraction.
- 3 Problem Formulation: Motif-oriented captions identify dominant motifs, describe node roles, and state structural deviations such as missing edges or added chords.The requirements include stars, paths, cycles, cliques, wheels, hubs, rim nodes, bridge nodes, and leaves.
- 3 Problem Formulation: The captioning criteria discourage exhaustive edge enumeration except when specific connections are needed for graph recovery.This makes compact structural description an explicit part of the task definition.
- 3 Problem Formulation: The dataset contains 220 undirected, unweighted graphs with at most 30 nodes, initialized from common motifs and modified with structural perturbations.The graph families include stars, cycles, paths, cliques, and wheels.
- 3 Problem Formulation: Forty representative graphs form a human-verified, free-form caption test set designed for controlled diagnosis rather than benchmark-scale evaluation.The examples cover diverse motif families and perturbation levels while preserving linguistic variation.
4 Direct Prompting Analysis
The direct-prompting analysis finds that GPT-5.1 can preserve connectivity for graph recovery, but often does so through verbose edge enumeration rather than reliable motif abstraction. Figure 1 illustrates this trade-off with a perturbed wheel motif.
- 4 Direct Prompting Analysis: Figure 1 contrasts a human-verified compact wheel-motif caption with a graph-recoverable generated caption that is verbose and sometimes self-contradictory.The example includes a central hub, rim structure, and one additional rim connection.
- 4 Direct Prompting Analysis: Direct prompting often preserves enough connectivity for graph recovery but exhibits edge enumeration, low compactness, and inconsistent or inaccurate motif interpretation.These failure modes motivate separating connectivity extraction from motif abstraction before final caption generation.
- 4 Direct Prompting Analysis: The analysis concludes that successful graph recovery alone does not establish motif-level abstraction, because all edges can be encoded through enumeration.This distinction supports a prompting strategy that explicitly separates topology extraction from structural interpretation.
5 Structurally Speaking
Structurally Speaking introduces a structured reasoning protocol that inserts explicit connectivity and motif analysis between graph inputs and captions or reconstructed graphs. Its templates decompose both translation directions into intermediate steps for more compact, motif-oriented outputs.
- Protocol: Structurally Speaking inserts an intermediate representation between adjacency matrices and captions, using neighbor lists for local connectivity and motif analysis for higher-level structure.The protocol decomposes translation rather than directly generating captions or graphs in one step.
- Graph-to-caption: Graph-to-caption translation converts adjacency information into neighbor lists, analyzes motifs, and then generates a final caption.
- Caption-to-graph: Caption-to-graph translation parses motifs, assigns node indices and layouts, creates edges, builds neighbor lists, and converts them into an adjacency matrix.
- Prompting settings: The protocol compares direct prompting with zero-shot and few-shot structured prompting, with zero-shot testing the scaffold without labeled examples.
6 Evaluation
The evaluation tests bidirectional graph-caption translation with cycle-consistency measures for graph recovery, caption reconstruction, and compactness. Structured prompting improves caption-focused measures while preserving strong recovery, whereas direct prompting reaches perfect recovery through verbose edge enumeration.
- Evaluation design: Graph-Caption-Graph measures whether generated captions preserve topology for graph recovery, while Caption-Graph-Caption evaluates motif-caption accuracy and compactness after graph translation.The latter uses ROUGE-1 together with caption length and qualitative inspection.
- Evaluation design: The evaluation compares direct, zero-shot structured, and few-shot structured prompting using GPT-5.1 across the two cycle-consistency settings.
- Results: Direct prompting achieves perfect edge precision, recall, and F1 for graph recovery but produces the longest captions and lowest ROUGE-1 precision.This pattern indicates that recovery is driven mainly by edge enumeration rather than motif abstraction.
- Results: Zero-shot structured prompting greatly reduces caption length and improves ROUGE-1 precision and recall over direct prompting without labeled examples.Its small drop in graph-recovery recall indicates that compact captions may omit some edge details.
- Results: Few-shot structured prompting maintains near-perfect graph recovery while producing the shortest captions and highest ROUGE-1 precision.Qualitative examples further associate the shorter outputs with better motif abstraction rather than merely shorter text.
7 Conclusion
The paper uses bidirectional graph-caption translation to diagnose whether LLMs infer motif-level structure from raw topology. Its results indicate that structured prompting improves motif-oriented abstraction while maintaining comparable graph recovery.
- Structurally Speaking guides topology-to-motif reasoning, eliciting more accurate and consistent motif-level inference while maintaining comparable graph recovery.
- The diagnostic evaluates both graph recovery and motif-oriented caption compactness through bidirectional graph-caption translation.
- Direct prompting can preserve topology through verbose edge enumeration without necessarily producing interpretable motif-level abstraction.
Limitations
The study is a controlled diagnostic rather than a comprehensive benchmark, using a synthetic motif-based dataset, one LLM, and a small human-verified evaluation set. Its quality measures are approximate and may not generalize broadly.
- The experiments use a synthetic motif-based dataset and a single LLM, so results may not generalize to all graph families, larger graphs, or other models.
- The captioned evaluation set is small because motif-oriented captions require human verification.
- ROUGE-1 and caption length are only approximate signals of motif-oriented caption quality and are interpreted with recovery metrics and qualitative examples.
Ethical Considerations
The study identifies a general risk that fluent graph captions may omit, distort, or overspecify structural information, so captions should be checked against the underlying graph. Qualitative examples also indicate that structured prompting produces shorter, more motif-focused descriptions than direct prompting.
- Ethical Considerations: Generated graph captions may appear fluent while omitting, distorting, or overspecifying structural information, so practical use requires verification against the underlying graph.The study evaluates this risk through graph recovery, caption reconstruction, caption length, and qualitative inspection rather than fluency alone.
- Ethical Considerations: Figure 3 compares human-verified captions with direct, zero-shot structured, and few-shot structured prompting on perturbed motif graphs.The figure caption presents the prompting settings and the comparison context.
- Ethical Considerations: Structured prompting reduces verbosity and self-contradictory descriptions while better focusing captions on motif-oriented graph patterns.These qualitative examples support the paper’s evaluation of interpretability beyond graph recoverability alone.
D Additional Quantitative Analyses
Additional analyses compare prompting schemes across clean and perturbed graphs and across motif families. They show that perturbations make the task harder, while wheel patterns are especially challenging despite preserving the overall advantage of structured prompting.
- D Additional Quantitative Analyses: All prompting schemes perform better on clean motif graphs than on perturbed graphs, which introduce structural variation beyond base motif patterns.The test set contains only two clean examples per motif family, so aggregate Table 2 results more closely reflect perturbed graphs.
- D Additional Quantitative Analyses: Wheel patterns are among the most challenging motif families across prompting schemes because they combine a central hub with a rim structure.This composition requires recognizing both star-like and cycle-like organization.
- D Additional Quantitative Analyses: For wheel patterns, structured prompting improves caption compactness and motif-oriented reconstruction while maintaining comparable graph recovery.The wheel-specific results are reported as broadly consistent with the overall trends in Table 2.