From Sequence to Structure: Uncovering Substructure Reasoning in Transformers
Authors: Xinnan Dai
Kai Yang
Jay Revolinsky
Kai Guo
Aoran Wang
Bohang Zhang
Jiliang Tang
Venue: NeurIPS 2025 poster ()
Keywords: LLMs for graph reasoning
interpretation for Transformers
Primary area: other

Abstract: Recent studies suggest that large language models (LLMs) possess the capability to solve graph reasoning tasks. Notably, even when graph structures are embedded within textual descriptions, LLMs can still effectively answer related questions. This raises a fundamental question: How can a decoder-only Transformer architecture understand underlying graph structures? To address this, 
we start with the substructure extraction task, interpreting the inner mechanisms inside the transformers and analyzing the impact of the input queries. Specifically, through both empirical results and theoretical analysis, we present Induced Substructure Filtration (ISF), a perspective that captures the substructure identification in the multi-layer transformers. We further validate the ISF process in LLMs, revealing consistent internal dynamics across layers. Building on these insights, we explore the broader capabilities of Transformers in handling diverse graph types. Specifically, we introduce the concept of thinking in substructures to efficiently extract complex composite patterns, and demonstrate that decoder-only Transformers can successfully extract substructures from attributed graphs, such as molecular graphs. Together, our findings offer a new insight on how sequence-based Transformers perform the substructure extraction task over graph data.

From Sequence to Structure: Uncovering Substructure Reasoning in Transformers
Xinnan D Kai Yang",, Jay Revolinsky', Kai Guo Aoran Wang', Bohang Zhang", Jiliang Tang' Michigan State University, *Peking University, University of Luxembourg (daixinna, revolins, guokail, tangjili) @msu.edu, yangkai @ alummni.ppp.mmmmmmm wwt.ummm.pkkueuucc.. zhangbohang @ eku..ede en,.edu.cn, walf.wong com
Abstract
Recent studies suggest that large language models (LLMs) possess the capability to solve graph reasoning tasks. Notably, even when graph structures are embedded within textual descriptions, LLMs can still effectively answer related questions. This raises fundamental question: How can decoder-only Transformer ar- chitecture understand underlying graph structures? To address this, we start with the substructure extraction task, interpreting the inner mechanisms inside the transformers and analyzing the impact of the input queries. Specifically, through both empirical results and theoretical analysis, Filtration (ISF), perspective that captures the substructure identification the multi-layer transformers. We further validate the ISF process in LLMs, revealing consistent internal dynamics across layers. Building on these insights, we explore the broader capabilities of Transformers in handling diverse graph types. Specifi- cally, we introduce the concept of thinking in substructures to efficiently extract complex composite patterns, and demonstrate that decoder-only Transformers successfully extract substructures from attributed graphs, such as molecular graphs. Together, our findings offer new insight on how sequence- basee Transformers perform the substructure extraction task over graph data.
present Induced Substructure
1 Introduction
is evident from recent studies that large language models (LLMs) are capable of understanding structured data 3 22 15). For example, when graph structures presented in textual sequence, LLMS can identify node connections 10 21.. detect graph patterns [3] 77, and compare common subgraphs across given set (20 77. However, transformers, which serve the backbone of LLMs, are inherently designed for sequential textual data, which does not naturally capture graph structures. This gap raises a fundamental question: How can sequence-based decoder-only transformer comprehend structured data like graphs?
To answer this question, existing research focuses mainly on basic graph reasoning tasks to build the concept of the mechanism by which transformers understand graph structures [7 29]. The shortest path is one of the basic tasks [21 [I) Based the shortest path task, SLN [5 suggests that form of spectral navigation implicitly emerges within Transformer layers, enabling global coordination across nodes. Meanwhile, Abulhair et al. [18] and ALPINE 25 argue that Transformers learn find paths by composing and merging multiple candidate paths based on the provided edge list. However, these studies are limited to linear paths, while real-world graphs often contain more complex, non- linear substructures such as cycles, trees, and other motifs. As a result, existing understandings drawn
ccorreppondig:: (guokail, daixinna @ edu, t cqual contribution, code is available at https://github.com www.://.ooooDDiiiiiiiieai wwwp:///DDiiiiioooooooooe.m wttrrrooseeeeeettoooooo
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Textual Gruph Representation Question Prompts
Iapul Quaries
any loopa Insido graph?
Comparison of Textual Graph Represeniatinss
Pertorhution on Qustion Promple
If phe
Ensoden
Encedery
ALUS) 0:113,1::2 1:3
Ternil Trlangle Topo (1) A: C, B:
Substructure Detection Transforment
Node is directed to Node 1.2.3. Node is directed Nodel 3.
Incloed
Totel Craph Repcoetaives
Guedke eQ- Crncshonda Frankrr, Enzadeyy
The nushex 0,1,3 constructe
Filtration
Anilysis
Trandoomer
Answer Generation
Machaniin
Transformer
Esteoder,
Trunsformer())
Overview of Substructure Extraction Task
Interpretation Modules
c) Simplified Substructure Extraction
Figure 1: An overview of the interpretation for the substructure extraction task. a) Substructure Extraction Task: The Transformer receives graph description and a question prompt as input and generates an answer. b) Interpretation Modules: The analysis includes input queries and internal Transformer processing. c) Simplified Substructure Extraction: The extraction process simplified to highlight the core mechanism.
from path-finding finding tasks may not generalize to comprchensive graph understanding and are limited to explain why LLMs can do various graph tasks.
In this work, we explore how Transformers tackle the broader challenge of substructure under- standing, with particular emphasis on the task of substructure extraction. Building on the use of LLMs for substructure extraction 77,, Figure[p)) illustrates the overall process with Transformers: transformer-basee models receive a query prompt, which is composed of textual graph representa- tion and question prompt as input. Then, they identify the relevant substructure, and generates an answer for the given graph.
To investigate how Transformers derive answers from input tokens, in Section we conduct empirical and theoretical analyses of train- from--cratch Transformers, focusing on the internal Transformer mechanisms and input queries, as shown Figure To understand the internal behavior of the model, we introduce a new perspective, Induced Substructure Filtration (ISF), which suggests that Transformers perform layer-wise wise node aggregation process detect substructures.
To verify the reliability of our interpretation modules, we demonstrate that our approach also applies understanding LLM behavior and argue that In Section we show that our explanation for Transformers aligns with the behaviors observed in LLMs, particularly in how they tackle various textual graph representations and perform graph extraction tasks. Furthermore. in Section 5 we explore the potential of Transformers in graph understanding. building on insights from our interpretation modules. We argue that it is reasonable extend Transformers to handle attributed graphs, such as molecular graphs. Finally, we introduce the Thinking- In-Substructure framework, which enhances Transformers' capabilities in complex graph reasoning tasks. In summary, we offer new perspective on how Transformers understand graph structures from sequential inputs. Our key contributions are summarized as follows:
inform the development of future methods.
1. We provide insights into how Transformers extract substructures, based on experiments and theory, focusing on internal mechanisms and input queries.
We propose Induced Substructure Filtration (ISF) to explain how Transformers identify substruc- tures across layers.
3. We show that our interpretation is applicable to LLMs, explaining their behaviors in graph tasks and supporting the extension of Transformers to attributed graphs and more complex graph reasoning.
2 Preliminary
We combine theoretical insights and experimental results to demonstrate how Transformers solve the substructure extraction task. To support this, we briefly introduce the core notations and definitions used in this work and provide an overview the experimental setup for the following empirical studies.

---

