Using deep neural networks that are either invariant or equivariant to permutations in order to learn functions on unordered sets has become prevalent. The most popular, basic models are DeepSets (Zaheer et al., 2017) and PointNet (Qi et al., 2017). While known to be universal for approximating invariant functions, DeepSets and PointNet are not known to be universal when approximating equivariant set functions. On the other hand, several recent equivariant set architectures have been proven equivariant universal (Sannai et al., 2019;Keriven & Peyré, 2019), however these models either use layers that are not permutation equivariant (in the standard sense) and/or use higher order tensor variables which are less practical. There is, therefore, a gap in understanding the universality of popular equivariant set models versus theoretical ones. In this paper we close this gap by proving that: (i) PointNet is not equivariant universal; and (ii) adding a single linear transmission layer makes PointNet universal. We call this architecture PointNetST and argue it is the simplest permutation equivariant universal model known to date. Another consequence is that DeepSets is universal, and also PointNetSeg, a popular point cloud segmentation network (used e.g., in (Qi et al., 2017)) is universal. The key theoretical tool used to prove the above results is an explicit characterization of all permutation equivariant polynomial layers. Lastly, we provide numerical experiments validating the theoretical results and comparing different permutation equivariant models.
TLDR: The function these deep set networks can approximate is too limited to call these networks universal equivariant set networks. Authors should scope the paper to the specific function family these networks can approximate. No baseline comparison with GraphNets.
The paper proposes theoretical analysis on a set of networks that process features independently through MLPs + global aggregation operations. However, the function of interest is limited to a small family of affine equivariant transformations.
A more general function is
\begin{equation}
P(X)_i = Ax_i + \sum_{j \in N(x_i, X)} B_{(x_j, x_i)} x_j + c
\end{equation}
where $N(x_i, X)$ is the set of index of neighbors within the set $X$. It is trivial to show that this function is permutation equivariant.
Then, can the function family the authors used in the paper approximate this function? No.
Can the proposed permutation equivariant function represent all function the authors used in the paper? Yes.
1) If $B=0$, then the proposed function becomes MLP.
2) If $A=0, N(x_i, X) = [n]$ and $B_{(x_j, x_i)} \leftarrow B$, then this is $\mathbf{1}\mathbf{1}^TXB$, the global aggregation function.
Also, this is the actual function that a lot of people are interested in. Let me go over few more examples.
3) If $N(x_i, X) = $adjacency on a graph and $B_{(x_j, x_i)} \leftarrow B$, then this is a graph neural network "convolution" (it is not a convolution)
Example adjacency $N(x_i, X) = \{j \;| \; \|x_i - x_j\|_p < \delta, x_j \in X\}$.
\begin{equation}
\text{GraphOp}(X)_i = Ax_i + \sum_{j \in \{j \;| \; \|x_i - x_j\|_p < \delta, x_j \in X\}} Bx_j + c
\end{equation}
4) If $x_i = [r,g,b,u,v]$ where $[r,g,b]$ is the color, $[u,v]$ is the pixel coordinate and $N(x_i, X) =$ pixel neighbors within some kernel size, $B(x_j, x_i)$ to be the block diagonal matrix only for the first three dimensions and 0 for the rest, then this is the 2D convolution.
Again, the above function is a more general permutation equivariant function that can represent: a graph neural network layer, a convolution, MLP, global pooling and is one of the most widely used functions in the ML community, not MLP + global aggregation.
Regarding the experiment metrics and plots:
On the Knapsack test, the metric of interest is not the accuracy of individual prediction. Rather, whether the network has successfully predicted the optimal solution, or how close the prediction is to the solution.
For example: success rate within the epsilon radius of the optimal solution while satisfying all the constraints. Fail otherwise. If these networks can truly solve these problems, authors should report the success rate while varying the threshold, not individual accuracy of the items which can be arbitrarily high by violating constraints.
Also, the authors should compare with few more graphnet + transmission layer (GraphNetST) baselines with the graph layers: $P(X)_i = Ax_i + \sum_{j \in N(x_i, X)} Bx_j + c$ and the same single transmission layer $\mathbf{1}\mathbf{1}^TXB$ in PointNetST.
PointNet is a specialization of graphnets and GraphNetST should be added as a baseline with reasonable adjacency.
Also experiment figures are extremely compact. Try using log scale or other lines to make the gaps wider.

Minor
I am quite confused with the name PointNetST. Authors claim adding one layer of DeepSet layer to a PointNet becomes PointNetST, but I see this as a special DeepSet with a single transmission layer. The convention is B -> B', not A + B -> A'. In this case, A: PointNet, B: DeepSet
Lemma 3 is too trivial.
The paper is not very self contained. Spare few lines of equations to define what are DeepSets and PointNetSeg in the paper and point out the difference since these networks are used throughout the paper extensively without proper mathematical definition.
P.2 power sum multi-symmetric polynomials. "For a vector $x \in R^K$ and a multi-index ..." I think it was moved out of the next paragraph since  the same $x$ is defined again as $x \in R^n$ again in the next sentence.
Also, try using the consistent dimension for x throughout the paper, it confuses the reader.