SIAM Workshop on Combinatorial Scientific Computing 2020

FEBRUARY 11–13, 2020, SEATTLE, WASHINGTON, U.S.

Invited Talk

Unearthing the Relationship Between Graph Isomorphism, Graph Neural Networks, and Matrix Factorization

Bruno Ribeiro, Purdue University, USA

Slides (18 MB in PDF format)

Graph tasks are ubiquitous, with applications ranging from recommendation systems, to language understanding, to automation with environmental awareness and molecular synthesis. A fundamental challenge in applying machine learning to these tasks has been encoding (representing) the graph structure in a way that machine learning models can easily exploit the relational information in the graph, including node and edge features. Until recently, this encoding has been performed by factor models (a.k.a. graph and node embeddings), which arguably originated in 1904 with Spearman's common factors. Recently, however, graph neural networks have introduced a new powerful way to encode graphs for machine learning models. In my talk, I will describe these two approaches and then introduce a unifying mathematical framework using group theory and causality that connects them. Using this novel framework, I will introduce new practical guidelines to generating and using node embeddings and graph representations, which fixes significant shortcomings of the standard operating procedures used today.

Joint work with Ryan Murphy, Bala Shrinivasan, and Vinayak Rao.