PaperlayerView exact revision on arXiv

Source-linked AI summary

Expressive Power of Invariant and Equivariant Graph Neural Networks

Waïss Azizian, Marc Lelarge

arXiv:2006.15646v3cs.LGcs.DMstat.ML

TL;DR

Existing universality theorems for GNNs relied on intractable classes, leaving approximation guarantees for practical architectures open. The paper characterizes approximation for invariant and equivariant GNNs using a symmetry-aware Stone-Weierstrass result. It establishes the strongest fixed-order approximation power for FGNNs and reports strong QAP graph-alignment performance.

  • Problem

    Existing GNN universality theorems apply to intractable classes, while approximation guarantees for practical architectures remain needed.

    Source: §1 · p. 2

  • Method

    The paper characterizes functions approximable by MGNNs, k-LGNNs, and k-FGNNs using a Stone-Weierstrass theorem extended to invariant and equivariant functions.

    Source: §1 · p. 2

  • Results

    For fixed tensor order, k-FGNNs have the best approximation power among the studied architectures, and equivariant 2-FGNNs outperform spectral, SDP, and other GNN algorithms on graph alignment.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The framework recovers prior GNN universality results and applies to graphs of varying sizes.

    Source: §1 · p. 2

    The stated results use compact sets; extension to graphs of varying sizes is deferred to Section F.2.

    Source: §4.3 · p. 7

Abstract

from arXiv · show

Various classes of Graph Neural Networks (GNN) have been proposed and shown to be successful in a wide range of applications with graph structured data. In this paper, we propose a theoretical framework able to compare the expressive power of these GNN architectures. The current universality theorems only apply to intractable classes of GNNs. Here, we prove the first approximation guarantees for practical GNNs, paving the way for a better understanding of their generalization. Our theoretical results are proved for invariant GNNs computing a graph embedding (permutation of the nodes of the input graph does not affect the output) and equivariant GNNs computing an embedding of the nodes (permutation of the input permutes the output). We show that Folklore Graph Neural Networks (FGNN), which are tensor based GNNs augmented with matrix multiplication are the most expressive architectures proposed so far for a given tensor order. We illustrate our results on the Quadratic Assignment Problem (a NP-Hard combinatorial problem) by showing that FGNNs are able to learn how to solve the problem, leading to much better average performances than existing algorithms (based on spectral, SDP or other GNNs architectures). On a practical side, we also implement masked tensors to handle batches of graphs of varying sizes.

1 INTRODUCTION

The paper develops approximation guarantees for practical invariant and equivariant GNNs, extending comparisons beyond pairwise graph separation. It finds that folklore GNNs are strongest at a fixed tensor order and demonstrates their performance on graph alignment.

1 INTRODUCTION

  • If (k + 1)-WL distinguishes two graphs, some k-FGNN distinguishes that pair, making it the strongest considered architecture at tensor order k.This extends the separating-power result for 2-FGNNs to general k.Source: §1 · pp. 1–2
  • For a fixed tensor order, k-FGNNs have the best approximation power among the studied GNN architectures.The framework characterizes functions approximable by MGNNs, k-LGNNs, and k-FGNNs.Source: §1 · p. 2
  • Letting k grow shows that k-FGNN approximation results imply universality for invariant functions.Earlier universality results for linear GNNs required tensor order to grow with the number of nodes.Source: §1 · p. 2
  • Equivariant (k + 1)-LGNNs and k-FGNNs approximate equivariant functions less powerful than the equivariant (k + 1)-WL, for k ≥1.The analysis also applies to graphs of varying sizes.Source: §1 · p. 2
  • Equivariant 2-FGNNs learn node embeddings for graph alignment that outperform spectral, SDP, and other GNN algorithms by a large margin.The paper uses the Quadratic Assignment Problem to illustrate its theoretical results.Source: §1 · p. 2
  • The paper highlights masked tensors as a practical way to handle batches of graphs with varying sizes.The introduction identifies handling such batches as an implementation question.Source: §1 · p. 2

