Beyond Graphs: Can Large Language Models Comprehend Hypergraphs?
Authors: Yifan Feng
Chengwu Yang
Xingliang Hou
Shaoyi Du
Shihui Ying
Zongze Wu
Yue Gao
Venue: ICLR 2025 Poster (2025)
Keywords: LLMs
Hypergraph
Benchmark
Primary area: datasets and benchmarks

Abstract: Existing benchmarks like NLGraph and GraphQA evaluate LLMs on graphs by focusing mainly on pairwise relationships, overlooking the high-order correlations found in real-world data. Hypergraphs, which can model complex beyond-pairwise relationships, offer a more robust framework but are still underexplored in the context of LLMs. To address this gap, we introduce LLM4Hypergraph, the first comprehensive benchmark comprising 21,500 problems across eight low-order, five high-order, and two isomorphism tasks, utilizing both synthetic and real-world hypergraphs from citation networks and protein structures. We evaluate six prominent LLMs, including GPT-4o, demonstrating our benchmark’s effectiveness in identifying model strengths and weaknesses. Our specialized prompt- ing framework incorporates seven hypergraph languages and introduces two novel techniques, Hyper-BAG and Hyper-COT, which enhance high-order reasoning and achieve an average 4% (up to 9%) performance improvement on structure classification tasks. This work establishes a foundational testbed for integrating hypergraph computational capabilities into LLMs, advancing their comprehension.

Published as a conference paper at ICLR 2025
BEYOND GRAPHS: CAN LARGE LANGUAGE MODELS COMPREHEND HYPERGRAPHS?
Yifan Feng', Chengwu Yang", Xingliang Hou", Shaoyi Du², Shihui Ying", Zongze Wu"*, Yue Gao' School of Software, BNRist, THUIBCS, BLBCI, Tsinghua University
Institute of Artificial Intelligence and Robotics, College of Artificial Intelligence, Xi'an Jiaotong University School of Software, Xi' an Jiaotong University
'Department of Mathematies, School of Science, Shanghai University 'College of Mechatronics and Control Engineering, Shenzhen University evanfeng37egmail com, slandunkycwégmail com HouXI@stu. xjtu. edu. en, dushaoyi@xjtu. shyingeshu.. wew.inngssu.uuu.cc. edu. cn, zzwuēgdut. edw.gddut.dd..... edu. en, gacyue@tsinghua edu
en
ABSTRACT
Existing benchmarks like NLGraph and GraphOA evaluate LLMs graphs by focusing mainly on pairwise relationships, overlooking the high-order correla- tions found in real-world data. Hypergraphs, which can model complex beyond- pairwise relationships, offer a more robust framework but are still underexplored the context of LLMs. To address this gap, we introduce LLM4Hypergzs the first comprehensive benchmark comprising 21,500 problems across eight low- order, five high-order, and two isomorphism tasks, utilizing both synthetic and real-world hypergraphs from citation networks and protein structures. We evaluate six prominent LLMs, including GPT-4o, demonstrating our benchmark' 's effec- tiveness in identifying model strengths and weaknesses. Our specialized prompt- ing framework incorporates seven hypergraph languages and introduces two novel techniques, Hyper-BAl BAG and Hyper-COf which enhance high-orde reasoning and achieve an average 4% (up to 9%) performance improvement on structure classi- fication tasks. This work establishes foundational testbed for integrating hyper- graph computational capabilities into LLMs, advancing their comprehension. The source codes at http:///ww...oom//oooo/a///l////
INTRODUCTION
Devlin 2018 Brown 2020; Ouyang et al. 2022) have made significant strides in domains such as dialogue systems (Bubeck et al. (023) and image understanding (Zhao et al.] 2023). However, they often produce untruthful or unsupported content, Generation (RAG) (Vu et al. 2023) enhances prompts with relevant, factual, and up-to-date information (Khan-) delwal et al. 2019), thereby grounding outputs more effectively. RAG typically retrieves structured data with complex relational dependencies (Guu et al.] 2020). such as social networks or molecular structures, which are efficiently represented graphs. Graph representations capture intricate inter- dependencies and provide a concise encapsulation of data relationships. This has spurred research improve LLMs' understanding of craph-structured data (Guo et al. (023). leading to benchmarks like NLGraph (Wang et al., 2024). GraphΩA (Fatemi et al.) (023). and LLM4DyG (Zhang et al.) 2023 These benchmarks evaluate and enhance LLMs' capabilities in handling graph-related tasks, promoting the integration of graph-based representations in large language models.
Large Language Models (LLMs) /Vaswani 2017
known hallucinations Wang al. 2023h. To mitigate this, Netrieval-Augmentt
However, real-world data often involve complex correlations beyond simple pairwise relationships (Zhou et al. (2066). For example, sentences within document sharing common keywords may exhibit high-order correlations that traditional graph models fail to capture (PM et al.) 2017). In multimodal scenarios (Kim et al. 2020) Feng et al. 2023), interactions across different data types further increase correlation complexity, exceeding the capabilities of conventional graphs, which
"oorreponning authors: Yue Gao and Zongze Wu

---

Published as a conference paper at ICLR 2025
limited to pairwise correlations. In contrast, hypergraphs can model high-order correlations, capturing intricate interdependencies among multiple entities simultaneously. This capability allows hypergraphs to more accurately represent the complex relationships in retrieved information, thereby enhancing prompting strategies in L.MMs. Despite these advantages, hypergraphs pose a challenge process linear textual data and cannot naturally ingest
for L.Mss, which are primarily designed hypergraph structures (Feng et al. (2024). This limitation hinders the integration of hypergraph- based representations into LLM training and inference. Therefore, investigating whether LLMs can comprehend hypergraphs and developing prompts to improve their understanding of hypergraph structures remains an underexplored and promising research direction.
Here, we introduce the LLM4Hypergrage
Benchmark, the first comprehensive testbed de- signed to evaluate LLMs' understanding and reasoning of hypergraphs. Unlike existing graph benchmarks that focus low-order, pairwise vertex correlation tasks, our bench- mark presents high-order tasks involving tex sets and isomorphism tasks that assess mod- els' ability recognize and interpret global structural correlations within hypergraphs. Our benchmark includes both synthetic and real- world hypergraphs, such as citation and pro- tein networks, ensuring diverse and represen- tative evaluations across domains. It com- prises 21,500 problems, covering eight low- order tasks, five high-order tasks, and two iso- morphism tasks. Low-order tasks extend pair- wise correlation reasoning to more complex vertex interactions, while high-order tasks in- volve reasoning about relationships among tex sets, capturing the rich multi-vertex correlations inherent to hypergraphs. Isomorphism tasks evaluate the models' ability identify and interpret global structural patterns and symmetries within hypergraphs. To assess our benchmark's s effectiivnesss, we evaluate six mainstream LLMs (including ERNIE-Lite-8K, ERNIE-Speed- 128K, Qwen-Long. LLaMA3-8B, GPT-3.5-Turbo, and GPT-4o) on the LIM4Hypergraph Benchmark, as shown in Figure The evaluation revealed four findings:
ERNIE-Lite Lite SK
ERNIE ERNIE-Speed 128K
Qwen-Loon GPI-4o
LLAMA3-8B
GPT-3.5 Turbo
Structure Classification
Isomorphism Recognition
Isomorphism
Vertex Connection
Tásk
High-Order Task
Low-Order
Task
Nertex-Set-in Hyperedge Check
Reachability Check
Vertex Set Connection
Performance of six leading LLMs on three types of hypergraph understanding task.
Figure I:
In-context learning enhances LLMs' comprehension and performance in hypergraph tasks.
Current mainstream LLMs struggle with isomorphism recognition, especially in larger hy- pergraphs, though improvements are possible.
The proposed High-order languages (specified for hypergraphs) outperform low-order lan- guages in enabling LLMs to understand syyond-pairwiss correlations hypergraphs.
The proposed Hyper-COT and Hyper-BAC. BAG significantly boost LLMs' performance on more challenging hypergraph tasks like structure classification.
Additionally, we design a specialized prompting framework for hypergraphs with seven languages for low-order and high-order structures, enabling nuanced interactions with LLMs. We introduce two instruction-based prompting techniques: Hyper-BAG and Hyper-COT, which guide LLMS to visualize high-order correlations and better understand multi-vertex relationships. Experimental results show that Hyper-COT improves performance by 4% on average (up to 9%) in challenging structure classification tasks. Despite these advancements, challenges in high-order reasoning and encoding remain. Our work paves the way for future research to overcome these limitations and further integrate hypergraph capabilities into LLMs.
LLM4HYPERGRAPH BENCHMARK
In this section, we introduce the LLM4Hypergraph Benchmark, designed to evaluate LLMs' abil- ity to comprehend the intricate higher-order structures of hypergraphs. To ensure comprehensive assessment, the benchmark encompasses a diverse array of tasks and hypergraph configurations, as shown in Figure 2 It includes Low-order tasks (basic hypergraph properties and pairwise rela-
2

---

Published as a conference paper at ICLR 2025
Low-Order Tasks
High
High-Order Tasks
Verter
Vertex Set
LLM:4Hyerggraph Benchmark
Verter Connection Check
between Hyperedges
Shorteat Path Length
Reachabiitt Check
Verteo-Sat-in- Hyporadge Check
Hyperedge-in- Hyperadge Check
Structures
Hyperpaahh
Networks
Isomorphism Tasks
Hyporgraph
Hypergrach y
Hyper Pyramid
Hyper Checked Table
Hyper Wheel
Isomorphism Recognition
Structure Classification
Figure Overview of the LLM4Hypergraph Benchmark.
tional inferences), High-order tasks (understanding complex multi-verte interactions and higher- order dependencies), and Isomorphic tasks (recognizing structural equivalences despite hypergraph variations). Additionally, the LLM4Hypergrapa Benchmark incorporates hypergraphs of varying scales and types, ranging from small-scale hypergraphs with limited entities and relationships to large-scale, intricate hypergraphs that emulate real-world complexity. By addressing these dimen- sions, the benchmark provides a holistic framework for assessing the versatility and depth of LLMs in comprehending and processing hypergraphs. Our LLM4 Hypezgraph Benchmark comprises diverse collection of hypergraphs, including both synthetic and real-world instances. Synthetic hypergraphs are generated using random and regular-structured methods, while real-world hyper- graphs are sourced from citation and protein networks. These hypergraphs categorized by scale to ensure a balanced complexity for comprehensive evaluation. For a detailed description of the hypergraph generation process, please refer to Appendix D
2.1
TASK DESIGN
In this subsection, briefly introduce the 15 tasks included in our Lypegraag Bench- mark. Detailed descriptions and methodologies for these tasks are provided in Appendix E
Isomorphism Tasks. Isomorphic tasks fundamental category within the HLM4 rggaph Benchmark, designed to evaluate LLMs' ability to recognize structural equivalences and classify hypergraphs based on their overall architectural patterns. These tasks are crucial for applications in specialized fields such as molecular and protein structure analysis, where distinguishing between subtly different structural configurations is essential. We introduce two key isomorphic tasks:
Isomorphism Recognition. This task assesses the model's ability to determine whether two hypergraph representations correspond to the same underlying structure.
Structure Classification. This task evaluates the model's proficiency in distinguishing hy- pergraphs based on their macro-level architectural frameworks.
Low-Order Tasks. In addition to isomorphic tasks, our ILM4Hyyerrgaphh Benchmark incorpo- rates a series low-order tasks designed to test L.LMs* understanding fundamental hypergraph properties and vertex relationships. These tasks focus basic hypergraph attributes and simple connectivity patterns essential for more complex structural analyses.
Hyperedge Count. Counts the total number of hyperedges.
Vertex Count. Counts the total number of vertices.
Vertex Degree. Counts the hyperedges connected to specific vertex.
Vertex Connection. Checks if two vertices are directly connected by a hyperedge.
Connected Vertices. Lists all vertices connected given vertex.
3

---

