Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddings

这是一份关于论文《Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddings》（基于排序的置换不变嵌入的定量界限）的详细技术总结。

1. 研究背景与问题定义

背景：
在图深度学习（Graph Deep Learning）和集合学习（Learning on Multisets）中，经常需要处理输入数据的排列不变性（Permutation Invariance）。即，对于包含 $n$ 个 $d$ 维点的集合 $X \in \mathbb{R}^{n \times d}$，无论点的顺序如何，输出应保持不变。

核心问题：
现有的方法（如 DeepSets）虽然具有排列不变性，但往往无法满足**轨道分离（Orbit Separation）和双 Lipschitz（Bi-Lipschitz）**性质。

• 轨道分离：如果 $f(X) = f(Y)$，则 $X$ 和 $Y$ 必须属于同一个轨道（即 $Y$ 是 $X$ 的某种排列）。
• 双 Lipschitz 条件：存在常数 $C_1, C_2 > 0$，使得对于任意 $X, Y$：
  $$C_1 \cdot \min_{\sigma \in S_n} \|X - \sigma Y\|_F \le \|f(X) - f(Y)\|_2 \le C_2 \cdot \min_{\sigma \in S_n} \|X - \sigma Y\|_F$$
  其中 $C_2/C_1$ 称为畸变（Distortion）。该条件保证了距离相近/较远的轨道在嵌入空间中也被映射为相近/较远的向量，这对度量学习（如最近邻搜索、聚类）至关重要。

研究对象：
论文聚焦于由 [BHS25] 提出的基于排序的嵌入函数 $\beta_A$：
$$\beta_A(X) := \begin{pmatrix} \downarrow(Xa_1) \\ \vdots \\ \downarrow(Xa_D) \end{pmatrix}$$
其中 $A \in \mathbb{R}^{d \times D}$ 是投影矩阵，$\downarrow(\cdot)$ 表示对向量进行非递减排序。该函数通过 $D$ 个独立的一维投影并排序来实现排列不变性。

现有研究的缺口：

1. 注入性（Injectivity）的维度界限不明：之前已知对于足够大的 $D$ 和一般位置的 $A$，$\beta_A$ 是单射，但最优的 $D$ 值未知。
2. 双 Lipschitz 常数未知：缺乏对映射畸变（Distortion）的具体估计，特别是其如何依赖于点数 $n$ 和维度 $d$。

---

2. 主要贡献与方法论

本文在解决上述两个缺口方面取得了实质性进展：

A. 嵌入维度的界限（Injectivity Bounds）

论文重新审视并改进了 $\beta_A$ 实现轨道分离所需的投影数量 $D$ 的上下界。

• 上界改进（Theorem 4）：

  • 证明了如果 $A$ 是**全火花（Full Spark）**矩阵（即任意 $d$ 列线性无关），且满足 $D \ge n(d-1) + 1$，则 $\beta_A$ 是单射。
  • 这比之前的结果（如 [RD23] 中的 $D \sim n^2$）有了显著改进，将 $D$ 的依赖关系从 $n$ 的二次方降低到了线性方。
  • 对应的嵌入维度为 $nD \sim n^2(d-1)$。

• 下界证明（Theorem 5）：

  • 证明了如果 $D$ 满足 $\lceil D/(d-1) \rceil \le \log_2(n) + 1$，则对于任意 $A$，$\beta_A$ 都不是单射。
  • 这意味着实现单射的最小 $D$ 至少是 $\Omega(d \log n)$ 量级。
  • 因此，$\beta_A$ 的嵌入维度 $nD$的下界为$\Omega(d \cdot n \log n)$。

• 其他映射的维度优化：

  • 针对线性投影后的映射 $\bar{\beta}_{A,L}$ 和另一种投影映射 $\delta_{A,B}$，论文证明了在 $D \ge (2n-1)d$ 时即可实现单射。这比之前已知的 $2nd+1$略有改进，且更接近理论下界$nd$。

B. 双 Lipschitz 畸变界限（Distortion Bounds）

论文分析了映射的畸变 $C_2/C_1$ 如何随 $n$ 和 $d$ 变化。

