Events

Upper bounding Graph Neural Networks made easy
07/Sep

RESUME

Graph neural networks (GNNs) provide a mechanism to bridge the discrete world of graphs to the continuous world of vectors in which machine learning methods typically operate. GNNs achieve this by computing vector representations of vertices and graphs, and are often specified as computations over adjacency matrices and feature vectors, interleaved with non-linear activation functions. There has been a recent interest in determining the distinguishing power of GNNs. That is, when can two vertices or graphs be distinguished by means of their vector representations computed by GNNs. Understanding the distinguishing power helps understanding the limitations of GNNs. In the machine learning community, for simple GNNs, connections to the classical Weisfeiler-Leman (WL) graph isomorphism test have recently been made. For more complex GNNs, higher-dimensional versions of the WL test are needed. Orthogonally, in the database theory community, similar connections are made in the study of the expressive power of matrix query languages.

In this talk, we argue that by viewing GNNs as queries in a matrix query language, and by analyzing the corresponding queries, bounds on the distinguishing power of the GNNs in terms the WL-tests, naturally arise. As such, a uniform (and simple) way to assess the distinguishing power of a variety of GNNs is obtained.

SPEAKER:

FLORIS GEERTS, University of Antwerp

Floris Geerts holds a research professor position at the University of Antwerp, Belgium. Before that, he held a senior research fellow position in the database group at the University of Edinburgh, and a postdoc position in the data mining group at the University of Helsinki. He received his PhD in 2001 at the University of Hasselt, Belgium. His research interests include the theory and practice of databases, the study of data quality, and more recently, the interaction between linear algebra and relational databases, and graph neural networks. He is co-author of the book “Foundations of Data Quality” published by Morgan and Claypool, received several best paper awards and was recipient of the 2015 Alberto O. Mendelzon Test of Time Award. He is was associate editor of ACM TODS and IEEE TKDE, was general chair of EDBT/ICDT 2015, PODS PC chair in 2017 and will be chairing ICDT 2023.

WHEN AND WHERE

WEDNESDAY SEPTEMBER 08TH, 15:00 – 16:00 (Santiago, Chile)