Published as a conference paper at ICLR 2025
Table
Statistics of the I.M44Hypegrraph Benchmark.
Task
Task Name
Task Type
Difficulty
#Sample
Hyperedge Count
Counting Problems
Easy
1500
Vertex Count
Counting Problems
Easy
1500
Vertex Degree
Counting Problems
Easy
1500
Low-Order
Vertex Connection Check
Decision Problems
Medium
1500
Reachability Check
Decision Problems
Medium
1500
Shortest Path
Computational Problems
Hard
1500
Connected Vertices
Descriptive Problems
Hard
1500
Disconnected Vertices
Descriptive Problems
Hard
1500
Hyperedge Degree
Counting Problems
Easy
1500
Vertex Set Connection Check
Decision Problems
Medium
1500
High-Order
Vertex-Set Hyppereee Check
Decision Problems
Medium
1500
Hyperedge-in- -iyeeeeedgge Check
Decision Problems
Medium
1500
Shared- Shared-Vertices Vertices between Hyperedges
Descriptive Problems
Hard
1500
Isomorphism Recognition Structure Classification
Computational Problems
Hard
1500
Isomorphism
Classification Problems
Hard
Total
21,500
Disconnected Vertices. Lists all vertices not connected to given vertex.
Shortest Path. Finds the shortest path between two vertices.
Reachability Check. Determines
vertex can be reached from another.
High-Order Tasks. Building upon low-order tasks, LLMAHypergrapl Benchmark introduces high-order tasks designed to assess LLMs' comprehension of complex correlations between vertex
sets within hypergraphs. Unlike low-order tasks that focus on individual vertices and hyperedges, high-order tasks evaluate the model's ability to understand and manipulate relationships involving groups vertices and their interactions through hyperedges.
Hyperedge Degree. Determines the number of vertices in given hyperedge.
Vertex Set Connection (VS Connection). Checks if two vertex sets are jointly contained within least one hyperedge.
Vertex-Set Serece--ee-ii----ee Heeeee--yypeeege Check (VS-in-He Check). Determines if a set of vertices is entirely contained within any hyperedge.
Hyperedge-in-T in-Hyperedge Check (He-in-He Check). Assesses if one hyperedge is com- pletely contained within another hyperedge.
Shared- Vertices between Hyperedges. Identifies and outputs the set of vertices shared be- tween two hyperedges.
2.2 BENCHMARK STATISTICS
Our LiMAHypergraph Benchmark comprises 14 tasks totaling 21,500 problems, as detailed in T These tasks are categorized into five types: Counting Problems (counting specific elements), Computational Problems (numerical answers), Decision Problems (yes/no responses). Descriptive Problems (listing sets of vertices or hyperedges), and Classification Problems (categorical labels). Each type includes 1,500 samples, providing a comprehensive assessment LLMs' abilities in numerical computations, binary decisions, descriptive generation, and hypergraph classification.
PROMPT ENGINBERING FOR HYPERGRAPHS
Prompt design is essential for accurately evaluating LLMs our LIM4Hypergraph Benchmark, as prompts guide the models' understanding of hypergraph structures. Here, we integrate existing strategies such as CoT (Wei et al.) 2022 Kojima et al.) 2022) and Few-Shot Prompting (Brown, 2020 Zhou et al. 2022a) to develop prompt framework tailored for hypergraph-related tasks. Additionally, we introduce a hypergraph language for textual descriptions and adapt these techniques with modifications like Hypeer-BAG and Hyper-COT to better accommodate hypergraphs.

---

Published as a conference paper at ICLR 2025
Exomplex:
Prompt
Example
Evamples:
in hyprogoohh.....
[Exomple]
Hypergraph Description
veriec and verten connected with hyperodge. deserbes
hynergraph, ((A)) means weteer
"Proklem to vahve
and connected
Hypergraph Description
[Myper-BAG]
typararaph among verties ná, n1, ni, ná, ns, dB, o2, ng, nts add, nid, n42, ei'l aid, and a1 The hypenedges in oner (12 miu (e La (.n
hypergraph describes (11.)Z
hypendger
[Myper8AG]]
Question
Let's constrect hysorgnaph hyponedges piast
Let's construct the hypergrooh with the veriies and nyperedges firrt
Toil
Q: there hypenedge that conbate both vertex sex (n21 (n21,nd4) and vertor (sA]?
Toif
hyporeage that verdos (n]))
answers
[Hyper-COT]
[CoT-for-Amswer]
format [tes, Aijj.:
Ais the onsweers offer "Ars"" No.) At
Arec/tin,)
Prompt Framework for Hypergraphs
Besause, there typaredde
Let's onolyce connectiatt by considiring hyperedger listed to vertioe and versicss ditted shrough hyperodges.
containg both vertew set (n11,n1d) vertes vet (n7).
Figure 3: The proposed prompt structure for hypergraphs.
3.1 PROMPT FRAMEWORK
Prompt design is crucial for accurately evaluating LLMs in our LLM4 LLM4Hyeergraph Benchmark, as directs the models' understanding of hypergraph structures. Figure illlstraatss BlusteBellustrtees our prompt frame- work, which consists of six components: Example, Hypergraph Description, Hyper-BAG, Question, Tail, and Hyper-COT. The Example section includes question-answer pairs and may optionally con- tain COT-for-Answer for detailed reasoning. Optional modules are indicated by brackets in the figure. More details of the framework are provided in Appendix F In the following, we briefly introduce the following prompt configurations:
ZERO-SHOT Includes only Hypergraph Description, Question, and Tail, without exam- ples or additional reasoning prompts.
ZERO-HYPER-COT: Extends Zero-Shot by adding Hyper-COT after the Tail, introducing hypergraph-speccffic reasoning.
FEW-SHOT: Adds Example content with Hypergraph Description, Question, Tail, and An- swer to provide concrete instances for guidance.
COT: Enhances Few-Shot by including COT-for-Anwwer in each example, offering detailed reasoning steps for more accurate responses.
COT-HYPER-BAC. Builds the CoT setup by inserting Hyper-BAG between Hypergraph Description and Question, contextualizing the model's focus on hypergraph construction and comprehension.
3.2 HYPERGRAPII LANGUAGE
Unlike traditional graphs, hypergraphs allow hyperedges connect any number of vertices, requir- ing more complex textual descriptions. Abstract high-order descriptions may hinder LLM compre- hension, while low-order descriptions enhance understanding but omit essential information. To address this, we designed two hypergraph languages: Low-Order Structure Language and High- Order Structure Language, as shown in Figure 4 The former focuses on pairwise relationships. while the latter preserves complex multi-vertex correlations. More details can refer to Appendix G
Low-Order Structure Language. facilitate LLMs' understanding of hypergraph structures through pairwise correlations, we introduce three low-order structure languages as follows:
Low-inderr-nnideence Description (LO-Inc): Describes pairwise connections between ver- tices, e.g., "Vertex is connected to vertices and v3."
Neighbor-Pate Description (N-Pair): Lists all pairs of vertices that share hyperedge, e.g., "(V1, 02), (V1, Uz)."
Raw Adjacency Matrix Description (Adj-Mat): Uses a numerical adjacency matrix where binary values indicate connections between vertex pairs.
High-Order Structure Language. To further enhance LLMs' comprehension of hypergraph struc- tures through ordher-order correlations, introduce four high-order structure languages as follows:
5

---