• 上界构造（Theorem 14, 15）：

  • 通过构造特定的投影矩阵 $A$（包括确定性构造 $d=2$ 和随机高斯/球面均匀采样构造），证明了可以控制畸变。
  • 关键结果：当 $D$ 足够大（例如 $D \sim n^4 d$ 或 $D \sim n^2 d \log n$）时，$\beta_A$ 的畸变以 $O(n^2)$ 为界，且完全独立于维度 $d$。
  • 这一结果将切片 Wasserstein 距离（Sliced Wasserstein Distance）的蒙特卡洛近似与真实 Wasserstein 距离之间的定量关系进行了明确化。

• 下界证明（Theorem 18）：

  • 证明了对于任何投影矩阵 $A$，$\beta_A$ 的畸变不可能优于 $\Omega(\sqrt{n})$。
  • 这意味着无论 $D$ 多大，畸变至少随 $\sqrt{n}$ 增长。这揭示了基于排序的嵌入在 $n$ 很大时的内在局限性。

• 降维投影的推广（Theorem 20）：

  • 利用**草图（Sketching）**技术，证明了可以通过线性映射 $L$ 将 $\beta_A$ 的维度从 $nD$降低到$O(nd)$，同时保持与原始$\beta_A$ 相似的双 Lipschitz 畸变（$O(n^2)$）。这使得该方法在实际应用中更加可行。

---

3. 关键结果总结

特性	映射类型	结果/界限	备注
单射性 (Injectivity)	$\beta_A$	上界：$D \ge n(d-1)+1$ 下界：$D = \Omega(d \log n)$	嵌入维度 $M \sim n^2 d$
单射性 (Injectivity)	$\delta_{A,B}, \bar{\beta}_{A,L}$	上界：$D \ge (2n-1)d$	嵌入维度 $M \sim nd$，接近最优
畸变 (Distortion)	$\beta_A$	上界：$O(n^2)$ (独立于 $d$)	需 $D \sim n^4 d$ 或 $n^2 d$
畸变 (Distortion)	$\beta_A$	下界：$\Omega(\sqrt{n})$	任何 $A$ 均无法突破此界限
降维后畸变	$\beta_{A,L}$	$O(n^2)$	嵌入维度可降至 $O(nd)$

数值实验发现：
对于较小的 $n$ 和 $d$，理论界限通常是次优的（Suboptimal）。例如，在某些参数下，实际所需的 $D$ 小于理论推导的 $n(d-1)+1$ 即可实现轨道分离。

---

4. 意义与影响

1. 理论完善：填补了基于排序的置换不变嵌入在单射性维度和双 Lipschitz 常数方面的理论空白，提供了更精确的定量界限。
2. 指导实践：
   • 为图神经网络和集合学习中的特征提取器设计提供了理论依据。
   • 证明了可以通过增加投影数量 $D$ 来换取更好的几何保持性（畸变控制），同时给出了具体的 $D$ 与畸变之间的权衡关系。
   • 提出的降维策略（Theorem 20）使得高维嵌入在实际计算中变得可行，同时保留了良好的度量性质。
3. 连接 Wasserstein 距离：论文清晰地建立了 $\beta_A$ 与切片 Wasserstein 距离（Sliced Wasserstein Distance）之间的联系，证明了该嵌入是经验测度上切片 2-Wasserstein 距离的有限维蒙特卡洛近似，并给出了其近似质量的定量保证。
4. 揭示局限性：通过 $\Omega(\sqrt{n})$ 的下界，指出了基于排序的嵌入在处理大规模点集时的固有瓶颈，为未来研究更优的不变嵌入方法指明了方向。

5. 结论

该论文系统地量化了基于排序的置换不变嵌入的性能。主要结论是：虽然可以通过增加投影维度实现单射并控制畸变在 $O(n^2)$ 范围内（独立于 $d$），但畸变无法低于 $\Omega(\sqrt{n})$。此外，通过巧妙的线性投影，可以在保持低畸变的同时将嵌入维度压缩至线性级别 $O(nd)$，为实际机器学习应用提供了强有力的理论支持和实用方案。