Microstructures and Accuracy of Graph Recall by Large Language Models

Authors: yanbang  wang
hejie  cui
jon  kleinberg
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-11 22:41:49

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.

Main paper: 
 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, to accurately answer questions pertaining to the characters in a story, it is crucial for an LLM to be able to recognize and analyze the social network of relations among these characters. In fact, graph-structured information is ubiquitous across many language-based applications, such as structured commonsense reasoning [32] , multi-agent communications [3] , multi-hop question answering [15] , and more. LLMs' graph reasoning ability has thus become an active research topic.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 [48, 20, 18] , to more challenging ones such as node/graph classification [14, 38] and link-based recommendations [55] . Sec. 7 provides a 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 LLMs -to recall and encode a set of relations described in earlier text. In this paper, we consider a graph recall task which has been extensively studied in cognitive science [8, 44, 7, 9, 41] , and which formalizes this basic goal, illustrated in Figure 1 : a set of pairwise relationships is described in a simple narrative form to 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 a graph.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 errors may propagate to (or even serve as the basis for) the behavior of LLMs in these more complex graph tasks. Therefore, we consider it important to investigate LLMs' graph recall ability, a 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.Figure 1 : Graph recall is a simple task but also a crucial pivot for other graph reasoning 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 substantial human experiments that, when memorizing a social network, humans extensively employ certain compression heuristics, such as triadic closure, near-clique completion, and certain degree biases [8, 35] , due to natural limits on cognitive capacity. Further studies show that a person's ability to accurately recall a social network, along with the microstructures (local subgraph patterns, or network motifs [2, 34] ) in their recalled network, not only has profound influence on their social decisions [25, 11, 52] , but also varies on different styles of graph narrative [44] , and the sex of the person [7, 22] . Do LLMs use similar compression heuristics as humans, and how are they affected by different working contexts? As LLMs become increasingly integrated into various social applications, it becomes crucial to understand LLM's behaviors and their associations with human behaviors in these regards.The human cognition studies not only motivate our study, but also establish a scientific foundation for our experimental designs. Similar to [42] which uses political orientation tests designed for humans to assess LLM's political bias, we also find some of the protocols employed by [8] for testing human's graph recall highly instructional, including: (1) memory clearance, where a classical word span test [17] 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 probabilistic generalization to the network motif methods in graph mining; (3) focusing on the probability of the tokens in subject'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 graph reasoning abilities, drawing its connection with the existing cognitive studies on human's graph recall ability. 2. We are the first to design and conduct systematical studies on the accuracy and biased microstructures 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 our understandings about LLM's graph reasoning ability. 
exponential random graph model (ergm): 
 We use the Exponential Random Graph Model (ERGM) [39] to characterize the statistical significance of the various microstructural patterns ("network motifs" [2, 34] ) in the recalled graphs. ERGM is a special case of the exponential family dedicated for modeling graph-structured data.Formally, let G be the probability space of all possible graphs over n nodes, and G = (V, E, f ) ∈ G be a random (graph) variable, where V is the set of nodes, E is the set of edges in G, and f : E → [0, 1] is a edge probability function. Assuming independence between edges, the probability of G can be written as:EQUATIONA is a list of k predefined microstructural patterns in G. Fig. 2's Step 6 shows k = 5 such patterns that we primarily investigate in this work, following [8] . The conditional probability of observing G given the parameter vector θ of length k is defined to beEQUATIONwhere s(G) is the sufficient statistics of G, and each s i (G) is a count of the number of occurrences of A[i] in G; c θ is the normalizing constant that only depends on θ. We assume an uninformative prior for θ ∼ [-10, 10]. The posterior P (θ|G) can then be optimized via MAP under Bayesian framework. θ measures the strength of presence of the k microstructural patterns we care about. A large θ i means a strong presence of pattern A[i] in G.The word span test [17] is a standard method for measuring a human'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 a given size. See Appendix B.2.1 for the sentence sets we used. Many cognition studies [8, 7, 6, 5] have adopted this test in their experiment to (1) serve as a chat buffer or spoiler that simulates the delayed query in real-world applications, and (2) clear the shortterm memory of the subject, which allows researchers to better focus on relatively persistent patterns in memory structures. It is important to note that transformer-based 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 to emphasize the close analogy and behavioral resemblance between LLMs and humans in graph recall. 
