How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension

## Abstract

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 data to align with the knowledge acquired during pretraining can enhance performance; (3) The strategies employed by LLMs may differ from those used in conventional algorithms.

## 1 Introduction

Originally trained on textual data, LLMs have demonstrated remarkable success in various tasks, such as reading comprehension and text reasoning (Achiam et al., ; Touvron et al., ). To evaluate whether LLMs can adapt the text understanding ability across graphs, several studies have investigated this at both the feature and structural levels (Zhao et al., ; Chai et al., ). Specifically, LLMs have been shown to enhance node features in social networks (Ye et al., ; Huang et al., ). Additionally, graph structure understanding tasks, such as shortest path and connectivity, have also been evaluated (Guo et al., ; Wang et al., ).

Graph patterns, a key aspect of graphs, have yet to be thoroughly explored. Mining graph patterns play a critical role in numerous real-world applications. For instance, they aid in uncovering new insights within biological protein-protein interaction networks (Hu et al., ; Tran et al., ), identifying key molecular structures in chemistry (Murray & Rees, ), and detecting fraudulent activities in transaction networks (Cheng et al., ), and so on. In addition, these patterns represent fundamental transferable structures among graphs, such as community groups for friendship recommendations in social networks (Wu et al., ) and functional groups for molecular property prediction (Agarwal et al., ). Therefore, it is of great interest to investigate whether LLMs possess the capability to comprehend these patterns and effectively apply them to a 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 to real-world applications. Specifically, we categorize the descriptions of graph patterns into three types: terminology-based, topology-based, and data-driven, as shown in Table 1. Based on these descriptions, we progressively challenge LLMs’ abilities in graph pattern tasks:

**Table 1: Three types of descriptions. ‘Square’ is defined by terminology and topology to outline its structure. In a data-driven description, ’Square’ frequently appears as a common pattern in the data.**
| Terminology-based | Topology-based | Data-driven |
| --- | --- | --- |
| The pattern, named Square,<br>is a 4-node cycle with each<br>node connected to exactly<br>two others. | The pattern, defined as G, is an<br>undirected graph with four Node<br>0, 1, 2, 3. Node 0 is connected<br>to Nodes 1 and 2. Node 1 is<br>connected to Nodes 2 and 3. |  |

Can LLMs understand graph patterns based on terminology-based descriptions? (Section 3) 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 a rudimentary understanding of simple graph patterns as described in terminology, such as ’triangle’ or ’diamond’. To evaluate this, we have devised three subtasks aimed at progressively testing LLMs’ comprehension of terminologically defined patterns. In detail, we first examine the alignment between LLMs’ 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 on topology-based descriptions? (Section 4) While certain graph patterns can be succinctly described using natural language, more complex patterns often necessitate representation through adjacency lists or edge lists. As LLMs are not trained for permutation invariance, the same pattern, when described with different node ID sequences, may result in varying understanding by LLMs.
Thus, to examine LLMs’ consistency in recognizing identical patterns, we first require LLMs to perform pattern mapping through isomorphic identification. Following this, we assess their ability to edit and extract topology-based patterns, similar to their handling of terminology-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 of understanding. To further probe the depth of LLMs’ capability, we 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 as 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 to comprehend. We gather ten 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 of LLMs for graph patterns in Section 7.

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 et al., ; Ying et al., ; Li et al., ). Specifically, we include 5 undirected graph patterns: triangle, tailed-triangle (T-triangle), square, diamond, and house. For directed graph patterns, we have V-structure (V-S), feedforward loop (FFL), feedback loop (FBL), and directed-diamond (D-diamond). The detailed definitions are illustrated in Appendix Table 11.
These graph patterns serve as key examples in constructing datasets and testing LLMs’ ability in terminology-based and topology-based tasks.

Datasets. For comprehensive benchmarking, we consider multiple factors to construct diverse datasets. We design the terminology-based and topology-based descriptions for patterns. The topology 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 patterns themselves. We randomly generate varying input graph sizes: small (S) with 5–15 nodes, medium (M) with 15–25 nodes, and large (L) 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 14.

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 (llama3.1-401B-Instruct), Gemini (gemini-1.5-pro), Claude (claude-3-opus-20240229) and O1-mini (o1-mini-2024-09-12). We set temperatures to 0 for all the models.

## 3 Terminology-based Patterns

