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

We first give indication that it is impossible to obtain $(1+\epsilon)$ approximation with a sub-quadratic-sized spanner even if we allow Steiner points. In particular, we prove the following two lower bounds for the Hamming metric and Euclidean metric, respectively.

Next, we show that if we consider a more general class of Steiner spanners, where we allow graph nodes that do not correspond to points $\in\mathbb{R}^{d}$, we can indeed obtain $(1+\epsilon)$-spanners of subquadratic size, answering positively the question from above. We refer to such spanners as non-metric Steiner spanners.

Furthermore, we distinguish two types of non-metric Steiner spanners: undirected, and directed. In particular, a directed spanner $H$ for sets $P,Q$ with stretch $c>1$ is a directed graph with vertex-set $P\cup Q\cup S$, satisfying for all $p\in P,q\in Q$:

where $\vec{\mathrm{d}}_{H}(p,q)$ as the shortest path from $p\in P$ to $q\in Q$. When we have one dataset $P$, we take $Q$ to be a copy of $P$. Note that directed spanner only makes sense for non-metric Steiner version.

While the directed spanner turns out to be already sufficient for our application below, there other applications which may require an undirected graph (as many graph problems are easier for undirected graphs). Thus, we also show that one can construct an undirected spanner, albeit the parameters are less efficient than for the directed case.

We highlight one concrete algorithmic application of our spanner construction. In particular, we consider the problem of Earth-Mover Distance in the high-dimensional spaces: given two $n$-points sets $A,B\subset\mathbb{R}^{d}$, compute the smallest cost bi-chromatic matching $\operatorname{argmin}_{\pi:A\to B}\tfrac{1}{n}\sum_{a\in A}\|a-\pi(a)\|$ where $\pi$ ranges over all permutations. In different communities, the EMD problem is also termed optimal transport, Wasserstein distance, Monge-Kantarovich, and others.²²2Formally, all these are defined over distributions over $n$ points, equivalently weighted pointsets. All our results apply to the weighted version as well, and hence we ignore the difference for simplicity of presentation.

The basic problem is to compute the (near-) optimal $\pi$ efficiently. When dimension $d$ is small, a long progression of results, starting from [Vai89] and culminating in [KNP19] yielded an $(1+\epsilon)$-approximate algorithm running in time $\widetilde{O}(n)\cdot\epsilon^{O(d)}$.

Another line of research concerns the general metric (or cost) setting, i.e., more general than the Euclidean setting. Here, the best possible runtime is $\sim n^{2}$, which is necessary in general. One approach uses Sinkhorn iteration algorithm to obtain additive error of $\epsilon\max_{p,q\in A,B}\|p-q\|$ [Cut13, ANWR17]. A different approach uses faster linear programming algorithms to solve the standard bi-partite matching in time near-linear in the size of the (complete) bi-partite graph on $A\times B$ [VDBLL⁺21, CKL⁺22] — this approach can obtain an exact result.

Nevertheless, the most common setting for general cost is still the high-dimensional Euclidean (or $\ell_{1}$) space (see, e.g., the experiments from [ANWR17], or this most recent paper [ARSS23]). In this setting, one can hope for runtime $\ll n^{2}$, as the input size is only $O(nd)$.

The best algorithm for the high-dimensional setting obtains runtime of $O(n^{1+O(1/c^{2})})$ for $c$-approximation, for $c\geq 3.4$. This follows from using the spanner of [HPIS13] in the following general approach. One can take the pointset $A\cup B$ and build a spanner $H$ on it. Then the EMD problem reduces to solving the “graphical EMD” case: EMD under the metric defined by the shortest path distance in $H$. The latter problem is equivalent to the problem of uncapacitated min-cost flow, or transshipment problem. This problem in turn can be solved in time near-linear in the graph size [She17, ASZ20, Li20]. While these algorithms are for undirected graphs (and hence would require an undirected spanner), the most recent algorithm does solve the min-cost flow problem in directed graph in near-linear time [CKL⁺22].