2 RELATED WORK

The related work positions fixed-order approximation guarantees against earlier universality results that often required arbitrarily high-order tensors. It also establishes graph-tensor notation and defines the permutation behavior used to distinguish invariant from equivariant operators.

2 RELATED WORK

  • Earlier universality approaches often required arbitrary or node-count-dependent tensor order, while this work gives approximation guarantees at fixed tensor order.The discussion also contrasts these results with message-passing and set-network approaches, and notes related pooling and sparse high-order architectures.Source: §2 · pp. 2–3

2.1 NOTATIONS: GRAPHS AS TENSORS

  • Graphs are represented either as order-k tensors or as discrete graphs with vertex features; the adjacency matrix is the order-2 representation.The discrete representation uses a graph on n nodes together with a feature vector for its vertices.Source: §2.1 · p. 3

2.2 DEFINITIONS: INVARIANT AND EQUIVARIANT OPERATORS

  • An invariant function leaves its output unchanged under node permutations, whereas an equivariant function permutes its output with the input.The definitions also introduce invariant summation and a lifting map that assigns k-tuples isomorphism types; for order 2, the initialization records adjacency and whether the nodes coincide.Source: §2.2 · p. 4

3 GNN DEFINITIONS

The paper defines three GNN families through layers operating on graph representations: message passing, linear equivariant layers, and folklore layers. Each family has invariant and equivariant forms, producing graph-level or node-level outputs.

3 GNN DEFINITIONS

  • The architectures compose layers over graph representations and finish with a continuous map that yields a graph feature or node features.The order-2 case represents graphs with node and edge features.Source: §3 · p. 4

3.1 MESSAGE PASSING GNN

  • MGNN layers update each node using its feature and the multiset of neighboring-node features, then compose equivariant layers.An invariant MGNN applies a symmetric function, typically summation, to node features.Source: §3.1 · pp. 4–5

3.2 LINEAR GNN

  • A k-LGNN applies linear equivariant layers to order-k tensors, with an initial lifting and, for the invariant form, a summation reduction.The passage defines the invariant k-LGNN composition using I_k, the layers, S_k, and a final map.Source: §3.2 · p. 5

3.3 FOLKLORE GNN

  • A k-FGNN composes folklore graph layers after lifting the graph to an order-k tensor, then reduces to node-level or graph-level features.The folklore layer uses learnable functions and is described as equivariant and expressive.Source: §3.3 · p. 5

4 THEORETICAL RESULTS FOR GNNS

The section compares GNN separating power with Weisfeiler-Lehman tests and gives fixed-order approximation guarantees for invariant and equivariant functions. It also derives practical implications for universality and order-2 architectures.

4.1 WEISFEILER-LEHMAN INVARIANT AND EQUIVARIANT VERSIONS

  • The stable k-WL coloring is a graph invariant, and its separating power increases with k.The section also notes that (k+1)-WL distinguishes strictly more than k-WL.Source: §4.1 · p. 6, §4.2 · p. 6

4.2 SEPARATING POWER OF GNNS

  • MGNN invariant separating power matches 2-WL, k-LGNN matches k-WL invariantly, and k-FGNN matches (k+1)-WL in both settings.For equivariant k-LGNNs, the stated relation is an inclusion in k-WL separating power.Source: §4.2 · p. 6
  • For order-2 tensors, 2-FGNN has the strongest separating power among the compared architectures, but its layer uses dense n × n matrix multiplication.Message-passing computations are local and can be parallelized, while the linear layer has only 15 linear functions for all n.Source: §4.2 · p. 6

