Theoretical Foundations of Efficient and Scalable Graph Learning

Overview

Graph neural networks (GNNs) have achieved remarkable empirical success in processing and representing graph-structured data across diverse fields. However, fundamental challenges remain, including limitations in expressive power and model depth. This talk addresses these challenges through rigorous analysis and efficient solutions across three key areas of graph learning. First, we establish that message-passing GNNs and their variants can universally approximate certain critical properties of (mixed-integer) linear programs. Second, we demonstrate that subgraph GNNs exhibit strong expressive power on graphs with bounded cycles. Third, we show that residual connections provably mitigate the oversmoothing issue and enable greater model depth. These results not only advance the theoretical understanding of GNNs but also provide practical insights for real-world applications.