On the Universality of Invariant Networks

By Haggai Maron, Ethan Fetaya, Nimrod Segol, Yaron Lipman. 2019

275 citations recorded by the source corpus.

Constraining linear layers in neural networks to respect symmetry transformations from a group $G$ is a common design principle for invariant networks that has found many applications in machine learning. In this paper, we consider a fundamental question that has received little attention to date: Can these networks approximate any (continuous) invariant function? We tackle the rather general case where $G\leq S_n$ (an arbitrary subgroup of the symmetric group) that acts on $\mathbb{R}^n$ by permuting coordinates. This setting includes several recent popular invariant networks. We present two main results: First, $G$-invariant networks are universal if high-order tensors are allowed. Second, there are groups $G$ for which higher-order tensors are unavoidable for obtaining universality. $G$-invariant networks consisting of only first-order tensors are of special interest due to their practical value. We conclude the paper by proving a necessary condition for the universality of $G$-invariant networks that incorporate only first-order tensors.

Subfields: Artificial Intelligence, Computational Mathematics

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 Computational Mathematics

Citations in the corpus

Set2Graph: Learning Graphs From Sets (2020, methodology): “We denote for an arbitrary tensor A ∈ R a × b ×···× c its inﬁnity norm by For an arbitrary (cid:15) > 0 , there exists an equivariant polynomial This is a standard lemma, similar to (Yarotsky, 2018; Maron et al., 2019c; Segol & Lipman, 2020); for completeness we provide a proof in the supplementary.”
Provably Powerful Graph Networks (2019, methodology): “First, establishing a baseline for expressive GNNs, we prove that the recent k -order invariant GNNs (Maron et al., 2019a,b) offer a natural hierarchy of models that are as expressive as the k -WL tests, for k ≥ 2 .”
A General Theory of Equivariant CNNs on Homogeneous Spaces (2018, methodology): “A framework for (non-convolutional) networks equivariant to finite groups was presented by [17], and equivariant set and graph networks are analyzed by [18–21].”
On Learning Sets of Symmetric Elements (2020, methodology): “…→ R (cid:96) that commutes with all the elements in G , namely: (3) Note that L can be realized as a (cid:96) × (cid:96) matrix (which will be denoted in the same way), and as in Maron et al. (2019b), Equation 3 is equivalent to the following linear system: where g acts on both dimensions of L .”
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.”
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).”
Universal Equivariant Multilayer Perceptrons (2020, background): “[26] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman.”
Universal Invariant and Equivariant Graph Neural Networks (2019, background): “In the invariant GNN case, the universality of architectures built using a single hidden layer of such equivariant operators followed by an invariant layer is proved in (Maron et al., 2019b) (see also (Kondor et al., 2018)).”
Relational Representation Learning for Dynamic (Knowledge) Graphs: A Survey (2019, background): “sentation learning models for graphs has been the focus of several studies. It has been studied from dierent perspectives and for dierent classes of models. Xu et al. (2019b), Morris et al. (2019), Maron et al. (2019), Keriven and Peyre (2019) and Chen et al. (2019c) study the expressivity of a clas”
How Powerful are Spectral Graph Neural Networks (2022, background): “Since then, various works have attempted to analyze GNNs with the WL test and graph isomorphism testing (Zhang et al., 2018; Morris et al., 2019; Maron et al., 2019a; Chen et al., 2019; Li et al., 2020; Sato et al., 2019; 2021; Zhang et al., 2021; Zhang & Li, 2021).”
DeeperGCN: All You Need to Train Deeper GCNs (2020, background): “Maron et al. [2019b] show the universality of invariant GNNs to any continuous invariant function.”
SIGN: Scalable Inception Graph Neural Networks (2020, background): “Second, on grids complex features can be constructed compositionally from simple ones by using multiple layers, whereas in message passing-type graph neural networks such compositionality is not achievable due to their inability to disambiguate graph substructure [61, 40, 41], hence depth does not i”
Benchmarking Graph Neural Networks (2023, background): “[60] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman.”
Universal approximations of permutation invariant/equivariant functions by deep neural networks (2019, background): “The second one, [22], considered a G-invariant model for any finite group G.”
On the equivalence between graph isomorphism testing and function approximation with GNNs (2019, background): “Upper bounds on the approximation power of the G-invariant networks when the tensor order is limited remains open except for when G = An [18].”
Can graph neural networks count substructures? (2020, background): “[40] show that if k is allowed to grow as a function of the size of the graphs, then k-IGNs can achieve universal approximation of permutation-invariant functions on graphs.”
Relational Pooling for Graph Representations (2019, background): “Another development explores the universality properties of invariance-preserving neural networks and concludes some architectures are computationally intractable (Maron et al., 2019).”