4.3 APPROXIMATION RESULTS FOR GNNS

  • For any fixed order k, k-FGNNs can approximate any continuous function less separating than (k+1)-WL, in both invariant and equivariant cases.Source: §4.3 · p. 7
  • For order 2, 2-FGNNI has strictly greater approximation power than MGNNI and 2-LGNNI.The section states MGNNI = 2-LGNNI ⊊ 2-FGNNI.Source: §4.3 · p. 7
  • The approximation proofs connect separating power to approximation through a generalized Stone-Weierstrass theorem and an input augmentation for equivariant functions.The method then applies a fine-grained approximation theorem.Source: §4.3 · p. 7
  • O(√n)-LGNNs or O(√n)-FGNNs achieve universality for planar graphs, while 2-FGNNs can approximate functions of the graph spectrum.The spectrum is stated to be less separating than 3-WL.Source: §4.3 · p. 7

5 EXPRESSIVENESS OF GNNS

The section develops general approximation tools for invariant and equivariant functions under finite group actions. It applies these tools to relational pooling GNNs and states an equivariant approximation theorem.

5 EXPRESSIVENESS OF GNNS

  • The section's general tools support approximation results for function classes that respect finite-group symmetries.It introduces invariant and equivariant continuous functions on a compact input space.Source: §5 · p. 8
  • For invariant k-ary relational pooling GNNs, the approximation class includes continuous functions no more separating than the architecture's own separating relation.The cited work establishes only that this relation is strictly contained in 2-WL invariant separating power.Source: §5 · p. 8
  • The section states a general theorem for equivariant functions under the permutation group acting on node outputs.The output coordinates are permuted by the inverse permutation of node indices.Source: §5 · p. 8

6 QUADRATIC ASSIGNMENT PROBLEM

The section evaluates 2-FGNNE on Quadratic Assignment Problem instances from Erdős–Rényi and random regular graph distributions. Its reported graph-matching accuracy is much improved over previous works.

6 QUADRATIC ASSIGNMENT PROBLEM

  • Quadratic Assignment Problem instances include network alignment, and QAP is NP-hard; prior methods described here fail on regular graphs.The section frames regular graphs as particularly hard for isomorphism testing.Source: §6 · pp. 8–9
  • 2-FGNNE substantially improves graph-matching accuracy over previous works on Erdős–Rényi and random regular graph distributions.The passage reports improvement without giving numeric results.Source: §6 · p. 9
  • The method embeds each graph, multiplies the embeddings into a node-similarity matrix, then solves a linear assignment problem using that matrix as costs.The system follows the siamese method described in the section.Source: §6 · p. 9

7 CONCLUSION

The paper compares the expressive power of practical message-passing, linear, and folklore GNNs in invariant and equivariant settings. It finds that folklore GNNs have the strongest approximation power among the studied order-2-tensor architectures and perform substantially better on QAP.

7 CONCLUSION

  • Folklore GNNs have the best approximation power among the studied GNNs using order-2 tensors and show a significant performance gap on QAP versus other approaches.The conclusion does not specify the size of the performance gap.Source: §7 · p. 9
  • The analysis covers message-passing, linear, and folklore GNNs, including both invariant and equivariant variants.Source: §7 · p. 9

A.1 DETAILS ON THE EXPERIMENTAL SETUP

The experiments train a siamese 2-FGNNE to match paired graphs, with training and evaluation on planted instances. The setup specifies the graph-generation conditions and model training parameters.

A.1 DETAILS ON THE EXPERIMENTAL SETUP

  • The 2-FGNNE produces embeddings for each graph, forms their outer product, applies row-wise softmax, and predicts the matching with cross-entropy loss.Source: §A.1 · p. 14
  • The model has two layers, MLPs of depth 3 and hidden size 64, and is trained for 25 epochs with batch size 32 and learning rate 1e-4 using Adam.Source: §A.1 · p. 14
  • Each experiment uses 20,000 training graphs, 1,000 validation graphs, and 1,000 test graphs; the Erdős–Rényi setting uses n = 50 and edge density 0.2.Source: §A.1 · p. 14
  • For the Erdős–Rényi perturbation, p1 sets the noise level and p2 is chosen so the perturbed graph has the same expected degree; the regular-graph setting uses degree 10.Source: §A.1 · p. 14