microstructures 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.3.1, followed by Sec.3.3 which presents head-tohead comparisons of LLMs and humans under [8] 's framework. Sec.3.2 substantiates the analysis by experiments on more diverse datasets. Our code and data are reported in Appendix A.LLMs Tested: GPT-3.5 [10] , GPT-4 [1] , Gemini-Pro [46] . We also examined Llama 2 (13B) [47] , but they can rarely follow through on our instructions.Our staged protocols are visualized in Fig. 2 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 LLM's intermediate response is always appended to the current thread as additional conservation context, before we proceed to the next stage along the pipeline. 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 [8] 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 response. Here, our vignette encodes the graph structures sampled from a certain application domain using a certain narrative style -see the dataset tab below for details.Step 3: Memory Clearance. A standard word span test [17] is conducted with the LLM. See Sec.2.2 for details. We use the same set of sentences as 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 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 0 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.1 to model both the recalled graph and the ground truth, in order to reveal statistically significant structural patterns, or "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 on the ground-truth graph. Table 1 shows the results of microstructural patterns and performance of LLMs in our graph recall test. We primarily investigate the five microstructural patterns as shown in Fig. 2 . This is because these patterns have been observed to be biased patterns in human studies and are substantiated with rich sociological explanations [8] ; 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/depressing the corresponding microstructural pattern in 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 close in most 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, 18, 20] .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 is relatively robust. For each model, the colors in each column are relatively consistent. This means that an LLM may have have some relatively persistent bias in its microstructual patterns, which does not change significantly across different application domains. This is a positive indicator of the generalizability of our findings above.Brashears et al. reported experimental results of social network recall on a total of 301 humans [8] .Here we report how we build upon this existing result to compare LLMs' and humans' behaviors in the social network recall test.To stay aligned with Brashears' settings, we use their dataset which consists of two 15-node social networks: an irreducible one which contains no cliques, and a reducible one which contains multiple cliques. Appendix B introduces more details. Table 2 shows the comparison results.Regarding the types of bias (forgetting vs. hallucination), LLMs are relatively consistent with humans. Both LLMs and humans tend to forget edges and alt-triangles while "hallucinating" triangles and stars. This interesting finding may reveal that LLMs have some information decoding and recall mechanisms similar to human memory.Regarding the strength of the bias, LLMs tend to have weaker forgetting but stronger hallucinations than humans. On microstructures such as edges and alt-triangles, LLMs tend to have a weaker forgetting pattern, while on some prominently increasing microstructures (e.g., triangles), LLMs tend to 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 to perform complex or critical graph tasks. It is a 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 performance in graph reasoning tasks [48, 14] . Here we focus on 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). 
narrative style: 
 Motivation. The effect of narrative styles on 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.The key idea is the following: it is known that graphs sampled from different domains have different distributions of topology, e.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.3.1. 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. 3 (a) -(c) . Appendix E provides the full table.Result Analysis. The heatmaps of GPT-4 and GPT-3.5 support our conjecture: the diagonals (corresponding to a 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-performing 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 it is an intuitively sensible conjecture that this might help, it is very interesting that this conjecture is borne out so clearly in the results. Gemini-Pro appears more sensitive to small noise in context, while GPT's are more robust. 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 is 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 a 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.3.1.$FF*UDSK5HFDOO $FF/LQN3UHGLFWLRQ )DFHERRNU $FF*UDSK5HFDOO $FF/LQN3UHGLFWLRQ &$5RDGU $FF*UDSK5HFDOO $FF/LQN3UHGLFWLRQ 5HDFWRPHU $FF*UDSK5HFDOO $FF/LQN3UHGLFWLRQ '%/3U $FF*UDSK5HFDOO $FF/LQN3UHGLFWLRQ (UGRV5HQ\LUSince superficial explanations do not seem to 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, it is a plausible mechanism that recall is helped when the 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.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 LLM may not be asked to work on the key data immediately after it receives them. 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 is dropped. Therefore, we vary this number in our experiment and record the performance of each model on each dataset.Result Analysis. The results are shown in Figure 3 (d) -(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 at 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 is 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 on 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 performance 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 an 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 (x) and graph recall accuracy (y) then map these results onto a scatter plot; (2) microstructural correlation: similar to Table 1 and 2, 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.Figure 4 shows the scatter plots for accuracy correlation; Table 3 shows microstructural correlation.LLM's link prediction performance correlates well with its graph recall performance on realworld graphs. This is clear from the scatter plot and the r values. For Erdős-Rényi graphs, the correlation is close to zero, which is unsurprising though because the link prediction on 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 3 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 LLMs 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 PerspectiveWe consider this study as a 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 F further discusses limitations of the work.• The graph recall test is one of the simplest and most fundamental graph reasoning tasks. Since 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-customized" 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 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 retrieval bias could emerge. A potential mitigation strategy worthy of exploration is to consider balancing/compensating 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 a 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-embedding methods [12, 37, 13] .7 Related WorkQuestion: Does the paper provide open access to the data and code, with sufficient instructions 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. • 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) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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 a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
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. [40] noticed that people forget a significant portion of their social networks, so they built a to predict missing links from recall. [9] 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 as triangles or cliques.Following the previous works, [8] establishes experimental protocols for examining the performance and microstructural patterns of human'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 a 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 a 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 human-readable corpus, many ideas and findings on human's graph recall are instructional to our exploration of LLM's graph reasoning ability. Further studies show that a person's ability to accurately recall a social network has profound influence on their social decisions [25, 11, 52, 53, 54] .The graph recall test is a meaningful test for both humans and LLMs, though their experiment outcomes may need to be interpreted in a subtly different way. The graph recall test is 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 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).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 or elaboration [4] . There has also been work on developing general graph models to handle various graph tasks with a unified framework [30] . More recently, [43] provides theoretical analysis on the limit of transformer's reasoning capability on graphs, by relating transformer'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 a 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.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: We provided 95% conficence internvals for all of the main results in the paper.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at 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, or 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 or the standard error of the mean. • It 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 a 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 of range (e.g. negative error rates). • If error bars are 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. 
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 of 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, 57] . Another direction is to study how to improve LLM's graph recall by prompting or other methods. "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.""I 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 a job in Washington, analyzing weapons expenditures for the U.S. Navy."Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: We have provided our cloud providers for all the APIs used in this paper in Appendix.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 of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). • 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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal 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 or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 a (referenced) previous paper that involves human subject. All details of instructions can be found in that paper. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main 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. 
 
 Appendix: We provide a full comparison of the true graph and the recall graph from different LLMs. The results are shown in Table 4 , Table 5 , and Table 6 , respectively. 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 in the corpus on which LLMs are trained, and therefore wonder whether LLMs perform better at graph recall when asked to play the role of a female.Procedures. Aligned with [7] 's design, we include at the beginning of the test (i.e. prior to all steps) a sex prime, which is a 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 as having any pre-given sex. Instead, we send role-playing instructions to LLMs by stating their "sex" in 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.Result Analysis. The results are shown in Fig. 9 (g) -(i). The error bars are 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 on humans. In fact, LLMs underperform in both roles when compared with the control group, i.e. cross-referencing Table 1 "Accuracy" column.Figure 9 : Different factors that influence LLM's graph recall. (g) -(i): sex. Following [7] 's procedures, we test and find that the effect of sex roles that an LLM is asked to play is insignificant on their capability of graph recall -a result different from that on humans.The full performance comparison of different narrative styles on five datasets for each LLM is present in Table 7 . 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 a limited number of graph samples from each domain. Also, while we have experimented with several main-stream 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 1 ) 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 in 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 in [18] for measuring LLM's graph reasoning ability. Both our graph recall test and the edge existence task require the LLM to 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's 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 are different. Our paper uses a 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 not reported [18] .• 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make 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 to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.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.38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


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

Reviews: review: paper_summary: paper_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).
strength_weakness: strength_weakness: -  I was left with some questions about disentangling parametric knowledge from recall (see questions below)
-  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
questions: 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.

