Date: 12 June 2024
Time: 12.45 Hours
Room: RA1501 & online
Speaker: Dr. Gaurav Rattan
Title: "Learning on Graphs with Message-Passing"
Abstract:
Graph Neural Networks (GNNs) are deep learning models for graph-structured data, generalizing Convolutional Neural Networks (CNNs) in image-processing. Typically GNNs operate on graphs via a message-passing mechanism, i.e. they carry out local computations on the vertices of a graph, aka graph convolutions, and then aggregate these computations to compute a global learnable represenation for the graph. From a practical perspective, GNNs have found widespread application in several domains, ranging from drug discovery and physics simulation to knowledge databases and computer vision.
However, the mathematical principles underlying GNNs are fairly elusive, mainly due to the complex nature of graph-structured data. In this talk, we describe a powerful mathematical framework for studying message-passing mechanisms on graphs. Consequently, we derive a precise characterization of the ability of GNNs to model functions on graphs, that is, their expressive power. Our framework uses classical tools from graph theory and graph algorithms, in particular, highlighting the role of graph symmetries. We also uncover deeper connections between message-passing and subgraph statistics: This leads to several interesting consequences for GNNs via the deep theory of graph limits enunciated by Lovasz and others.