Published as a conference paper at ICLR 2025
Low-Order Language
retern, nannecer to aertbitt
The cheeeemtten reboee bewees Cty (hu Suric Duind
The odfermnnn mo oelvert remoor
mnderss seen bi sertin zonnectr sertenty
Neighbor-Falt Description
Tru-AAdaaenty-Mtate Description (Ad] Mart)
Hypergraph
Description (LD-Ind)
Hettrr, tooeentdd Appcrgent vestary sus socorr Ruareger eu, Aa-
vembtaryy cenecterloommtaan extee i secented untior lawrndere, fueenolprr
reseecee'
hysmndees,
The heprrger (op
heceemer manber horggnee ITAS po
Ventvity corecttdion heperaget ty
loner by pontrand iitor by wir tverrdppey.
hyyerage comvened vettte it.
High Neighbor
High Order
Neighbor Description (N-Set)
Raw-lincidence Matrix Description (Inc Mar)
Description (HO-Nelph
Description (HD-Ind)
High-Order Structure Language
Figure 4: The proposed "Hypergraph Language" for Hypergraph Description section.
High-Order Order Neighbor Description (HO-Neigh): Describes hypergraph relationships two stages, detailing connections between vertices and hyperedges, then hyperedges and their vertices.
High-Order Incidence Description (HO-Inc): Extends LO-Ine by including higher-order correlations, such as "Vertex 81 is connected to vertices U2 and V3 with hyperedge e1."
Neighbor-Set Description (N-Set): Lists entire sets of vertices connected by each hyper- edge, for example, "(V1, 02; uz).""
Raw Incidence Matrix Description (Inc-Mat): Uses an incidence matrix where each entry indicates the inclusion of vertex in a hyperedge.
3.3 SPECIFICAL PROMPTING FOR HYPERGRAPISS
Given that hypergraphs are difficult to describe using conventional language, we introduce two spe- cialized prompting techniques enhance LLMs' comprehension of hypergraph structures: Hyper- BAG and Hyper-CO1 More details can be found in Appendix
Build-a- Mhildda-HHpped Hyyeergrapp Prompting (Hyper-BAG) facilitates mental visualization of hypergraphs by guiding LLMs to imagine their architecture, helping the model form a coherent representation of hypergraph connections (Wang al. 2024).
Meuii-of-Thhouee for Hypergraphs (Hyper-COr COT) adapts traditional CoT prompting by incorpo- rating step-by-step reasoning tailored for hypergraphs. It includes specific prompts that guide the model to break down complex hypergraph tasks into manageable steps:
v1: "Let's 's think step by step. Make sure the data is calculated and recorded accurately at each step."
.2: "Let's analyze the connectivity by considering hyperedges linked to vertices and vertices linked through hyperedges."
v3: "Let's think hyperedges connected by vertices then vertices connected by hyperedges."
4 EXPERIMENTS
Based on the I.LM4 HYM4Hypeegraph Benchmark, we aim to investigate whether language models can comprehend hypergraphs by evaluating L.LMs and different prompting settings.
Experimental Settings. We evaluate six LLMs: ERNIE-LLit-80 (Zhang et al.) 2019). ERNIE
Speed- 128K (Sun al. 202I). Qwen-Long (Bai et al. 2023). LLaMA3-8B (Touvron et al. 2023) GPT-3.5-Turbe (Brown 2020), and GPT-4 (Achiam et al. 2023), selected for their diverse architec- tures. our experiments, we employ Qwen-Long as the LLM due to its robust performance and scalability. In the FFew",hot", "CoT" and "CoT-Hyper-BAA BAG settings, we provide two examples by default. For Decision Problems, we maintain a balanced essitive-tonngatti ratio of 1:1 to ensure fairness. Other tasks assess consistency by comparing I.I. outputs ground truth.

---

Published as a conference paper at ICLR 2025
4.1 RESULTS OF DIFFERENT HYPERGRAPH LANGUAGES
We evaluated different hypergraph languages under various settings using synthetic hypergraphs, with the experimental results presented in Table 2 and Table 3
Observation 1: Low-order structure languages enhance LLMs' understanding of vertex cor- relations within hypergraphs. As illustrated in Table in low-order tasks, high-order languages outperform low-order languages in simple tasks, achieving higher accuracy due to their ability to ac- curately describe high-order structures. However, medium and difficult low-order tasks, low-order languages demonstrate superior performance. This decline in high-order language effectiveness in more challenging low-order tasks can be attributed to the redundancy of high-order descriptions when the primary focus shifts to investigating pairwise vertex correlations. Consequently, when the objective is to examine relationships between individual vertices within hypergraphs, low-order languages are more beneficial for enhancing LLMs' understanding.
Table 2: Results of different prompting frameworks and hypergraph languages.
Difficulty
Fsay
Medium
Hard
Settings
Hypenige Count
Vertex Count
Vertex Degree
Vertex Connection
Reachability Check
Shortest Path
Connected Verrices
Disconnection Vertices
N. Pair
18.4%
99.4%
41.2%
93.0%
91.6%%
60.2%
51.8%
34.0%%
59.2%
97.4%
67.4%
79.4%
ZERO SHOT
Adj-Mat
57.6%
100.0%
23.0%
92.2%
73.2%
47.6%
19.8%
14.0%
Avg.
45.1%
99.8%
34.9%
94.2%
86.2%
58.45
50.3%
29.6%
N. N-Set
85.8%
99.6%%
90.4%
89.6%
89.88
58.6%
46.2%
37.8%
HO-Ine
88.2%
100.0%
53.8%
84.0%
91.8%
70.4%
67.4%
39.8%
Ine-Mat
95.8%
99.8%
50.6%
79.8%
67.8%
33.8%
9.4%
8.6%
NiigN
87.6%
Avg.
90.0%
99.9%
70.2%
85.3%
85.5%
54.8%
39.0%
27. 97.8%
Pair
20.6%
75.0%
49.0%
94.6%
95.6%
62.9%
70.6%
39.4%
ZERO HYPER COT
LO-Ine
53.0%
99.8%
53.8%
99.8%
98. 4%
(9.8%
75.6%
57.2%
Adj-Mat
56.4%
99.2%
21.4%
94.0%
73.2%
51.8%
16.6%
7.2%
Avg.
43.3%
91.3%
41.4%
96.
89.1%
61.5%
54.3%
34,6%
N. Set
96.2%
54.6%
99.2%
91.4%%
91.6%%
63.2%
73.4%
46.4%
HO-Ine
97.2%
100.0%
2%
72.0%
73.8%
58.
Inc-Mat
76.0%
99.4%
67.8%
79.4%
69.4%
33.0%
16.4%
1.8%
HO-Neigh
91.4%
89.4%
97.6%%
96.0%
95.6%%
58.6%
58.6%
47.4%
Avg.
90.2%
85.9%
90.5%
91.7%
89.0%
56.7%
55.6%
65.0%
00.0%
30.4%
LO-Ine
95.6%
99.0%
45.4%
96.0%
93.6%
79.4%
92.8%
47.2%
FEW SHOT
Adj-Mat
79.2%
100.0%
33.8%
87.2%
85.6%
64.8%
34.2%
23.8%
Avg.
79.9%
99.4%%
42.7%
92.3%
90.1%
72.8%)
64.2%
33.8%
N-Set
84.0%
99.6%
78.0%
94.0%
88.8%
75.2%
55.8%
31.0%
HO-Ine
98.6%
100.0%
80.0%
98.2%
87.4%
74.8%
75.6%
45.4%
Inc-Mat
98.8%
73.0%
12.0%
14.8%
HO Neigh
97.8%
98.0%
96.4%
90.4%
88.6%%
63.2%%
40.4%
23.4%
Avg.
94.8%
99.4%
78.1%
88.9%
81.8%
65.0%
46.0%
28.7%
N-Pair
90.6%
99.6%
48.0%
93.8%
91.6%
66.4%
63.2%
32.2%
LO-Ine
45.6%
95.6%
04.0%
73.4%
92.8%
48.2%
Adj-Mai
92.6%
99.8%
38.8%
87.2%
87.6%
6-1.6%
35.4%
24.2%
COT
Avg.
93.5%
N-Set
82.6%
99.8%
89.49 39.4%
59.4%
31.4%
HO-Inc
97.2%
100.0%
87.2%
97.6%
87.6%
74.0%
78.2%
44.8%
Ine-Mat
97.8%
99.4%
60.4%
74.2%
66.6%%
44.4%
13.0%
15.0%
HO Neigh
96.5%
97.6%
96.4%
92.2%
88. 6%
60.4%
42.8%
24.0%
Avg.
93.6%
99.2%
811.4%
89.5%
83.1%
62.6%
48.4%
28. 896
N-Pair
87.8%
100.0%
44,4%
95.0%
92.0%
70.8%
62.0%
32.4%
COT-HYPERR BAG
LO-Ine
95.8%
99.8%
47.0%
96.4%
94.0%
78.4%
90.8%
46.2%
Mal
89.2%
100.0%
36.4%
88.4%
87.8%
67.2%
35.2%%
25.0%
Avg.
90.9%
99.9%
42.6%
93.3%
91.3%
72. 1%
62.7%
34.5%
N-Set
93.6%
100.0%
79.4%
93.6%
86.8%
74.6%
55.8%
29.8%
97.85
76.8%
Inc Mat
97.6%%
99.6%
60.2%
77.2%
72.0%
47.2%%
11.8%
16.0%
HO-Neigh
97.2%
90.0%
Avg.
96.7%
99.6%
80.2%
89.7%
83.2%
66.5%
45.6%
27.9%
Overall
83.4%
97.3%
63.4%
91.0%
86.6%
63.5%
52.1%
31.7%

---

Published as a conference paper at ICLR 2025
Table 3: Results of different prompting frameworks and hy hypergraph languages.
High. Order Tasks
Isomorphism
Diflicuity
Easy
Medium
Hard
Hard
Settings
Hyperodge Degree
Vertex Set
VS-in-He Check
He-in-He
Shared-Vertices between
Ismorphism Recognition
Structure Classification
Connection
N- Pair
51.6%
65.4%
73.0%
33.4%
30.3%
0%
25.2%
1.0-Ine
22.6%
77.4%
82.2%
54.6%
25.1%
47.0%
31.9%
ZERO-SERE PERO-SHOT SHOT
Adj-Mat
19.6%
[4.0%
10.6%
51.4%
35.7%
50. 00.6%
29.2%
Avg.
31.3%
52.5%
55.3%
46.5%
30.4%
49.9%
28.88
N-Set
85.8%
67.0%
51.7%
46.2%
41.2%
HO Inc
82.0%
83.8%
91.2%
61.6%
31.3%
50.6%
2%
Inc-Mat
39.2%
1.4%
45.4%
HO-Neigh
98.2%
82.2%
74.8%
57.2%
32.0%
51.2%
31.2%
Avg.
79.8%
65.9%
63.3%
56.9%
40.1%
53.2%
31.71%
N-Pair
54,2%
64.2%
79.6%
33.6%
29.7%
53.2%
27.0%
ZERO ZERO-HYPER CEO--HYPER-OOO COT
1.0-nnc
31.4%
Adj-Mat
19.2%
13.0%
4.6%
53.2%
31.7%
48. 6%
25.7%
Avg.
31.5%
53.6%
56.0%
46.1%
30.1%
51.1%%
28.0%5
N Set
52.8%
93.8%
92.0%
60.8%
91.5%
47.8%
32.3%
HO-Tne
97.0%
96.6%
98.0%
52.0%
96.9%
52. 8%
31.0%
Inc-Mat
52.0%
6.4%
2.6%
41.0%
44.4%
64.8%
26.1%
HO-Neigh
Avg.
75.5%
73.7%
72.8%
50.3%
81.8%
55.5%
32.0%%
N-Pair
56.4%
78.6%
81,2%
37.2%
22.6%
45.0%
30.5%
LO-Ine
33.2%
84.4%
90.8%
62,2%
20.7%
44.9%
42.0%
FEW-SHOT SHOT
Adj-Mat
26.2%
76.8%
53.2%
23.0%
41.4%
38.5%
Avg.
38.6%%
77.3%
82.9%
50.9%
22.1%
43.8%
37.0%%
N-Set
99.6%
83.4%
87.2%
82.6%
89.2%
43.3%
82.7%
HO-Ine
84.8%
87.8%
6%
65.2%
51.7%
14.2%
43.8%
Inc-Mat
40.6%
44.0%
53.2%
48.2%
23.0%
47.8%
53.5%
J1O-Neigh
99.87E
81.4%
87.2%
65.2%
62.7%
47.7%)
65.5%%
Avg.
81.2%
74.2%
80.3%
65.3%
56.7%
45.8%%
61.4%
N-Pair
76.4%
40.0%
25.7%
47.2%
28.3%
1.O. Inc
34.0%
84.4%
82.4%
$9.0%
18.5%
46.6%
41.8%
Adj-Mat
25.4%
74.6%
77.4%
62.4%
29.3%
44.2%
40.3%
COT
Avg.
36.4%
79.9%
78.7%
53.8%
24.5%
46.0%%
36.8%
N-Set
100.0%
84.0%
87.2%
77.4%
91.1%
47. 97.2%
82.3%
HO-Ine
86.6%
88.4%
88.4%
69.8 99.8%
55.2%
46.0%
41.66
Ine-Mai
57.4%
60.00%
110 Neigh
100.0%
84.2%
82.66%
66.6%
62.0%
49. 29
66.4%
Avg.
58.
N Pair
53.2%
77.4%
75.0%
38.8%
24.9%
47.0%
27.4%
COT-HYPER-BB BBAG
1.0-Ine
32.8%
86.4%
82.2%
65.4%
23.9%
46.5%
39.4%
Adj Mat
24.0%
49.8%
66.4%
64.6%%
33.6%%
47.4%
38.9%
Avg.
47.
35.2%
N-Set
100.0%
84.6%
6%
81.4%
89.4%
46.6%
87.2%
HO-Ine
86.6%
90.4%
88.2%
77.2%
53.5%
48.2
38.9%
Mat
44.6%
27.2%
43.0%
58.2%
28.4%
58.8%
49.6%%
HO-Neigh
100.0%
83.09:
81.6%
70.4%
61.8%
56.6%
65.0%
Avg.
82.8%
71.3%
1%
71.8%
58,3%
52.6%
60.2%
Overall Avg.
60.8%
69.9%
72.0%
57.4%
45.2%
49.8%
42.3%
Observation 2: High-order structure languages enhance LLMs' comprehension of vertex set correlations within hy hypergraphs. As shown in Table 3 high-order structure languages signif- icantly outperform low-order structure languages in high-order and isomorphism tasks across all difficulty levels. This improvement stems from high-order tasks focusing on vertex set correlations, which low-order languages find challenging to describe. High-order languages effectively repre- sent complex multi-vertex structures, enabling LLMs to perform accurate computations and provide precise answers for intricate relationships. Consequently. using high-order structure languages sig- nificantly boosts LLMs' understanding of vertex set correlations within hypergraphs.
Observation 3: Current LLMs struggle with isomorphism recognition tasks, but example- based prompting can partially bridge this gap. In binary classification isomorphism tasks, LLMs achieve around 50% accuracy (Table 3), showing that existing hypergraph textualizations are inad-
8

---

Published as a conference paper at ICLR 2025
equate. In chree-class structure classification, low-order structure languages produce approximately 30% accuracy, failing to distinguish macro structures, and high-order structure languages alone of- fer little improvement. However, combining high-order structure languages with example- based prompting increases accuracy to over 60%, suggesting that providing examples can aid LLMs in better understanding high-order structures and distinguishing between different macro-structures.
Observation 4: In-context learning methods enhance LLMs' understanding of hypergraph structures and task logic, thereby improving accuracy. Our experiments in Table 2 and Table 3 show that providing examples, such as Few-Shot and CoT prompts, significantly boost LLM perfor- mance compared scenarios without examples. These examples help LLMs grasp the task logic, follow instructions more effectively, and produce accurate results. Specifically, settings with ex- amples exhibit notable accuracy increases, highlighting the crucial role of in-context learning in understanding complex hypergraph structures and task requirements.
In the following, we selected two typical tasks from each of the three hypergraph categories study the LLMs' understanding of hypergraphs in depth.
4.2 RESULTS OF DIFFERENT LLMS
We evaluate six mainstream LLMs on hypergraph tasks, as shown in Figure ! Larger models like GPT-4 outperform smaller ones such as GPT-3.5, highlighting the importance of model capacity in understanding complex hypergraph relationships. While LLMs handle low-order and high-order tasks-ana local and multi-vertex associations- struggle with isomorphism recognition, which requires a comprehensive understanding of entire hypergraph structures beyond their current visualization and global pattern recognition abilities.
Observation 5: Enhancing LLM capabilities improves hypergraph understanding, but cur- rent models generally cannot solve isomorphism recognition tasks for macro-structures. Our evaluation shows that increasing model power aids hypergraph comprehension, yet existing LLMs fail to recognize and distinguish complex global structures within hypergraphs. This limitation un- derscores the need for future research enhance LLMs' ability to visualize and internally represent high-order relational dependencies essential for effective isomorphism recognition. Consequently, only low-order and high-order tasks are used for further evaluation.
4.3 RESULTS OF DIFFERENT HYPER-COS COT PROMPTINGS
Observation Hyper-COT enhances LLMs' hypergraph comprehension. Hypergraphs high- order correlations challenge LLMs more than low-order structures. We introduce Hyper-COT, adding step-by-step prompts. Tested on structure classification tasks (Table 4.. Hyper-COT con- sistently outperforms the "Naive COT". Note that "Naive COT" refers to "Let's 's think step by step". Specifically, Hyper-COT v3 boosts performance by 4% on average across seven encodings and up to 9% in N-Pair and N-Set encodings by guiding LLMs to interpret connections hierarchically.
Table 4: Resutls of different Hyper-COT prompts on the structure classification task.
Low-Order Language I.O-Ine
High-Order Language HO-Ine
Avg.
N-Pair
Adj-Mat
N-Set
Inc-Mat
HO-Neigh
Rank
Naive COT
24.3%
30.1%
27.0%
27.0%
25.2%
23,0%
32.3%
2.86
Hyper-COT v1
22,1%
27.4%
26.1%
29.6%
25.8%
23.9%
31.4%
2.86
Hyper-COT v2
22.1
23.5%
27.1%
28.8%
27.0%
23.5%
31.9%
2.71
Hyper-COT v3
33.6%
36.7%
27.9%
36.0%
20.9%
29.2%
32.4%
1.43
4.4 RESULTS OF HYPER-BAG PROMPTING
Observation 7: Hyper-BAG enhances LLMs performance on high-order tasks. While Build-
A- A-Graph (BAG) prompting Wang et al. 2024) is effective for graph understanding. we introduce Hyper-BAG tailored for hypergraphs. Experiments in Table 5 5 show that BAG does not significantly improve simple low-order tasks. However, both BAG and Hyper- BAG enhance performance by over 2% in high-order tasks, with Hyper- BAA achieving 2.8% improvement in the Vertex Set Connec- tion task compared to no BAG usage. These findings demonstrate that Hyper-BAt BAG effectively aids LLMs in understanding and performing high-order hypergraph tasks.
Byp

---

