Title
Graph neural networks: asymptotics and unbounded expressivity
Abstract
Learning with graph and network data is an area in machine learning that has seen explosive growth in recent years. This growth is fueled by an increasing amount of graph structured data (generated, e.g., by social, sensor, traffic networks) on the one hand, and the success of graph neural networks (GNNs) for graph related prediction tasks on the other hand.
Key theoretical questions for statistical graph models are their expressivity, and their asymptotic behavior. The expressivity of different classes of GNNs has been investigated in some detail, while asymptotics has received much less attention. In this talk I will review existing results and report on ongoing work investigating GNN expressivity and convergence properties. My focus is on strictly ubounded expressivity, i.e., the question whether a GNN can produce separate representations for two distinct infinite sets of input graphs. I will discuss how such unbounded expressivity properties are related to convergence properties, and how high expressivity and robust domain size generalization are conflicting objectives. Concretely, we will investigate the impact that the choice of aggregation and activation functions defining specific classes of GNNs has on the resulting convergence/expressivity tradeoff.
Bio
Manfred Jaeger studied mathematics in Freiburg, Germany, where he obtained his diploma in mathematics in 1991. He subsequently went to the Max-Planck-Institute for Computer Science in Saarbrucken, where he obtained a PhD in Computer Science from Saarland University in 1995. From 1996-2003 he continued as research associate at the Max-Planck-Institute for Computer Science, and in that period also spent time as postdoctoral researcher at Stanford University, the University of Helsinki, and Freiburg University. In 2002 he obtained the Habilitation in computer science from Saarland University. Since 2003 he is associate professor at the Computer Science department at Aalborg University, Denmark. Since 2024 he also is a visiting professor at Trento University, Italy.
Manfred Jaeger has served as associate editor for the Journal of Artificial Intelligence Research and the Artificial Intelligence Journal. He is currently a member of the editorial board of Machine Learning.
Speaker is presenting in person from Tromsø.
Practical
The Tuesday Seminar Series covers a range of topics relevant to Integreat’s research focus. Presenters from within and beyond the Integreat community give 40-minute presentations, followed by group discussions.
Seminars are open.
For those unable to attend in person: https://uio.zoom.us/j/65632027408
Point of contacts:
- Organiser and moderator: Veronica Lachi, University of Tromsø
- Integreat Administrative Leader Maria Dikova, University of Oslo