LLMTM: Benchmarking and Optimizing LLMs for Temporal Motif Analysis in Dynamic Graphs¶

🕒 Published (v1): 2025-12-24 18:10 UTC · Source: Arxiv · Venue: AAAI 2026 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

LLMTM is the first benchmark to systematically evaluate LLMs on temporal motif tasks in dynamic graphs, covering six tasks across nine motif types with nine models. LLMs perform well on simple single-motif classification but collapse on complex multi-motif identification due to cognitive load. A tool-augmented ReAct agent achieves near-perfect accuracy at 3× token cost, which a lightweight structure-aware dispatcher then mitigates by routing queries based on predicted difficulty.

Problem¶

Temporal motifs—structured, time-ordered interaction patterns in dynamic graphs—are foundational for fraud detection, link prediction, and graph analytics. Traditional detection methods are motif-specific and cannot generalize; deep learning methods require supervised training and underperform. Whether LLMs can solve temporal motif problems in a unified, zero/few-shot manner is entirely unexplored, and no benchmark existed to measure it.

Method¶

Benchmark (LLMTM): Generates synthetic dynamic graphs using the Erdős–Rényi model with a quadruplet edge representation (u, v, t, op) capturing both edge additions and deletions. Six tasks at two complexity levels: (1) single-motif recognition (Motif Classification, Motif Detection, Motif Construction) and (2) multi-motif identification (Multi-Motif Detection, Motif Occurrence Prediction, Multi-Motif Count) across nine motif types (3-star, triangle, 4-path, 4-cycle, 4-chordalcycle, 4-tailedtriangle, 4-clique, bitriangle, butterfly). Balanced datasets ensure ~50% positive/negative instance rates.

Prompting experiments: Evaluates zero-shot, one-shot, zero-shot+CoT, and one-shot+CoT strategies across nine LLMs.

Tool-augmented agent: ReAct-style four-stage workflow (Task Planning → Tool Selection → Tool Calling → Response Generation) equipped with five algorithmic tools. Core motif detection uses two steps: VF2-based subgraph isomorphism (GraphMatcher) for structural/connectivity constraints, then temporal/duration constraint verification.

Structure-aware dispatcher: An XGBoost classifier trained on 1,500 instances using five graph-structural and cognitive-load features—number of edges (structural scale), cyclomatic complexity and node degree proportions (structural complexity), and edge locality score (LLM cognitive load, measuring sequential dispersion of edges). Routes easy queries to direct LLM prompting and hard queries to the full agent.

Key Contributions¶

First benchmark (LLMTM) for evaluating LLMs on temporal motif problems, with six tasks, nine motif types, and balanced synthetic datasets.
Systematic empirical study across nine LLMs and four prompting strategies yielding seven behavioral observations.
A tool-augmented LLM agent (ReAct + five algorithmic tools) achieving ~98–100% accuracy on all six tasks.
A structure-aware dispatcher (XGBoost + five novel difficulty-prediction features) that routes queries to balance accuracy vs. token cost, with demonstrated generalization to unseen motif types.

Results¶

Motif Classification (Level 1): o3 reaches 100% on 3-star and triangle; DeepSeek-R1 achieves 100% on 3-star, 4-path, 4-cycle, 4-tailedtriangle; most strong models score ≥90%.
Motif Detection (Level 1): Accuracy drops sharply—e.g., DeepSeek-R1 scores 90%/95% on 3-star/triangle but drops to 55–85% on complex motifs; DeepSeek-Qwen-7B hits 0% on butterfly.
Level 2 tasks: Severe collapse—best single-model scores are o3 at 39.64% (Multi-Motif Detection), 25.92% (Motif Occurrence Prediction), and only 1.94% (Multi-Motif Count).
Tool-augmented agent vs. GPT-4o-mini: Agent achieves 98–100% on Level 2 tasks vs. GPT-4o-mini's 8–19%, at ~3–4× token cost (9,190–12,299 vs. ~2,700–3,000 avg. tokens).
Structure-aware dispatcher: Achieves second-best accuracy (e.g., 86.5% on 3-star vs. agent's 100%) at substantially lower token cost than the pure agent; generalizes to held-out motif types (4-tailedtriangle: 84.0% acc, triangle: 79.8% acc).
Best standalone LLM: DeepSeek-R1 is the strongest across tasks; o3 leads on Level 2 multi-motif detection.

Limitations¶

Benchmark uses only synthetic (Erdős–Rényi) graphs; real-world ego-graph experiments are limited to an appendix, leaving generalization to organic temporal network distributions unclear.
Temporal motif definition requires only edge-add events in the motif sequence; the richer quadruplet representation (add/delete) is used for the graph context but motifs themselves remain edge-addition patterns.
Structure-aware dispatcher is trained and evaluated specifically on the Motif Detection task; its applicability to the other five tasks is not demonstrated.
Agent cost analysis is limited to token count; wall-clock latency and API-call overhead of multi-step ReAct cycles are not quantified.
Coverage of nine motif types may miss real-world domain-specific patterns not captured by common small subgraph families.

Relevance to Agentic AI / LLM Agents¶

This paper directly probes LLM agents on a domain requiring multi-step, constraint-satisfying structural reasoning—a close analogue to real-world agentic tasks involving relational data. The "capability collapse" on multi-motif identification illuminates a general bottleneck in current LLMs: compounding cognitive load across interdependent reasoning chains, not just knowledge gaps. The structure-aware dispatcher is a concrete instantiation of adaptive tool-routing, a pattern increasingly central to efficient agentic systems where calling powerful tools universally is too expensive. The finding that LLMs self-diagnose their inability and request algorithmic tools (metacognitive awareness) is particularly relevant for agentic architectures that rely on self-directed tool invocation.