Published as a conference paper at ICLR 2025
Table The influence of using additional Hyper- BAG prompting under different settings.
Table 6: The influence of the Hyper-COT
with k-shot step-by-step demonstration.
Low Oww-Order Tasks
High-Orler Tasks
Low--Odder
Tasks
High-Order Tasks
Settings
Vertex
Rea.
VS
VS-in-Ho Chock
#Shot
Vertex. Con.
Rea. Chock
VS
VS-in-Ho
Con.
Check
Connection
Connection
Chock
94.0%
88.8%
83.4%
87.2%
0
83,8%
91.4%
84.4%
84,4%
BAG
93.0%%
90.2%
85.2%
89.2%
82.4%
79.2%
90.2%
86.4%
COT-BAG
93.6%
87.8%
84.6%
87.2%
96.2%
84.4%
87.8%
93.4%
Hyper BAG
93.6%
89.4%
86.2%
89.8%
3 97.8%
85.8%
90.4%
92.6%
4.5
RESULTS OF HYPER-COM WITH DIFFERENT NUMBER OF SHOTS
Observation Providing example solutions enhances LLMs' understanding of hypergraphs. In structure classification tasks, supplying example solutions improves LLMs' comprehension of hy- pergraphs. Experiments 6able show that increasing the number of examples does not enhance performance in low-order tasks. However, in high-order tasks, more examples lead to significant performance gains of approximately 6% to 9% compared to no examples. Specifically, example prompts help LLMs better understand and distinguish complex hypergraph structures, thereby en- abling more accurate classifications.
4.6 RESULTS OF DIFFERENT HYPERGRAPII SIZE ON
HYPERGRAPHI
Observation 9: Larger hypergraphs pose greater challenges for LLMs' comprehension. We further investigated the impact of hypergraph size on the ability of LLMs to understand hyper- graph structures. The experimental results are presented in Table 7 Considering that real-world hypergraphs exhibit certain regularities as the number of vertices increases, we sampled hypergraph structures from citation networks and protein structures for this experiment. The hypergraph sam- pling method and size settings are detailed Appendix D From the results, we observe that as the size of the hypergraph increases, the performance of LLMs deteriorates. This trend is more pronounced in high-order tasks compared to low-order tasks. Specifically, in citation data, the per- formance on high-order tasks declines by up 13% the hypergraph size grows. This degradation attributed to the increased complexity of larger hypergraph structures, which hinders LLMs' abil- ity comprehend and reason effectively.
Table 7: Influence of hypergraph size on real-world citation and protein datasets.
Low-Order Tasks Reachability Check
High- Order Tasks
Vertex Connection
Vertex Set Connection
Vertex-Set-in-Hyee Hereei--yyrrdggee
Check
Small 96.0%
90.0%
95.0%
94.0%
Citation Middle
100.0%
82.0%
93.0%
90.0%
Large
97.0%
77.0%
91.0%
81.0%
Small
86.0%
92.0%
96.0%
92.0%
Protein
Middle
90.0%
91.0%
94.5%
86.0%
Large
90.0%
88.0%
94.0%
88.0%
CONCLUSION
In this paper, we introduce LLM4HYpergraph, the first benchmark designed to evaluate and en- hance LLMss' understanding of hypergraph-structured data. Our benchmark includes 21,500 tasks covering various low-order, high-order, and isomorphism challenges using both synthetic and real- world hypergraphs. Evaluating six prominent LLMs, we demonstrate the benchmark's 's ability to identify model strengths and weaknesses. Additionally, our specialized prompting framework, fea- turing Hyper-BAG and Hyper-COT, boosts reasoning performance by average 4% (up to 9%) the structure classification task. This work lays the groundwork for future integration of hypergraph computational capabilities into LLMs, fostering more advanced data comprehension.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported by the National Natural Science Foundation of China under Grant (No. U24A20252, 623B2066), the National Major Scientific Instruments and Equipments Development Project of National Natural Science Foundation of China under Grant 62327808, Beijing Natu- ral Science Foundation (No. L242167). the Key Research and Development Program of Shaanxi Province of China under Grant Nos. 2024PT-ZCK-66 and 4024CY2-GJHX-45 Guangdong Major Project of Basic and Applied Basic Research under Grant 202380303000009, National Key Labora- tory of Human-Maching Hybrid Augmented Intelligence, Xi'an an Jiaotong University (No. HMHAI- 202412). We would like to express our sincere gratitude to OPPO for their generous support of our work.
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Ale- man, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774 2023.
Jinze Bai, Shuai Bai, Shusheng Yang. Shijie Wang, Sinan Tan, Peng Wang, Junyang Lin, Chang Zhou, and Jingren Zhou. Qwen-vl: A frontier large vision-language model with versatile abilities. arXiv preprint arxi::2308..22 12966, 2023.
Tom B Brown. Language models few-shot learners. arXiv preprint
2020.
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Ka- mar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv:2303.127111 2023.
Sirui Chen, Mengying Xu, Kun Wang, Xingyu Zeng, Rui Zhao, Shengjie Zhao, and Chaochao Lu. Clear: Can language models really understand causal graphs? arXiv preprint arXiv:2406. 16605, 2024.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 14168, 2021.
Jacob Devlin. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.048800 2018.
Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. Talk like a graph: Encoding graphs for large language models. arXiv preprint urXiv:2310.04500 2023.
Yifan Feng, Shuyi Ji, Yu-Shen Liu, Shaoyi Du, Qionghai Dai, and Yue Gao. Hypergraph-basse multi-modal representation for open-set 3d object retrieval. IEEE Transactions on Pattern Anal- ysis and Machine Intelligence, 2023.
Yifan Feng, Jiashu Han, Shihui Ying, and Yue Gao. Hypergraph isomorphism computation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant, Did aristotle use laptop? a question answering benchmark with implicit reasoning strategies. Transactions of the Association for Computational Linguistics,
2021.
Jiayan Guo, Lun Du, Hengyu Liu, Mengyu Zhou, Xinyi He, and Shi Han. Gpt4graph: Can large language models understand graph structured data? an empirical evaluation and benchmarking. arXiv preprint arXiv:2305./550 55066, 2023.
Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Mingwei Chang. Retrieval augmented language model pre-training. In International conference on machine learning, pp. 3929-3938. PMLR, 2020.
Urvashi Khandelwal, Omer Levy, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. Generalization through memorization: Nearest neighbor language models. arXiv preprint arXiv:1911.00177 2019.
11

---