Any results or discussion in this area would be interesting.
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 1.The ability of graph recall should encompass many aspects, not just the recall of different micro structures.
2.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.
questions: questions: 1.Are there other evaluation metrics to measure recall ability? Why can't direct edge prediction be considered a manifestation of recall?
2.For some nodes with rich text information, could this also be a manifestation of recall ability, potentially affecting prediction results?
limitations: limitations: 1.The article provides limited explanation on how the graph recall ability of LLMs affects downstream tasks, focusing only on link prediction analysis.
2.Whether large models are sensitive to microstructures when processing graphs needs to be substantiated.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

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

3. I cannot find the formulas used to obtain the results for Table 1.

4. Some phenomena in this paper do not have corresponding explanations (line 327).

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

[2] Chen, R., Zhao, T., Jaiswal, A., Shah, N., & Wang, Z. (2024). LLaGA: Large Language and Graph Assistant. ArXiv, abs/2402.08170.
questions: questions: 1. Will the conclusions be consistent when we use a multi-modal LLMs and using tokens encoded by graph models like GNNs?
2. How will the conclusion change when we vary the size of the graphs?
3. How to calculate the bias score in Table 1?
4. May you provide more explanations for some phenomena, like one in line 327?
5. 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. 

[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: limitations: Authors have dicussed the limitations and potential social impacts.

Comments: comment: Dear Reviewers and Meta Reviewer,

Towards the end of the discussion period, we would like to sincerely thank you again for your reviews and discussion. We are glad to know that we have addressed concerns of the reviewers, who have all raised their scores. We will also update our final version to reflect all clarifications and suggested improvements.

Warm regards,

Authors of Submission 4790
Thank you for raising the score. We are glad to know that we have addressed your concerns.
Thank you for raising the score. We are glad that your concerns have been addressed. 

We will follow your advice to add the interesting experiment to appendix. Regarding the latest theoretical results, please see our response to Reviewer QYAY in Question 5. We will also include this in our final version.
Thanks to to the authors for their reply, I have raised my score.

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

This would be an interesting experiment to add to the appendix if it isn't too costly to run.

-  An additional thought while re-reading this paper -- recent theoretical results ("Understanding Transformer Reasoning Capabilities via Graph Algorithms", Sanford et al) categorize recall (in particular, edge recall iirc) as one of the simplest operations (it doesn't require a very "large" transformer network to perform it).  Any thoughts about how your results connect to this kind of theoretical framework would be insightful.
Thanks for your rebuttal which has addressed some of my concerns, and thus I would like to raise the original score to reflect it.
Dear Reviewer,

Please let us know if you have any further questions or concerns. Thank you very much for your time and consideration.

Warm regards,

Authors of Submission 4790
Dear Reviewer,

Please let us know if you have any further questions or concerns. Thank you very much for your time and consideration.

Warm regards,

Authors of Submission 4790
Thank you. We are glad that your concerns have been addressed.
Thanks for your response, which address my concerns. I have raised my score.