In this section, we first introduce a pattern translation task to assess the alignment between LLMs’ comprehension and human understanding of terminology-based graph patterns. Then, we design graph modification and pattern detection tasks to evaluate LLMs’ ability to 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-based patterns.
Given the terminology of a primitive graph pattern, we prompt LLMs to create a 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 a 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 $\mathrm{DIV}=\frac{\mathrm{\#Different\ pairs}}{\mathrm{\#All\ pairs}}$.

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 on 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, LLMs show biased outputs, resulting in low DIV scores for simple patterns. For instance, when processing triangle patterns, GPT-4o often outputs a simple graph containing a triangle with a chain.

**Table 2: The accuracy and diversity score for pattern translation**
|  | Undirected pattern | Directed pattern |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Triangle | T-Triangle | Square | Diamond | House | V-S | FBL | FFL | D-Diamond |  |  |  |  |  |  |  |  |  |  |  |  |
| ACC | DIV | ACC | DIV | ACC | DIV | ACC | DIV | ACC | DIV | 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.08 | 1.00 | 0.04 | 0.45 | 0.05 |
| Gemini | 0.52 | 0.82 | 0.44 | 0.32 | 0.24 | 0.90 | 0.84 | 0.88 | 0.50 | 0.23 | 0.78 | 0.86 | 0.90 | 0.89 | 0.90 | 0.78 | 0.94 | 0.92 | 0.67 | 0.73 |
| Claude | 1.00 | 0.61 | 0.02 | 0.00 | 0.24 | 0.67 | 0.78 | 0.58 | 0.88 | 0.62 | 0.20 | 0.93 | 1.00 | 0.29 | 0.90 | 0.53 | 0.84 | 0.59 | 0.65 | 0.54 |
| Llama | 1.00 | 0.48 | 0.00 | 0.00 | 0.86 | 0.75 | 1.00 | 0.80 | 0.14 | 0.30 | 0.00 | 0.00 | 1.00 | 0.90 | 0.98 | 0.77 | 1.00 | 0.00 | 0.66 | 0.44 |
| GPT-4 | 1.00 | 0.12 | 0.35 | 0.75 | 0.98 | 0.33 | 0.92 | 0.76 | 0.86 | 0.80 | 0.42 | 0.94 | 1.00 | 0.28 | 0.98 | 0.45 | 1.00 | 0.54 | 0.83 | 0.55 |
| GPT-4o | 0.98 | 0.29 | 0.92 | 0.46 | 0.74 | 0.80 | 0.82 | 0.77 | 0.68 | 0.40 | 0.88 | 0.26 | 1.00 | 0.64 | 0.82 | 0.87 | 0.68 | 0.77 | 0.84 | 0.58 |
| O1-mini | 1.00 | 0.79 | 0.62 | 0.70 | 1.00 | 0.94 | 0.74 | 0.87 | 0.66 | 0.97 | 0.82 | 0.90 | 0.98 | 0.75 | 0.96 | 0.82 | 0.98 | 0.85 | 0.86 | 0.84 |
| AVG. | 0.93 | 0.44 | 0.34 | 0.32 | 0.58 | 0.63 | 0.87 | 0.70 | 0.53 | 0.47 | 0.44 | 0.56 | 0.98 | 0.55 | 0.79 | 0.61 | 0.92 | 0.53 | 0.71 | 0.54 |

### 3.2 Graph Modification

In graph modification, we construct a dataset of input graphs, each including a specific primitive pattern, and then prompt LLMs to transform one pattern into another.
Specifically, we define the following modifications: Square to House (S $\rightarrow$ H), Square to Diamond (S $\rightarrow$ D), Diamond to Square (D $\rightarrow$ S), and FFL to FBL (F $\rightarrow$ B). They contain edit operations like adding several edges, removing one edge, or changing the direction of an edge.
A prompt example is “Modify the input graph to include a house pattern. The input graph G is $\dots$. 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 in Table 3. We observe that O1-mini stands out in its ability to edit diverse terminology-based patterns. Additionally, the scale of the input graphs generally doesn’t have a major impact. This is 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**
|  | Gemini | Mixtral | Llama | Claude | GPT-4 | GPT-4o | O1-mini |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| S. | M. | L. | S. | M. | L. | S. | M. | L. | S. | M. | L. | S. | M. | L. | S. | M. | L. | S. | M. | L. |  |  |
| S $\rightarrow$ H | A.L. | 0.06 | 0.28 | 0.20 | 0.32 | 0.58 | 0.64 | 0.34 | 0.48 | 0.40 | 0.26 | 0.50 | 0.48 | 0.14 | 0.12 | 0.14 | 0.28 | 0.36 | 0.44 | 0.38 | 0.64 | 0.58 |
| E.L | 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 $\rightarrow$ D | 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.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 |  |
| D $\rightarrow$ S | 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 |
| E.L | 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 |  |
| F $\rightarrow$ B | A.L. | 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 |
| E.L | 0.22 | 0.42 | 0.44 | 0.28 | 0.52 | 0.36 | 0.28 | 0.58 | 0.50 | 0.24 | 0.56 | 0.34 | 0.15 | 0.40 | 0.16 | 0.18 | 0.18 | 0.22 | 0.34 | 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 is “Identify the occurrence of the given pattern in the input graph. The pattern is a diamond, defined as a 4-node motif with five edges. The input graph is $\dots$.” For each pattern, we calculate the F1 score to evaluate LLM performance in terms of precision and recall.

The results for small and medium scales are shown in Figure 1, with the full results provided in Appendix Table 16.
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 is less affected by the graph scale, as its step-by-step approach may help mitigate this issue.

Figure: Figure 1: The F1 score for terminology-based pattern detection (small and medium scale)
Refer to caption: x2.png

## 4 Topology-based Pattern

In this section, we first perform pattern isomorphic mapping to examine LLMs’ understanding of topology-based graph patterns. Subsequently, we conduct graph modification and pattern detection tasks to further evaluate LLMs’ capabilities with various patterns and graph scales.

### 4.1 Pattern Isomorphic Mapping

In a topology-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, we 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-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.

Figure: Figure 2: The influence of underlying algorithms used in pattern isomorphic mapping
Refer to caption: x3.png

The results, presented in Table 4, show that most LLMs perform 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. Consequently, 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 algorithms to help LLMs reason whether the graphs are isomorphic.
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 2, O1-mini uses the degree counting approach with the proportion 89%. Only about 30% of the outputs from Claude and GPT-4o use degree counting, with the majority relying on edge comparison. As LLMs are not good at counting, the overall accuracy of Claude and GPT-4o is significantly higher than that of O1-mini.

**Table 4: The accuracy for isomorphic mapping**
|  | GPT-4 | GPT-4o | Mixtral | Llama | Gemini | Claude | O1-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.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.2 Graph Modification

We use the same setting as that in the terminology-based pattern detection, except the descriptions are now replaced with topology-based 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-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-based descriptions is lower than that for terminology-based 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 within diamond structures prevents LLMs from exhibiting any change.

**Table 5: The success rate for topology-based graph modification**
|  | Gemini | Mixtral | Llama | Claude | GPT-4 | GPT-4o | O1-mini |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| S. | M. | L. | S. | M. | L. | S. | M. | L. | S. | M. | L. | S. | M. | L. | S. | M. | L. | S. | M. | L. |  |  |
| S $\rightarrow$ H | A.L. | 0.20 | 0.34 | 0.20 | 0.78 | 0.58 | 0.66 | 0.57 | 0.52 | 0.48 | 0.45 | 0.64 | 0.44 | 0.34 | 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 |  |
| S $\rightarrow$ D | 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 |
| E.L | 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 $\rightarrow$ S | A.L. | 0.12 | 0.24 | 0.12 | 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.40 | 0.48 | 0.55 | 0.56 | 0.64 |
| E.L | 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 $\rightarrow$ B | A.L. | 0.28 | 0.38 | 0.50 | 0.52 | 0.40 | 0.64 | 0.55 | 0.68 | 0.70 | 0.37 | 0.54 | 0.40 | 0.48 | 0.68 | 0.76 | 0.57 | 0.80 | 0.80 | 0.41 | 0.76 | 0.68 |
| E.L | 0.20 | 0.24 | 0.32 | 0.34 | 0.52 | 0.40 | 0.41 | 0.50 | 0.44 | 0.29 | 0.44 | 0.34 | 0.27 | 0.46 | 0.48 | 0.44 | 0.62 | 0.52 | 0.32 | 0.66 | 0.66 |  |

### 4.3 Pattern detection

We use the same setting as that in the terminology-based pattern detection, except the pattern descriptions are now topology-based descriptions. The results are shown in Figure 3, with full results provided in Appendix Table 17.
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 F1 score in detecting tailed-triangle, square and diamond patterns, other models only reach an F1 score of 20%. Moreover, although O1-mini performs well on small-scale graphs, it fails on medium-scale datasets. Among the patterns, the house pattern is particularly difficult to detect, as it is the most complex pattern in our setting.

**Table 6: The precision of nodes in k-core detection**
|  | GPT-4 | GPT-4o | Mixtral | Llama | Gemini | Claude | O1-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 | 0.63 | 0.63 |
| Medium | 0.73 | 0.62 | 1.00 | 0.85 | 0.84 | 0.80 | 0.78 | 0.84 | 0.80 | 0.80 | 0.88 | 0.88 | 0.88 | 0.88 |
| Large | 0.66 | 0.52 | 1.00 | 1.00 | 0.90 | 0.80 | 0.88 | 1.00 | 0.84 | 0.76 | 1.00 | 1.00 | 1.00 | 1.00 |

Figure: Figure 3: The F1 score of topology-based pattern detection (small and medium scale)
Refer to caption: x4.png

## 5 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 is valuable in chemistry and biology. Discriminative patterns enable us to distinguish between different classes within the data, aiding in classification tasks.

### 5.1 Dense subgraph mining (k-core)

K-core is a commonly used densely connected subgraph, defined as a maximal subgraph containing nodes of degree $k$ or more.
In this task, we prompt LLMs to leverage the k-core algorithm (Batagelj & Zaversnik, ) to identify 3-core in the input graph.
We compute Precision as the metric by judging whether the identified nodes belong to a 3-core and present the results in Table 6.

On average, LLMs achieve over 60% precision across various graph scales, demonstrating their ability to execute the algorithm effectively.
Notably, LLMs obtain better performance on large-scale graphs than on smaller ones, likely because most nodes in large graphs have degrees greater than 3. LLMs tend to make errors when node degrees are close to 3 but become increasingly accurate as 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 5 reach nearly 100% precision.

### 5.2 Frequent Subgraph Extraction

Mining frequent subgraphs is an important task on graphs, defined as finding subgraphs that appear frequently in a graph dataset given a frequency threshold. In this task, we set a 100 turns evaluation. In each turn, we randomly select 10 graphs, and task LLMs to extract frequent patterns and output patterns in topology-based description. The accuracy is calculated when the patterns appear in more than 60% graphs, and summarize the results in Table 7.

**Table 7: The accuracy of extracted frequent subgraphs**
|  | GPT-4 | GPT-4o | Mixtral | Llama | Gemini | Claude | O1-mini |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| S. | M. | L. | S. | M. | L. | S. | M. | L. | S. | M. | L. | S. | M. | L. | S. | M. | L. | S. | M. | L. |  |  |
| Triangle | A.L. | 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.43 | 0.26 | 0.09 | 1.00 | 1.00 | 1.00 |
| E.L | 1.00 | 1.00 | 1.00 | 0.94 | 1.00 | 0.81 | 1.00 | 1.00 | 1.00 | 0.94 | 0.95 | 1.00 | 1.00 | 0.57 | 0.29 | 0.84 | 0.58 | 0.32 | 1.00 | 1.00 | 1.00 |  |
| Square | A.L. | 1.00 | 1.00 | 1.00 | 1.00 | 0.86 | 1.00 | 0.69 | 0.95 | 1.00 | 0.61 | 0.94 | 1.00 | 0.75 | 0.47 | 0.40 | 0.30 | 0.37 | 0.07 | 1.00 | 1.00 | 1.00 |
| E.L | 1.00 | 1.00 | 1.00 | 0.97 | 0.71 | 0.98 | 1.00 | 1.00 | 1.00 | 0.94 | 0.93 | 0.91 | 0.80 | 1.00 | 0.17 | 0.93 | 0.67 | 0.21 | 1.00 | 1.00 | 1.00 |  |
| Diamond | A.L. | 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 |
| E.L | 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 | A.L. | 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 |
| E.L | 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 | A.L. | 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.89 | 0.00 | 1.00 | 0.33 | 0.32 | 0.26 | 1.00 | 1.00 | 1.00 |
| E.L | 1.00 | 1.00 | 1.00 | 0.96 | 0.67 | 0.92 | 1.00 | 1.00 | 1.00 | 0.92 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.68 | 0.52 | 0.34 | 1.00 | 1.00 | 1.00 |  |
| FBL | A.L. | 1.00 | 1.00 | 1.00 | 0.78 | 0.89 | 0.90 | 1.00 | 1.00 | 0.59 | 0.77 | 0.67 | 0.87 | 1.00 | 1.00 | 1.00 | 0.46 | 0.22 | 0.40 | 1.00 | 1.00 | 0.85 |
| 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.84 | 0.45 | 0.31 | 1.00 | 1.00 | 1.00 |  |
| D-Diamond | A.L. | 1.00 | 1.00 | 1.00 | 0.81 | 0.95 | 1.00 | 1.00 | 1.00 | 0.67 | 0.54 | 0.73 | 0.91 | 0.67 | 0.00 | 1.00 | 0.41 | 0.42 | 0.35 | 1.00 | 1.00 | 1.00 |
| E.L | 1.00 | 1.00 | 1.00 | 0.85 | 0.88 | 0.66 | 1.00 | 0.60 | 1.00 | 0.78 | 1.00 | 1.00 | 1.00 | 0.75 | 1.00 | 0.61 | 0.46 | 0.28 | 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 |

LLMs exhibit a strong capability in identifying frequent subgraphs, with GPT-4 and O1-mini showing impressive performance. However, LLMs are prone to 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, is rarely recognized.

Figure: Figure 4: The precision in various node degrees
Refer to caption: x5.png

### 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, we calculate the discriminative pattern ratio as $\mathrm{D.P.=\frac{\mathrm{\#Discriminative\ patterns}}{\mathrm{\#Extracted\
patterns}}}$, which assesses the efficiency of the extraction process.

