How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension
Authors: Xinnan Dai
Haohao Qu
Yifei Shen
Bohang Zhang
Qihao Wen
Wenqi Fan
Dongsheng Li
Jiliang Tang
Caihua Shan
Venue: ICLR 2025 Poster (2025)
Keywords: Large language models
graph pattern
graph mining
Primary area: datasets and benchmarks
TL;DR: We propose a comprehensive benchmark to assess LLMs' capabilities in graph pattern tasks.

Abstract: Benchmarking the capabilities and limitations of large language models (LLMs) in graph-related tasks is becoming an increasingly popular and crucial area of research. Recent studies have shown that LLMs exhibit a preliminary ability to understand graph structures and node features. However, the potential of LLMs in graph pattern mining remains largely unexplored. This is a key component in fields such as computational chemistry, biology, and social network analysis. To bridge this gap, this work introduces a comprehensive benchmark to assess LLMs' capabilities in graph pattern tasks. We have developed a benchmark that evaluates whether LLMs can understand graph patterns based on either terminological or topological descriptions. Additionally, our benchmark tests the LLMs' capacity to autonomously discover graph patterns from data. The benchmark encompasses both synthetic and real datasets, and a variety of models, with a total of 11 tasks and 7 models. Our experimental framework is designed for easy expansion to accommodate new models and datasets. Our findings reveal that: (1) LLMs have preliminary abilities to understand graph patterns, with O1-mini outperforming in the majority of tasks; (2) Formatting input graph data to align with the knowledge acquired during pretraining can enhance performance; (3) LLMs employ diverse
potential algorithms to solve one task, with performance varying based on their execution capabilities.

