Theoretical Foundations of Graph Neural Networks | Petar Veličković @DeepMind
Deriving graph neural networks (GNNs) from first principles, motivating their use and explaining how they have emerged along several related research lines. Computer Laboratory Wednesday Seminar, 17 February 2021 Recent years have seen a surge in research on graph representation learning, including techniques for deep graph embeddings, generalizations of CNNs to graph-structured data, and neural message-passing approaches. These advances in graph neural networks (GNNs) and related techniques have led to new state-of-the-art results in numerous domains: chemical synthesis, vehicle routing, 3D-vision, recommender systems, question answering, continuous control, self-driving and social network analysis. Accordingly, GNNs regularly top the charts on fastest-growing trends and workshops at virtually all top machine learning conferences. But, what even is a GNN ? Quick online searching reveals many different definitions. These definitions may drastically differ (or even use entirely different terminology) depending on the background that the writer is assuming. And this is no coincidence: the concepts that we now attribute to graph neural networks have independently emerged over the past decade(s) from a variety of machine learning directions. In this talk, I will attempt to provide a “bird’s eye” view on GNNs. Following a quick motivation on the utility of graph representation learning, I will derive GNNs from first principles of permutation invariance and equivariance. Through this lens, I will then describe how researchers from various fields (graph embeddings, graph signal processing, probabilistic graphical models, and graph isomorphism testing) arrived—-independently—-at essentially the same concept of a GNN . The talk will be geared towards a generic computer science audience, though some basic knowledge of machine learning with neural networks will be useful. I also hope that seasoned GNN practitioners may benefit from the categorisation I will present. The content is inspired by the work of Will Hamilton, as well as my ongoing work on the categorisation of geometric deep learning, alongside Joan Bruna, Michael Bronstein and Taco Cohen.

00:00 Intro 1:10 Graph Neural Networks 6:52 Roadmap 31:23 Spectral GNNs 41:17 Probabilistic Graphical Models 45:09 Graph Isomorphism Testing 52:22 Conclusion and Discussion