Umap: why use np.max instead of np.min in smooth_knn_dist

[rayeaster]

thought it should be nearest neighbor which has mininum distance?

https://github.com/lmcinnes/umap/blob/master/umap/umap_.py#L179

rho[i] = np.max(non_zero_dists)

[lmcinnes]

This comes up (only) if the local_connectivity parameter is greater than the number of non-zero dists. The local connectivity parameter is such that if it is k we take the kth nearest neighbor. This defaults to 1, so we take the first nearest neighbor, but you can set it higher. If we are requesting the 5th nearest neighbor and we only have 4 non-zero distances then we will just take the largest one to be the distance. It is not ideal, but it is the best option given the odd circumstances.

[rayeaster]

This comes up (only) if the local_connectivity parameter is greater than the number of non-zero dists. The local connectivity parameter is such that if it is k we take the kth nearest neighbor. This defaults to 1, so we take the first nearest neighbor, but you can set it higher. If we are requesting the 5th nearest neighbor and we only have 4 non-zero distances then we will just take the largest one to be the distance. It is not ideal, but it is the best option given the odd circumstances.

@lmcinnes

That does make sense. Thanks.

I have another quick question: why do we need dim+1 for eigen vectorization and then sort ascendingly and fetch the largest dim eigen value out of them in algorithm 4 spectral embedding initialization, why not just directly get the dim largest eigen vector/value? any special difference or consideration there?
https://github.com/lmcinnes/umap/blob/7a07db21417b99c68803408f14c4915f5590f91e/umap/spectral.py#L312-L313

[jlmelville]

The smallest eigenvector is uninformative (it's always just a vector of 1s). See A Tutorial on Spectral Clustering for more.

[rayeaster]

The smallest eigenvector is uninformative (it's always just a vector of 1s). See A Tutorial on Spectral Clustering for more.

so if there is a way we could get the largest dim eigenvectors, we are good to go? or here we actually want the smallest dim eigenvectors (excluding the uninformative all 1s)?

[lmcinnes]

It depends on the choice of Laplacian (there are several) and a few other things. I got some advice from some experts in the area and went with that. I did recently get some alternative approaches suggested from another expert in spectral methods on graphs, but haven't had time to explore them yet.

[rayeaster]

It depends on the choice of Laplacian (there are several) and a few other things. I got some advice from some experts in the area and went with that. I did recently get some alternative approaches suggested from another expert in spectral methods on graphs, but haven't had time to explore them yet.

Sounds good. from above tutorial doc:

[jlmelville]

The way it's currently done in UMAP is the symmetrized normalized Laplacian (L_sym in the notation used by von Luxburg in that tutorial). For that, you need the dim + 1 smallest eigenvectors, ignoring the smallest eigenvector.

You could instead use the random walk transition matrix, P, in which case you would want the dim + 1 largest eigenvectors, ignoring the top eigenvector. Those are the equivalent to the dim + 1 bottom eigenvectors of the random walk Laplacian, L_rw (once again ignoring the bottom eigenvector). That's basically the same procedure as Laplacian Eigenmaps.

In the tutorial, on various theoretical grounds, von Luxburg suggests that L_rw is superior to L_sym for spectral clustering. But I've not noticed that one is superior to the other for the purposes of initializing UMAP.

[rayeaster]

The way it's currently done in UMAP is the symmetrized normalized Laplacian (L_sym in the notation used by von Luxburg in that tutorial). For that, you need the dim + 1 smallest eigenvectors, ignoring the smallest eigenvector.

You _could_ instead use the random walk transition matrix, P, in which case you would want the dim + 1 largest eigenvectors, ignoring the top eigenvector. Those are the equivalent to the dim + 1 bottom eigenvectors of the random walk Laplacian, L_rw (once again ignoring the bottom eigenvector). That's basically the same procedure as Laplacian Eigenmaps.

In the tutorial, on various theoretical grounds, von Luxburg suggests that L_rw is superior to L_sym for spectral clustering. But I've not noticed that one is superior to the other for the purposes of initializing UMAP.

This is quite helpful insight. Thanks a lot.