Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddings
Pith reviewed 2026-05-18 04:36 UTC · model grok-4.3
The pith
Sorting-based embeddings of point sets have bi-Lipschitz distortion quadratic in the number of points and independent of dimension.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The paper shows that suitable matrices of projection vectors exist making the distortion of the sorted-projection mapping quadratic in n and independent of d, while proving that sqrt(n) is a lower bound on the achievable distortion for any projections. It also advances the understanding of the minimal embedding dimension D required for injectivity.
What carries the argument
Matrices of projection vectors chosen so that the sorted one-dimensional projections control the bi-Lipschitz constants quadratically in n.
If this is right
- The embedding dimension D can be chosen smaller than previously known while guaranteeing injectivity.
- Bi-Lipschitz constants depend only on n, allowing use in high-dimensional settings without degradation.
- Further linear projections can reduce the output dimension while preserving the distortion bounds.
- Any sorting-based embedding must have distortion at least proportional to sqrt(n).
Where Pith is reading between the lines
- These bounds suggest that sorting-based methods can be practical for graph learning tasks even as the number of nodes grows, provided n is not too large.
- Connections to other invariant representations in machine learning may benefit from similar quantitative analyses.
- Testing the constructions on real datasets could reveal if the quadratic bound is tight in practice.
Load-bearing premise
The analysis assumes that the projection vectors are in general position so that the sorted values distinguish different point configurations.
What would settle it
An explicit set of n points and projection vectors where the ratio of distances in the embedded space to original distances exceeds c n^2 for the constructed matrices, or falls below c sqrt(n) for the lower bound.
read the original abstract
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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies sorting-based permutation-invariant embeddings of n-point sets in R^d, obtained by sorting D one-dimensional projections. It improves known upper bounds on the minimal embedding dimension D for injectivity and supplies a matching lower bound. Explicit matrix constructions are given for the projection directions such that the bi-Lipschitz distortion is O(n^2) and independent of d; a general lower bound of Omega(sqrt(n)) is shown to hold for any choice of directions. Similar guarantees are extended to the case of an additional linear dimension reduction on the embedding.
Significance. If the stated constructions and distortion bounds hold, the work supplies the first quantitative bi-Lipschitz estimates for this family of embeddings, with the key feature that the distortion factor is independent of ambient dimension d. The explicit matrix constructions and the matching-style lower bound constitute a concrete advance for the theoretical analysis of permutation-invariant models used in graph neural networks.
major comments (2)
- [§4.2] §4.2, Construction 1: the claimed O(n^2) upper bound on the bi-Lipschitz constant is derived from the sorted projections; the proof sketch must explicitly track the dependence on the minimal separation of the projected points to confirm that the constant is indeed independent of d and quadratic in n.
- [Theorem 5.1] Theorem 5.1: the Omega(sqrt(n)) lower bound for arbitrary projection directions is established via a worst-case configuration of n points; it should be clarified whether the same order holds uniformly over all point sets or only in the worst case, as this affects the tightness claim relative to the upper bound.
minor comments (2)
- [§2] The notation for the permutation-invariant metric on unordered point sets (likely a sorted Hausdorff or matching distance) is introduced without a numbered definition; adding an explicit equation would improve readability.
- [Figure 2] Figure 2 caption: the plotted distortion values for the constructed matrices should include error bars or explicit constants to allow direct comparison with the O(n^2) and Omega(sqrt(n)) analytic bounds.
Simulated Author's Rebuttal
We thank the referee for their positive evaluation and constructive comments. We address the two major comments point by point below and will revise the manuscript accordingly to improve clarity.
read point-by-point responses
-
Referee: [§4.2] §4.2, Construction 1: the claimed O(n^2) upper bound on the bi-Lipschitz constant is derived from the sorted projections; the proof sketch must explicitly track the dependence on the minimal separation of the projected points to confirm that the constant is indeed independent of d and quadratic in n.
Authors: We thank the referee for this observation. The proof in §4.2 relies on our explicit matrix construction of projection directions, which guarantees that the minimal separation δ among the sorted one-dimensional projections satisfies δ ≥ c/n for a positive constant c independent of d. This separation bound directly yields the claimed O(n²) bi-Lipschitz distortion that is independent of ambient dimension d. In the revised manuscript we will expand the proof sketch to derive and track this lower bound on δ explicitly, making the dependence on n and independence from d fully transparent. revision: yes
-
Referee: [Theorem 5.1] Theorem 5.1: the Omega(sqrt(n)) lower bound for arbitrary projection directions is established via a worst-case configuration of n points; it should be clarified whether the same order holds uniformly over all point sets or only in the worst case, as this affects the tightness claim relative to the upper bound.
Authors: The referee correctly identifies that the Ω(√n) lower bound in Theorem 5.1 is established existentially: for any choice of projection directions there exists a worst-case configuration of n points for which the distortion is at least Ω(√n). The bound does not hold uniformly for every point set; some configurations may exhibit smaller distortion. We will revise the statement of Theorem 5.1 and the surrounding discussion to make this distinction explicit. This clarification does not alter the contribution: the O(n²) upper bound holds uniformly over all point sets, while the lower bound shows that no choice of directions can improve the n-dependence below √n in the worst case. revision: yes
Circularity Check
No significant circularity detected
full rationale
The paper's central results consist of explicit constructions of projection matrices yielding bi-Lipschitz distortion quadratic in n and independent of d, together with a general lower bound of order sqrt(n) that holds for arbitrary directions. These rest on direct geometric arguments using general-position properties of linear projections and a well-defined permutation-invariant metric on unordered point sets. No load-bearing step reduces by construction to a fitted parameter, self-definition, or self-citation chain; the quantitative bounds are derived from the stated matrix constructions and standard linear-algebra facts without circular reduction to the paper's own inputs.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Projections are in general position
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.