LAB42 Talk | FOAM: Michael Benedikt - Logic and asymptotic combinatorics of Graph Neural Networks
Join us in this FOAM seminar from Michael Benedikt (University of Oxford).
Logic and asymptotic combinatorics of Graph Neural Networks
Graph neural networks (GNNs) are the predominant architectures for a variety of learning tasks on graphs. We present a new angle on the expressive power of GNNs by studying how the predictions of a GNN probabilistic classifier evolve as we apply the classifier on larger graphs drawn from some random graph model. We show that the output converges asymptotically almost surely to a constant function, which upper-bounds what these classifiers can express uniformly.
Our convergence results are framed within a query language with aggregates, subsuming a very wide class of GNNs, including state of the art models, with aggregates including mean and the attention-based mechanism of graph transformers. The results apply to a broad class of random graph models, but in the talk we will focus on Erdős-Rényi model and the stochastic block model. The query language-based approach allows our results to be situated within the long line of research on convergence laws for logic.
The talk will include joint work with Sam Adam-Day, Ismail Ceylan, and Ben Finkeshtein – see https://arxiv.org/abs/2403.038..., and also joint work with Sam Adam-Day and Alberto Larrauri.
FOAM seminars
The FOAM Seminar, organised by computer scientists at the ILLC, features research on questions of a fundamental nature in computer science and AI, in research areas such as algorithms, optimisation, data management, planning, knowledge representation, and multiagent systems. Talks are intended to be broadly accessible and pitched at the level you might find at a plenary talk of a relevant conference (such as IJCAI, AAAI, KR, ICAPS, AAMAS, EC, PODS, LICS, STOC, FOCS, and SODA).
FOAM usually takes place on a Friday at 15:00. Talks are roughly 45 minutes long, followed by a brief discussion. Afterwards, you are invited to stay for a chat and a drink. Everyone is welcome to attend!