Graph Reasoning in Large Language Models

Abstract:
Large language models (LLMs) have demonstrated impressive capabilities in text generation, but their ability to reason over complex data remains an area of ongoing research. In this talk, we present three distinct approaches to improve LLM reasoning over complex structures. First, we leverage graph algorithms to analyze and understand the reasoning capabilities of transformer models. Our results establish a representational hierarchy, revealing the necessary Transformer capacity (number of layers, embedding dimension size) for solving different classes of reasoning tasks. Next, we exploit the topology of temporal reasoning to generate novel synthetic problem instances. This allows for a more robust evaluation of LLM reasoning capabilities. Finally, we introduce a method for improving in-context representations of structured data for pretrained LLMs, facilitating more effective reasoning over complex information.

Bio: 

Bryan Perozzi is a Research Scientist in Google Research’s Algorithms and Optimization group, whose research focuses on learning expressive representations of graph data with neural networks.  Bryan is an author of 40+ peer-reviewed papers at leading conferences in machine learning and data mining (such as NeurIPS, ICML, ICLR, KDD, and WWW).   He's the author of popular models in graph representation learning such as DeepWalk (random walk node embeddings),  MixHops (graph neural networks) and more.  Bryan's current research focuses on the intersection of structured data and generative AI, where he's teaching large language models to 'Talk Like a Graph'.  

Bryan was awarded the ACM SIGKDD 2024 Test of Time Award for his work in advancing neural network representations for graph data in "DeepWalk: Online Learning of Social Representations", and his doctoral thesis won the prestigious ACM SIGKDD Dissertation Award (2017).  Bryan received his Ph.D. in Computer Science from Stony Brook University, where he was advised by Steven Skiena. Prior to that he obtained a M.S. in Computer Science from The Johns Hopkins University and a B.S. in Computer Engineering from Virginia Tech.