The results in Table 8 demonstrate that most LLMs successfully perform graph classification tasks, particularly when using the edge list format. Interestingly, a high D.P. score does not always correspond to high accuracy. For instance, despite having a D.P. score of 0.08, O1-mini still achieves a classification accuracy of 0.72.

## 6 Evaluation on Real-world Graphs

In this section, we gather a wide range of real-world datasets across diverse domains, 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 C. In this evaluation, we focus on pattern detection and discriminative pattern learning.

Molecule Pattern Detection. Followed by Section 3.3 and Section 4.3, we perform pattern detection 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-Carbonyl (R-CO), and Fluoride-Carbonyl (F-CO), where the target patterns are hexagons, alkane groups, and fluoride groups, respectively. We compare the terminology-based with topology-based patterns, and also assess a combined approach, referred to as Both.

**Table 9: The F1 score for pattern detection in molecules**
|  | Terminology-based | Topology-based | Both |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Benzene | R-CO. | F-CO | Benzene | R-CO | F-CO | Benzene | R-CO | 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 9 illustrates 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-MOL | OGBG-BBBP | IMDB-BINARY | ENZYYMES | FINGERPRINT | IMDB-MULTI |  |  |  |  |  |  |  |
| 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 | 0.66 | 0.70 | 0.56 | 0.58 | 0.64 | 0.66 | 0.72 | 0.78 | 0.40 | 0.38 | 0.36 | 0.36 | 0.33 | 0.35 |
| GPT-4o | 0.61 | 0.63 | 0.52 | 0.60 | 0.68 | 0.70 | 0.68 | 0.72 | 0.40 | 0.35 | 0.35 | 0.34 | 0.34 | 0.35 |
| Discriminative<br>Patterns |  |  |  |  |  |  |  |  |  |  |  |  |  |  |

Discriminative Pattern Learning and Classification. Based on Section 5.3, we conduct the 2-step process of discriminative pattern learning and classification on real-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-BBBP), social network (IMDB-BINARY, IMDB-MULTI), bioinformation (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 et al., ). 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.

## 7 Discussions

In this section, we endeavor to provide intuitions and insights on LLMs’ ability in graph pattern tasks. We first provide our theoretical intuitions from the perspective of expressiveness and then summarize key insights from our observations.

### 7.1 Theoretical Intuitions

In this subsection, we discuss the theoretical intuitions of LLMs’ capabilities in graph pattern recognition from an expressiveness standpoint, often used in analyzing Transformers (Feng et al., ; Li et al., ; de Luca & Fountoulakis, ). We demonstrate that Transformers, given graph inputs, can be configured to perform graph pattern tasks. The LOCAL framework Angluin () 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., ; Korhonen & Rybicki, ). 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 a Transformer with edge list as input that can simulate A.

The detailed proof is given in Appendix B. The proof intuition is that the attention mechanism is a message-passing 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.

###### Theorem 1 .

### 7.2 Empirical Insights

LLMs may employ strategies differently from traditional algorithms. Previous theoretical works (Feng et al., ; Wu et al., ; Li et al., ; de Luca & Fountoulakis, ) demonstrate that LLMs can perform graph-related tasks by simulating traditional graph algorithms (with chain-of-thought). However, in many cases, the LLMs pretrained by language could use strategies differently from traditional algorithms. First, while frequent subgraph extraction is computationally more challenging than k-core detection, LLMs perform better on the former. This is because LLMs struggle with simple degree counting and fail to execute specific algorithms effectively. Second, the format of the adjacency list and edge list can be easily converted to each other in linear time, but the adjacency list is often better than the edge list in experiments. We hypothesize that the adjacency list format provides a more concise representation of a node’s edges, which aligns well with the locality of attention mechanisms in LLMs (Xiao et al., ). Third, in the pattern isomorphic mapping task, O1-mini prefers the degree counting approach with the proportion 89% while only about 30% of the outputs from Claude and GPT-4o use degree counting, as shown in Figure 2.

Input format that aligns with the pretrained knowledge improves the performance. Our experiments demonstrate that LLMs have basic knowledge about graph patterns and they help LLMs in graph pattern tasks. First, in Section 3.1, LLMs can translate the terminologies to the topology descriptions, which shows that LLMs have the basic knowledge about graph patterns. Second, comparing the results in Section 3.3 and those in Section 4.3, we find that terminology-based graph pattern detection is usually better than topology-based ones. It indicates that with terminology as input, LLMs make use of their internal knowledge to improve performance. Third, comparing the results in Section 3 and Section 4, we find that the terminology-based description is often better than topology-based. In most cases, the adjacency list input is better than the edge list input.

#### O1-mini often gives the best results, but not always.

In most tasks, O1-mini has the best performance, especially when the graph size is large. This is not surprising because it has a much longer chain-of-thought. For example, in the pattern detection task, which requires LLMs to search node combinations one by one, O1-mini holds a clear advantage.
However, it falls back in the discriminative 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 O1-mini attempts graph classification, the patterns struggle to generalize, leading to lower classification accuracy.

