Universal Invariant and Equivariant Graph Neural Networks

By Nicolas Keriven, G. Peyr'e. 2019

334 citations recorded by the source corpus.

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 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 operator. 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 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. Finally, unlike many previous settings 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.

Subfields: Artificial Intelligence, Materials Chemistry, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Materials Chemistry

In Statistical and Nonlinear Physics

Citations in the corpus

Set2Graph: Learning Graphs From Sets (2020, background): “, 2017) are proven equivariant universal (Keriven and Peyré, 2019; Segol and Lipman, 2020; Sannai et al., 2019; Maron et al., 2020).”
Provably Powerful Graph Networks (2019, background): “…any message passing neural network (Gilmer et al., 2017) to an arbitrary precision; Maron et al. (2019b) proved that these models are universal for a very high tensor order of k = ( n 2 ) , which is of little practical value (an alternative proof was recently suggested in Keriven and Peyré (2019)).”
A General Theory of Equivariant CNNs on Homogeneous Spaces (2018, methodology): “A framework for (non-convolutional) networks equivariant to ﬁnite groups was presented by [17], and equivariant set and graph networks are analyzed by [18–21].”
Permutation Invariant Graph Generation via Score-Based Generative Modeling (2020, background): “The message passing operations in a graph neural network are guaranteed to be permutation equivariant (Keriven and Peyré, 2019), as well as edgewise and nodewise operations for graphs.”
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting (2020, background): “Higher-order Invariant Graph Networks (IGNs) have been studied in a series of works [22], [23], [24], [39], [64], [65], establishing connections with the WL hierarchy, similarly to [17], [66].”
Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning (2020, background): “Some works view GNNs as general approximators of invariant functions but the proposed models hold more theoretical implication than practical usage because of their dependence on polynomial ( n ) -order tensors [29,45,46].”
DeeperGCN: All You Need to Train Deeper GCNs (2020, background): “Keriven and Peyré [2019] further extend it to the equivariant case.”
Representation Learning for Dynamic Graphs: A Survey (2019, background): “On the other hand, Maron et al. (2019) and Keriven and Peyré (2019) study how well certain GCN models can approximate any continuous function which is invariant to permutation of its input.”
On the equivalence between graph isomorphism testing and function approximation with GNNs (2019, background): “Such a dependence on the graph size was been theoretically overcame by the very recent work [13], though there is no known upper bound on the order of the tensors involved.”
What graph neural networks cannot learn: depth vs width (2019, background): “This result compliments recent universality results (Maron et al., 2019b; Keriven & Peyr ´ e, 2019) that considered approximation (rather than computability) over speciﬁc classes of functions (invariant and equivariant) and particular architectures.”
Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations (2022, methodology): “…distribution at time t. Note that since the message-passing operations of GNNs and the attention function used in GMH are permutationequivariant (Keriven & Peyré, 2019), the proposed scorebased models are also equivariant, and theryby from the result of Niu et al. (2020), the log-likelihood…”
On Learning Sets of Symmetric Elements (2020, background): “…papers studied the properties of equivariant layers (Ravanbakhsh et al., 2017; Kondor & Trivedi, 2018; Cohen et al., 2019a) and characterized the expressive power of models that use such layers (Yarotsky, 2018; Maron et al., 2019c; Keriven & Peyr´e, 2019; Maehara & NT, 2019; Segol & Lipman, 2019).”
Diffusion Models: A Comprehensive Survey of Methods and Applications (2022, background): “g, permutation, rotational and translational invariance) or equivariance properties [108].”
Probabilistic Symmetries and Invariant Neural Networks (2020, background): “…distributions, and in that sense they are related to the recent literature on universal approximations (as in Cybenko, 1989; Hornik, 1991) of invariant and equivariant functions (e.g., Yarotsky, 2018; Maron et al., 2019; Keriven and Peyré, 2019; Segol and Lipman, 2020; Ravanbakhsh, 2020).”
Can graph neural networks count substructures? (2020, background): “[40] and Keriven and Peyré [29] propose architectures that achieve universal approximation of permutation-invariant functions on graphs, though such models involve tensors with order growing in the size of the graph and are therefore impractical.”