Published as a conference paper at ICLR 2025
Eun-Sol Kim, Woo Young Kang, Kyoung-Wood Woon On, Yu-Jung Heo, and Byoung- Tak Zhang. Hyper- graph attention networks for multimodal learning. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognition, pp. 14581-14590, 2020.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 11222199-2221,,, 2022.
Soochan Lee and Gunhee Kim. Recursion of thought: A divide-and-conquer approach to multi- context reasoning with language models. arXiv preprini (rXii:230660689), 2023.
Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom. Program induction by rationale gener- ation: Learning to solve and explain algebraic word problems. arXiv preprint arXiv:1705.04146, 2017.
Chenxiao Liu, Shuai Lu, Weizhu Chen, Daxin Jiang, Alexey Svyatkovskiy, Shengyu Fu, Neel Sun- daresan, and Nan Duan. Code execution with pre-trained language models. arXiv preprint arXiv:2305.05383, 2023.
Zihan Luo, Xiran Song, Hong Huang, Jianxun Lian, Chenhao Zhang, Jinqi Jiang, Xing Xie, and Hai Jin. Graphinstruct: Empowering large language models with graph understanding and reasoning capability. arXiv preprint arXiv:2403.0444. 044433 2024.
Aman Madaan, Shuyan Zhou, Uri Alon, Yiming Yang, and Graham Neubig. Language models of code are few-shot commonsense learners. arXiv preprint arXiv:2210.07128, 2022.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to fol- low instructions with human feedback. Advances in neural information processing systems, 35: 27730-27744 2022.
Arkil Patel, Satwik Bhattamishra, and Navin Goyal. Are nlp models really able solve simple math word problems? arXiv preprint arXiv:2103.07191, 2021.
Dhanya PM, A Sreekumar, M Jathavedan, and P Ramkumar. Document modeling and clustering using hypergraph. International Journal of Applied Engineering Research, 12110):2127-2135, 2017.
Swarnadeep Saha, Prateek Yadav, Lisa Bauer, and Mohit Bansal. Explagraphs: An explanation graph generation task for structured commonsense reasoning. arXiv preprint arXiv:2104.07644, 2021.
Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonse al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. arXiv preprint arXiv:2206.0400 046115 2022.
Yu Sun, Shuohuan Wang, Shikun Feng, Siyu Ding, Chao Pang, Junyuan Shang, Jiaxiang Liu, Xuyi Chen, Yanbin Zhao, Yuxiang Lu, et al. Ernie 3.0: Large-scale knowledge enhanced pre-training for language understanding and generation. arXiv preprint arXiv:2107.02137, 2021.
Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. Commonsensega: A question answering challenge targeting commonsense knowledge. arXiv preprint arX1: 2018.
Niket Tandon, Bhavana Dalvi Mishra, Keisuke Sakaguchi, Antoine Bossclut, and Peter Clark. Wiqa: A dataset for" what if..." reasoning over procedural text. arXiv preprint (tti::/999.4773333 2019.
Jianheng Tang, Qifan Zhang, Yuhan Li, and Jia Li. Grapharena: Benchmarking large language models on graph computational problems. arXiv preprint (tXXi:2447000377 2024.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Niko- lay Bashlykov. Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open founda- tion and fine-tuned chat models. arXiv preprint w072022307.09288 2023.
12

---

Published as a conference paper at ICLR 2025
A Vaswani. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
Tu Vu, Mohit Iyyer, Xuezhi Wang, Noah Constant, Jemyy Wei, Jason Wei, Chris Tar, Yun-Hsuan Sung. Denny Zhou, Quoc Le, et al. Freshllms: Refreshing large language models with search engine augmentation. arXiv preprint arXiv:2310.032// 2023.
Cunxiang Wang, Xiaoze Liu, Yuanhao Yue, Xiangru Tang, Tianhang Zhang. Cheng Jiayang, Yunzhi Yao, Wenyang Gao, Xuming Hu, Zehan Qi, et al. Survey on factuality in large language models: Knowledge, retrieval and domain -peniiiipeeiiiictty. arXiv preprint arXiv:2310.07521, 2023.
Heng Wang. Shangbin Feng, Tranxing Hc, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can language models solve graph problems in natural language? Advances in Neural Information Processing Systems, 36, 2024.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Lc, Denny Zhou, al. Chain-of-thouggh prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837, 2022.
Sean Welleck, Jiacheng Liu, Ximing Lu, Hannaneh Hajishirzi, and Yejin Choi. Naturalprover: Grounded mathematical proof generation with language models. Advances Neural Information Processing Systems, 35:4913-4999 2022.
Zeyang Zhang, Xin Wang, Ziwei Zhang, Haoyang Li, Yijian Qin, Simin Wu, and Wenwu Zhu. Llm4dyg: Can large language models solve problems on dynamic graphs? arXiv preprint arXiv:2310.17110 2023.
Zhengyan Zhang, Xu Han, Zhiyuan Liu, Xin Jiang, Maosong Sun, and Qun Liu. Emie: Enhanced language representation with informative entities. arXiv preprint arXiv:9905.07129, 2019.
Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, et survey of large language models. arXiv preprint 2333::230331822333 2023.
Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. Learning with hypergraphs: Clustering, classification, and embedding. Advances in neural information processing systems, 19, 2006.
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuur- mans, Claire Cui, Olivier Bousquet, Quoc Le, et al. Least-to-most prompting enables complex reasoning in large language models. arXiv preprint arXiv:2205. 10625, 2022a.
Hattie Zhou, Azade Nova, Hugo Larochelle, Aaron Courville, Behnam Neyshabur, and Hanie Sedghi. Teaching algorithmic reasoning via in-context learning. arXiv:2211.09000 2022b.
arXiv preprint
13

---

Published as a conference paper at ICLR 2025
A RELATED WORKS
LLMs for Graphs. LLMs' ability to address graph-based problems has garnered significant at- tention. Benchmarks like NLGraph Wang al. (2024), GraphInstruct Luo al. (2024), GraphOA Fatemi et al. 2023), and LLM4DyG Zhang et al. 2023) demonstrate LLMs' potential in handling structured and dynamic graph data, emphasizing the importance of encoding strategies. Additionally, in structured commonsense reasoning, LLMs generate various graph structures from
natural language inputs (Tandon et al., 2019 Madaan et al. 2022. Saha et al., 202T). However, LLMSs ability to perform reasoning within hypergraphs remains underexplored. To bridge this gap, we introduce the benchmark, designed to enhance LLMs' understanding of hypergraph tasks.
LLMs for Few-Shot Reasoning. Extensive research has assessed LLMs' few-shot reasoning across arithmetic, logical, and commonsense domains. Arithmetic tasks use datasets like AQUA (Ling al., 2017), GSM8K (Cobbe et al.] 202T), and SVAMP (Patel al. 2021). For mathematical reasoning, NaturalProofs (Welleck et al., 2022) evaluates LLMs' ability to generate proof steps and complete proofs. Logical reasoning includes symbolic problems such as Coin Flip and Last Letter Concatenation (Wei et al.) 2022), and the Logic Grid Puzzle from BIG-BENCH (Srivastava et al.,
2022). Commonsense reasoning utilizes datasets from Talmor et al. (0188) and Geva et al. (2021)
Additionally, methods to enhance and evaluate LLMs' algorithmic reasoning have been developed Zhoo et al. 2022b; Lee & Kim 2023 Liu al. 2023). Despite these efforts, achieving reliable and
deep reasoning remains challenging. To address this, we introduce the LLM4Hype pepprrrrrphh... aimed
at improving the assessment of LLMs' reasoning abilities hypergraph- based tasks.
B EXPERIMENTS OF THE UNCERTAINTY QUANTIFICATION
To comprehensively assess the capability of LLMs in comprehending hypergraphs, we designed a series of experiments focusing their performance across various hypergraph-related tasks. Rec- ognizing the importance of uncertainty quantification and error characterization, we introduced con- trolled randomness by setting the temperature parameter to 0.8. This setup allows for the exami- nation of model stability and consistency in output generation. We evaluated six prominent LLMss: ERNIE-Lite-SK. ERNIE-Speed- 128K, Qwen-Long, LLaMA3-SB, GPT-3.5 Turbo, and GPT-4o. For each model, five independent runs were conducted to ensure the reliability of the results.
The evaluation encompassed six distinct tasks categorized into three types: low-order tasks (Vertex Connection Check and Reachability Check), high-order tasks (Vertex Set Connection Check and Sertx--Setin--yypeee Check), and isomorphism tasks (Isomorphism Recognition and Structure Classification). Table 8 presents the mean accuracy and standard error for each model across these tasks.
Table 8: Mean accuracy (%) and standard error for each model across various tasks.
Low-Order Tasks
High-Order Tasks
Isomorphism Tasks
Model
Vertex Connection
Reachability Check
Vertex Set Connection
Ve-in-He Check
Isomorphism Recognition
Structure Classification
FRNTE-L Lite-KK
82.12
78.28
67.52+ as
77-5242.18
43.2440.11
42.58 =4.60
ERNIE-Spead-128K
78. 78.01-20.00
97. 97.56=o.oz
67. 20:0
71 21.2142.00
43. 13.84 44.144
22,83 20.22
Owen-Long
97.56_2o.16
98.24_0.24
73.96 as
18
14.6010.02
44.942o.05
LLaMA3-8B
79.48.1.33
82.60
71.80
78. 78.40114.1
47. 47.7241.
23.70
GPT-3.5 Turbo
73.68=1.01
74.12-1.29
58, 1.84
70.400+1.10
41.68+0..11
27.60=3.49
GPT-4o
66.68_00.00
99.48
96.3610 os
98. 98.6840.15
44.0440.10
27.32_8.00
The results reveal several key insights into the performance and reliability of the evaluated LLMs. Firstly, most models exhibit low standard errors across various tasks, indicating high consistency and reliability in their performance. For example, Qwen-Long achieved a mean accuracy of 97.56 0.16% on the Vertex Connection Check task, demonstrating exceptional stability. Secondly, significant variability exists in the performance of different models the same tasks. While Qwen- Long excels in the Reachability Check task with an accuracy of 1988.2 0...2400.244 24% ERNIE-Speed- 128K underperforms in the Structure Classification task, attaining only 22.83 + 0.20%. This variability highlights inherent differences in the capabilities of each model rather than being attributable to random errors.
14

---

Published as a conference paper at ICLR 2025
Furthermore, high-order tasks present greater challenges, evidenced by higher standard emrors in some models. Notably, GPT-4o exhibits a substantial standard error of 8.68% in the Structure Classification task, underscoring the increased complexity involved in high-order relational reason- ing. This indicates that while LLMs can handle low-order relationships with high consistency, their performance in more complex, high-order tasks remains variable and warrants further investigation.
In summary, the comprehensive experimental evaluation demonstrates that the evaluated LLMs maintain consistent and reliable performance across a range of hypergraph-related tasks, with min- imal impact from random errors. However, significant performance differences among models and challenges in high-order tasks highlight the distinct strengths and limitations of each architecture. These findings provide a robust foundation for future research aimed at enhancing the hypergraph comprehension abilities of L.MMs.
C IMPACT OF HYPERGRAPH DOMAINS ON LLM PERFORMANCE
To explore how the performance of LLMs varies across different hypergraph domains, conducted an additional set of experiments using real-world hypergraph datasets. The motivation behind this investigation stems from the recognition that hypergraph structures significantly influence the ability of LLMs to comprehend and reason about complex relationships. Specifically, we aimed to assess both low-order and high-order understanding capabilities of LLMs within varying hypergraph contexts.
We selected two representative datasets: the Coauthorship dataset and the Protein dataset. These were chosen based on their distinct average hyperedge degrees, with the Coauthorship dataset ex- hibiting an average hyperedge degree of 3.34 and the Protein dataset an average 2.75, compared to traditional low-order structured graphs which typically have average hyperedge degree of 2. This distinction allowed us to quantify the high-order nature of each dataset and evaluate the models' performance accordingly. The experiments focused on two primary tasks: the Vertex Connec- tion Check Task as a representative low-order node understanding task, and the Vertex-Set-ine Hyperedge Check Task as representative high-order hyperedge understanding task. To encode the hypergraph structures, we employed four distinct high-order encoding methods N-Set, HO-Ine, Inc-Mat, and HO-Neigh-ensuringg comprehensive evaluation of different encoding strategies.
Table 9: Mean accuracy (%) for each model across different hypergraph Domains and Tasks
Low-Order Task
High-Order Task
Model
Coauthorship
Protein
Coauthorship
Protein
Averaged Hyperedge Degree
3.34
2.75
3.34
2.75
N-Set
98.0
97.6
95.6
94.6
HO-Ine
99.6
99.6
97.2
87.2
Inc-Mat
79.8
72.8
91.2
94.6
HO-Neigh
76.4
87.6
88.4
81.6
Averaged Results
88.4
89.4
93.1
89.5
T presents the mean accuracy for each model across the different tasks and datasets. The results reveal that for the high-order Serte--St-iin-Hyyerede Check Task, the performance of LLMs improved as the hyperedge degree of the dataset increased, with an approximate enhancement of 3.6%. This suggests that the high-order encoding methods effectively enhance the models' ability to handle complex relational tasks, particularly benefiting from the richer high-order structures present the Coauthorship dataset. contrast, for the low-order Vertex Connection Check Task, lower hyperedge degree correlated with better performance. Datasets with hyperedge degrees closer to traditional graph structures facilitated higher accuracy, likely due to reduced redundancy in high- order descriptive language, which simplifies structural comprehension for LLMs.
Furthermore, our findings confirm that variations in hypergraph domains lead to significant dif- ferences in LLM performance. These differences fundamentally attributable variations in hypergraph data distributions across domains, such as the sparsity of connections and the density of hyperedges. For instance, the Protein dataset, with lower average hyperedge degree of 2.75.
15

---

Published as a conference paper at ICLR 2025
supported better performance in low-order tasks compared to the Coauthorship dataset. This under- scores the importance considering domain-specific characteristics when evaluating and designing LLMs for hypergraph comprchension.
In summary, the extended experiments demonstrate that the performance of LLMs is inherently influenced by the characteristics of hypergraph domains. Higher-order structures in datasets like Coauthorship enhance LLMs' capabilities in complex relational tasks, while lower-order structures in datasets such as Protein support better performance in simpler tasks. These insights highlight the necessity of tailoring hypergraph encoding strategies to specific domain characteristics to optimize LLM performance. Future work will involve expanding this analysis additional real-world hy- pergraph datasets from diverse domains to further elucidate the domain domain-specific impacts on LLM performance.
D HYPERGRAPH GENERATION
We create a diverse series of hypergraphs that cover both synthetic and real-world instances. The LIM4Hypergraph, Benchmark encompasses wide spectrum of hypergraph types and scales, thereby providing a robust and versatile framework for assessing the proficiency of large language models in understanding and processing hypergraph-based data structures.
D.1 SYNTHETIC HYPERGRAPHS
We first introduce the construction of synthetic hypergraphs. The synthetic hypergraphs can be cat- egorized into two distinet types: random hypergraphs and regular-structured hypergraphs. Random hypergraphs are generated using the hhyerrrrah_ (amrr) function from the DHG toolkif" Im- portantly, we configure these hypergraphs with "low-order first" structure. This configuration grounded in the principle of Occam's 's razor, which posits that simpler, lower-order associations are more prevalent and thus more representative of real-world scenarios where low-order relationships typically dominate over high-order ones. Consequently, random hypergraphs are extensively utilized across various tasks within the benchmark, with the exception of isomorphic tasks where structured classification is paramount. In contrast, regular-structured hypergraphs are specifically tailored for structural classification tasks. We select three classical hypergraph structures Feng et al. (2024) known for their distinct and regular patterns: the Hyper Pyramid, Hyper Checked Table, and Hyper Wheel. To introduce variability and enhance the robustness of the benchmark, we systematically modify the hyperparameters of these base structures. For instance, we vary the number of layers in the Hyper Pyramid and the number of vertices per blade in the Hyper Wheel, thereby generating a multitude of structurally diverse yet regularly patterned hypergraphs.
D.2 REAL- WORLD HYPERGRAPHS
As for the real-world instances, we source data from citation networks and protein structure datasets. The construction process involves randomly sampling sub-hypergraphs by selecting central vertex and performing a random walk through selected hyperedges. During this walk, the vertices encoun- tered randomly retained until the uubhhypeggr reaches the predetermined vertex count. This methodology ensures that the sampled hypergraphs retain the intricate and authentic correlations inherent in real-worke data.
D.3 MULTI-SCALE SETTINGS
To ensure scalability and applicability across range of scenarios, both synthetic and real-world hypergraphs are categorized based on their size, defined by the number of vertices: small-scale hypergraphs (Containing between 5 to 10 vertices), medium-scale hypergraphs (Containing between 10 to 15 vertices), and large-scale hypergraphs (containing between 15 to 20 vertices). Additionally, to maintain structural generality, synthetic hypergraphs adhere a hyperedge-to-wee -ereedee-to-veetxx ratio ranging from 0.2 to 1.5 times the number of vertices. This ratio ensures balanced complexity that is neither
hoyyrrandmmm.hyyegrrahhh Gnm()
www.deephyyergraph.com
16

---

Published as a conference paper at ICLR 2025
too sparse nor excessively dense, thereby facilitating meaningful evaluations of LLM capabilities. In contrast, real hypergraphs do not impose such restrictions on the number of hyperedges, allowing them to naturally reflect the inherent connectivity patterss of their source datasets.
E DETAILS OF TASK DESIGN
In this section, we will introduce the proposed three types of tasks in detail, respectively.
E ISOMORPHISM TASKS
In the LLM4Hypergraph Benchmark, we prioritize isomorphic tasks as a fundamental component of our evaluation framework. This prioritization is grounded in the belief that a comprehensive understanding of the overall structural architecture essential for LLMs to be effectively utilized in practical applications. Isomorphic tasks serve as theoretical cornerstone for numerous model capabilities, particularly in specialized fields such as molecular structure analysis and protein anal- ysis. In these domains, proteins with similar global structures but differing local configurations can exhibit entirely distinct properties. This phenomenon underscores the necessity for models to pos- sess heightened sensitivity structural isomorphism, enabling them to accurately recognize and differentiate between nuanced structural variations. To evaluate this capability, we introduce two representative isomorphic tasks within our benchmark:
Isomorphism Recognition. This task assesses the model's ability to determine whether two different representations accurately reflect the same underlying hypergraph structure. Given two hypergraphs G = [V.E} and G' = {V','), E'}, the target to find whether a bijective mapping == V + V exists. The mapping is called the isomorphism function, such that (U1, U2,,... Um) E & 3
(g(v1). [V can directly have 9 and G' are not isomorphism.
E 8'. Note that if [V /
Structure Classification. This task evaluates the model's proficiency in distinguishing hy- pergraphs based on their macro-level architectural frameworks. It requires the model to identify and understand differences in the overall structural layout, even when local config- urations may appear similar. Let S denote an equivalence class set of hypergraphs, encom- passing several distinct types of hypergraphs {T1, T2. ... Tn.. Each subtype T, within $ adheres to specific topological rule or structural pattern that defines its global architecture. These topological rules encapsulate the macroscopic organizational principles that distin- guish one hypergraph type from another within the equivalence class. Prior to the task, the I.I.Ms is provided with the fundamental topological rules governing each hypergraph subtype in T. The model is expected to internalize these structural paradigms to facilitate accurate classification. This task emphasizes the model's ability to comprehend and differ- entiate hypergraphs based their overarching structural frameworks, rather than merely local or pairwise relationships. Accurate performance on the Macroscopic Architecture Differentiation task indicates that the LLM possesses nuanced understanding of hyper- graph topology, which is critical for applications in domains such as molecular structure analysis and protein modeling.
E.2 LOW-ORDER TASKS
In addition isomorphic tasks, our L.M4HHyergraaph Benchmark incorporates series of low- order tasks designed to enhance LLMs' understanding of fundamental hypergraph properties and the relationships between vertices. These tasks facilitate the comprehension of basic hypergraph attributes and simple connectivity patterns, which are essential for more complex structural analyses.
Hyperdge Count. This task aims to evaluate the model's ability to determine the total number of hyperedges within a given hypergraph. Given a hypergraph g = (V,E), the target is to return [E,, the cardinality of the hyperedge set E.
Vertex Count. This task assesses the model's capability to ascertain the total number of vertices in a hypergraph. Given g = {V,E), the target is to return [V], the cardinality of the vertex set V.
17

---

and Published as a conference paper at ICLR 2025
Vertex Degree. This task assesses the model's capability to count the number of hyperedges that connects a specific vertex. Given G = {V,E} and vertex v, the target is to return {e E eH|.
Vertex Connection. This task is designed to evaluate whether specific pair of vertices is directly connected by at least one hyperedge. Given 9 = {V,E} and a pair of vertices (u, the target is to determine if there exists hyperedge E & such that V e.
Connected Vertices. This task examines, given a vertex u, the model's ability to output the set of vertices directly connected to by at least one hyperedge. Formally, given g = (V,E) and a vertex u E V. the target is to output the subset W S V such that for each W, there exists hyperedge E & where E and w E c.
Disconnected Vertices. This task requires, given vertex u. the identification and output the set vertices that are not connected to u by any hyperedge. Formally, given {V, } and a vertex u E V, the target is to output the subset Z _ V where for each E Z, there does not exist any hyperedge e E E such that u E e and & e.
Shortest Path. This task aims to determine, given two vertices w and v, the minimal sequence of vertices representing the shortest path connecting them. Formally, given g {V,E} and a pair of vertices (u, v), the target is to find the shortest sequence (1, 12. Un] such that
U1, = Un: and for each consecutive pair (w,, 1++1), there exists a hyperedge E & containing both o and ti+1-
Reachability Check. This task assesses whether one vertex can be reached from another through sequence of hyperedges. Formally, given G {V.E) E} and pair (u, v), the target is to determine if there exists a sequence of hyperedges 61, c Ck E E that connects u
to
These low-order tasks collectively ensure that LLMs develop a robust understanding of basic hyper- graph properties and simple relational structures. By accurately performing tasks such as counting hyperedges and vertices, determining direct and indirect connections, and assessing reachability, models build a solid foundation for tackling more complex hypergraph-related challenges. The in- clusion of these tasks within the ..yyyyrrrrrap Benchmark not only provides comprehensive assessment of model's foundational capabilities but also facilitates the identification of specific areas requiring further enhancement, thereby contributing to the advancement of hypergraph com- putational intelligence.
E.3 HIGH-ORDER TASKS
Building upon the foundation of low-order tasks, our LLM4Hypeggapph Benchmark introduces series of high-order tasks tailored assess LLMs' comprehension of complex correlations between vertex sets within hypergraphs. Unlike low-order tasks that focus individual vertices and hy- peredges, high-order tasks evaluate the model's ability to understand and manipulate relationships involving groups of vertices and their interactions through hyperedges.
Hyperedge Degree. This task aims to determine the degree of a given hyperedge, which is defined as the number of vertices it encompasses. Formally, given a = (V,8) and hyperedge
E, the target is to compute deg(e) {u E V E
Vertex Set Connection. This task evaluates whether two distinet sets of vertices A and B C V are jointly contained within at least one hyperedge, thereby determining if A and B are connected through common hyperedge. Formally, given G (V,E) and two vertex subsets A, B C V, the target is to ascertain whether there exists hyperedge e E such that AUB
Vertex- Serre--St-inn-yypered of vertices S C V is entirely contained within any hyperedge of the hypergraph. Formally, given G = (V,E) and vertex subset S C V, the target to evaluate if there exists hyperedge e = E such that S Ce.
Check. This task involves determining whether specific subset
Hyperedge- in- Hyypereddg Check. This task assesses whether one hyperedge is completely contained within another, thereby identifying hierarchical or nested structures within the
18

---

Published as a conference paper at ICLR 2025
hypergraph. Formally, given 9 {V,E) and two hyperedges c1, 02 &, the target is to determine if e1 e2.
Shared-Veriie Vertices between Hyperedges. This task requires the model to identify and output the of vertices shared between any two given hyperedges, thus revealing the overlapping structures and potential intersections within the hypergraph. Formally, given g = =V,E] and two hyperedges e1, e2 E E, the target is return S e1 n e2, where S C V.
Collectively, these high-order tasks compel LLMs to engage in more sophisticated relational reason- ing and structural analysis, enabling a deeper and more comprehensive understanding of hypergraph architectures. By mastering these tasks, models can better handle complex scenarios encountered in real-world applications such molecular chemistry, social network analysis, and biological sys- tems, where understanding intricate multi-way relationships is paramount. The inclusion of high- order tasks within the Lerggape Benchmark thus ensures a thorough evaluation of an LLM's ability to navigate and interpret the multifaceted connectivity inherent in hypergraph data structures, promoting advancements in hypergraph computational intelligence.
E.4 COMPARISON WITH OTHER BENCHMARKS
In this subsection, we compare our ILMAEypergraph Benchmark with existing graph bench- marks, categorizing them into two main types: purely synthetic graph structure benchmarks and real-world graph structure benchmarks. Prominent examples of purely synthetic benchmarks in- clude NI.Graph Wang al. (024) and CLEAR Chen al. (2024), while real-world benchmarks encompass @PP44Grph/Guus Guo et al. (023) and GraphArena Tang et al. (024). These existing bench- marks predominantly focus on tasks that assess the understanding of local, low-order structural properties within graphs. In contrast, our LLM4Hypergraph Benchmark not only includes low- order structural understanding tasks but also introduces high-order tasks specifically designed to evaluate models' comprehension of associations between sets of vertices. This dual focus enables a more comprehensive exploration of LLMs' ability to grasp complex multi-way relationships in- herent in hypergraphs. Moreover, our benchmark uniquely incorporates isomorphic tasks, marking the first instance of such an inclusion in this domain. Isomorphic tasks serve to assess the models' proficiency in understanding and discerning global structural properties of graphs and hypergraphs, thereby providing a more holistic evaluation of their structural comprehension capabilities. Addi- tionally, our benchmark integrates both synthetic hypergraph data and real-world hypergraph data, ensuring a diverse and representative dataset that mirrors the complexities found in practices.
By encompassing both low-order and high-order tasks, along with the novel isomorphic tasks, LLM4 Hypergraph Benchmark extends beyond the scope of existing benchmarks. It not only evaluates foundational structural understanding but also delves into advanced relational reasoning and global structural interpretation. This comprehensive approach facilitates a thorough assessment of LLMs' abilities to comprehend and process hypergraph structures, thereby advancing the field of hypergraph computational intelligence. Consequently, our benchmark provides a robust framework for identifying both the strengths and limitations of current models, guiding future improvements in model architecture and training methodologies.
F DETAILS OF PROMPT FRAMEWORK
The overall prompt framework tailored for hypergraph structures illustrated Figure 3 A com- plete prompt comprises six components: Example, Hypergraph Description, Hyper-BAG, Question, Tail, and Hyper-COT. The Example section includes question-answer (QA) pairs for each hyper- graph and may additionally contain -OT-for-Answer. which provides standard chain-of-thouge (CoT) explanation detailing the step-by-step reasoning process to derive the answer. In the depicted figure, certain modules within the prompt enclosed in brackets "["", indicating their optional na- ture depending on the specific prompt configuration employed. We introduce a set of distinct prompt configurations as follows:
ZERO-SHOT: This configuration includes only the Hypergraph Description, Question, and Tail sections, providing the model with the essential information required to address the query without any illustrative examples or additional reasoning prompts.
19

---

Published as a conference paper at ICLR 2025
HERO-HYPER-CO Building upon the Zero-Shot setup, this configuration incorporates the Hyper- COT component after the Tail, introducing a nypergraph-specitte chain-of- thought prompt that facilitates structured reasoning tailored to hypergraph-rclated tasks.
NEW-SHOT: Extending the Zero-Shot approach, the Few-Shot configuration precedes the main prompt with Example content. These examples consist solely of Hypergraph De- scription, Question, Tail, and Answer, thereby providing the model with concrete instances to guide its understanding and response generation.
COT: Enhancing the Few-Shot configuration, the CoT setup adds COI-for-Answer to each example within the Example section. This addition entails detailed explanations of how each answer is systematically derived, enabling the model to follow a logical reasoning pathway for more accurate and transparent responses.
COT-HYPER-BAG:
This advanced configuration builds upon the CoT setup by inserting the Bypee-BAGG component as a transitional sentence between the Hypergraph Description and the Question. The Hyper-BAC serves contextualize the model's focus on hyper- graph construction and comprehension, thereby guiding it into the appropriate analytical framework for handling hypergraph-specific queries.
By integrating these varied prompt structures, the proposed framework effectively leverages ex- isting prompting strategies as Chain-of-Thougle and Few-Shot Prompting-whine introduc- ing hypergraph-speciif enhancements. This comprehensive prompt architecture ensures that large language models are adequately guided through diverse hypergraph scenarios, encompassing both synthetic and real-world complexities. Consequently, the framework optimizes the models' inter- pretative and reasoning capabilities, facilitating more precise and nuanced evaluation of their hy- pergraph comprehension within the LLMAHypergrage
Benchmark. The deliberate inclusion of optional modules allows for flexible prompt configurations tailored to different evaluation require- ments, thereby enhancing the robustness and versatility of the benchmarking process.
G DETAILS OF HYPERGRAPH LANGUAGE
Unlike traditional graphs, where an edge connects exactly two vertices, hypergraphs allow hyper- edges to connect any number of vertices, thereby necessitating more intricate textual descriptions. However, directly employing abstract language to describe high-order associative structures in hy- pergraphs can impede LLMs' comprehension hypergraph architectures, subsequently diminishing performance downstream tasks. Conversely, utilizing language that describes low-order struc- tures facilitates better understanding by LLMs but may result in the loss of essential high-order information. Inspired by graph description languages, have designed two distinct types of lan- guages for describing hypergraph structures: Low-Order Structure Language and High-Order Struc- ture Language, shown in Figure 4 The former primarily adopts a graph-like approach, leverag- ing low-order structural descriptions to represent hypergraphs by focusing on pairwise relationships and individual connections. This method enhances LLMs' ability parse and interpret the hy- pergraph by simplifying its representation into more familiar graph terminology. In contrast, the High-Order Structure Language directly conveys the complex, multi-vertex correlations inherent in hypergraphs, encapsulating high-order relational information without reducing them to mere pair- wise interactions. This approach preserves the richness of hypergraph structures, allowing L.MMs to grasp the full extent of multi-way relationships that define hypergraph topology. By employing these two complementary descriptive languages, our framework ensures that LLMS can effectively balance the simplicity of low-order descriptions with the comprehensive detail of high-order struc- tures, thereby optimizing their ability to understand and perform accurately on hypergraph-related tasks within the LLM4 HaMM4Hyprgggagg Benchmark.
G.1 LOW-ORDER STRUCTURE LANGUAGE
To effectively facilitate LLMs' understanding of hypergraph structures through pairwise correla- tions, we introduce three distinct low-order structure languages as follows: Low-Order Incidence Description (LO-Inc), Neighbor-Pair Description (N-Pair), and Raw Adjacency Matrix Description (Ad)-Mat). Each method provides a unique approach to textualizing hypergraph relationships, en- hancing the models' ability to interpret and process hypergraph data.
20

---

Published as a conference paper at ICLR 2025
Low-Order-Incidewe Description (LO-Inc): This method directly describes how given vertex is connected to other vertices through hyperedges by explicitly stating the connec- tions in pairwise manner. For example, consider a hypergraph where vertex vi is con- nected to vertices 12 and Vz. The LOOIne representation would he: Vertex e is connected vertices 12 and Uz. This description clearly indicates the direct correlations involving v1, facilitating the model's understanding of its immediate connections within the hypergraph.
Neighbor- Description (N-Pair): This method focuses on enumerating all pairs of ver- tices that share hyperedge, thereby explicitly listing the connected vertex pairs within the hypergraph. Using the same hypergraph example where vertex is connected to vertices U2 and es., the N-Pair representation would be: 02), (v1, Us). This method emphasizes pairwise relationships without referencing the broader connectivity of individual vertices, providing a straightforward enumeration of connected pairs.
Raw Adjacency Matrix Description (Adj-Mat): This method utilizes an adjacency matrix to represent the hypergraph structure numerically. In this matrix- approach, the presence or absence of a connection between any two vertices is indicated by binary values. For the hypergraph where vertex 01 is connected to vertices 122 and it the Adj-Mat representation would be: [[o, 1, 0], [1, 0, 1, 1], [1, 1, O, 0], [o, 1, 0, Oj]. In this adjacency matrix, each row and column corresponds to a vertex (0) to 04). A value of '1' at position (i,j) indicates that vertex oy is connected to vertex vy via hyperedge, while a "0" signifies no direct connection. For instance, the entry at (1, 2) is '1', indicating a connection between 0j and
V2-
These low-order structure languages-LLO-Te N-Pair, and Adj-Mat-providee varied methods for representing hypergraph structures through pairwise correlations. 1.0IInc offers descriptive clar- ity by outlining direct vertex connections, N-Pair emphasizes the enumeration of connected vertex pairs, and Adj-Mat delivers a comprehensive numerical representation through an adjacency matrix. By employing these diverse descriptive techniques, our framework enhances LLMs' ability to accu- rately interpret and analyze the fundamental properties and local relationships within hypergraphs, thereby supporting robust performance on subsequent high-order and isomorphic tasks within the LLM4Hyyprgrapph Benchmark.
G.2 HIGH-ORDER STRUCTURE LANGUAGE
To further enhance LLMs' comprehension of hypergraph structures through higher-order correla- tions, introduce four distinct high-order structure languages follows: High-Order Order Neighbor Description (HO-Neigh), High-Order Incidence Description (HO-Inc), Neighbor-Se Description (N-Set), and Raw Incidence Matrix Description (Inc-Mat).
High-Order Neighbor Description (HO-Neigh): This method leverages the neighbor defi- nitions from HGNN describing hypergraph relationships in a two-stage manner by first detailing the connections between vertices and hyperedges, and subsequently outlining the connections between hyperedges and their constituent vertices. For instance, may state, "Vertex e1 is connected to hyperedge e1", ", followed by "Hyperedge en is connected to ver- tices vi, U2, and V3", , thereby providing a comprehensive view of the local neighborhood structure.
High-Ordes Incidence Description (HO-Inc): This method extends the LO-Inc by incorpo- rating higher-orde correlations between vertices. An example of HO-Ine would be, "Ver- tex di connected vertices U2 and v3 with hyperedge e1 ". which succinetly captures the multi-vertex association facilitated by a single hyperedge.
Neighbor-Set Description (N-Ser): This method builds upon the N-Pair by enumerating entire sets of vertices connected by each hyperedge, thus providing a more holistic rep- resentation of the hypergraph's 's connectivity. For example, it may list, "(r1, U2, v3)" and "(u2, va)", explicitly indicating the groups of vertices that jointly form hyperedges.
Raw Incidence Matrix Description (Inc-Mat): This method employs an incidence matrix to numerically represent the hypergraph structure, where each entry indicates the presence or absence of a connection between vertices and hyperedges. An example of an incidence matrix is [11, 0), [1, 1), (1, O), (0, 1]]. In this matrix, rows correspond vertices (u) to v4)
21

