Metricizing the Euclidean Space towards Desired Distance Relations in Point Clouds

Abstract

Given a set of points in the Euclidean space ${\mathbb{R}}^{\ell }$ with $\ell >1$, the pairwise distances between the points are determined by their spatial location and the metric $d$ that we endow ${\mathbb{R}}^{\ell }$ with. Hence, the distance $d(\mathbf{x},\mathbf{y})=\delta$ between two points is fixed by the choice of $\mathbf{x}$ and $\mathbf{y}$ and $d$. We study the related problem of fixing the value $\delta$, and the points $\mathbf{x},\mathbf{y}$, and ask if there is a topological metric $d$ that computes the desired distance $\delta$. We demonstrate this problem to be solvable by constructing a metric to simultaneously give desired pairwise distances between up to $O(\sqrt{\ell })$ many points in ${\mathbb{R}}^{\ell }$. We then introduce the notion of an $\epsilon$-semimetric $\tilde{d}$ to formulate our main result: for all $\epsilon >0$, for all $m\ge 1$, for any choice of $m$ points ${\mathbf{y}}_1,\dots ,{\mathbf{y}}_m\in {\mathbb{R}}^{\ell }$, and all chosen sets of values $\{{\delta }_{ij}\ge 0:1\le i<j\le m\}$, there exists an $\epsilon$-semimetric $\tilde{\delta }:{\mathbb{R}}^{\ell }\times {\mathbb{R}}^{\ell }\to \mathbb{R}$ such that $\tilde{d}({\mathbf{y}}_i,{\mathbf{y}}_j)={\delta }_{ij}$, i.e., the desired distances are accomplished, irrespectively of the topology that the Euclidean or other norms would induce. We showcase our results by using them to attack unsupervised learning algorithms, specifically $k$-Means and density-based (DBSCAN) clustering algorithms. These have manifold applications in artificial intelligence, and letting them run with externally provided distance measures constructed in the way as shown here, can make clustering algorithms produce results that are pre-determined and hence malleable. This demonstrates that the results of clustering algorithms may not generally be trustworthy, unless there is a standardized and fixed prescription to use a specific distance function.

References in corpus (7)

• Societal Biases in Retrieved Contents: Measurement Framework and Adversarial Mitigation for BERT Rankers
• Practical Attacks Against Graph-based Clustering
• Statistically-Robust Clustering Techniques for Mapping Spatial Hotspots: A Survey
• A black-box adversarial attack for poisoning clustering
• Imperceptible Adversarial Examples by Spatial Chroma-Shift
• Metricizing the Euclidean Space towards Desired Distance Relations in Point Clouds
• Frequency Centric Defense Mechanisms against Adversarial Examples

Cited by in corpus (4)

• Metricizing the Euclidean Space towards Desired Distance Relations in Point Clouds
• Recognition of near-duplicate periodic patterns by continuous metrics with approximation guarantees
• Geographic-style maps with a local novelty distance help navigate the materials space
• AVP-AP: Self-supervised Automatic View Positioning in 3D cardiac CT via Atlas Prompting