Microstructures and Accuracy of Graph Recall by Large Language Models
Authors: Yanbang Wang
Hejie Cui
Jon Kleinberg
Venue: NeurIPS 2024 poster (2024)
Keywords: large language models
graph recall
human cognition
sociology
network motif
Primary area: machine_learning_for_social_sciences
TL;DR: We perform the first systematical study of graph recall by LLMs, investigating the accuracy and biased microstructures (local subgraph patterns) in the recalled graphs.

Abstract: Graphs data is crucial for many applications, and much of it exists in the relations described in textual format. As a result, being able to accurately recall and encode a graph described in earlier text is a basic yet pivotal ability that LLMs need to demonstrate if they are to perform reasoning tasks that involve graph-structured information. Human performance at graph recall by has been studied by cognitive scientists for decades, and has been found to often exhibit certain structural patterns of bias that align with human handling of social relationships. To date, however, we know little about how LLMs behave in analogous graph recall tasks: do their recalled graphs also exhibit certain biased patterns, and if so, how do they compare with humans and affect other graph reasoning tasks? In this work, we perform the first systematical study of graph recall by LLMs, investigating the accuracy and biased microstructures (local structural patterns) in their recall. We find that LLMs not only underperform often in graph recall, but also tend to favor more triangles and alternating 2-paths. Moreover, we find that more advanced LLMs have a striking dependence on the domain that a real-world graph comes from --- by yielding the best recall accuracy when the graph is narrated in a language style consistent with its original domain.

Microstructures and Accuracy of Graph Recall by Large Language Models
Yanbang Wang Cornell University ywangdr co.eellll
Hejie Cui Stanford University hejie.cuié cui sta
Jon Kleinberg Coreell University kleinberg edn
Abstract
Graphs data crucial for many applications, and much of it exists in the relations described in textual format. As a result, being able accurately recall and encode graph described earlier text is basic yet pivotal ability that large language models (LLMs) need to demonstrate if they are to perform reasoning tasks that involve graph-structured information. Human performance at graph recall by has been studied by cognitive scientists for decades, and has been found to often exhibit certain structural patterns of bias that align with human handling social rela- tionships. To date, however, know little about how LLMs behave in analogous graph recall tasks: do their recalled graphs also exhibit certain biased patterns, and if so, how do they compare with humans and affect other graph reasoning tasks? In this work, we perform the first systematical study of graph recall by LLMs, investigating the accuracy and biased microstructures (local subgraph patterns) in their recall. We find that LLMs not only underperform often in graph recall, but also tend to favor more triangles and alternating 2-paths. Moreover, more advanced LLMs have striking dependence on the domain that a real-world graph comes from - by yielding the best recall accuracy when the graph is narrated in a language style consistent with its original domain.
find that
Introduction
Large language models (LLMs) achieve remarkable progress in recent years. In many applications, LLMs' success relies on appropriate handing of graph-structured information embedded in text. For example, accurately answer questions pertaining to the characters LLM to be able to recognize and analyze the social network of relations among these characters. In fact, graph-structure as structured commonsense reasoning (2), multi-agent communications R multi-hop question answering 15), and more. L.MMs' graph reasoning ability has thus become an active research topic.
story, it is crucial for an
information is ubiquitous across many language-bet based applications, such
Existing works on LLMs' graph reasoning ability have been primarily posited in the context of various graph tasks, from most basic ones such as computing node degree, graph diameter, clustering coefficient, or checking cycles [88 20 [8] to more challenging ones such as node/graph classification
14 38
and link-based recommendations [55] Sec. 7 provides more comprehensive survey.
But all of the tasks above rely on the premise that an LLM is able to start from the graph that is described in the text it is given. Thus, our key starting observation here is that all of these tasks rely on a pivotal (and perhaps seemingly trivial) ability of L.MMs - to recall and encode a set of relations described in earlier text. In this paper, we consider graph recall task which has been extensively studied in cognitive science g
9 41, and which formalizes this basic goal, illustrated in Figure M set of pairwise relationships is described in simple narrative form the experimental subject (human or LLM); then at a later point in the experiment, the subject is asked to recall and describe these relationships explicitly in the form of graph.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

