Universal Invariant and Equivariant Graph Neural Networks

Nicolas Keriven; Gabriel Peyré

Source-linked AI summary

Universal Invariant and Equivariant Graph Neural Networks

Nicolas Keriven, Gabriel Peyré

arXiv:1905.04943v2May 13, 2019cs.LGstat.ML

TL;DR

The paper addresses limited universality theory for permutation-equivariant GNNs, alongside established invariant results. It uses Stone-Weierstrass arguments to analyze one-hidden-layer networks and extends them with a generalized equivariant theorem. The results establish uniform approximation for invariant and equivariant functions across varying graph sizes, while the equivariant proof remains limited to full permutations and vector-valued outputs.

Problem
Universality for equivariant GNNs, particularly with high-order graph inputs, has been less studied than universality for invariant GNNs.
Method
The paper analyzes one-hidden-layer GNNs built from equivariant linear operators, pointwise nonlinearities, and invariant or equivariant final operators using classical and generalized Stone-Weierstrass theorems.
Results
The network classes are dense in continuous invariant and equivariant function spaces, with a single parameter set approximating functions uniformly across graph sizes.
Takeaways & Limitations
The results provide universality guarantees for invariant and equivariant GNNs beyond fixed-size graph settings.
Takeaways & Limitations
The equivariant theorem applies only to the full permutation group and vector-valued outputs, not higher-order graph-valued outputs.

Abstract

from arXiv · show

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.

1 Introduction

The paper studies permutation-invariant and permutation-equivariant GNNs, motivated by applications requiring outputs independent of—or aligned with—node relabeling. It develops universality results for a one-hidden-layer architecture, including varying graph sizes.

Motivation: Permutation invariance preserves outputs under node relabeling, whereas equivariance permutes outputs correspondingly; both are central design goals for GNNs.Equivariance is relevant to applications including community detection, recommender systems, physical interaction networks, state prediction, and protein interface prediction.
Previous work: Prior work established universality for certain invariant GNNs, while universality for equivariant networks, especially with graph-valued inputs, remained less studied.Existing point-cloud results did not allow high-order inputs such as graphs or hypergraphs.
Contributions: The paper gives an alternative Stone-Weierstrass proof for invariant GNN universality and introduces a generalized Stone-Weierstrass theorem for the equivariant case.The generalized theorem handles vector-valued equivariant functions, for which the classical real-valued theorem cannot be applied directly.
Architecture: The studied networks sum channels combining equivariant linear maps, pointwise nonlinearities with equivariant biases, and final invariant or equivariant linear operators.The intermediate maps can increase or decrease tensor order, and the final operator determines global invariance or equivariance.
Scope: The parameter count is independent of the node count, allowing one parameterized GNN to apply across graphs of varying size.The results establish uniform approximation simultaneously for multiple graph sizes rather than only a fixed number of nodes.

2 The case of invariant functions

The invariant-case result combines a graph edit-distance framework with a Stone–Weierstrass argument to establish uniform approximation of continuous invariant functions, including across varying graph sizes.

Graph space and metric: The invariant graph space identifies isomorphic graphs and uses graph edit distance to compare graphs with different numbers of nodes.Node additions and edge-weight modifications receive explicit costs; below the node-addition cost, the distance reduces to the minimum permutation-aligned ℓ1 distance.
Scope and comparison: A single parameter set uniformly approximates every continuous invariant function over all graph sizes up to nmax, improving on the fixed-size setting of Maron et al.The proof does not provide an upper bound on tensorization order, whereas the compared result supplies sufficient and necessary order bounds.
Universality proof: Stone–Weierstrass yields density after the extended invariant GNN class separates non-isomorphic graphs.The separation proof shows that graphs producing identical outputs for every such GNN must be permutations of one another.
Graph space and metric: The graph space is compact under the edit-distance metric, enabling application of Stone–Weierstrass.The construction establishes a Hausdorff metric space and obtains compactness from the continuous image of a compact bounded tensor space.
Invariant GNN algebra: Kronecker products extend invariant GNNs into an algebra closed under multiplication, while equivariant biases preserve invariance under simultaneous permutations.The extended class allows arbitrarily large numbers of channels, tensor orders, and intermediate constructions.
Universality proof: The original invariant architecture is recovered by approximating the auxiliary cosine-based class through Fourier approximation and standard non-linearities.The argument establishes equality for cosine networks and density of networks using any multilayer-perceptron non-linearity.

3 The case of equivariant functions

The paper extends universality results from invariant to equivariant GNNs, proving uniform approximation of equivariant functions across multiple graph sizes with one parameter set. Its proof introduces a generalized Stone-Weierstrass theorem for equivariant functions and uses step-functions over ordered output coordinates.