## 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 is to solve graph algorithm tasks, such as connectivity, degree counting, cycle check, shortest path, and Hamilton path.
NLGraph (Wang et al., ) and Talk like a graph (Fatemi et al., ) translated graph structures into natural language, and leveraged techniques like few-shot prompting or chain-of-thought (CoT) to feed these descriptions directly into LLMs for inference.
Since exact computational algorithms can be employed to obtain an accurate reasoning process and results,
GraphInstruct (Luo et al., ) built the instruction-tuning dataset and fine-tuned LLMs by Lora. Moreover, Graphwiz (Chen et al., ) extended the scale and diversity of the dataset and applied Direct Preference Optimization (DPO) loss to enhance the performance. Recently, GraphToken (Perozzi et al., ) utilized a GNN-like encoder to process the input graph and train this encoder with a frozen LLM.

The second category encompasses graph learning tasks, which typically include node classification, link prediction, and graph classification (Chen et al., ). 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., ) and GraphText (Zhao et al., ) 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 construct datasets for tuning.
LLaGA (Chen et al., ) and MuseGraph (Tan et al., ) reorganized the center node and its neighborhood information as a 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., ) utilized a 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., ) and InstructMol (Cao et al., ) used similar GNN encoders for molecular structures to predict their properties.

Graph Pattern Discovery. Graph patterns (also known as 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, ), biology (Hu et al., ), and social science (Wu et al., ). Numerous exact 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. (); Zhang & Parthasarathy (). These methods were further extended to attributed graphs to capture more realistic and complex patterns (Hu et al., ). Frequent subgraph mining algorithms were developed to efficiently search for possible patterns (Yan et al., ; Elseidy et al., ), 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., ; Zhang et al., ; Luo et al., ) 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.

As previously mentioned, few studies have addressed graph pattern discovery using LLMs, despite their importance for many downstream tasks, which still require further exploration.

## 9 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 unexplored. To bridge this gap, we propose a benchmark featuring both synthetic and real-world data, spanning 11 subtasks evaluated across 7 LLMs. 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 are gathered to further assess LLMs’ ability to handle the attributes and noise in the pattern. Our results show that LLMs possess a preliminary capability to understand graph patterns and perform tasks related to them effectively.

## Appendix A Appendix

## Appendix B Proof for Theorem 1

We first define the edge list format.

$$ $\displaystyle\underbrace{u_{1}\ v_{1}\ a_{u_{1}\leftarrow v_{1}}\ u_{1}\ v_{2} \ a_{u_{1}\leftarrow v_{1}}\ \ldots\ u_{n}\ v_{n}\ a_{u_{n}\leftarrow v_{n}}}_ {\text{edge list}}\ \underbrace{u_{1}\ a_{1}\ \ldots\ u_{n}\ a_{n}}_{\text{ initial states}}$ (1) $$

where $u_{1},v_{1}$ are the node id, $a_{i}$ is the node feature and $a_{u_{1}\leftarrow v_{1}}$ is the edge weights. The definition of message-passing graph neural networks.

###### Theorem 2 (Formal version of Theorem 1 ) .

Assume the input format is given in equation 1. Let $\textsf{T}_{\ell}(G_{a})$
be the state $(x_{1}^{(\ell)},\ldots,x_{n}^{(\ell)})$ of a Transformer network T with edge list input in 1. For any LOCAL algorithm N and small number $\epsilon$, there exists T such that

$$ $\|\textsf{T}_{O(\ell)}(G_{a})-\textsf{N}_{\ell}(G_{a})\|_{\infty}\leq\epsilon \quad\text{for every layer }\ell\ \ \text{and}\ \ G_{a}\in\mathcal{G}_{a},$ $$

where $\mathcal{G}_{a}$ is the set of all attributed graphs.

###### Proof.

This theorem is a combination between Lemma 1 and Lemma 2.
∎

###### Lemma 1 (Equivalence between MPGNNs and LOCAL) .

Let $\textsf{N}_{\ell}(G_{a})$
be the state $(x_{1}^{(\ell)},\ldots,x_{n}^{(\ell)})$ of a MPGNN network N
and $\textsf{A}_{\ell}(G_{a})=(s_{1}^{(\ell)},\ldots,s_{n}^{(\ell)})$ that of a LOCAL algorithm A.
For any algorithm A there exists N (resp. for any N there exists A) such that

$$ $\textsf{A}_{\ell}(G_{a})=\textsf{N}_{\ell}(G_{a})\quad\text{for every layer } \ell\ \ \text{and}\ \ G_{a}\in\mathcal{G}_{a}.$ $$

Figure: Algorithm 1 Message passing graph neural network Loukas ()

###### Lemma 2 (Representing MPGNNs by Transformers) .

Assume the input format is given in equation 1 and Msg and Up in Algorithm 1 are implemented by MLPs. Let $\textsf{T}_{\ell}(G_{a})$
be the state $(x_{1}^{(\ell)},\ldots,x_{n}^{(\ell)})$ of a Transformer network T with edge list input in 1. For any MPGNN N and small number $\epsilon$, there exists T such that

$$ $\|\textsf{T}_{O(\ell)}(G_{a})-\textsf{N}_{\ell}(G_{a})\|_{\infty}\leq\epsilon \quad\text{for every layer }\ell\ \ \text{and}\ \ G_{a}\in\mathcal{G}_{a}.$ $$

###### Proof.

The proof is heavily built on the proof of Theorem 1 in Wu et al. ().