The rationale for studying an LLM's graph recall is simple. If an LLM cannot even accurately recall the graph it is asked to reason upon, it will not be able to do well in any of the more advanced graph tasks surveyed above. Further, structural patterns in recall emrors may propagate to (or even serve as the basis for) the behavior of L.LMs in these more complex graph tasks. Therefore, we consider important to investigate L.MMs graph recall ability, topic absent from existing literature. The edge prediction task is related to but fundamentally different from the graph recall task: the correct answer for graph recall always exists in the prompt and can be directly extracted, which is not true for any prediction tasks.
Meanwhile, the existing two decades of studies on human's graph recall ability provide another fascinating perspective to motivate our study. Cognitive scientists have found through substan- tial human experiments that, when memorizing a social network, humans extensively employ certain compression heuristics, such triadic closure, near-clique completion, and certain de- gree biases [ 355, due to natural limits cog- nitive capacity. Further studies show that a per- son's 's ability accurately recall social network, along with the microstructures (local subgraph patterns, or network motifs 2 (44) in their re-
Graph Recall
User: We will now conduct an experiment on your ability to memoriie relational structures text
LLM: understand the task...
User: paragraph deseribing graph) Bogdan Gabrys and Lakhmsi Jain coauthored paper in 2006, Bogdan Gabrys and Honghai Liu coauthored paper in 2007. Lakhmi C. Join and Rajiv Khosla ...
Before we proceed (more inrefevant tasks and interactions]. ...
recall, we will perform an excreise
please recall structure the graph you saw LLM: (Begdlnn Gabeys, Lakhmi Jain): (Bogdan Gabrys, Rogden Gabrys): .....
[Retrieved edge probabilities: (Ronald Hartung, Lakhmi Jain) (Bogdan Gabrys, Bogdlmn Gabrysst ...]
called network, not only has profound influence on their social decisions [25
52 but also
Presence of Variows Microstructures
/e I
varies on different styles of graph narrative 44
Edge
Triangle
Star
and the sex of the person [2]] Do LLMs use similar compression heuristics as humans, and how are they affected by different working con- texts? As LLMs become increasingly integrated into various social applications, it becomes cru- cial to understand LLM's behaviors and their associations with human behaviors in these re- gards.
Truth Graph
Recall Graph
Performance Aes,
Downstream Tacks
Link Prediction
Graph
Nede/Graph
Summary
Classifscation
Figure I: Graph recall is a simple task but also a erucial pivot for other graph reasoning tasks.
The human cognition studies not only motivate our study, but also establish scientific foundation for our experimental designs. Similar to [4] which uses political orientation tests designed for humans assess LLM's political bias, we also find some of the protocols employed by (8) for testing human's graph recall highly instructional, including: (I) memory clearance, where a classical word span test
is conducted between the presentation of the graph content and the query prompt; this serves as a chat buffer that helps simulate the delayed queries in many real-world applications; (2) analyzing biased patterns in graph recall via Exponential Random Graph Model (ERGM), a probabílistic generalization to the network motif' methods in graph mining; (3) focusing on the probability of the tokens in subject's 's response, rather than just their presence; we replicate this through the log_prob parameter in GPT series or conducting Monto Carlo sampling for Gemini. We will elaborate on these in the following sections.
Our Work In this work, we investigate the several primary questions regarding the capabilities of LLMs in recalling graph structures. First, we examine the accuracy and microstructures in graphs recalled by LLMs through experiments on real-world graph structures, as well as compare these results with human performance. Second, we explore factors affecting LLMs' graph recall abilities, focusing on memory clearance strength, and narrative styles of graph encoding, which are known to affect human's graph recall, Finally, we also consider how LLMs' graph recall influences their performance in downstream tasks like link prediction, and discuss actionable insights that our findings provide for future research. To summarize, our work makes the following contributions:
1. We propose graph recall as a simple yet fundamental task for understanding LLM's s graph reasoning abilities, drawing its connection with the existing cognitive studies on human's 's graph recall ability.
2. We are the first to design and conduct systematical studies on the accuracy and biased microstruc- tures of LLM's graph recall, and to compare the results with humans.
3. We present many important and interesting findings on LLM's behaviors in graph recall, which significantly helps deepen understandings about LLM's graph reasoning ability.

---

2 Preliminaries
2.1 Exponential Random Graph Model (ERGM)
We use the Exponential Random Graph Model (ERGM) 39 characterize the statistical significance of the various microstructural patterns ("network motifs" 34 in the recalled graphs. ERGM is a special case of the exponential family dedicated for modeling graph-structure Formally, let G be the probability space of all possible graphs over n nodes, and G = E. E g be a random (graph) variable, where V the set of nodes, E is the set of edges G. and f E + [0. 1] is a edge probability function. Assuming independence between edges, the probability of G can be written as:
data.
P(G) II f(e) eEE
II egE
A is list of k predefined microstructural patterns in G. 2s s Step 6 shows k 5 such patterns that we primarily investigate in this work, following []. The conditional probability of observing G given the parameter vector 0 of length k is defined to be
P(G exp 8,8 (,s;
exp s())
(2)
C9
Ce
where s (() is the sufficient statistics of G, and each s; (G) is a count of the number of occurrences of A[i] in G; is the normalizing constant that only depends on 0. We assume an uninformative prior for ~ [-10, 10). The posterior P(O G) can then be optimized via MAP under Bayesian framework. 0 measures the strength of presence of the k microstructural patterns we care about. A large A means a strong presence of pattern Ali] in G.
2.2 Memory Clearance
The word span test [17] is a standard method for measuring a human's 's working memory capacity, The test requires the subject to read a series of sentence sets out loud, and then recall the last word in each previous sentence in the current set. The number of sentences in each set gradually increases from two to seven, i.e. from three sets of two sentences to three sets of seven sentences. The test continues until the subject fails to recall the final words for two out of three sets of given size. See Appendix B.2.1 for the sentence sets we used.
Many cognition studies 88 77 6 5) have adopted this test in their experiment to (1) serve as a chat buffer spoiler that simulates the delayed query in real-world applications, and (2) clear the short- term memory of the subject, which allows researchers to better focus on relatively persistent patterns in memory structures.
important to note that transformer-basee LLMs are stateless models that, in strict sense, do not have memory. Nevertheless, we choose to preserve the (slightly misleading) term "memory clearance"' to stay aligned with literature and emphasize the close analogy and behavioral resemblance between LLMs and humans in graph recall.
3 Mierostructures and Accuracy of Graph Recall by LLMs
Being able to correctly recall a graph described in earlier text is a fundamental ability for LLMs to perform graph reasoning. While graph recall may seem an easy task for the high-capable LLMs nowadays, our extensive experiment shows that their performance is in fact far from perfect.
This section presents our study on the performance and the microstructures of graph recall by LLMs. Our experimental protocols are introduced in Sec followed by Sec which presents head-to- head comparisons of LLMs and humans under [8] framework. Sec(3.2 substantiates the analysis by experiments on more diverse datasets. Our code and data are reported Appendix A
LLMs Tested: GPT-3.5 [00). GPT-4 M. Gemini-Pro [66.. We also examined Llama 2 (13B) (7]
but they can rarely follow through on our instructions.
3.1 Experimental Protocols and Datasets
Our staged protocols are visualized in Fig and explained below. To recall each graph sample, an LLM needs to separately go through the entire pipeline. The stages proceed in an auto-regressive manner. In other words, the L.MM's intermediate response is always appended to the current thread as additional conservation context, before we proceed to the next stage along the pipeline.
3

---

Task Introduction
Presenting Graph Vignette
Memory Clearance
Prompting
User: We will now conduct on relational structures
User Bogdan Gabrys and Labdhnt C. comunhored paper 2006 Bagdan Gabrys Honghai escachared a paper in 2007. Lakfuol C. Jadn and Rufiv Xhosia
User: Before preceed, we will perfors
User: Now please recall the the grugh you hegiining, every pair of sades - -formatting Instructionss
ability recall
with you be gives sories sentences, v. you will need to recall the last ward in each precealigg ser... Assistant:...
be grven rig nettee which a paragroph descriiing graph awong multipis entities... Assistarat....
Ex
Assiatant: eLLM's graph recall-
Assistant:
Microstructure & Performance Analysis
Retrieving Edge Probabilities
ERGM
eLLM's graphs recull-- (llgdan calyy, Lattenl
optin 1pr0
784 Lomping
(lather Max Honghat
Mirradmrattree:: D8s 2.43 29, - -197
2.32
aB, -1.00
Greph
Grophe
Nerfermance:
Figure 2:
Experimental protocols for analyzing microstructures and accuracy of LLM's graph recall. See Sec T for detailed explanations.
Step 1:
Task Introduction. The LLM is informed that this is a graph recall test, and that the recall task may happen at a later time. It is also incentivized to yield its best performance. These components follow the ones used in g for human studies.
Step 2: Presenting Graph Vignette. A vignette in sociology is a short, descriptive story that encodes the central piece of information for soliciting subject's 's response. Here, our vignette encodes the graph structures sampled from certain application domain using certain narrative style see the dataset tab below for details.
Step Memory Clearance. standard word span test is conducted with the LLM. See See 2.2 for details. We use the same set of sentences in (8).
Step 4: Prompting, We use zero-shot prompting with moderate formatting instructions for answers. This follows both [8's protocol and the finding in [18 that simple prompts are the best for simple tasks, which we also empirically observed.
Step 5: Retrieving Edge Probabilities. We are interested in both the existence and the probability of each edge (i.e. the f in ERGM) in graphs recalled by LLM the latter lets us examine LLM's behavior at finer granularities. We use two tricks to retrieve edge probabilities from LLM's 's answers:
For GPT series, we can directly access token probabilities through the ChatCompletion API. We instruct the model to output 1 for each edge it believes to exist, and 0 otherwise. Then, we retrieve and normalize the probabilities for tokens and 1, using the latter as the edge probability.
For Gemini-Pro whose token probabilities are not accessible via the API, we conduct Monte Carlo sampling for each potential edge (repeating the query for 100 times), and use the fraction of existence as the edge probability.
Note that the retrieved edge probabilities essentially constitute a probability graph.
Step 6: Microstructure Analysis & Performance Measurement. We use the ERGM introduced in Sec. 2. to model both the recalled graph and the ground truth, in order to reveal statistically significant structural patterns, "microstructures as termed by (8), in the recalled graphs. Specifically, for each microstructural pattern, we compute the gap between its estimated coefficient on the recalled graph against its estimated coefficient the ground-truth graph. Steps 1 6 are repeated for 100 different graphs uniformly sampled from the same domain to compute confidence intervals.
Datasets. We create five graph datasets from the following application domains. (1) Co-authorship:
DBLP (1995-2005); (2) Social network: Facebook (27]: (3) Geological network: CA road; (4) Protein interactions: Reactome [16]; (5) Erdös-Rényi graph: as [18]. Each dataset comprises of 100 graphs and their corresponding textual descriptions in the domain's narrative language, which generated from templates that are intentionally kept simple: Fig.2's Step 2 shows an example for the DBLP dataset. More examples and details provided in Appendix [
Graphs in the first four datasets are uniformly sampled as ego-network, with the central node removed so that no graph isomorphism gets excluded by the sampling scheme. Each graph has to 30 nodes. The Erdös Erdōs-Rényi graph generated by uniformly sampling p value from [0. 1]. Also note that because the templates used are simple and fixed, we can easily create baselines by reverse-engineering the template achieve perfect accuracy in graph recall.

---

Table Microstructural patterns and performance of graph recall by LLMs on graphs sampled from various application domains; mean + Clas% reported. The numbers reported for microstructural patterns are signficance parameters computed by the ERGM model introduced in Sec. 2.1 A positive (negative) number means the LLM is biased towards encouraging (depressing) the corresponding microstructural pattern in recalled graphs. The patterns are visualized in Fig Step 6. Full table available in Appendix
Microstructure
Performance
Model/ / Dataset
Edge
Triungle
Star
Ali- Alt-Triangl
Ali-2-Paih
Accuracy (%)
FI (%)
GPT-3.5
Facebook
1 1.34
40.00
3.00
-0.91 + 2.25
3.31 1.77
71.60 4.07
72.34 3.54
Road
0.64
-3.46
10.92
95.52
2..5222.67
Reactome
-18.01 6.22
-0.71 4.662
+.861
-6.32 4,222
4.993
53.08 4: 3.32
44.47
= 6.19
DBLP
2..2
1,17 4.43
2:44
-11.162:4.35
5.77 3.76
72.47 3.66
65.08
4.73
Erdds-Rényi
=1040
9:57 $..894899
1.40 2.71
-0.41 4.19
3.36 2.76
5 3.32
49.49
GPT-4
Facebook
0.50
0.05 a 0.78
0.06 = 0.21
-0.01 = 0.26
0,01 = 0.06
99.80 0.11
99.75 0.13
CA Road
1.34 1.62
6.07 3.93
-3.09 1,09
-1.27 0,96
0.91
98.11 2.54
98.00
2.74
Reactome
5.8544
0,82
2.69 2.87
-1.99 2.03
40.66
77.04 4.13
76.80
DBLP
-1.26 2.56
-1.41 3,26
-0.69 3,74
1.71 2,96
+
98.70 0.74
97.88
1.65
Erdds-Rényi
-1.49
1.95
0.52 2.79
-1.26
0.76
60.34 2.37
44.03
5.20
Gemini-Pro
Facebook
1
2.99
0.67 +
34,56
CA Road
0.84 1.68
2.02
5.24
0.89 + 0.28
6.82
44.69 3.86
31.92
4.83
Reactome
-11.94 #
1.22
13.47
4.57
4.15
$4.09 2.92
46.59
DBLP
-1947 3.30
-1.72
41.24
11.08 1,90
10.83
46.33 3.54
47.36 4.55
Erdōs Réngs
25.16
1.51
(0.66:3:.95
2.81
4.170
$2.40:4.41
22.27 4.64
3.2 Results and Analysis
Table I shows the results of microstructural patterns and performance of LLMs in our graph recall test. We primarily investigate the five microstructural patterns as shown Fig. 2 This is because these patterns have been observed to be biased patterns in human studies and are substantiated with rich sociological explanations [X] other patterns may also be interesting to examine though, which we leave for future work. A positive/negative value means the LLM is biased towards encouraging/depprssinng the corresponding microstructural pattern recalled graphs. We have the following findings.
LLMs underperform in the graph recall test. We start by examining the performance metrics on the right columns. None of the models are able to perform perfectly on any dataset - in fact not even cases. The unsaturated performance shows that the graph recall test is a meaningful task to investigate. The result also helps partially explain the poor performance of LLMs on many other graph tasks including node degree, edge count, and cycle check 48 20].
close
LLMs may tend to forget, rather than hallucinate edges. The "edge" column shows an interesting result that LLMs generally recall fewer edges than the ground truth. This crucially tells us that LLM's bias in other microstructural patterns may more likely be the consequence of selective forgetting. rather than hallucination.
An LLM's microstructural bias relatively robust. For each model, the colors each column are relatively consistent. This means that LLM may have have some relatively persistent bias in its microstructual patterns, which does not change significantly across different application domains. This is positive indicator of the generalizability of our findings above.
3.3 LLMS Compared with Humans in Graph Recall
Brashears et al. reported experimental results of social network recall on a total of 301 humans (8] Here report how we build upon this existing result compare LLMs' and humans' behaviors in the social network recall test.
To stay aligned with Brashears' settings, networks: an irreducible one which contains no cliques, and reducible one which contains multiple cliques. Appendix B introduces more details. Z the comparison results.
their dataset which consists of two 15-node social
Regarding the types of bias (forgetting vs. hallucination), L.LMs are relatively consistent with humans. Both LLMs and humans tend to forget edges and alt-triangles while "hallucinating"
5

---

triangles and stars. This interesting finding may reveal that LLMs have some information decoding and recall mechanisms similar human memory.
Regarding the strength of the bias, LLMs tend to have weaker forgetting but stronger hallu- cinations than humans. On microstructures such edges and alt-triangles, L.MMs tend to have weaker forgetting pattern, while on some prominently increasing microstructures (e.g., triangles), LLMs tend demonstrate strong hallucinating patterns. These findings suggest that while LLMs may have a distinct advantage than humans in retaining certain graph structures in their memory, they may still struggle with accurately recalling, potentially limiting their ability perform complex or critical graph tasks.
Table 2: LLMs vs. Humans: microstructural patterns and performance of graph recall, conducted on the two social networks used in [8. Numbers on the "humans" row were taken from Brashears' paper and postprocessed by not reported in Brashears' paper.
Microstructure
Performance
Model
Edge
Triangle
Star
Alt-Triangle
All-2-Panh
Accuracy (%)
"Irreducible"
social network
Humans
-3.194-5.97
9,52+-123
2.31+00.11
-3.39+-1.22
-1.71+-3.32
29.72
GPT-3.5
-2.234-2.79
5.40s-0.51
4.694-2.09
-1.744-087
-1,264-1.399
31.51
GPT-4
-5.364-1.59
11.404-3.07
3,40+-145
-2.05+-1.22
-0.96+-0.48
95.71
Gemini-Pro
9.824-0.28 t
7.63+-0.45
-0,46+-11111
-2884-0.98
-0.474-0.99
24.99
"Reducible"
social network
Humums
-9414-2.21
1,714-0.51
-1.67+-0.03
4.34+-1.72
17.80
GPT-3.5
-5.644-1.56
-0.13+-5.71
-2.52+-16.43
4.794-14.96
1.91+-2.97
51.11
GPT:4
-2.82-22551
-1.10--086
-1.70-0097
-0.934-0.64
0.47+-0.27
95.74
Gemini-Pro
-3.254-2.09
10.9243.52
f
-1.994-8.35
-0.44:-4.7
0.034-0.39
38.82
4 What Affects LLM's Graph Recall?
It is natural question to ask about factors that can affect an LLM's performance in the graph recall task. Many existing works have investigated graph properties and prompting methods as two key variants affecting LLM's s performance in graph reasoning tasks [48] [4]. Here focus several interesting factors that are less explored but still play a crucial role in graph recall: narrative style, strength of memory clearance, and sex priming (Appendix D).
4.1 Narrative Style
The effect of narrative styles several graph reasoning abilities has been studied by 18 with synthetic random graphs. Here we will present an interesting finding on real-world graphs, and by novelly cross-evaluating narrative styles and real-world domains.
Motivation.
The key idea the following: it is known that graphs sampled from different domains have different distributions of topology, c.g. road networks are usually star-shaped, whereas social networks usually have more triangles 45 Meanwhile, each domain has its own style of narration: for describing road networks geographical locations and names are often used, while for describing social networks names and personal relationships are used more often. Our experiment thus far has always used for each dataset the matched narrative with its domain. Therefore, an interesting question is whether LLM would perform best in graph recall only if the narrative style of the graphs matches the domain.
To this end, we conduct cross-evaluation over the five different application domains and their corresponding narrative styles as introduced in Sec More concretely, for graphs from each domain, we describe it in five different ways, corresponding to the five different domains. The resulting performance is visualized as heatmaps in Fig (a) (c). Appendix provides the full table.
Result Analysis. The heatmaps of GPT-4 and GPT-3.5 support our conjecture: the diagonals (corresponding matching between narrative style and the domain of the data) tend to have higher performance. Such an effect seems to be more prominent with better perterrperfomming models.
We find this result striking, that the LLM should do better when the graph is described in the narrative language of the domain that it comes from. While an intuitively sensible conjecture that this might help, it is very interesting that this conjecture is borne out so clearly in the results.

---

0.5
Dechook
0.72
Rundwed
0::5
0.32
0.32
0.51
0.29
2:55
0.
CA.trall
6:43
0:96
6:42
0.40
0.47
0.
Co
0,55
0.95
6:44
0.58
644
CARod
0:41
0.39
360
Dataret
Y
0:55
0.56
0.54
0.55
0.54
0.51
0.54
0.52
0.51
0.54
6.11
0:47
9.6
055
DBSU
0.54
0.58
0.46
0.52
0.
0.99
1.90
0:93
0.5
D002
0.30
0.47
0.49
2.57
0.63
0.74
0.49
0.55
0.4
0,75
0.79
0.50
0.78
0.60
0.4
0.50
0.52
0.2
0,3
Qudloiia Dokkdee M Buadon
Swi
Gudepii
Seiti
Narrative Style
Narative Style
Narnative Style
(4) G.::3355: Narrative Style
(b) GPT-4: Narrative Style
(c) Gemini-Pro: Narrative Style
Facebook
Renchene
Accuncy
Aceuncy
TRR
12L
Freebook CA Road
Facebook
CA Road
Iteadrenc
Heatom:
DRE
DGLP
Memory Clearance Strength
Memory Clearance Strength
Memory Clearance Steength
(d) GPT-3.5: Memory Clearance
(e) GPT-4: Memory Clearance
(1 Gemini-Pro: Memory Clearance
Figure 3: Different factors that influence LLM's graph recall. (a) (c): narrative styles. The heatmaps show that more advanced LLMs like GPT-4 yield best recall accuracy when the graph is narrated in language style consistent with its original domain. (d) (f): memory clearance.
Gemini-Pro appears more sensitive to small noise in context, while GPT's are more robust.
Pacibook (1-6.44)
CARaat (-9-55)
(10.70
DRLP
Endas Rore
Aay Lan Proliciion
A-c Link Presecii
Ave Lan Pesticion
066 Copp
0.2
Grept
Cloghh
Graph
Figure 4: Correlation between GPT-3.5's performance at graph recall (y) and link prediction (z:).
Given this, it is natural to ask whether the result might be coming from the mechanics of the training; in particular, is it possible that the LLM just reciting text from its training corpus, since the five datasets we use are all public on the Internet? We find this very unlikely, for simple reason: while the structured graph data comes from the Internet, the narrative descriptions do not; they were generated by us from a simple template for purposes of this experiment, as explained in Sec
Since superficial explanations do not seem explain the strength of the results, it becomes reasonable to suppose that the narrative style is indeed helping with the graph recall task. There are natural, if subtle, reasons why this may indeed be the case: since organically produced text describing road networks, for example, refers a different distribution over graph structures than organically produced text describing social networks, distributional properties in the text align with the distributional properties of the graph that the text describes. An implication is thus that LLMs, especially GPT-4, may have indeed formed a good understanding of the different distributions of graph structures from different domains, as otherwise they wouldn't be able to so consistently perform better when the narrative matches the data domain.
a plausible mechanism that recall is helped when the
4.2 Strength of Memory Clearance
Motivation, Our next experiment contains memory clearance (word span test) which is a standard component in previous human graph recall tests. We use memory clearance both to align with these human tests and to simulate the real-world situation where an L.LM may not be asked to work on the key data immediately after it receives them.
7

---

Table Correlation between LLM's graph recall and link prediction on different microstructures.
Microstructure
Dataset Task
Edge
Triangle
Star
Alt-Triangle
Alt-2-Path
Facebook
Graph Recall
-3.00+-5880
1.72+-1.34
-0.70+33000
-0.91+-2.25 | 1.21+-0.55
3.31+-1,77
Link Prediction
-.011-0.69
3.24+-1.05
-3.334-7.39
4.98+-3.01
Road
Graph 0.64+-0.1
7.31+-349
-3.4++ 1.77 4
-1.47-0.92 4
2.35+
Link Prediction
0,334-0.58
5,10+-3.73
-7.00+-3.34
1.64+-0.50
2.86+-2.50
Reactome
Graph Recall
18.014-6.22
-0.71+-4.62
4,96-
-6.324-4.23
4.434-4.93
Link Prediction
-9.99+3..0
7.71+-4.62
4.99+-4.44 4
8.32+-2.10
4.54+-4.25
DBLP
Graph Recall Link Prediction
3..2++3.25
1,17+-4.43
7.17+2244
41.166+4.35
3.77
-6.81-55.44
6,11+-4.68
-2.85+-2.47
7.43+4..04
2.83+-1.72
Erdūis Rényi
Graph Recall
-1.40+-5.01
9.57+-4.89 f
L40+-2.71
-0.41+4.119
3.36+-2.76
Link Prediction
2.514-3.79
8.44+ 4.26
-0.35+2.27
7.59+ 6.22
3.38+ 2.55
Since both GPT and Gemini are able to perform 100% correctly in the word span test, by design principle we always need to progress to the maximum set of seven sentences. This makes the memory clearance significant source of noisy context between L.LM's first sight of the graph and the final prompt of the recall question. Therefore, it is natural to wonder if the relatively poor performance of LLMs this graph recall test could have resulted from too much noisy context. this mini-study, we investigate how different strengths of memory clearance measured would affect the performance.
The strength of memory clearance can be naturally measured by the maximum number of sentences of which the subject proceeds to recite the final words. The number in the standard word span test ranges from 2 to 7, and 0 if the test dropped. Therefore, we vary this number in our experiment and record the performance of each model on each dataset.
Result Analysis. The results shown in FigureBidd (f), and we have the following findings.
LLMs can significantly differ on their sensitivity to small amount of noise in graph recall. The trends are clear from the three line plots: Gemini-Pro's performance plunges in the first few clearance levels before it touches the bottom. GPT's performance, in contrast, remain more stable, or even increases initial clearance levels. This indicates that many of our results for GPT models may still likely hold when there is no memory clearance, i.e. prompt is given immediately after relevant context which is default setting of most previous studies.
Performance of GPT-3.5's and Gemini-pro's is poor even when the question prompt provided immediately after the relevant context. This is obvious from the line plots' intersections with y-axis, and perhaps a bit surprising to people who have primarily focused on using LLMs for more challenging graph tasks. This result also helps eliminate the chance that the mediocre performance comes from overly strong memory clearance module that we've installed in place. To boost LLM's ability to reason graphs, we may need to first figure out how to help them better attend to the correct edge before we seek to improve other more advanced aspects of reasoning. See Sec. 6 for more discussion.
Correlation between LLM's Graph Recall and Link Prediction
Motivation. The graph recall task should not be confused with How do microstructures and perfor- mance of LLM's graph recall affect its behavior in other graph reasoning tasks? In this mini-study, we conduct a correlation analysis of LLM's behavior in the label-free link prediction task, which is important graph reasoning task for LLMs (24]. We primarily experiment with GPT-3.5 because its graph recall exhibits more significant microstructural patterns than GPT-4, and meanwhile have larger performance variation than Gemini-Pro.
Procedures. For each graph in the five datasets, we remove 20% of their edges as missing edges. The LLM is then asked to predict those missing edges. Two types of correlation are studied: (1) accuracy

---

correlation: for each graph in the dataset, we evaluate the LLM's link prediction accuracy (z) and graph recall accuracy (y) then map these results onto a scatter plot; (2) microstructural correlation: similar to Table and we evaluate and compare the microstructural coefficients of the predicted graph (in link prediction) and the recalled graph (in graph recall test). Table 3 shows the results.
5.1 Result Analysis.
TigureAshowwe the scatter plots for accuracy correlation; Table shows microstructural correlation.
LLM's link prediction performance correlates well with its graph recall performance on real- world graphs. This is clear from the scatter plot and the r values. For Erdös-Rénny graphs, the correlation is close to zero, which is unsurprising though because the link prediction random graphs cannot do better than random guess.
Different tasks may trigger behavior changes of LLMs that can be subtly revealed by their microstructural bias. Table 3l shows that LLM's microstructural bias in both tasks tend to be positively correlated on triangles and alt-2-paths, and negatively correlated on alt-triangles. We do not have an intuitive explanation for this result. However, this result does indicate that different tasks can trigger certain interesting behavior changes of L.LSs that can be subtly revealed by examining their microstructure patterns, which shows the meaningfulness of our study.
6 What to Inform about Future Research: an Empirical Perspective
We consider this study step towards the long-term agendas both for improving LLM's graph reasoning ability and for further integrating LLM graph analysis into social-science applications. Here we discuss how our findings may translate into actionable bias mitigation strategies and architectural improvements. Appendix further discusses limitations of the work.
The graph recall test is one of the simplest and most fundamental graph reasoning tasks. Since ad advanced LLMs yield unsatisfactory performance in this test, we need to re-examine the recent development of approaches that attempt to directly solve more challenging graph reasoning tasks. Meanwhile, notice the association between graph recall test and the "Needle in a Haystack" test (i.e. random fact retrieval from long context) [26 19: in some sense, the former can viewed as a "graph-ccstoomzedd" version of the latter. Therefore, existing techniques for boosting LLM's performance in the "Needle in a Haystack" test, e.g. recurrent memory augmentations 26 may likely benefit LLM's 's's graph recall ability as well.
Our experiment shows that LLMs tend to favor more triangles and alternating 2-paths. Researchers of Graph Foundation Models (GFM) [31] 33 59 29 should be alerted of such systematic bias. Because the procedures for training GFMs are largely inspired by those for LLMs, similar re- trieval bias could emerge. A potential mitigation strategy worthy of exploration is to consider balancing/comppenatiing the frequencies of different graph motifs that occur in the training data.
We have also found that more advanced LLM's performance have a striking dependence on the compatibility between the application domain of real-world graph and its narrative style. This hints a potential direction for designing more powerful graph encoding for LLMs via certain domain adaptation strategies - by combining the adaptation strategy with either the graph-to-text
methods 18 20 or the graph-to-embedddin methods 12 37
7
Related Work
7.1 Humans in the Graph Recall Task
There have been decades of work studying human's graph recall ability, primarily focused on their memory and recall of social networks. This line of work originates from sociologist's need to collect real-world social networks by asking people to recall their social relationships. [4 noticed that people forget a significant portion of their social networks, so they built a to predict missing links from recall.
O more closely study the mechanism of the forgetting of social networks. [5] found that
humans can more accurately recall social networks that contain more certain microstructural patterns such triangles or cliques.

---

Following the previous works, [8] establishes experimental protocols for examining the performance and microstructural patterss of human's 's recall of social networks. In their study, each subject reads a short, artificial description of the relationships among a number of 15 people: "Henry is member of the same club as Elizabeth. James sings in a choir with Anne ". The subject is then asked to name who has interacted with whom in the experiment. The authors are also among the first to verify that humans' graph recall tend to exhibit patterns of triadic closure. 7 further investigates how sex affects human's ' recall. [6] uses signed network model to show that human's graph recall may repel certain unstable patterns that involve unbalanced relationships between enemies and friends. Since LLMs are trained on are instructional to our exploration of LLM's graph reasoning ability. Further studies show that a person's 's ability to accurately recall social network has profound influence on their social decisions 25
corpus, many ideas and findings human's 's graph recall
52 53
The graph recall test is meaningful test for both humans and LLMs, though their experiment outcomes may need to be interpreted in subtly different way. The graph recall test meaningful for LLMs because we observe their performance to be far from perfect in the test. Compared with humans, however, LLMs may face different challenges. Human's 's bottleneck in this test is their limited brain capacity, while LLMs may have difficulty in always attending to the correct positions in distant earlier context (or in precisely encoding context into hidden states for RNN- based models).
7.2 Graph Reasoning with Large Language Models
Graph reasoning with LLMs is an active research area in recent years. On the benchmark and methodology level, datasets and frameworks are developed to integrate graphs with LLMs 49 36 In addition, researchers are exploring ways to solve question answers over structured data with LLMs in a unified way [23]. Others are also trying to advance the prompting capabilities of LLMs by mimicking the connective manner of human thinking elaboration [4]. There has also been work on developing general graph models to handle various graph tasks with a unified framework [30). More recently, (33) provides theoretical analysis on the limit of transformer's reasoning capability on graphs, by relating transformer's 's capabilities on graph reasoning to the computational complexity of related tasks. On the application level, LLMs have been adopted in graph reasoning applications such as node classification (21] 14,, graph classification [38 60), knowledge graphs [58] 56). and recommendation systems
(55) We are still lacking data perspective to address the basic question of whether LLMs can accurately remember the graph that they are supposed to reason upon, which is a prerequisite for any advanced graph tasks. Inspired and supported by cognitive studies, we conduct the first comprehensive investigation of graph recall by LLMs, filling a gap in the existing literature.
8 Conclusion
This work proposes and studies graph recall as a simple yet fundamental task for understanding LLM's graph reasoning abilities. We design and conduct systematical studies on the accuracy and biased microstructures LLM's graph recall, by creatively drawing its connection with the existing cognitive studies on humans. Future work may examine more varieties of microstructural patterns including higher-order structures [51] and "sense of distance", both of which which are crucial for understanding graph structures [28 50 (5]. Another direction is to study how to improve LLM's graph recall by prompting or other methods.
Acknowledgment
We thank Matt Brashears, Eric Quintane for their help in discussing their earlier work network recall and its relation to the current project, as well as their help with data relevant to their work. We also thank Tianxiang Zhao for his insights into the intersection of graphs and LLMs. Their generous assistance was a great benefit to our project. Our work here has been supported in part by a Vannevar Bush Faculty Fellowship. AFOSR grant 1495500-191-001 from the MacArthur Foundation, and a grant from the Microsoft AFMR program.
Simons Collaboration grant, a grant
10

---

References
[1] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, lige Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.087: 2023.
[2] Uri Alon. Network motifs: theory and experimental approaches. Nature Reviews Genetics, 8(6):450-461, 2007.
[3] Jacob Andreas. Language models as agent models. In Findings of the Association for Computational Linguisties: EMNLP 2022, pages 5769-5779, 2022.
[4] Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Michal Podstawski, Hubert Niewiadomski, Piotr Nyczyk, and Torsten Hoefler. Graph of thoughts: Solving elaborate problems with large language models. In AAAI, 2024.
[5] Matthew E Brashears. Humans use compression heuristics to improve the recall of social networks. Scientific reports, 3(1):1513, 2013.
[6] Matthew E Brashears and Laura Aufderheide Brashears. The enemy of my friend is easy to remember: Balance as compression heuristic. Advances in group processes, volume 33, pages 1-31. Emerald Group Publishing Limited, 2016.
[7] Matthew E Brashears, Emily Hoagland, and Eric Quintane. Sex and network recall accuracy.
Social Networks, 44:74-84, 84, 2016.
[8] Matthew E Brashears and Eric Quintane. The microstructures of network recall: How social networks are encoded and represented in human memory. Social Networks, 41:113-126 2015.
[9] Devon D Brewer. Forgetting in the recall-based elicitation personal and social networks. Social networks, 22(1):29944 2000.
[10] Tom Brown, Benjamin Mann, Nick Ryder, Mclanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
[11] Ronald Burt, Joseph Jannotta, and James T Mahoney. Personality correlates of structural holes. Social networks, 20(1):63-81) 87, 1998.
[12] Ziwei Chai, Tianjie Zhang, Liang Wu, Kaiqiao Han, Xiaohai Hu, Xuanwen Huang, and Yang Yang. Graphllm: Boosting graph reasoning ability of large language model. arXiv preprint
1rXiv:2310.05855, 2023.
[13] Runjin Chen, Tong Zhao, AJAY KUMAR JAISWAL, Neil Shah, and Zhangyang Wang. Llaga: Large language and graph assistant. In Forty-first International Conference on Machine Learning, 2024.
[14] Zhikai Chen, Haitao Mao, Hongzhi Wen, Haoyu Han, Wei Jin, Haiyang Zhang, Hui Liu, and Jiliang Tang. Label-free node classification on graphs with large language models (Ilms). ICLR, 2024.
[15] Antonia Creswell, Murray Shanahan, and Irina Higgins. Selection-inference: Exploiting large language models for interpretable logical reasoning. In The Eleventh International Conference on Learning Representations, 2022.
[16] David Croft, Gavin O'kelly, Guanming Wu, Robin Haw, Marc Gillespie, Lisa Matthews, Michael Caudy, Phani Garapati, Gopal Gopinath, Bijay Jassal, et al. Reactome: a database of reactions, pathways and biological processes. Nucleic acids research, 39(supp[[I::D91 2010.
[17] Meredyth Daneman and Patricia A Carpenter. Individual differences in working memory and reading. Journal of verbal learning and verbal behavior, 1944:4500-466, 1980.
[18] Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. Talk like a graph: Encoding graphs for large language models. arXiv preprint arX1v:2310.04560, 2023.
[19] gkamradt. L.mmtet needle haystack pressure testing llms.
com/
http://LMneettt.eeeeeeeeellaaaaa 2023.

---

[20] Jiayan Guo, Lun Du, and Hengyu Liu. Gpt4graph: Can large language models understand graph structured data? an empirical evaluation and benchmarking. arXiv preprint arXiv:2305.15066. 2023.
[21] Xiaoxin He, Xavier Bresson, Thomas Laurent, and Bryan Hooi. Explanations as features:
Llm-based features for text-attributed graphs. ICLR, 2024.
[22] Herminia Ibarra. Homophily and differential returns: Sex differences in network structure and
access in an advertising firm. Administrative science quarterly, pages 422-447, 1992.
[23] Jinhao Jiang, Kun Zhou, Zican Dong, Keming Ye, Xin Zhao, and Ji-Rong Wen, Structgpt: A general framework for large language model to reason over structured data. In Houda Bouamor, Juan Pino, and Kalika Bali, editors, EMNLP, 2023.
[24] Bowen Jin, Gang Liu, Chi Han, Meng Jiang, Heng Ji, and Jiawei Han. Large language models on graphs: A comprehensive survey. arXiv preprint arXiv:231 htt.::3312022255. 02.2783, 2023.
[25] Martin Kilduff and David Krackhardt. Interpersonal networks in organizations: Cognition. personality, dynamics, and culture, volume 30. Cambridge University Press, 2008
[26] Yuri Kuratov, Aydar Bulatov, Petr Anokhin, Dmitry Sorokin, Artyom Sorokin, and Mikhail Burtsev. In search of needles in a 10m haystack: Recurrent memory finds what llms miss. arXiv preprint 2t.t22422..790), 2024.
[27] Jure Leskovec and Julian Mcauley. Learning to discover social circles in ego networks. Advances in neural information processing systems, 25, 2012.
[28] Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465-445
2020.
[29] Hao Liu, Jiarui Feng. Lecheng Kong, Ningyue Liang, Dacheng Tao, Yixin Chen, and Muhan Zhang. One for all: Towards training one graph model for all classification tasks. arXiv preprint arXiv:2310.001
2023.
[30] Hao Liu, Jiarui Feng. Lecheng Kong, Ningyue Liang, Dacheng Tao, Yixin Chen, and Muhan Zhang. One for all: Towards training one graph model for all classification tasks. In ICLR, 2024.
[31] Jiawei Liu, Cheng Yang, Zhiyuan Lu, Junze Chen, Yibo Li, Mengmei Zhang, Ting Bai, Yuan Fang, Lichao Sun, Philip S Yu, et al. Towards graph foundation models: A survey and beyond. arXiv preprint arXiv:23100 20. 18299, 2023.
[32] Aman Madaan, Shuyan Zhou, Uri Alon, Yiming Yang, and Graham Neubig. Language models of code are few-shot commonsense learners. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 1384-1403, 2022.
[33] Haitao Mao, Zhikai Chen, Wenzhuo Tang, Jianan Zhao, Yao Ma, Tong Zhao, Neil Shah, Michael Galkin, and Jiliang Tang. Graph foundation models. arXiv preprint arXiv:2402.00 022111....2 2024.
[34] Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Network motifs: simple building blocks of complex networks. Science 298(5594):224-82,, 2002.
[35] Elisa Omodei, Matthew E Brashears, and Alex Arenas. A mechanistic model of human recall of social network structure and relationship affect. Scientific reports, 7(1):17133, 2017.
[36] Shirui Pan, Yizhen Zheng, and Yixin Liu. Integrating graphs with large language models: Methods and prospects. IEEE Intelligent Systems, 2023.
[37] Bryan Perozzi, Bahare Fatemi, Dustin Zelle. Anton Tsitsulin, Mehran Kazemi, Rami Al-Rfou, and Jonathan Halcrow. Let your graph do the talking: Encoding structured data for llms. arXiv 2024.
preprint a arXiv:2402.05888
[38] Chen Qian, Huayi Tang, Zhirui Yang, Hong Liang, and Yong Liu. Can large language models empower molecular property prediction? arXiv preprint arXiv:2307.07443 2023.
[39] Garry Robins, Pip Pattison, Yuval Kalish, and Dean Lusher. An introduction to exponential random graph (p*) models for social networks. Social networks, 173 2007.
[40] Kimball Romney and Katherine Faust. Predicting the structure of a communications network from recalled data. Social Networks, 4(4):285-304, 1982.
12

---

[41] Adam R Roth, Siyun Peng, Max E Coleman, Evan Finley, and Brea L Perry. Network recall among older adults with cognitive impairments. Social Networks, 64:99-108, 2021.
[42] David Rozado. The political preferences of Ilms. arXiv preprint arXiv:2402.0178) 2024.
[43] Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Halcrow, Bryan Perozzi, and Vahab Mirrokni. Understanding transformer reasoning capabilities via graph algorithms. arXiv preprint arXiv:2405. 00..4055.15111 18512, 2024.
[44]
Brent Simpson, Barry Markovsky, and Mike Steketee. Power and the perception of social networks. Social Networks, 33(2):166-171, 2011.
[45] Stavros Sintos and Panayiotis Tsaparas. Using strong triadic elosure to characterize ties in social networks. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1466-1475, 2014.
[46]
Gemini Team, Rohan Anil, Sebastian Borgeaud, Yonghui Wu, Jean Bean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, et al. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312. 1805, 2023.
[47] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307 .09288, 2023.
[48] Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can language models solve graph problems in natural language? In Proceedings of the 2023 Conference on Neural Information Processing Systems, 2023.
[49] Heng Wang. Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can language models solve graph problems in natural language? In NeurIPS, 2023.
[50] Yanbang Wang, Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. arXiv preprint arXiv:2101.05974, 2021.
[51] Yanbang Wang and Jon Kleinberg, From graphs to hypergraphs: Hypergraph projection and its reconstruction. In The Twelfth International Conference on Learning Representations, 2024.
[52] Yanbang Wang and Jon Kleinberg. On the relationship between relevance and conflict in online social link recommendations. Advances in Neural Information Processing Systems, 36, 2024.
[53] Yanbang Wang, Pan Li, Chongyang Bai, and Jure Leskovec. Tedic: Neural modeling of behav- ioral patterns in dynamic social interaction networks. In Proceedings of the Web Conference 2021, pages 693-705, 2021.
[54] Yanbang Wang, Pan Li, Chongyang Bai, V Subrahmanian, and Jure Leskovec. Generic representation learning for dynamic social interaction. In Proc. 26th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining Workshop, pages 1-9, 2020.
[55] Wei Wei, Xubin Ren, Jiabin Tang, Qinyong Wang, Lixin Su, Suqi Cheng, Junfeng Wang, Dawei Yin, and Chao Huang. Limrec: Large language models with graph augmentation for recommendation. In WSDM, 2024.
[56] Yunzhi Yao, Shengyu Mao, Ningyu Zhang, Xiang Chen, Shumin Deng, Xi Chen, and Huajun Chen. Schema-aware reference as prompt improves data-efficient knowledge graph construction. In SIGIR, 2023.
[57] Haoteng Yin, Yanbang Wang, and Pan Li. Revisiting graph neural networks and distance encoding from a practical view. arXiv preprint 1:XXi:2011.12225: 2020.
[58] Rui Zhang, Yixin Su, Bayu Distiawan Trisedya, Xiaoyan Zhao, Min Yang. Hong Cheng, and Jianzhong Qi. Autoalign: Fully automatic and effective knowledge graph alignment enabled by large language models. IEEE Transactions on Knowledge and Data Engineering, 2023.
[59] Ziwei Zhang, Haoyang Li, Zeyang Zhang, Yijian Qin, Xin Wang, and Wenwu Zhu. Large graph models: A perspective. arXiv preprint ArXiv:2308. 14522, 2023.
[60] Haiteng Zhao, Shengchao Liu, Chang Ma, Hannan Xu, Jie Fu, Zhi-Hong Deng, Lingpeng Kong, and Qi Liu. Gimlet: A unified graph-text model for instruction molecule zero-shot learning. bioRxiv, 2023.
13

---

Appendix
A Code and data
Our code and data can be downloaded at: httppe//ggtaab..co/bbbb0//22///1 http:///bbblll0////laaaaarrreell
B More Experimental Details
Dataset. For the experiment in 3.1 and 3.2] Fig 5 show graph samples of the Facebook,
Reactome, and Erdos-Renyi datasets. The graph narratives are shown in Appendix B.1 The sentence sets for memory clearance shown in Appendix B.2.1
For the experiment in Sec 3.3 we utilize the two social networks in 8 human experiment. Each social network was presented to the test taker in two different narrative styles: one is friendship-basees and the other is kinship-bate based egg. "James is the brother of Anne..." " In Brashears' experiment, test taker has equal chance to their paper, however, was reported an aggregated form that mixes up response to both narrative styles, the authors reported choose do the same with LLMs, but make a note that LLMs may behave differently to different graph narrative styles, which we have further investigated in separate study, Sec 4.1
of the two narrative style (but never both). The final result in
difference between caused by these two. To stay aligned
We need to be careful with the generation of the node names, because it affects how much parametric knowledge in the LLM gets elicited to aid the graph recall process. We general guideline is that, although the parametric knowledge can potentially create a shortcut for LLM's handling of the graph recall task, this should not be forcefully forbidden as it is also seen in real-world applications. Therefore, we have two cases when creating our datasets, namely (1) where parametric knowledge potentially useful, and (2) where parametric knowledge is less useful.
For protein networks, the protein names are not random. They are unique protein identifiers (known as the "UniProtK B/Swiss- Prot accession number" or NCBI index). Each node is assigned its real name. We also confinmed that LLMs know and precisely understand those protein identifiers. The same true for DBLP coauthorship networks.
For all other networks, the node names are generated and randomly assigned. For example, in traffic (geographical) networks, the node names are "bank", "townhall", "high school", etc.
Computing Resources. We use the Azure OpenAl service to test GPT-based models. For Gemini-Pro, use the gemini-pro model API provided by Google's 's Generative Al. For Llama Family models, we use the open-sourced models meta-llama/Lie http//llaaaa2----a and meta-llane 1laaaaalamaa2-1111 48 GB of RAM.
on Hugging Face, tuned on two Quadro RTX 8000 GPUs with
14

---

Figure 5: Graph samples of the Facebook dataset.
Figure Graph samples from the Reactome (protein- protein interaction) dataset.
15

---

Figure 7: Graph samples of the Erdos-Renyi dataset.
Irreducible
Redueible
Figure 8: The two 15-node social networks with different connectivity patterns used in 8 and in our Sec. 3.3 experiment.
16

---

B.1 Samples of the Graph Narratives for All Datasets
** **acebook***
Harper, James, Abigail, Noah, Alexander, Oliver, William, Charlotte, Sophia, Benjamin, Emily, Daniel, Ethan, Henry. Their have friend- ships: Harper and Daniel are friends. Harper and Sophia are friends. James and William are friends. James and Daniel are friends. James and Abigail friends. James and Sophia are friends. James and Noah are friends. Abigail and Benjamin are friends. Abigail and Noah are friends. Abigail and Ethan are friends. Abigail and William are friends. Noah and Charlotte are friends. Noah and Benjamin are friends. Noah and Emily are friends."
"The following people have friendship relations:
**Traffic Network**
We have traffic network that involves the following destinations: Bank, Town Hall, Grocery Store, High School. The traffic network is the following. The traffic can directly flow from the Bank to the Grocery Store. The traffic can directly flow from the Town Hall to the Grocery Store. The traffic can directly flow from the Grocery Store to the High School.
**Protein Interaction **
The following proteins have mutual interactions: Q13563, Q16280, P61006, O75385, Q9ULVO,
075154, Q7L804, Q15907, Q96QF0, Q8IV77, POS 100, P18085, Q14028, P98161, Q9ULHI,
Q9P2M4. Their interactions are: Protein Q13563 interacts with Protein P98161. Protein Q13563
interacts with Protein PO8100. Protein Q13563 interacts with Protein Q8IV77. Protein Q13563
interacts with Protein Q16280. Protein Q13563 interacts with Protein Q14028. Protein Q13563
interacts with Protein P18085. Protein Q13563 interacts with Protein QUULHI. Protein Q13563
interacts with Protein 075154. Protein Q13563 interacts with Protein P61006. Protein Q13563
interacts with Protein Q96QF0. Protein Q16280 interacts with Protein P98161. Protein Q16280
interacts with Protein PO8100. Protein Q16280 interacts with Protein Q8IV77. Protein Q16280
interacts with Protein Q14028. Protein Q16280 interacts with Protein P18085. Protein Q16280
interacts with Protein QUULHI. Protein Q16280 interacts with Protein 075154. Protein Q16280
interacts with Protein P61006. Protein Q16280 interacts with Protein Q96QFO. Protein P61006
interacts with Protein Q96QF0. Protein P61006 interacts with Protein P98161. Protein P61006
interacts with Protein P08100. Protein P61006 interacts with Protein Q8IV77. Protein P61006
interacts with Protein Q14028. Protein P61006 interacts with Protein Q9ULHI, Protein P61006
interacts with Protein O75154. Protein O75385 interacts with Protein Q15907. Protein O75385
interacts with Protein Q9P2M4.
** =EEdoos-Rent Renyi *raph**
A graph has the following nodes: Node 0, Node 1, Node 2. Node 3, Node 4, Node 5, Node 6, Node 7, Node 8, Node Node 10, Node 11, Node 12. Node 13, Node 14, Node 15, Node 16, and the following edges: Node 0 is connected with Node 1. Node 0 is connected with Node 2. Node 0 is connected with Node 3. Node 0 is connected with Node 4. Node 0 is connected with Node 6. Node is connected with Node 7. Node 0 is connected with Node 8. Node 0 is connected with Node 10. Node 0 is connected with Node 11. Node O connected with Node 12. Node 0 is connected with Node 13. Node 0 is connected with Node 14. Node 1 is connected with Node 4. Node is connected with Node 5. Node 1 is connected with Node 7. Node is connected with Node 8. Node 1 is connected with Node 9. Node is connected with Node 10. Node is connected with Node 11. Node 1 connected with Node 14. Node I is connected with Node 16. Node 2 is connected with Node 4. Node 2 is connected with Node 5. Node 2 is connected with Node Node is connected with Node 7. Node 2 is connected with Node 9. Node 2 is connected with Node 10. Node 2 is connected with Node 11. Node 2 is connected with Node 13. Node is connected with Node 14. Node 2 connected with Node 16.
17

---

B.2
Textual Samples Used in Experiment
B.2.1
Sentence Sets for Memory Clearance
**Two sentence sets**
"The ghillie suit, the modern sniper's principle camouflage uniform, derives its name from Scottish game hunters."
"Industrial accidents- explosions of stored oil and gas- are bad enough on land."
**Three sentence sets
"But overall, the teenage share of the population wasn't getting much bigger." "This is a system steeped in tradition, and think that's part of the problem."
"We're unable to move, legs stuck beneath under great weight."
**Seven Sentence Set**
"One aftermoon open letter from my younger sister, the photo chronicler of family events." "Although they have enough food sustain your group for years, supermarkets are also danger- ous."
"Maternity, or additional offspring, may force upon the woman a distressful life and future."
"By Wednesday night's vote meeting, Sabrina was thoroughly disgusted by the superficiality of the week."
ask him to please stop lying about trying to take my place in the war."'
"Since the 1950's, freeways have been built through every large and medium-sized city." "Instead, he took job in Washington, analyzing weapons expenditures for the U.S. Navy."
18

---

C Full Comparison of True Graph and LLM Recall Graph
We provide full comparison of the true graph and the recall graph from different LLMs. The results are shown in Table
Table and Table 6 respectively.
Table Full comparison of true graph and GPT- Table 5: Full comparison of true graph and GPT-4 3.5 recall graph on different microstructures.
recall graph on different microstructures.
Microstracture
Edly
Dateat
Faige
Trangle
Star
ab-Trannie
Ab-2-hai
Fashhec
Fasthook
Gloph
818--1
061+-0.11
<1 0.755-011
Graph
Recil
0.14-1151 3077-0330
0.65-061
126-021
3.70-5800
4.701-3.00
Dill
0.054-6775
(106-00:1
801--006
CA Read
CA Roal
True Glapls
2356-250
2901-1-79
4.31-1.53
-0:31
4.25-0.32
Graph
0.36e2
2.We-1:79
448
-2.03=0-111
Recall
1.11-1733
Gopp
739-1152
3.34--135
Broetoe
Bostimm
Uhe Grass
58.194-5.8
1:33-4.31
9.46--3.0
L15--261
1-00-322
Tue Gruph
18.19-5306
1.34-433
946--150
L154-261
140-333
Reaal Gagp
1118-55
0.57--1.1
1.
17+-1.89
181e-11
Roall Coogh
2.15-1.31
1.7--1311
4044--13
11.4--532
2.0-2377
-1.99-2000
0.46-214
DRLP
The Cliegh
7.8m-124
-1 A84--100
-1 1.300-3441
2.0--3114
-1177-1:30
The Draph
1.64-3324
+1 6.6--22.2
<5 5.30--241
2.604-2.1
-1.17-230
Rocall Geople
12401-224
0.511
LX81-1.70
4.471-4.16
4.00-355
Razil Creph
6376-808
-5 3.94-1335
4.40+1111
-2 1.-6-223
3126-325
1,171-448
7.171:244
11.16::433
3.711-376
Diff
1236-256
1:40
0.994324
1.50-224
Ead'
The Groph
it 1119--5 84
11 1.99
0.75+-3.55
0:6-1106
1.3
-196-1159 1.59
1.3
Rocill Gimple
- 1.80-5 10
7614-425
0.64-116 66
0.4--330 3.30
4.24-2533
Recil Gruph
-160-321
4.04-1109
-0.34-2.13
0.400-1.40
0636-176
1140-501
9.37-4339
1404-271
00414-1.19
Dif
-140 15
199--1:94
1.55--775 7.79
76a-
Table 6: Full comparison of true graph and Gemini-Pro recall graph different microstructures.
Microstructure
Dataset
Edge
Tringge
Shor
Ali-Trianlee
Alb---uath
Facehook
Gruph
0184-11466
0.64-00.57
-1.75+0445
-002--0.44
1.07-4021
Recall Graph
-1.44-000
-1.68--3.000
-0254-2.35
2.381-1.35
1.74--1.05
Dift
-.31
-2.291-2.99
1.00-2.37
2,00-1137
0.671-1.10
True Graph
0.86+22.0
2.90+11779
-1834-1.53
-2.07-0.37
4.75+00.22
Recall Graph
1.70+-111
4.934-0.84
0.44-2.95
-1.88-0
-2.074-2.28
Diff
0.81-1168
2022-0022
5.24-0227
0.894-0.28
4.824-0.62
Reactome
Gruph
18.19-5.6
1.24-4.31
9046--2.50
140+-3.28
Recall Graph
6.251-5811
2.501-4.04
4.02--387
4.471-8.71
5.56-5.01
Diff
4.694..666
1276:5:22
13.47-4.70
3:326-4.57
4.15+4.01
DBLP
Graph
7.631-3:24
-5300-2.41
-1.174-2.30
Recall Graph
11.84e-.722
3.400-3.83
5.94--2.13
-8.39-3.34
9.66+-3.99
Dift
19.376-330
-1.72+3.45
11:24-2:45
-1108--3.90
10.83+11.53
Erdös- Rdayá
0.19--3.4
-1.96--1.59
0.75+-3.26
1.38+-0.89
Recall Gruph
3.06--1667
40,55+4000
-1.44+11.20
1.15-2.17
0.69+-0.16
Dill
2.86-
1.11-5.04
-0.64-3.95
0.594-281
-0.70-1.115
19

---

D Sex Priming as a Mini-study
Motivation. 7 interestingly found that females can more accurately recall their social networks than males. The underlying explanation is that underrepresented groups tend to be more aware of their surroundings. We conjecture that this trend might also exist the corpus on which LLMs are trained, and therefore wonder whether LLMs perform better at graph recall when asked to play the role female.
Aligned with '7's I's design, we include at the beginning of the test (i.e. prior to all steps) prime, which is piece of text designed to elicit the test subject's awareness of their sex. [7]'s sex prime is a short question that asks the subject's opinion on same-sex versus mixed-sex housing. However, this method fails with LLMs because they refuse to identify having any pre-given sex. Instead, we send role- vole-plaiin instructions to LLMs by stating their "sex" the system message at the beginning of the chat. We further confirm the successful elicitation by asking what their sex is afterwards. We compare the LLM's graph recall performance under male and female roles.
Procedures.
Result Analysis. The results shown in Fig (g) (i). The error bars 95% confidence intervals. The effect of sex roles appear to be insignificant in most cases, which negates our initial conjecture and interestingly opposes the existing findings humans. In fact, LLMs underperform in both roles when compared with the control group, i.e. cross-referencing Table T "Accuracy" column.
1.2
Accuncy
Malt
Lemalo
Pertale
Dacthook
FRLP
Baotbokk
Backhne
Fandbook
1B22
Dacasets
Datasets
Datiness
GPT Sex
(h) GPT-4 Sex
(g) Gemini- ProminiiPPro::c Sex
Figure 9: Different factors that influence LLM's s graph recall. g (i): sex. Following M7's
procedures, we test and find that the effect of sex roles that an LLM asked to play insignificant on their capability of graph recall a result different from that on humans.
20

---

E Full Performance Metrics with Different Narrative Styles
The full performance comparison of different narrative styles on five datasets for each LLM is present in Table
Table Full graph recall performance metries with different narrative styles on five datasets.
GPT-3.5 (8)
GPT-4 (8)
Gemini-Pro (5)
Datuset
Nurrative Style
Accurucy
Precision
Recull
Precision
Recull
Accaracy
Precision
Recall
Social
66.84
51.13
Geological
Facebook
Biological
$1.99
47.11
40:48
75.91
19.93
48.64
67.72
31.01
08.79
27.67
49.88
Co-authership
42.30
48.76
38.25
53.09
37.98
51887
37.42
$3.59
28.95
51.84
27.08
42.27
Random
47.57
47.81
40.28
03.03
44.57
51.27
40.41
51.54
24.36
55.25
31.39
27.30
Social
41.37
49.30
36.43
53.07
40.85
$8.22
40.85
40.85
28.19
40.55
25.78
45.17
Gcological
Biological
Co-authorship
40.6
48.71
$3.66
40.50
$7.91
40.67
24.08
40.15
46.41
Randoen
31.88
47.26
29.39
38.14
31.43
49.10
29.38
35.58
31.52
59.93
33.23
35.46
Social
$6.32
54.99
49.5 54
71.59
50.68
$3.69
50.45
50.91
43.34
51.5%
47.48
$2.57
Geological
57.47
56.18
51.41
68.15
50.09
54.05
50.41
50.06
48.72
51.28
44.97
63.11
Reactome
Biological
44.17
53.68
46.53
$4,62
76.80
77.04
77.57
77.44
46.59
51,09
49.06
55.07
Co-auburship
53.67
52.77
46.82
Social
51.00
53.79
42.65
68.22
42.05
58.79
42.05
42.05
35.72
49,70
36.09
$1.83
Goological
47.01
59.17
30
$3.66
42.10
$9.81
42.09
42.3
41.89
47.02
36.96
66.99
DBLP
Biological
51.75
41.300
4 11.44
75.21
50.60
50.30
41.67
69 24
41.95
19.15
33.76
69.52
Co-authorship
65.08
72.47
67.55 56
74.97
97.88
98. 70
97.17
98, 88.81
47.36
46.35
40.23
77.56
Rundocn
45.22
52.35
40.08
$4,86
53.58
39.98
47.07
57.50
32,94
13.06
Goological
62.70
$6.07
79.13
43.18
41.96
ER
Hiological
47.84
49.09
69.47
46.11
50.42
39.69
62.71
36.56
52.92
33.54
54.60
Co-anborship
$2.69
66.74
48. 15
66 66.00
61.13
78. 10
60:33
62.06
29.69
50.442
38.57
42.52
Randonn
49.40
55.21
45.33
63.94
44.03
60.34
44.97
44.40
22.27
$2,40
36.95
26.33
F Limitations
Our evaluation of LLM's graph recall performance is not exhaustive. Due to budget constraint, we only test on datasets from five domains and on limited number of graph samples from each domain. Also, while we have experimented with several main-streamt LLMs including GPT-3.5, GPT-4, Gemini-Pro, and Llama-2, there are other popular LLMs such as Claude 3 and Llama-3 which our experiment have not covered.
Another limitation of our work, which we also consider to be an important direction for future work, lies in the distinction between graph recall and graph retrieval. The latter requires a more variational setting on the amount of contextual noise in graph narratives. In our work, we have intentionally designed the graph narratives to be simple and fixed, because we already observed considerable errors in LLM's graph recall at this starting point (and we know little about LLM's behaviors even in this simplest setting). However, the real-world structure-rich text that LLMs process may contain significantly more contextual noise, where some of the findings in this work may not be easily generalizable (although we conjecture that many systematic bias we have observed will persist). How to both realistically and comprehensively vary the amount of noise in graphs narratives remains to be a challenging topic to explore.
Finally, despite being small, the gap between our result and the recent "Needles in a Haystack" by Greg Kamradt [19] on GPT-4 needs more investigation. In [19] it is reported that GPT-4 makes little errors in long-context recall over Paul Graham essays, up to the context length of 73k. While our study also shows (in Table IT that GPT-4 performs well on three out of the five datasets used, its performance on the rest two is mediocre. There can be many possible explanations to reconcile the gap, but the lack of robustness that we observe tests of this kind is an important starting point for further investigation.
G Relationship with the "Edge Existence" Task in (Fatemi et al.) 18
The edge existence task is one of the six exemplary tasks proposed [8] for measuring L.M'' graph reasoning ability. Both our graph recall test and the edge existence task require the LLM to
21

---

decide the existence of graph edges described in earlier text. However, our work has the following main differences and novelty.
The main topics of investigation are different. The central topics in this paper are 1) to unveil biased subgraph patterns (motifs) in LLM'' graph recall, (2) to rigorously compare LLM's performance with humans, and (3) to investigate how results of (1) are affected by various factors. These topics are not studied in [18].
The empirical findings are completely non-overlapped. Our work presents many findings about LLM's biased graph recall patterns and their rigorous comparison with humans, which are novel to 18].
Our experimental pipelines different. Our paper uses more rigorous evaluation pipeline inspired by classical human cognition studies. In addition to synthetic data, we also extensively use real-world datasets for experiment, which was reported (18).
22

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No] ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
We've made claims about this work's originality, novelty, and significance. They are accurately described, with the central task and scope well defined.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as 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]
23

---

Justification:
We have Appendix for this.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are 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 sell-specifiitiinn asymptotic approximations only holding locally). The authors should reflect on 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 on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texi system might not 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 to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren'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 a complete (and correct) proof?
Answer: [NA]
Justification:
This paper does not include theoretical results.
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 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: We've provided original code and data be downloaded at: https They can be used to re-
// //anonymous wwwe..pppn..... wtt.://nce//...emr.pe.eaaaaaaaaa graph-rreaal--8111
produce the main experimental results of the paper.
Guidelines:
24

---

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 a 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 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 it 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 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, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS 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) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be 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 deseribe the particular way they provide for reproducibility. In the case of closed-source models, it 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 to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We've provided original code and data to reproduce the main experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
gablic/guides/Codeee wwtp///eesmiisiiiooooooooooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new 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
/ //niss.ccppullc//guus http://////iie/////eeububiiiiiii
for more details.
The authors should provide instructions on 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.
25

---

At submission time, to 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 is 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: The paper has provided the main hyperparameters for the evaluation test, such as the prior for the ERGM, and the specifications for generating the synthetic datasets. More nuanced details have been included in the code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or 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:
We provided 95% conficence internvals for of the main results the paper.
Guidelines:
The answer NA means that the paper does 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 error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall
run 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).
It should be clear whether the error bar is the standard deviation 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 or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or 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: We have provided our cloud providers for all the APIs used in this paper in Appendix.
26

---

Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well 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 make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We have strictly conformed to the NeurIPS Code of Ethics
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We have a section for this.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.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.
The conference expects that many papers will be foundational research and not tied to 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 that 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 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
27

---

Answer:
[NA]
Justification:
We believe that this paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no 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 require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We have properly cited all the dataset being used in this paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.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 datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodll 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 to 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
28

---

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 as details about compensation (if any)?
Answer: [NA]
Justification: This paper is not directly involved with research with human subjects. It is, however, inspired by and adopts some of the results in (referenced) previous paper that involves human subject. All details instructions can be found in that paper.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in 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 in the main paper.
According to the NeurlPS Code of 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: This paper is not directly involved with research with human subjects. It is, however, inspired by and adopts some of the results in (referenced) previous paper that involves human subject. All details instructions can be found in that paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "MWgXFfH3KY", "reviewer": "Reviewer_iUa6", "summary": "This paper studies how well LLM models can recall graph structured information they have been provided with.  While the core of it is a fairly straightforward evaluation of LLM graph recall, it has an interesting experimental design inspired by psychology that adds substantially to the paper.  Some of the graphs used for evaluation come from real networks, which could bias the results (if, for example, an LLM's parametric knowledge had information about the nodes already).", "questions": "One of the biggest questions I have concerns how much parametric knowledge is being used for the \"in-domain\" narrative setting -- Are the node names random (when the \"in-domain Graph Narratives\" are used?) or e.g. are they actual proteins?  (if real protein names, are you assigning the correct name to each node?).  Related work on temporal graph reasoning (Test of Time: A Benchmark for Evaluating LLMs on Temporal Reasoning, https://arxiv.org/pdf/2406.09170) shows a significant effect from \"masking\" node ids.\n\nAny results or discussion in this area would be interesting.", "limitations": "Yes", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "+  interesting questions about recall ability of complex structure, with interesting results\n+  interesting psychology inspired experimental design\n+  nice presentation", "weaknesses": "-  I was left with some questions about disentangling parametric knowledge from recall (see questions below)\n-  The (perhaps well intentioned) sex priming assignment experiment seems out of place with the rest of the work and could raise a yellow flag for some readers.  In its current form, the experiment and discussion adds little scientific value", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review!\n\n**Weakness 1**\n\nPlease see Question 1.   \n\n**Weakness 2**\n\nWe agree with the reviewer and will remove this mini-study or move it to the appendix.  As Section 4.3 explains, this mini-study was inspired by the previous human experiment “Sex and network recall accuracy” (our reference [7]). We included it for a comprehensive evaluation. However, the hypothesis was found to be not statistically significant.\n \n**Question 1**\n\n> Are the node names random (when the \"in-domain Graph Narratives\" are used?) or e.g. are they actual proteins? \n\nFor the in-domain narrative setting, our datasets cover both cases: (1) where parametric knowledge is potentially useful, and (2) where parametric knowledge is less useful:\n\n\n- For protein networks, the protein names are not random. They are unique protein identifiers (known as the “UniProtKB/Swiss-Prot accession number” or NCBI index). Each node is assigned its real name. We also confirmed that LLMs know and precisely understand those protein identifiers. The same is true for DBLP coauthorship networks.\n\n- For all other networks, the node names are generated and randomly assigned. For example, in traffic (geographical) networks, the node names are “bank”, “townhall”, “high school”, etc.\n\n\nTo further disentangle the effect of parametric knowledge and pure graph topology on graph recall, Section 4.1 introduces tests on cross-domain narratives (i.e. node names are randomly assigned from other domains or are plain indices like node 1, node 2, etc.). These tests essentially serve as an ablation study on parametric knowledge.\n\n> Any results or discussion in this area would be interesting.\n\nRegarding results and discussion in this area, we observe the following general trend in our numerical results:\n\n“in-domain narratives with real names ”  $\\approx$ “in-domain narratives with permuted/generated names” > “cross-domain narratives”\n\n\nFor example, see heatmaps in Figure 3 (a) – (c), where the diagonals are the in-domain cases; the off-diagonal cells show the cross-domain ablations.  \n\n\nWe observe that even when the LLM hasn’t seen the graph in training, they do better at recalling when the narrative style hints at the true domain from which the graph is sampled. This corresponds to the “no parametric knowledge” case. (or we might say the parametric knowledge factors in through a very implicit and subtle way, via LLM’s general understandings of the domain)\n\n\nThat said, when the LLM happens to know about the graph to recall, parametric knowledge can certainly help with graph recall. We decided not to fully exclude this case in our test because many real-world graphs do come from domains familiar to LLMs. \n\n\nIf the reviewer is particularly interested in the effect of parametric knowledge in protein networks, we would be happy to provide further experiments in which *real* protein names are *randomly* assigned to nodes. \n\nPlease let us know if we have addressed your concerns. Thank you!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4d92qLvDsl", "reviewer": "Reviewer_uAxF", "summary": "The article discusses the issue of graph recall in large language models (LLMs) and conducts experiments on this topic. It tests the ability of LLMs to recall graphs, identifies factors influencing this ability, and examines the impact of this ability on subsequent tasks.", "questions": "1.Are there other evaluation metrics to measure recall ability? Why can't direct edge prediction be considered a manifestation of recall?\n2.For some nodes with rich text information, could this also be a manifestation of recall ability, potentially affecting prediction results?", "limitations": "1.The article provides limited explanation on how the graph recall ability of LLMs affects downstream tasks, focusing only on link prediction analysis.\n2.Whether large models are sensitive to microstructures when processing graphs needs to be substantiated.", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1.This article is the first to propose the scenario of graph recall. Existing methods do not yield good results for large models on graph tasks, making it difficult to identify the underlying issues.\n2.It introduces an innovative method to verify the ability of graph recall. Using a heuristic approach, it evaluates the model's ability to recall graph structures.\n3.The problem statement and method presentation are clear and well-organized.", "weaknesses": "1.The ability of graph recall should encompass many aspects, not just the recall of different micro structures.\n2.The article mentions that the ability to recall is crucial for LLMs to complete graph tasks. However, the experimental section only examines the relationship between recall ability and link prediction.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review!\n\n**Weakness 1**\n\nWe not only study the recall's microstructures, but also study: \n- the recall's accuracy (as the title suggests, and throughout the paper), \n- its correlation with other prediction tasks such as link prediction (Section 5) and node classification (new experiment, see Weakness 2),\n- its comparison with human behaviors (Section 3.3),\n- the many factors that can potentially affect it (Section 4).\n\n**Question 1**\n> Are there other evaluation metrics to measure recall ability? \n\nPlease see \"Weakness 2 & Limitation 1\" below.\n\n\n> Why can't direct edge prediction be considered a manifestation of recall? \n\nSection 1, paragraphs 2-4 provide the answer. Here we summarize it as follows.\n\nWe agree with the reviewer that edge prediction is related to graph recall, and we’ve conducted correlation studies on this (Section 5).\n\n\nHowever, edge prediction should not be considered as an inherent part of the graph recall task. Graph recall is a very different task from the downstream prediction tasks, including edge prediction, graph prediction, etc.  This is because the correct answer for graph recall always exists in the prompt and can be directly extracted, which is not true for any prediction task. Please see our definition of graph recall task in paragraph 3, which also follows references [8, 33, 24, 11, 41, 7, 21] that experimented with humans.\n\n\nWe've followed the existing definition and focused on graph recall as a standalone task for studying LLMs because:\ngraph recall is both the most straightforward and fundamental step for graph reasoning; as lines 38 - 40 explain, if an LLM can’t even remember what edges it has seen, it is likely to suffer greatly in those downstream graph reasoning tasks. \n\n\nOur experiment indeed shows LLMs suffer at graph recall, which is consistent with LLMs' poor performance at prediction tasks as well as other graph reasoning tasks [46, 34].\n\n\nBesides, the rich literature [8, 33, 24, 11, 41, 7, 21] in human studies also suggests that graph recall, under its current definition, is a scientifically meaningful and important topic to study.\n\nWe have added an experiment on the correlation between graph recall and a node classification. Please see Figure 1 in our uploaded pdf.\n\n\n**Weakness 2 & Limitation 1**\n\n\nWe have added a new experiment on the correlation between graph recall and node classification, please see Figure 1 in our uploaded pdf for more details. Our new experiment again shows that there exists positive correlation (r>0) between performance in graph recall and in node classification task, though the correlation is relatively less stronger. This is mainly due to the larger difference between the nature of the two tasks (graph recall and node classification). \n\n>The article mentions that the ability to recall is crucial for LLMs to complete graph tasks. However, the experimental section only examines ...\n\nThis argument is based on the simple reasoning that graph recall is among the most straightforward and fundamental steps for graph reasoning:  If an LLM can’t even remember what edges it has seen, it is very likely to suffer in downstream graph reasoning tasks (note that this trend can also be empricially observed from plots in both correlation studies just discussed). Therefore, we need to understand LLM's graph recall first, before proceeding to downstream tasks. \n\n\nBesides, since LLM’s graph recall has never been studied, “relationship with downstream tasks” is only one of the many aspects of this topic that we need to examine (other aspects include accuracy, biased microstructures, comparison with humans, and factors that can affect it).\n\n\n\n\n**Question 2**\n\n\nWe are not certain about the reviewer's definition of “rich text information”, so we have the following discussion.\n\n\n- If the reviewer considers semantic information of nodes as “rich text information”, then most of the nodes in our dataset are already described with concrete semantic meanings (Appendix D). In terms of results, which have been extensively discussed in Section 4.1, we've shown that different semantics in narration (i.e., what we call “narrative styles”) have interesting effects on recall accuracy. \n\n\n- If the reviewer has a different definition of “rich text information” (e.g., every node needs to have a feature vector or be associated with a long document), please let us know. We would be happy to discuss this further and/or provide more experiments.\n\n\n**Limitation 2**\n\n\nWe are not certain about the exact meaning of LLMs being “sensitive to microstructures” as raised by the reviewer. Here are our answers based on two possible interpretations: \n- *Interpretation 1: “LLM’s graph recall performance is affected by microstructures of the input graph”.* We have not made such a claim in our paper, which is why it has not been “substantiated”. Here is further discussion: we conjecture this to be true because if we look at the microstructures of graph samples from different datasets (Figure 5 - 8 in Appendix), we can see that they have great variations. It does seem that either having too many cliques (e.g. the protein dataset) or too many spurious edges (or random graph dataset) can lead to low performance. We would be happy to provide more experiments if the reviewer is referring to this interpretation.\n- *Interpretation 2: “LLM’s recalled graphs have variations in microstructures”.* This is exactly one of the main themes which has been discussed throughout Section 3, with rigorous test procedures and numerical results that are statistically significant. If the reviewer could kindly let us know which particular statement needs to be substantiated, we would be happy to provide more discussion and/or experiment.\n\nPlease let us know if we have addressed your concerns. Thank you!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "33MpmdFVyo", "reviewer": "Reviewer_QYAY", "summary": "This paper conducts a comprehensive evaluation of LLMs' capability to recall graph (sub)structures when using natural languages as the interface. Through extensive experiments on diverse graphs from different domains, it points out interesting phenomena like LLMs' underperformance in graph recall tasks. It sheds light on novel insights and inspires further research in relevant fields.", "questions": "1. Will the conclusions be consistent when we use a multi-modal LLMs and using tokens encoded by graph models like GNNs?\n2. How will the conclusion change when we vary the size of the graphs?\n3. How to calculate the bias score in Table 1?\n4. May you provide more explanations for some phenomena, like one in line 327?\n5. There's one recent paper [1] which provides theoretical analysis on transformer's reasoning capability on graphs. They relate transformer's capabilities on graph reasoning to the computational complexity of related tasks. In this case, I think graph recalling (edge level) is also a retrival task, and it would be interestring to discuss the relationships between findings in these two papers. \n\n[1] Sanford, C., Fatemi, B., Hall, E., Tsitsulin, A., Kazemi, S.M., Halcrow, J., Perozzi, B., & Mirrokni, V.S. (2024). Understanding Transformer Reasoning Capabilities via Graph Algorithms. ArXiv, abs/2405.18512.", "limitations": "Authors have dicussed the limitations and potential social impacts.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. This paper is well-written and well-motivated. The idea of integrating computational social science and LLMs, especially comparing the behavior of both LLMs and human beings, is interesting.\n2. This paper tackles an important problem. Despite various papers on evaluating the effectiveness of LLMs' reasoning capability for graphs, few evaluate the first step, such as LLMs' capability to accurately memorize graph structures. This paper strengthens this point and makes a valuable contribution. In section 5, the authors also show that LLMs' capability on structure-related tasks is highly correlated to their capability to recall substructures.\n3. The evaluation is well-designed, with support from social science.\n4. Code implementation is provided, ensuring the reproducibility of experiments.\n5. Several potential directions are provided to inspire future research.", "weaknesses": "1. This paper primarily studies the case where natural language is used as the interface to represent graphs. However, many recent works [1, 2] demonstrate that using a graph encoder and multi-modal projector may be a better choice to inject graph-related knowledge into LLMs. I wonder whether we would arrive at different conclusions when using such graph language models.\n\n2. The authors focus on the case with k=5 (line 101) in this paper, which somewhat limits the generalizability of the conclusions. I think LLMs' recalling capability may also be closely related to the length of inputs. As a result, those LLMs designed with long-context capabilities may perform better for larger graphs. Moreover, larger graphs may present more complicated substructure patterns and lead to somewhat different results.\n\n3. I cannot find the formulas used to obtain the results for Table 1.\n\n4. Some phenomena in this paper do not have corresponding explanations (line 327).\n\n[1] Perozzi, B., Fatemi, B., Zelle, D., Tsitsulin, A., Kazemi, M., Al-Rfou, R., & Halcrow, J. (2024). Let Your Graph Do the Talking: Encoding Structured Data for LLMs. ArXiv, abs/2402.05862.\n\n[2] Chen, R., Zhao, T., Jaiswal, A., Shah, N., & Wang, Z. (2024). LLaGA: Large Language and Graph Assistant. ArXiv, abs/2402.08170.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review!\n\n**Question 1**\n\nWe believe the conclusions will be relatively close to those of our results obtained when using domain-free narrative style to describe the graph (i.e. naming nodes as \"node 1\", \"node 2\", etc.).  Our work has used this narrative style to test “Erdos-Renyi” graphs in Table 1, and to test topology structures extracted from other graph datasets in Figure 3 (a) – (c) “random” columns.\n\n\nThis is because the graph encoder [1,2] projects all nodes/edges to the same token space of LLMs, while leaving out all domain-relevant information. This is similar to, though not exactly the same as, one of our settings where the narrative style is domain-free, in which case the node tokens are simply extracted by dictionary lookup.\n\n\nThis work still makes meaningful contributions in this context, for two reasons: \n\n- In terms of the proposed graph recall task and evaluation pipeline, they can be directly used to evaluate the “LLM+graph encoder” type of models. In fact, they are model-agnostic. \n\n- The conclusions derived, in addition to the transferability we discussed in the first paragraph, also inform the many use cases where LLMs are used to process relational data that haven’t been (or can’t be) encoded by a graph encoder. “LLM + graph encoder” is certainly an important architectural innovation and could be increasingly popular in graph-based RAG, where an explicit graph structure has to be ready in place as part of the prompt.\n\n**Question 2**\n\nPlease see Figure 2, 3 in the new pdf uploaded. We group the tested graphs by the number of nodes they have, into three intervals: [5, 10), [10, 20), and [20, 30]. We then report accuracy (Figure 2) and bias scores (Figure 3) for graphs in each of the three groups. These two figures essentially provide more fine-grained results for Table 1 in our paper. We observe:\n\n- In terms of accuracy, we can see that larger graphs indeed have worse recall accuracy. \n- In terms of bias scores for microstructures, the strongest trend exists with \"edge\" patter, showing that LLMs forget significantly more edges for larger graphs. For other patters, we do not observe a strong consistent trend.\n\n**Question 3**\n\nPlease refer to Section 2.1 for this. Briefly speaking, we fit a random graph model (ERGM) to the recalled graph output by LLMs. The model parameters ($\\theta$) have the physical meaning of being the bias scores.\n\n\n**Question 4**\n\nYes. Line 327 is explained by lines 328 - 332. Below are our further explanations.\n\n\nWe observe that (1) LLMs tend to hallucinate triangles and “Alt-2-Paths” (i.e., the 5th pattern in Figure 2 Step 6) in both graph recall and link prediction tasks; (2) LLMs tend to hallucinate “Alt-Triangles” (i.e., the 4th pattern) in link prediction task, while forgetting this pattern in graph recall task. \n\n\nThese indicate that LLMs do not always exhibit consistent biases between graph recall and link prediction: on some patterns, the bias across the two tasks is consistent; on other patterns, the bias across the two tasks can be opposite to each other.\n\n\nWe also found this observation interesting or even counterintuitive to some extent, and that’s why we mentioned that we do not have a perfect explanation yet: because of triadic closure in link prediction, we had expected LLMs to favor less “Alt-Triangles” in link prediction. Our observation is the opposite, however. We had conjectured that the increase in “Alt-Triangles” might come from more spurious edges that get hallucinated but not from triadic closure over existing dense structures. \n\n\n\n\n\n**Question 5**\n\n\nBelow please find our discussions of this interesting latest work (even though it came out after the submission deadline). We will also substantiate them further in our final version.\n\n\n[1]’s theory indicates that graph recall, as a fundamental graph reasoning task, should be solvable by a dedicated \"small\" transformer-based LLM. Meanwhile, our work shows through rigorous empirical tests that the general-purpose transformer-based LLMs achieve a performance much lower than the theoretical upper bound. Therefore, there exist huge opportunities for improvement. More concretely:\n\n- Theoretically, our proposed task of graph recall is indeed a graph retrieval task, which belongs to the simplest “D1” complexity class of problems for transformers. In other words, it is theoretically solvable by a “small” transformer (single-layer single-headed transformer with embedding dimension O(log N) where N is the length of the input node/edges sequence). This is consistent with our statement that graph recall is one of the simplest and most fundamental problems in graph reasoning. \n- Empirically, [1] shows in its Table 4 that there still exists a huge gap between the best empirical performance and theoretical upper bound. For example, even fine-tuned Palm has an accuracy of computing node degree < 0.7 most of the time. This suggests that there is still huge room and opportunities to improve LLM’s graph recall performance, and that it may not be necessary to switch to new architectures beyond transformers.\n\nPlease let us know if we have addressed your concerns. Thank you!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear Reviewers,

We deeply appreciate your reviews. New experimental results have been provided in the attached pdf to this post. Our response to each reviewer has been posted separately. 

We very much look forward to further interacting with you in the discussion period.

Warm regards,

Authors of Submission 4790

Meta-review: This paper studies the recall of micro-structures by various LLMs. While the approach is unorthodox for the NeurIPS community; I am positive that the paper will generate interesting discussion at the conference. I also note the positive change in the score by all 3 of the reviewers; it seems that most of the concerns are addressed in the rebuttal.
Decision: Accept (poster)