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 \emph{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.
 We consider the problem of graph learning, namely finding a functional relation between input graphs (more generally, hyper-graphs) G and corresponding targets T , e.g., labels. As graphs are common data representations, this task received quite a bit of recent attention in the machine learning community BID2 ; BID13 ; ; BID38 .More specifically, a (hyper-)graph data point G = (V, A) consists of a set of n nodes V, and values A attached to its hyper-edges 1 . These values are encoded in a tensor A. The order of the tensor A, or equivalently, the number of indices used to represent its elements, indicates the type of data it represents, as follows: First order tensor represents node-values where A i is the value of the i-th node; Second order tensor represents edge-values, where A ij is the value attached to the (i, j) edge ; in general, k-th order tensor encodes hyper-edge-values, where A i1,...,i k represents the value of the hyper-edge represented by (i 1 , . . . , i k ). For example , it is customary to represent a graph using a binary adjacency matrix A, where A ij equals one if vertex i is connected to vertex j and zero otherwise. We denote the set of order-k tensors by R n k .The task at hand is constructing a functional relation f (A ) ≈ T , where f is a neural network. If T = t is a single output response then it is natural to ask that f is order invariant, namely it should produce the same output regardless of the node numbering used to encode A. For example, if we represent a graph using an adjacency matrix A = A ∈ R n×n , then for an arbitrary permutation matrix P and an arbitrary adjacency matrix A, the function f is order invariant if it satisfies f (P T AP ) = f (A). If the targets T specify output response in a form of a tensor, T = T , then it is natural to ask that f is order equivariant, that is, f commutes with the renumbering of nodes operator acting on tensors. Using the above adjacency matrix example, for every adjacency matrix A and Figure 1 : The full basis for equivariant linear layers for edge-value data A ∈ R n×n , for n = 5. The purely linear 15 basis elements, B µ , are represented by matrices n 2 × n 2 , and the 2 bias basis elements (right), C λ , by matrices n × n, see equation 9.every permutation matrix P , the function f is equivariant if it satisfies f (P T AP ) = P T f (A)P . To define invariance and equivariance for functions acting on general tensors A ∈ R n k we use the reordering operator: P A is defined to be the tensor that results from renumbering the nodes V according to the permutation defined by P . Invariance now reads as f (P A) = f (A); while equivariance means f (P A) = P f (A). Note that the latter equivariance definition also holds for functions between different order tensors, f : R n k → R n l .Following the standard paradigm of neural-networks where a network f is defined by alternating compositions of linear layers and non-linear activations, we set as a goal to characterize all linear invariant and equivariant layers. The case of node-value input A = a ∈ R n was treated in the pioneering works of BID39 ; BID26 . These works characterize all linear permutation invariant and equivariant operators acting on node-value (i.e., first order) tensors, R n . In particular it it shown that the linear space of invariant linear operators L : R n → R is of dimension one, containing essentially only the sum operator, L(a) = α1T a. The space of equivariant linear operators L : DISPLAYFORM0 The general equivariant tensor case was partially treated in where the authors make the observation that the set of standard tensor operators: product, element-wise product, summation, and contraction are all equivariant, and due to linearity the same applies to their linear combinations. However, these do not exhaust nor provide a full and complete basis for all possible tensor equivariant linear layers.In this paper we provide a full characterization of permutation invariant and equivariant linear layers for general tensor input and output data. We show that the space of invariant linear layers L : R n k → R is of dimension b(k), where b(k) is the k-th Bell number. The k-th Bell number is the number of possible partitions of a set of size k; see inset for the case k = 3. Furthermore, the space of equivariant linear layers DISPLAYFORM1 Remarkably, this dimension is independent of the size n of the node set V. This allows applying the same network on graphs of different sizes. For both types of layers we provide a general formula for an orthogonal basis that can be readily used to build linear invariant or equivariant layers with maximal expressive power. Going back to the example of a graph represented by an adjacency matrix A ∈ R n×n we have k = 2 and the linear invariant layers L : Figure 1 shows visualization of the basis to the linear equivariant layers acting on edge-value data such as adjacency matrices. DISPLAYFORM2 In BID12 the authors provide an impressive generalization of the case of node-value data to several node sets, V 1 , V 2 , . . . , V m of sizes n 1 , n 2 , . . . , n m . Their goal is to learn interactions across sets. That is, an input data point is a tensor A ∈ R n1×n2×···×nm that assigns a value to each element in the cartesian product V 1 × V 2 × · · · × V m . Renumbering the nodes in each node set using permutation matrices P 1 , . . . , P m (resp.) results in a new tensor we denote by P 1:m A. Order invariance means f (P 1:m A) = f (A) and order equivariance is f (P 1:m A) = P 1:m f (A). BID12 introduce bases for linear invariant and equivariant layers. Although the layers in BID12 satisfy the order invariance and equivariance, they do not exhaust all possible such layers in case some node sets coincide. For example, if V 1 = V 2 they have 4 independent learnable parameters where our model has the maximal number of 15 parameters.Our analysis allows generalizing the multi-node set case to arbitrary tensor data over V 1 × V 2 × · · · × V m . Namely, for data points in the form of a tensor A ∈ R n k 1 1 ×n k 2 2 ×···×n km m . The tensor A attaches a value to every element of the Cartesian product DISPLAYFORM3 2 , that is, k 1 -tuple from V 1 , k 2 -tuple from V 2 and so forth. We show that the linear space of invariant linear layers DISPLAYFORM4 , while the equivariant linear layers L : DISPLAYFORM5 We also provide orthogonal bases for these spaces. Note that, for clarity, the discussion above disregards biases and features; we detail these in the paper.In appendix C we show that our model is capable of approximating any message-passing neural network as defined in BID9 which encapsulate several popular graph learning models. One immediate corollary is that the universal approximation power of our model is not lower than message passing neural nets.In the experimental part of the paper we concentrated on possibly the most popular instantiation of graph learning, namely that of a single node set and edge-value data, e.g., with adjacency matrices. We created simple networks by composing our invariant or equivariant linear layers in standard ways and tested the networks in learning invariant and equivariant graph functions: (i) We compared identical networks with our basis and the basis of BID12 and showed we can learn graph functions like trace, diagonal, and maximal singular vector. The basis in BID12 , tailored to the multi-set setting, cannot learn these functions demonstrating it is not maximal in the graph-learning (i.e., multi-set with repetitions) scenario. We also demonstrate our representation allows extrapolation: learning on one size graphs and testing on another size; (ii) We also tested our networks on a collection of graph learning datasets, achieving results that are comparable to the state-of-the-art in 3 social network datasets.
The paper provides a full characterization of permutation invariant and equivariant linear layers for graph data.
{"src": "scitldr-AIC_train", "paper_id": "Syx72jC9tm"}