Token Embedding and Positional Embedding: The token embedding includes the token type $e^{\text{type1}}$ (0 0 for the node feature; $1$ for node id; $2$ for edge feature), refined token type $e^{\text{type2}}$ (0 0 for node feature, $1$ for the node id 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 $e^{\text{token}}$ (from 0 0 to $|V|-1$). The two-dimensional positional embedding includes the embedding for initial state tokens $e^{\text{pos1}}$ (0 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^{\text{pos2}}$ (0 0 for initial state sentence tokens, $1$ for the first three elements of the edge list, $2$ for the second three elements of the edge list, etc.). There are also placeholders to put the intermediate states of MPGNNs.

Block 1 - Node feature Preparation: The goal of the first block is to broadcast the node feature $a_{i}$ from the initial state sentence tokens to node tokens in edge list. (1) Use MLPs to recover the digits of the node features $a_{i}$ and put them in the first placeholder if $e^{type}_{k}==0$; (2) Copy the first placeholder from initial state sentence token to its previous node token by using COPY in Lemma 3 and setting $\mathcal{S}_{k}=\{j|(e^{\text{pos1}}_{k}-e^{\text{pos1}}_{j})^{2}<\delta\}$; (3) Broadcast the first placeholder with MEAN in Lemma 3 and setting $\mathcal{S}_{k}=\{j|(e^{\text{type1}}_{k}-e^{\text{type1}}_{j})^{2}+(e^{\text{
token}}_{k}-e^{\text{token}}_{j})^{2}<\delta\}$. Now the state for every node token $u_{i}$ is $[e^{\text{type1}},e^{\text{type2}},e^{\text{token}},e^{\text{pos1}},e^{\text{
pos2}},a_{u_{i}}]$; (4) Use MLP to put the token id into the second placeholder if $e^{\text{type1}}==2$ or $e^{\text{type1}}==3$. Now the state for every node token $u_{i}$ is $[e^{\text{type1}},e^{\text{type2}},e^{\text{token}},e^{\text{pos1}},e^{\text{
pos2}},a_{u_{i}},u_{i}]$

Block 2 - Edge feature Preparation: 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^{\text{type1}}==2$; (2) Copy the third placeholder from the edge feature token to the node tokens by using SUM in Lemma 3 and setting $\mathcal{S}_{k}=\{j|(e^{\text{pos2}}_{k}-e^{\text{pos2}}_{j})^{2}<\delta\}$. Now the state for every target node token $u_{i}$ of the $i$-th edge is $[e^{\text{type1}},e^{\text{type2}},e^{\text{token}},e^{\text{pos1}},e^{\text{
pos2}},a_{u_{i}},u_{i},a_{u_{i}\leftarrow v_{i}}]$; (3) Use MLPs to put the node feature in the fourth placeholder if $e^{\text{type1}}==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 3 and setting $\mathcal{S}_{k}=\{j|(e^{\text{pos2}}_{k}-e^{\text{pos2}}_{j})^{2}<\delta\}$. Now the state for every target node token $u_{i}$ of the $i$-th edge is $[e^{\text{type1}},e^{\text{type2}},e^{\text{token}},e^{\text{pos1}},e^{\text{
pos2}},a_{u_{i}},u_{i},a_{u_{i}\leftarrow v_{i}},a_{v_{i}}]$; (5) Put node id $u_{i}$ into the fifth placeholder if $e^{\text{type1}}==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 $\mathcal{S}_{k}=\{j|(e^{\text{pos2}}_{k}-e^{\text{pos2}}_{j})^{2}<\delta\}$. Now the state for every target node token $u_{i}$ of the $i$-th edge is $[e^{\text{type1}},e^{\text{type2}},e^{\text{token}},e^{\text{pos1}},e^{\text{
pos2}},a_{u_{i}},u_{i},a_{u_{i}\leftarrow v_{i}},a_{v_{i}},v_{i}]$

Block 3 - Message Preparation: The goal of the third block is to compute $m_{u_{i}\leftarrow v_{i}}$. (1) Use MLPs to compute $\textsc{MSG}_{\ell}$ and place the results in the sixth placeholder. Now the state for every target node token $u_{i}$ of the $i$-th edge is $[e^{\text{type1}},e^{\text{type2}},e^{\text{token}},e^{\text{pos1}},e^{\text{
pos2}},a_{u_{i}},a_{u_{i}\leftarrow v_{i}},a_{v_{i}},\textsc{MSG}_{\ell}(a_{u_
{i}},u_{i},a_{u_{i}\leftarrow v_{i}},a_{v_{i}},v_{i})]$; (2) Use MLPs to clean up the remaining placeholders. Now the state for every node token $u_{i}$ is $[e^{\text{type1}},e^{\text{type2}},e^{\text{token}},e^{\text{pos1}},e^{\text{
pos1}},\textsc{MSG}_{\ell}(a_{u_{i}},u_{i},a_{u_{i}\leftarrow v_{i}},a_{v_{i}}
,v_{i})]$.

Block 4 - Message Passing: The goal of the fourth block is to compute $x_{i}^{(1)}$. (1) Use two attention heads to perform the sum operation in aggregation. This is achieved by using SUM in Lemma 3 for the first placeholder and setting $\mathcal{S}_{k}=\{j|(e^{\text{token}}_{k}-e^{\text{token}}_{j})^{2}+(e^{\text{
type2}}_{k}-e^{\text{type2}}_{j})^{2}<\delta\}$. Now the state for every node token $u_{i}$ is $[e^{\text{type1}},e^{\text{type2}},e^{\text{token}},e^{\text{pos1}},e^{\text{
pos2}},\sum_{v_{j}\in\mathcal{N}_{i}^{*}}\textsc{MSG}_{\ell}(a_{u_{i}},u_{i},a
_{u_{i}\leftarrow v_{i}},a_{v_{i}},v_{i})]$; (2) Use MLPs to compute $\textsc{UP}_{\ell}$ and obtain $x_{i}^{(1)}$

After four blocks, the final state for every node token $u_{i}$ is given by $[e^{\text{type1}},e^{\text{type2}},e^{\text{token}},e^{\text{pos1}},e^{\text{
pos2}},x_{i}^{(1)}]$. $x_{i}^{(l)}$ can be obtained by repeating the above four blocks $k$ times.
∎

###### Lemma 3 .

Feng et al. () Let $n\in\mathbb{N}$ be an integer and $\bm{x}_{1},\cdots,\bm{x}_{n}$ be a sequence of vectors where $\bm{x}_{i}=(\tilde{\bm{x}}_{i},r_{i},1)\in[-M,M]^{d+2}$ where $M$ is a large constant. Let $\bm{K},\bm{Q},\bm{V}\in\mathbb{R}^{d^{\prime}\times(d+2)}$ be any matrices with $\|\bm{V}\|_{\infty}\leq 1$ and let $0<\rho,\delta<M$ be any real numbers. Denote $\bm{q}_{i}=\bm{Q}\bm{x}_{i},\bm{k}_{j}=\bm{K}\bm{x}_{i},\bm{v}_{j}=\bm{V}\bm{x
}_{j}$. Define a matching set $\mathcal{S}=\{j||\bm{q}_{i}^{T}\bm{k}_{j}|\leq\rho\}$. Define two following operations

- •
COPY: The output is a sequence of vectors $\bm{u}_{1},\cdots,\bm{u}_{n}$ with $\bm{u}_{i}=\bm{v}_{\text{pos}(i)}$, where $\text{pos}(i)=\arg\max_{j\in\mathcal{S}_{i}}r_{j}$.
- •
MEAN, MAX, SUM: The output is a sequence of vectors $\bm{u}_{1},\cdots,\bm{u}_{n}$, where $\bm{u}_{i}=\square_{j\in\mathcal{S}_{i}}\bm{v}_{j}$ and $\square$ is min or max or sum or mean.

Specifically, for any sequence of vectors $\bm{x}_{1},\bm{x}_{2},\cdots,\bm{x}_{n}$, denote the corresponding output of the attention layer as $\bm{o}_{1},\bm{o}_{2},\cdots,\bm{o}_{n}$. Then, we have $\|\bm{u}_{i}-\bm{o}_{i}\|_{\infty}\leq\epsilon$ for all $i\in[n]$ and $\mathcal{S}\neq\emptyset$.

###### Theorem 2 (Formal version of Theorem 1 ) .

###### Proof.

###### Lemma 1 (Equivalence between MPGNNs and LOCAL) .

###### Lemma 2 (Representing MPGNNs by Transformers) .

###### Proof.

###### Lemma 3 .

## Appendix C Dataset

### C.1 Primitive graph patterns

We select primitive graph patterns with varying node counts and edge numbers. First, 3-node patterns are the simplest structures in graphs, so we 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 of one edge. For 4-node patterns, we select the tailed-triangle (T-triangle), square, and diamond for undirected graphs, and the directed-diamond 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 introduce the house pattern, a 5-node structure combining a triangle and a square. The summarization of patterns shown in Table 11

**Table 11: The selected primitive graph patterns (5 undirected and 4 directed patterns)**
| Undirected Pattern | Directed Pattern |  |  |  |  |
| --- | --- | --- | --- | --- | --- |
| Name | Terminology-based Description | Structure | Name | Terminology-based Description | Structure |
| Triangle | A motif consisting of three nodes where each node is connected to the other two, forming a triangle |  | V-structure (V-S) | two nodes have directed edges pointing toward a common target node |  |
| Tailed-triangle (T-triangle) | A triangle with an additional node connected to one of the vertices of the triangle |  | Feedforward loop (FFL) | A 3-node directed motif in which one source node influences a target node through two distinct pathways |  |
| Square | A 4-node cycle where each node is connected to exactly two other nodes |  | Feedback loop (FBL) | A 3-node directed cycle where the nodes form a loop |  |
| Diamond | A 4-node motif with five edges |  | Directed-diamond (D-diamond) | A 4-node motif in a directed graph where one node has directed edges to two intermediate nodes, and both of those intermediate nodes have directed edges to a common target node. |  |
| House | A motif resembling the shape of a house with 5 nodes and 6 edges. The vertices and edges are arranged such that there is a triangular ”roof” on top of a square or rectangular ”base.” |  |  |  |  |

### C.2 Synthetic dataset details

We generate different datasets for various tasks.
In the pattern detection task, we randomly generate graphs on 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.
In the modification task, we randomly generate the graph with constraints. For example, we assume that LLMs need to add at most two nodes to achieve the goal, as in the Square $\rightarrow$ House sets. This means the original graphs contain at least one square pattern but lack a house pattern, requiring LLMs to modify the graph to create the house pattern. Similarly, Square $\rightarrow$ Diamond needs to add one edge while Diamond $\rightarrow$ Square needs to minus one edge. FFL $\rightarrow$ 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 a triangle.
In the discriminative pattern learning task, we employ the BA-2motif dataset (Luo et al., ). We split it into 900 graphs to evaluate the discriminative pattern learning of LLMs and 100 for classification testing.
For the evaluation, we 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 to evaluate the metrics due to the cost of APIs.

**Table 12: Details of synthetic datasets**
| Task | Dataset type | difficulty | Num | AVG. node | AVG. edge | AVG. density |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Pattern<br>detection | Undirected<br>graph | Evaluation | Small | 250 | 9.50 | 22.80 | 0.52 |
| Medium | 250 | 19.50 | 96.20 | 0.52 |  |  |  |
| Large | 250 | 29.50 | 247.96 | 0.58 |  |  |  |
| Directed<br>graph | Evaluation | Small | 250 | 9.50 | 23.44 | 0.26 |  |
| Medium | 250 | 19.50 | 96.98 | 0.26 |  |  |  |
| Large | 250 | 29.50 | 223.58 | 0.26 |  |  |  |
| Modification | Undirected<br>graph | Square $\rightarrow$<br>House | Small | 166 | 9.71 | 25.07 | 0.56 |
| Medium | 347 | 14.67 | 22.09 | 0.33 |  |  |  |
| Large | 476 | 18.54 | 24.89 | 0.26 |  |  |  |
| Square $\rightarrow$<br>Diamond | Small | 144 | 9.91 | 10.96 | 0.27 |  |  |
| Medium | 332 | 15.32 | 17.95 | 0.19 |  |  |  |
| Large | 484 | 19.54 | 23.45 | 0.16 |  |  |  |
| Diamond $\rightarrow$<br>Square | Small | 111 | 8.95 | 10.98 | 0.34 |  |  |
| Medium | 180 | 12.59 | 13.92 | 0.26 |  |  |  |
| Large | 205 | 14.52 | 16.03 | 0.24 |  |  |  |
| Directed<br>graph | FFL $\rightarrow$<br>FBL | Small | 227 | 9.63 | 14.64 | 0.18 |  |
| Medium | 396 | 13.69 | 19.08 | 0.13 |  |  |  |
| Large | 493 | 16.60 | 23.48 | 0.12 |  |  |  |
| Frequent<br>subgraph | Undirected<br>graph | Triangle | Small | 231 | 9.87 | 17.61 | 0.39 |
| Medium | 248 | 19.46 | 56.04 | 0.31 |  |  |  |
| Large | 247 | 29.46 | 149.27 | 0.35 |  |  |  |
| Square | Small | 217 | 10.14 | 19.35 | 0.40 |  |  |
| Medium | 249 | 19.49 | 56.32 | 0.31 |  |  |  |
| Large | 249 | 29.49 | 152.85 | 0.35 |  |  |  |
| Diamond | Small | 214 | 10.19 | 20.12 | 0.42 |  |  |
| Medium | 244 | 19.44 | 63.30 | 0.35 |  |  |  |
| Large | 246 | 29.45 | 168.59 | 0.39 |  |  |  |
| House | Small | 205 | 10.37 | 20.50 | 0.41 |  |  |
| Medium | 250 | 19.50 | 60.47 | 0.33 |  |  |  |
| Large | 247 | 29.46 | 156.12 | 0.37 |  |  |  |
| Directed<br>graph | FFL | Small | 238 | 9.71 | 17.93 | 0.20 |  |
| Medium | 248 | 19.48 | 59.90 | 0.17 |  |  |  |
| Large | 250 | 29.50 | 154.67 | 0.18 |  |  |  |
| FBL | Small | 208 | 10.20 | 20.79 | 0.21 |  |  |
| Medium | 244 | 19.41 | 64.15 | 0.18 |  |  |  |
| Large | 248 | 29.48 | 156.56 | 0.18 |  |  |  |
| D-Diamond | Small | 187 | 10.60 | 22.33 | 0.21 |  |  |
| Medium | 248 | 19.48 | 62.01 | 0.17 |  |  |  |
| Large | 247 | 29.47 | 150.57 | 0.18 |  |  |  |
| Discriminative<br>pattern learning | Discrimination | - | - | 900 | 25 | 25.5 | 0.09 |
| Classification | - | - | 100 | 25 | 25.5 | 0.09 |  |

### C.3 Real-world 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 molecule datasets: MUTAG, ogbg-molhiv, BBBP, Benzenes, Alkane-Carbonyl, and Fluoride-Carbonyl; one bioinformatics datasets: ENZYMES; one computer vision dataset: Fingerprint; and two social network datasets: IMDB-BINARY and IMDB-MULTI.
Detailed information regarding datasets is delineated in Table 13.

MUTAG (Debnath et al., ). The MUTAG dataset is a collection of nitroaromatic compounds and its goal is to predict their mutagenicity on Salmonella typhimurium.
In our evaluation, we use the PyGeometric (^1^11[https://www.pyg.org/](https://www.pyg.org/)) version of the dataset, which comprises 188 molecular graphs, for conducting the binary classification task.

OGBG-HIV (Hu et al., ; Wu et al., ). 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 a 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., ). The Blood–brain barrier penetration (BBBP) dataset originates from a study (Martins et al., ) focusing on modeling and predicting barrier permeability.
As a 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 compounds on their permeability properties.
In alignment with our experimental conditions, we randomly select 500 compounds for pattern discrimination and 50 compounds for pattern-based binary classification, ensuring an equitable distribution of positive and negative samples.

IMDB-BINARY (Yanardag & Vishwanathan, ). It is a movie collaboration dataset that consists of the ego networks of 1,000 actors/actresses who have shared roles in movies listed on IMDB, originating from the Action and Romance genres.
In each graph, the nodes symbolize actors/actresses, with edges connecting them if they have appeared together in a movie.
For our experiments, we partition 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, ). 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 a total of 60 graphs are reserved as test samples for a multi-classification objective.
This task involves predicting whether a movie graph corresponds to a Comedy, Romance, or Sci-Fi network.

Fingerprint (Morris et al., ). The Fingerprint dataset is a multi-classification dataset obtained from fingerprint images, where 2,149 fingerprints are transformed into graphs through image filtering 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., ). The ENZYMES dataset comprises 600 protein tertiary structures sourced from the BRENDA enzyme database, featuring six distinct enzymes.
In our study, we focus on three out of the six enzymes to perform a 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 (Sanchez-Lengeling et al., ). Benzene consists 12,000 molecular graphs from the ZINC15 (Sterling & Irwin, ) 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 a hexagon made up of carbon atoms is used as the target pattern in LLM prompts.

Alkane-Carbonyl (Sanchez-Lengeling et al., ). The Alkane-Carbonyl 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=O) functional 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-Carbonyl (Sanchez-Lengeling et al., ). The Fluoride-Carbonyl dataset has 8,671 molecular graphs and its ground-truth explanation is based on the particular combination of fluoride (F-) atoms and carbonyl (C=O) functional groups present in each molecule.
For the pattern detection task, we select 100 molecules from each class, aiming to identify whether a molecule includes both fluoride atoms and carbonyl functional groups.