A.2 EXPERIMENTAL RESULTS ON GRAPHS OF VARYING SIZE

The appendix tests GNN performance on graphs of varying size and describes Weisfeiler–Lehman tools used to characterize expressive power. It also gives supporting results on separating power and approximation assumptions, including the initialization and augmented-separation constructions.

A.2 EXPERIMENTAL RESULTS ON GRAPHS OF VARYING SIZE

  • For varying-size graphs, vertex counts are sampled from a binomial distribution with n = 50 and pn = 0.9; masking batches tensors to nmax × nmax allows operations to remain valid for each graph.The section contrasts masking with grouping graphs by size in earlier tensor-based implementations.Source: §A.2 · pp. 14–15

A.3 GENERALIZATION FOR REGULAR GRAPHS

  • A model trained at noise level ≈0.1 performs best across all tested noise levels, and a majority of models generalize to noise levels outside their training setting.Source: §A.3 · p. 15

B.1 WEISFEILER-LEHMAN TEST ON VERTICES; B.2 ISOMORPHISM TYPE

  • The vertex-coloring test starts from graph structure and vertex features, while tuple isomorphism types identify tuples whose positionwise mapping is a partial isomorphism.Source: §B.1 · p. 16, §B.2 · p. 16

B.3 WEISFEILER-LEHMAN AND FOLKLORE WEISFEILER-LEHMAN TESTS OF ORDER k ≥2

  • For k-tuples, k-WL replaces one coordinate at a time, whereas k-FWL forms neighborhoods by inserting the same vertex across tuple positions.Source: §B.3 · p. 17

C SEPARATING POWER OF GNN

  • Invariant k-FGNN and equivariant k-FGNN have the separating power of (k + 1)-WL, while k-LGNN matches k-WL in the invariant case and is bounded by k-WL in the equivariant case.Source: C SEPARATING POWER OF GNN · p. 18

C.1 MUTLI-LINEAR PERCEPTRONS

  • The separating-power proof assumes continuous MLP classes dense in C(F0, F1) for finite-dimensional feature spaces.Source: §C.1 · p. 18

C.2 AUGMENTED SEPARATING POWER

  • Augmented separating power refines ordinary separating power and behaves well under composition with reduction layers.Source: §C.2 · p. 18

C.3 INITIALIZATION LAYER

  • The initialization layer encodes adjacency and vertex colors in an order-2 tensor, then maps it to a k-tuple tensor with separating power matching isomorphism type.Source: §C.3 · p. 19

C.4 KNOWN RESULTS ABOUT THE SEPARATING POWER OF SOME GNN CLASSES

The appendix assembles known separating-power results and adds a bound for folklore GNNs, then applies symmetry-aware approximation results to GNNs. It also extends Stone–Weierstrass reasoning and illustrates the resulting approximation framework with PointNet.

C.4 KNOWN RESULTS ABOUT THE SEPARATING POWER OF SOME GNN CLASSES

  • The appendix recasts message-passing, linear-equivariant, and folklore GNN layer classes and attributes prior separating-power results to earlier work.Source: §C.4 · p. 20

C.5 BOUNDING THE SEPARATING POWER OF k-FGNN

  • The appendix completes the literature results with a separating-power bound for k-FGNN, noting that the k = 2 case was already proved by Geerts (2020a).Source: §C.5 · p. 20

C.6 CONCLUSION

  • The appendix proof of the separating-power statements relies on earlier results or direct consequences of the preceding lemmas.Source: §C.6 · p. 21

