My talk starts by turning back the clock to 1931 and 1981, introducing the ideas that culminated with a fundamental representation theorem of graphs (the Aldous–Hoover theorem). I will then show how these ideas connect to a probabilistic interpretation of matrix factorization methods, explaining why matrix factorization is fundamentally not as expressive as it could be to describe finite graphs. I will then introduce the concept of representation learning with graph neural networks (GNNs) and explain its connections to statistical graph models and the Weisfeiler-Lehman isomorphism test. Finally, I will introduce a newly proposed general framework for graph representation learning using deep neural networks, which is directly rooted in the ideas that gave us the Aldous–Hoover representation theorem. This new representation framework points to novel graph models, new approaches to make existing graph model more scalable, and provides a unifying approach connecting matrix factorization, graph mining algorithms, and graph neural networks. I will end my talk with a few open problems.
This is joint work with Ryan Murphy, Bala Shrinivasan, and Vinayak Rao.