Large Language Models (LLMs) excel at various tasks, from writing poems to generating code. But how well do they handle complex reasoning, especially with graph-structured data, the kind that describes relationships between things? A new research paper, "Revisiting the Graph Reasoning Ability of Large Language Models," challenges the assumption that LLMs can easily tackle graph problems. The researchers tested LLMs like GPT and LLAMA on three core graph tasks: translating between different ways of describing a graph, determining if a path exists between nodes (connectivity), and finding the shortest path. Surprisingly, even the powerful GPT-4 struggled. While LLMs could often perform simple translations, they stumbled when asked to switch between different representations, suggesting they might not truly grasp the underlying structure. In the connectivity task, LLMs fared well on simple connections but faltered as the paths became longer or the graph more complex. The researchers dug deeper and discovered that the way a graph is described significantly impacts LLM performance. For instance, describing a graph as a list of connected nodes works better than listing individual edges. The study also found that LLMs may rely on shortcuts. If a node isn't explicitly mentioned in the graph description, they often assume it's isolated, even if it's part of a larger, unmentioned structure. When it came to finding the shortest path, LLMs again showed weaknesses, particularly with weighted graphs, where each connection has a cost. This suggests they may not correctly process or represent edge weights. Real-world tests with knowledge graphs confirmed these limitations. LLMs struggled more with longer paths and simpler graph descriptions. Interestingly, providing the LLMs with a few examples or hinting at the algorithm helped in some cases but not others. These findings challenge the theoretical understanding of LLM abilities, as some theoretical models predict LLMs should be capable of solving these graph problems. The research concludes that LLMs aren’t yet ready to be standalone graph reasoners. They excel at pattern recognition in text but struggle with the logical steps needed for complex graph analysis. This has big implications for applications that rely on graph reasoning. Future research will explore ways to enhance LLMs’ graph-reasoning abilities, possibly through fine-tuning or incorporating external tools.