Thus, we obtain the following statement, which is direct corollary of our directed spanner Theorem 1.4 combined with [CKL⁺22]:

First, we show that we cannot obtain approximation $c<2$ using vanilla spanners or even spanners with Steiner points in the Euclidean/Hamming metric. Indeed, consider a random pointset $P$ on the surface of a unit sphere in $\mathbb{R}^{d}$. Then all distances are concentrated around $\sqrt{2}$. It is immediate that, for any spanner $H_{r}$, any pair of points without a direct edge will have stretch 2. One can also show that even if we have Steiner points in $\mathbb{R}^{d}$, then a subquadratic-sized spanner much have stretch at least $\sqrt{2}$. For intuition, note that the best Steiner point for $P$ is the center of the sphere. A similar lower bound holds for Steiner spanners in the Hamming space.

To deal with the first source of approximation from [HPIS13] algorithm, we consider adding Steiner vertices to the spanner that does not represent points in the metric itself. In particular, in the above equidistant case, the solution is to add a node $s$ to the graph, and connect it to each of the points in $P$ with an edge of length $cr/2$. We term this a “star gadget” below.

Now we can focus on the second source of stretch: that we need to set $p_{2}$ as low as $1/n^{3}$, which is a much more significant technical challenge. The natural first question would be: why not set $p_{2}\approx 0.1/n$ and hence $p_{1}=1/n^{1-\epsilon}$ for $c=1+\epsilon$?

Consider a pair of points $p,q\in P$ at distance $\leq r$ that we would like to collide in some bucket, in which case they are connected by a path of distance $cr$ (using our new star gadget from above). It is immediate to argue that $p,q$ will collide with probability $p_{1}$, and hence $1-o(1)$ over all $L$ hash functions. The tricky part is to ensure that this successful bucket does not also contain a pair of far points (i.e., at distance $>cr$), in which case the star gadget will shortcut the pair.

To analyze the probability of far pair of points falling into the bucket, we can consider, for example, the probability that a “far” point $f\in P$ at distance $\|q-f\|>cr$ collides with $q$. Standard analysis says that the expected number of far points is $\leq p_{2}n$, and hence, by Markov’s, there’s, say, $\Omega(1)$ probability that no far point collides with $q$. The crucial caveat is that this probability is not independent of the event that $p,q$ collide: i.e., it may be the case that whenever $p,q$ collide, the number of colliding far points is much larger than the expectation.

We are lead to consider the “3-point collision” probability: $\Pr[(h(f)=h(q))\wedge(h(q)=h(p))]$. If we were able to prove that these two events are essentially independent, we would be all set. Such property has indeed been considered, at least in [AR15] who used it for data-dependent LSH algorithms. They proved such desired independence by a very intricate reduction to the “pseudo-random” case: where $P$ is essentially random on the sphere, except for the pair of interest $p,q$. Alas, their reduction does not seem applicable here for a couple of reasons. The first is that the independence holds only in the case when far point $f$ is far from both $p$ and $q$. The second is that, while in [AR15] one can think of $p$ being a “rare” close point to $q$ (this helps in the reduction), in our setting, there could be both $\Omega(n)$ close points and $\Omega(n)$ far points for most $q$’s!

Our approach is different and uses two main ideas: the first enough to get directed spanners, and the second necessary for the undirected spanners.

We circumvent the “3-point collision” analysis by considering a different setting of the hashing, roughly corresponding to the ANNS algorithm with sub-polynomial query time. In particular, we use the hashing scheme from [ALRW17]. Think of the dataset as being two sets $P$ and $Q$, and we need to worry only about the collision of points $p\in P$ vs $q\in Q$ (in the end we take $Q=P$). Then [ALRW17] design a hashing scheme such that for some $L=n^{O(1)}$, there’s a function $h_{P}:\mathbb{R}^{d}\to 2^{[L]}$ which describes for each point $p\in P$ which set of buckets it is hashed to, and there’s an equivalent $h_{Q}:\mathbb{R}^{d}\to 2^{[L]}$ function. Then we have that, for any pair $p,q$ at distance $\leq r$, we have that $h_{P}(p)\cap h_{Q}(q)\neq\emptyset$ with constant probability. Furthermore, $|h_{P}(p)|=n^{\rho_{P}+o(1)}$ and $|h_{Q}(q)|=n^{\rho_{Q}+o(1)}$ for $\rho_{Q},\rho_{P}\geq 0$ satisfying some relation, and the runtime to compute $h_{P}(p),h_{Q}(q)$ is roughly proportional to their output size. It is possible to set $\rho_{Q}=0$ in which case $\rho_{P}\approx 1/\epsilon^{2}$ (we note that this bound is tight [ALRW17]).

