Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddings

1. Planteamiento del Problema

El artículo aborda el problema de construir incrustaciones (embeddings) invariantes a permutaciones para conjuntos de puntos de dimensión $d$ (representados como matrices $X \in \mathbb{R}^{n \times d}$). En el aprendizaje profundo de grafos y el aprendizaje en multiconjuntos, es crucial que las funciones aprendidas sean invariantes al reordenamiento de los nodos (filas de la matriz).

El objetivo es definir una función $f: \mathbb{R}^{n \times d} \to \mathbb{R}^M$ que satisfaga tres condiciones principales:

1. Invarianza a permutaciones: $f(\sigma X) = f(X)$ para cualquier permutación $\sigma \in S_n$.
2. Separación de órbitas (Inyectividad): $f(X) = f(Y)$ implica que $X$ y $Y$ son permutaciones entre sí (es decir, pertenecen a la misma órbita bajo $S_n$).
3. Condición Bi-Lipschitz: La función debe preservar la distancia relativa entre órbitas. Es decir, existen constantes $C_1, C_2 > 0$ tales que:
   $$C_1 \cdot \text{dist}(X, Y) \leq \|f(X) - f(Y)\|_2 \leq C_2 \cdot \text{dist}(X, Y)$$
   donde $\text{dist}(X, Y) = \min_{\sigma \in S_n} \|X - \sigma Y\|_F$ es la distancia entre órbitas.

El trabajo se centra en el mapa de incrustación $\beta_A$ propuesto previamente, que se basa en proyectar las filas de $X$ en $D$ direcciones unidimensionales y ordenar los resultados:
$$\beta_A(X) := \begin{pmatrix} \downarrow(Xa_1) \\ \vdots \\ \downarrow(Xa_D) \end{pmatrix}$$
donde $\downarrow(\cdot)$ denota el ordenamiento no decreciente y $A \in \mathbb{R}^{d \times D}$ contiene los vectores de proyección.

Brechas conocidas:

• No se conocía el tamaño óptimo de $D$ (dimensión de proyección) necesario para garantizar la inyectividad.
• No existían estimaciones cuantitativas de las constantes de distorsión bi-Lipschitz ($C_2/C_1$) ni de su dependencia con $n$ (número de puntos) y $d$ (dimensión).

---

2. Metodología

Los autores emplean una combinación de geometría algebraica real, teoría de matrices aleatorias y análisis de distorsión métrica.

• Análisis de Inyectividad: Utilizan propiedades de matrices "full spark" (donde cualquier subconjunto de $d$ columnas es linealmente independiente) y técnicas de geometría algebraica (conjuntos semialgebraicos y el teorema del testigo finito) para determinar los límites inferiores y superiores de $D$ necesarios para la separación de órbitas.
• Acotación de Distorsión: Introducen el concepto de uniformidad proyectiva para acotar la constante de Lipschitz inferior. Analizan la relación entre la distancia de Wasserstein cortada (sliced Wasserstein) y la distancia de Wasserstein completa, ya que $\beta_A$ puede interpretarse como una aproximación Monte Carlo de la distancia de Wasserstein cortada.
• Construcciones Probabilísticas y Deterministas: Proponen tres métodos para construir la matriz $A$:
  1. Una construcción determinista para $d=2$.
  2. Matrices aleatorias Gaussianas.
  3. Vectores de columna muestreados uniformemente en la esfera unitaria.
• Reducción de Dimensión: Utilizan argumentos de sketching (proyección aleatoria) para demostrar que se puede reducir la dimensión de salida sin perder significativamente la propiedad bi-Lipschitz.

---

3. Contribuciones Clave y Resultados

A. Límites de Dimensión de Incrustación (Inyectividad)

El artículo refina drásticamente los límites conocidos para la dimensión $D$ necesaria para que $\beta_A$ sea inyectivo:

