Say I have some discrete space $(X,d)$ where $X$ is a finite set and $d$ is a metric. For each $x \in X $ I can find the set of $k$-nearest neighbors with respect to metric $d$.
Is there are any type of transformations (apart from isometries) that preserve the $k$-nearest neighbour order for each point?
Note that the distance is not really that important, just the order.
Edit: $X$ is a finite set. (thanks for pointing it out)
I think that depends strongly on the particular metric space $(X,d)$ you have. If $X$ is a finite collection of points in $\mathbb{R}^n$ and $d$ is just the standard Euclidean distance, then generically shifting all the points in same random direction by a sufficiently small amount will preserve the nearest neighbor order.
For a specific example, consider the $4$ points $0$, $1$ and $3$ and $8$ on the real axis. You can shift them all around a little bit (up to $1/10$ in either direction should be save) and the order of $k$-nearest neighbors will be preserved (for all $k$ because there are only $3$ neighbors in total).
One can construct examples with countably many points in a similar way.