---

Published as a conference paper at ICLR 2025
and columns correspond to hyperedges (e1 and e2), where value of 1 denotes the inclusion a vertex in hyperedge and denotes absence.
Collectively, these high-order structure languages (HO-Neigh, HO-Ine, N-Set, and Inc-Mat) pro- vide varied and sophisticated methods for representing hypergraph structures through multi-vertex associations. By utilizing these descriptive techniques, our framework facilitates deeper and more nuanced understanding of hypergraph topologies, therehy supporting advanced analytical capabili- ties in subsequent high-order and isomorphic tasks within the LLM4Hypergraph Benchmark.
H DETAILS OF SPECIFICAL PROMPTING FOR HYPERGRAPHS
Given that hypergraphs do not naturally lend themselves to description using conventional natural language constructs, we introduce two specialized instruction-based prompting techniques designed to enhance LLMs' ability to comprehend hypergraph structures: Hyper-BAt BAG and Hyper-COT.
Build-a-Hyln Hyyeergapp Prompting (Hyper-BAG) addresses the inherent complexity of hyper- graphs by facilitating a mental visualization of their structures (Wang et al. 2024). Recog- nizing that certain aspects of hypergraph comprehension are more effectively understood through visualization, Jyper-BAG employs instruction-based enhancements that explicitly guide LLMs to imagine the hypergraph's 's architecture. This approach provides a concep- tual buffer, allowing the model to assimilate hypergraph information by mapping it into structured conceptual space. For instance, an instruction might prompt the model to "imag- ine hypergraph where vertex U1 is connected to hyperedge 61," thereby aiding the model in forming a coherent mental representation that better prepares it for subsequent queries related to the hypergraph.
Chain-of-Thoughl for Hypergraphs (Hyper-COT) builds upon the traditional CoT prompt- ing methodology (Wei al. 2022)) (202) to address the observed difficulties that LLMs encounter in understanding hypergraph structures. Inspired by the step-by-ster reasoning inherent in COT, Hyper-COT integrates a tailored reasoning process specifically designed for hyper- graphs. By appending "step-by-step thinking" instructions, Hyper-COT encourages the model to decompose complex hypergraph-related tasks into manageable inference steps, thereby enhancing its comprehension in zero-shot scenarios. Through our experiments, we identified four hypergraph-friendly prompts that effectively guide the model's reasoning process.
vl: "Let's think step by step. Make sure the data is calculated and recorded accurately at each step."
v2: "Let's analyze the connectivity by considering hyperedges linked to vertices and vertices linked through hyperedges."
v3: "Let's think hyperedges connected by vertices then vertices connected by hyper- ed edges."
-
These prompts are strategically designed to align the model's reasoning with the multi-way relationships characteristic of hypergraphs, thereby facilitating a deeper and more accurate understanding of hypergraph connectivity and structure.
By implementing Hyper- Hyper-BAG BAG and Hyper-COT within our prompting framework, we aim to signif- icantly bolster the I.LMs' proficiency in interpreting and processing hypergraph structures. These instruction-basse techniques address the unique challenges posed by hypergraphs' multi-vertex as- sociations, ensuring that models can effectively navigate both low-order and high-order structural information. Consequently, these strategies play crucial role in advancing the capabilities of LLMs within the LLM Hypergraph Benchmark, promoting more accurate and sophisticated analyses of hypergraph data.
22