3 The case of equivariant functions: The main result proves universality for GNNs approximating equivariant functions that return node-indexed vectors.The result concerns permutation equivariance, where permuting graph nodes permutes the output coordinates.
3 The case of equivariant functions: The theorem considers compact graph sets with multiple node counts and establishes uniform approximation simultaneously for all n ≤ nmax.A single GNN parameterization applies across the considered graph sizes.
3.1 Sketch of proof of Theorem 3: an equivariant version of Stone-Weierstrass theorem: The proof constructs a generalized Stone-Weierstrass theorem because equivariant functions form a strict subalgebra of vector-valued continuous functions.Closure under component-wise multiplication motivates the new theorem rather than direct application of the classical scalar-valued version.
3.1 Sketch of proof of Theorem 3: an equivariant version of Stone-Weierstrass theorem: The generalized theorem requires separability and self-separability, under which the relevant subalgebra is dense in the space of equivariant continuous functions.Self-separability distinguishes values across coordinates under the stated graph and index conditions.
3.1 Sketch of proof of Theorem 3: an equivariant version of Stone-Weierstrass theorem: The proof approximates ordered output vectors by summing equivariant step-functions whose initial coordinates approach 1 while the remaining coordinates approach 0.The construction uses modified level sets to distinguish jumps between ordered coordinates.
3.1 Sketch of proof of Theorem 3: an equivariant version of Stone-Weierstrass theorem: The resulting one-hidden-layer GNN class forms an algebra, satisfies both separation conditions, and is dense in the target equivariant network class.The proof connects the algebraic construction to the stated network classes through equivariant linear operators and nonlinearities.

4 Numerical illustrations

The experiments use synthetic adjacency-matrix graphs with two graph sizes to illustrate how tensorization order and width affect approximation. Increasing tensorization order substantially lowers the optimal out-of-sample error, whereas increasing width quickly stagnates and can slightly hurt training.

4 Numerical illustrations: The experiments evaluate invariant and equivariant GNNs on synthetic adjacency-matrix graphs with 5 and 10 nodes.The dataset contains 1.4 · 10^4 graphs, evenly split between the two sizes, drawn from five topologies.
4 Numerical illustrations: Figure 3 reports MSE after 150 epochs, averaged over 5 experiments, with dashed lines denoting testing error.The invariant results appear in the top panel and equivariant results in the bottom panel.
4 Numerical illustrations: Increasing tensorization order significantly lowers the optimal out-of-sample prediction error in both examined cases.This supports the paper’s emphasis on higher-order tensorization for universality.
4 Numerical illustrations: Increasing width S rapidly stagnates out-of-sample error, while excessively large widths can slightly degrade performance by making training harder.The numerical section presents these results as illustrations of the theoretical findings rather than state-of-the-art comparisons.

5 Conclusion

The paper proves universality for a class of one-hidden-layer equivariant networks using an extension of Stone–Weierstrass. It leaves graph-valued outputs and bounded tensorization orders as open problems.

The paper proves universality for a class of one-hidden-layer equivariant networks.
The proof extends the classical Stone–Weierstrass theorem to the vector-valued equivariant setting.
Extending this proof technique to more general equivariant networks with graph-valued outputs remains open.Such outputs could support dynamic-graph models using recurrent architectures.
The approximation power of networks with bounded tensorization orders remains an open question.These bounded-order networks are more likely to be implemented on large graphs.

A.1.1 Proof of Lemma 1

The proof establishes continuity of invariant network functions with respect to d_edit by combining local Lipschitz properties with permutation invariance.

Invariant GNN functions are shown to be continuous with respect to d_edit.
For sufficiently close graphs, the graphs have the same number of nodes.The argument uses local Lipschitz properties of ρ, H, and F.
Permutation invariance is used together with the Lipschitz bounds to control differences between network outputs.
The proof framework treats invariant operators as closed under multiplication by constructing H3 = H1 ⊗ H2.

A.1.2 Proof of Lemma 2

The proof shows that invariant network outputs can distinguish graphs by recovering node counts and multisets of tensor entries, ultimately identifying graphs up to permutation.

The contradiction argument assumes every invariant network gives equal outputs on two graphs.
The proof first establishes that the two graphs have the same number of nodes using sigmoid networks and a threshold τ.
It then shows that corresponding tensor entries form the same multisets, including multiplicities.
Because the sigmoid is one-to-one on the relevant domain, a permutation matching transformed tensors also matches the original graph entries.
The invariant operator construction and tensor identities yield a permutation relating the two graphs.
The multiset correspondence supplies a permutation σ satisfying the required equality of tensor entries.