Our solution uses the above asymmetric hashing as follows: split the dataset $P$ into $\approx n^{1-\epsilon^{2}/2}$ groups of size $m=n^{\epsilon^{2}/2}$. For each group, preprocess as above, taking a total of $\approx n/m\cdot m^{\rho_{P}}<n^{1.5}$ time, and then query each $q\in Q$, taking a total of $\approx n\cdot n/m=n^{2-\epsilon^{2}/2}$ time. We can then prove that, for every close pair $p\in P,q\in Q$, with probability at least $1/2$, there exists a bucket where 1) $p,q$ collide, but 2) contains no point $f$ that is far from $q$.

The remaining caveat is that we need to verify that a bucket succeeded — all hashed $p,q$ are close to each other — as we cannot add star gadget to the failed ones (otherwise, we create shortcuts). For this, we need to employ furthest neighbor search data structure. A naïve adaptation of the best currently known data structure, would result in extra runtime $\approx n^{2-\epsilon^{3}}$, a slow-down we manage to avoid.

The above procedure obtains only a directed spanner since we guarantee distances between $p\in P$ and $q\in Q$ but among $p,p^{\prime}\in P$ pairs or $q,q^{\prime}\in Q$ pairs. This turns out to be much more difficult to ensure.

In fact, our original “star gadget” is not even enough to get an undirected spanner. In particular, consider the case when, we have $n/2$ points $P$ drawn from sphere of radius $a=2$ and $Q$ drawn sphere of radius $b=1$. Then the distance between a pair $p\in P,q\in Q$ is typically $\sqrt{a^{2}+b^{2}}=\sqrt{5}$; fix $r=\sqrt{5}$. At the same time the distance between points $p,p^{\prime}\in P$ is $\sqrt{2}a=\sqrt{8}>r$. It seems impossible to construct an undirected spanner of sub-quadratic size with stretch $1+\epsilon$ using the “star gadget” from before — because it would shortcut $P$-to-$P$ distances.

Instead, we introduce a new gadget: asymmetric star gadget. In particular, in the above example, we have a Steiner vertex $s$ that is connected with distance $\sqrt{2}a/2$ to points $p\in P$ and with distance $\sqrt{a^{2}+b^{2}}-\sqrt{2}a/2\geq\sqrt{2}b/2$ to points $q\in Q$. Now the distance $P$-to-$Q$ is $r$; $P$-to-$P$ is $\sqrt{2}a$; and $Q$-to-$Q$ is $\geq\sqrt{2}b$ as well. While the $Q$-to-$Q$ distance is stretched (it will be taken care of at a different scale $r$), the $r$-scale distances are taken care of, and there are not shortcuts created.

To be able to use this gadget, we start from where we left off with the directed spanner: a pair of sets of $P^{\prime}\subset P,Q^{\prime}\subset Q$ such that each $p\in P^{\prime}$ is close to each $q\in Q^{\prime}$. We show that in this case, there exists $a,b$ with $a+b\leq r$, such that we can decompose $P^{\prime}$ (and $Q^{\prime}$) into smaller parts so that the diameter of each part is $(1+\epsilon)a$ (and $(1+\epsilon)b$ respectively). The number of such parts is bounded by $P^{\prime 1-\Theta(\epsilon)}$ and $Q^{\prime 1-\Theta(\epsilon)}$ respectively. Then we use the asymmetric gadget on each pair of such parts.