Timezone: »

 
Poster
Universal Invariant and Equivariant Graph Neural Networks
Nicolas Keriven · Gabriel Peyré

Tue Dec 10 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #218
in Theory -- Hardness of Learning and Approximations »

Graph Neural Networks (GNN) come in many flavors, but should always be either invariant (permutation of the nodes of the input graph does not affect the output) or \emph{equivariant} (permutation of the input permutes the output). In this paper, we consider a specific class of invariant and equivariant networks, for which we prove new universality theorems. More precisely, we consider networks with a single hidden layer, obtained by summing channels formed by applying an equivariant linear operator, a pointwise non-linearity, and either an invariant or equivariant linear output layer. Recently, Maron et al. (2019) showed that by allowing higher-order tensorization inside the network, universal invariant GNNs can be obtained. As a first contribution, we propose an alternative proof of this result, which relies on the Stone-Weierstrass theorem for algebra of real-valued functions. Our main contribution is then an extension of this result to the \emph{equivariant} case, which appears in many practical applications but has been less studied from a theoretical point of view. The proof relies on a new generalized Stone-Weierstrass theorem for algebra of equivariant functions, which is of independent interest. Additionally, unlike many previous works that consider a fixed number of nodes, our results show that a GNN defined by a single set of parameters can approximate uniformly well a function defined on graphs of varying size.

Keywords: Hardness of Learning and Approximations · CNN Architectures · Theory · Deep Learning
[ Paper]  [ Slides] 

Author Information

Nicolas Keriven (Ecole Normale Supérieure)
Gabriel Peyré (CNRS and ENS)

More from the Same Authors