# Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddings

arXiv: https://arxiv.org/abs/2510.22186 · HTML: https://mlsanity.com/paper/2510.22186/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 60 references that are in the map.
- First posted on arXiv 25 Oct 2025.

## Builds on (most cited first, 19 of 19)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [On the Expressive Power of Geometric Graph Neural Networks](https://mlsanity.com/paper/2301.09308/) (2023)
- [Sliced Wasserstein Kernel for Persistence Diagrams](https://mlsanity.com/paper/1706.03358/) (2017)
- [Universal Approximation of Functions on Sets](https://mlsanity.com/paper/2107.01959/) (2021)
- [Low Dimensional Invariant Embeddings for Universal Geometric Learning](https://mlsanity.com/paper/2205.02956/) (2022)
- [Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theorem](https://mlsanity.com/paper/2306.06529/) (2023)
- [Permutation Invariant Representations with Applications to Graph Deep Learning](https://mlsanity.com/paper/2203.07546/) (2022)
- [Group-invariant max filtering](https://mlsanity.com/paper/2205.14039/) (2022)
- [Universal Representation of Permutation-Invariant Functions on Vectors and Tensors](https://mlsanity.com/paper/2310.13829/) (2023)
- [FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network](https://mlsanity.com/paper/2410.09118/) (2024)
- [Fourier Sliced-Wasserstein Embedding for Multisets and Measures](https://mlsanity.com/paper/2504.02544/) (2025)
- [Polynomial Width is Sufficient for Set Representation with High-dimensional Features](https://mlsanity.com/paper/2307.04001/) (2023)
- [Max filtering with reflection groups](https://mlsanity.com/paper/2212.05104/) (2022)
- [Stability of sorting based embeddings](https://mlsanity.com/paper/2410.05446/) (2024)
- [Bi-Lipschitz Ansatz for Anti-Symmetric Functions](https://mlsanity.com/paper/2503.04263/) (2025)
- [The stability of generalized phase retrieval problem over compact groups](https://mlsanity.com/paper/2505.04190/) (2025)
- [On the (Non) Injectivity of Piecewise Linear Janossy Pooling](https://mlsanity.com/paper/2505.20150/) (2025)

## Built on by (most cited first, 2 of 2)

- [Toward bilipshiz geometric models](https://mlsanity.com/paper/2511.11735/) (2025)
- [Towards Metric-Faithful Neural Graph Matching](https://mlsanity.com/paper/2605.06588/) (2026)

## Abstract (arXiv)

We study permutation-invariant embeddings of d-dimensional point sets, which are defined by sorting D independent one-dimensional projections of the input. Such embeddings arise in graph deep learning where outputs should be invariant to permutations of graph nodes. Previous work showed that for large enough D and projections in general position, this mapping is injective, and moreover satisfies a bi-Lipschitz condition. However, two gaps remain: firstly, the optimal size D required for injectivity is not yet known, and secondly, no estimates of the bi-Lipschitz constants of the mapping are known. In this paper, we make substantial progress in addressing both of these gaps. Regarding the first gap, we improve upon the best known upper bounds for the embedding dimension D necessary for injectivity, and also provide a lower bound on the minimal injectivity dimension. Regarding the second gap, we construct matrices of projection vectors, so that the bi-Lipschitz distortion of the mapping depends quadratically on the number of points n, and is completely independent of the dimension d. We also show that for any choice of projection vectors, the distortion of the mapping will never be better than a bound proportional to the square root of n. Finally, we show that similar guarantees can be provided even when linear projections are applied to the mapping to reduce its dimension.