Yeganeh Alimohammadi (University of Southern California)
https://simons.berkeley.edu/talks/yeganeh-alimohammadi-university-southern-california-2025-08-12
Graph Learning Meets Theoretical Computer Science
Scaling graph neural networks (GNNs) is crucial in modern applications. For this purpose, a rich line of sampling‑based approaches (neighborhood, layer‑wise, cluster, and subgraph sampling) has made GNNs practically scalable. In this talk, I will briefly survey these sampling‑based GNN methods and then develop how the local graph‑limit (Benjamini–Schramm) perspective offers a clean, potentially unifying tool for the theoretical understanding of sampling‑based GNNs. Leveraging this perspective, we prove that, under mild assumptions, parameters learned from training GNNs on small, fixed‑size samples of a large input graph are within an $\epsilon$‑neighborhood of those obtained by training the same architecture on the entire graph. We derive bounds on the number of samples, the subgraph size, and the training steps required. Our results offer a principled explanation for the empirical success of training on subgraph samples, aligning with the literature’s notion of transferability. This is based on joint work with Luana Ruiz and Amin Saberi.
