INVARIANT AND EQUIVARIANT GRAPH NETWORKS
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 multigraph 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.
Given a graph G of n vertices, the activations at each level of a graph neural network (G-NN) for G 
can be arranged in an n^k tensor T for some k. A fundamental criterion is that this tensor must be equivariant 
to permutations of the vertices of G in the sense of each index of of T being permuted simultaneously. 
This paper enumerates the set of all linear maps that satisfy this criterion, i.e., all linear maps 
which (the authors claim) can serve as the analog of convolution in equivariant G-NNs. 
The authors find that for invariant neural networks such maps span a space of dimension just b(k), whereas 
for equivariant neural networks they span a space of dimension b(2k).
The proof of this result is simple, but elegant. It hinges on the fact that the set of tensor elements of 
the same equality type is both closed and transitive under the permutation action. Therefore, the 
dimensionality of the subspace in question is just the number of different identity types, i.e., 
partitions of either {1,...,k} or {1,...,2k}, depending on whether we are talking about invariance or 
equivariance.
My problem with the paper is that the authors' model of G-NNs doesn't actually map to what is used 
in practice or what is interesting and useful. Let me list my reservations in increasing order of significance.
1. The authors claim that they give a ``full characterization'' of equivariant layers. This is not true. 
Equivariance means that there is *some* action of the symmetric group S_n on each layer, and wrt these actions 
the network is equivariant. Collecting all the activations of a given layer together into a single object L, 
this means that L is transformed according to some representation of S_n. Such a representation can always be 
reduced into a direct sum of the irreducible representations of S_n. The authors only consider the case then 
the representation is the k'th power of the permutation representation (technically called the defining 
representation of the S_n). This corresponds to a specific choice of irreducibles and is not the most general case. 
In fact, this is not an unnatural choice, and all G-NNs that I know follow this route. 
Nonetheless, technically, saying that they consider all possible equivariant networks is not correct.
2. The paper does not discuss what happens when the input tensor is symmetric. On the surface this might seem 
like a strength, since it just means that they can consider the more general case of undirected graphs (although 
they should really say so). In reality, when considering higher order activations it is very misleading because 
it leads to a massive overcounting of the dimensionality of the space of convolutions. In the case of k=2, for 
example, the dimensionality for undirected graphs is probably closer to 5 than 15 for example (I didn't count).
3. Finally, and critically, in actual G-NNs, the aggregation operation in each layer is *not* 
linear, in the sense that it involves a product of the activations of the previous layer with the adjacency 
matrix (messages might be linear but they are only propagated along the edges of the graph). 
In most cases this is motivated by making some reference to the geometric meaning of convolution,  
the Weisfeiler-Lehman algorithm or message passing in graphical models. In any case, it is critical that the 
graph topology be reintroduced into the network at each layer. The algebraic way to see it is that each layer 
must mix the information from the vertices, edges, hyperedges, etc.. The model in this paper could only aggregated 
edge information at the vertices. Vertex information could not be broadcast to neighboring vertices again. 
The elemenary step of ``collecting vertex information from the neighbors but only the neighbors'' cannot be 
realized in this model.
Therefore, I feel that the model used in this paper is rather uninteresting and irrelevant for practical 
purposes. If the authors disagree, I would encourage them to explicitly write down how they think the model 
can replicate one of the standard message passing networks. It is apparent from the 15 operations listed on 
page 11 that they have nothing to do with the graph topology at all.
Minor gripes:
- I wouldn't call (3) and (4) fixed point equations, that's usually used in dynamical systems. Here there is 
an entire subspace fixed by *all* permutations.
- Below (1), they probably mean that ``up to permutation vec(L)=vec(L^T)''.