Time: 10:00, Monday, 11 Nov 2024
Place: AI4LIFE, Room 618, Tạ Quang Bửu Library, HUST
Presenter: Prof. Michael Benedikt, Đại học Oxford
Bio:
Michael Benedikt is a professor at Oxford University’s computer science department, and a fellow of University College Oxford.
He has held previous positions in industry at Bell Laboratories and at Yahoo! Research.
He has worked extensively in AI, computational logic, verification, and data management. He has served as program chair of the two main database theory conferences, Principles of Database Systems and International Conference on Database Theory, and has served as vice chair and co-chair for conferences and workshops on databases and the Web. His current work focuses on the interaction between machine learning, data management, and reasoning.
Title: What you can and cannot do (usually) on Graph Neural Networks.
Abstract:
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 a strong limit on what GNNs based on averaging can express on “typical’’ graphs: the output converges asymptotically almost surely to a constant function.
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. Our query language-based approach allows our results to be situated within the long line of research on probabilistic analysis of declarative languages.
The talk will include joint work with Sam Adam-Day, Ismail Ceylan, and Ben Finkelshtein, to be presented at NeurIPS 2024– see https://arxiv.org/abs/2403.03880, It will also include ongoing joint work with Sam Adam-Day and Alberto Larrauri.