---

Published as a conference paper at ICLR 2025
1 PROMPT EXAMPLES
1.1 EXAMPLES HYPERGRAPH LANGUAGES
11111 LOW-ORDER STRUCTURE LANGUAGES
LO-Inn
Prompt: G describes a hypergraph among verlices vO, vl, v2, v3, v4, and v5 and hyperedges e0, el, e2, and e3. In this hypergraph:
Vertex v0 connected vertices vl, 12, v3, 14, v5.
Vertex vI is connected to vertices v0, v2, v3, 14, v5.
Vertex v2 is connected to vertices v0, vl, v3, 14, v5.
Vertex v3 is connected to vertices v0, vl, v2, 14, v5.
Vertex v4 is connected to vertices v0, vl, v2, v3, v5.
Vertex v5 is connected vertices vO, vl, v2, v3, v4.
N-Pair
In undirected hypergraph, (i.j) means that vertex i and vertex are connected with an undirected hyperedge. describes a hypergraph among vertices vO, vl, v2, v3, v4, and v5 and hyperedges e0, el, e2, and e3. The connection relation between vertices in G are: (v0, v1) (v2, v4) (vl, v2) (vO, v4) (v3, v4) (vl. v5) (vO, v3) (vl, v4) (v2, v3) (vO, v2) (v4, v5) (v0, v5) (v2, v5) (vl, v3) (v3, v5).
Prompt:
Adj-Mat
Prompt: G describes hypergraph among vertices v0, vl, v2, v3, v4, and v5 and among hyperedges e0, el, e2, and e3.
The adjacency matrix between vertices of the hypergraph is [II.I,I,,IIII, II,IIIII,IIIJ. [1.11,1,1,I.,
1.1.1
1.1.2 HIGH-ORDER STRUCTURE LANGUAGES
HO-Neigh
Prompt: G describes a hypergraph among vertices v0, vl, v2, v3, v4, and v5 and hyperedges
e0, el, e2, and e3. In this hypergraph:
Vertex v0 is connected hyperedges el, c2.
Vertex vI is connected to hyperedges e0, el,e3.
Vertex v2 connected hyperedges e0, el.
Vertex v3 is connected to hyperedges e0, el.
Vertex v4 connected hyperedges e0, el, e2. Vertex v5 is connected to hyperedges el, e3.
Hyperedge e0 connected to vertices vI, v2, v3, v4. Hyperedge el is connected to vertices v0, vl, v2, v3, v4, v5. Hyperedge e2 connected vertices v0, 14.
Hyperedge e3 is connected vertices vl. v5.
23

---

Published as a conference paper at ICLR 2025
HO-Ine
Prompt: G describes hypergraph among vertices vO, vl, v2, v3, v4, and v5 and among hyperedges e0, el, e2, and e3.
In this hypergraph:
Vertex v0 connected to vertices vl, v2, v3, v4, with hyperedge el, to vertex v4 with hyperedge e2.
Vertex vl is connected to vertices v2, v3, v4 with hyperedge e0, to vertices vO, v2, v3, v4, v5 with hyperedge el, to vertex v5 with hyperedge e3.
Vertex v2 is connected to vertices vl, v3, 14 with hyperedge e0, to vertices vO, vl, v3, v4, v5 with hyperedge el.
Vertex v3 is connected to vertices vl, v2, v4 with hyperedge e0, to vertices vO, vl, v2, v4, v5 with hyperedge el.
Vertex v4 is connected to vertices vl, v2, v3 with hyperedge e0, to vertices vO, vl, v2, v3, v5 with hyperedge el, to vertex with hyperedge e2. Vertex v5 is connected to vertices vO, vl, v2, v3, v4 with hyperedge el, to vertex vl with hyperedge e3.
N-Set
In an undirected hypergraph, ji k) means that vertex vertex and vertex k are connected with an undirected hyperedge. G describes hypergraph among vertices vO, vl, v2, v3, v4, and v5, and among hyperedges e0, el, e2, and e3. The hyperedges in G are: (vl, v2, v3, v4), (v0, vl, v2, v3, v4, v5), (vO, v4), (vl, v5).
Prompt:
Inc-Mat
Prompt: G describes hypergraph among vertices v0, vl, v2, v3, v4, and v5 and hyperedges e0, el, e2, and e3.
The incidence matrix of the hypergraph is
110.1,1,0.1 11,1,0.1,1.
[1,1,0,0.].
[1,1,0,0.].
11,1,
10,1,0,1.11
1.2
EXAMPLES OF QUESTION FOR DIFFERENT TASKS
1.2.1
LOW-ORDER TASKS
Hyperedge Count
Prompt:
How many hyperedges are in this hypergraph? List the answers after "Ans:" in the format like [10].
Vertex Count
How many vertices are in this hypergraph? List the answers after "Ans:" " in the format like [10].
Prompt:
24

---

Published as a conference paper at ICLR 2025
Vertex Degree
What is the degree of vertex v14? List the answers after "Ans:" in the format like [10].
Prompt:
Vertex Connection Check
Prompt: Is vertex v14 connected to vertex v3? List the answers after "Ans:" in the format of [Yes, No.
Reachability Check
there path from node vO to node vl? List the answers after "Ans:" in the format of [Yes, No.].
Prompt:
Shortest Path
Prompt:
What is the length of the shortest path from node vO node v5? List the answers after "Ans:" in the format of (Yes, No.).
Connected Vertices
List all the vertices connected to v14 in alphabetical order. List all the answers after " "Ans:" in the format of [vO, vl, v2] and separate the answers by a comma.
Prompt:
Disconnected Vertices
Prompt:
List all the vertices that are not connected v14 in alphabetical order.
List all the answers after "Ans:" in the format of [vO, vl, v2] and separate the answers by comma.
1.2.2 HIGH--ORDER TASKS
Hyperedge Degree
What is the degree of hyperedge e4? List the answers after "Ans:" " in the format like [10].
Prompt:
Vertex Set Connection Check
Prompt: there hyperedge that contain both vertex (v2, v3) and vertex set (v5, v7)? List the answers after "Ans:" in the format of [Yes, No.).
Vertex-Set-in--lyprreede Check
Prompt: there a hyperedge that contains all vertices in vertex set (v4, v16)?
List the answers after "Ans:" in the format [Yes, No.].
25

---

Published as a conference paper at ICLR 2025
Hlyeeredgeinn--yypereeeg Check
Prompt:
Whether any hyperedge in the hypergraph contained by other hyperedges? List the answers after "Ans:" in the format [Yes, No.].
Shared- Vertices between Hyperedges
Prompt: List the vertices connected to both hyperedge e3 and hyperedge e2 in alphabetical order.
List all the answers after "Ans:" in the format of [v0, vl, v2] and separate the answers by a comma.
1,2.3
ISOMORPHISM TASKS
Isomorphism Recognition
Are these two hypergraphs isomorphism? List the answers after "Ans:" in the format of [Yes, No.
Prompt:
Structure Classification
What is the shape of the visualization of the hypergraph like? Please directly give the answer number corresponding to the 3 hypergraph visualization shapes as shown below. Answer [0] corresponds the Hyper Pyramid, which represents the visualization of the hypergraph as a Pyramid.
Prompt:
Answer [1] corresponds to the Hyper Checked Table. Answer [2] corresponds to the Hyper Wheel.
List the answer after "Ans:" in the format like [2].
1.3
EXAMPLES OF PROMPTS UNDER DIFFERENT SETTINGS
ZERO SHOT
In an undirected hypergraph, (i. j. k) means that vertex i, vertex j, and vertex k are connected with an undirected hyperedge. G describes a hypergraph among vertices vO, vl, v2, v3, v4, and v5 and among hyperedges e0, el, e2, and e3.
Prompt:
The hyperedges in are: (vl, v2. v3, v4), (vO, vl, v2, v3, v4, v5), (vO, v4), (vl, v5).
Let's 's construct the hypergraph with the vertices and hyperedges first.
Q: How many hyperedges are in this hypergraph? list the answers after "Ans:" " in the format
like [10].
A:
Response: Ans:/4]
Ground Truth: Ans:(4)
26

---

Published as a conference paper at ICLR 2025
ZERO-HYPER-COT
In an undirected hypergraph, (i. j. k) means that vertex vertex and vertex k are connected with an undirected hyperedge. G describes a hypergraph among vertices vO, vl, v2, v3, y4, and v5 and among hyperedges e0, el, e2, and e3. The hyperedges in are: (vl, v2, v3, v4), (v0, vI, v2, v3, v4, v5), (v0, v4), (vl, v5).
Prompt:
Let's 's construct the hypergraph with the vertices and hyperedges first.
Q: How many hyperedges are in this hypergraph? list the answers after "Ans:" in the format
like [10].
A: Let's think hyperedges connected by vertices then vertices connected by hyperedges.
Response: To determine the number of hyperedges in the given hypergraph G, need to count each unique hyperedge listed.
Given hyperedges:
1. (vl, v2, v3, v4)
2. (v0, vl, v2, v3, v4, v5)
3. (vO, v4)
4. (vl, v5)
Let's count these:
1. [vl,, v2, v3, v4) This one hyperedge connecting vertices vl, v2, v3, and v4.
2. (vO, vl. v2, v3. v4, v5)- This is another hyperedge connecting vertices vO, vl, v2, v3, v4, and v5.
3. (vO, v4) This is a third hyperedge connecting vertices vO and v4. 4. (vl, v5) This is a fourth hyperedge connecting vertices and v5.
So, there are four distinct hyperedges listed.
Ans: [4]
Ground Truth: Ans:[4]
FEW SHOT
Prompt: Example: In an undirected hypergraph, (i, j. k) means that vertex i, vertex and vertex k are connected with an undirected hyperedge. G describes a hypergraph among vertices v0, vl, v2, v3, v4, v5, v6, v7, v8, v9, v10, vl1, v12, v13, v14, v15, v16, and v17 and among hyperedges e0, el, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11, e12, e13, e14, e15, e16, e17, e18, and e19.
G are: (v8, v16, v17), (v/1, v/4, v17), (v4, v15), (vl, v6, v15, v17), (vO, v)1), (v2, vl4), (v6, vll), (v3, v9, v15), (v5, 19),(v9, v10), (v7, v8, v15), (v0, v10), (vl, vl1), (v7. v9), (v15, v16), (v9, vll, v12), (v4, v13), (v9, v12), (v2, v12), (v7, v14).
The hyperedges
Q: How many hyperedges are in this hypergraph? list the answers after "Ans:" in the format
like [10].
A: Ans:/20].
In an undirected hypergraph, (i. j. k) means that vertex i, vertex and vertex are connected with an undirected hyperedge. G describes a hypergraph among vertices vO, vl, v2, v3, v4. and v5 and among hyperedges e0, el, e2, and e3.
The hyperedges in G are: (vl, v2, v3, v4), (v0, vl. v2, v3, v4, v5), (vO, v4), (vl, v5).
Q: How many hyperedges are in this hypergraph? list the answers after "Ans" the format
like [10].
A:
Response: Ans:/4]
Ground Truth: Ans:(4)
27

