Do any dimensionality reduction techniques find embeddings which optimally preserve the K-nearest neighbors of each point? If no algorithm provably does this, are there algorithms which heuristically achieve this more often than, say, PCA?

I imagine that an algorithm which builds the nearest neighbors graph and then uses this to find a new embedding would do something like this.

(I'd also be interested in a python library implementing any such algorithm)

  • $\begingroup$ Maybe random projections? It has guarantees on the pair-wise distance between points on the projected points. en.wikipedia.org/wiki/Random_projection. You can also look at MDS (Multi dimensional scaling). $\endgroup$ – Kozolovska Mar 7 at 16:19

Some manifold learning algorithms (Isomap, LLE, LTSA, Hessian Eigenmaps, I think they are collectively called spectral dimensionality reduction) should in principle do this - this is because they actually use $k$NN graph. This results in algorithm that preserves local structure rather than global one (they aim at distorting smaller distances less than big distances, kind of reverse of what PCA does).

These algorithms share similar structure:

  • construct a pairwise distance/similarity matrix $M$
  • perform some kind of matrix decomposition on $M$ (like SVD for example).

For constructing $M$ these algorithms use neighborhood graph: run $k$NN for some $k$ and then make graph where $x,y$ are connected if $x$ is in $k$-neighborhood of $y$ or vice versa. Then they run an algorithm for finding distances in this graph.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.