**Table 13: Statistics of real-world datasets. Alkane* and Fluoride* represent the Alkane-Carbonyl and Fluoride-Carbonyl datasets, respectively.**
| Task | Domain | Name | Progress | Num | AVG. node | AVG. edge | AVG. density |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Bi-Class. | Molecule | MUTAG | discrimination | 150 | 15.67 | 16.79 | 0.0725 |
| classification | 38 | 15.68 | 16.76 | 0.0723 |  |  |  |
| overall | 188 | 15.67 | 16.78 | 0.0725 |  |  |  |
| OGBG-<br>HIV | discrimination | 200 | 31.77 | 34.82 | 0.0445 |  |  |
| classification | 40 | 30.50 | 33.45 | 0.0467 |  |  |  |
| overall | 240 | 31.65 | 34.69 | 0.0447 |  |  |  |
| OGBG-<br>BBBP | discrimination | 500 | 21.99 | 23.40 | 0.0595 |  |  |
| classification | 50 | 28.24 | 30.64 | 0.0429 |  |  |  |
| overall | 550 | 22.56 | 24.06 | 0.0580 |  |  |  |
| Social<br>Network | IMDB-<br>BINARY | discrimination | 500 | 19.56 | 96.18 | 0.2457 |  |
| classification | 50 | 19.73 | 98.43 | 0.2466 |  |  |  |
| overall | 550 | 19.57 | 96.39 | 0.2458 |  |  |  |
| Pattern<br>Detection | Chemicals | Benzene | overall | 200 | 20.49 | 21.75 | 0.0547 |
| Alkane* | overall | 200 | 41.54 | 42.72 | 0.0259 |  |  |
| Fluoride* | overall | 200 | 21.46 | 22.65 | 0.0508 |  |  |
| Multi-Class. | Bioinformatics | ENZYMES | discrimination | 240 | 33.40 | 63.91 | 0.0731 |
| classification | 60 | 31.93 | 62.78 | 0.0774 |  |  |  |
| overall | 300 | 33.15 | 63.72 | 0.0738 |  |  |  |
| Computer<br>Vision | Fingerprint | discrimination | 300 | 2.92 | 2.13 | 0.2428 |  |
| classification | 60 | 2.93 | 2.20 | 0.2560 |  |  |  |
| overall | 360 | 2.92 | 2.14 | 0.2450 |  |  |  |
| Social<br>Network | IMDB-<br>MULTI | discrimination | 300 | 12.95 | 67.21 | 0.3503 |  |
| classification | 60 | 12.62 | 52.90 | 0.3279 |  |  |  |
| overall | 360 | 12.89 | 64.83 | 0.3466 |  |  |  |