---

Published as a conference paper at ICLR 2025
COT
Prompt: Example: In an undirected hypergraph, (i, j. k) means that vertex i, vertex and vertex are connected with an undirected hyperedge. G describes a hypergraph among vertices vO, vl, v2, v3, v4, v5, v6, v7, v8, v9, v10, vI1, v12, v13, v14, v15, v16, and v17 and among hyperedges e0, el, e2, e3, e4, e5, e6, e7, e8, e9, e10, el1, e12, e13, e14, e15, el6, e17, e18, and e19.
G are: (v8, v16, v17), (vl1, v14, v17), (v4, v15). (vl, v6, v15, v17), (vO, vI1), (v2, v14), (v6, vI1), (v3, v9, v15), (v5, 19), (v9, v10), fv7, v8, v/5), (vO, v10), (vl, v!I), (v7, 19), (v15, v16), (v9, vII, v/2), (v4, v13), (v9, v/2), (v2, v12), (v7, v14).
The hyperedges
Q: How many hyperedges are in this hypergraph? list the answers after "Ans:" in the format
like [10].
A: Ans:/20]. The hyperedges are e0, el, e2, e3, e4, e5, e6, e7, e8. e9, e10, ell, e12, e13,
e14, e15, e16, el7, e18, and e19.
In undirected hypergraph, (i, j. k) means that veriex i, veriex and vertex k are connected with an undirected hyperedge. G describes a hypergraph among vertices vO, vl, v2, v3, v4, and v5 and among hyperedges e0, el, e2, and e3. The hyperedges in are: (vl, v2, v3, v4), (v0, vl, v2, v3, v4, v5), (vO, v4), (vl, v5).
Q: How many hyperedges are in this hypergraph? list the answers after "Ans" in the format like [10].
A:
Response: Ans:[4]. The hyperedges are e0, el, e2, e3.
Ground Truth: Ans:[4]
COTHHPPER BAG BAG
Example: In an undirected hypergraph, (i. j. k) means that vertex i, vertex and vertex are connected with an undirected hyperedge. G describes a hypergraph among vertices v0, vl, v2, v3, v4, v5, v6, v7, v8, v9, v10, vl1, v12, v13, v14, v15, v16, and v17 and among hyperedges e0, el, e2, e3, e4, e5, e7, e8, e9, e10, el1, e12, e13, e14, e15, e16, e17, e18, and e19.
Prompt:
G are: (v8, v16, v17), (v11, v/4, v17), (v4, v15), (vl, v6, v15, v17), (vO, v)1), (v2, v14), (v6, vl1), (v3, v9, v15), (v5, v9), (v9, v10), (v7, v8, v15), (v0, v10), (vl, vlI), (v7. v9), (v15, v16), (v9, vl1, v12), (v4, v13). (v9, v12), (v2, v12), (v7, v14).
The hyperedges
Let's construct the hypergraph with the vertices and hyperedges first.
Q: How many hyperedges are in this hypergraph? list the answers after "Ans:" " in the format
like [10].
A: Ans:[20]. The hyperedges are e0, el, e2, e3, e4, e5, e6, e7, e8, e9, el0, el1, e12, e13,
e14, e15, e16, e17, e18, and e19.
In an undirected hypergraph. (i, j. k) means that vertex i, vertex and vertex are connected with an undirected hyperedge. G describes a hypergraph among vertices vO, vl, v2, v3, v4. and v5 and among hyperedges e0, el, e2, and e3.
The hyperedges in G are: (vl, v2, v3, v4), (v0, vl, v2, v3, v4, v5), (v0, v4), (vl, v5).
Let's construct the hypergraph with the vertices and hyperedges first.
Q: How many hyperedges are in this hypergraph? list the answers after "Ans" in the format
like [10].
A:
Response: Ans:[4]. The hyperedges are c0, el, e2, e3.
Ground Truth: Ans:[4]
28


Reviews:
[{"review_id": "eM2xRic7kh", "reviewer": "Reviewer_vz6R", "summary": "The paper introduces LLM4Hypergraph, a benchmark designed to evaluate large language models' (LLMs) understanding of hypergraphs, which can capture complex, multi-way relationships beyond pairwise correlations found in traditional graphs. The benchmark includes 21,500 problems across low-order, high-order, and isomorphism tasks using both synthetic and real-world hypergraphs. The study evaluates six prominent LLMs and introduces novel prompting techniques to enhance LLMs' performance on hypergraph tasks.", "questions": "How do the prompting techniques generalize to other complex data structures beyond hypergraphs?\nCould the authors elaborate on the potential scalability issues of the prompting techniques with increasingly large and complex hypergraphs?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Originality: The paper proposes a new benchmark and prompting techniques tailored for hypergraphs, addressing a gap in the assessment of LLMs' capabilities.\nQuality: The benchmark is comprehensive, covering a wide range of tasks and hypergraph types, which strengthens the validity of the findings.\nClarity: The paper is well-organized, with clear explanations of the hypergraph languages and prompting frameworks.\nSignificance: The work is significant as it pushes the boundaries of LLMs' understanding of complex data structures, which has implications for various real-world applications.", "weaknesses": "The paper could benefit from a deeper analysis of the limitations of the current LLMs in handling hypergraphs, beyond performance metrics.\nWhile the benchmark is comprehensive, it may lack diversity in terms of the types of real-world hypergraphs used, which could affect the generalizability of the findings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mcRa2bkv58", "reviewer": "Reviewer_d74r", "summary": "The paper provided a new benchmark to evaluate the LLM's ability to understand hypergraphs and developed a new prompting framework to improve the hypergraph comprehension. The prompting framework demonstrated that CoT and BAG, adapted to hypergraphs, can improve the LLM's performance on hypergraph tasks, especially for high-order tasks such as Vertex Set Connection Checks and Vertex-Set--in-Hypergraph Checks using synthetic hypergraphs.", "questions": "1. Why is prompting a promising research direction for hypergraph understanding in light of other techniques such as function calling?\n2. What are the empirical graphs used in the experiments? What are the selection criteria?\n3.  Some tasks involve computing tasks whose answers are numbers. How does the accuracy is computed for these tasks? Is it an exact match? Or allow some error under a certain threshold?\n4. Does the BAG and CoT outperform beyond statistical variations attributed to the variations of individual graph data and stochatic behaviors of LLMs?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The paper is easy to read and the experiments are comprehensive and thorough.", "weaknesses": "**Main arguments**:\n1. The paper adapts existing benchmarks and prompting techniques for hypergraphs. While the results offer some insights into the extent to which LLMs understand hypergraphs, they largely mirror findings for simple graphs---specifically, that CoT and BAG can enhance LLM performance. The only notable point is that using suitable language to describe hypergraphs can aid LLM comprehension, which is novel but trivial.\nGiven that the proposed techniques are naive adaptations of existing techniques and new insights specific to hypergraphs are not found, the contribution of the paper is incremental and not significant.\n2. The paper lays out a main motivation by the underexploration of (i) investigating the LLM's ability to understand hypergraphs and (ii) developing prompting framework for hypergraph understanding and argue that they are promising research directions. This is not a strong motivation, i.e.,  \"underexploration\" alone does not justify the promising research directions. More specific question is: why is prompting a promissing research direction for hypergraph understanding in light of other techniques such as function calling?\n3. Unsupported claim 1: In abstract, ``our specialized prompting framework incorporates seven hypergraph languages and introduces two novel techniques, Hyper-BAG and Hyper-COT, which enhance high-order reasoning and achieve an average 4% (up to 9%) performance improvement on structure classification tasks.'' This is not sufficiently supported by the empirical results. The performance improvement for Hyper-COT is 4\\% on average. However, for the Hyper-BAG, it is 2\\% for low-order hypergraphs and 2.8\\% for high-order hypergraphs.\n\n**Minor arguments**:\n1. Give the stochastic nature of the LLMs and the graph data, it is crucial to report the variation of the results across different runs (e.g., confidence intervals, standard deviations), given the performance gain of the proposed prompting techniques (Hyper-BAG and Hyper-COT) is slim.\n2. Unsupported claim 2: The paper claimed in the supporting information (B.4) that the benchmark represents the first instance that includes isomorphism checks. This is not precise. Isomorphism checks are a special case of Maximum Common Subgraph (MCS) problem, which is included in the existing benchmark cited in the paper (GraphArena Tang et al. (2024)). The author used \"in this domain\" to limit the scope of their claim, and it is crucial to spell out the \"domain\" (e.g., general graphs, or hypergraphs specifically) to be more precise.\n3. The paper did not provide descriptions about real-world graphs used in the experiments and their selection criteria.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DKs49rhgwr", "reviewer": "Reviewer_rA8g", "summary": "This paper introduces LLM4Hypergraph, the first benchmark aimed at evaluating the ability of LLMs to understand hypergraph data. The authors design a series of tasks of varying difficulty levels and evaluate six different LLMs. Then, they identify their strengths and weaknesses. While this work represents a first step and provides a comprehensive study, there are several areas where improvement is needed.", "questions": "- How does the performance of LLMs depend on the hypergraph domains (e.g., emails, coauthorship)?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper proposes the first benchmark for evaluating LLMs on hypergraphs.\n- The authors thoroughly address questions about hypergraphs.\n- The problems are well-structured and clearly categorized according to their objectives.\n- The code is released for reproducibility.", "weaknesses": "- The motivations for this research are not sufficiently discussed. Why is it important to enable LLMs to understand hypergraph structures? Are there potential practical use cases? Are there any motivations beyond the fact that similar research has been done with graphs?\n- The datasets used in the study are not comprehensive. To be specific:\n  - The definition of \"hypergraph size\" is unclear. Is it referring to the number of nodes, the number of hyperedges, or the sum of hyperedge sizes?\n  - The specific sizes of the hypergraphs (both real-world and synthetic) are not mentioned in the main content. How large are the synthetic hypergraphs used for evaluation?\n  - According to the appendix, even the so-called \"large-scale hypergraphs\" only contain 15 to 20 vertices, which is too small to meaningfully capture higher-order structures typically expected in hypergraphs.\n  - The synthetic hypergraphs are not sufficiently representative. There are other synthetic hypergraph models (e.g., configuration models) available.\n  - It is unclear how the random walk approach for sampling sub-hypergraphs from real-world hypergraphs (Appendix A.2) ensures that the sampled hypergraphs \"retain the intricate and authentic correlations inherent in the original data.\"\n- The definition of task \"difficulty\" is unclear.\n- The authors may consider discussing/citing the recent work \"When LLM Meets Hypergraph: A Sociological Analysis on Personality via Online Social Networks\" (CIKM 2024) in the related work.\n\n**In summary**, this paper makes a valuable contribution to LLMs and hypergraph analysis. However, the benchmark datasets lack comprehensiveness and have room to consider additional synthetic hypergraph generators. Also, the paper lacks detailed statistics on real-world hypergraphs. Scalability is also a concern; if large-scale hypergraph handling poses challenges for LLMs, these limitations should be clearly discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)