1. Límite Superior Mejorado: Se demuestra que si $A$ es una matriz full spark y $D \geq n(d-1) + 1$, entonces $\beta_A$ es inyectivo. Esto mejora significativamente el límite anterior que crecía cuadráticamente en $n$ (del tipo $O(n^2 d)$).
2. Límite Inferior: Se prueba que si $D \leq (d-1)(\log_2 n + 1)$, el mapa no puede ser inyectivo para ninguna elección de $A$. Esto establece que la dimensión de incrustación total ($nD$) debe ser al menos $\Omega(d \cdot n \log n)$.
3. Variantes Lineales: Para las variantes con proyección lineal posterior ($\delta_{A,B}$ y $\bar{\beta}_{A,L}$), se demuestra que la inyectividad se logra con una dimensión de proyección $D \geq (2n-1)d$, mejorando el límite previo de $2nd+1$.

B. Límites de Distorsión Bi-Lipschitz

El trabajo proporciona las primeras estimaciones cuantitativas de la distorsión:

1. Límite Superior de Distorsión (Construcciones Positivas):

   • Se construyen matrices $A$ (deterministas para $d=2$ y probabilísticas para $d>2$) tales que la distorsión de $\beta_A$ escala como $O(n^2)$.
   • Crucialmente, esta distorsión es independiente de la dimensión $d$.
   • Para lograr esto, se requiere un número de proyecciones $D$ del orden de $O(n^4 d)$ (Gaussianas) o $O(n^2 d \log n)$ (esfera unitaria).
   • Se demuestra que mediante una proyección lineal aleatoria ($\beta_{A,L}$), se puede mantener una distorsión similar ($O(n^2)$) con una dimensión de incrustación final proporcional a $nd$ (casi óptima).

2. Límite Inferior Universal (Imposibilidad):

   • Se demuestra un teorema fundamental: para cualquier elección de vectores de proyección $A$, la distorsión de $\beta_A$ no puede ser mejor que $\Omega(\sqrt{n})$.
   • Esto implica que existe una brecha entre el límite inferior teórico ($\sqrt{n}$) y los límites superiores construidos ($n^2$), dejando abierta la pregunta sobre la distorsión óptima exacta.

C. Conexión con la Distancia de Wasserstein

El artículo establece un vínculo directo entre estas incrustaciones y la distancia de Wasserstein cortada (Sliced Wasserstein).

• La distorsión de $\beta_A$ corresponde a la calidad de la aproximación de Monte Carlo de la distancia de Wasserstein 2.
• Los resultados implican que la distancia de Wasserstein cortada muestreada proporciona una aproximación bi-Lipschitz de la distancia de Wasserstein completa para medidas empíricas de tamaño $n$, con una distorsión de orden $\tilde{O}(n^2)$.
• También se confirma que no es posible obtener una equivalencia bi-Lipschitz con constantes uniformes en $n$ para medidas generales, lo cual es consistente con resultados previos en la literatura.

---

4. Significado e Impacto

Este trabajo es fundamental para la teoría del aprendizaje profundo invariante a simetrías por varias razones:

1. Fundamentación Teórica: Proporciona los primeros límites cuantitativos rigurosos sobre la eficiencia y la estabilidad de las incrustaciones basadas en ordenamiento, un componente clave en arquitecturas modernas de GNN (Graph Neural Networks) y aprendizaje en multiconjuntos.
2. Optimización de Recursos: Al reducir el requisito de $D$ de crecimiento factorial/superexponencial a polinomial (lineal o cuadrático en $n$), hace viables teóricamente estas incrustaciones para problemas de mayor escala.
3. Guía de Diseño: La distinción entre la dimensión necesaria para la inyectividad ($O(nd)$) y la necesaria para una buena distorsión ($O(n^2d)$) ofrece a los investigadores una hoja de ruta clara para equilibrar la eficiencia computacional con la calidad de la representación métrica.
4. Aplicabilidad Práctica: Los resultados sobre la reducción de dimensión mediante sketching sugieren que es posible implementar estas incrustaciones en espacios de baja dimensión sin sacrificar excesivamente la capacidad de separación de órbitas, lo cual es vital para la implementación en hardware y aplicaciones de tiempo real.

En resumen, el artículo cierra brechas teóricas importantes sobre la viabilidad y los límites de las incrustaciones invariantes a permutaciones basadas en ordenamiento, estableciendo un nuevo estándar para el análisis de distorsión en este campo.