Published as a conference paper at ICLR 2025
HoW Do LARGE LANGUAGE MODELS UNDERSTAND GRAPH PATTERNS? A BENCHMARK FOR GRAPH PAT- TERN COMPREHENSION
Xinnan Dail, Haohao Qu Wenqi Fan?, Dongsheng Li Jiliang Tang'. Caihua Shan
Yifei Shen', Bohang Zhang', Qihao Wen',
'Michigan State University, "The Hong Kong Polytechnic University.
MMicooooft Research, 'Independent Researcher (daixinna, wengihao, (zhangbohang, pku, wenqifan03 f @gmail com,
Jesuu. haohao - pol.....ppp.............. .k,
lyffeihhe, dongsheng. 1i, caihuashan www.hhaannmmmrooooo.oooooooo
ABSTRACT
Benchmarking the capabilities and limitations of large language models (LLMs) in graph-related tasks is becoming an increasingly popular and crucial area research. Recent studies have shown that LLMs exhibit preliminary ability understand graph structures and node features. However, the potential LLMs in graph pattern mining remains largely unexplored. This is key component in fields such as computational chemistry, biology, and social network analysis. To bridge this gap, this work introduces comprehensive benchmark assess LLMMs' capabilities in graph pattern tasks. We have developed a benchmark that evaluates whether LLMs can understand graph patterns based on either terminological or topological descriptions. Additionally, our benehmark tests the LLMs' capacity to autonomously discover graph patterns from data. The benchmark encompasses both synthetic and real datasets, and a variety of models, with total of 11 tasks and models. Our experimental framework designed for easy expansion accommodate new models and datasets. Our findings reveal that: (1) LLMs have preliminary abilities to understand graph patterns, with O1 O1-mini outperforming the majority of tasks; (2) Formatting input graph data align with the knowledge acquired during pretraining can enhance performance; (3) LLMs employ diverse potential algorithms solve one task, with performance varying based their execution capabilities. Our dataset and implementations are available at httpp:
INTRODUCTION
Originally trained on textual data, LLMS have demonstrated remarkable success in various tasks,
such as reading comprehension and text reasoning (Achiam et al. 2023 Touvron al. 2023)
To evaluate whether LLMs can adapt the text understanding ability across graphs, several studies
have investigated this both the feature and structural levels (Zhao et al. 2023 Chai et al. 2023).
Specifically, LLMs have been shown to enhance node features on graphs YYe et al.) 2023 Huang jet al.) 2024 Chen et al. 2024c). Additionally, graph structure understanding tasks, such as shortest path and connectivity, have also been evaluated (Guo et al. 2023 Wang et al. 2024).
Graph patterns, a key aspect of graphs, have yet to be thoroughly explored. Mining graph patterns play critical role in numerous real-world applications. For instance, they aid in uncovering new insights within biological protein-protein interaction networks (Hu et al. (0055 Tran et al. 2013), identifying key molecular structures in chemistry (Murray & Rees 2009). and detecting fraudulent activities in transaction networks (Cheng et al.) 2020), and so on. addition, these patterns rep- resent fundamental transferable structures among graphs, such community groups for friendship recommendations in social networks (Wu et al. 2022) and functional groups for molecular property
Correspondence Caihua Shan (caiuaasaan@ wicnsssnnnn@mmmmoofft...momm Jiliang Tang (tangjili @es.iedu.ssu..du....

---

Published as a conference paper at ICLR 2025
prediction (Agarwal et al. 2023) Therefore, it is of great interest investigate whether LLMs possess the capability to comprehend these patterns and effectively apply them to variety of graph mining and learning tasks.
In this work, we begin by exploring how LLMs handle various types of graph patterns and how they can be applied real-world applications. Specifically, categorize the descriptions of graph pat- terns into three types: terminology-base topology-based, and data-driven, as shown in Table Based on these descriptions, we progressively challenge LLMs' abilities in graph pattern tasks:
Table I:
Three types of descriptions. 'Square" is defined by terminology and topology to outline its structure. In data-driven description, 'Square' frequently appears as a common pattern in the data.
Terminology-bast
Topology-based
Data-driven
The pattern, defined as G, is an undirected graph with four Node
The pattern, named Square, is 4-node cycle with each node connected to exactly two others.
0, I, 2, 3. Node 0 is connected Nodes and 2. Node is connected to Nodes and 3.
Can LLMs understand graph patterns based on terminology -ased descriptions? (Section Given that LLMs are pre-trained on extensive internet datasets, which include passages relevant to graph terminologies, it is plausible to hypothesize that they possess rudimentary understanding of simple graph patterns as described in terminology, such as 'triangle' or 'diamond'. To evaluate this, have devised three subtasks aimed progressively testing L.MMs' comprehension of termi- nologically defined patterns. In detail, we first examine the alignment between LLMSs and human understanding of the same pattern, and then assess whether LLMs can follow human instructions to modify and detect these patterns.
Can LLMs understand graph patterns based topology-basee baaeed descriptions? (Section While certain graph patterns can be succinctly described using natural language, more complex pat- terns often necessitate representation through adjacency lists edge lists. As LLMs are not trained for permutation invariance, the same pattern, when described with different node ID sequences, may result varying understanding by LLMss Thus, to examine L.MMs' consistency in recognizing iden- tical patterns, we first require LLMs to perform pattern mapping through isomorphic identification. Following this, we assess their ability to edit and extract topology-basee based patterns, similar to their handling of lerminology-based patterns.
Can LLMs automatically discover graph patterns from data? (Section 5) The benchmarks previously discussed assess LLMs' comprehension of rule-based predefined graph patterns. These patterns, initially identified by human experts, represent a foundational level understanding. To further probe the depth of LLMs' capability, check their ability to independently mine graph patterns from a provided dataset. We explicitly prompt certain key information to constrain and guide the data-driven patterns, such detecting dense substructures like k-core, finding the frequent subgraphs, or identifying the distinctive patterns based on the labels of input graphs.
Can LLMs deal with graph patterns in real-world applications? (Section 6 Compared with synthetic datasets, real-world datasets contain node and edge attributes and inevitable noise within graphs, increasing the difficulty for LLMs comprehend. We gather real-world datasets across diverse domains, including molecules, social networks, bioinformatics, and computer vision, and perform similar tasks such as pattern detection, to assess their ability.
Based on the extensive experimental results from various tasks, we provide theoretical intuitions and summarize three key empirical insights on the capacity LLMs for graph patterns in Section
In conclusion, this paper provides an initial yet comprehensive study of LLMs' understanding on graph patterns, aiming to further improve performance in graph learning and mining tasks, and enhance graph reasoning skills.
2 BENCHMARK SETTINGS
Primitive graph patterns. We select 9 primitive graph patterns with varying numbers of nodes, edges and connection types, commonly used in network analysis (Cheng al.) 2008 Ying al.,
2

---

Published as a conference paper at ICLR 2025
2019 Li al. 2021p. Specifically, include 5 undirected graph patterns: triangle, tailed-triangle (r-riiaggl), square. diamond, and house. For directed graph patterns, we have V-structure (V-S), feedforward loop (FFL), feedback loop (FBL), and directed-diamone (D-diamond). The detailed definitions are illustrated in Appendix Table [1] These graph patterns serve as key examples in constructing datasets and testing L.MSs' ability in terminology-basee and topology-hased tasks.
Datasets. For comprehensive benchmarking, we consider multiple factors to construct diverse datasets. We design the terminology-base and topology-based descriptions for patterns. The topol- ogy of patterns can be represented using either the adjacency list (A.L.) or edge list (E.L.) format. Furthermore, certain tasks, such as modification and detection, require input graphs beyond the pat- terns themselves. We randomly generate varying input graph sizes: small (S) with 5-15 nodes, medium (M) with 15-25 nodes, and large (I.) with 25-35 nodes, to control the task difficulty. These input graphs are also described in either either adjacency list or edge list format. In addition to the synthetic datasets, we also utilize real-world application attributed graphs from various domains, including molecules, information networks, social networks, and computer visions. We summarize the datasets used and the prompts designed for each task in Appendix Table [
Large Language Models. Since different LLMs may have varying task performance, we evaluate several widely used models, including GPT-4 (0125-Preview), GPT-4o (2024-05-13) Mixtral (open- mixtral-8x22b), Llama (1lama3, B-0tti--ssttt,ut,, Gemini (gemini- 1.5 1.5-pro), Claude (claude-3-opus-- 20240229) and -m-mini (ol-mini-2024-09-122 We set temperatures to for all the models.
3 TERMINOLOGY-BASER PATTERNS
In this section, first introduce a pattern translation task to assess the alignment between LLMs' comprehension and human understanding of terminology-base graph patterss. Then, we design graph modification and pattern detection tasks evaluate LLMs' ability either modify the input graph to include specific patterns, or identify all patterns present in the input graph.
3.1 PATTERN TRANSLATION
We study whether LLMs have an accurate understanding of terminology- -hased patterns. Given the terminology of primitive graph pattern, we prompt L.LMs to create graph including this pattern. Besides, we also require that the resulting graph is constrained by a specified number of nodes and pattern occurrences. One prompt example is "Generate graph that includes only one triangle, with a total of 20 nodes. Each node should be connected." For evaluation, we use accuracy (ACC) to assess whether the output meets the requirement. In addition, to evaluate the creativity of LLMs, we measure diversity of generated graphs by comparing each pair to ascertain their uniqueness. The diversity score (DIV) is defined as DIV #Different pairs
# pairs
Table 2: The accuracy and diversity score for pattern translation
Undirected pattern
Directed pattern
Triangle T-Triangle Square
Diamond
House
V-S
FBI.
FH.
D- D-Diamond
ACC DIV ACC DIV ACC DIV ACC DIV
ACC
ACC DIV
ACC DIV ACC DIV
ACC
DIV
Avg. A Avg. D
Mixtral
1.00 0.00 0.00 0.00 0.00 0.00 1.00
0.25 0.00 0.00
0.00
0.00
1.00
0.11
0.02 0.00
1.00
0.04
0.45
0.04
Gemini
0.52 0.82 0.46 0.32
0.24
0.84
0.50
0.78
0.76
0.90
0.89
0.90
0.73
0.94
0.91
0.67
Claude
1.00 0.61 0.02 0.00
0.24 0.67
0.78 0.58 0.88 0.62
0.20
0.53
1.00)
0.29
0.90
0.42
0.84
0.42
0.65
0.46
Llama
1.00 0.48 0.00 0.00
0.86 0.75 1.00 0.80 0.12 0.80
0.00 0.00
1.00
0.90 0.98
0.77 1.00
0.00
0.66
0.50
GPT-4
1.00 0.12 0.35 0.75 0.98
0.33
0.92
0.76
0.86
0.42
0.80
1.00
0.98
0.43
1.00
0.54
0.83
0.53
GPT-40
0.98
0.29 0.92 0.46
0.74
0.80
0.82
0.77
0.68
0.41
0.88
0.05
1.00)
0.64
0.82
0.81
0.68
0.54
0.84
0.53
O1-mini
1.00 0.79 0.62
0.35
1.00
0.80
0.74
0.87
0.66
0.95
0.82
0.85
0.98
0.75
0.96
0.80
0.98
0.84
0.86
0.78
AVG.
0.93 0.44 0.34 0.32 0.27 0.63 0.87 0.69 0.53
0.54
0.44 0.49
0.98
0.55 0.79 0.57
0.92
0.47
0.71
0.51
We repeat experiments 50 times for each pattern and LLM, and present the results in Table 2 Most LLMs effectively understand primitive graph patterns, demonstrating their ability to translate terminology- based descriptions into graph structures. Among the models tested, O1-mini stands out with the highest ACC and DIV average. LLMs perform badly in T-triangle and V-S patterns because LLMs prefer to add one extra edge to these patterns to make them into other unintended patterns. In addition, LLMMs show biased outputs, resulting in low DIV scores for simple patterns.
3

---

Published as a conference paper at ICLR 2025
0.-
Small Vedere
F1 3ooe
0.
AL.
Al I-trinngee
AL
A1
AL
E1
EL
Ihann
e
Square
Ulemood
House
VS
1F
FUL
Ulaamondd
Figure 1: The Fl score for terminology-based pattern detection (small and medium scale)
For instance, when processing triangle patterns, GPT-4o often outputs a simple graph containing a triangle with chain.
3.2 GRAPH MODIFICATION
In graph modification, we construct a dataset of input graphs, each including a specific primitive pattern, and then prompt LLMs transform one pattern into another. Specifically, we define the following modifications: Square to House (S + H), Square to Diamond (S + D), Diamond to Square (D + S), and FFL to FBL (F + B). They contain edit operations like adding several edges, removing one edge, changing the direction of an edge. A prompt example is "Modify the input graph to include house pattern. The input graph .... The number of modified edges should be minimized."" We evaluate if LLMs modify graphs to include the target pattern by the success rate.
The results are presented Table 3 We observe that O1-mini stands out its ability to edit diverse terminology-basee patterns. Additionally, the scale of the imput graphs generally doesn't 't have major impact. This because LLMs generally prioritize high-degree nodes and their neighbors to form the pattern. In larger graphs, LLMs tend to identify more regions for potential edits. These regions are local and invariant to the graph size.
Table 3: The success rate for terminology- based graph modification
Gemnni M.
Mixtral M.
Llama M.
Claude
GPT-
GPT-4o
Ol-mini
S.
M.
L
M.
L.
M.
L.
L.
+ H
0.06
0.28 0.20
0.32 0.58
0.32
0.34
0.48
0.50
0.14
0.12
0.14
0.36
0.44
0.64
0.58
E.I.
0.13
0.36 0.40)
0.31 0.48 0.72
0.26
0.48 0.54
0.28
0.48 0.14
0.09
0.18
0.14
0.34
0.46
0.58
0.37
0.74 0.64
A.L. 0.53 0.48 0,32
0.77 0.64 0.62
0.50
0.32 0.50
0.74 0.50 0.26
0.18
0.16
0.20
0.71
0.68
0.54
0.95
0.98 0.94
E.L 0.53 0.28
0.82 0.76 0.86
0.42
0.36 0.44
0.78
0.64 0.34
0.42
0.38
0.32
0.72
0.64
0.92 0.96
A.L. 0.27 0.42 0.28
0.29
0.28 0.40
0.51
0.70
0.64
0.54
0.84 0.68
0.15
0.12 0.24
0.41
0.44
0.28
0.77
0.72 0.88
S
EL 0.15 0.52 0.48
0.29
0.26 0.32
0.43
0.56 0:40
0.38
0.64
0.52
0.14
0.24
0.32
0.36
0.28
0.20
0.78
0.82 0.88
A.I. 0.30
0.58 0.52
0.29
0.56
0.48
0.29
0.60
0.50
0.36
0.56
0.62
0.26
0.42
0.46
0.18
0.24
0.20
0.40
0.76 0.74
F
EL
0.22 0.42
0.28
0.52
0.28
0.58
0.56
0.16
0.22
0.76 0.64
3.3 PATTERN DETECTION
In the pattern detection task, we prompt LLMs to detect specific primitive graph patterns in the input graph. We randomly generate thousands of non-isomorphic input graphs, with three graph scales: small (5-15 nodes), medium (15-25 nodes), and large (25-35 nodes). The example prompt "Identify the occurrence of the given pattern in the input graph. The pattern is diamond, defined as a 4-node motif with five edges. The input graph is score to evaluate L.M performance terms of precision and recall.
For each pattern, we calculate the FI
The results for small and medium scales are shown in Figure π with the full results provided in Appendix Table [8] Overall, the performance of most LLMs declines as the pattern becomes more complex and the input graph grows larger. This is because LLMs must examine every pair of nodes to determine whether they align with the pattern. Notably, O1-mini less affected by the graph scale, as its step-by-step approach may help mitigate this issue.
4 TOPOLOGY-BASEI PATTERN
In this section, first perform pattern isomorphic mapping to examine LLMs' understanding of topology-bart based graph patterns. Subsequently, we conduct graph modification and pattern detection tasks to further evaluate LLMMs capabilities with various patterns and graph scales.
4

---

Published as a conference paper at ICLR 2025
Table 4: The accuracy for isomorphic mapping
GPT-4
GPT-4n
Mixtral
Llama
Gemini
Claude
O1-mini
A.L.
E.L.
A.L.
E.I.
A.L.
E.L.
A.L.
E.L.
A.I.
E.L.
A.I.
E.I.
A.L.
E.I.
Small
0.30
0.83
0.30
0.94
0.20
0.93
0.42
0.96
0.22
0.39
0.41
0.94
0.77
0.66
Medium
0.08
0.34
0.00
0.82
0.00
0.64
0.24
0.86
0.00
0.14
0.18
0.92
0.32
0.28
Large
0.06
0.14
0.00
0.94
0.04
0.10
0.14
0.68
0.00
0.02
0.20
1.00
0.00
0.32
4.1 GRAPH ISOMORPHIC MAPPING
In topology-basee based description, isomorphic graphs can appear different due to the distinct naming of nodes. Thus, LLMs may mistakenly recognize isomorphic graphs as distinct entities. In this task, test whether LLMs find a one-to-one correspondence (bijection) between the node sets of two isomorphic graphs. We reuse the graph datasets in the terminology-basd based pattern detection task. For each graph, the original node IDs range from 0 to 35. We shuffle and relabel the node IDs to span from 100 to 135 to create the isomorphic graphs. Each sample is guaranteed to have at least one valid mapping solution. We employ accuracy as the evaluation metric, measuring how effectively LLMs map node IDs correctly between two graphs.
The results, presented in Table show that most LLMs per- form well on small datasets, but their performance degrades as the graph scale increases. However, GPT-4o and Claude still maintain high accuracy using the edge list format. Conse- quently, we select medium- and large-scale graphs for further analysis. Upon manually reviewing the output text from GPT- 4o, Claude, and O1-mini, we found that there exist two algo- rithms to help LLMs reason whether the graphs phic. One approach involves first calculating node degrees and then mapping nodes with matching degrees, while the other compares the edge list directly. Due to the LLMs' inherent difficulty with counting, results based on degree counting tend to be less reliable. As shown in Figure -1-mini uses the de- gree counting approach with the proportion 89%. Only about 30% of the outputs from Claude and GPT-4o use degree count- ing, with the majority relying on edge comparison. As LLMs are not good at counting, the accuracy of Claude and GPT-4o is significantly higher than O1-mini.
0,50
0.3
0.8
Insputtion wding deopree
0.6
0.31
isomor-
0:23
0.34
0.3
O1emi
GFT-4c
Cánaaee
Figure 2: The influence of underly- ing algorithms used in pattern iso- morphic mapping
4.2 GRAPH MODIFICATION
We use the same setting as that in the terminology-based pattern detection, except the descriptions are now replaced with topology-basee descriptions. Note that since the graph nodes are represented by numerical IDs, we use uppercase letters for pattern nodes to prevent confusion for LLMs. The results are shown in Table 5 Similar to the terminology-base based case, O1-mini still delivers the best performance, and the graph scale has little impact on the outcome. However, the average accuracy for topology-basee based descriptions is lower than that for terminology-base ones, likely due to increased hallucinations. For instance, when modifying diamond graphs to include square patterns using the edge list format, the presence of squares with diamond structures prevents L.MSs from exhibiting any change.
Table 5: The success rate for topology-based graph modification
Gemiin M.
Mixtral
Llama M.
Claude
GPT-4
GPT-40
O1-mini
S.
S.
M.
I.
S.
L.
S.
M.
L.
S.
M.
S.
M.
L.
S.
M.
L.
A.L. 0.20
0.34
0.70
0.78
0,58
0.57 0.52 0.48
0.45
0.45 0.64
0.44
0..4
0.56
0.56
0.67 0.70 0.68
0.61 0.82 0.80
E.L. 0.22
0.42 0.26
0.66
0.68 0.54
0.45 0.50
0.48
0.38
0.54
0.42
0.24
0.60
0.52 0.36 0.52
0.60
0.46
0.68 0.74
A.L. 0.45 0.34 0.32
0.78 0.66 0.60
0.65 0.50 0.74
0.69
0.62 0.60
0.48
0.56
0.40
0.75
0.68
0.66
0.82 0.76 0.86
S 0 D
EL 0.48
0.40 0.52
0.67
0.70 0.62
0.69
0.46 0.62
0.72
0.74 0.74
0.67
0.62
0.20
0.67
0.68
0.74
0.88
0.86 0.84
A.I.
0.12 0.24 0.12
0.58 0.42 0.60
0.29
00.2200.20 0.26 0.40
0.12
0.26 0.36
0.16
0.48
0.40
0.41
0.40
0.48
01.55 0.56 0.64
S
E.
0.11 0.32
0.32
0.40
0.32 0.44
0.29 0.30 0.20
0.11
0.22
0.48
0.06
0.30
0.20
0.20
0.18
0.36
0.24
0.36 0.28
A.L. 0.28
0.38
0.52
0.40
0.55 0.68
0.37
0.54
0.48
0.68
0.76
0.80
0.76 0.68
F
E.L
0.20
0.24
0.32
0.52 0.34
0.34
0.55
0.29
0.44
0.34
0.27
0.46
0.48
0.44
0.62
0.52
0.32
0.66 0.66
5

---

Published as a conference paper at ICLR 2025
[CPT-4
(O/T46
Mistral
Lama
Gemini
Cladd Claude
Gl-mini
(P1-9o
Mistral
Liema
Otemini
0.6
0.4
Triangle
T-triangee
Square
Diemond
House
V-5
FFL
FBL
D-Diamond
Figure 3: The F1 score of topology-ber pattern detection (small and medium scale)
4.3 PATTERN DETECTION
We use the same setting that in the terminology-biie pattern detection, except the pattern de- scriptions are now topology-base -baeed descriptions. The results are shown Figure 3 with full results provided in Appendix Table [9] The performance of LLMs is also influenced by their capabilities, graph scales, and the complexity of patterns. For instance, while O1-mini achieves a high FI score in detecting tailed-triangle, square and diamond patterns, other models only reach F1 score of 20%. Moreover, although O1-mini performs well on small-scale graphs, fails on medium-scale datasets. Among the patterns, the house pattern is particularly difficult detect, it is the most complex pattern in our setting.
Table 6: The precision of nodes in k-core detection
GPT4
Go
Mixtral
Llama
Gemini
Claude
Ol-mini
A.L.
E.L
A.L.
E.L
A.L.
E.L
A.L.
E.L
A.L.
E.L
A.L.
E.L.
A.L.
E.L
Small
0.63
0.62
0.61
0.62
0.62
0.61
0.63
0.63
0.61
0.60
0.63
0.63
Medium
0.73
0.62
1.00
0.85
0.84
0.78
0.84
0.80
0.80
0.88
0.88
Large
0.66
0.52
1.00
1.00
0.90
0.88
1.00
0.84
0.76
1.00
1.00
1.00
DATA-DRIVEN PATTERNS
In this section, we focus on three classic data-driven patterns that are useful in many areas: densely connected subgraphs, frequent subgraphs within graphs, and discriminative patterns based on labels. By examining densely connected subgraphs, such as k-cores, we can identify communities and make friendship recommendations in social networks. Frequent subgraphs help uncover common structural motifs, which valuable chemistry and biology. Discriminative patterns enable us to distinguish between different classes within the data, aiding in classification tasks.
5.1 DENSE SUBGRAPII MINING (K-CORE)
K-core is commonly used densely connected subgraph, defined as maximal subgraph containing nodes of degree or more. In this task, we prompt LLMs to leverage the k-core algorithm (Batagelj & Zaversnik 2003) to identify 3-core in the input graph. We compute Precision the metric by judging whether the identified nodes belong to a 3-core and present the results in T
On average. LLMs achieve ability to execute the algorithm effectively. Notably, LLMs obtain better performance on large-scale graphs than smaller ones, likely because most nodes in large graphs have degrees greater than LLMs tend to make errors when node degrees are close to 3 but become increasingly accurate node degrees increase. In Figure 4 we select GPT-4o and O1-mini to analyze the relationship between node degrees and precision scores. Nodes with a degree of 3 have 50% precision, while those with degrees above reach nearly 100% precision.
60% precision across various graph scales, demonstrating their
5.2 FREQUENT SUBGRAPH EXTRACTION
Mining frequent subgraphs is important task graphs, defined as finding subgraphs that appear frequently a graph dataset given a frequency threshold. For each pattern, we first generate graph dataset, ensuring that each graph contains the target pattern. The statistics of datasets provided in

---

Published as a conference paper at ICLR 2025
Table 7: The accuracy of extracted frequent subgraphs
GPP14
GPT-4o
Mistral M.
Liama
Gemini
Clande
Ol-minn
M.
L.
S.
M.
L.
5.
S.
M.
L.
S.
M.
L.
M.
L.
S.
M.
L.
Trisngle
A.L.
1.80
1,00
1.00
0.84
0.88
11.8
0.86
0.8%
1.00
0.62
0.68
0.87
1.00
1.00
0.59
0.43
0.26
0.09
1,00
1.00
1.00
E.L.
1.00
1.00
1.00
03:44
1,00
11.11
1.00
1
1.00
0.94
0.55
1,00
1.00
0.57
0.29
0.54
0.58
0.32
1,00
1,00
1.00
Square
A.L
1.00
1,00
1,00
1,003
0.69
1.00
0.61
0.94
1.00
0.75
0.47
1.00
0.40
0.37
0.07
1.00
Diamond
A..
1.00
1,00
1,00
0.89
1.00
0.50
0.92
1.00
1.00
0:3
0.52
0.96
1.00
1.00
0.83
0.34
0.33
0.14
1.00
1.00
F.I.
1.00
1.00
1.00
1,00
0.87
0.99
1.00
1.00
1.00
0.99
0.93
0.91
1.00
0.38
0.52
0.90
0.68
0.32
1.00
1.00
1.00
Heuse
A.I.
1.00
1,00
1.00
1,00
1,00
13.95
0.33
1,00
1,00
0.53
0.66
0.95
1.00
0.78
0.10
0.31
0.32
0.22
1,00
1,00
1.00
E.L
1.00
FFL
A.T.
1.00
1.00
1.00
0.91
0.64
1.00
0.89
1.00
0.86
0.67
0.68
0.93
0.80
0.00
1.00
0.33
0.32
0.36
1,00
1,00
1.00
1.00
1.00
1,00
1,00
0.78
0.77
0.67
1100
E.L.
1,00
1,00
1,00
0.98
0.75
0.83
1.00
1.00
1,00
0.96
1.00
1.00
1.00
1.00
1.00
0.54
0.45
0.31
1,00
1.00
1.00
D DiDamoodd
A.L.
E.L
1,00
1,00
1,00
1,00
1.00
1,00
0.81
0.85
0.88
0.95
0.66
1.00
1.00
1.00
0.60
1,00
0.67
1,00
0.54
0.78
0.73
1.00
0.91
1.00
0.67
1.00
0.75
0.00
1.00
1.00
0.41
0.61
0.46
0.42
0.35
0.28
1,00
1,00
1,00
1.00
1.00
1.00
Table 8: Results for discriminative pattern learning by labels
GPT-4
GPT-4o
Mixtral
LLAMA
Gemini
Claude
O1-mini
ACC
D.P.
ACC
D.P.
ACC
D.P.
ACC
D.P.
ACC
D.P.
ACC
D.P.
ACC
D.P.
A.L.
0.82
0.66
0.63
0.25
0.52
0.33
0.80
0.43
0.91
0.70
0.79
0.68
0.77
0.31
E.L.
0.97
0.47
1.00
0.58
0.75
0.12
0.89
0.71
0.99
0.70
1.00
0.64
0.72
0.08
Table 12 In each turn, we randomly select 10 graphs from the dataset, task LLMs to extract frequent patterns based on these selected graphs, and output patterns in the topology-bard -based description. We repeat this process 100 times and calculate the accuracy as the percentage of cases where the output pattern appears in more than 60% of the selected graphs. It is worth noting that the extracted pattern does not need exactly match the tested pattern. For example, if the LLMs identify triangle pattern during testing with a house pattern, we still consider this an accurate outcome. The accuracy and frequency of extracted patterns are summarized in Table 7 and Figure respectively.
In Table 7 LLMs exhibit a strong capability in identifying frequent subgraphs, with GPT-4 and 01- mini showing impressive performance. However, LLMS are prone detect simpler patterns rather than more complex ones in the dataset. In Figure 5 we illustrate the accuracy when different models extract the defined patterns in the datasets. Although various patterns appear with similar probability across different datasets, LLMs predominantly identify triangles. The house pattern, a combination of a triangle and square, rarely recognized.
1.0
trianila
equare dimonnd
1.00
Signfintiticent pattemo for
0.75
graphs
0.50
What's dillieent??
0.6
CP740 A.:
GP74c
Show signilicant patterns for set2
0L mm/ ALL
OL-mLLEL
0.00
GP74
40
Modrel
Linea
Genov
Glesie
of man
lahel 2 graphs
Node
Sampling
Identifying
Figure 4: The precision Figure 5: The frequency in various node degrees
Figure 6: The pipeline of discriminative
of extracted patterns
pattern learning by labels
5.3 DISCRIMINATIVE PATTERN LEARNING
This task is to extract and learn important patterns from input graphs to discriminate labels. The labels, which typically represent categories or outcomes, act as a guide for discovering the most significant patterns for the task. We implement a two-step process to instruct LLMs, as illustrated in Figure 6
We first sample an equal number of graphs from each label to form a dataset. Then, we prompt LLMS to identify discriminative patterns that differentiate one label from another. This process is repeated multiple times, and all extracted patterns are retained. We further filter these patterns: for each pattern, we ensure that over 90% of graphs with the corresponding label contain the identified pattern, while 90% of graphs with other labels do not. The remaining are regarded as discriminative patterns. We use two metrics to evaluate the discriminative patterns. We introduce an extra classification task to measure the effectiveness, where we ask LLMs to predict the labels of new graphs based on the discriminative patterns and compute the prediction accuracy. In addition,
7

---

Published as a conference paper at ICLR 2025
calculate the discriminative pattern ratio as D.P. #Diccrininative patterns which assesses the # Extracted pattorns
efficiency of the extraction process.
The results in Table demonstrate that most LLMs successfully perform graph classification tasks, particularly when using the edge list format. Interestingly, high D.P. score does not always linearly correspond to high accuracy. For instance, despite having a D.P. score of 0.08, O1-mini still achieves classification accuracy of 0.72.
6 EVALUATION ON REAL-WORLD GRAPHS
In this section, we gather a range of real-world datasets across diverse domains of graphs, including molecules, social networks, bioinformatics, and computer vision. Different from synthetic dataset, the real-world graphs have node attributes and potential noise in the graph structures, which makes the graph pattern tasks more challenging. More details of datasets and prompts are provided in the appendix B In this evaluation, we focus on pattern detection and discriminative pattern learning.
we perform pattern detec- tion in molecular graphs, where the goal is to ask LLMs to detect the target pattern in the given molecule. We evaluate three datasets: Benzene, Alkane-Carbone (F-CO), where the target patterns are hexagons, alkane groups, and fluoride groups, respectively. We compare the terminology-base with topology-based patterns, and also assess a combined approach, referred to as Both.
Molecule Pattern Detection. Followed by Section 3.3 and Section 4.3
(R-CO), and
Table 9: The Fl score for pattern detection in molecules
Terminology-bant based
Topology-based R-CO
Both R-CO
Benzene
R-CO.
F-CO
Benzene
F-CO
Benzene
F-CO
GPT-4
A.L.
0.88
0.73
0.68
0.71
0.64
0.70
0.89
0.71
0.69
E.L.
0.85
0.71
0.67
0.72
0.64
0.69
0.83
0.69
0.70
GPT-4o
A.L.
0.88
0.66
0.67
0.76
0.66
0.69
0.87
0.68
0.67
E.L.
0.90
0.66
0.67
0.78
0.67
0.69
0.86
0.65
0.67
Table Iillustrate that terminology-based descriptions outperform topology-based ones for both the Benzene and R-CO datasets. However, combining both descriptions does not enhance performance, as the final F1 scores are slightly lower than using terminology alone. This indicates that in real- world applications, LLMs may rely on internal knowledge, such as retrieving the name of patterns, to understand molecular structures.
Table 10: Discriminative patterns and classification result in real-world datasets
Binary classification
Multi label classification
MUTAG
OGBG
DGBG-MOL
OGBG BBBP
IMDB BINARY
ENZYYMES
FINGERPRINT
IMDB MULTI
A.L.
EL.
A.L.
E.L.
A.L.
E.L
A.L.
E.L.
EL.
EL.
A.L.
EL.
GPT-4
0.66
0.70
0.56
0.58
0.64
0.7
0.78
0.38
0.36
0.36
0.35
GPT-1o
0.61
0.63
0.52
0.60
0.68
0.70
0.68
0.72
0.40
0.35
0.35
0.31
0.31
0.35
Discriminative Patterss
Discriminative Pattern Learning and Classification. Based on Section 5.3 we conduct the 2- step process of discriminative pattern learning and classification roal-world datasets. We use hundreds of samples for discrimination and test about 50 samples in classification. Further details can be found in Appendix Table 13
Table 10 presents the results for both binary and multi-label classification accuracy on the molecular (MUTAG, OGB-MOL, OGB- social network mation (ENZYYMES), and computer vision (FINGERPRINT) datasets. Notably, we highlight the most discriminative patterns extracted by GPT-4 which provide meaningful insights into the given dataset. For instance, in the MUTAG dataset, NO2 groups are marked as positively influencing mutagenicity (Agarwal al. 2023). Due to the current high cost of LLMs, we performed limited sampling during the discrimination process. We believe that increasing the sampling size in this stage would improve the overall classification score.
IMDB-MULTD,, bioinfor-
8

---

Published as a conference paper at ICLR 2025
7 DISCUSSIONS
In this section, we first provide our theoretical intuitions from the perspective of expressiveness and then summarize key insights from our observations.
7.1 THEORETICAL INTUITIONS
Here we discuss the theoretical intuitions of LLMs' capabilities in graph pattern recognition from an expressiveness standpoint, often used in analyzing Transformers (Feng et al. 2024 Li et 2024 de Luca & Fountoulakis 2024). We demonstrate that Transformers, given graph inputs, can be configured to perform graph pattern tasks. The LOCAL framework Angluin (980) is a distributed computing paradigm, implemented by the message passing among the nodes. Many graph pattern algorithms such as pattern detection can be efficiently implemented by LOCAL (Drucker et al.) 2014 Korhonen & Rybicki 2017). Intuitively if Transformers can simulate any LOCAL algorithms, it has the capability for graph pattern tasks. We build the following theorem for this intuition.
Theorem 1. (Informal) For any LOCAL algorithm A, there exists Transformer with edge list as inpul that can simulate A.
The detailed proof is given in Appendix A The proof intuition is that the attention mechanism is message- passiin between the tokens and each token is executed in a parallel manner. Consequently, this mechanism enables Transformers to simulate the message passing between nodes. The above theorem suggests the existence of such weights.
7.2 EMPIRICAL INSIGHTS
LLMs use diverse algorithms for one task, and the performance varies due to their execution ability. We provide two observations: (I) We manually reviewed most of the outputs generated by LLMs in graph mining tasks, and summarized the algorithms used by LLMs in Appendix H. Our analysis reveals that different LLMs utilize diverse algorithms to solve the same problem. For instance, more than eight algorithms are used for pattern detection tasks (Section 3.3 (2) Due to the internal flaws of L.Mss, these algorithms, although logically correct, will have different perfor- mance. In the graph isomorphic mapping task (Section[4.I). a common algorithm starts by counting node degrees and then mapping nodes. O1-mini uses this approach for 89% of the data but achieves only 30% accuracy due to errors in degree counting. In contrast, Claude applies degree counting only 23% of the data, relying primarily on a direct edge-matching algorithm for the rest. This alternative strategy enables Claude to achieve an impressive 96% accuracy.
Input format that aligns with the pretrained knowledge improves the performance. Our exper- iments demonstrate that LLMSs have basic knowledge about graph patterns and they help LLMs in graph pattern tasks. First, LLMs are pre-trained on extensive internet datasets where graph patterns are often described using specific terminologies. This exposure helps LLMs understand these terms. Comparing the results in Section 3.3 with those Section 4.3 we observe that terminology-base graph pattern detection generally outperforms topology- based detection. This suggests that LLMs leverage their internal knowledge to enhance performance when provided with terminology as input. Second, the pretrained knowledge will influence the strategies employed by LLMs, and the graph input format that aligns with the strategies will improve the performance. For example, in the case of discriminative pattern learning (Section (.3). the algorithms used by LLMs often rely on com- paring corresponding edges in two graphs. In this scenario, the edge list format typically leads to better performance than the adjacency list format. Conversely, k-core detection (Section 5.I). the algorithms require counting node degrees, so the edge list is inferior to the adjacency list.
O1-mini often gives the best results, but not always. In most tasks, O1-mini has the best perfor- mance, especially when the graph size is large. This is not surprising because it has much longer chain-of-thought. For example, in the pattern detection task, which requires LLMs to search node combinations one by one, Ol-mini holds a clear advantage. However, it falls back in the discrimina- tive pattern learning by labels in Section 5.3 The reason is that O1-mini strictly searches for patterns that exactly meet the data requirements, without allowing for fuzzy matching. This results in smaller discriminative patterns being found. Consequently, when Ol- mini attempts graph classification, the patterns struggle to generalize, leading lower classification accuracy.

---

Published as a conference paper at ICLR 2025
8 RELATED WORK
Large Language Models for Graphs. Here, we introduce previous work using LLMs based on the types of graph tasks they focused on. The first category to solve graph algorithm tasks, such as connectivity, degree counting, cycle check, shortest path, and Hamilton path. NLGraph (Wang) jet al., 2024) and Talk like graph (Fatemi et al. (023) translated graph structures into natural lan- guage, and leveraged techniques like few-shot prompting or chain-of-thoughh (CoT) to feed these descriptions directly into LLMs for inference. Since exact computational algorithms can be em- ployed to obtain accurate reasoning process and results, GraphInstruct (Luo et al. (2024) built the instruction-tunin totiinnnnnnntngggg dataset and fine-tuned LLMs by Lora. Moreover, Graphwiz (Chen et al. 2024a) extended the scale and diversity of the dataset and applied Direct Preference Optimization (DPO) loss to enhance the performance. Recently, GraphToken (Perozzi et al. 2024) utilized a GNN-like
encoder to process the input graph and train this encoder with frozen LLM.
The second category encompasses graph learning tasks, which typically include node classifica- tion, link prediction, and graph classification (Chen et al.] 2024c). Unlike graph algorithm tasks relying on deterministic rules for inference, graph learning tasks involve learning the relationship between graphs and labels using provided training examples. Graph-LLM (Chai et al., (023) and GraphText (Zhao et al. (203)) designed prompts that convert graph structure, node/edge attributes, and label information into natural language, enabling LLMs to make predictions without additional training. In contrast, other approaches incorporate projectors or encoders before LLMs and con- struct datasets for tuning. LLaGA (Chen et al., 2024b) and MuseGraph (Tan et al., 2024) reorga- nized the center node and its neighborhood information as structure-aware textual description, which is then tokenized by a projector and fed into LLMs to predict node labels in citation graphs GraphGPT (Tang et al. (2224) utilized GNN encoder to tokenize the input graph before processing it with the LLM to address node classification in text-attributed graphs. MolCA (Liu et al., (023) and InstructMol (Cao et al. 2023) used similar GNN encoders for molecular structures to predict their properties.
Graph Pattern Discovery. Graph patterns (also known substructures, graphlets, motifs and subgraphs) have been extensively studied before the era of LLMs due to their crucial role in real- world applications, particularly in chemistry (Murray & Rees 2009), biology (Hu et al. 2005). and social science (Wu et al., 2022). Numerous algorithms have been proposed for pattern discovery. For example, the algorithms designed to identify and count dense pre-defined patterns, such as k- core, k-cycle, and k-clique, were introduced in Milo et al. (2002); Zhang & Parthasarathy (2012).
Frequent subgraph mining algorithms were developed to efficiently search for possible patterns (Yan) et al. 2008 Elseidy et al. 2014), aiming to reduce the search space as much as possible.
In recent years, deep learning, particularly graph neural networks (GNNs), has become prominent in this area. Many studies (Chen et al. 2020; [Zhang et al. 2023) Luo et al., 2022) investigated the theoretical guarantees of specific GNNs capable of identifying certain substructures, and developed subgraph-aware GNNs with strong expressiveness to improve the accuracy of graph learning tasks. More recently, some studies (Zhngg et al.) (202)) have begun exploring the use of LLMs to identify SMILES patterns in molecular data, opening new avenues for research.
As previously mentioned, few studies have addressed graph pattern discovery using LLMs, despite their importance for many downstream tasks, which still require further exploration.
CONCLUSION
We investigate how LLMs understand graph patterns. While recent studies demonstrate that LLMs have shown success in various graph-related tasks, the comprehension of graph patterns remains un- explored. To bridge this gap, we propose benchmark featuring both synthetic and real-world data, spanning 11 subtasks evaluated across 7 LLMss. Using known patterns defined through terminology- based and topology-based descriptions, we conduct tasks including pattern translation, isomorphic mapping, graph modification, and pattern detection. For unknown patterns, we cover classic tasks such as densely connected subgraph detection, frequent pattern mining and discriminative pattern learning using labeled graph data. The real-world datasets gathered to further assess LLMs' ability to handle the attributes and noise in the pattern. Our results show that LLMs possess a pre- liminary capability to understand graph patterns and perform tasks related to them effectively.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The work supported by the Accelerating Foundation Model Research Program (AFMR), Mi- crosoft Research. Ximnan Dai and Jiliang Tang are supported by the National Science Foundation (NSF) under grant numbers CNS2321416, IIS2212032, I1S2212144, IOS2107215, DUE2234015, CNS2246050, DRL2405483 and IOS2035472, the Army Research Office (ARO) under grant num- ber W911NF-21-1-0199. Amazon Faculty Award, Meta, Microsoft and SNAP.
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.08771 087744 2023.
Chirag Agarwal, Owen Queen, Himabindu Lakkaraju, and Marinka Zitnik. Evaluating explainability for graph neural networks. Scientific Data, 10(1):144, 2023.
Dana Angluin. Local and global properties in networks of processors. In Proceedings of the twelfth annual ACM symposium Theory of computing, pp. 82-93, 1980.
Vladimir Batagelj and Matjaz Zaversnik. An (m) algorithm for cores decomposition of networks. arXiv preprint cs/0310049, 2003.
Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 1s(upppL.);: 147-i56.22 2005.
He Cao, Zijing Liu, Xingyu Lu, Yuan Yao, and Yu Li. Instructmol: Multi-modal integration for building a versatile and reliable molecular assistant in drug discovery. arXiv preprint arXiv:2311.16208, 2023.
Ziwei Chai, Tianjie Zhang, Liang Wu, Kaiqiao Han, Xiaohai Hu, Xuanwen Huang, and Yang Yang. Graphlim: Boosting graph reasoning ability of large language model. arXiv preprint arXiv:2310.05845, 2023.
Nuo Chen. Yuhan Li, Jianheng Tang, and Jia Li. Graphwiz: An catruction-following language model for graph computational problems. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 353-364, 2024a.
Runjin Chen, Tong Zhao, Ajay Jaiswal, Neil Shah, and Zhangyang Wang. Llaga: Large language and graph assistant. arXiv preprint arXiv:2402.08/70 2024b.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 33:10383-10395, 2020.
Zhikai Chen, Haitao Mao, Hang Li, Wei Jin, Hongzhi Wen, Xiaochi Wei, Shuaiqiang Wang. Dawei Yin, Wenqi Fan, Hui Liu, et al. Exploring the potential of large language models (Ilms) in learning on graphs. ACM SIGKDD Explorations Newsletter. 25(2):42-61 61, 2024c.
Dawei Cheng, Xiaoyang Wang, Ying Zhang, and Liqing Zhang. Graph neural network for fraud detection via spatial- attention. IEEE Transactions on Knowledge and Data Engineering, 3408)33800-3813, 2020.
Jiefeng Cheng. Jeffrey Xu Yu, Bolin Ding, S Yu Philip, and Haixun Wang. Fast graph pattern matching. In 2008 IEEE 24th international conference on data engineering, pp. 913-922. IEEE, 2008.
Artur Back de Luca and Kimon Fountoulakis. Simulation of graph algorithms with looped trans- formers. arXiv preprint arXiv:2402.01 107, 2024.
Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Cor- win Hansch. Structure-activee activity relationship of mutagenic aromatic and heteroaromatic nitro com- pounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2)786--777, 1991.
11

---

Published as a conference paper at ICLR 2025
Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pp. 367-376, 2014.
Mohammed Elseidy, Ehab Abdelhamid, Spiros Skiadopoulos, and Panos Kalnis. Grami: Frequent subgraph and pattern mining in a single large graph. Proceedings of the VLDB Endowment, 7(7): 517-528, 2014.
Bahare Fatemi, Jonathan Halerow, and Bryan Perozzi. Talk like a graph: Encoding graphs for large language models. arXiv preprint arXi::2310.45500, 2023.
Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: a theoretical perspective. Advances in Neural Information Processing Systems, 36, 2024.
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 (rXXi:2305.50666 2023.
Haiyan Hu, Xifeng Yan, Yu Huang, Jiawei Han, and Xianghong Jasmine Zhou. Mining coherent dense subgraphs across massive biological networks for functional discovery. Bioinformatics, 21 2005.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benehmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 11222118-22133 11-11183,,1311111 2020.
Jin Huang, Xingjian Zhang, Qiaozhu Mei, and Jiaqi Ma. Can Imms effectively leverage graph struc- tural information through prompts, and why? Transactions on Machine Learning Research, 2024.
Janne H Korhonen and Joel Rybicki. Deterministic subgraph detection in broadcast congest. arXiv preprint arXiv: 10195, 2017.
Xiaodong Li, Reynold Cheng, Kevin Chen-Chuan Chang, Caihua Shan, Chenhao Ma, and Hongtai Cao. On analyzing graphs with motif-paths. Proceedings of the VLDB Endowment, 14(6). 2021.
Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. arXiv preprint arXiv:2402. 12875, 2024.
Zhiyuan Liu, Sihang Li, Yanchen Luo, Hao Fei, Yixin Cao, Kenji Kawaguchi, Xiang Wang, and Tat-Seng Chua. Molca: Molecular graph-language modeling with cross-modal projector and uni- modal adapter. arXiv preprint arXiv:2310.1277 127998. 2023.
Andreas Loukas What graph neural networks cannot learn: depth vs width. arXiv preprint
arXiv:1907.03199, 2019.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances in neural information pro- cessing systems, 33:19620-199 19631, 2020.
Zihan Luo, Jianxun Lian, Hong Huang, Hai Jin, and Xing Xie. Ada-gnn: Adapting to local pat- terns for improving graph neural networks. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, pp. 638-647, 2022.
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 wwXiv:2403.04483 2024.
Ines Filipa Martins, Ana I. Teixeira, Luis Pinheiro, and Andre Falcao. A bayesian approach to in silico blood-brain barrier penetration modeling. Journal of chemical information and modeling, 1266).666-1667, 2012.
Ron Milo, Shai Shen-Om: Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Net- work motifs: simple building blocks of complex networks. Science, 298(5594):824-837 827, 2002.
12

---

Published as a conference paper at ICLR 2025
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs arXiv preprint arXiv:2007.08663, 2020.
Christopher W Murray and David C Rees. The rise of fragment-basee based drug discovery. Nature chemistry, 13):1877-92, 2009.
Bryan Perozzi, Bahare Fatemi, Dustin Zelle, Anton Tsitsulin, Mehran Kazemi, Rami AI-Rfou, and Jonathan Halcrow. Let your graph do the talking: Encoding structured data for Ilms, arXiv preprint arXiv:2402.005822 2024.
Benjamin Sanchez-Lengeling, Jennifer Wei, Brian Lee. Emily Reif, Peter Wang, Wesley Qian, Kevin McCloskey, Lucy Colwell, and Alexander Wiltschko. Evaluating attribution for graph neural networks. Advances in neural information processing systems, 33:5898-590 2020.
Teague Sterling and John J Irwin. Zinc 15-ligand discovery for everyone. Journal of chemical information and modeling, 55(1 (1:22)22222335 2337, 2015.
Yanchao Tan, Hang Lv, Xinyi Huang, Jiawei Zhang, Shiping Wang, and Carl Yang. Musegraph: Graph-oriented instruction tuning of large language models for generic graph mining. arXiv preprint 4rXiv:2403.04780 2024.
Jiabin Tang, Yuhao Yang, Wei Wei, Lei Shi, Lixin Su, Suqi Cheng, Dawei Yin, and Chao Huang. Graphgpt: Graph instruction tuming for large language models. In Proceedings of the 47th In- ternational ACM SIGIR Conference on Research and Development in Information Retrieval, pp- 491-500, 2024.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint 3rX1v:2302..3971, 2023.
Ngoc Hieu Tran, Kwok Pui Choi, and Louxin Zhang. Counting motifs the human interactome.
Nature communications, 4(1):2241, 2013.
Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can language models solve graph problems in natural language? Advances Neural Information Processing Systems, 36, 2024.
Xixi Wu, Yun Xiong, Yao Zhang, Yizhu Jiao, Caihua Shan, Yiheng Sun, Yangyong Zhu, and Philip S Yu. Clare: A semi-supervised community detection algorithm. In Proceedings of the 28th ACM SIGKDD conference knowledge discovery and data mining, pp. 2059-2069 2022.
Xixi Wu, Yifei Shen, Caihua Shan, Kaitao Song, Siwei Wang, Bohang Zhang, Jiarui Feng, Hong Cheng, Wei Chen, Yun Xiong, et al. Can graph learning improve task planning? arXiv preprint arXiv:2405. 19119, 2024.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learn- ing. Chemical science, 9(2):513-53) 2018.
Xifeng Yan, Hong Cheng, Jiawei Han, and Philip S Yu. Mining significant graph patterns by leap search. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pp. 433 444, 2008
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. Proceedings of the 21th ACM SIGKDD international conference knowledge discovery and data mining, pp. 1365-1374, 2015.
Ruosong Ye, Caiqi Zhang, Runhui Wang, Shuyuan Xu, Yongfeng Zhang, et al. Natural language is all graph needs. arXiv preprint arXiv:2308.071334 4(5):7, 2023.
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zimik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019.
13

---

Published as a conference paper at ICLR 2025
Bohang Zhang, Guhao Feng, Yiheng Du, Di He, and Liwei Wang. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests. In International Conference Machine Learning, pp. 41019-41077. PMLR, 2023.
Yang Zhang and Srinivasan Parthasarathy. Extracting analyzing and visualizing triangle k-core motifs within networks. In 2012 IEEE 28th international conference on data engineering, pp-
1049-1060. IEEE, 2012.
Jianan Zhao, Le Zhuo, Yikang Shen, Meng Qu, Kai Liu, Michael Bronstein, Zhaocheng Zhu, and Jian Tang. Graphtext: Graph reasoning in text space. arXiv preprint arXiv:2310.01089, 2023.
Yizhen Zheng, Huan Yee Koh, Jiaxin Ju, Anh TN Nguyen, Lauren T May, Geoffrey I Webb, and Shirui Pan. Large language models for scientific synthesis, inference and explanation. arXiv preprint arXiv:2310.07984, 2023.
A PROOF FOR THEOREM
We first define the edge list format.
U1 U1 Ous e-1 U1 Up an
Un Un Oun 4- U1 01
Un On
edge list
initial states
where U1, are the node id, a, is the node feature and au tor is the edge weights. The definition of mhessage-passingg graph neural networks.
Theorem 2 (Formal version of Theorem D.. Assume the input format is given in equation 7 Let Te(Ga) be the state ( 1nl of a Transformer network with edge list imput in For any LOCAL algorithm N and small number e, there exists T such that
,...,
(G,) Ne(Ga)ll s for every layer and G. E Ga:
where Go is the set of all attributed graphs.
Proof. This theorem is a combination between Lemma I and Lemma
Lemma 1 (Equivalence between MPGNNs and LOCAL). Let Ne(Ga) be the state (x ..... x!) of a MPGNN network N and Az(Ga) = (s{),... (0)) that of a LOCAL algorithu For any algorithm A there exists N (resp. for any N there exists A) such that
Ac(G.) = N:(G.) for every layer & and Ga E Ga-
Algorithm Message passing graph neural network Loukas (011
Initialization: Set (0) a; for all v; V.
for layer = 1.... .d do
for every edge eizj E (in parallel) do
m MSG; (2. (e-1) (1-1)
(0)
Use Uj airs)
for every node V (in parallel) do
(e) UP: Σ
mirj)
UyEN;
Set v; z return 2; for every Py E
Lemma 2 (Representing MPGNNs by Transformers). Assume the input format is given in equa- tion and MSG and Up in Algorithm [ are implemented by MLPs. Let Te(Ga) be the state (at (e)
...., (1)) of a Transformer network T with edge list input in 1 For any MPGNN N and small number e, there exists T such that
(T(e)(Gaa) NeGGa))loo for every layer and Ga Ga.
14

---

Published as a conference paper at ICLR 2025
Proof. The proof is heavily built on the proof of Theorem 1 in Wu et al. (2024)
Token Embedding and Positional Embedding: The token embedding includes the token type elypel (0 for the node feature; 1 for node id: 2 for edge feature), refined token type ebyee (0 for node feature, 1 for the node tokens in initial state sentences, 2 for the target node tokens in the edge list, 3 for the source node tokens in the edge list, 4 for edge feature tokens), and the token id cloken (from O to [V] -).. The two-dimensional positional embedding includes the embedding for initial state tokens eoss (0 for edge list tokens, 1 for the first two elements of initial state sentences, 2 for the second two elements of initial state sentences, etc.), embedding for edge list tokens e e (0 for initial state sentence tokens, 1 for the first three elements of the edge list, for the second three elements of the edge list, etc.). There are also placeholders to put the intermediate states of MPGNNs.
The goal of the first block is to broadcast the node feature a, from the initial state sentence tokens to node tokens in edge list. (1) Use MLPs to recover the digits of the node features o; and put them in the first placeholder if 6
Block 1 Node feature Preparation:
type = 0; (2) Copy the
first placeholder from initial state sentence token to its previous node token by using COPY in Lemma 3 and setting S₁- = fil(eh -
pusl )²= < 8): (3) Broadcast the first placeholder with MEAN
in Lemma and setting Ss (e j
elaken ) 8). Now the state for every node token u; is [ctyel ,etpee, cloken cposl e an.l: (4) Use MLP to put the token id into the second placeholder if etypel == 2 or etypel == 3. Now the state for every node token u, is (ebre1, ,evvc2, gloken ePoss epos2 Oaa Ui]
2prely2 y² + (e
The goal of the second block is to copy the prepare the edge features for the target node token, which will be used for message passing. (1) Use MLPs to recover the digits of the edge feature tokens and put them in the third placeholder if e/ypel == 2; (2) Copy the third placeholder from the edge feature token to the node tokens by using SUM in Lemma 3 and setting Sx = (e p002 - cpmegz < 8J. Now the state for every tar- get node token u, of the i-th edge is [etrel, etype2 clokkn elosi c Ou,,, Us au eu.e (3) Use MLPs to put the node feature in the fourth placeholder if etypel = 3: (4) Copy the fourth placeholder from the source node token to the edge feature token and target node token by using SUM in Lemma ] and setting Sx- = [ji(eeh - e0od222 < 63. Now the state for every target node to- ken u; of the i-th edge is [e.vec elype2 elokon epost .poo2 (h,, Uj uu; ] (5) Put node id w; into the fifth placeholder if etypel = 2: (6) Copy the fifth placeholder from the source node token to the edge feature token and target node token by using SUM in Lemma 3 and setting Se- -ileet of 3 < x0}- Now the state for every target node token u, of the i-th edge is [ebsee, elype? cloken eposl epon2, an. Wi, au, ar, Us]
Block 2 - Edge feature Preparation:
Block 3 Message Preparation: The goal of the third block is to compute (1) Use MLPs to compute MSG, and place the results in the sixth placeholder. Now the state for every target node token u, of the i-th edge is (eNrel, elype2 cinken epast epos2 an, Ou,e-n; ag,, MSG U3 Qu,t am Dt]l;
Mu.er;-
(2) Use MLPs to clean up the remaining placeholders. Now the state for every node token u, is [eBpel, etype, eloken epost eposl MSGe(au,, Ui, Out Ov,, [;)].
Block 4- Message Passing:
The goal of the fourth block is to compute 2!"). (1) Use two attention heads to perform the sum operation in aggregation. This is achieved by using SUM in Lemma 3 for type2
the first placeholder and setting S₃- = (elkee - cjokken2 )2 + +(e - E eypo2y3 < 8). Now the state
for every node token u; is (erpel etype2 _ooken cpost cPos2 E EnjeN; MSGr(au Ui Ou,t B0g U/) 0z]];
(2) Use MLPs to compute UP, and obtain x!!
After four blocks, the final state for every node token u is given by [etypel etype2 ctoken, cpos) cPoo2 (.) A times.
x.(() can be obtained by repeating the above four blocks
O
Lemma 3. Feng et al. 2024g Let n. E N be an integer and æt,, In be a sequence of vectors
where x, = (Z; rú, 1) E I-M M where M is a large constant. Let K, Q, V E Rdd x(d+2) be any matrices with Iloo < 1 and let 0 p, < M be any real numbers. Denote q: = Qæi,k; = K w. 0j- = Vay. Define a matching set S = {illg] k, $ p). Define two following operations
15

---

Published as a conference paper at ICLR 2025
COPY: The output is sequence of vectors u1 Un with u, Upod(iy where pos(i) arg maxjes, Tj.
MEAN, MAX, SUM: The output is a sequence of vectors u1 Uns where ui Djes, v and O is min or max or sum or mean.
Specifically, for any sequence of vectors 3i, 21, In. denote the corresponding output of the attention layer 01, 02,"" ....... On. Then, we have I|u, Oilloo for all [n] and 8 + O.
B DATASET
B. PRIMITIVE GRAPI PATTERNS
We select primitive graph patterns with varying node counts and edge numbers. First, 3-node pat- terns are the simplest structures in graphs,
begin with patterns like the triangle, V-structure (V-S), feedforward loop (FFL), and feedback loop (FBL). In directed graphs, the V-S has two edges, while both the FFL and FBL have three. However, the FFL and FBL differ in the direction one edge. For 4-node patterns, we select the tailed tailed-triangle (T-triangle), square, and diamond for undi- rected graphs, and the directed-diamone for directed graphs. Both the T-triangle and square have four edges but differ in their connectivity, while the diamond includes five edges. Finally, we intro- duce the house pattern, 5-node structure combining a triangle and square. The summarization of patterns shown in Table 11
Table 11: The selected primitive graph patterns (5 undirected and 4 directed patterns)
Undirected Pattem
Directed Pattern
Name
Terminology-bass Description
Structure
Name
Terminology -bacd Description
Structure
Triangle
motif consisting of three
V-structure (V-S)
two nodes have directed edges pointing toward common get node
nodes where each node nected to the other two, forming triangle
Tailed- triangle
triangle with additional
Feedforward loop (FFLL
3-nude directed motif which one source node influ- ences target node through two distinct pathways
node connected to one of the vertices of the triangle
(T-triangle)
Square
4-node cycle where each
Feedhack loop (FBL.)
A 3-node directed cycle where the nodes form a loop
node is connected to exactly two other nodes
Directed- diamond
A 4-node motif in directed graph where one node has di- rected edges two intermedi- nodes, and both of those in- termediate nodes have directed edges to a common target node.
Diamond
4-node motif with five edges
diamond)
House
motif resembling the shape of a house with nodes and 6 edges. The vertices and edges are arranged such that there is triangular "roof" on top square rectangular "buse."
B.2 SYNTHETIC DATASET DETAILS
We generate different datasets for various tasks. In the pattern detection task, we randomly generate graphs small (5-15 nodes), medium (15-25 nodes), and large (25-35 nodes) scales. Besides, to keep the numbers of different patterns reasonable, we ensure the average density of graphs is 0.5 for the undirected graph and 0.25 for the directed graph. We have 1893 undirected graphs and 1313 directed graphs in total. the modification task, we randomly generate the graph with constraints. For example, assume that LLMs need to add most nodes to achieve the goal, in the Square - House sets. This means the original graphs contain at least one square pattern but lack a house pattern, requiring L.LMs modify the graph to create the house pattern. Similarly, Square
16

---

Published as a conference paper at ICLR 2025
Diamond needs to add one edge while Diamond Square needs minus edge. FFL FBL needs to change one edge direction. In the frequent subgraph task, we restrict the generated graphs to include at least one given pattern, specifically triangle. In the discriminative pattern learning task, we employ the BA-2motif dataset (Luo et al. 2020). We split into 900 graphs to evaluate the discriminative pattern learning of LLMs and 100 for classification testing. For the evaluation, will randomly select 250 instances from the small-scale dataset, 50 instances from the medium-scale dataset, and 50 instances from the large-scale dataset evaluate the metries due to the of APIs.
Table 12: Details of synthetic datasets
Task
Dataset type
difficulty
Num
AVG. node
AVG. edge
AVG. density
Small
250
9.50
22.80
0.52
Undirected graph
Evaluation
Medium
250
19.50
96.20
Pattern detection
Large
250
29.50
247.96
0.58
Small
250
9.50
23.44
0.26
Directed graph
Evaluation
Medium
250
19.50
96.98
0.26
Large
250
29.50
223.58
0,26
Small
166
9.71
25.07
0.56
Square + House
Medium
347
14.67
22.09
0.33
Large
476
18.54
24.89
0.26
Small
144
9.91
10.96
0.27
Undirected graph
Square +
Diamond
Medium
332
15.32
17.95
0.19
Large
484
19.54
23.45
0.16
Modification
Small
111
8.95
10.98
0.34
Diamond Square
Medium
180
12.59
13.92
Large
205
14.52
16.03
Small
227
9.63
14.64
0.18
Directed graph
FFI FBL
Medium
396
13.69
19.08
0.13
Large
493
16.60
23.48
0.12
Small
231
9.87
17.61
0.39
Triangle
Medium
248
19.46
56.04
0.31
Large
247
29.46
149.27
0.35
Small
217
10.14
19.35
0,40
Square
Medium
249
19.49
56.32
0.31
Undirected graph
Large
249
29.49
152.85
0,35
Small
214
10.19
20.12
0.42
Diamond
Medium
244
19.44
63,30
Large
246
29.45
168.59
Small
205
10.37
20.50
0.41
Frequent subgraph
House
Medium
250
19.50
60.47
0.33
Large
247
29.46
156.12
0.37
Small
238
9.71
17.93
0.20
FFL
Medium
248
19.48
59.90
Large
250
29.50
154.67
0.18
Small
208
10.20
20.79
0.21
Directed graph
FBL
Medium
244
19.41
64.15
0.18
Large
248
29.48
156.56
0.18
Small
187
10.60
22.33
0.21
D-Diamond
Medium
248
19.48
62.01
0.17
Large
247
29.47
150.57
0.18
Discriminative
Discrimination
900
25
25.5
0.09
pattern learning
Classification
100
25
25.5
0.09
B.3 REAL-WORLDD DATASET DETAILS
To assess the effectiveness of our approach in practical scenarios, we utilize various classical real- world datasets with known ground-truth labels. These datasets encompass six molccule datasets: MUTAG, ogbg-molhiv. BBBP, Benzenes, Alkane-Carbonyl, and Fluoride-Carbonyl: one bioinfor- matics datasets: ENZYMES; computer vision dataset: Fingerprint; and two social network datasets: IMDE-BINARY and IMDB-MULTI. Detailed information regarding datasets delineated in Table 3
MUTAG (Debnath et al. 1991). The MUTAG dataset a collection of nitroaromatic compounds and its goal is predict their mutagenicity Salmonella typhimurium. In evaluation,
17

---

Published as a conference paper at ICLR 2025
the PyGeometric Secinnttrieeresiiiii binary classification task.
version of the dataset, which comprises 188 molecular graphs, for conducting the
OGBG-HIV (Hu et al., 2020; Wu et al. 2018 This dataset encompasses 41,127 graphs, with each graph representing a molecule where nodes denote atoms and edges represent chemical bonds. The primary objective is to predict whether molecules inhibit HIV, constituting binary classification task. For pattern discrimination, we sample 200 molecular graphs fairly, comprising 100 positive instances (i.e., inhibit HIV) and 100 negative instances. Subsequently, we select another 40 test graphs for pattern-based classification purposes.
OGBG-BBBP (Hu et al., 2020 The Blood-brain barrier penetration (BBBP) dataset originates from a study (Martins et al. 2012) focusing on modeling and predicting barrier permeability. As membrane separating circulating blood and brain extracellular fluid, the blood-brain barrier blocks most drugs, hormones and neurotransmitters. This dataset includes binary labels for 2,050 com- pounds on their permeability properties. alignment with our experimental conditions, we ran- domly select 500 compounds for pattern discrimination and 50 compounds for pattern-based binary classification, ensuring an equitable distribution of positive and negative samples.
IMDR-BINARY (Yanardag& & Vishwanathan 2015). It is movie collaboration dataset that consists of the ego networks of 1,000 actors/actresses who have shared roles in movies listed on IMDB, orig- inating from the Action and Romance genres. In each graph, the nodes symbolize actors/actresses, with edges connecting them if they have appeared together a movie. For our experiments, we par- tition 80% of the 1,000 ego networks for pattern discrimination purposes, reserving the remaining networks for a binary classification task, i.e., aiming to predict whether a movie graph is an action or romance network.
IMDB-MULTI (Yanardag & Vishwanathan 2015). IMDB-MULTI is a multi-class extension of IMDB-BINARY, comprising a balanced collection of ego-networks (1,500 graphs) sourced from Comedy, Romance, and Sci-Fi genres. In our study, a subset of 100 graphs from each genre is designated for extracting notable patterns, while total of 60 graphs are reserved as test samples for a multi-llassfficttinn objective. This task involves predicting whether a movie graph corresponds to a Comedy, Romance, or Sci-Fi network.
Fingerprint (Morris et al. 2020). The Fingerprint dataset is multi- classification dataset obtained from fingerprint images, where 2, 149 fingerprints are transformed into graphs through image filter- ing and region extraction processes to isolate relevant areas. In our research, we engage in a 3-class classification endeavor utilizing this dataset. We extract patterns by sampling 100 fingerprint graphs from each of the three distinct classes and reserve 20 graphs from each class for the classification task.
ENZYMES (Borgwardt et al. 2005). The ENZYMES dataset comprises 600 protein tertiary struc- tures sourced from the BRENDA enzyme database, featuring six distinct enzymes. In our study, we focus on three out of the six enzymes to perform 3-class classification task using LLMs. Each class is represented by 80 graphs utilized for pattern discrimination, while the remaining graphs are earmarked for evaluation purposes.
Benzene SSanchez-Lengelingg et al., 2020). Benzene consists 12,000 molecular graphs from the ZINC15 (Sterling& & Irwin (215)) database, which can be classified into two classes. The main goal is to determine if a Benzene ring is existed in each molecule. In our settings, 200 graphs (1:1 for positive and negative) are sampled uniformly for LLM-based pattern detection, and hexagon made up of carbon atoms is used as the target pattern in LLM prompts.
Alkane-Carbony! (Sanchez-Lengeling et al. 2020). The Alkane- Caanonnl dataset comprises 4.326 molecule graphs categorized into two distinct classes based on the presence of specific functional groups. Positive samples correspond to molecules containing both alkane and carbonyl (C=0) fune- tional groups. To analyze patterns, we select 100 molecules from each class, aiming to identify whether a molecule includes both alkane and carbonyl functional groups.
Fluoride-Carbont (Sanchez-Lengelingg et al.) 2020). The Fluoride-Carbee Carbonyl dataset has 8,671 molecular graphs and its ground-truth explanation based on the particular combination of fluoride (F-) atoms and carbonyl (C=0) functional groups present in each molecule. For the pattern detection
https://www.pyz
18

---

Published as a conference paper at ICLR 2025
task, select 100 molecules from each class, aiming to identify whether molecule includes both fluoride atoms and carbonyl functional groups.
Table 13: Statistics of real-world datasets. * and Fluoride* represent the Alkane- Canbonyl and Pluorid-Carboony datasets, respectively.
Task
Domain
Name
Progress
Num
AVG. node
AVG. edge
AVG. density
discrimination
150
15.67
16.79
0.0725
MUTAG
classification
38
15.68
16.76
0.0723
overall
188
15.67
16.78
0.0725
discrimination
200
31.77
34.82
0.0445
OGBG-
Molecule
HIV
classification
40
30.50
33.45
0.0467
overall
240
31.65
34,69
0.0447
Bi-Class.
discrimination
500
21.99
23,40
0.0595
OGBG- BRRP
classification
50
28.24
30.64
0.0429
overall
550
22.56
24.06
0.0580
discrimination
500
19.56
96.18
0.2457
Social Network
classification
50
19.73
98.43
0.2466
BINARY
overall
550
19.57
96.39
0.2458
Benzene
overall
200
20.49
21.75
0.0547
Pattern Detection
Chemicals
Alkane
overall
200
41.54
42.72
0.0259
Fluoride*
overall
200
21.46
22.65
0.0508
discrimination
240
33.40
63.91
0.0731
Bioinformatics
ENZYMES
classification
60
31.93
62.78
0.0774
overall
300
33.15
63.72
0.0738
discrimination
300
2.92
2.13
0.2428
Computer Vision
Multi-Class.
Fingerprint
classification
60
2.93
2.20
0,2560
overall
360
2,92
2.14
0.2450
discrimination
300
12.95
67.21
0.3503
Social Network
IMDB-
classification
60
12.62
52.90
0.3279
MULTI
overall
360
12.89
64.83
0.3466
B.4 PROMPT
We collect the prompt for different tasks in Table T6 Further, provide the molecule description prompts in Table To enhance L.LM understanding, we use "both" to combine these two descrip- tions. The detailed prompt is: "In the context of molecular biology, you have been provided with a pattern motif to compare against a test molecule graph. The pattern is Terminology-bent based de- scription, which also can be represented Topology-basee description. ... Test-Molecular ... Now, please determine whether the pattern motif exists in the molecule graph by selecting either "The pattern does exist" "The pattern does not exist"."
Table 14: The descriptions of functional groups
Function group
Terminology-ban
Topollgyybbsse
Benzene (Cn)
benzene ring
(Node 0 Atom C, Node Atom C), (Node Atom
C, Node Atom C). (Node 2 Atom C, Node 3 Atom C), (Node Atom C, Node Atom C),
(Node 4 Atom C, Node 5 Atom C)
Alkane (C2nH2n+2) Alkane Carbonyl which
(Node Atom C, Node Atom H), (Node Atom C, Node Atom H), (Node 0 Atom C, Node 3
contains unbranched
alkane and carbonyl Atom H), (Node O Atom C, Node 4 Atom H)
functional group
Fluoride (COF2)
Fluoride Carbonyl which
(Node 0 Atom C, Node Atom O), (Node 0 Atom C. Node Atom F), (Node Atom C, Node 3
contains fluoride and
a carbonyl functional Atom F)
group
Further, for the molecular graphs, employ two different methods for graph description: adjacency list (A.L.) and edge list (E.L.). The conversion process involves three steps: Using the function Chem. MolFrommmmils from the Chem library in Python, extract the atoms and adjacency matrix
19

---

Published as a conference paper at ICLR 2025
of given molecule from its SMILES representation; 2. The atom and adjacency matrix information used to construct an undirected graph with the Python tool networkx. networkx.Graph; The graph is then described using node and edge information in either adjacency list (A.L.) or edge list (E.L.) format.
Taking a molecular graph with the SMILES of "CICC=OjOO-JNCCC-NHHHY as an example, the molecular graph be converted to textual format expressed in the following Table T5
Table 13: A.L. and E.L. on the molecular graph
A.L
E.L.
describes an undirected graph among 0, I, 2. describes an undirected graph among node O,
3, 4, 5, 6, and 7. In this graph: Nodo 0 (atom: 2, 3, 4, 5, 6, and 7. Node 0 (atom: C) is con-
C) connected to nodes (atom: C), (atom:
nected to Node (atom: C). AnNode 0 (atom: C)
N).AnNode 1 (atom: C) is connected to nodes 0
connected to Node 4 (atom: N). An.ne 1 (atom:
(atom: C), (atom: O), 3 (atom: noode
C) is connected to Node (atom: O). Anode
2 (atom: O) is connected to nodes I (atom:
(atom: C) is connected to Node 3 (atom:
C). Noode 3 (atom: O) is connected to nodes
O). AnNode 4 (atom: N) connected to Node 5 (atom: C). Anode 5 (atom: C) is connected to
(atom: C). 4 (atom: N) is connected to
nodes 0 (atom: C), 5 (atom: C). Node (atom:
Node 6 (atom: N). 5 (atom: C) is con-
C) is connected to nodes (atom: N), 6 (atom:
nected to Node 7 (atom: N).
N), 7 (atom: nndee (atom: is connected to nodes (atom: C). 1))mm nNode 7 (atom: N) is con-
nected nodes 5 (atom: C).
Table 16: Summarization of prompts
Task
Prompt
Generate graph that includes only one (terminology-base pattern description). the node number is 20. Each node at least has one edge.
Pattern
translation
Identify the occurrence patterns of the given motif in the graph. The given pattern (terninology-be (topology-basee based) pattern description ). The graph is...
Pattern
detection
Modify the graph to include the given pattern (terminology- (topology-basco
Pattern
pattern description ). The pattern ... The graph is...
modification
Pattern
Given a pair of isomorphic graphs, determine the node correspondence between the graphs. The first graph is... The second graph is...
isomorphic
mapping
K-core
Determine the 3-core subgraphs in the graph. The graph
detection
Frequent subgraph
Consider the following graphs and summarize the common patterns in them. No. The graph is No. 2. The graph is...
extraction
Discriminative
You are provided two of graphs. The first is: No. The graph is... No. I. The graph is... The second set is: No. 1. The graph is... No. 2. The graph What are the differences between the two sets? Show the special pattern in Setl (Set2)
pattern
learning
You are an expert at classifying different types of graphs based on whether they con- tain specific patterns. The first type of graph includes patterns such as: No.1 the pattern is.. No.2 The pattern is...Th second type includes patterns like: No.1 the pattern No. The pattern is... Now, plcase identify which type the given graph is most likely belong to. The graph is...
Classification
20

---

Published as a conference paper at ICLR 2025
C REAL-WORLD APPLICATIONS
C.I EXPERIMENTAL SETTINGS
The evaluation setup involves comparing GPT-4, GPT-4o, and Olmini models in real-world applica- tions, following pipeline similar to that proposed for synthetic datasets to prompt Large Language Models (LLMs) comprehend graph patterns. Details are depicted in Table 17 In classification tasks, we sample five graphs from each class for comparison within an turns, requesting LLMs to discriminate significant graph patterns within a designated target set. All classes within the dataset are utilized as the target set for the pattern discrimination process, and the discrimination process is performed twice for complementary insights. After filtering out discriminate patterns, we prompt LLMs to classify test graphs individually. An effective LLM-based graph reasoning technique is characterized by the ability to discriminate more patterns and achieve satisfactory performance in classifications, with accuracy serving as the key metric for quantitative assessment. Notably, these settings here apply to both binary and multi-label classification tasks.
Table 17: Hyper parameters for real-world tasks.
Binary Classification
Multi-label Classification
Param
OGBG-
OGBG-
IMDB BINARY
IMDB-
MUTAG
ENZYMES
Fingerprint
HIV
BBBP
MULTI
# Sampling
10
5
5
5
5
# Turns
16
40
100
100
32
40
40
D THE FULL RESULTS FOR PATTERN DETECTION
The whole results of terminology-based and topology-basee pattern detection are shown in Table and Table 19 respectively.
Table 18: The Fl score for terminology-boe graph detection
Undirected patterns
Dndirected patterns
Scale
Models
Triangle A.L.
T-tringle Square
Diamond
House
V-S
FFL
FBL
D-Diamond
E.L A.L. E.L. A.L. E.L. A.L. E.L
A.L.
E.L
A.L.
E.L
A.L.
E.L.
A.L.
E.L. A.L.
E.L
GPT-4
.632 .581 .151
002
.13
.003
.352
.380
.279
.448
.396
GPT-4o
.748 .702
.210
.20
.149
.132
317
309
.008
.033
.477
.490
.478
450
.10
.357
.411
.360
Mixtral
.694 .622
.224
.211
.128
.002
.23
.181
.121
.118
.117
.110
.191
.211
.110
.145
.238
.140
Small
Llama
.681 .693 .189 .193
118
.106
115
.15
.042
.021
.486
.527
.388
388
.373
.349
.425
.367
Gemini
712 .725 .207
.274
150
.176
.23
.262
.104
.225
.287
.281
.263
.267
.14
.13
.149
.111
Claude
782 .740 .217
.222
.17
149
.23
.259
.210
.171
.385
.365
300
.277
.62
.265
.229
.201
Ol-mini
828 .832
.593
.578
.335
.316
.663
.684
.054
.066
.584
.600
.605
.602
.567
.584
.504
.488
GPT-4
.356 .345 .061
.031
.10
004
.083
.057
.017
.000
101
.130
.085
.117
0554
108
.035
.023
GPT-4o
.671
.563
.108
120
102
.114
.24
.255
.024
.034
.247
.300
.246
191
.141
163
.097
.081
Mixtral
474 .478 .104
.118
006
032
132
.125
.000
007
.040
.053
.049
114
J60
0081
007
.003
Medium
Llama
.618 .584 .059
.043
0082
.070
.140
.108
.020
.000
.207
.210
.153
166
.119
.134
.051
.043
Gernini
.678 .658 .197
.091
.107
.247
.299
.155
.133
.148
.111
.012
.018
Claude
.725 .673 .144
.157
.130
.161
.205
.130
.141
.181
.104
.052
.006
.009
01-mini
848 .777 .409
.335
.274
.535
.567
.009
.000
.277
.516
.611
.637
.603
.594
.318
.327
GPT-4
.057 .086 .003
..00
.003
.000
.001
.002
.000
.000
.067
.061
.066
.064
.031
.059
,029
.016
GPT-4o
.404 .317 .016
.011
.063
.000
.156
.226
.151
.14
.111
.066
.091
.058
Mixtral
319 .233 .016
.014
0005
.064
.056
002
.016
.030
.046
.155
.055
.008
.012
Large
Llama
361 .384 .012 .013
.018
0011
025
.30
.020
.220
111
.123
.133
.167
.054
.073
.02
.014
Gemini
.600 .496 .035
.014
004
0011
009
006
.038
.047
101
.133
.174
166
.110
.137
.001
.000
Claude
.300 .278 .013
.20
020
023
051
044
.020
.200
.074
0054
.147
.138
.066
.078
.004
.007
O1-mini
,636 .428
.065
002
009
026
103
025
.000
.000
533
5660
665
663
568
552
.363
.367
The figures are shown as terminology- pattern detection for all scales in Figure and topology- based pattern detection for all scales in Figure
21

---

Published as a conference paper at ICLR 2025
Table 19: The Fl score for topology-based graph detection
Undirected patlerns
Dndirected patterns
Scale
Models
Triangle
T-triangle
Square
Diamond
House
V-S
FBL
D-Diamond F.I.
A.I., E.I. A.I., E.T. A.I. E.L. A.I. E.L. A.I. F.T.
A.T..
E.I.
A.I.
E.I.
A.I. E.I. A.I.
GPT-4
.633 .584 .011
.056
001
.099
.162 .110 .022 .000
.415
475
.346
429
.23
.422
.47
.397
GPT-4o
.717 .706 .194
.143
.118
.111 .233
.227 .005 .015
.537
.489
.296
.383
.407
.287
.285
.269
Mixtral
.20 .550 .108
.134
.12
.107
.170
.157
.77
.191
.227
.287
.364
.276
.352
.255
.257
Small
Llama
.45 .678 .122
.145
076
.74
.112
.157 .005
.097
.476
.488
.266
.361
.382
.386
.388
.283
Gemini
651 .666 .166
192
.13
1175
117
.171
.122
192
.304
.171
.266
.23
.144
.205
.203
.126
Claude
.730 .713 .186
.269
.122
160
.263
.50
.241
.249
.370
.329
.302
.393
.322
.257
.206
.128
O1-mini
.82 .821 .617
.499
365
.364
.633
574
.107
.249
.588
.599
.678
.670
.572
.566
.492
.477
GPT-4
.273 .329 .032
045
.064
.688
.000
.177
.256
.072
.210
.129
.099
.051
.041
GPT-4o
.657 .575 .183 089
086
066
143
205
.000
000
.298
.289
.072
.58
146
154
.046
.053
Mixtral
414 .430 .057 .074
039
0051
0051
.139
.000
0000
.040
.127
.188
.180
009
.095
.021
.029
Medium
Llama
299 .290 .029
.032
050
061
.081
.094
.000
020
193
.213
.94
.134
059
124
.061
.035
Gemini
484 .632 .037
.075
.123
0088
.033
.124
.000
.030
.140
.037
.170
1662
.109
.098
.062
.000
Claude
.671 .651 .100
.159
.097
.127
.247
.253
.040
.040
.310
.166
.204
.233
.084
.092
.019
.035
01-mini
.83 .749 .488
.367
.449
.417
.494
.557
.000
.024
.471
.496
.690
.625
.567
.591
.298
.301
GPT-4
.067 .113 .004
.002
.000
.002
.003
.005
.000
.000
.194
.230
.068
.133
.108
.085
.007
.010
GPT-4o
.327 .257 .018
.015
.03
008
027
005
.000
.000
.240
.158
.065
.180
.119
096
.055
.014
Mixtral
.177 .262 .006
.010
000
009
0446
0025
.000
.000
.043
.086
.144
.184
.021
.037
.006
.013
Large
Llama
.855 .068 .012
.0.4
0020012222
0001
047
.08
020
.042
.094
.106
.070
.020
.134
.003
.013
Gemini
186 .535
001
.002
.027
.064
.025
.122
.152
.074
.016
.000
Claude
454 .286
0011
.015
015
048
072
040
.88
.162
.151
110
117
.080
.011
.040
O
511 5544
005
.049
044
050
134
114
.000
.000
.18
.488
.608
625
5591
.595
.340
.343
C214
Hecral
Liems
Cameras
Gaude
01 mert
0.6
large
El
0.2
0.0
Mitrangle
D.Ulamond
Figure 7: The score of topology-based pattern detection (small and medium scale)
Small
GPT4
GFT-4
Matral
Lima
Gerrini
Claude
02 mini
Medium
CPT-4o
Claude
03-mini
0.6
large
GF1--1
GP1-4o
Mictral
Liaraa
Guriini
claude
02.mini
0.4
0.2
Trianglo
T-triang o
Square
Diamond
House
V-5
FFL
FBL
D-Diamond
Figure 8: The F1 score of topology-basee pattern detection (small and medium scale)
E PSEUDO-CODES
E. FREQUENT SUBGRAPH EXTRACTION
The pseudo-code of the algorithm is shown in Algorithm
E.2 DISCRIMINATIVE PATTERN LEARNING
The pseudo-code of the algorithm is shown in Algorithm
F BIRD-VIEW
To show the model's ability across various tasks, provide bird-view of the models.
For each LLM, we select the best performance from either edge list or adjacency list graph descrip- tions and then calculate the models' average scores across small, medium, and large-scale datasets.
22

---

Published as a conference paper at ICLR 2025
Algorithm 2 Frequent Subgraph Extraction
1: Input: A graph dataset G 92...........9 9u.. frequency threshold fihres
2: Output: Frequent patterns and accuracy
for iteration = 100 do
4: Randomly select graphs from form a subset Gp
5: Prompt LLMs to extract the set of frequent patterns based on Gp
6: Initialize Acc; 0
7:
for each pattern p E do
if p appears more fahres graphs in Gp then
9:
Increment Acc;
10: Compute Acc;
pattems
11:
Compute overall accuracy Ace of ierpiioss 12: Return: Extracted frequent patterns and accuracy
E Acc,
Algorithm 3 Discriminative Pattern Extraction and Evaluation
1: Input: Two graph dataset G' (gg. .!....,gh..
with label L1 and G² - .2........................ pm1)
with label
L2
Output: Discriminative patterns and Metries
3: Step 1: Pattern Extraction
4: for each iteration do
5: Sample equal number of graphs from G and GH to form balanced dataset G.
Prompt LLMs to identify discriminative patterns from G.
7: Add the extracted patterns into the set
Step Pattern Filtering
9: for each pattern p E P do
10: Compute the occurrence of p in G and G²
11:
if (occurrence(p, GO) 2 90% and occurrence(p, G²) 10%) OR (occurrence(p, G2) 90%
and occurrence(p, G 10%) then
12:
Retain p discriminative pattern 13: Obtain final discriminative pattern set Piinl
14: Step 3: D.P. Computation
Compute the discriminative pattern ratio as:
D.P. # Discriminative patterns in Panal
#xxtracted patterns in
16: Step 4: Classification Accuracy Computation
17: for cach new graph in the test set Grest do Prompt LL to predict the lahel of based on Priaal
18:
19: Compute the prediction accuracy Acc the proportion of correctly predicted labels
20: Return: Panat, Acc, and D.P.
Furthermore, we average the scores across different graph patterns. Finally, we rank the models for each task and provide an overall ranking.
Table 20: Model rank across various tasks
Terminology-baan -ased patterns
Topology based patterns
Data-driven patterns
AVG rank. rank.
Pattern transia-
Graph modifica- tion
pattern
Isomophic Graph mapping modifica- detection tinn
pattern
K-core
Frequent subgraph extraction
Discriminative
detection
patlern
tion
leamming
GPT-4
GPT-4o
2
4
2.2
Mixtral
Ilama
4
5
4.3
Gemini
3
6
3
5.2
Claude
O1-mini
1
1
2.1
In Table 20 O1-mini achieves an average rank of 2.1, outperforming other models in most cases while still facing challenges in isomorphic mapping and discriminative pattern learning tasks. In-
23

---

Published as a conference paper at ICLR 2025
terestingly, GPT-4o demonstrates balanced performance across all tasks. Overall, recommend using O1-mini, GPT-4o, and Claude for solving graph pattern tasks.
G ALGORITHM SUMMARY
To ensure comprehensive evaluation that encompasses both hop-performing results and identified mistakes from under-performing models, we meticulously examine 10% of the samples across all LLMs utilized in diverse tasks. The descriptions of specific procedures and their respective occur- rence rates in varied scenarios are detailed in Table and Table 22
H EXPERIMENTS ANALYSIS
H.1 UNINTENDED MODIFICATION IN PATTERN TRANSLATION
LLMs generally follow the logic of first creating the target pattern and then adding extra edges to expand into larger graph, as shown in Appendix G To illustrate this process, we analyze output from GPT-4 as an example of how LLMs perform graph translation in tailed-triangle generation:
Here's how the graph can be formulated: **Tailed Triangle Edges**: (1, 2), (2. 3), (3, 1), (1, 4)
This forms the tailed triangle. **Connecting Remaining Nodes**: To ensure each of the remaining nodes (5 to 20) has at least one edge and avoid forming any additional tailed triangles,
can simply connect each new node to the next one in sequence. This will form a chain that can connected back to one of the nodes in the tailed triangle to ensure the graph is undirected and connected. Here's the complete edge list: 1. (1, 2) 2. (2, 3) 3. (3, 1) (1, 4) 5. (4, 5) 6. (5, 6) 7. (6, 7) 8. (7, 8) 9. (8, 9) 10. (9, 10) 11. (10, 11) 12. (11, 12) 13. (12, 13) 14. (13, 14) 15. (14, 15) 16. (15, 16) 17. (16, 17) 18. (17, 18) (18, 19) 20. (19, 20) 21. (20, 3) This last edge connects the chain back the triangle, ensuring the graph is undirected and connected.
The connection (20, 3) is an unintended modification, as the graph is already connected without it. Another example is from Gemini while generating the VS pattern. The example is follows:
Here's directed graph with 20 nodes and single V-structure, along with the edge list representation: #+V-Structure:# * Node 1 -> Node 20 # Node 2 -> Node 20 **Remaning Graph Structure (ensuring
each node has at least one edge):** We'll create a cycle involving the remaining nodes and then add a few extra edges for variety: 3 -> 4 -> 5 -> -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14
-> 15 -> 16 -> 17 -> 18- -> 19 ~> (This forms the cycle) 1 -> 5 (Additional edge) * 10 -> 18
(Additional edge)
Nodes 1, 2, and 20 already form VS structure, but Gemini creates cycle and adds two additional edges to connect all the nodes in the graph. This results in the formation of another VS structure involving nodes (1, 4, 5).
H.2 LLMS' BEHAVIORS IN THE MODIFICATION CASE
According the algorithms summarized in Appendix G find that most responses follow strategy where they first select subset of nodes equal in number to the target pattern and then apply modifications to match the given pattern. Second, we calculated the average degree of the nodes selected by the LLMs and summarized this information in Table
We find that the nodes selected by LLMs consistently have higher degrees than the average node degree of the graph, particularly in Medium and Large scales. This suggests that LLMs are more likely to select digher-degree nodes for editing.
H.3 HALLUCINATION IN PATTERN DETECTION
The hallucination happened graph understanding, which means adding or ignoring edges on the graphs. We analyze the hallucinations that occurred during terminology-base pattern detections. After analyzing in Appendix G we find the behavior of LLMs on pattern detec- tions are: (1) LLMs often provide solution without actually executing the algorithm. This leads to failures, such as Gemini and GPT-4 in terminology-bar -based pattern detection and GPT-4o in topology- based pattern detection. (2) In cerminology-based pattern detection tasks, LLMs are more flexible
and topology-based
24

---

Published as a conference paper at ICLR 2025
Table 21: Overview of algorithms employed by LLMs for graph pattern comprehension tasks
Method
Task
Item
Description
Use external tools e-g. NetworkX
Pattern Translation
Directly give an answer
C
1. Construct a structure based on the given patterns.; 2. Add random paths
or trees among other nodes.
A
1. Select set of nodes.2. Modify the subset to match the target pattern.
Pattern Modification
B
A special algorithm house 1. Identify triangle; 2. Modify square based the triangle.
A special algorithm on house 1. Identify a square; 2. Modify a triangle based on the square. Assume the graph already meets the requirements and avoid making modifications.
Terminology -based
D
A
Directly give an answer Use external tools e-g. NetworkX
B
Draw figure of graph and give answer Traverse every node, and check whether this node and its neighbors can form the pattern.
Pattern Detection
E
Generate all possible node combinations and verify one by one.
Traverse all possible edge combinations, and verify if they form the pattern. A special algorithm on house: Identify triangles as roof first and check if the triangle has a square as its base.
H A special algorithm on the house: Identify squares as the base first and check if the square has triangle its roof.
I
Only give the process but answers
A
1. Count the degrees of nodes in both graphs. 2. Identify nodes with matching degrees and assign them mapping pairs. Directly map the edge connections. Provide example code (networkx package) only, without displaying the re- sults.
Isomorphic Mapping
C
D
Using the VF2 algorithm.
Topology -hased
Pattern Modification
1. Select set of nodes. 2. Adjust the subset to match the target pattern.
A Directly give an answer Traverse every node, and check whether this node and its neighbors the target pattern. Generate all combinations with the specified number of nodes and select those that meet the pattern definition. Traverse all edges, and determine if they form pattern based their com- mon nodes.
Pattern Detection
D
E
Only give the process but no answers Using external tools e.g. networkx
F
A
Using external tools e.g. networkx
Dense Subgraph
B
1. Count the degrees. 2. Modify the graph. 3. Repeat the steps iteratively. Assume every node meets the degree requirement and take no further action. Collect nodes with degree greater than 3.
C
Mining (K-core)
D
Directly give an answer
Data-driven
Frequency Subgraph
1.List common graph patterns, such triangles, stars, and loops; Verify whether these patterns exist the given graphs.
Extraction
1. Check the nodes by their IDs; 2. Examine the neighbors of each node to determine if their combinations appear other graphs.
D
Check the patterns by node IDs. For example. I.Nodes connected to others with smaller IDs. Nodes connected only one other node. No solution
Discriminative Pattern Learning
1. Assume the patterns are common structures; Identify which nodes exhibit these patterns; 3. Compare the differences in their connections Check the edge connection patterns to determine if they are identical.
B
25

---

Published as a conference paper at ICLR 2025
Table 22: Percentage of occurrence for each algorithm during LLM-basee graph pattern compre-
hension
Method
Task
Item
Llama
Gemini
Mixstral
GPT-4
GPT-4o
Claude
Q1-mini
A
100.00%
0.00%
0.00%
0.00%
0.00%
0.00%
0.00%
Pattern
B
0.00%
0.00%
0.00%
0.00%
0.00%
100.00%
0.00%
Translation
0.00% C
100.00%
100.00%
100.00%
100.00%
0.00%
100.00%
A
100.00%
85.00%
80.00%
75.00%
95.00%
80.00%
100.00%
Pattern
B
0.00%
10.00%
20.00%
0.00%
5.00%
20.00%
0.00%
Modification
C
0.00%
0.00%
0.00%
25.00%
0.00%
0.00%
0.00%
0.00%
15.00%
0.00%
0.00%
0.00%
0.00%
0.00%
0.00%
34.00%
24.00%
4.00%
0.00%
24.00%
18.00%
Temminology-baa based
6.00%
0.00%
4.00%
0.00%
6.00%
0.00%
20.00%
C
0.00%
4.00%
0.00%
0.00%
4.00%
0.00%
0.00%
D
0.00%
4.00%
24.00%
24.00%
38.00%
12.00%
4.00%
Pattern
54.00%
12.00%
20.00%
16.00%
38.00%
60.00%
28.00%
Detection
40.00%
8.00%
14.00%
16.00%
0.00%
4.00%
18.00%
0.00%
0.00%
8.00%
2.00%
12.00%
0.00%
2.00%
0.00% H
0.00%
2.00%
2.00%
0.00%
0.00%
0.00%
10.00%
36.00%
4.00%
38.00%
2.00%
0.00%
0.00%
A
0.00%
20.00%
60.00%
70.00%
50.00%
0.00%
100.00%
Isomorphic Mapping
B
100.00%
10.00%
20.00%
0.00%
50.00%
100.00%
0.00%
0.00%
70.00%
0.00%
30.00%
0.00%
0.00%
0.00%
0.00%
0.00%
20.00%
0.00%
0.00%
0.00%
0.00%
Pattern Modification
A
100.00%
100.00%
100.00%
100.00%
100.00%
100.00%
100.00%
Topology-hand hhased
0.00%
43.33%
10.00%
0.00%
0.00%
53.33%
10.00%
0.00%
36.67%
16.67%
33.33%
36.67%
36.67%
36.67%
Pattern
C
66.67%
16.67%
33.33%
33.33%
43.33%
10.00%
50.00%
Detection
D
33.33%
3.33%
40.00%
33.33%
0.00%
0.00%
0.00%
E
0.00%
0.00%
0.00%
0.00%
20.00%
0.00%
0.00%
0.00%
0.00%
0.00%
0.00%
0.00%
0.00%
3.33%
0.00%
0.00%
0.00%
20.00%
0.00%
0.00%
0.00%
Dense Subgraph
0.00%
100.00%
0.00%
80.00%
100.00%
80 80.00%
40.00%
0.00%
0.00%
0.00%
0.00%
0.00%
20.00%
60.00%
Mining (K-core)
D
100.00%
0.00%
100.00%
0.00%
0.00%
0.00%
0.00%
A
0.00%
0.00%
0.00%
0.00%
0.00%
100.00%
0.00%
Data-driven
Frequency
B
100.00%
30.00%
10.00%
0.00%
40.00%
0.00%
100.00%
Subgraph
C
0.00%
0.00%
0.00%
100.00%
60.00%
0.00%
0.00%
Extraction
D
0.00%
0.00%
90.00%
0.00%
0.00%
0.00%
0.00%
0.00%
70.00%
0.00%
0.00%
0.00%
0.00%
0.00%
Discriminative
0.00%
10.00%
0.00%
0.00%
0.00%
0.00%
20.00%
Pattern Learning
100.00%
90.00%
100.00%
0.00%
0.00%
100.00%
80.00%
Table 23: Degree analysis in pattern modification tasks
Scale
AVG. degree
Llama
Gemini
Mixtral
GPT-4
GPT-4o
Claude
O1-mini
Small
3.32
3.41
2.60
2.64
3,66
3.61
3.75
3.65
Medium
2.15
2.30
2.98
2.69
2.39
2.78
2.95
2.95
Large
2.36
2.80
2.89
3.10
2.38
3.03
3.39
3.15
26

---

Published as a conference paper at ICLR 2025
to utilize different algorithms. For instance, LLMs decompose house pattern into separate triangle and square detections, transferring the problem into simpler tasks. (3) We observe that most LLMs prefer to list all possible combinations first and then check whether they match the target pat- tern. However, their accuracy varies significantly. To explore underlying failure reasons, we further calculate the precision and recall of detected patterns. These two metrics provide insight into the type of hallucinations that occur when LLMs perform pattern detection. A low precision suggests that LLMs hallucinate extra edges in the extracted patterns, whereas a low recall indicates that some edges in the input graph were overlooked by LLMs.
As shown in the Table we find that LLMs achieve higher precision than recall. This indicates that most emrors come from the overlooked edges. Furthermore, most LLMs show performance drops when transitioning from terminology-base -based to topology-bane based detection. The terminology helps reduce the hallucination.
Table 24: Precision and recall on the large scale triangle dataset
Llama
Gemini
Mixstral
GPT-4
GPT-4o
Claude
O1-mini
Precision
0.599
0.622
0.543
0.449
0.609
0.763
0.776
Terminology-basee
Recall
0.294
0,493
0.224
0.039
0.256
0.304
0.416
Precision
0.190
0.484
0,507
0.409
0.586
0.764
0.765
Topology-based
Recall 0.052
0.308
0.142
0.050
0.195
0,249
0.387
Precision
-0,409
-0.138
-0.036
-0.039
-0.023
0,001
-0.011
Decrease
Recall
-0.242
-0.185
-0.082
0.012
-0.062
-0.056
-0.029
H.4 DEGREES ANALYSIS K-CORE
We provide example explain why the 3 is important for LLMs in k-core solution. Here is an output of -1-mini:
After analyzing the given graph, we aim to identify the **3-core** subgraphs. A "*K-core** of a graph is maximal subgraph in which every vertex has at least degree **k**, ### Step-by-Step Analysis: 1. Initial Degrees: **Nodes with degree 2 3:*0 0, 2, 8, 9, 12, 13, 15, 19 **Nodes with degree 3:*4 4,5, 5, 6, 7, 10, 11, 16, 17, 18, 20, 21
**Iterative Pruning:** **First Removal:** Eliminate nodes with degree 3. This affects the remain- ing nodes' degrees. **eecacullation=** After removal, the degrees of > the remaining nodes drop below 3: For example, node 0 initially has degree 3 but loses connections as other nodes are pruned. Suubeequent Removals: Continually removing nodes with degrees dropping below leads to the eventual elimination of all nodes.
**Final Outcome:** No subset of nodes remains where each node has at least degree 3. Therefore, there are **no 3-core subgraphs** in the given graph.
We observe that LLMS do not calculate the exact node degree but instead evaluate whether it is greater less than Therefore, the critical factor for LLMs to make accurate predictions occurs when the node's 's degree is around 3.
I ANALYSIS ON CHAIN-OF- THOUGHT PROMPTING
We have conducted several experiments to illustrate the effect of Chain-of- -hain-of-Thought prompting on both terminology-be
and topology-based pattern detection tasks using edge list descriptions. Specifically, we utilize 3 cases with the reasoning process demonstrations to require LLMS to de- tect triangle and house patterns in small-scale graphs and triangle patterns in medium-scale graphs. The results are summarized in Table
Table 25: Performance comparison between zero-shot and CoT promptings in pattern detection.
Zero-shot house(S) triangle(M) triangle(S) house(S) triangle(M) Avg. Increase
CoT
Method
Model
triangle(S)
Gemini 0.725
0.225
0.218
0,822
0.103
0.513
0.090
Terminology-bused 01-mini
0.832
0.066
0.409
0.811
0.011
0.727
0.081
Gemini 0.651
0.122
0.484
0.767
0.263
0.596
0.123
Topology-basee -based
0m-mini
0.832
0.000
0.833
0.736
0.075
0.756
40.033
27

---

Published as a conference paper at ICLR 2025
Overall, these results indicate that CoT prompting generally enhances pattern detection performance, particularly in terminology-bass baaee tasks. However, the effect of CoT limited when the models already acheive high scores in the zero-shot setting. This aligns with previous studies that in-context learning does not always enhance the ability of LLMS to understand graph structures Wang et al. (2024)
Fatemi al. 2023
SPLIT TABLES
Here split the tables make them clearer read.
Table 26: Terminology-basee graph modification in A.L. description
Gemini
Mixtral
Llama
Claude
GPT-4
GPT-4o
O1-mini
A.L.
S.
L.
M.
L.
M.
M.
S.
S.
L.
M. L.
S
0.06
0.28
0.20
0.58
0.64 0.34 0.48 0.40
0.26
0.50
0..4
0.12
0.24
0.36 0.44 0.38 0.64 0.58
S
0.53
0.48
0.32
0.77
0.64
0.62
0.50
0.32
0.50
0.50
0.26
0.18
0.16
0.20
0.71 0.68
0.54
0.95 0.98 0.94
D
-
0.27
0.42
0.28
0.29
0.28
0.40
0.51
0.70
0.64
0.54
0.84
0.68
0.15
0.12 0.24
0.41
0.44
0.28
0.77
0.72 0.88
F
0.30
0.58
0.52
0.29 0.56
0.48
0.29
0.60
0.50
0.36
0.56 0.62
0.26 0.42 0.46
0.18 0.24
0.20
0.40
0.76 0.74
Table 27: Cerminology-basee graph modification in E.L. description
Gemini
Mixtral
Llama
Claude
GPT-4
GPT40
O1-mini
E.L.
S.
M.
I.
M.
T..
M.
S.
M.
S.
M.
L.
S.
L.
M. L.
S
0.13
0.36
0.40
0.31 0.48 0.72 0.26 0.48 0.54
0.28
0.48 0.14
0.09
0.18 0.14
0.34
0.46 0.58 0.37 0.74 0.64
S
0.53
0.28
0.22
0.82
0.76 0.86
0.42
0.36
0.44
0.78
0.64
0.34
0.42
0.38 0.32
0.79
0.72
0.64
0.97 0.92 0.96
0.15
0.48
0.26
0.32
0.56
0.40
0.38
0.64
0.52
0.14
0.24
0.32
0.36
0.20
0.88
F
0.22
0.44
0.28
0.52
0.36
0.28
0.58
0.50
0.24
0.56
0.15 0.40
0.16
0.18
0.22
0.34
0.76 0.64
Table 28: Terminology-bant based graph detection in A.L. description
Undirected patterms
Dndirected patterns
Scale
Model
Triangle
T-triangle
Square
Diamond
House
V-S
FFI.
FBI.
D-Diamond
GPT-4
.632
.151
.069
.113
0006
.352
.89
.191
.448
4o
.748
.210
.149
337
.008
.47
.478
.410
.411
Mixtral
.694
.224
.128
.232
.121
.117
.191
.110
.238
Small
Llama
.681
.189
.118
.185
.042
.486
.358
.373
.425
Gemini
.712
.207
.150
.230
.104
.287
.263
.194
.149
Claude
.782
.217
.178
.273
.210
.385
.300
.262
.229
01 3l-mini
828
.593
.335
.663
.054
.584
.605
.567
.504
GPT-4
.356
.061
.010
.083
.017
.101
.085
.054
.035
GPT-4o
.671
.108
.242
.024
.247
.246
.141
.097
Mixtral
.474
.104
.040
.049
.060
.007
Medium
Llama
.059
.207
.153
.119
.051
Gemini
.678
.197
.188
.148
Claude
.725
.144
.130
.205
.130
.181
.104
.006
O1-mini
848
.409
.335
.527
.611
.603
.318
GPT-4
.057
.003
.003
.001
.000
.067
.066
.031
.029
GPT-4o
.004
.016
.011
.063
.000
.156
.151
.111
.091
Mixtral
.319
.166
.005
.064
.000
.016
.046
.034
.008
Large
Ilama
.61
.022
.018
.025
.020
.111
.133
.054
.022
Gemini
.600
.055
.043
.099
.038
.101
.174
.110
.001
Claude
.300
.013
.020
.051
.020
.074
.147
.066
.004
01-mini
.636
.065
.039
.103
.000
.533
.635
.568
.363
28

---

Published as a conference paper at ICLR 2025
Table 29: Terminology-baen graph detection in E.L. description
Undirected patterns
Dndirected patterns
Scale
Model
Triangle
T-triangle
Square
Diamond
House
V-$
FFI.
FBI.
D-Diamond
GPT-4
.581
.107
.026
.113
.003
.380
.406
.279
.396
GPT-4o
.702
.250
.132
.309
.053
.490
.450
.357
.360
Mixtral
.622
.211
.022
.181
.188
.110
.241
.145
.140
Small
Llama
.693
.193
.106
.195
.011
.527
.388
.349
.367
Gemini
.725
.274
.176
.262
.225
.281
.267
.193
.111
Claude
.740
.229
.149
.259
.171
.365
.277
.265
.201
O1-mini
832
.588
.316
.684
.066
.600
.602
.584
.488
GPT-4
345
.031
.004
.057
.000
.130
.117
.108
.023
GPT-4o
.563
.120
.114
.215
.034
.300
.191
.163
.081
Mixtral
.478
.118
.032
.125
.007
.053
.149
.081
.003
Medium
Llama
.584
.043
.070
.108
.000
.210
.167
.134
.043
Gemini
.658
.218
.107
.299
.000
.133
.167
.111
.018
Claude
.673
.157
.161
.210
.016
.141
.173
.052
.009
O1-mini
.777
.533
.244
-677
.000
.116
.637
.594
.327
GPT-4
.086
.005
.000
.002
.000
.061
.064
.059
.016
GPT-4o
337
.055
.012
041
.000
.226
.140
.066
.058
Mixtral
233
.014
.006
.056
.022
.030
.155
.055
.012
Large
Llama
384
.013
.011
030
.020
.123
.167
.073
.144
Gemini
.966
.014
.011
.063
.047
.103
.166
.137
.000
Claude
.278
.020
.023
044
.020
.054
.138
.078
.007
O1-mini
.488
.072
.026
.025
.000
.560
.637
.592
.367
Table 30: Topology-based graph modification in A.L. description
Gemini M.
Mixtral
Llama
Claude
GPT-4
GPT-4o
O1-mini
A.L.
S.
L.
M.
S.
L
+
H 0.34
0.20
0.78
0.78
0.58 0.66
0.57
0.52 0.48 0..45 0.64 0.44
3.34 0.56 0.56 (066 0.70 0.68
(0.61 0.82 0.80
0.45
0.34
0.78
0.60
0.65
0.74
0.60
0.56
0.75
0.66
0.82
0.86
D S 0.12
0.24
0.58
0.42
0.60
0.29
0.26
0.40
0.12
0.26
0.36
0.16
0.48
0.40
0.41
0.41
0.40
0.48
0.55
0.56 0.64
- B 0.28
0.38
0.50
0.52
0.40
0.64
0.55
0.68
0.70
0..7 0.54 0.40
0.48 0.68
0.76
0.57
0.57
0.80
0.80
0.41 0.76 0.68
Table 31: Topology-bese based graph modification in E.L. description
Gemini
Mixtral
Llama
Claude
GPT-4
GPT400
O1-mini
E.L.
S.
M.
L.
S.
M.
L.
S.
M.
L.
S.
M.
L.
S.
M.
L
S.
M.
L.
S.
M.
L.
S
0.22
0.42
0.26
0.66 0.68 0.54
0.45
0.50
0.48
0.38
0.54 0.42
0.24
0.60 0.52
0.36 0.52 0.60
0.46 0.68 0.74
S
0.48
0.40
0.52
0.67
0.70 0.62
0.69
0.46
0.62
0.72
0.74
0.74
0.67
0.62
0.20
0.67
0.68
0.74
0.88
0.86 0.84
D
S
0.11
0.32
0.32
0.40
0.32
0.44
0.29
0.30
0.20
0.11
0.22
0.48
0.06
0.30
0.20
0.20
0.18
0.36
0.24
0.36 0.28
F
B
0.20
0.32
0.34
0.52
0.40
0.50
0.29
0.44
0.34
0.27
0.46
0.48
0.44
0.62
0.52
0.32
0.66
29

---

Published as a conference paper at ICLR 2025
Table 32: Topology-basee graph pattern detection in A.L. description
Undirected patterns
Dndirected patterns
Scale
Model
Triangle
T-triangle
Square
Diamond
House
V-S
FFL
FBL
D-Diamond
GPT-4
.653
.051
.041
.162
.002
.415
.346
.423
.477
GPT-4o
.717
.118
.233
.005
.537
.296
.407
.285
Mixtral
.520
.132
.170
.105
.287
.276
.255
Small
Llama
.545
.076
.112
.005
.266
.382
.388
Gemini
.651
.133
.177
.122
.266
.194
.203
Claude
.122
.263
.241
.302
.322
O1-mini
.322
.617
.365
.633
.107
.572
.492
GPT-4
.273
.032
.012
.064
.000
.177
.072
.129
.051
GPT-4o
.657
.183
.086
.143
.000
.298
.072
.146
.046
Mixtral
.414
.057
.039
.051
.000
.040
.188
.089
.021
Medium
Llama
.299
.029
.050
.081
.000
.193
.094
.059
.061
Gemini
.484
.037
.123
.033
.000
.140
.170
.109
.062
Claude
.671
.000
.097
.247
.040
.310
.204
.084
.019
O1-mini
.833
.488
.449
.494
.000
.471
.690
.567
.298
GPT-4
.067
.000
.003
.194
.108
GPT-4o
.327
.003
.027
.000
.119
.055
Mixtral
.177
.006
.046
.000
.043
.144
.006
Large
Llama
.085
.012
.012
.047
.020
.042
.106
.020
.003
Gemini
.186
.001
.003
.002
.000
.064
.122
.098
.016
Claude
.544
.011
.010
.048
.000
.188
.151
.107
.011
O1-mini
.11
.045
.044
.134
.000
.518
.608
.591
.340
Table 33: Topology-based graph pattern detection in E.I. description
Undirected patterns
Dndirected patterns
Scale
Model
Triangle
T-triangle
Square
Diamond
House
V-S
FFL
FBL
D-Diamond
GPT-4
.584
.056
.039
.110
.010
.429
.422
.397
GPT-4o
.706
.111
.227
.015
.383
.287
.269
Mixtral
.550
.107
.157
.070
.364
.352
.257
Small
Llama
.678
.074
.157
.097
.386
Gemini
.696
.175
.171
.192
.230
.205
.126
Claude
.713
.269
.160
.250
.249
.329
.393
.257
.128
O1-mini
.211
.499
.364
.574
.249
.599
.670
.566
.477
GPT-4
.329
.047
.045
.068
.000
.256
.210
.099
.041
GPT-4o
.575
.089
.066
.205
.000
.289
.258
.154
.053
Mixtral
.430
.074
.051
.139
.000
.127
.180
.095
.029
Medium
I.ama
.290
.032
.061
.094
.020
.213
.134
.124
.035
Gemini
.632
.075
.088
.124
.030
.037
.162
.098
.000
Claude
.651
.159
.127
.253
.040
.166
.233
.092
.035
O1-mini
.749
367
.417
.57
.024
.496
.625
.591
.301
GPT-4
.113
.002
.002
.005
.000
.230
.133
.085
.010
GPT-4o
.257
.015
.008
.055
.000
.158
.180
.096
.014
Mixtral
.262
.010
.009
.025
.000
.086
.184
.037
.013
Large
Llama
.068
.044
.001
.008
.020
.094
.070
.134
.013
Gemini
.355
.000
.061
.005
.027
.025
.152
.074
.000
Claude
.266
.015
.015
.072
.040
.162
.170
.080
.040
O1-mini
.544
.049
.050
.114
.000
.488
.625
.595
.343
Table 34: Frequency subgraph extraction in A.L. description
GPT4
GPT-4n
Mixtral M.
Ilama M.
Gemini
Claude
O1-mini
A.L.
M.
L.
M.
L
S.
S.
M.
S.
S.
M. L.
Triangle
1.00 1.00
1.00
0.84
0.88
0.88
0.86 0.88
1.00
0.62
0.68
0.87
1.00
1.00
0.59
0..4
0.26
0.09
1.00
1.00
1.00
Square
1.00
1.00
1.00
0.86
1.00
0.95
0.61
0.94
1.00
0.75
0.47
0.40
0.30
0.07
1.00
1.00
Diamond
1.00 1.00
1.00
0.89
1.00
0.50
0.92
1.00
1.00
0.43
0.52
0.96
1.00
1.00
0.83
0.34
0.33
0.14
1.00
1.00
1.00
House
1.00 1.00
1.00
1.00
1.00
0.98
0.73
1.00
1.00
0.53 0.66
0.93
1.00
0.78
0.10
0.31
0.32
0.22
1.00
1.00
1.00
FFI.
1.00 1.00
1.00
0.64
1.00
0.89
1.00
0.86
0.67
0.68
0.93
0.89
0.00
1.00
0.33
0.32
0.26
1.00
1.00 1.00
1.00
1.00
0.89
0.90
1.00
1.00
0.77
0.67
1.00
1.00
0.46
0.40
1.00
0.85
D-Diamond
1.00 1.00
1.00
0.81
0.95
1.00
0.54
0.73
0.67
1.00
0.41
0.35
1.00
1.00
30

---

Published as a conference paper at ICLR 2025
Table 35: Frequency subgraph extraction E.L. description
GPT-4
GPT-4o
Mixtral
Llama M.
Gemini M.
Claude
O1-mini
E.I.
M.
L.
M.
L.
M.
S.
S.
S.
M. L.
Triangle
1.00
1.90
0.94
1.00
0.81
1.00
1.00
0.94
0.95
1.00
1,00
0.29
0.84
0.32
1.00
1.00
Square
1.00
1.00
0.97
0.71
0.98
1.00
1.00
0.94
0.93
0.80
0.17
0.93
0.67
0.21
1.00
1.00
Diamond
1.00 1,00
1.00
1.00
0.87
0.93
1.00
1.00
1.00
0.99
0.93
0.91
1.00
0.38
0.52
0.99
0.68
0.32
1.00
1.00
1.00
House
1.00 1,00
1.00
1.00
1.00
0.76
1.00
1.00
1.00
1.00
0.74
0.95
1.00
0.33
0.18
1.00
0.55
0.44
1.00
1.00
1.00
FFL
1.00 1.00
1.00
0.67
0.92
1.00
1.00
0.90
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.68
0.52
0.34
1.00
1.00 1.00
1.00
1.00
0.75
1.00
1.00
0.96
1.00
1.00
0.84
0.31
1.00 1.00
D-Diamond
1.00 1.00
1.00
0.85
0.88
0.66
1.00
0.60
0.78
1.00
1.00
1.00
0.75
1.00
0.61
0.28
1.00
1.00
31


Reviews:
[{"review_id": "o45CaZkW7S", "reviewer": "Reviewer_FSEL", "summary": "This paper presents a benchmark that evaluates SOTA LLM graph pattern understanding and whether any graph reasoning is gleaned from pretraining in graph-based tasks. The authors describe three distinct settings for evaluating graph pattern understanding: terminology-based, topology-based, and data-driven. \n\nThe terminology-based evaluation explores whether LLMs can comprehend and reproduce graph patterns from the terminology found in pretraining data. Models are tested by examining their alignment with human understanding of a given pattern and assessing whether LLMs can follow human instructions for pattern-detection.\n\nThe topology-based evaluation assesses if LLMs are consistent in their ability to recognize identical patterns in different permutations. Models are evaluated on their ability to perform pattern mapping through isomorphic identification, graph editing, and extracting topology-based patterns.\n\nThe last evaluation strategy evaluates LLMs’ ability to independently identify and mine graph patterns within real-world datasets.\nThe paper evaluates 7 SOTA LLMs on their ability to understand 5 undirected graph patterns and 4 directed graph patterns. The results also include model performances on prompts using adjacency lists and edge lists, which are both popular formats for representing graph in LLM-Graph reasoning.", "questions": "- Has analysis of the errors of each model been done? If so, is it possible to include these analyses in the appendix?\n- Could you clarify whether the extra edges added by LLMs in the T-triangle and V-S patterns result in completely disconnected structures or merely unintended modifications?\n- What was the reasoning behind not analyzing the impact of parameter size on model performance? This information could provide valuable insights, especially given that certain models outperformed others.\n- Could you expand on the analysis of the input prompt formats?\n- Can you separate the EL and AL results into separate tables in the final version of the paper? If space constraints prevent both from being included in the main text, I suggest moving the weaker result to the appendix with the results from the above question.\n- Was the exclusion of 'large' graphs in many figures done for the purpose of interpretability? If so, please include versions with the full or just the large results in the appendix.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "While the novelty of the overall goal is limited, this work offers the LLM-Graph reasoning community valuable, and seemingly reliable insight into how LLMs are able to manipulate and understand graph patterns. The paper also stands out because of its clear experimental design and extensive set of experimental results, which would yield insight into the growing research community focusing on LLMs applied to graph reasoning.", "weaknesses": "While the paper is generally well-organized and well-written, the paper suffers from a lack of space. It becomes difficult to parse, given the breadth of experimental results, some of which are not followed by fully satisfactory analyses. There are a total of 9 tasks, each with their own table or figure. Furthermore, several tables include both adjacency list and edge list results, which makes tables very difficult to read. I would suggest splitting the results into separate tables or even moving the lesser results to the appendix, as the impact prompt format is not a central result. \n\nThe analysis of each set of experiments is often quite short and focuses mainly on the performance of o1 or generalizes to all LLMs. While it is important to discuss the best performing model, the paper offers little insights into the types of mistakes being made by underperforming models. For instance, section 4.2 simply states that the decreased average performance (as compared to the terminology-based results discussed in 3.2) were “likely due to increased hallucinations”. Is this backed by the experimental results? \n\nSection 4.1 provides an example of the type of analysis the other results analysis sections would benefit from. I also think the paper would benefit from providing a bird’s-eye view of how each model performs across all tasks. This would provide insight into the relative strengths and weaknesses of each model, which are currently difficult to glean.\n\nMinor Issues:\n- The paper mentions that LLMs tend to add extra edges to patterns such as T-triangle and V-S, leading to unintended structures. It would be helpful to clarify whether these extra edges result in completely disconnected structures or simply unintended modifications.\n\n- The paper asserts that the adjacency list format is better suited for LLMs, which does seem to be the case for o1; however, the results for other models (e.g., pattern isomorphic mapping) do not seem to be as conclusive. A short analysis of these results would be helpful to the community when deciding which format to use for a given model in future experiments.\n\n- The exclusion of 'large' graph sizes results in many figures limits the reliability of those figures.", "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": "tp851t1Goq", "reviewer": "Reviewer_3Su5", "summary": "The paper uses 11 experiments to evaluate the abilities of 7 state-of-the-art (SOTA) LLMs to understand graph patterns from synthetic and real data, as well as their abilities to discover these patterns from data. The authors vary the description of these patterns (terminology-based vs topology-based) in order to observe the impact on performance. The authors claim that models may employ strategies different to strategies found in traditional algorithms to solve tasks, and that models tend to perform better when the input description of the pattern follows a terminology-based description rather than a topological-based description.", "questions": "- In Section 3.1, how can DIV be more than 0 if the temperature of all models is set to 0?\n- In Section 3.3, does every input graph have a graph pattern inside it, or do some input graphs have no graph pattern?\n- In Section 6, how does the “Both” description look like? How do the “alkane groups and fluoride groups” target patterns look like?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well motivated relative to prior work. This work introduces several key graph pattern tasks, and effectively highlights the potential applications of these tasks.\n- The experimentation done in the paper are very comprehensive. The authors evaluate a large set of SOTA LLMs on a large breadth of experiments, including both synthetic and real datasets. This breadth in experimentation effectively showcase the current abilities of SOTA LLMs on graph pattern understanding and discovery.", "weaknesses": "=== Lack of In-Context Learning === \n- All experiments in the paper are done in a zero-shot setting. Demonstrating the impact of in-context learning, such as CoT prompting, on a subset of the experiments would improve the contribution of the paper.\n\n=== Lack of Clarity in Writing ===\n- Section 3.3 lacks clarity on the underlying data. The authors mention that in this task, the LLM takes in an input graph, and is instructed to “detect specific primitive graph patterns” within the input graph. Does every input graph have a graph pattern inside it, or do some input graphs have no graph pattern?\n- Following from the above point, in Section 4.1 the authors “reuse the graph datasets in the terminology-based pattern detection task” in order to test the models’ abilities to map between isomorphic graphs. If some of these graphs do not have a graph pattern, then isn’t this experiment testing graph isomorphic mapping and not pattern isomorphic mapping? What is the explicit relevance of this section with respect to graph patterns?\n- Sections 5.2, 5.3, and 7.2 are poorly written. In Section 5.2, it is unclear what the accuracies in Table 7 represent and how they differ from the accuracies in Figure 5. It is unclear as to what either are reporting. In Section 5.3, the structure of the experiment is difficult to follow. For both Section 5.2’s and 5.3’s experiment, including an algorithmic description or pseudocode for the experiment would also greatly improve clarity. In Section 7.2 where the authors first discuss the strategies LLMs use, for each task, it would be effective to state what strategies traditional algorithms actually use, and then compare these to the strategies used by LLMs. Also, the second point in this first paragraph states that “the adjacency list is often better than the edge list in experiments”, but it is unclear as to what relevance this has on the central claim of this paragraph. When the authors discuss the impact of input format on performance, they mention that “terminology-based graph pattern detection is usually better than topology-based ones”, but then soon afterwards repeat themselves by mentioning that the “terminology-based description is often better than topology-based”. It is also unclear what this point, as well as the later point that “the adjacency list input is better than the edge list input”, have to do with the pretrained knowledge of the LLMs.\n\n=== Unsubstantiated Claims===\n- In Section 3.2, the author state that “the scale of the input graphs generally doesn’t have a major impact...because LLMs generally prioritize high-degree nodes and their neighbors to form the pattern. In larger graphs, LLMs tend to identify more regions for potential edits.” It would be helpful for the authors to empirically validate that the LLMs are in fact prioritizing high-degree nodes when forming the pattern, as this would provide evidence to substantiate this claim.", "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": "ru9TwSX8Zc", "reviewer": "Reviewer_Dygb", "summary": "Summary:\nThe author proposed a new benchmark evaluates LLMs in graph pattern recognition. While LLMs show early abilities in understanding graph structures, their potential in pattern mining is under-explored. This benchmark, covering 11 tasks and 7 models, tests LLMs' capacity to recognize and discover patterns in synthetic and real data. Key findings show O1-mini outperforms in most tasks, aligning data formatting with pretrained knowledge enhances performance, and LLMs use unique strategies distinct from traditional algorithms.", "questions": "Same as Cons", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Pros: \n- The paper provide benchmark for evaluating LLMs’ ability in understanding graph patterns.\n- Analysis has been conducted based on the proposed benchmark. Multiple research questions have been studied.", "weaknesses": "Cons:\n- It would be great if o1-preview result can also be included, if feasible.\n- In molecular graphs, how is the molecule features being provided to the LLMs? I am curious about how the molecular graph is being converted to textual format and feed into the LLMs.  More details are encouraged to be included. If edge lists is utilized, then example of the edge list representing molecules are encouraged to be shown.\n- For the question, Can LLMs automatically discover graph patterns in real-world applications? A work using LLMs to find patterns in molecular data is encourage to be mentioned. The work has tried to use LLMs to identify key functional groups in molecular data for diverse molecular property prediction tasks[1].   [1] Zheng, Y., Koh, H. Y., Ju, J., Nguyen, A. T., May, L. T., Webb, G. I., & Pan, S. (2023). Large language models for scientific synthesis, inference and explanation. arXiv preprint arXiv:2310.07984.", "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": "dn14VzCHDb", "reviewer": "Reviewer_jJDa", "summary": "The paper avaluates large language models (LLMs) on graph pattern comprehension. It explores three types of descriptions: terminology-based, topology-based, and data-drive and evaluates model performance across synthetic and real-world datasets. The study highlights LLMs' limitations and potential for recognizing graph patterns, especially with the inclusion of recent models like O1-mini.", "questions": "1. In Section 3.1, what is the temperature used for evaluating diversity? Would increasing the temperature lead to more diversity?\n2. In Section 5.1, the paper mentions that “LLMs tend to make errors when node degrees are close to 3.” Could the authors clarify why this happens?\n3. In Section 6, is the test set complete, or is only a subset used for testing? Section C.3 does not clearly clarify this.\n4. In the data-driven approach, what is the input format? Are these images?\n5. Would fine-tuning be a feasible strategy to improve accuracy for real-world graph tasks?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 1, "strengths": "1. The paper includes O1, a very recent model specifically designed for reasoning, highlighting its capabilities and limitations for graph tasks and revealing that there is still room for improvement in how LLMs handle graphs.\n2. The paper is well-written, with good clarity and well-organized explanations, making it accessible for readers. The consideration of multiple input formats serves as a useful starting point for anyone new to the field of graph tasks using LLMs.\n3. The range of tasks, spanning both synthetic and real-world datasets, provides a comprehensive evaluation of LLM performance on graph-related tasks.", "weaknesses": "1. Lack of Novelty:\nThe paper’s findings align with existing research, notably with studies like [1], which already demonstrate that LLMs have limited graph understanding. Although the inclusion of O1 is new and valuable, most results are expected and reflect known limitations of other LLMs in graph comprehension.\n\n2. Predictable Results:\nThe finding that “formatting input data to align with pretraining knowledge can enhance performance” is elementary and expected in LLM research. This does not offer a significant new insight and detracts from the paper's contribution.\n\n3. Limitations of Terminology-Based Approaches:\nWhile terminology-based descriptions can be effective for small, simple graphs, they become impractical for larger, denser graphs with multiple cycles, squares, and complex structures. The approach lacks scalability, which is a significant drawback in the context of graph pattern tasks.\n\n4. Overlap with Existing Work:\nPrior studies, such as [2] have already evaluated multiple topology-based prompts across diverse tasks, revealing similar findings. This paper’s contribution is limited since it doesn’t introduce substantial new insights beyond these previous efforts.\n\n\n[1] Wang, Heng, et al. \"Can language models solve graph problems in natural language?.\" Advances in Neural Information Processing Systems 36 (2024).\n\n[2] Fatemi, Bahare, Jonathan Halcrow, and Bryan Perozzi. \"Talk like a graph: Encoding graphs for large language models.\" arXiv preprint arXiv:2310.04560 (2023).", "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)