### C.4 Prompt

We collect the prompt for different tasks as following Table 14

**Table 14: Summarization of prompts**
| Task | Prompt |
| --- | --- |
| Pattern<br>translation | Generate a graph that includes only one {terminology-based pattern description}, the node number is 20. Each node at least has one edge. |
| Pattern<br>detection | Identify the occurrence patterns of the given motif in the graph. The given pattern is {terminology-based (topology-based) pattern description }. The graph is… |
| Patern<br>modification | Modify the graph to include the given pattern {terminology-based (topology-based) pattern description }. The pattern is … The graph is… |
| Pattern<br>isomorphic<br>mapping | Given a pair of isomorphic graphs, determine the node correspondence between the two graphs. The first graph is… The second graph is… |
| K-core<br>detection | Determine the 3-core subgraphs in the graph. The graph is … |
| Frequent<br>subgraph<br>extraction | Consider the following graphs and summarize the common patterns in them. No. 1. The graph is … No. 2. The graph is… |
| Discriminative<br>pattern<br>learning | You are provided two sets of graphs. The first set is: No. 1 The graph is… No. t. The graph is… The second set is: No. 1. The graph is… No. 2. The graph is…What are the differences between the two sets? Show the special pattern in Set1 (Set2) |
| Classification | You are an expert at classifying different types of graphs based on whether they contain specific patterns. The first type of graph includes patterns such as: No.1 the pattern is… No.2 The pattern is…The second type includes patterns like: No.1 the pattern is…No.2 The pattern is… Now, please identify which type the given graph is most likely to belong to. The graph is… |

## Appendix D Real-world applications

### D.1 Experimental settings

The evaluation setup involves comparing GPT-4, GPT-4o, and O1mini models in real-world applications, following a pipeline similar to that proposed for synthetic datasets to prompt Large Language Models (LLMs) to comprehend graph patterns.
Details are depicted in Table 15.
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 15: Hyper parameters for real-world tasks.**
| Param | Binary Classification | Multi-label Classification |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| MUTAG | OGBG-<br>HIV | OGBG-<br>BBBP | IMDB-<br>BINARY | ENZYMES | Fingerprint | IMDB-<br>MULTI |  |
| # Sampling | 10 | 5 | 5 | 5 | 5 | 5 | 5 |
| # Turns | 16 | 40 | 100 | 100 | 32 | 40 | 40 |

## Appendix E The full results for pattern detection

The whole results of terminology-based and topology-based pattern detection are shown in Table 16 and Table 17, respectively.

**Table 16: The F1 score for terminology-based graph detection**
| Scale | Models | Undirected patterns | Dndirected patterns |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Triangle | T-triangle | Square | Diamond | House | V-S |  | FFL | FBL | D-Diamond |  |  |  |  |  |  |  |  |  |  |
| 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 | A.L. | E.L |  |  |
| Small | GPT-4 | .632 | .581 | .151 | .107 | .069 | .026 | .113 | .113 | .006 | .003 | .352 | .380 | .389 | .406 | .191 | .279 | .448 | .396 |
| GPT-4o | .748 | .702 | .210 | .250 | .149 | .132 | .317 | .309 | .008 | .053 | .477 | .490 | .478 | .450 | .410 | .357 | .411 | .360 |  |
| Mixtral | .694 | .622 | .224 | .211 | .128 | .102 | .232 | .181 | .121 | .118 | .117 | .110 | .191 | .241 | .110 | .145 | .238 | .140 |  |
| Llama | .681 | .693 | .189 | .193 | .118 | .106 | .185 | .195 | .042 | .021 | .486 | .527 | .358 | .388 | .373 | .349 | .425 | .367 |  |
| Gemini | .712 | .725 | .207 | .274 | .150 | .176 | .230 | .262 | .104 | .225 | .287 | .281 | .263 | .267 | .194 | .193 | .149 | .111 |  |
| Claude | .782 | .740 | .217 | .229 | .178 | .149 | .273 | .259 | .210 | .171 | .385 | .365 | .300 | .277 | .262 | .265 | .229 | .201 |  |
| O1-mini | .828 | .832 | .593 | .578 | .335 | .316 | .663 | .684 | .054 | .066 | .584 | .600 | .605 | .602 | .567 | .584 | .504 | .488 |  |
| Medium | GPT-4 | .356 | .345 | .061 | .031 | .010 | .004 | .083 | .057 | .017 | .000 | .101 | .130 | .085 | .117 | .054 | .108 | .035 | .023 |
| GPT-4o | .671 | .563 | .108 | .120 | .102 | .114 | .242 | .215 | .024 | .034 | .247 | .300 | .246 | .191 | .141 | .163 | .097 | .081 |  |
| Mixtral | .474 | .478 | .104 | .118 | .006 | .032 | .132 | .125 | .000 | .007 | .040 | .053 | .049 | .149 | .060 | .081 | .007 | .003 |  |
| Llama | .618 | .584 | .059 | .043 | .082 | .070 | .140 | .108 | .020 | .000 | .207 | .210 | .153 | .167 | .119 | .134 | .051 | .043 |  |
| Gemini | .678 | .658 | .197 | .218 | .091 | .107 | .247 | .299 | .056 | .000 | .125 | .133 | .188 | .167 | .148 | .111 | .012 | .018 |  |
| Claude | .725 | .673 | .144 | .157 | .130 | .161 | .205 | .210 | .038 | .016 | .130 | .141 | .181 | .173 | .104 | .052 | .006 | .009 |  |
| O1-mini | .848 | .777 | .409 | .453 | .335 | .274 | .535 | .567 | .009 | .000 | .527 | .516 | .611 | .637 | .603 | .594 | .318 | .327 |  |
| Large | GPT-4 | .057 | .086 | .003 | .005 | .003 | .000 | .001 | .002 | .000 | .000 | .067 | .061 | .066 | .064 | .031 | .059 | .029 | .016 |
| GPT-4o | .404 | .317 | .016 | .045 | .011 | .012 | .063 | .041 | .000 | .000 | .156 | .226 | .151 | .140 | .111 | .066 | .091 | .058 |  |
| Mixtral | .319 | .233 | .016 | .014 | .005 | .006 | .064 | .056 | .000 | .022 | .016 | .030 | .046 | .155 | .034 | .055 | .008 | .012 |  |
| Llama | .361 | .384 | .012 | .013 | .018 | .011 | .025 | .030 | .020 | .020 | .111 | .123 | .133 | .167 | .054 | .073 | .022 | .014 |  |
| Gemini | .600 | .496 | .035 | .014 | .043 | .011 | .099 | .063 | .038 | .047 | .101 | .103 | .174 | .166 | .110 | .137 | .001 | .000 |  |
| Claude | .320 | .278 | .013 | .020 | .020 | .023 | .051 | .044 | .020 | .020 | .074 | .054 | .147 | .138 | .066 | .078 | .004 | .007 |  |
| O1-mini | .636 | .428 | .065 | .072 | .039 | .026 | .103 | .025 | .000 | .000 | .533 | .560 | .635 | .637 | .568 | .592 | .363 | .367 |  |