2.1 Problem formulations
Substructure extraction in transformers Although prompt LLMs interpret natural lan- guage sentences to answer substructure-relatee questions, we simplify the process by converting these sentences into symbolic tokens. This enables scratch. The simplified process is illustrated in Figure 1 c). Given graph G = {V, E} and a question prompt T, encode them using Encoderg and Encodert respectively obtain simpli- fied sentence sequences. These are then concatenated, with the encoded question placed after the graph representation, forming the imput query Q. The objective to extract the set of isomorphic subgraphs G (0i, 92, ... 9s where each 9: represents an instance of the desired substructure within the input graph. The overall process is defined as: Encoder (G) = Transformers(() = Transformers [Encodera (G), Encoderr (T)). We introduce each encoder of this framework in the following paragraphs.
analyze and train Transformers from
Textual graph representations (Encoderç) To input graphs into Transformer, prior work [10] often converts them into textual sequences using either the Adjacency List (AL) or Edge List (EL). Specifically, for graph G (V, E} and vertex vs E V, the AL format captures its neighborhood N (w:) {or E V (us, v) E F. { uu. : ... 1 ). where m, is the number of neighbors of nodes v,- formatted sentence: the central node
In the textual representation, each node and its neighbors and its neighbors are separated by a colon ".", and different such groups are separated by commas "." which formulated as:
;,""" Instead of focusing on central nodes, the EL format enumerates all possible edges (u,, vz) E E. Each edge pair is separated by vertical bar "I" The representation of EL is formulated
AL(G) (v): " w/:
;"'"; Un)
EL) (vi; o "I"; ... "I"; "";""""""""" 0i;ef" " "I";... "'';; Un oh "";.... "I"; Un i 1/
The details of the definitions are in the Definition D.I and Definition D.2 in Appendix D.I
Question prompt (Encoder.) Next, we define the question prompt to determine which substruc- tures should be extracted from the input graph. This prompt, denoted as instruction T, can be either terminology-base or topology-based, as a "triangle", they can defined using either terminology or topological instructions, represented Term (T) (triangle) and TTT)(T)) (A BC, B C), respectively. However, in most cases, the substructures are not clearly defined by terminology, so we rely on topology-base definitions.
described in 7 If the substructures are well-known, such
Answer generation (Encoder The output of the Transformer is text sequence. However, this sequence must correspond to unique substructure. To align the substructures with the text output, constrain the Transformer output the node sets for each substructure, separated by commas. " ","""" d. .... egr
Formally, the output represented as: ANS(C) (vff ug ..... egg where each group (uf....,, ...., g: denotes the nodes in subgraph and commas "," are used to delimit different substructures.
2.2 Experiment settings
Transformer training We train Transformer models using the same architecture as GPT-2 but in lightweight version, with only 384 hidden dimensions and small number of layers depending on the tasks. The details for each task are shown in the Appendix E During training, the model optimized only to predict GNS( For evaluation, we use accuracy as the metric. A predicted answer is considered correct only if the ANS(G) is exactly the same with the ground truth.
Dataset setting We generate over 5 million directed graphs, with node counts ranging from 4 to 16 and edge counts from 3 to 120. The graphs are constructed based on specific requirements detailed in the following empirical studies. To prevent result copying from the same graphs, we ensure that the graphs in the training and testing sets are non-isomorphic.
3

---

Table 1: Transformers extract the substructures from the given graph sequence
Training
Triongle
Square
Diagonal
trangle
Thinggle
Diamend
Pentagon
100K
0,5534
0,8066
0.1926
0.3991
0.04
0.4974
a
0.2877
0.5329
B,0656 0.01
0.1635 0.03
0.5638
0.01
0,560
300K
0,9947 a
0,9948
0,9493 0.00
0.01
0.7247
0.9405 0:0
0:01
0.910
0.775
09000 a 0.03
0,02
0,781 1.006
0.8097 0.02
0,6189 0.02
0,876
4 0.02
0,7063
0.005
0.545 0.05
0.886 a 0.04
400K
0.9977 a 0.00
0,5802 = 0.02
0,9902 0.11
(198820.0
0:00
0.9679 6.0
0.00
0U7077 0.01
0.50%
0:00
0.287 0.02
0.9300 0.04
0.3750 0.12
0.11
119088 0.03
0,930 0.02
0.8922
0.86122
0.5023 sus5
0.8500
3 Interpretations for Substructure Extraction in Transformers
In this section, we present our insights into how Transformers perform substructure understanding. We focus on two main aspects: the internal mechanisms of Transformers solving the substructure extraction task, discussed in Section 3.1] and the impact of input query formulation on extraction performance Section 3.2
3.1 Induced Substructure Filtration in Transformer
In this subsection, we introduce how Transformers solve the substructure extraction task. First, we show that Transformers can extract substructures of diverse shapes, as detailed in Dection[3.1.] We then analyze the underlying mechanism and propose the ISF process Section 3.1.2 Finally, we demonstrate how ISF generalizes to cases with multiple substructures of varying numbers and shapes in Section 3.1.3
3.1.1 Single substructure extraction
We begin with the Single-Shape-Single-We
case, evaluating whether Transformers can extract specific target substructure from given graph whose scale and shape may vary. The selected substructures contain 3 to 5 nodes and to edges. We also investigate the effects of dataset size and the number of Transformer layers. To this end, we vary the training set size from 100K to 400K and the number Transformer layers from 5. For each substructure, we evaluate the extraction accuracy on 30K test graphs, averaging results over three runs. Table I shows the results for various substructure extraction tasks.
The Transformers are capable to extract the target shape of substructures from the given graph with at least 2 layer transformers, achieving over 85% accuracy. However, different substructures exhibit varying requirements in terms of both data scale and model depth. For instance, the 3- cycle (triangle) structure can achieve 99% accuracy with just 3 layers and 100K training examples, while the 5-cycle (pentagon) structure requires over 5 layers and at least 400K examples to attain comparable performance. Furthermore, we observe that the minimum number of Transformer layers required to achieve 85% accuracy correlates with the number of nodes in the substructure. For example, all 4-node substructures can achieve promised results with 4-layer transformers, while 5-node substructures need 5-layer transformers. This suggests that the number of layers is a crucial factor in a Transformer's ability to understand graph structures. To understand how the number of layers affects Transformer's grasp of graph structures, we analyze substructure extraction across layers in the following subsections.
3.1.2 Induced Subgraph Filtration
Visualization Results We visualize token embeddings to better understand how Transformers extract substructures. Since decoder-only Transformers process input left to right (2), we use the final token embeddings to reflect their graph understanding. We apply t-SNE to project these embeddings into a 2D space, labeling each graph by its substructure answer, which is represented by the node IDs as illustrated in ANS(C') As an example, we the square substructure extraction task, shown in Figure 2 The legends are the node IDs. For example, "0431" indicates that the model first identifies node 0 (with out-degree 2), followed by its neighbor 4 (out-degree 1), then node 3 (a neighbor of 4), and finally node (a neighbor of both 3 and 0)
The visualization results reveal how Transformers identify substructures across layers, with graphs sharing similar answers gradually clustering together. Although the visualization targets the final graph token, the substructure answers already determined by the last layer before the generation

---

I-SNE at the layer
E-SNF al the layer?
0431
2130
Thinnn
2431
00
Frandoree
2240
VS 10
R- [0
Yeu
LSNE the layer
layer
%
a) Multi-Num setting
goob BBg
Yuiiing
Tonnlernar
B
G 1/ (A 2.333
TeX SATER
arowen
b) Multi-Shupe setting
Figure 2: Visualization across layers. We show the node ID distributions of target substructures. Legends indicate the node IDs
Figure 3: 4-Node 3- Filtration and Induced Subgraph Filtration
Figure 4: Tasks in Si- multaneous detection
step. We also observe that substructures form progressively across layers. For example, in layer 2, graphs with substructure ID '2431' (dark blue) begin clustering near '0431' (grey) and '2413' (purple), sharing '31' and '24'. By layer 3, '2431' moves closer to '0431', which shares '431'. 1 In the final layer, substructure types are clearly separated. Since outputs follow a left-to-right order, those with similar starting tokens cluster together. Transformers infer substructures before generation, progressively organizing substructures across layers.
Theoretical modeling We further provide theoretical framework for this process by introducing filtrations to formalize progressive substructure extraction. Using the square extraction visualization as example, we model it as a 4-node, 3-filtration process, indicating that the target substructure contains 4 nodes and requires 3 filtration steps, each corresponding to an induced subgraph. More generally, we define this framework as k-Node m-Filtration, referred to as Induced Subgraph Filtration, as defined in Definition 3.1
Definition 3.1 (k-Node m-Filtration and Induced Subgraph Filtration). A k-node m-filtration on V' (V'I = k)) is F(V") = (Vi...., V") where Ø + V S.... ... V.* = =V' For G" = (V', E'), this yields induced subgraph filtration (Gi, Gmm) where G² = GVV.
Figure 3 iillustrates the concept defined in Definition 3.1 We model the extracted substructure as G E') with [V k, and represent the extraction process using nn-Filtration, where m denotes the number of gathering operations required for the Transformers to identify the substructure.
Further, to capture the matches of G' in G EV, we define Substructure Isomorphism Indicator Tensor.
Definition 3.2 (Subgraph Isomorphism Indicator Tensor). For graphs G= (V, E) (V) n) and
G' = OV='v', F*) (VV'= = k)), the subgraph isomorphism indicator tensor T(G, is k-dimensional (n x n) where its entry for ordered k-tuple of vertices (.),.-.., --..; Ujy from V is 1 if these vertices induce a subgraph isomorphic to G' (via a predefined mapping u, + Ug for 1, k).
and T otherwise (see Definition D.5 for details).
Theorem 3.3 (proof in Appendix D.3 shows that Transformers can progressively compute T(G, G') for each substructure along the filtration. O(n²) is the hidden dimension needed for the Transformer to check all k-node subgraphs in n-node graph.
Theorem 3.3 (Expressiveness for Progressive Identification). Given a k-node m-filtration F(V') on V {u/...., 3- For any directed graphs G = (V, E) (V n) and G' =(', E"), log-precision Transformer with m + layers, constant heads, and O(n²) hidden dimension can output vec (G, (VV) at layer + 2. (L....,m}.
Furthermore, the Transformer extracts the unique instance of G', meaning the answer is uniquely determined by the given graph representation and question prompt, and T(G, (G,GG G') contains exactly one entry equal
This leads Assumption 3.4 and Theorem 3.5. With this condition, the substructure extraction task is solvable for transformers.
Assumption 3.4 (Single-Shon Saale--haa--SSil--iiime (i....., is) for which TGG, G") Mi....k 1.
For graphs G, G", there is a unique k-tuple of indices
5

---

Figure 7: Transformers Figure 8: Triangles (tr) has organized the an-are identified layer Theorem 3.5 (Expressiveness for Pattern Extraction). Under Assumption 3.4 for directed graphs G = - EV ([VI= = n) and G² = (V', EE) (vV'= k), dog-precision Transformer with constant depth, constant heads, and O(n²) hidden dimension can output the unique k-tuple of vertices (Ua....., Ux2) ) for which T(G, G') 1.
Remark 3.6. Theorems 3.3 and 3.5
3.5 hold for various input graph representations (e.g.. adjacency lists AL(G) edge lists (L( as formally defined in Definitions D.1 and D.2
3.1.3 Simultaneous detection of multiple substructures
As graphs often contain multiple and diverse substructures, we further demonstrate how the ISF process adapts to such scenarios. Specifically, we evaluate whether a 4-layer Transformer can accurately detect both repeated and differently shaped substructures. To this end, we design the Single- Shape-Multi-Nuns and SaattiShaap--Sngl-Niiie evaluation settings, with the pipeline illustrated in Figure
Single-Shape-Muult-Nnn As shown in Figure 4 a), the Single-Shapee Shape-Multi-Nuune task involves training and testing on graph sets where each sample may contain multiple target substructures up to five in total. This task evaluates whether Transformers can successfully extract all target substructures within a single graph. We define the task in Definition 3.7
extraction task requires a model to output all k-tuples of vertices (V) Vi.)) corresponding to occurrences of directed graph G' (V', F²) (V' k) in G (V, E) ([V) n.). Formally, the objective is to output all tuples satisfying T G.G.G G") 11... = 1, where T(G, G") is Subgraph Isomorphism Indicator Tensor defined in Definition 3.2
Definition 3.7 Sengle-Shape-Miie Masioo-Multi--Nae Nullti-Num Extraction). The
As shown in Figure 5 Both triangles and square detections can achieve over 85% accuracy. The number of substructures has little impact on the Transformers' ability. They can identify multiple patterns at once. We further analyze examples with two substructures and find that answers are still often determined before the final generation step (Figure 7. The theoretical explanation is provided
in Theorem 3.8
Theorem 3.8 (Expressiveness for
Extraction). Fix integers n. 2 k 2 There exists a log- log-precision Transformer with constant depth, constant number of attention Extraction defined Definition 3.7 for directed graphs G (V, F) (VVI n) and G = (V', E²) (VV' = k)).
Shape-Multt
heads, and On ) hidden dimension that can complete
tape
1.00
"Sargle
2.93
3:00
2.00
3.55
0.00
2.85
0221
02.
3.70
345
Pessagote
Sptar
540
Figure 5: The Multi- Figure 6: The Multi- swers before the gener-3 when trained with squares (sq).
Num setting results
Shape setting results
ate the answers.
Multi-Shape-Single-Num As illustrated Figure bb), the Multi-Shape-Sinee Single-Num, task involves training and testing graph sets where each sample may contain multiple substructures shapes. This task evaluates whether Transformers can identify diverse substructure types within a single graph defined in Definition 3.9
of different
Definition 3.9
extraction task requires a model to find all the occurrences for any directed graph G' = (V', E') (V') < k) in G= (V, E) ([V) = n1) satisfying Assumption! 3.4 Formally, the objective is to output the unique
Extraction). The Multi- Swi--Shapp-Sinn---Wee
k' k'-tuple of vertices (Vi,,... ) for which T(G, G' by...igr = 1, where T(G, G') is Subgraph
Isomorphism Indicator Tensor defined in Definition 3.2

---

We create this task by mixing single-shape training data and dividing it into four groups (details in Appendix E.2), (e.)), as shown Figure 6 Each substructure can be extracted independently, guided by its specific question prompt. Therefore, in visualization, we take the embedding of the last input query token rather than the last graph representation token. From Figure[8) we find that Transformers often identify simpler substructures, like triangles, in layer 3, instead of delaying all predictions to the final layer (the Transformer has 4 layers this setting). We summarize the mechanism in Theorem 3.10
Theorem 3.10 (Expressiveness for Saatt-Shaa---Sngl--e
Extraction). Fix integers n 2 There exists a log-precision Transformer with constant depth, constant heads, and O hidden dimension that can complete Sallii-haae-SSa Shape-Single-Nii Extraction defined in Definition 3.9 for directed graph G = (V. E) ([V) n) and any target subgraph G' (V', E') with [V]
satisfying Assumption 3.4
These two properties form the foundation for understanding how decoder-only Transformers decom- pose complex graphs into simpler ones for substructure extraction, as discussed in Section 5.1
3.2 Impact of Input Query Formulation
the input query consists of two components: a text-based graph repre- sentation and question prompt. In Section 3.2.T and Section (32.22 we discuss how Transformers perform the substructure extraction task based on these inputs.
As illustrated in Section 2
3.2.1 Text-Based Graph Representations
We start with the comparison of different text-based graph representation methods. Specifically, we focus the two basic methods, which are the neighborhood-base based AL and the edge-based EL. To ensure controllable input lengths, we conduct a toy experiment using graphs with 4 to nodes, keeping both representations within 100-token limit. We then vary the number of Transformer layers to extract substructures (c.g., triangle, square, or pentagon) from the graph representations. Experimental details are provided in the Table 7 Appendix E.1 and the results are shown in Figure 9
The experimental results indicate that both AL and EL formats allow Transformers to extract substructures from text-based graph representations. As the size of the target substructure increases, both formats require more Transformer layers to achieve more than 80% accuracy. As mentioned Remark [3.6] the theoretical results hold for both AL and EL formats. The intuition is that both formats can be transformed into the same binary adjacency matrix A(G), which encodes the structure of graph G. This matrix is then vectorized vec(AA (G)) for processing within the model, where we provides the details in Lemma D.6 in Appendix D.2
Aol us Frgee Accurnr for Cutivver Sentterttme
2.0
Pertagon Ad
Pentagon Edge Square Acj Squure hige Thangle Art Thannge Enge
10
Layer Numbers
Although we theoretically show that EL and AL are equivalent in representational power, experimental results reveal that EL requires more Transformer layers achieve comparable performance. This may be because EL inherently requires more tokens to explicitly represent all edges, whereas AL. encodes the same information with fewer tokens and additional padding, benefiting from its more com- pact structure. In practice, for a fully connected graph, the AL needs x 1 tokens, while the EL needs 3 (V [V[) tokens. Therefore, for efficiency, mainly adopt AL in discussions. Appendix E.3 provides the details of the training efficiency comparison on AL and EL.
Figure 9: Using AL and EL to predict substructures with varying numbers of Trans- former layers.
3.2.2 Question prompt encoders
We explore how question prompts influence structural understanding in substructure extraction. The question prompt T claims the target substructure, expressed as either terminology-baa -based TT)m(T) (e.g., "triangle") or topology- symbolic node labels, e.g., a triangle as Topo = (A: :
Topo(T). In Topo(T), use AL-style descriptions with
We construct mixed data set to train the Transformer, following the setup in Section 3.1.3 but balance it with equal samples using topology-based and terminology-based prompts, denoted Term". ". "Topol" and "Topo2" in Table 2 The "Term" uses semantic labels (c.g.. "Triangle"), while "Topol"
7

---

Table 2: Results on different question prompts. "p" means the pad token.
Mixture training
Term
ACC
Topol
Topo2
Symbel-level
Teken-level
Gooup
Squaee
Trizngle
0.8788
0.9782
A.B.B.CC
A.D.CAADD.
0.404
0.794
B:ACAA:C
RAD.CGG
0.8000
0.9166
:.:
0.9152
0.7444
C.D
C/D
0.552 07532/0.8470
07004/0.1027
Croup2
Square
Dagonal
0.8810
0.9082
A.C.C.DD.
A.C.D.DDDDBB
0,2332
0.8091
B.A.A.CCD.
B.D.CABDDAA
0,7354
0,9037
0.7086
0.7106
A/C
A/C
0.1271 /0.9094
08866/0.220
gives direct node connections and "Topo2" describes the same structure with shuffled node names. To examine how Transformers align different descriptions with graph inputs, we introduce two types of perturbations: symbol-level and token-level where these tokens are used directly as question prompts. Symbol-level perturbations test the impact of structural phrasing, while token-level perturbations assess reliance on specific tokens within topology prompts. Results are reported in Table 2 In token-level perturbation, we use two different tokens to examine whether they have distinct impacts on Transformer performance.
The results show that Transformers can use both terminology- and topology- prompts, achieving over 70% accuracy in each case. However, lerminology-based prompts perform better, reaching over 85% in Group 2. For example, Topology-based questions show limitations, struggling to represent diagonal substructures accurately. Perturbation results suggest that predictions often rely on specific symbolic cues or tokens rather than full structural understanding. For instance, in Group 1, triangles are identified via symbolic patterns, while Group 2. diagonal and square structures are distinguished by tokens like "A" and "C.". This suggests that Transformers do not explicitly learn full structural representations or map them back to the original graphs for answers. Instead, they abstract substructure concepts using series of key tokens.
4 Consistency in LLM Graph Understanding Behavior
we identify three key findings: In terms of the Transformer mechanism, (1) Transformers perform the ISF process extract substructures simultaneously. Regarding input formulation, (2) both EL and AL can represent the adjacency matrix A(G), though EL may perform slightly worse than AL due to sequence length limitations, and (3) Transformers tend to abstract substructures into a sequence of tokens in the question prompt, rather than fully capturing the underlying topological concepts. Since decoder-only Transformers are common architecture in modern LLMs, we further evaluate whether LLMS exhibit the ISF process during substructure extraction, and whether our understanding of input formulation can explain their behavior.
As discussed in Section 3
Induced Subgraph Filtration To investigate whether LLMs exhibit the ISF process, we visual- ize the fine-tuned LLaMA 3.1-SB-Instruct model on
Answer Clusbeiig
Vis. at Layer 17 (ARI: 0.41)
a triangle detection task (details in Appendix [E.4.2). shown in Figure T0. The results align with our findings in Section 3.I the model often identifies the correct answer before generating it, and deeper layers better distinguish between similar answers. For ex- ample, the responses of the substructures in node IDD '302' and '304' become more separable at layer 23 than at layer 17. We quantify this trend in Figure II where Adjusted Rand Index (ARI) and Normalized Mutual Information (NMI) scores increase with depth. However, unlike Transformers trained from scratch, which only predict answers, LLMs can generate explanatory content. For instance, 23% of responses
245
Layer (ARI:
24:
104
ARI
Tansformer Layers
Figure 10: Visualization on Figure 11: ART 1imma3.1-8B-Instruue
and NMI across the layers.
include P Python code, while others describe node relationships in the graph. As result, ARI and NMI scores slightly decrease in the ending layers.
Text-based Graph Representation Current evaluations have discussed the effect of how different graph representations influence the LLMs in graph reasoning tasks. For example, GraphMem [31] demonstrates that LLMs possess the ability to transfer knowledge across different graph descriptions. This is possible because both AL and EL can be mapped to vec(A(G)). making them share the representations the graph representation level. However, since the EL typically requires more tokens to describe a graph and L.MSs have limitations in handling long contexts, prior studies [10 report that EL representations sometimes perform worse than AL descriptions.
8

---

Question Prompt In the context of substructure understanding, GraphPatt [7] introduces both terminology-basee and topology-basee descriptions for the substructure extraction task, showing that cominologyy-asee prompts generally lead to better performance. Moreover, single terminology concept can correspond to multiple diverse topology- descriptions reported in [7].
5 Understanding on Complex Graphs
In Section we highlight the ISF process key mechanism enabling Transformers to solve the substructure extraction task. Moreover, we observe that when text-based descriptions can be mapped to the adjacency matrix A(G), Transformers can perform substructure extraction on the given graph. Building on these insights, we explore broader applications: in Section 5.1 we introduce new method for efficiently reasoning over composite substructures and in Section 5.2 we examine how Transformers adapt to attributed graphs.
5.1 Thinking in substructures
As introduced in Section g] Transformers apply the ISF process to extract substructures. This process runs synchronously across different patterns, with smaller ones being easier to detect. Besides, complex structures often consist of simpler components, which we refer to as decomposing substructures. Building on these observations, method to explain how decoder-only Transformers solve complex substructure reasoning tasks. For example, 77 reports that reasoning language models decompose house pattern into triangle and square to search for the substructures. We reformulate the answer generation part as ANSTins ({Pi), (Pt) (Pt), < ANS >, ANS(G)), where {P.} is the collection of each decomposing structure and < ANS > is a special token to indicate that the followings are final answers. This decomposition reduces the extraction complexity from (n to O(n"), where q and ls are the maximum size of decomposing substructures and target substructures, respectively, with < k. We
propose the Thinking-in--Suuttruuuuuuu Substructure (Tins)
show the proof in Theorem D.13 Appendix D.4]
To verify the efficiency of Tins, in the experiment, we design 4 different composite substructures with their decomposition process trained with 100K samples. The experiment settings are Ap- pendix E,4.3 The results suggest that Tins can help transformers significantly improve the perfor- mance with limited training data. The overall performance can increase 10%, and in the 3 layer for diagonal structure, the performance increases about 46% percent.
Table 3: The results of Thinking-in-sunn in-substructures (Tins)
Table 4: molecular graphs
Directly Preds
Tins
Functional group
# Node
ACC
Substructures
Decomposition
4 layer 3 layer
4 4aaerr
layer
C-O(H)
9
0.9207
Diagonal
0.6314
0.1998
0.8648
0.6606
COO(H)
121
0.9159
Diamond 88
0.4756
0.1288
0.7792
0.4338
Co(H))
121
0.7245
House
0.5887
0.5640
0.8066 0.6678
Mix
121
0.8946
Complex
0.1182
0.1208
0.2268 0.2124
5.2 Attributed graphs
As shown in Theorem 3.5 the only condition required for Transformers to extract sub- Therefore, if node features uniquely assigned to en-
structures is T(G, G") sure a distinct graph representation for each graph, Transformers can extract substructures while incorporating these features, as discussed in Theorem D.16 Taking the AL-based fea- ture description as an example, we define the attributed graph representation as AL₁(G) = "" :ot"! mi emi, mm........ u u.", ".".v. fl. ; mm fm ). where f. is the node features.
We use molecular graphs examples to test how well Transformers understand attributed graphs with the attributed AL list (G), where we set node feature f; as atoms. In the experiments, the transformers predict the positions of functional groups like Hydroxyl (C-O(H)), Carboxyl (COO(H)).

---

and Benzene Ring C,HH)). We also use a mixed training setup where Hydroxyl and Carboxyl are combined as "Mix". Molecules contain to 4 target groups. Details are Appendix Resul (see Table 4 show that Transformers perform well, even with mixed training, aligning with our discussion in Theorem 3.8 and Theorem 3.10
6 Related work
Evaluations for LLMs in graph understanding Benchmarks reveal that LLMs can recover graph structure from text. NLGraph showed basic reachability and shortest-path competence [21]: Instruct- Graph and GraphArena scaled tasks and graphs, with graph-aware verbalization and instruction-tuning boosting accuracy even on million-node inputs [22] 20 GPT-4 few-shot can rival GNNs on node classification but is sensitive to token order [26] Parallel work builds graph foundation models: GraphToken injects learned tokens, yielding substantial performance gains [32]; Graph2Token aligns molecules with text; and recent surveys chart tross-domain transfer [27] 23 These two threads, task
benchmarks and graph- LLMs, form the empirical backdrop for our ISF theory.
Understanding transformers for graphs The mechanisms originate from graph learning methods, with detailed comparisons of graph neural networks, graph transformers, and decoder-only trans- formers in Appendix C Theory now probes how vanilla Transformers perform graph reasoning. Log-depth models suffice. and are necessary, for connectivity and cycles [17], while width can trade for depth [29]. ALPINE [24] shows GPT layer embeds adjacency and reachability, validating on planning tasks; two-layer decoders trained on shortest-pate -atts learn spectral line une-graph embeddings instead of Dijkstra-style rules [3]. Surveys relate attention power to Weisfeiler-Lehman bounds and
over-squashing limits [13 [9]: scalable variants such AnchorGT mitigate O(n²) cost without losing accuracy (34]. Hierarchical distances or sparse global attention keep Transformers compet-
itive large molecular graphs (9 8 30). Collectively, these studies view attention heads as seaucedd-neighourhhoo selectors-exache the mechanism ISF formalises via filtration depth.
7
Conclusion
This paper explores how decoder-only Transformers perform substructure reasoning over graphs represented as text. We propose ISF to model how substructures are progressively identified across layers. Our analysis shows that extraction accuracy depends substructure size, model depth, and input format. We further validate ISF in LLMs, revealing consistent internal mechanisms. Extending this framework, introduce the Tins method to handle composite and attributed graphs. These findings provide a unified view of how Transformers and LLMs reason over structured data.
Acknowledgement
Xinnan Dai, Jay Revolinsky, Kai Guo, and Jiliang Tang are supported the National Science Founda- tion (NSF) under grant numbers CNS2321416 IIS2212032 I1S2212144, IIS 2504089, DUE2234015, CNS2246050, DRL2405483 and IOS2035472, the Michigan Department of Agriculture and Rural Development, US Dept of Commerce, Gates Foundation, Amazon Faculty Award, Meta, NVIDIA, Microsoft and SNAP.
References
[1] Gregor Bachmann and Vaishnavh Nagarajan. The pitfalls of next-token prediction. In Interna- tional Conference on Machine Learning, pages 2296-2318, PMLR, 2024.
[2] Lijie Chen, Binghui Peng, and Hongxun Wu. Theoretical limitations of multi-layer transformer. arXiv preprini arXiv:2412.02295. 2024.
[3] Nuo Chen, Yuhan Li, Jianheng Tang, and Jia Li. Graphwiz: An instruction-follee following language model for graph computational problems. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 353-364, 2024.
10

---

[4] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances neural information processing systems, 33:10383-10395, 2020.
[5] Andrew Cohen, Andrey Gromov, Kaiyu Yang, and Yuandong Tian. Spectral journey: How transformers predict the shortest path. arXiv preprini arXiv:2502.08794, 2025.
[6] Xinnan Dai, Qihao Wen, Yifei Shen, Hongzhi Wen, Dongsheng Li, Jiliang Tang, and Caihua Shan. Revisiting the graph reasoning ability of large language models: Case studies in translation, connectivity and shortest path, 2024. URL /tttps://aaiiii www.iiii.gg/.....oooooo aas///as/2/000 09529
[7] Xinnan Dai, Haohao Qu Yifei Shen, Bohang Zhang, Qihao Wen, Wenqi Fan, Dongsheng Li, Jiliing Tang, and Caihua Shan. How do large language models understand graph patterns? a benchmark for graph pattern comprehension. In The Thirteenth International Conference Learning Representations, 2025.
[8] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012. 096999 2020.
[9] Vijay Prakash Dwivedi, Yozen Liu, Anh Tuan Luu, Xavier Bresson, Neil Shah, and Tong Zhao. Graph transformers for large graphs. arXiv preprint arXiv:2312./1109, 2023.
[10] Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. Talk like a graph: Encoding graphs for large language models. In The Twelfth International Conference on Learning Representations, 2024.
Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: A theoretical perspective. In Thirty-sevnnth Conference on Neural Information Processing Systems, 2023. URL (RLLLttpss//ppeeeeeeev.e.o www.er/vwwii.eeteo/omotieee. AHgADgy
[11]
[12] Guhao Feng, Kai Yang, Yuntian Gu, Xinyue Ai, Shengjie Luo, Jiacheng Sun, Di He, Zhenguo Li, and Liwei Wang. How numerical precision affects mathematical reasoning capabilities of Ilms, 2024. URL http:::ttta/at::
wwwp/rg////aaaaeee 13857
[13] Luis Müller, Mikhail Galkin, Christopher Morris, and Ladislav Rampášek. Attending to graph transformers. arXiv preprint ar arXiv:2302.0418., 2023.
[14] Luis Müller, Daniel Kusuma, Blai Bonet, and Christopher Morris. Towards principled graph transformers, Advances in Neural Information Processing Systems, 37:126767-126001. 2024.
[15] Miao Peng, Nuo Chen, Zongrui Suo, and Jia Li. Rewarding graph reasoning process makes Iims more generalized reasoners. arXiv preprint arXiv:2503.0080 2025.
[16] Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):177, 2014.
[17] Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Halcrow, Bryan Perozzi, and Vahab Mirrokni. Understanding transformer reasoning capabilities via graph algorithms. Advances in Neural Information Processing Systems, 37:78320-78370, 2024.
[18] Abulhair Saparov, Srushti Pawar, Shreyas Pimpalgaonkar, Nitish Joshi, Richard Yuanzhe Pang. Vishakh Padmakumar, Seyed Mehran Kazemi, Najoung Kim, and He He. Transformers struggle to leam to search. In The Thirteenth International Conference on Learning Representations, 2025. URL
https://openrevier: net. http://foommm.ddddBcBiiirrr
[19] Ahsan Shehzad, Feng Xia, Shagufta Abid, Ciyuan Peng, Shuo Yu, Dongyu Zhang, and Karin Verspoor. Graph transformers: A survey. arXiv preprint arXiv:2407.09777, 2024.
[20] Jianheng Tang, Qifan Zhang, Yuhan Li, and Jia Li. Grapharena: Benchmarking large language models on graph computational problems. arXiv preprint arXiv:2407.00333 2024.
[21] Heng Wang. Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can language models solve graph problems natural language? Advances in Neural Information Processing Systems, 36:30840-30866 2023.

---

[22] Jianing Wang, Junda Wu. Yupeng Hou, Yao Liu, Ming Gao, and Julian McAuley, Instructgraph: Boosting large language models via graph-centric instruction tuning and preference alignment. arXiv preprini wrXiv:2402.08785. 2024.
[23] Runze Wang, Mingqi Yang, and Yanming Shen. Bridging molecular graphs and large language models. Proceedings of the AAAI Conference on Artificial Intelligence, 39(20):21334 21242, 2025.
[24] Siwei Wang, Yifei Shen, Shi Feng, Haoran Sun, Shang-Hua Teng, and Wei Chen. Alpine: Unveiling the planning capability of autoregressive learning in language models. In A. Glober- son, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Ad- vances in Neural Information Processing Systems, volume 37, pages 119662-1 19688. Curran As- sociates, Inc., 2024. URL htttps://prooeeeddnggs www.::/..eerrrr..ccccce paper_ f wiles/paperr/000 Pww.Paappr--offoeeeeeeeeeeeeee pdf
[25] Siwei Wang, Yifei Shen, Shi Feng. Haoran Sun, Shang-Hur Hua Teng, and Wei Chen. Alpine: Unveiling the planning capability of autoregressive learning in language models. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[26] Yuxiang Wang. Xinnan Dai, Wenqi Fan, and Yao Ma. Exploring graph tasks with pure Ilms: A comprehensive benchmark and investigation. arXiv preprint arXiv: 18771, 2025.
[27] Yuxiang Wang. Wenqi Fan, Suhang Wang, and Yao Ma. Towards graph foundation models: A transferability perspective. arXiv preprint arXiv:2503.003363 2025.
[28] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu. Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9()):133-533 2018.
[29] Gilad Yehudai, Clayton Sanford, Maya Bechler-Speicher, Orr Fischer, Ran Gilad- and Amir Globerson. wipth tradeoffs in algorithmic reasoning of graph tasks with transformers. arXiv preprint arXiv:2503.0/885, 2025.
[30] Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform badly for graph representation? Advances in neural information processing systems, 34:28877-28888 2021.
[31] Yizhuo Zhang, Heng Wang, Shangbin Feng, Zhaoxuan Tan, Xiaochuang Han, Tianxing He, and Yulia Tsvetkov. Can I1m graph reasoning generalize beyond pattern memorization? In Findings of the Association for Computational Linguistics: EMNLP 2024, pages 2289-2305, 2024.
[32] Qi Zhu, Da Zheng, Xiang Song, Shichang Zhang, Bowen Jin, Yizhou Sun, and George Karypis. Parameter-efficies efficcien tuning large language models for graph representation learning. arXiv preprint 2XXv:22404112711, 2024.
[33] Wenhao Zhu, Tianyu Wen, Guojie Song. Liang Wang, and Bo Zheng. On structural expressive power of graph transformers. In Proceedings of the 29th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 3628-3637, 2023.
[34] Wenhao Zhu, Guojie Song, Liang Wang, and Shaoguo Liu. Anchorgt: Efficient and flexible attention architecture for scalable graph transformers. In Proceedings of the Thirty-Thrrd International Joint Conference on Artificial Intelligence, IJCAI 2024, Jeju, South Korea, August 3-9, 2024, pages 5707-5715. ijcai.org, 2024.
12

---

NeurIPS Paper Checklist
Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope?
Question:
Answer:[Yess Yes]
Justification:(Ys))
We have claimed the scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer:[Yes,
Justification: [Yes]
We have discussed limitation
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification:
[Yes] We have the assumptions and proofs
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: [Yes]
We have the experimental results
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [Yes]
Justification: [Yes]
We have the description in the appendix and provide the code in the
supplement material
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cmm ec/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips. //nips.cc/ppl wwwppbblccgguiicuceccccccooooope /etggudddsse/eebbbinninn htt.SSbbbiiiiooooiiiiiooooi for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
[Yes] we've ve set the experiment details
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
[Yes] Yes, the experiment statistical significant.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
15

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
[Yes] We've included it in the appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: [Yes] We' ve reviewed
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
[Yes] Yes, we'v we've discussed
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer:
[NA]
Justification:
[NA] No such risks
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer:[Yes)
Justification: [Yes] We've cited
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets. Researchers should communicate the details of the dataset/codeemmodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA] The paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA] the paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [Yes]
Justification: [Yes] we only use LLMs for writing and editing
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy for what should or should not be described.
19

---

Table Comparison among GNNs, Graph Transformers, and Decoder- Only Transformers (LLMs).
GNNs
Graph Transformer
Decoder-Only Transformer
Input
Discrete graph data (node features, ad- jacency matrix)
Discrete graph data (node leatures, ud- jucency matrix)
Textual description of graph
Oulput
(e-g. count) lixed size vector (egg. for classilication
value (e-g. count) size vector (e.g. for classification)
forming a
readable structural description in indefinite longth
Learning tion
Facode graph message passing and neighborhood aggregation; super- scalar oulputs
Fncode graph graph-aware attention; supervised on scalar out-
Next-token prodiction over graph- structured text
puis
Mechanism
1-WL
k-WL
SEG-WL 33
The proposed ISF (Ours)
Appendix
A
Boarder Impact
In this work, we present new insights into how Transformers solve the substructure extraction task, offering a deeper understanding of their internal mechanisms. Our contributions span three key areas: (1) we introduce a novel concept Induced Substructure Filtration (ISF), instructing L.LMs in structure data understanding: (2) propose decomposition basdd approach for tackling complex substructure reasoning by breaking down intricate patterns into simpler components, enabling more efficient extraction. This concept of thinking in substructures
generalize beyond graph tasks-for example, complementing step-by-step reasoning with pattern-by by-pttterr thinking; and (3) we provide both theoretical and empirical evidence supporting the development of graph foundation models, highlighting the potential of Transformers as backbones for structured learning tasks.
B Limitation
In this work, we focus primarily on the fundamentals of the substructure extraction task. However, other Mobstructure-reltte tasks remain to be explored in future research. Additionally, current study provides a high-level overview of decoder-only Transformers, leaving out theoretical details. Future work can extend this foundation to develop more comprehensive and rigorous understanding.
C Related work
The mechanisms by which machine learning models learn graph-related problems have been widely studied, ranging from graph neural networks to transformers. However, due to their differing ontut- formulations. the underlying mechanisms vary substantially, as summarized in Table
D
More on Theoretical Analysis
D.1 Preliminaries
Let G (V. E) be directed graph, where V {u1. N(e;)) = {u V (v,,v) E} = {o! ..... "."'" as the set of its neighbors. We formally define two sequence representations of the graph G where each vertex identifier (v;, u?) and the special symbols """"""""""""" "!") are treated as individual tokens.
{.i...., Un). For each vertex v; V. denote
The adjacency list sequence representation AL(G) is constructed by concatenating blocks of tokens for each vertex vi, separated by special token " The block for vertex 2; consists of the token o; and token ".", followed by the sequence of tokens representing its neighbors u........... Formally, we have the following definition.
Definition D.1 (Adjacency List Graph Representation). For a directed graph G (V, F) with V {er,-- , }. denote (wv) {u V (v, E} {uf.... , }
as the set of its ,.
20

---

neighbors. The adjacency list graph representation of G' is defined as AL(G) (v " ue:: .. ; "."
Uni
; 1 (.
The edge list sequence representation EL(G) is constructed by sequentially listing token pairs (vi, v/) representing edges, separated by the "I" token. We give the formal definition below.
Definition D.2 (Edge List Graph Representation). For a directed graph = (V, B) with V {Vi,-.- , Jn J. denote N (vx) {u V (e%, v) E E} {e "u," } as the set of its neighbors. The edge list graph representation of is defined as
EL(G) = (vi; of: " 1...
" U1; "Y" "I" "I" ons o T.: ; Un U
We also define adjacency matrix for graph G as A()), where
1, (n) uy) E
A(G) = 00 (u, 12) $ E
In the subsequent analysis, we need a vectorized representation of a matrix or tensor. We first define tensor vectorization as follows.
Definition D.3 (Tensor Vectorization). Let AA be a d-dimensional tensor (or tensor of order d) with dimensions (M1, n2...... na), denoted as A E R X x*a The elements of AA are indexed by tuple (4) 12................... ..........)...... i4). where i n for f1.2.....d}
The vectorization A, denoted as vec( is a one-dimension vector a RR,, where II nik is the total number of elements in A.
The elements of the vector of the tensor A in row-major order. Specifically, the tensor element da....... maps to the vector element ay, where the index j (1 S S.S.A. N) determined by the following formula:
(a1, 02:..., ,.) aN) are obtained by arranging the elements Az..i.....
j = 1=1+ Σ (im
II
71
(=m+1
Here, the empty product convention is used, i.e., II Th - 1.
Remark D.4. This indexing scheme corresponds to ordering the elements such that the last index ia varies the fastest, followed by the second-to-last index id- and so on, with the first index i varying the slowest. For example, in the case of matrix (d = 2), this corresponds to concatenating the rows of the matrix.
Definition D.5 (Subgraph Isomorphism Indicator Tensor). Let G = (V, F) and G' = =(V,, F') be two directed graphs, referred as the target graph and the query graph, respectively, Let V and l: = V' and denote V = {v1, 02,.... Un) V = (v1, ",,,,,,,,,
The subgraph isomorphism indicator tensor T(G, G') associated with G, G", and the chosen vertex orderings is a k-dimensional tensor of size n X n X ... X n. An element T(G, G") ii of the tensor T(G, G"), indexed by tuple (j1, ........... (..) where 1 ji n for all / E k). satisfies:
1, the mapping f V - satisfies both conditions:
defined by f(x/) = Un for I,..., k
(i) Injectivity: Uji U......, Uj. are distinct vertices in V (i.e., ji * fm for all 1 < < $ k).
T(G, G'G,G")innnn Disamaade
(ii) Edge Preservation: For every directed edge (v/, ot) E E', the directed edge (f()), f(v()) (ry, Uj,) exists in E.
S 0, otherwise.
That is, T(G, G') "' = if and only the sequence of target vertices (M/ ("),.... Ui forms subgraph in G that is isomorphic to G' under the mapping implied by the indices and the fixed vertex orderings.
Throughout our theoretical analysis, we consider log-precision auto- Transformer, instead of constant-precision Transformer. See [1] Appendix B] for more discussions.
21

---

D.2 Technical Lemmas
Lemma D.6 (Adjacency Matrix Extraction).
(i) For any integer n, there exists a two-layer log-precision Transformer with single attention head and hidden dimension O(n²), such that for any directed graph G = (V, with
V n, the Transformer can output vec(A(G)) for input sequence AL(G).
(ii) For any integer n, there exists a two-layer log preepiieisoon Transformer with single attention head and hidden dimension O(n²), such that for any directed graph G (V, E) with
V n. the Transformer can output vec(A(G)) for input sequence EL(G).
Proof. We need token embeddings to encode the index of the node (i for vertex v;), the type of the node (v; or ). and absolute positional embedding.
The first attention layer finds all the edges in G. For adjacency list graph representation, we COPY the value of (i 1) (from the position v;) to the positions ii ... " th Applying [T] Lemma C.7] and setting (q: k2) = x; æ,1lā. where æ; is the type of the node in the embedding suffices. For edge list graph representation, suffices to COPY from the previous token. Thus we can set (g,, k,) = (i j 1)²
The subsequent MLP calculates vec(A(G((f), vy)l)) for each edge. Notice that the value on index can be formulated as
(==n((-11+5
ReLU - n (i 1) - (i 1) 1) -]
j + R n 1--j-11 (I)
2ReLU
By Lemma C.2], Equation can be calculated with constant hidden dimension.
The second attention layer aggregates all vec(A(G((us, vy) for each edge. We first calculate the MEAN of all valid vec(A(G[[u) Ui, v)) from the last layer by [1] Lemma C.8]. The result can be expressed as vec( (A)))) where
(Us, U2) E E (,), $ E
A'G)) - O,
n²:
Thus we can get ((G) by
A(G); = -
A') n2
which can be implemented in the subsequent MIP by Lemma C.2].
Lemma D.7 (One-Step Subgraph Isomorphism Indicator Tensor Calculation). Fix integers n, k, m 2 1. Let V {u',...,, "i......y v be set of k vertices, and let F(V') = (Vi, Vi...., Vi be a k- node m-filtration on V" (defined in Definition B.I). There exists m two-layer MLPs with GeLU activation f1,... f.n each with hidden dimension O(n²k?), such that for any directed graphs CV, E) with V {UI,.... vn) and G' = (V',E'), E'), fi can output vec ("V for input vec(A(()) vec vec(A((") @ (ec
(% denotes concatenation), where Vo Ø.
Proof. Denote k; [V/l. Without loss of generosity, we assume V = =f11," 2/. Notice that T(G, G)), Se. can be calculated as
T(G, VGG,G.LA ((G,G,--) Je,1
Σ
[A(G"),, - A(G''
z. z.ski a> 1
Thus it suffices to calculate the value of A for 1 111,I,10 x, x, S x' 1/ S n. By
Lemma C.1], this can implemented with 2n22k) hidden dimension.
D.3 Proofs for Section 3
Theorem
(Expressiveness for Progressive Identification). Given a k-node m-filtration F(V') on V ......,))) For any directed graphs G (V, E) (V) n) and G"
3.3
(V',E"),
22

---

log- log-precision Transformer with m 2 layers, constant heads, and O(n²) hidden dimension can output ve (G, (VV) at layer i for i E [I...., m}.
Theorem D.8 (Formal Statement of Theorem 3.3 Fix inlegers n 2 k 2, 2,m Let V
be a k-node m-filtration on V. There exists log-precision Transformer with m 2 layers, constant number of attention heads, and ((n²) hidden dimension, such that for any directed graphs G = (V. E) with V = (U1..... 3n and G' =(V, E"), the Transformer processing G, G' can output vec(T(G, (((V))) at layer + for i E (1,...,m, Here, vec(.) is the vectorization for tensor (formal defined in Definition D.3
{u',,... d be sel of k vertices, and let F(V") " (V V....,, Vm))
Proof. The first two layers of Transformer calculates vec(A(G)) and vec(A((")) ) for graph G, G'. The desired output is at the last token for each graph, respectively. By Lemma D.6 this can be implemented with (n²² hidden dimension, regardless the representation of G.G
For the next m layers, we first apply [1, Lemma C.7] to COPY vec(A(()) vec(A(G")) in the attention layer. This can be implemented by adding special marks on the last token for each graph. In the subsequent MLP layer, we apply Lemma D.7 to calculate desired results with On k2) hidden dimension.
D.7
Theorem 3.5 (Expressiveness for Pattern Extraction). Under Assumption 3.4 for directed graphs G = (V, E.) ) (VV)= n) and G' = (V', EE) ([V' = k), log-precision Transformer with constant depth, constant heads, and O(n²) hidden dimension can output the unique k-tuple of vertices (U.,..... U(gg) for which T(G, G') ( =
Theorem D.9 (Formal Statement of Theorem 3.5 Fix integers
k: 1, and let V (u',....,dy v/}} There exists a log rog-precision Transformer with constant depth, constant number of attention heads, and Onn*)) ) hidden dimension, such that for any directed graphs G = (V. F) with V = -Vi,--.. . Fu and G = (V', satisfying Assumption 3.4 the Transformer processing G, G can output the unique tuple (Vzz...., Us. for which T(G, G' Di =1
Proof. We first take m output ( G))) ) for any directed graphs G, G'. By Assumption 3.4 Rel.U((ee(T(GG,C) G")) is a one-hot vector and can be obtained with a two-layer MLP via 11 Lemma C.2).
in Theorem 3.3
indicating that a constant depth Transformer can
Notice that
1
Σ
is ReLUU(ve
thus by linear transformation we can obtain (i....., .i) for which T(G, G') = 1, from the corresponding one-hot vector (TLLU(ee(T(GGGG)))
The final step is to output (Ui,,.... vi,,) sequentially. This can be obtained by adding one-hot positional encoding in all the output tokens determine the current output position. Therefore, the next token can be obtained by calculating the inner product between (...... (x) and the positional encoding. Since all the steps can be finished in constant layers, we finished our proof.
Extraction). Fix integers 2 k 1. There exists a log-precision Transformer with constant depth, constant number of attention heads, and O hidden dimension that can complete Shagte--hape-Mult--Wiee
Theorem 3.8 (Expressiveness for
Chape-Multii-We
Extraction defined in Definition 3.7 for directed graphs G = (V, E) ( n. and G = (V', , FE') r[V' = k)).
Theorem D.10 (Formal Statement of Theorem 3.8 Fix integers n 2 k 2 1, and let V' {u',..., J. There exists a log-precision Transformer with constant depth. constant number of attention heads, and O(n²)) hidden dimension, such that for any directed graphs G = (V, E) with V = {ti...., vn and G' = (V', EE', the Transformer processing G, G' can output all the tuples (v.,.... .U.,....,, V.r)) for which T(G, G") M
Proof. Follow the proof of Theorem 3.5 first calculate v ReLU[ G')) which marks all feasible tuples with 1, and 0 otherwise.
Next, we calculate d where of = tn +..... oa by linear projection, and define wf o. of In v.. the feasible tuples are marked as 1, 1,2, and otherwise. By [I]] Lemma C. x2 3 can be obtained with two-layer MLP.
23

---

The final step is to determine which position in which tuple the next-token corresponds to. This can be obtained by adding special positional encoding in the outputs. When the Transformer need to output the z-th tuple, it can first obtain the corresponding one-hot vector by the following formula:
ReLU(v
1) ReLU(v*
1) 2 ReLU(v* - =2),
then following with the proofs in Theorem 3.5 to output the current position. By 11 Lemma C.2], the above steps can be obtained with constant-layer MLPs, which concludes our proof.
Theorem 3.10 (Expressiveness for Multi- Shwpe-Single-Neee Extraction). Fix integers n 2 k 2 There exists log- log-precision Transformer with conslant depth, constunt heads, and O(n²) hidden dimension that can complete Multi-Shape-SS Seappe--ingl-Nuur Extraction defined in Definition 3.9 for
directed graph G = (V. F) (VV) n) and any target subgraph G² = =V', E') with [V] k < k
satisfying Assumption 3.4
Theorem D.11 (Formal Statement of Theorem 3.10p. Fix integers 2 121 There exists a log-
precision Transformer with constant depth, constant number of attention heads, and O(n") hidden dimension, such tha any directed graph G = (V,E) (with V = {U ".......,,,..................... and G' = E") (with V' = {t',.... Ugg where k' S k) satisfying Assumption 3.4 the Transformer processing G, G' can output the unique tuples (Vigs-..,,%, Viy for which T(G G') Kayrr = 1.
Proof. The proof is based on that of Theorem 3.5 and we extend G' to &² with & - k' extra isolated node.
Now, for more general case that k S k. there may exist multiple tuples (V vie) such that T(G, ... 1. However, by Assumption 3.4 all these tuples shares the same it, , Therefore, can first obtain one-hot vector via
Re + ReL.U(b -2) -2 ReLU 1),
where v is defined in the proof of Theorem 3.8 Finally, it suffices to output the corresponding
(Di .gg). which similar the final step of Theorem 3.5
D.4 Theoretical Results for Section 5.1
Assumption D.12. For directed graphs G = (V, E) with V = foi.... "......,,,, G (V', E') with
V fe/.... ... 2 and Vi, "., V C V", and collection of vertex subsets Vi,..., V C V
is assumed that:
(i) There exists unique k-tuple of distinct vertex indices (4 (i1....,,44 (4) from {1,..., n} such that T(G, G') (") 1.
(ii) For each j E fl.....t). t). there is a fixed constant c 2 such that the number of distinct [V/|- V/I-tuples of distinct vertex indices (i1,..., (113)) from (!. for which T(G, G'VV[Dii.... My = is at most e.
Theorem D.13. Fix integers n 2 k and 2 1. Let G' = (V', E²) be a fixed directed graph with V' toh...., v.J. Let Vi...., Vú be a collection of subsets of V' such that G' is covered by the subgraphs induced by these subsets, meaning V = =U V2 and E' S U (VG'VV)) Denote
q max,e((.....) [V]..
There exists log-precision Transformer with constant depth, constant number of attention heads, and O(n + + (2) hidden dimension, such that: For any directed graph G = (V, E) (with V {ui,..., ) that, together with the predefined G' and subsets Vi...., Vi, satisfies Assumption D.12 (where is the constant from Assumption D.12), the Transformer processing can
(i) First, for each j I,..., output a special token (S,), then identify and output all distinct Vi -tuples of vertices (V:,...., " from G such that T(G, G' [V]]))e...nd 1.
(ii) Subsequently, output a special token (ANS) and the unique k-tuple of vertices (Viy...., Nay) from G such that T TGG G") Dir...ik = 1.
Remark 1.14 we assume e, l are both constants, then the result becomes 0 which demon- strates the ad advantages of thinking in substructures.
24

---

Remark D.15. Theorem D.13 highlights a trade-off concerning the hidden dimension complexity.
O(n c + en). This complexity is influenced by:
t: the number of intermediate decomposition steps, or the CoT steps.
q: the maximum size of any intermediate subgraph GV]] considered during these steps.
the maximum number of instances (matches) in G' for any such intermediate subgraph G'V]].
When increases (employing more, potentially smaller, intermediate steps), q generally decreases, However, c may increase, as simpler or smaller intermediate subgraphs could appear more frequently, In this scenario, the n component of the hidden dimension tends to decrease, while the cf + c2 components are likely to increase.
Conversely, when t decreases (employing fewer, potentially larger, intermediate steps), g generally increases. Conrespondingly, e may decrease, as more complex or larger intermediate subgraphs could be less common. This tends to increase the n component, while the cx + (2 components likely to decrease.
Thus, the optimal decomposition strategy for minimizing the required hidden dimension depends on the interplay between these parameters, dictated by the specific problem structure.
Proof. We first design the necessary embeddings.
1. For the special token (Sy), need q² dimension vector representing vec(A)))V)) (if [V]] < q. then we need to add q - -V]] isolated nodes); and nº dimension vector representing (e)( where T is dimenniional tensor of size n x n X ... x n defined as:
(
[{. 00 1, otherwise
AI = VVl. & lyi 1
S q.
=1
T de =
(2)
2. For the output answer tokens step (i), we need a cln dimension vector. For vi in the y-th tuple for the subgraph induced by Vj. the embedding satisfies: the value on the cn(j-1) +a dimension is ig, while the others are 0. Here, x' is the node us, corresponds to in origin G' (u'r).
To get the desired output sequence, need complete the following tasks:
Task 1: At the position of (S,), we need to get all the tuples (i1, (1yy)....113)) for which T(G, G'VV
Task 2: At the position of (ANS), we need to get the unique tuple (i1,..., in) for which
T(G, G*) G")
For task 1, the idea is similar to the proof of Theorem 3.8 We first use Lemma D.6 to extract vec(A(G)) for input graph G, then apply [I] Lemma position. Next, we calculate vec (eG(T"(GG' Here, G'VV is obtained by adding g - [V] isolated nodes on G'VV;]; and
C.7 COPY vec(A(G)) to the current
1, iT (yg) = and 1 = ig =
T (G,G'1V)) h.r dg
0, otherwise
Thus, vec(T'(C (G, G(VYD) is a n dimensional vector. Notice that T' G'VV dy can be calculated as
Σ (GVV3) A(G) - A - AGVVV))
-7(0) -Ter
25

---

where TU) is defined in Equation ( while the only difference is we only want the first VV dimension. This can be implemented by modifying the positional encoding to give the correct position for the next-token.
The following steps are similar to the proof of Theorem 3.8
For task 2, first aggregate all the previous VVjl-tuples for eration in [1Α Lemma C.8]. We then multiplies the result with the sequence length (which can be obtained by absolute positional encoding). After this, we get cin-dimension vector (b),1,-.. ,i,,, b2.1, ... b, Dr,e). Here, big is a n-dimension vector corresponds to the j-th tuple for the subgraph induced by V."
1,... , using MEAN op-
Next, we maintain t-dimension tensor Tams of size с c x .... x c, defined as
= 0, if " ,bii, can be combined as G"
11. 1, otherwise
By Assumption D.12 there exists unique t-tuple (i1...., de) such that i1," = 0. Notice that b bi,i. can be combined as G' if and only if the following holds:
L1 t, bz,i, + 0
s x <<><5=> S t, V1 S 2 S n, (bx,i.)= (by,,,)= or (br,i.== =0 or (by,i,)== (3)
Since (by,ig)= 10. ... ,n), Equation 3 is equivalent to
vI ReLU 1 - Σ (barie) =0
15=5m
V1 M<<=<y<> 11 S = S ni, ReLU)(be,.e) - (by.i,)al ReLU) -(bo..)2)
(ba.i.) or (by.i,)= =
The second condition is equivalent to v1 < < y t. v1 I 2 n, ReLU [1 - ReLU (by. ReL ReLU|[(bg.ie
(b2,ie)2l
+ ReLL (bz,..)al ReLU - (by, )=l 11,
or
ReLU [1 ReLU [1 ReLU (by,,.)) ReLU)((yy..)) (bm,i..)l]
RReLU[1 (bz, )=1 ReLU[1 (by.t,)=ll 0.
Thus, for any tuple (i., dt). we can get f,.--..,, via an MLP with constant layers and (nt?² hidden dimension. Notice that there are many components remaining the same when calculating different Th .i We can calculate
ReLU 1 ReLU - ReLU(((pp.))): (bpa.02)2 ReLU((bpp)e)== - (bpl-
ReLLU[1 (p) ReLU[1 (2)]l
for all (p1, 91), (p2, 92) pairs and 1 S E n, which are (c)2tnn.. Each can be calculated via an MLP with constant depth and constant hidden dimension.
Finally, we will calculate the unique I-tuple (i1,...,44) such that T de 0. Notice that
Σ
ReLU(1
Thp ).
Σ b
1Sh
IsiSt
which can be calculated via an MLP with constant depth and Oce²) hidden dimension by Lemma C.I].
D.5 Theoretical Results for Section 5.2
Theorem D.16. Fix integers n 2 > 1, and let V
(oi..... ..... Fix
a feature function vp : VUV' + Z. There exists a log-precision Transformer with constant depth, constant number of attention heads, and O hidden dimension, such that for any directed
26

---

Table 6: Hyperparameter details
heads
embedding
drop out rate
batch size
learning rate
max epoch
12
384
0.2
2048
0.001
40000
graphs G= GV. E) and G' (V',E)) the Transformer processing G, G' output all the tuples
(Ui):-. Viy) that satisfy both of the following conditions:
(i) Subgraph Isomorphism: The subgruph of G induced by the set of vertices foir... is isomorphic G' under the mapping v/p + Vi, for p {1,..,, kk. That is,
, Mix
(ii) Feature Matching: For all p {L...., k}, the feature of the p-th vertex in the tuple from G matches the feature of the p-th vertex in V', i.e, (pU;,) ((()))
Proof. The proof is similar to that of Theorem X X (G, G*) as
3.8
We define a k-dimensional tensor of size
1,
if the mapping / V' - V defined by f(1)) = Vij for I = 1,..., satisfies both conditions:
Injectivity: Uj Via.-.., U5, distinct vertices in V (i.e., ji * Jm for all
m S k).
T' G*) Je
(ii) Edge Preservation: For every directed edge (o ryy E E", the directed edge (f(r), f(()) = (Di, y/ exists in E. (iii) Feature Matching: For all E {1,... kj. the features of the p-th vertex match, i.e., :pvv,,) (1()).
S 0, otherwise.
Notice that (G, G¹) j') can be obtained
T(G, G
Σ
15E5K
or
G(G,G') di
Σ (ReLU((((,)) - (p((() + ReLU(((()))) - ((v1,))]
Therefore, it suffices to COPY the feature while constructing the adjacency matrix A(G), A(G"). And suffices further calculate the value of ReLU [y((;) -(())] ReLU [f(e() - ((e))] which requires (nk) hidden dimension in total (by Lemma C.2]).
E Experiments setting
Here, we provide the details of our experimental setup. We use a lightweight version of the GPT-2 model, which is an implementation version of nano-GPT, with hyperparameters listed in Table 6 10% the data is used for validation, and the model is saved when the validation loss reaches its minimum. All experiments are conducted on machine equipped with 8 NVIDIA A6000 GPUs.e.
E.1 training details in input formulations
We take more 50,000 graphs for training and testing. Each graph contains target substructure: either a triangle, square, or pentagon. While the number of training samples varies, the test set size remains fixed, as shown in Table 7 Since this a toy example, we set the Transformer's 's hidden dimension to small size of 192.
27

---

Table 7: The dataset information for the AL and EL comparison
#Training data
#Test data
#Node
Triangle 5000
1000
5
Square 15000
1000
8
Pentagon 35000
1000
8
Table 8: Performance across epochs for Square (4 layers) and Pentagon (5 layers).
Epoch
10000
20000
30000
40000
50000
60000
Square (4 layers)
AL
0.97 1 0.004
0.98 1 0.003
EL 0.83 1 0.078
0.93 1 0.050
0.99 1 0.006
Pentagon (5 layers)
AL
0.69 1 0.017
0.73 1 0.058
0.84 1 0.031
0.92 1 0.004
EL
0.61 1 0.017
0.60 1 0.019
0.74 1 0.018
0.87 1 0.010
0.89 + 0.0056 0.93 + 0.044
E.2
Multi-Shape setting
To evaluate the discrimination ability of Transformers in detecting multiple structures, we set the evaluations from four perspectives: different numbers of nodes (Triangle vs. Square); 2. the same number of nodes but different numbers of edges (Square vs. Diamond); 3. the same number of nodes and edges, but different edge directions (F-triangle vs. T-triangle); 4. whether the substructure forms closed loop (Square vs. Path). We construct 600K question-answer pairs to train 4-layer transformer model. Since triangles require less training data, as suggested the Multi-num task, we set the training sample ratio of Triangle to Square to 1:6, while maintaining 1:1 ratio for the other substructure pairs.
E.3 Efficient of EL and AL
EL performs worse than AL when trained for the same number of epochs, but it eventually reaches comparable performance. In our results, we selected the epoch at which AL achieves its best performance. However, we will also provide additional information indicating when EL catches up with AL, as shown in the Table below::
EL with longer input lengths requires more training epochs achieve the same performance AL. Although EL and AL are theoretically equivalent in their ability to represent graph structures, the longer input sequences in EL lead to less efficient learning. We will clarify this point in the revision.
E.4
LLMs Experiments
E.4.1
Evaluation on substructure detection
In substructure detection, we the question prompt as: Given structure G, Node 1 connected to Node 2, 3; Node 2 is connected to.... List all of the square patterns in the graph the form of: [#1, #2, #3, ...]
Meanwhile, we set the answer as:
The answer is [1, 3]
For the triangle detection task, we 1,000 training samples and 200 for evaluation. Using supervised fine-tuning (SFT) over 4 epochs, we achieve 58.86% accuracy on the test set. The model responses suggest that LLaMA331-8B-Insst Instrruccct still generates explanatory content, including code, during answer generation.
We also evaluate L.LM performance on the square detection task using 283 test samples, which contain only four distinct answer types. As shown in the Table lightweight LLMSs fail extract meaningful patterns without fine-tuning, Due the high computational cost of training LLMs,
28

---

Table Large Language Models do the ISF process in the middle layers
Model
Llama3.2 2-----2------ttuue
Qwen3-4B Base
Llama3.1 1-BB 1-18--88sttii Instruct
ACC/ finetuned ACC
0.0035 0.4982
0.0141 /..524
0. 0.0035/0.6572
Uaretit se LaM at
Uerra33 3a S the 10
1029
Vis. for non-finetuned
Tratured Laand' T6 TENCE tt byyer
Eeptuned Ulrnall Syee
1064
1043
Vis. for finetuned
Table 10: Concept learning
no-finetune
without topos
with topos
Ilama
0
0 0.50
Qwen1.5
0.75
Qwen3B
0
0
0.85
limit the training data to only include samples with these four answer types, using 480 samples for training and 120 for validation. After fine-tuning, observe significant improvement in accuracy. Additionally, visualization shows that graphs corresponding to similar answers tend to cluster together.
E.4.2 Evaluation on question prompt
evaluate how LLMs align conceptual descriptions with underlying topological structures. Specifi- cally, we test LLaMA3.2-3BB 3-3-IInrutt Qwen2.5-1.5B, and Qwen2.5-3B by setting the temperature to 0.6, running 20 dialogue turns per model, and manually evaluating the responses.
First, we assess whether the models understand the concept of a "house" in graph terminology by prompting them with: What is house in graphs? Giving the graph in the formulate of: 'Node is connected to nodes 2, 3' the baseline setting (without topological prompts), we explicitly teach the concept using natural language definitions generated by Gemini-1.5-P using 200 such concept-descriptiv sentences. For example, a training sample might look like: In graph theory, "house" isn' 't standard term like "tree" "cycle." It usually refers to specific small graph resembling a house drawing. This graph consists of five vertices and six edges. It's formed by cycle of four vertices (the "walls" and "floor") with additional veriex connected to one of the cycle vertices (the "roof peak"). ). In the train with topos setting, we add topology description to the house, which is: The house is described as: G describes and 5.In this graph: Node is connected to nodes 2, S.Node is connected to nodes 1, 1. 5. Node 3 is connected nodes 2, 4. Node 4 is connected nodes 3, 5. Node 5 is connected nodes 1, 2, 4.
We fine-tune each model
undirected graph among 1, 2, 3, 4,
As shown in Table 10 the L.LMs only learn the topological descriptions training with the terminology terms together. The L.LMs do not generate new concepts by the already known knowledge.
E.4.3 Thinkking-in-substtuuuuurss
We use 100K samples for training and 5,000 for testing. Since each composite substructure is com- posed of different sets of decomposing substructures, the required thinking length varies accordingly. A summary of these decompositions is provided in Table II
29

---

Table 11: Max length for each composite substructure extraction
Substructures
[RH)
[(P2)
{PsH]
overall length
Diagnoal
95
55
150
Diamond
55
95
150
House
75
115
190
Complex
80
100
110
290
E.4.4 Transformers for moleculars
In this subsection, we introduce the experimental setup for applying transformers to molecular data. Specifically, we focus the task of functional group recognition, where the goal is to identify the atomic positions corresponding to specific functional groups within molecules. We then introduce dataset, functional group and experimental dataset construction.
Dataset We conduct experiments on QM9 [[6] and PCBA [28]. The QM9 dataset primarily contains quantum mechanical calculated properties of approximately 134,000 molecules, suitable for molecular property prediction and quantum chemistry research. The PCBA dataset, on the other hand, contains activity data for approximately 440,000 molecules against 128 biological assays, making it more suitable for drug screening and bioactivity prediction.
Functional Group We search for molecules containing basic functional groups in the QM9 and PCBA datasets. Specifically, we extract 33,000 molccules containing hydroxyl groups (C-O-H) from QM9, and 13,000 molecules containing carboxyl groups (-COOH) as well 33,000 molecules containing benzene rings (C,H)) from the PCBA dataset. For all these molecules, H atoms are ignored during processing. The maximum number of atoms is 9 for molecules containing hydroxyl groups, while it 121 for both carboxyl- and senzene-containio molecules.
Experimental Dataset Construction For the hydroxyl group identification task, first convert molecular graphs into molecular description inputs by omitting H atom. A simple example of such a description is "0 C: O", and the corresponding answer for the position of the C-O-(H) (H) group is "0.1". We then select molecules containing hydroxyl groups, using 30,000 molecules for the training and 3,000 for the test set.
Similarly, for the identification of molecules containing carboxyl groups and benzene rings, we also convert molecular graphs into molecular description inputs by omitting hydrogen atoms, and generate the corresponding position answers for the target functional groups. We use 10,000 molecules for training and 3,000 for testing in the carboxyl group recognition task. For the benzene ring recognition task, we construct a dataset with 30,000 molecules for training and 3,000 for testing. The maximum input lengths for molecular descriptions are 100, 1000, and 1000 for molecules containing hydroxyl group, carboxyl group, and benzene ring, respectively.
In addition, we construct mixed dataset containing molecules with hydroxyl and carboxyl groups. Specifically, we use 10,000 hydroxyl-containing molecules and 10,000 carboxyl-containing molecules for training, and 1,500 molecules of each type for testing.
30


Reviews:
[{"review_id": "R2xqCLru6l", "reviewer": "Reviewer_CMYh", "summary": "The paper introduces Induced Substructure Filtration to explain how decoder-only Transformers, when fed textual graph descriptions, progressively isolate tokens belonging to a queried substructure across layers. They provide some empirical results and theoretical analysis showing this dynamic in causal transformers and show it generalises to attributed graphs (e.g., molecular graphs). The work aims to explain how sequence-based LLMs perform substructure extraction.", "questions": "- What are the main differences between Theorems 3.3, 3.5, 3.7, and 3.8? Also, what new insights are being gained from these theorems 3.7 and 3.8?\n    \n- The result in 3.2.2. It is not surprising also because the author trains a transformer from scratch and trains using a specified synthetic dataset that helps the model learns the correlation between the sequence of tokens in the prompt and the graph input. What surprises me is when the topology-based prompt encoder fails in the diagonal case. Could the authors elaborate on the reasons for such failure?", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "### Strengths\n- The paper is well-written with nice figures\n- The question posed in the paper is interesting and holds significant impact if properly addressed. However, it would be better if the authors could focus and elaborate on the differences between vanilla causal transformers and other transformer architectures such as GNNs and Graph Transformers.\n\n### Weaknesses\n\n- Results are not new, experiments are toy examples. They donot highlight the main difference between transformers and other graph models such as graph transformers.\n\n- Most experiments are toy experiments where transformers are trained from scratch with well-defined synthetic data. However, the main question, how large-scale pretraining LLMs on textual data can enable model understanding of graph structures and solve graph-based tasks, remains unclear.\n\n- A comparison to GNN models and Graph Transformer using the same set of data for training would be helpful.\n    \n- What is the connection between the graph transformer and the vanilla transformer? If the graph transformer is already well-known for handling graph data, should the transformer be good for well-represented data? The main difference is the positional encoder?\n    \n- The main results (Theorems 3.3, 3.5, 3.7, and 3.8) oversimplify the settings, which assume that the hidden dimensions go up to n^k. The results are not surprising under those assumptions", "was_revised": true, "final_justification": "The authors provided a detailed rebuttal that addresses some of my concerns. I agree that the research question regarding the ability of LLMs on graph reasoning tasks is an interesting research question. Understanding why this capability emerges from large-scale, noisy pretraining and enables zero-shot or in-context graph reasoning is indeed very important for the field. However, the fact that the authors restrict the scope to showing that a decoder-only Transformer trained from scratch on well-defined input–output pairs can perform graph tasks does not seem to address the core question about LLMs. Therefore, I would like to maintain my initial assessment of the paper after the rebuttal.", "rebuttal": "Thank you for your suggestions. We would like to clarify your key concerns below\n- W: decoder-only transformers Vs. GNNS and graph transformers\n\nA:  We respectively point out potential misunderstandings in your comments regarding the motivation and the goal of our paper. We want to clarify them below: \n\nRecent studies have empirically shown that LLMs possess strong capabilities in graph reasoning tasks [1, 2, 3]. At the same time, it is important to understand the underlying mechanisms behind this graph reasoning ability with the textual data [4, 5]. We focus on the substructure extraction task, motivated by prior work [2, 3] showing that LLMs can identify and extract specific substructures from a given graph.\n\nTo bridge the gap, the goal of our paper is to provide **insights into why LLMs can extract substructures from text descriptions of graphs**. As clearly stated in the abstract **How can a decoder-only Transformer architecture understand underlying graph structures?**. We do not aim to argue using transformers to replace GNNs or graph transformers, nor do we propose new algorithms to solve graph tasks.\n\nTo this end, we train **decoder-only** transformers using a **text-based input** format, following the GPT-2 training pipeline, to explore the mechanisms underlying their graph reasoning abilities. Therefore, connecting and comparing with graph-specific encode models such as GNNs and graph transformers are completely beyond the scope of this work. \n\nAlthough it is off topic of our paper, we'd like to introduce the differences between decoder-only transformer and encoder based GNN, and Graph Transformers which have been discussed in the existing papers [5, 6, 7]. GNNs and graph transformers in substructure extractions are models for graph encoding, and the output only limited in the substructure counting, instead of in indefinite length of textual description of substructure. Therefore, the mechanism is totally different as summarized in the Table:\n\n|                                | **GNNs**                                                                                    | **Graph Transformer**                                                      | **Decoder-Only Transformer (LLMs)**                         |\n| ------------------------------ | ------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------- | ----------------------------------------------------------- |\n| **Input**                      | Discrete graph data (node features, adjacency matrix)                                       | Discrete graph data (node features, adjacency matrix)                      | Textual description of a graph                              |\n| **Output**                     | Scalar value (e.g., count) or fixed-size vector (e.g., for classification)                  | Scalar value (e.g., count) or fixed-size vector (e.g., for classification) | Text tokens forming a human-readable structural description in indefinite length|\n| **Learning Formulation**       | Encode graph via message passing and neighborhood aggregation; supervised on scalar outputs | Encode graph via graph-aware self-attention; supervised on scalar outputs  | Next-token prediction over graph-structured text            |\n| **Mechanism** | 1-WL [5]                                                                                       | k-WL [6]/ SEG-WL [7]                                                              | The proposed ISF (Ours)                                                        |\n\n- W: toy examples and how textual data can enable model understanding.\n\nA: We follow the experimental setups of prior studies [4, 5], which suggest that simplified datasets can capture key properties of decoder-only transformers that are also reflected in the performance of LLMs. In line with these studies, we use simplified textual graph data to construct both theoretical and empirical experiments aimed at exploring the mechanism of decoder-only transformers in substructure understanding tasks. The findings from these foundational experiments also support and help explain the behaviors observed in LLMs, as discussed in Section 4.\n\n- W: The result in 3.2.2. It is not surprising and explanations for the diagonal case.\n\nA: As discussed in the previous response, we use simplified settings to uncover the basic and foundational mechanisms of decoder-only transformers. Moreover, we do not assume that the hidden dimensions scale up to $n^k$. Instead, we argue that the number of layers is the most important factor enabling decoder-only transformers to understand substructures, which is the central focus of our main results. To support this, we present an additional  experiment in which we increase the hidden dimension while training a transformer to detect triangles, using 300K training samples:\n\n| layer      |     1 |     2 |     2 |     3 |\n|------------|------:|------:|------:|------:|\n| hidden size    |   768 |   192 |   384 |   192 |\n| model size | 7.10M | 0.89M | 3.55M | 1.33M |\n| ACC        |  0.37 |  0.75 |  0.76 | 0.98 |\n\nThe results show that increasing hidden size alone does not improve accuracy. For instance, 2 layers with 384 hidden size perform similarly to smaller models. In contrast, 3 layers with 192 hidden size achieve 0.98 accuracy (1.33M parameters), while 1-layer (768) and 2-layer (384) models only reach 0.37 and 0.76. This suggests that substructure understanding relies more on model depth than size. We will add this in the revision.\n\n- Q: differences between Theorems 3.3, 3.5, 3.7, and 3.8\n\nA: We first establish the basic case, single-num-single-shape, in Section 3.1.2, where only one substructure is to be extracted. Theorem 3.3 provides the foundation for how substructure extraction unfolds across layers, while Theorem 3.5 shows that the Transformer identifies the correct substructure through internal computation of a subgraph isomorphism indicator, rather than relying solely on next-token prediction. In Section 3.1.3, we address a more complex setting involving multi-num-single-shape and single-num-multi-shape cases, as illustrated by Theorems 3.7 and 3.8. These results lead to a new insight: the ISF process can operate simultaneously across multiple substructures with various prompts. This understanding helps explain how LLMs are capable of extracting diverse substructures in varying quantities [3]. Furthermore, Theorems 3.7 and 3.8 provide the theoretical foundation for the Thinking-in-Substructure phenomenon discussed in Section 5. We will further clarify these points in the final version.\n\n- Q: results in 3.2.2 setting\n\nA: In the 3.2.2 setting, substructures are not explicitly specified, which is the extension of single-num-multi-shape setting. The dataset includes diverse substructures and question types, covering both terminology and topology, all trained within a single transformer. As a result, a single graph may contain both diagonal and square substructures, and only the question prompt guides the model to extract the correct one. If the transformer fails to distinguish the prompt accurately, it may extract the wrong substructure. For instance, in the Topo1 format, the topological descriptions of diagonals and squares are similar, which can lead to confusion in prompts understanding. We will clarify this in the revision.\n\n[1] Wang H, Feng S, He T, et al. Can language models solve graph problems in natural language?[J]. Advances in Neural Information Processing Systems, 2023, 36: 30840-30861.\n\n[2] Tang J, Zhang Q, Li Y, et al. GraphArena: Evaluating and Exploring Large Language Models on Graph Computation[C]//The Thirteenth International Conference on Learning Representations.\n\n[3] Dai X, Qu H, Shen Y, et al. How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension[C]//The Thirteenth International Conference on Learning Representations.\n\n[4] Saparov A, Pawar S A, Pimpalgaonkar S, et al. Transformers Struggle to Learn to Search[C]//The Thirteenth International Conference on Learning Representations.\n\n[5] Wang S, Shen Y, Feng S, et al. Alpine: Unveiling the planning capability of autoregressive learning in language models[J]. Advances in neural information processing systems, 2024, 37: 119662-119688.\n\n[6] Chen Z, Chen L, Villar S, et al. Can graph neural networks count substructures?[J]. Advances in neural information processing systems, 2020, 33: 10383-10395.\n\n[7] Zhu W, Wen T, Song G, et al. On structural expressive power of graph transformers[C]//Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023: 3628-3637.\n\n[8] Müller L, Kusuma D, Bonet B, et al. Towards principled graph transformers[J]. Advances in Neural Information Processing Systems, 2024, 37: 126767-126801."}, {"review_id": "I3xi5byV8e", "reviewer": "Reviewer_XYAX", "summary": "This paper investigates the internal mechanisms by which serialized Transformer models understand graph structures, focusing on how they extract substructures from textual descriptions. It finds that the model progressively integrates node information through layer-wise Induced Substructure Filtering (ISF), where the input format (e.g., adjacency lists outperforming edge lists) and prompt design significantly impact performance. The study further proposes the Substructure Thinking (Tins) framework and validates its generalizability on attributed graphs such as molecular graphs.", "questions": "see in weakness", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1、The paper explores how decoder-only Transformers process graph-structured data through sequential input, which is a relevant and underexplored topic.\n\n2、The ISF framework provides a structured way to describe substructure extraction, and the theoretical results are generally sound and clearly stated.\n\nWeaknesses:\n\n1、Line 90:\nThere is a spelling error—\"Definations\" should be corrected to \"Definitions\"; similarly, the word \"Diagnoal\" is misspelled in several tables.\n\n2、Figure 2:\nThe legend items such as \"0431\" or \"2431\" are unclear—what these IDs represent should be clarified for better interpretability.\n\n3、Lines 243–257:\nThe paper claims that AL and EL representations are theoretically equivalent, yet EL performs significantly worse in experiments. Moreover, although EL uses more tokens and might carry richer structural information, it does not show better performance—even with deeper models, EL only matches AL's results.\n\n4、Assumption 3.4 requires substructures to be unique in the graph, but the Multi-Num task explicitly involves multiple substructures—this inconsistency needs to be clarified.", "was_revised": true, "final_justification": "My concerns have been largely addressed.  I would like to maintain acceptance for this paper after considering both the response and the reviews from other reviewers.", "rebuttal": "Overall response: Thank you for your suggestions. We would like to clarify your key concerns below.\n\n- W: spelling error.\n\nA: Thanks for your careful reading and feedback. We will address these points in the final version.\n\n- W: legend items\n\nA: The legend items represent the IDs of the extracted substructures. We conduct experiments in the directed graph setting to reduce randomness in token generation. As a result, when the model outputs a substructure, it follows a consistent central ordering of node IDs. For example, \"0431\" indicates that the model first identifies node 0 (with out-degree 2), followed by its neighbor 4 (out-degree 1), then node 3 (a neighbor of 4), and finally node 1 (a neighbor of both 3 and 0). Similarly, in the \"2431\" case, the node with out-degree 2 is node 2, serving as the structural starting point. We will address these points in the final version.\n\n- W: EL Vs. AL\n\nA: EL performs worse than AL when trained for the same number of epochs, but it eventually reaches comparable performance. In our results, we selected the epoch at which AL achieves its best performance. However, we will also provide additional information indicating when EL catches up with AL, as shown in the table below:\n\n|          | Epoch |        10000 |          20000 |        30000 |          40000 |         50000 |        60000 |\n|----------|-------|-------------:|---------------:|-------------:|---------------:|--------------:|-------------:|\n| Square (4 layers)   | AL    | 0.97 ± 0.004 | 0.98  ±  0.003 | -            | -              | -             | -            |\n|          | EL    | 0.83 ± 0.078 | 0.93  ± 0.050  | 0.99 ± 0.006 | -              | -             | -            |\n| Pentagon (5 layers) | AL    | 0.69 ± 0.017 | 0.73  ±  0.058 | 0.84 ± 0.031 | 0.92  ±  0.004 | -             | -            |\n|          | EL    | 0.61 ± 0.017 | 0.60  ± 0.019  | 0.74 ± 0.018 | 0.87  ± 0.010  | 0.89 ± 0.0056 | 0.93 ± 0.044 |\n\nEL with longer input lengths requires more training epochs to achieve the same performance as AL. Although EL and AL are theoretically equivalent in their ability to represent graph structures, the longer input sequences in EL lead to less efficient learning. We will clarify this point in the revision.\n\n- W: inconsistency of Assumption 3.4.\n\nA: The unique case is used as a special setting in Section 3.1.2, referred to as the Single-Num-Single-Shape case. This assumption is not used in the subsequent sections. Assumption 3.4 applies specifically to the scenario in Section 3.1.2, where each graph contains only one target substructure, and the Transformer is trained to extract that particular substructure. We then extend our analysis to more complex settings involving multiple substructures. In the Multi-Num-Single-Shape case, the graph contains multiple instances of a specific substructure. In the Single-Num-Multi-Shape case, the graph includes diverse substructures, and a prompt is used to guide the Transformer to extract a specific one. \n\nWe will clearify the definations of these three tasks in the revision as:\n\nSingle-Num-Single-Shape Task:\n\nThe input is directed graphs G=(V,E) (|V|=n) and G'=(V',E') (|V'|=k), where there exists a unique copy of G' in G. The Transformer is required to find the unique copy of G' in G for the input G,G'.\n\nMulti-Num-Single-Shape Task:\n\nThe input is directed graphs G=(V,E) (|V|=n) and G'=(V',E') (|V'|=k), where there might exist multiple copies of G' in G. The Transformer is required to find all copies of G' in G for the input G,G'.\n\nSingle-Task-Multi-Shape Task:\nThe input is directed graphs G=(V,E) (|V|=n) and G'=(V',E') (|V'|$\\leq$ k), where there exists a unique copy of G' in G. The Transformer is required to find the unique copy of G' in G for the input G,G'."}, {"review_id": "qVeOWIolai", "reviewer": "Reviewer_ZFQo", "summary": "This paper explores the mechanisms by which decoder-only Transformers, including large language models (LLMs), perform substructure extraction and reasoning on graph-structured data represented as text. The authors introduce the novel concept of Induced Substructure Filtration (ISF) to interpret how Transformers progressively identify graph substructures. The work includes both theoretical modeling and empirical studies and is extended to consider composite and attributed graphs via the Thinking-in-Substructure (Tins) approach.", "questions": "1.\tHow does the proposed ISF framework compare empirically with existing graph reasoning models, such as GNNs or Transformer variants like Graphormer, on standard graph benchmarks?\n2.\tTo what extent are the results sensitive to the format and structure of the input prompts?\n3.\tHow scalable is the proposed method (ISF and Tins) when applied to large graphs with high substructure complexity in real-world settings?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength**\n\n1.\tThis paper proposes the concept of ISF, providing a mathematically grounded explanation for how Transformers identify sub-structures layer by layer, with a solid theoretical foundation.\n2.\tExtensive experiments conducted on a variety of synthetic datasets demonstrate the effectiveness of the method.\n3.\tThe paper delves into the relationship between Transformers trained from scratch and LLMs fine-tuned with instructions.\n\n**Weakness**\n\n1.\tThe paper does not include comparisons with existing GNNs or graph-aware Transformer architectures on the substructure extraction task.\n2.\tThe experiments mainly focus on synthetic datasets and small molecular graphs. It is unclear how well the proposed methods generalize to real-world graphs with larger size and noise.\n3.\tThe applicability of the ISF framework to Transformer variants with different architectures or to other domains is not fully discussed.", "was_revised": false, "final_justification": "", "rebuttal": "Overall response: Thank you for your suggestions. We would like to clarify your key concerns below\n\n- W: decoder-only transformers Vs. GNNS and graph transformers\n\nA: We respectively point out potential misunderstandings in your comments regarding the motivation and the goal of our paper. We want to clarify them below: \n\nRecent studies have empirically shown that LLMs possess strong capabilities in graph reasoning tasks [1, 2, 3]. At the same time, it is important to understand the underlying mechanisms behind this graph reasoning ability with the textual data [4, 5]. We focus on the substructure extraction task, motivated by prior work [2, 3] showing that LLMs can identify and extract specific substructures from a given graph.\n\nTo bridge the gap, the goal of our paper is to provide **insights into why LLMs can extract substructures from text descriptions of graphs**. As clearly stated in the abstract **How can a decoder-only Transformer architecture understand underlying graph structures?**. We do not aim to argue using transformers to replace GNNs or graph transformers, nor do we propose new algorithms to solve graph tasks.\n\nTo this end, we train **decoder-only** transformers using a **text-based input** format, following the GPT-2 training pipeline, to explore the mechanisms underlying their graph reasoning abilities. Therefore, connecting and comparing with graph-specific encode models such as GNNs and graph transformers are completely beyond the scope of this work. \n\nAlthough it is off topic of our paper, we'd like to introduce the differences between decoder-only transformer and encoder based GNN, and Graph Transformers which have been discussed in the existing papers [5, 6, 7]. GNNs and graph transformers in substructure extractions are models for graph encoding, and the output only limited in the substructure counting, instead of in indefinite length of textual description of substructure. Therefore, the mechanism is totally different as summarized in the Table:\n\n|                                | **GNNs**                                                                                    | **Graph Transformer**                                                      | **Decoder-Only Transformer (LLMs)**                         |\n| ------------------------------ | ------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------- | ----------------------------------------------------------- |\n| **Input**                      | Discrete graph data (node features, adjacency matrix)                                       | Discrete graph data (node features, adjacency matrix)                      | Textual description of a graph                              |\n| **Output**                     | Scalar value (e.g., count) or fixed-size vector (e.g., for classification)                  | Scalar value (e.g., count) or fixed-size vector (e.g., for classification) | Text tokens forming a human-readable structural description in indefinite length|\n| **Learning Formulation**       | Encode graph via message passing and neighborhood aggregation; supervised on scalar outputs | Encode graph via graph-aware self-attention; supervised on scalar outputs  | Next-token prediction over graph-structured text            |\n| **Mechanism** | 1-WL [5]                                                                                       | k-WL [6]/ SEG-WL [7]                                                              | ISF (Ours)                                                        |\n\n- W: It is unclear how well the proposed methods (ISF and Tins) generalize to real-world graphs with larger size and noise.\n\nA: As claried in the previous question, the focus of this work is \"How can a decoder-only Transformer architecture understand underlying graph structures?\" Therefore, our work does not propose new methods for solving graph tasks. Instead, we focus on providing both theoretical and empirical foundations for why decoder-only transformers can understand structural information from textual graph descriptions. We summarize the underlying mechanisms and refer to them as ISF and Tins.\n\nWe follow the data and settings used in prior work [4, 5], which showed that simplified datasets can capture key properties of decoder-only transformers, which are also reflected in the performance of LLMs. Based on this, we use simplified textual graph data to design experiments that explore how decoder-only transformers understand substructures. The findings from these foundational experiments also support and help explain the behaviors observed in LLMs, as discussed in Section 4. \n\nMeanwhile, we use molecular graphs as a special case of attributed graphs to demonstrate the theoretical foundations in real-world applications, where LLMs are capable of reasoning over attributed graphs [2, 3, 7, 10].\n\n- Q: sensitive to the format\n\nA: Thank you for your great question. This is exactly one of the key goals of our paper. Prior work has shown that LLMs are sensitive to the formulation of input structure prompts, and different formats can lead to varying performance [3, 9]. In our paper, we explain this phenomenon by comparing the EL and AL formulations. While both formats are valid for graph tasks, they differ in input length, which is an important factor, as LLMs are sensitive to sequence length and effect performance.\n\n[1] Wang H, Feng S, He T, et al. Can language models solve graph problems in natural language?[J]. Advances in Neural Information Processing Systems, 2023, 36: 30840-30861.\n\n[2] Tang J, Zhang Q, Li Y, et al. GraphArena: Evaluating and Exploring Large Language Models on Graph Computation[C]//The Thirteenth International Conference on Learning Representations.\n\n[3] Dai X, Qu H, Shen Y, et al. How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension[C]//The Thirteenth International Conference on Learning Representations.\n\n[4] Saparov A, Pawar S A, Pimpalgaonkar S, et al. Transformers Struggle to Learn to Search[C]//The Thirteenth International Conference on Learning Representations.\n\n[5] Wang S, Shen Y, Feng S, et al. Alpine: Unveiling the planning capability of autoregressive learning in language models[J]. Advances in neural information processing systems, 2024, 37: 119662-119688.\n\n[6] Chen Z, Chen L, Villar S, et al. Can graph neural networks count substructures?[J]. Advances in neural information processing systems, 2020, 33: 10383-10395.\n\n[7] Zhu W, Wen T, Song G, et al. On structural expressive power of graph transformers[C]//Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023: 3628-3637.\n\n[8] Müller L, Kusuma D, Bonet B, et al. Towards principled graph transformers[J]. Advances in Neural Information Processing Systems, 2024, 37: 126767-126801.\n\n[9] Fatemi B, Halcrow J, Perozzi B. Talk like a Graph: Encoding Graphs for Large Language Models[C]//The Twelfth International Conference on Learning Representations.\n\n[10] Zhang Y, Wang H, Feng S, et al. Can LLM Graph Reasoning Generalize beyond Pattern Memorization?[C]//Findings of the Association for Computational Linguistics: EMNLP 2024. 2024: 2289-2305."}, {"review_id": "zA6Hqxn7fe", "reviewer": "Reviewer_J4XB", "summary": "This work explores how substructure reasoning is enabled in Transformers when graph-structured inputs are presented as sequences, which has been a common approach for leveraging recent LLMs for graphs (text-attributed graphs mainly, but this paper presents a general case). It introduces Induced Substructure Filtration (ISF), a theoretical framework explaining how Transformers progressively identify substructures through layer-wise node aggregation. They provide formal theorems, empirical validation on both small trained models and LLMs (Llama), and extend the approach to complex multiple patterns and molecular graphs using a 'thinking in substructures' method. Overall, the paper aims to uncover some of the capabilities of LLMs to understand graph structures when the corresponding input is sequential and the presented insights seem useful, although understood in literature through the fact that (i) Transformers can be instantiated as a case of GNNs, and (ii) encode-process-decode networks are used in graph reasoning domains (e.g., neural algorithmic reasoning) to model progressive node aggregation.", "questions": "How does a Transformer trained with a substructure counting-heavy approach/dataset affect downstream performance in real-world tasks that take textified graphs as input?", "limitations": "NA", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The proposed ISF gives an understanding of how Transformers or sequence models process graph structure.\n- Empirical results are interesting and shows the challenges of large scale multi-resolution understanding in graph structures.\n- The paper overall has neat visualization and interpretability of the messages.\n- Insights such as the use of AL vs. EL in the text,graph prompt design is a useful message and is clearly demonstrated both conceptually and empirically.\n\nWeaknesses:\n- I believe one of the central messages of the paper on progressive node aggregation in Transformers is well known. Transformers are considered special cases of GNNs, which implies the understanding that a node must have at least m GNN operation layers to incorporate information from an m-hop receptive field. This is close to the result that Transformers progressively identify substructures through layer-wise node aggregation. In addition, the encode-process-decode framework in [1] suggests the GNN core be iterated for M times to have the GNN form progressive embeddings required for graph reasoning. This is used in neural algorithmic reasoning works, e.g., [2]. Therefore, the overall advances from this paper, apart from the methods and results in sections 5.1 and 5.2, may be limited, since the question of how ISF would apply to other structured reasoning tasks beyond substructure extraction (such as problem solving in maths, logic, etc.) remains open.\n- minor typo on line 81 in page 3: there may be an 'convert' or similar word missing here \"To input graphs into a Transformers, ...\" \n\n[1] Battaglia, P.W., Hamrick, J.B., Bapst, V., Sanchez-Gonzalez, A., Zambaldi, V., Malinowski, M., Tacchetti, A., Raposo, D., Santoro, A., Faulkner, R. and Gulcehre, C., 2018. Relational inductive biases, deep learning, and graph networks.\n[2] Veličković, P. and Blundell, C., 2021. Neural algorithmic reasoning.", "was_revised": true, "final_justification": "The rebuttal demonstrated how their approach contributes to addressing the main question posed in the paper, a point I initially had concerns about due to closer prior works which investigates links between GNNs/Transformers, particularly regarding how such methods, despite not explicitly using graph structure, can still capture and understand the underlying graph.", "rebuttal": "Overall: Thanks for your suggestions. We would like to clarify your key concerns below. \n\nWe respectively point out potential misunderstandings in your comments regarding the motivation and the goal of our paper. We want to clarify them below: \n\nRecent studies have shown that LLMs possess strong capabilities in graph reasoning tasks [3, 4, 5]. At the same time, it is important to understand the underlying mechanisms behind this graph reasoning ability with the textual data [6, 7]. We focus on the substructure extraction task, motivated by prior work [4, 5] showing that LLMs can identify and extract specific substructures from a given graph.\n\nTo bridge the gap, the goal of our paper is to provide **insights into why LLMs can extract substructures from text descriptions of graphs**. As clearly stated in the abstract **How can a decoder-only Transformer architecture understand underlying graph structures?**. We do not aim to argue using transformers to replace GNNs or graph transformers, nor do we propose new algorithms to solve graph tasks.\n\nTo this end, we train **decoder-only** transformers using a **text-based input** format, following the GPT-2 training pipeline, to explore the mechanisms underlying their graph reasoning abilities. Therefore, connecting and comparing with graph-specific encode models such as GNNs and graph transformers are completely beyond the scope of this work. \n\n- W: Transformers are considered special cases of GNNs, and the findings are not new.\n\nA: As discussed in the “Overall Response,” our work focuses on understanding why **decoder-only** transformers can capture substructures when trained using next-token prediction. Therefore, a detailed comparison with encoder-based frameworks falls outside the scope of this paper.\n\nAlthough it is off topic of our paper, we'd like to introduce the differences between decoder-only transformer and encoder based GNNs in the Table:\n\n|                  | GNNs                                                                                          | Decoder-Only Transformers (LLMs)                            |\n|--------------------------|-----------------------------------------------------------------------------------------------|-------------------------------------------------------------|\n| Input                    | Discrete graph data (node features, adjacency matrix)                                         | Textual description of a graph                              |\n| Output                   | A scalar value (e.g., count) or fixed-size vector (e.g., for classification)                  | Text tokens forming a human-readable structural description |\n| Learning Formulation     | Encode graph via message passing and neighborhood aggregation, then predict scalar outputs     | Next-token prediction over graph-structured text            |\n| Substructure Mechanism   | 1-WL [8]                                                                                         | ISF                                                         |\n| Information Aggregation  | m-hop                                                                                         | m-filter                                                    |\n\nThe concept of information aggregation in our work, referred to as m-filter, is fundamentally different from the conventional m-hop aggregation in GNNs.\nWhile GNNs aggregate information from m-hop neighbors based on the adjacency matrix toward a central node, decoder-only transformers instead learn to filter relevant information across m tokens in the input sequence, without relying on explicit graph structure.\n\n- W: Comapring with the GNNs that used in reasoning tasks.\n\nA: As mentioned in the \"Overall Response,\" this paper focuses on the question: \"How can a decoder-only transformer understand graph structure?\" Accordingly, our analysis is centered specifically on decoder-only transformers, which align with the architecture of LLMs. To the best of our knowledge, this is the first work to analyze structure understanding in the context of next-token prediction.\n\n[1] proposes graph neural network blocks to encode algorithmic reasoning tasks using edge and node representations in the form of vector lists, but our approach relies solely on textual sequences and trained by next token prediction. [2] presents a blueprint for neural algorithmic reasoning within an encoder-decoder framework, whereas our study targets decoder-only transformers. Therefore, both works are outside the scope of our discussion, which explains how decoder-only transformers trained on textual graph data can learn to understand structural information.\n\nIn Sections 5.1 and 5.2, we continue to follow our central focus on how LLMs can understand graph structures presented in textual descriptions. These sections include more complex graph types, such as composed and attributed graphs. Our motivation for analyzing these graphs stems from prior findings that LLMs are capable of decomposing graphs and understanding attributed graphs such as molecular structures [5]. Thus, exploring neural algorithmic reasoning in real-world applications is beyond the scope of our current discussion.\n\nHowever, we would like to share our view that reasoning tasks often involve substructure understanding, making this an important direction for future research. Given that decoder-only transformers such as GPT-2 have demonstrated strong performance on reasoning tasks (e.g., mathematics and logic), it would be valuable to investigate whether graph reasoning can be framed as a specific instance of general reasoning in LLMs.\n\n- W: minor typo\n\nA: Thanks for your advice, we will change it into \"Following prior work, we represent graph data using either Adjacency Lists (AL) or Edge Lists (EL), and encode them as textual sequences for input into Transformers\" to make it clear.\n\n- Q: transformer trained with a substructure counting-heavy approach.\n\nA: We do not train the transformer to count substructures. Instead, we train a decoder-only transformer using a next-token prediction objective to extract substructure node lists from given graphs. While prior work using GNNs or graph transformers has primarily focused on substructure counting [8], our model is trained to generate complete substructure lists in text form. Previous studies have shown that the graph reasoning ability of decoder-only LLMs can be enhanced through cross-task fine-tuning on graph-related tasks [9, 10]. Building on this, our work provides theoretical foundations for why LLMs can understand structural information, offering a basis for extending their capabilities to a wide range of structure-based tasks.\n\n[1] Battaglia, P.W., Hamrick, J.B., Bapst, V., Sanchez-Gonzalez, A., Zambaldi, V., Malinowski, M., Tacchetti, A., Raposo, D., Santoro, A., Faulkner, R. and Gulcehre, C., 2018. Relational inductive biases, deep learning, and graph networks.\n\n[2] Veličković, P. and Blundell, C., 2021. Neural algorithmic reasoning.\n\n[3] Wang H, Feng S, He T, et al. Can language models solve graph problems in natural language?[J]. Advances in Neural Information Processing Systems, 2023, 36: 30840-30861.\n\n[4] Tang J, Zhang Q, Li Y, et al. GraphArena: Evaluating and Exploring Large Language Models on Graph Computation[C]//The Thirteenth International Conference on Learning Representations.\n\n[5] Dai X, Qu H, Shen Y, et al. How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension[C]//The Thirteenth International Conference on Learning Representations.\n\n[6] Saparov A, Pawar S A, Pimpalgaonkar S, et al. Transformers Struggle to Learn to Search[C]//The Thirteenth International Conference on Learning Representations.\n\n[7] Wang S, Shen Y, Feng S, et al. Alpine: Unveiling the planning capability of autoregressive learning in language models[J]. Advances in neural information processing systems, 2024, 37: 119662-119688.\n\n[8] Chen Z, Chen L, Villar S, et al. Can graph neural networks count substructures?[J]. Advances in neural information processing systems, 2020, 33: 10383-10395.\n\n[9] Zhang Q, Chen N, Li Z, et al. Improving LLMs' Generalized Reasoning Abilities by Graph Problems[J]. arXiv preprint arXiv:2507.17168, 2025.\n\n[10] Zhang Y, Wang H, Feng S, et al. Can LLM Graph Reasoning Generalize beyond Pattern Memorization?[C]//Findings of the Association for Computational Linguistics: EMNLP 2024. 2024: 2289-2305."}]

Author rebuttal:

Meta-review: The paper studies a fundamental question: How can a decoder-only Transformer architecture understand graph structures? The authors first investigate the underlying mechanism inside transformers with the substructure extraction task. Specifically, the authors formulate Induced Substructure Filtration (ISF), and validate it in LLMs. The authors further explore the capabilities of Transformers in handling diverse graph types, including attributed graphs such as molecular graphs.  

Strengths:
- The paper investigates an interesting and important question. 
- The ISF provides a mathematical framework for the understanding of Transformers in identifying substructures.
- The paper has a good balance of both theoretical and empirical results.

Weaknesses:
- Experiments are mostly on simplified synthetic toy data or small molecular graphs, raising questions if the results of the paper can be extended to larger graphs. 
- Lacking discussions on how decoder-only transfers differ from existing GNNs or graph Transformers on the substructure extraction task.
- The results in the paper based on decoder only transformers pre-trained from scratch are disconnected with the big question: why LLMs can extract substructures from text descriptions of graphs? 

Overall, the paper has academic significance in providing a new perspective on the capabilities of LLMs in extracting graph structures. While the execution relied on simplified settings/models, I do not view these as fundamental issues and they still provide useful insights to advance the field. In my opinion, the merits outweigh the shortcomings.
Decision: Accept (poster)