Sub-quadratic (1+\eps)-approximate Euclidean Spanners, with Applications

Alexandr Andoni, Hengjie ZhangarXiv 2023 · DOI · arXiv

This paper, presented by Alexandr Andoni and Hengjie Zhang, tackles a fundamental problem in high-dimensional geometry: how to represent the distances between $n$ points in Euclidean space using a sparse graph, known as a spanner.

TL;DR

The authors prove that while high-dimensional $(1+\epsilon)$-approximate Euclidean spanners traditionally require nearly quadratic size, they can achieve sub-quadratic size by introducing "non-metric" Steiner points (extra graph nodes that don't correspond to physical points in $\mathbb{R}^d$). They leverage this to provide the first sub-quadratic time $(1+\epsilon)$-approximation algorithm for the Earth Mover Distance (EMD) in high dimensions.

What Problem Does This Paper Address?

In computational geometry, a spanner is a subgraph that preserves distances between points within a small multiplicative factor (the "stretch"). For $n$ points in low-dimensional space, we can easily build spanners with a linear number of edges. However, the "curse of dimensionality" makes this much harder in high dimensions.

Previously, researchers believed that to get a high-accuracy approximation (stretch $1+\epsilon$) in high dimensions, you essentially needed a complete graph with $O(n^2)$ edges. Earlier results only achieved sub-quadratic size for very loose approximations (stretch $\ge 3.4$). The authors ask: Can we achieve high accuracy ($1+\epsilon$ stretch) with sub-quadratic size in high dimensions?

Methods

The paper introduces several novel theoretical and algorithmic techniques:

  1. Non-metric Steiner Points: The authors distinguish between "metric" Steiner points (extra points placed in $\mathbb{R}^d$) and "non-metric" Steiner points (abstract nodes added to the graph). They show that while metric Steiner points cannot break the $\sqrt{2}$ stretch barrier for sub-quadratic graphs, non-metric ones can.
  2. Asymmetric Locality-Sensitive Hashing (LSH): They utilize a sophisticated data-independent LSH scheme (originally from ALRW17). This allows them to group points that are "close" with high probability while ensuring "far" points don't collide too often.
  3. Star Gadgets and FNS Checks: To build the spanner, they connect clusters of points to a central Steiner node (a "star gadget"). To prevent this from creating "shortcuts" (making the graph distance shorter than the real distance), they use a Furthest Neighbor Search (FNS) data structure to verify that no point in a cluster is too far from the others.
  4. Asymmetric Star Gadgets: For undirected spanners, they develop a more complex gadget to ensure that connecting two sets of points doesn't accidentally create illegal shortcuts between points within the same set.

Datasets

As a theoretical computer science paper, it does not use empirical real-world datasets. Instead, the authors use:

  • Synthetic Point Sets: Specifically, random points on the Hamming cube $\{0,1\}^d$ and the unit sphere $S^{d-1}$ to prove lower bounds.
  • Mathematical Proofs: The "evaluation" consists of rigorous proofs of the size and stretch of the proposed graph constructions.

Key Insights and Ideas

  • The $\sqrt{2}$ Barrier: A major "aha" moment is the proof that if Steiner points must reside in $\mathbb{R}^d$, you cannot achieve a stretch better than $\sqrt{2}$ without using $\Omega(n^2)$ edges. This explains why previous attempts were stuck.
  • Bypassing Geometry with Graphs: By allowing Steiner points to be non-metric, the authors essentially "cheat" the geometric constraints of the high-dimensional space, allowing for more efficient connectivity.
  • Directed vs. Undirected Symmetry: The authors find that directed spanners are significantly easier to construct ($n^{2-\Omega(\epsilon^2)}$) than undirected ones ($n^{2-\Omega(\epsilon^3)}$) because they don't have to worry about "backwards" shortcuts.
  • EMD Application: They show that the Earth Mover Distance (Optimal Transport) problem can be reduced to a min-cost flow problem on their spanner. Since their spanner is sub-quadratic, the resulting EMD algorithm is also sub-quadratic.

Key Results

  • Lower Bounds: Proved that for metric Steiner spanners, $\Omega(n^2)$ edges are required for any stretch less than $2$ (Hamming) or $\sqrt{2}$ (Euclidean).
  • Upper Bounds (Directed): Constructed a directed $(1+\epsilon)$-spanner with $n^{2-\Omega(\epsilon^2)}$ edges.
  • Upper Bounds (Undirected): Constructed an undirected $(1+\epsilon)$-spanner with $n^{2-\Omega(\epsilon^3)}$ edges.
  • EMD Speedup: Provided an algorithm to compute $(1+\epsilon)$-approximate EMD in $O(n^{2-\Omega(\epsilon^2)})$ time, breaking the long-standing $O(n^2)$ barrier for high-dimensional optimal transport.

Limitations and Future Work

  • The Exponent: While the size is sub-quadratic, the term subtracted from the exponent ($\Omega(\epsilon^2)$ or $\Omega(\epsilon^3)$) is quite small. For very high precision (small $\epsilon$), the graph size remains very close to $n^2$.
  • Aspect Ratio: The construction time and size currently depend on the aspect ratio $\Delta$ (the ratio of the furthest to closest pair of points), though the authors show how to remove this dependence for the edge count at the cost of more complex construction.
  • Practical Implementation: The algorithms rely on complex LSH and FNS structures. Future work could explore whether these "non-metric" gadgets can be implemented efficiently for real-world high-dimensional clustering or similarity search tasks.

Summary updated

BibTeX
@misc{andoni2023sub,
  author = {Alexandr Andoni and Hengjie Zhang},
  title = {{Sub-quadratic (1+\textbackslash\{\}eps)-approximate Euclidean Spanners, with Applications}},
  year = {2023},
  eprint = {2310.05315},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.05315},
}
Figure