Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddings PubID: pubid: 0000–0000 © 2025 IEEE
Nadav Dym, Matthias Wellershoff, Efstratios Tsoukanis, Daniel Levy, Radu Balan · 2025
Read Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddings PubID: pubid: 0000–0000 © 2025 IEEE by Nadav Dym, Matthias Wellershoff, Efstratios Tsoukanis, Daniel Levy, Radu Balan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-22186.txt.
Introduction
Nadav Dym, Matthias Wellershoff, Efstratios Tsoukanis, Daniel Levy, and Radu Balan study a disarmingly simple way to fingerprint a cloud of points. Project the points onto several lines, sort each list of shadows, and stack the sorted lists into one vector. Shuffling the points changes nothing, which makes the trick attractive for graph learning, where node order is arbitrary.
Earlier work showed that with enough well-aimed projections the fingerprint is unique and distorts distances only within fixed bounds. Two gaps remained: how many projections are truly needed, and how large the distortion can get. The team improves the upper bound on the required number and adds a lower bound, then constructs projection sets whose distortion can be estimated concretely. The results turn a neat existence theorem into engineering numbers.
Catalog record
| CREATOR | Nadav Dym, Matthias Wellershoff, Efstratios Tsoukanis, Daniel Levy, Radu Balan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 92 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-22186
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddings PubID: pubid: 0000–0000 © 2025 IEEE Nadav Dym, Matthias Wellershoff, Efstratios Tsoukanis, Daniel Levy, Radu Balan Abstract We study the sorting-based embedding β 𝐀 : ℝ n × d → ℝ n × D \beta_{\mathbf{A}}:\mathbb{R}^{n\times d}\to\mathbb{R}^{n\times D} , 𝐗 ↦ ↓ ( 𝐗𝐀 ) \mathbf{X}\mapsto{\downarrow}(\mathbf{X}\mathbf{A}) , where ↓ \downarrow denotes column wise sorting of matrices. 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 D and appropriate 𝐀 \mathbf{A} , the mapping β 𝐀 \beta_{\mathbf{A}} is injective, and moreover satisfies a bi-Lipschitz condition. However, two gaps remain: firstly, the optimal size D 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 D necessary for injectivity, and also provide a lower bound on the minimal injectivity dimension. Regarding the second gap, we construct matrices 𝐀 \mathbf{A} , so that the bi-Lipschitz distortion of β 𝐀 \beta_{\mathbf{A}} depends quadratically on n n , and is completely independent of d d . We also show that the distortion of β 𝐀 \beta_{\mathbf{A}} is necessarily at least in Ω ( n ) \Omega(\sqrt{n}) . Finally, we provide similar results for variants of β 𝐀 \beta_{\mathbf{A}} obtained by applying linear projections to reduce the output dimension of β 𝐀 \beta_{\mathbf{A}} . I Introduction Consider the action of the symmetric group S_{n} on the matrices \mathbb{R}^{n\times d} by row permutation. We are interested in constructing functions f:\mathbb{R}^{n\times d}\to\mathbb{R}^{M} that satisfy three main requirements: 1. Permutation invariance. f(\sigma\mathbf{X})=f(\mathbf{X}) for all \sigma\in S_{n} , \mathbf{X}\in\mathbb{R}^{n\times d} . 2. Orbit separation. f(\mathbf{X})=f(\mathbf{Y}) implies \mathbf{X}\in S_{n}\mathbf{Y} for all \mathbf{X},\mathbf{Y}\in\mathbb{R}^{n\times d} . 3. Bi-Lipschitz condition 1 1 1 Here, \lVert\cdot\rVert_{F} denotes the Frobenius norm. . There exist constants C_{1},C_{2}>0 such that, for all \mathbf{X},\mathbf{Y}\in\mathbb{R}^{n\times d} , C_{1}\cdot\min_{\sigma\in S_{n}}\lVert\mathbf{X}-\sigma\mathbf{Y}\rVert_{\mathrm{F}}\leq\lVert f(\mathbf{X})-f(\mathbf{Y})\rVert_{2}\leq C_{2}\cdot\min_{\sigma\in S_{n}}\lVert\mathbf{X}-\sigma\mathbf{Y}\rVert_{\mathrm{F}}. (1) The motivation for these requirements comes from permutation-invariant learning on multisets. This is a common setting where one wishes to “learn” a permutation-invariant function q(\mathbf{X}) , using a parametric family of functions f_{\theta}(\mathbf{X}) which is also permutation-invariant. A simple yet powerful and popular method to do this is the DeepSets model [ ZKR+17 ] . It applies a neural network h_{\theta} to each of the rows \mathbf{x}_{i}\in\mathbb{R}^{d} of \mathbf{X}\in\mathbb{R}^{n\times d} , and then sums over all rows to obtain permutation invariance: f_{\theta}(\mathbf{X})=\sum_{j=1}^{n}h_{\theta}(\mathbf{x}_{i}). It was shown in [ AGA+23 , TW24 , WYL+24 , ZKR+17 ] that, if constructed correctly, the DeepSets model also has the orbit separation property. This orbit separation result guarantees that any permutation-invariant function can be approximated by a concatenation of a DeepSets model with an additional neural network [ WFE+22 , ZKR+17 ] and is also used to provide maximally expressive graph neural networks [ MBHSL19 , XHLJ19 ] . Recently, the bi-Lipschitz condition defined above has received more attention in the invariant learning community. The motivation for this requirement is controlling the quality of orbit separation, so that we can guarantee that orbits which are close to/far from each other are mapped to close/far vectors. Such properties can be useful, for example, for metric based learning tasks such as nearest neighbor search or clustering, as discussed in [ CIM24 ] . Unfortunately, the DeepSets model cannot be bi-Lipschitz [ AGA+23 ] . Recent work suggests [ RD25 ] that this is also the case for Janossy pooling: a generalization of DeepSets which sums over all k -tuples of rows of \mathbf{X} . These results inspired research to suggest new permutation-invariant functions which do have the bi-Lipschitz properties. Among the most promising bi-Lipschitz permutation-invariant functions suggested in the literature is the function proposed in [ BHS22 ] , \beta_{\mathbf{A}}:\mathbb{R}^{n\times d}\to\mathbb{R}^{n\times D}\simeq\mathbb{R}^{nD} , defined as \beta_{\mathbf{A}}(\mathbf{X}):=\begin{pmatrix}|&&|\\ {\downarrow}({\mathbf{X}\mathbf{a}_{1}})&\dots&{\downarrow}({\mathbf{X}\mathbf{a}_{D}})\\ |&&|\end{pmatrix},\qquad\mathbf{X}\in\mathbb{R}^{n\times d}, (2) where {\downarrow}({\cdot}):\mathbb{R}^{n}\to\mathbb{R}^{n} denotes sorting vectors in a non-decreasing order and (\mathbf{a}_{k})_{k=1}^{D}\in\mathbb{R}^{d} are the columns of \mathbf{A}\in\mathbb{R}^{d\times D} . It has been shown in [ BHS22 ] that, for large enough D and generic \mathbf{A} , this function is both orbit separating and bi-Lipschitz. The usefulness of this bi-Lipschitz mapping and the closely related FSW embedding [ AD25 ] for permutation-invariant learning tasks was demonstrated in [ DD25 , SDDA24 ] . In [ DLM25 ] , a variant of \beta_{\mathbf{A}} is proposed which gives bi-Lipschitz invariants for the alternating group. Other bi-Lipschitz permutation-invariant mappings include the max filter approach [ CIMP24 ] and group invariants based on coorbits [ BT23a ] . To enable a theoretically informed choice between the different bi-Lipschitz permutation-invariant functions suggested in the literature, a more refined analysis is necessary. That is, a successful bi-Lipschitz invariant function f should satisfy three additional requirements: 4. Efficient computability. f can be computed in polynomial time with respect to n and d , where, again, the lower the computational burden the better. 5. Small embedding dimension. M is as small as possible. It is known that necessarily M\geq n\cdot d [ JBM+23 , AGA+23 ] and so one would hope for M to be as close to this lower bound as possible. 6. Small distortion. The distortion C_{2}/C_{1} (where C_{1},C_{2}>0 are the optimal constants satisfying equation ( 1 )) is as close to one as possible. The computational complexity of the function \beta_{\mathbf{A}} is well understood. Our goal in this paper is to study the embedding dimension and distortion of the function \beta_{\mathbf{A}} , improving upon previous results obtained on this topic. We will now introduce some notation, and then review previous results, and give an overview of our main results. I-A Notation Our convention for the natural numbers is \mathbb{N}=\{1,2,\dots\} . Given a natural number n\in\mathbb{N} , we denote [n]:=\{1,\dots,n\} . The cardinality (i.e., number of elements) of a finite set S is denoted by \lvert S\rvert . The complement of a subset T\subset S is denoted by T^{\mathrm{c}}:=S\setminus T . Additionally, we denote the characteristic function of T by K_{T} , x\in S\mapsto K_{T}(x):=\begin{cases}1&\mbox{if }x\in T,\\ 0&\mbox{else}.\end{cases} The n -dimensional vector of zeros is denoted by \mathbf{0}_{n}=(0~\dots~0)\in\mathbb{R}^{n} while the n -dimensional vector of ones is denoted by \mathbf{1}_{n}=(1~\dots~1)\in\mathbb{R}^{n} . Similarly, the m\times n matrix of zeros is denoted by \mathbf{0}_{m\times n}\in\mathbb{R}^{m\times n} . The two-norm of a vector \mathbf{x}=(x_{1}~\dots~x_{n})\in\mathbb{R}^{n} is \lVert\mathbf{x}\rVert_{2}=\left(\sum_{i=1}^{n}x_{i}^{2}\right)^{1/2}. The unit sphere in n dimensions is S^{n-1}=\{\mathbf{x}\in\mathbb{R}^{n}\,|\,\lVert\mathbf{x}\rVert_{2}=1\} . The singular values of a matrix \mathbf{A}\in\mathbb{R}^{m\times n} are denoted by \sigma_{1}(\mathbf{A}),\dots,\sigma_{\min\{m,n\}}(\mathbf{A}) and assumed to be ordered non-increasingly; i.e., \sigma_{1}(\mathbf{A})\geq\dots\geq\sigma_{\min\{m,n\}}(\mathbf{A}). The Frobenius norm of a matrix \mathbf{A}\in\mathbb{R}^{m\times n} is \lVert\mathbf{A}\rVert_{\mathrm{F}}=\left(\sum_{i=1}^{m}\sum_{j=1}^{n}A_{ij}^{2}\right)^{1/2}=\left(\sum_{i=1}^{\min\{m,n\}}\sigma_{1}(\mathbf{A})^{2}\right)^{1/2}. We say that a wide matrix \mathbf{A}\in\mathbb{R}^{m\times n} , m\leq n , is full spark if every set of m columns of \mathbf{A} is linearly independent. Given an index set I\subset[n] and a matrix \mathbf{A}\in\mathbb{R}^{m\times n} , we let \mathbf{A}(I)\in\mathbb{R}^{m\times\lvert I\rvert} be the matrix obtained from \mathbf{A} by discarding all columns whose indices are not in I . We write V\simeq W if two vector spaces, V and W , are canonically isomorphic. If f(x) , g(x) are two families of objects parametrized by x\in S , where S is some set, then we write f\lesssim g if