D STONE-WEIERSTRASS THEOREM WITH SYMMETRIES

  • The symmetry-aware Stone–Weierstrass extension is developed beyond graphs and permutations, with GNN approximation results obtained by applying it to tensors and the symmetric group.Source: D STONE-WEIERSTRASS THEOREM WITH… · p. 21

D.1 GENERAL NOTATIONS

  • Invariant functions are unchanged by group action, whereas equivariant functions transform their outputs according to that action.Source: §D.1 · p. 22

D.2 SEPARATING POWER

  • The appendix defines separating power through the equivalence relation induced by a function class and states that it is stable under closure.Source: §D.2 · p. 22

D.3 APPROXIMATION THEOREMS FOR REAL-VALUED FUNCTIONS

  • The real-valued approximation result extends Stone–Weierstrass to cases where the function class need not separate all points, and the appendix applies it to invariant PointNet functions.Source: §D.3 · p. 23

D.4 THE EQUIVARIANT APPROXIMATION THEOREM

The section develops equivariant approximation theorems using separation up to group orbits, applying the framework to recover PointNetST universality and characterize subalgebras of R^p. Its proof reduces the general case to a quotient algebra where the prior result applies, then uses injectivity to establish the characterization.

D.4 THE EQUIVARIANT APPROXIMATION THEOREM

  • Theorem 22 characterizes the uniform closure of equivariant function classes using their separation relation and attainable outputs, under scalar separation modulo output orbits.It relaxes the condition ρ(F_scal) ⊆ ρ(F) to ρ(F_scal) ⊆ ρ(π ◦ F), where π projects outputs to group orbits.Source: §D.4 · p. 25
  • Theorem 22 implies PointNetST is universal for continuous equivariant functions, whereas PointNet alone cannot approximate every such function.The transmission layer adds the needed class of functions to PointNet.Source: §D.4 · p. 25

D.5 A PRELIMINARY VERSION OF THE EQUIVARIANT APPROXIMATION THEOREM

  • Under uniform convergence, closure of F consists of equivariant f satisfying ρ(F) ⊆ ρ(f) and f(x) ∈ F(x) for all x, if F is a subalgebra and ρ(Fscal) ⊆ {(x,x′): ∃g∈G, (g·x,x′)∈ρ(F)}.Source: §D.5 · p. 26

D.6 CHARACTERIZING THE SUBALGEBRAS OF Rp

  • Every subalgebra A of R^p consists exactly of vectors obeying its coordinate-equality constraints and having zero in its identically zero coordinates.For a subalgebra containing 1 and a vector with pairwise distinct coordinates, Lagrange interpolation yields A = R^p.Source: §D.6 · pp. 28–29
  • The proof defines J as coordinates that are always zero and constructs a subalgebra A′ by imposing those zeros and the equalities indexed by I, with A ⊆ A′.These constraints set up the reduction to the previous case.Source: §D.6 · p. 29
  • The equivalence classes of I on Jᶜ define a representative-coordinate map ϕ whose image ϕ(A) satisfies the prior case’s conditions and equals Rp′.Here p′ is the number of equivalence classes; ϕ(A) is a subalgebra because ϕ is an algebra homomorphism.Source: §D.6 · p. 29
  • Because A ⊆ A′ and ϕ is injective on A′, the equality ϕ(A) = ϕ(A′) implies A = A′, concluding the proof.The proof obtains the equal images since ϕ(A) = Rp′ and ϕ(A) ⊆ ϕ(A′) ⊆ Rp′.Source: §D.6 · p. 29

D.7 PROOF OF THE MAIN EQUIVARIANT APPROXIMATION THEOREM

This section proves an equivariant approximation characterization and characterizes the distinguishability relation induced by F, using invariance for one inclusion and MLP-based separation for the reverse. It also derives practical invariant and node-equivariant reductions and connects them to GNN expressivity.

