Learning on Edges: A Narrative Review of Graph Neural Networks from Recursive Networks to Geometric Deep Learning

Abstract

Graph neural networks---learning over relational, irregular structure by passing messages between nodes---generalized deep learning's grids to the graph: molecules, social networks, knowledge bases, and the web. This article presents a narrative review of that arc's canonical line: Sperduti and Starita's 1997 structure classification, Gori, Monfardini, and Scarselli's 2005 graph-domain learning, Scarselli and colleagues' 2009 GNN model, Bruna and colleagues' 2014 spectral networks, Defferrard and colleagues' 2016 localized filtering, Kipf and Welling's 2017 graph convolutions, Gilmer and colleagues' 2017 message passing, Hamilton, Ying, and Leskovec's 2017 GraphSAGE, Velickovic and colleagues' 2018 attention, Ying and colleagues' 2019 GNNExplainer, Wu and colleagues' 2021 comprehensive survey, and Bronstein and colleagues' 2021 geometric deep learning. The synthesis is organized around three themes: recursion, in which state propagation over nodes founded learning on graphs; convolution, in which spectral theory and message passing gave the graph a deep architecture; and geometry, in which attention, pooling, explainability, and symmetry made the network general. It is concluded that the GNN is deep learning's relational settlement---convolution's invariance learned from graph geometry rather than grid regularity---and that its message-passing abstraction is one of machine learning's cleanest unifications.