Invariant and Equivariant Graph Networks

By Haggai Maron, Heli Ben-Hamu, Nadav Shamir, Yaron Lipman. 2018

576 citations recorded by the source corpus.

Invariant and equivariant networks have been successfully used for learning images, sets, point clouds, and graphs. A basic challenge in developing such networks is finding the maximal collection of invariant and equivariant linear layers. Although this question is answered for the first three examples (for popular transformations, at-least), a full characterization of invariant and equivariant linear layers for graphs is not known. In this paper we provide a characterization of all permutation invariant and equivariant linear layers for (hyper-)graph data, and show that their dimension, in case of edge-value graph data, is 2 and 15, respectively. More generally, for graph data defined on k-tuples of nodes, the dimension is the k-th and 2k-th Bell numbers. Orthogonal bases for the layers are computed, including generalization to multi-graph data. The constant number of basis elements and their characteristics allow successfully applying the networks to different size graphs. From the theoretical point of view, our results generalize and unify recent advancement in equivariant deep learning. In particular, we show that our model is capable of approximating any message passing neural network Applying these new linear layers in a simple deep neural network framework is shown to achieve comparable results to state-of-the-art and to have better expressivity than previous invariant and equivariant bases.

Subfields: Artificial Intelligence, Management Science and Operations Research, Molecular Biology

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 Management Science and Operations Research

In Molecular Biology

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 .”
Gauge Equivariant Convolutional Networks and the Icosahedral CNN (2019, methodology): “, 2018), graphs (Kondor et al., 2018b; Hy et al., 2018; Maron et al., 2019), translations and rotations of the plane and 3D space (Oyallon & Mallat, 2015; Cohen & Welling, 2016; 2017; Marcos et al.”
A Comprehensive Survey on Graph Neural Networks (2019, background): “Maron et al. [104] theoretically study the characteristics of permutation invariant and equiv-ariant linear layers for graph data.”
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].”
Identity-aware Graph Neural Networks (2021, methodology): “Recently, many neural networks have been proposed with expressive power beyond the 1-WL test, including (Chen et al. 2019; Maron et al. 2019a; Murphy et al. 2019; You, Ying, and Leskovec 2019; Li et al. 2020).”
DeeperGCN: All You Need to Train Deeper GCNs (2020, background): “Maron et al. [2019a] compose networks by proposed invariant or equivariant linear layers and show their models are as powerful as any MPNN [Gilmer et al., 2017].”
Weisfeiler and Lehman Go Cellular: CW Networks (2021, background): “[52] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman.”
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting (2020, background): “ing that GSN is strictly more expressive than traditional GNNs for the vast majority of substructures, while retaining the locality of message passing, as opposed to higher-order methods [17], [22], [23], [24] that follow the WL hierarchy (see Section 2).”
On the equivalence between graph isomorphism testing and function approximation with GNNs (2019, methodology): “† : Reported in [29], [42] and [26].”
Benchmarking Graph Neural Networks (2023, methodology): “This model uses the equivariant linear layer LW defined in [59] as LW (h)·,·,k = ∑17 i=1 ∑d j=1Wi,j,kLi(h)·,·,j , where {Li} i=1 is the set of all basis functions for all linear equivariant functions from Rn×n → Rn×n and {Li} i=16 are the basis for the bias terms.”
Relational Pooling for Graph Representations (2019, background): “Another line of work derives bases for permutation-invariant functions of graphs and propose learning the coefficients of basis elements from data (Maron et al., 2018; Hartford et al., 2018).”
Generalization and Representational Limits of Graph Neural Networks (2020, background): “Maron et al. (2019c); Keriven and Peyr´e (2019) proved universality theorems for a speciﬁc class of invariant and equiv-ariant networks, respectively.”
On the Universality of Invariant Networks (2019, methodology): “…the equivalence relations deﬁned above for A n and S n reduce to the same equivalence relation ( i 1 , . . . , i k + l ) ∼ ( j 1 , . . . , j k + l ) if i α = i β if and only if j α = j β , for all α, β ∈ [ k + l ] (see (Maron et al., 2019) where these classes are called equality patterns ).”
Universal approximations of permutation invariant/equivariant functions by deep neural networks (2019, background): “Maron et al. (2019b)”
Combinatorial optimization and reasoning with graph neural networks (2021, background): “…the Trade-off in Scalability, Expressivity, and Generalization Current GNN architectures might miss crucial structural patterns in the data [Morris et al. , 2019; Xu et al. , 2019a], while more expressive approaches [Morris et al. , 2020; Maron et al. , 2019] do not scale to large-scale inputs.”
On the Equivalence between Positional Node Embeddings and Structural Graph Representations (2019, background): “description of graphs (Bloem-Reddy & Teh, 2019; Chen et al., 2019; Kondor & Trivedi, 2018; Maron et al., 2019; Murphy et al., 2019), with connections to finite exchangeability and prior work on multilayer perceptrons (Wood & Shawe-Taylor, 1996).”
Secure Deep Graph Generation with Link Differential Privacy (2020, methodology): “Recent research on graph models has been primarily focused around GCN [Kipf and Welling, 2017], which is shown to be promising in calculating universal graph representations [Maron et al., 2019; Xu et al., 2019].”