D.7 PROOF OF THE MAIN EQUIVARIANT APPROXIMATION THEOREM

  • Under its stated assumptions, Theorem 22 characterizes the uniform closure of F as equivariant maps f with ρ(F) ⊆ ρ(f) and f(x) ∈ F(x) for every x.The assumptions include that F is a subalgebra containing the constant function 1.Source: §D.7 · p. 30

D.8 PRACTICAL REDUCTIONS

  • For invariant functions, Corollary 29 characterizes the closure by ρ(F) ⊆ ρ(f); the constant vector (1, 2, …, p) ensures F(x) = Rp.The proof applies Theorem 22 using a trivial action on Y and reduces the pointwise constraint to the full output space.Source: §D.8 · pp. 30–31
  • For node-equivariant functions, the closure consists exactly of equivariant maps f satisfying ρ(F) ⊆ ρ(f).The proof removes the pointwise constraint by showing that F(x) is determined by equalities between nodes that coincide for every function in F.Source: §D.8 · pp. 32–33

D.9 REDUCTIONS FOR GNNS

  • Lemma 32 connects the continuous-function reductions to MLP-based families, and Theorems 5 and 6 follow by combining it with Corollaries 29 and 30.The lemma’s construction replaces the MLP with an arbitrary continuous function and preserves equivariance under the action described in Corollary 30.Source: §D.9 · pp. 33–34

E PROOFS FOR EXPRESSIVENESS OF GNNS

  • The additional stability assumption in Theorem 6 is described as “almost” necessary for the result.The passage gives this qualification while discussing the theorem’s expressive-power result.Source: E PROOFS FOR EXPRESSIVENESS OF GNNS · p. 34

E.1 EXPRESSIVITY OF GNN LAYERS

  • The layer family formed from multi-linear perceptrons is dense in CI(K, F1).Its functions use f0 on the global feature and pooled features, together with fj maps from the global feature, for compact K.Source: §E.1 · p. 34
  • Invariance implies that ρ(inv) is contained in ρ(F).The proof then aims to show the reverse inclusion.Source: §E.1 · p. 35
  • For pairs with different global features, an MLP separates them; otherwise, a lemma-based decomposition and MLP separate node arrays not related by a permutation.The proof uses this case distinction to establish the reverse inclusion.Source: §E.1 · p. 35

E.2 APPROXIMATION THEOREMS FOR GNNS

The section establishes approximation results for invariant and equivariant GNN classes, then extends approximation results to settings with varying graph sizes under structural assumptions.

E.2 APPROXIMATION THEOREMS FOR GNNS

  • Invariant k-LGNN approximation includes invariant functions whose separating power is at least k-WL’s.The stated class inclusion compares functions on compact input spaces.Source: §E.2 · p. 35
  • Equivariant k-LGNN approximation includes equivariant functions whose separating power is at least k-WL’s.The proof checks a stability assumption before applying the equivariant approximation theorem.Source: §E.2 · pp. 35–36

F.1 EXTENSION TO DISCONNECTED INPUT SPACES

  • A general lemma extends approximation results to varying-size graphs when input-size components are disconnected and the function classes satisfy subalgebra and scalar-discrimination assumptions.The lemma also assumes adapted functions preserve the corresponding output components.Source: §F.1 · pp. 37–38

F.2 APPROXIMATION THEOREM WITH VARYING GRAPH SIZE

The section extends fixed-size approximation results to graphs of varying sizes, using a general lemma and a graph-size discrimination condition.

F.2 APPROXIMATION THEOREM WITH VARYING GRAPH SIZE

  • For graphs of size less than N, the extension uses the final topology or equivalently graph edit distance, and requires GNN classes to discriminate between graph sizes.The proof is presented as a sketch based on the general lemma.Source: §F.2 · p. 39
  • The invariant approximation result for k-LGNNs extends to the varying-size setting through the fixed-size theorem and the disconnected-space lemma.The stated corollary uses an additional lemma to satisfy the subalgebra assumption.Source: §F.2 · p. 39
Loading 2006.15646v3…