**Table 17: The F1 score for topology-based graph detection**
| Scale | Models | Undirected patterns | Dndirected patterns |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Triangle | T-triangle | Square | Diamond | House | V-S |  | FFL | FBL | D-Diamond |  |  |  |  |  |  |  |  |  |  |
| 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 | A.L. | E.L |  |  |
| Small | GPT-4 | .653 | .584 | .051 | .056 | .041 | .039 | .162 | .110 | .002 | .010 | .415 | .475 | .346 | .429 | .423 | .422 | .477 | .397 |
| GPT-4o | .717 | .706 | .194 | .143 | .118 | .111 | .233 | .227 | .005 | .015 | .537 | .489 | .296 | .383 | .407 | .287 | .285 | .269 |  |
| Mixtral | .520 | .550 | .108 | .134 | .132 | .107 | .170 | .157 | .105 | .070 | .191 | .227 | .287 | .364 | .276 | .352 | .255 | .257 |  |
| Llama | .545 | .678 | .122 | .145 | .076 | .074 | .112 | .157 | .005 | .097 | .476 | .488 | .266 | .361 | .382 | .386 | .388 | .283 |  |
| Gemini | .651 | .696 | .166 | .192 | .133 | .175 | .177 | .171 | .122 | .192 | .304 | .171 | .266 | .230 | .194 | .205 | .203 | .126 |  |
| Claude | .730 | .713 | .186 | .269 | .122 | .160 | .263 | .250 | .241 | .249 | .370 | .329 | .302 | .393 | .322 | .257 | .206 | .128 |  |
| O1-mini | .832 | .821 | .617 | .499 | .365 | .364 | .633 | .574 | .107 | .249 | .588 | .599 | .678 | .670 | .572 | .566 | .492 | .477 |  |
| Medium | GPT-4 | .273 | .329 | .032 | .047 | .012 | .045 | .064 | .068 | .000 | .000 | .177 | .256 | .072 | .210 | .129 | .099 | .051 | .041 |
| GPT-4o | .657 | .575 | .183 | .089 | .086 | .066 | .143 | .205 | .000 | .000 | .298 | .289 | .072 | .258 | .146 | .154 | .046 | .053 |  |
| Mixtral | .414 | .430 | .057 | .074 | .039 | .051 | .051 | .139 | .000 | .000 | .040 | .127 | .188 | .180 | .089 | .095 | .021 | .029 |  |
| Llama | .299 | .290 | .029 | .032 | .050 | .061 | .081 | .094 | .000 | .020 | .193 | .213 | .094 | .134 | .059 | .124 | .061 | .035 |  |
| Gemini | .484 | .632 | .037 | .075 | .123 | .088 | .033 | .124 | .000 | .030 | .140 | .037 | .170 | .162 | .109 | .098 | .062 | .000 |  |
| Claude | .671 | .651 | .100 | .159 | .097 | .127 | .247 | .253 | .040 | .040 | .310 | .166 | .204 | .233 | .084 | .092 | .019 | .035 |  |
| O1-mini | .833 | .749 | .488 | .367 | .449 | .417 | .494 | .557 | .000 | .024 | .471 | .496 | .690 | .625 | .567 | .591 | .298 | .301 |  |
| Large | 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 | .003 | .008 | .027 | .055 | .000 | .000 | .240 | .158 | .065 | .180 | .119 | .096 | .055 | .014 |  |
| Mixtral | .177 | .262 | .006 | .010 | .006 | .009 | .046 | .025 | .000 | .000 | .043 | .086 | .144 | .184 | .021 | .037 | .006 | .013 |  |
| Llama | .085 | .068 | .012 | .004 | .012 | .001 | .047 | .008 | .020 | .020 | .042 | .094 | .106 | .070 | .020 | .134 | .003 | .013 |  |
| Gemini | .186 | .535 | .001 | .000 | .003 | .061 | .002 | .005 | .000 | .027 | .064 | .025 | .122 | .152 | .098 | .074 | .016 | .000 |  |
| Claude | .454 | .286 | .011 | .015 | .010 | .015 | .048 | .072 | .000 | .040 | .188 | .162 | .151 | .170 | .107 | .080 | .011 | .040 |  |
| O1-mini | .511 | .514 | .045 | .049 | .044 | .050 | .134 | .114 | .000 | .000 | .518 | .488 | .608 | .625 | .591 | .595 | .340 | .343 |  |

## Peer Reviews

confidence: 4
contribution: 4
initial_rating: 6
presentation: 2
questions: - Has analysis of the errors of each model been done? If so, is it possible to include these analyses in the appendix?
- 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?
- 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.
- Could you expand on the analysis of the input prompt formats?
- 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.
- 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.
soundness: 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.
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. 

The 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.

The 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.

The last evaluation strategy evaluates LLMs’ ability to independently identify and mine graph patterns within real-world datasets.
The 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.
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. 

The 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? 

Section 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.

Minor Issues:
- 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.

- 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.

- The exclusion of 'large' graph sizes results in many figures limits the reliability of those figures.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: - In Section 3.1, how can DIV be more than 0 if the temperature of all models is set to 0?
- In Section 3.3, does every input graph have a graph pattern inside it, or do some input graphs have no graph pattern?
- In Section 6, how does the “Both” description look like? How do the “alkane groups and fluoride groups” target patterns look like?
soundness: 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.
- 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.
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.
weaknesses: === Lack of In-Context Learning === 
- 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.

=== Lack of Clarity in Writing ===
- 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?
- 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?
- 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.

=== Unsubstantiated Claims===
- 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.

---

confidence: 5
contribution: 3
initial_rating: 6
presentation: 3
questions: Same as Cons
soundness: 3
strengths: Pros: 
- The paper provide benchmark for evaluating LLMs’ ability in understanding graph patterns.
- Analysis has been conducted based on the proposed benchmark. Multiple research questions have been studied.
summary: Summary:
The 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.
weaknesses: Cons:
- It would be great if o1-preview result can also be included, if feasible.
- 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.
- 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.

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 4
questions: 1. In Section 3.1, what is the temperature used for evaluating diversity? Would increasing the temperature lead to more diversity?
2. 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?
3. In Section 6, is the test set complete, or is only a subset used for testing? Section C.3 does not clearly clarify this.
4. In the data-driven approach, what is the input format? Are these images?
5. Would fine-tuning be a feasible strategy to improve accuracy for real-world graph tasks?
soundness: 3
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.
2. 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.
3. The range of tasks, spanning both synthetic and real-world datasets, provides a comprehensive evaluation of LLM performance on graph-related tasks.
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.
weaknesses: 1. Lack of Novelty:
The 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.

2. Predictable Results:
The 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.

3. Limitations of Terminology-Based Approaches:
While 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.

4. Overlap with Existing Work:
Prior 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.


[1] Wang, Heng, et al. "Can language models solve graph problems in natural language?." Advances in Neural Information Processing Systems 36 (2024).

[2] Fatemi, Bahare, Jonathan Halcrow, and Bryan Perozzi. "Talk like a graph: Encoding graphs for large language models." arXiv preprint arXiv:2310.04560 (2023).

Meta-review: The paper examines the ability of LLMs to understand graph patterns from synthetic and real data, and their capacity to discover these patterns from data. The authors vary the description of these patterns based on terminology and topology to observe the impact on performance. 

The authors claim that models may employ strategies different from 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. Some reviewers felt this is an obvious observation.

In their initial reviewes, the reviewers expressed concerns about novelty with respect to existing studies on LLM-understanding of graph topologies and associated queries. The initial version also omitted the impact of COT reasoning, which the authors addressed in the rebuttal. The authors also enhanced the differentiation with works in their rebuttal. While the reviewers still feel the novelty is limited, they agree that this is a step in the right direction. Overall, all reviewers agree on the merits of the work and are in favor of acceptance.

Decision: Accept (Poster)