Research map / Large language models / Retrieval and knowledge
Beyond Graphs: Can Large Language Models Comprehend Hypergraphs?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces LLM4Hypergraph, a 21,500-problem benchmark of low-order, high-order, and isomorphism hypergraph tasks, and evaluates six LLMs under multiple prompting styles and seven hypergraph text encodings, proposing Hyper-BAG and Hyper-COT prompts.
Problem
Whether LLMs can comprehend hypergraphs, whose high-order (beyond-pairwise) correlations are not covered by existing graph benchmarks such as NLGraph and GraphQA.
Approach
A hypergraph-specific benchmark spanning low-order, high-order, and isomorphism tasks, paired with hypergraph text encodings (low-order and high-order languages) and prompt variants (Hyper-BAG, Hyper-COT) that are tested without any weight updates.
Key results
- Hyper-COT v3 improves structure classification by about 4% on average across seven encodings and up to 9% on N-Pair and N-Set encodings.
- Isomorphism recognition stays near 50% for binary classification under zero-shot prompting, showing current textualizations are inadequate.
- Few-shot and CoT prompting with high-order languages raise structure classification accuracy to over 60%, from about 30% zero-shot.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use few-shot examples with the N-Set high-order structure language instead of zero-shot N-Set | Qwen-Long · LLM4Hypergraph structure classification | accuracy: 41.2% -> 82.7% | Helped |
| Replace Naive COT with Hyper-COT v3 (ablation) | Qwen-Long · LLM4Hypergraph structure classification | accuracy: 24.3% -> 33.6%; 30.1% -> 36.7%; 27.0% -> 27.9%; 27.0% -> 36.0%; 25.2% -> 20.9%; 23.0% -> 29.2%; 32.3% -> 32.4% | Mixed |
| Add Hyper-BAG prompting (ablation) | Qwen-Long · Vertex Set Connection | accuracy: 83.4% -> 86.2% | Helped |
| Add Hyper-BAG prompting (ablation) | Qwen-Long · Vertex-Set-in-Hyperedge Check | accuracy: 87.2% -> 89.8% | Helped |
| Add Hyper-BAG prompting (ablation) | Qwen-Long · Vertex Connection | accuracy: 94.0% -> 93.6% | Hurt |
| Increase Hyper-COT example solutions from 0-shot to 3-shot (ablation) | Qwen-Long · Vertex Set Connection | accuracy: 84.4% -> 90.4% | Helped |
| Increase Hyper-COT example solutions from 0-shot to 2-shot (ablation) | Qwen-Long · Vertex-Set-in-Hyperedge Check | accuracy: 84.4% -> 93.4% | Helped |
| Use high-order rather than low-order structure languages for vertex-set correlations | Qwen-Long · LLM4Hypergraph high-order tasks | accuracy: Overall Avg. high-order language results are reported as 79.8%, 65.9%, 63.3%, 56.9%, 40.1%; low-order averages are 31.3% | Helped |
| Increase real-world citation hypergraph size from small to large | Qwen-Long · Citation hypergraphs, Vertex-Set-in-Hyperedge Check | accuracy: 94.0% -> 81.0% | Hurt |
Surprising findings
- Current LLMs remain near chance on isomorphism recognition, with binary accuracy around 50%.
- Adding more examples does not help low-order tasks, while high-order tasks gain roughly 6-9% from more shots.
Limitations
- Main experiments use only Qwen-Long, with the other models evaluated on a subset of settings.
- Tasks and hypergraph sizes are small (5 to 20 vertices), limiting scale.
- Hyper-COT gains are not uniform, and some encodings degrade under Hyper-COT v1 and v2.
Experimental setup
Datasets: synthetic hypergraphs (dhg hypergraph_Gnm random and regular structures) real-world citation network hypergraphs protein structure hypergraphs
Benchmarks: LLM4Hypergraph
Metrics: accuracy
Baselines: ERNIE-Lite-8K ERNIE-Speed-128K LLaMA3-8B GPT-3.5-Turbo GPT-4o Naive CoT
Builds on: Chain-of-Thought prompting Build-a-Graph prompting NLGraph GraphQA
Closest papers by meaning
- How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension (ICLR 2025 · similarity 0.90)
- SPHINX: Structural Prediction using Hypergraph Inference Network (ICML 2025 · similarity 0.90)
- Improved Expressivity of Hypergraph Neural Networks through High-Dimensional Generalized Weisfeiler-Leman Algorithms (ICML 2025 · similarity 0.89)
- Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models (NeurIPS 2024 · similarity 0.88)
- LLaGA: Large Language and Graph Assistant (ICML 2024 · similarity 0.87)
- Label-free Node Classification on Graphs with Large Language Models (LLMs) (ICLR 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.