Let $\{\mathbf{x}_i\}_{i=1}^N$ be a set of $N$ points such that $\mathbf{x_i} \in \mathbb{R}^M$.
Now, assume we define the graph $G=(V,E)$ such that for each point $\mathbf{x}_i$ we define a node $v_i \in V$ and we assign an undirected edge between node $v_i$ and node $v_j$ if the distance $|\mathbf{x}_i - \mathbf{x}_j| < \delta_0 $.
Clearly, a weighted graph based on the Euclidean pairwise distances will have more information on the set of data points, however, if it makes it easier I think we can assume that the graph’s adjacency matrix is binary.
Is there something similar to the Johnson–Lindenstrauss lemma to quantify how "lossy" this transformation is or maybe to find the least lossy $\delta_0$ based on how $\mathbf{x}_i$ are distributed in $\mathbb{R}^M$.
In some sense, every non one-to-one (non-injective) map of an input domain will be lossy, e.g., $(x, y)\to x+y$ is an irreversible mapping. However, it's still informative to know the sum of two numbers than knowing nothing.