A.1.3 Proof of Lemma 3

The proof approximates nonlinear tensor features with cosine expansions and controls the resulting approximation error through tensor products and bounded linear operators.

On a bounded domain, the relevant affine features are uniformly bounded by some M.
The sigmoid is uniformly approximated on [−M, M] by a finite linear combination of cosine functions.
Tensor-product approximation errors are bounded recursively, yielding e_s ≤ 3T_sε under the stated construction.
The proof uses boundedness of finite-dimensional linear operators to propagate the approximation error through the final invariant or equivariant operator.
Cosine products are expanded using cos(a) cos(b) = cos(a + b) + cos(a − b).
Tensor features are lifted into equivariant outputs using invariant all-ones vectors and equivariant linear functions and biases.

A.2.1 Proof of Lemma 4

The proof shows that equivariant linear operators can be composed to represent the Hadamard product, preserving equivariance under node permutations.

A.2.1 Proof of Lemma 4: Two equivariant linear operators can be combined through tensorization and matricization into a third equivariant operator.The construction defines H3 on a tensor product so that H1[G1] ⊙ H2[G2] = H3[G1 ⊗ G2].
A.2.1 Proof of Lemma 4: Therefore, the Hadamard product closure required by eq.(ρ) holds for equivariant operators.This completes the equivariance argument for the constructed operator H3.
A.2.1 Proof of Lemma 4: Permutation identities for H1, H2, and the matricization map establish that H3 transforms equivariantly.The proof applies the relations H1P ⊗k = PH1, H2P ⊗ℓ = PH2, and the corresponding matricization identity.

A.2.2 Proof of Lemma 5

The proof establishes separability and self-separability for equivariant GNNs by constructing equivariant operators and distinguishing coordinates or non-permutation-equivalent graphs.

Separability: Separability in the equivariant setting follows from the invariant case by stacking invariant linear operators across coordinates.The construction turns invariant operators into linear equivariant operators acting coordinatewise.
Separability: An equivariant operator is used to separate two graphs that are not permutations of one another.Applying the invariant separation result to the operator in eq.(ρsig.) yields f(G) ≠ f(G′), and repeating it across coordinates separates every output coordinate.
Self-separability: For self-separability, equality of all equivariant outputs at two indices implies that the graph has a self-isomorphism exchanging those indices.The proof proceeds by contradiction for indices k ∈ I and ℓ ∈ I^c.
Self-separability: The construction defines a coordinate-sensitive equivariant GNN using permutation orbits and verifies its equivariance under arbitrary permutations.The sets O(q) organize permutations by the image of a fixed index, allowing the constructed function to transform as required.
Self-separability: Orbit cardinality and inclusion relations complete the argument that the constructed operator is valid for the required equivariant separation.The proof uses a permutation in O(ℓ) fixing the relevant representation and observes O(ℓ) ⊂ OI.

B Adapted Stone-Weierstrass theorem: proof of Theorem 4

The proof develops step-functions in an equivariant function algebra and uses them to approximate continuous equivariant functions uniformly on graphs with bounded, varying sizes.

Step-functions: The key intermediate result constructs equivariant step-functions that separate closed graph sets under orbit and self-isomorphism conditions.Lemma 7 assumes n ≤ nmax, an index subset I, and conditions excluding relevant permutations and self-isomorphisms.
Step-functions: The construction first builds local functions that are large on a neighborhood of one graph and small on a disjoint closed set.Lemmas 8 and 9 provide coordinate-wise and scalar versions of this local separation.
Step-functions: Compactness turns finitely many local separators into global functions by combining auxiliary functions that control behavior across neighborhoods.The proof uses finite covers, orbit-excluded closed sets, and products or related combinations to obtain the required bounds.
Step-functions: Bernoulli’s inequality and powers of bounded functions sharpen the separation to arbitrary ε-accuracy.For sufficiently large p, q^p is at most ε on the target set and at least 1 − ε on the selected coordinates, yielding f = 1 − q^p.
Proof of Theorem 4: The proof of Theorem 4 restricts to ordered-coordinate representatives, partitions the target range into compact sets, and applies the step-function lemma.Equivariance makes approximation on the ordered representative set sufficient for approximation on the full graph space.
Proof of Theorem 4: Summing the constructed functions produces a GNN that approximates the continuous equivariant function on graphs with different node counts up to nmax.The argument separates compact regions indexed by node count, coordinate interval, and output scale, then combines the resulting bounds.