On Geometric Alignment in Low Doubling Dimension

Hu Ding, Mingquan Ye

Abstract

Geometric alignment in high-dimensional spaces is a computational bottleneck for many fields, from natural language processing to bioinformatics. This paper introduces a framework that leverages the "doubling dimension"—a measure of intrinsic data complexity—to compress large point sets. By performing alignment on these compressed "coresets," we achieve significant speedups with theoretical guarantees that the resulting approximation remains close to the optimal solution. Experimental results on synthetic and real-world linguistic datasets demonstrate that our method can reduce running times by over 95% while maintaining high alignment fidelity.

The Challenge of High-Dimensional Alignment

Geometric alignment involves finding the best spatial transformation (such as rotation and translation) to match two sets of points. While well-studied in 2D and 3D for computer vision, modern applications—such as aligning word embeddings across languages or matching protein-protein interaction (PPI) networks—require alignment in much higher dimensions.

The standard metric for measuring mismatch is the Earth Mover’s Distance (EMD). While robust to noise, EMD is computationally expensive, often scaling at $O(n^2d)$ or worse. Existing high-dimensional algorithms frequently suffer from the "curse of dimensionality," becoming prohibitively slow as the number of points ($n$) or dimensions ($d$) increases.

Methodology: Compress-then-Align

We propose a framework based on the observation that high-dimensional data often lives on a lower-dimensional manifold.

  1. Doubling Dimension: We use the concept of "doubling dimension" ($\rho$) to measure the intrinsic complexity of the data. Unlike the ambient Euclidean dimension, the doubling dimension captures how the data actually fills the space.
  2. Compression via $k$-center Clustering: Using Gonzalez’s algorithm (a greedy 2-approximation for the $k$-center problem), we reduce the original point sets into much smaller sets of weighted cluster centers. The compression level is represented by $\gamma$.
  3. Alignment: We run an iterative alignment algorithm on the compressed sets. This algorithm alternates between updating the EMD flow and updating the rigid transformation using Orthogonal Procrustes analysis.
  4. Theoretical Guarantee: A core contribution is the proof that the alignment found on compressed sets is a provable approximation of the alignment on the original sets, with the error bounded by the doubling dimension and the diameter of the point sets.

Experimental Results

The framework was evaluated on synthetic data, linguistic word embeddings, and bioinformatics networks.

Performance on Linguistic Datasets

For word embeddings across five language pairs (e.g., Spanish-English, Chinese-English), the framework maintained high fidelity. Even with heavy compression, the alignment quality (EMD) typically remained within 1.2x of the baseline.

Table 1: EMD and running time (s) for linguistic datasets across different compression levels $\gamma$.

Efficiency and Scalability

The most significant gains were seen in large-scale datasets. On synthetic random data, compressing the set to 2% of its original size ($\gamma = 1/50$) resulted in a running time of 48.7 seconds, compared to the baseline of 1,418.2 seconds—a reduction of over 96%.

Table 2: Performance on random synthetic datasets, showing the trade-off between compression level $\gamma$, EMD, and time.

Conclusion

By decoupling the compression step from the specific alignment algorithm, this framework offers a versatile solution for high-dimensional geometric tasks. It effectively bypasses the computational bottlenecks of EMD by focusing on the intrinsic doubling dimension of the data, enabling practical, large-scale alignment without sacrificing theoretical rigor or empirical accuracy.

Summary updated

Abstract

In real-world, many problems can be formulated as the alignment between two geometric patterns. Previously, a great amount of research focus on the alignment of 2D or 3D patterns, especially in the field of computer vision. Recently, the alignment of geometric patterns in high dimension finds several novel applications, and has attracted more and more attentions. However, the research is still rather limited in terms of algorithms. To the best of our knowledge, most existing approaches for high dimensional alignment are just simple extensions of their counterparts for 2D and 3D cases, and often suffer from the issues such as high complexities. In this paper, we propose an effective framework to compress the high dimensional geometric patterns and approximately preserve the alignment quality. As a consequence, existing alignment approach can be applied to the compressed geometric patterns and thus the time complexity is significantly reduced. Our idea is inspired by the observation that high dimensional data often has a low intrinsic dimension. We adopt the widely used notion "doubling dimension" to measure the extents of our compression and the resulting approximation. Finally, we test our method on both random and real datasets, the experimental results reveal that running the alignment algorithm on compressed patterns can achieve similar qualities, comparing with the results on the original patterns, but the running times (including the times cost for compression) are substantially lower.
BibTeX
@inproceedings{ding2019geometric,
  author = {Hu Ding and Mingquan Ye},
  title = {{On Geometric Alignment in Low Doubling Dimension}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=9g5iiN3cKBH},
}
Figure