Differences between `umap.UMAP` and `cuml.UMAP` in embeddings logic

[jcrist]

While bug hunting through our UMAP implementation, I found two notable (and related) differences between our logic and that in umap-learn. Raising them here.

When generating the embeddings,umap-learn does the following:

• Stores the unmodified fss graph as a graph_ attribute
• Makes a copy of the input graph (link)
• Thresholds values in the copy of the graph, setting low values to 0 (link)
• Drops zero values in the copy of the graph (link)
• Runs initialization (spectral, random, ...)

In contrast, our implementation:

• Runs initialization (spectral, random, ...)
• Thresholds values in the input graph, setting low values to 0. This happens in place, mutating the input graph. (link)
• Allocates a new COO and copies the non-zero elements of the above graph to it (link)
• Then stores the input (thresholded, but with zero elements not removed) graph as graph_ (link).

This results in two functional differences:

• In our implementation, init is run before thresholding. In umap-learn init is run after thresholding. This may be partially responsible for the differences we see in our embeddings vs those generated by umap-learn.
• In our implementation, graph_ has had thresholding applied to it (but zero values not removed). In umap-learn, graph_ is the raw graph with no thresholding applied.

[viclafargue]

Thanks for uncovering this @jcrist!

In our implementation, init is run before thresholding. In umap-learn init is run after thresholding. This may be partially responsible for the differences we see in our embeddings vs those generated by umap-learn.

Random initialization should be shielded from this, but it however might very well have a strong effect on spectral initialization. This may have been made on purpose to yield better precision (@cjnolet ?), but trimming the graph could dramatically speedup the embeddings initialization process.

In our implementation, graph_ has had thresholding applied to it (but zero values not removed). In umap-learn, graph_ is the raw graph with no thresholding applied.

Thanks for noticing this. This is an implementation error. I think that the transform function should not be affected though since the graph is trimmed to produce new embeddings.

[jcrist]

I think that the transform function should not be affected though since the graph is trimmed to produce new embeddings.

This is correct, our implementation never references the graph_ attribute again, it's purely exposed as an output. We do know of some users that reference this attribute for inspection purposes though, so this would be a user-facing bug for them. Additionally, umap-learn references this attribute when merging models; this could result in bugs for users making use of this along with cuml.accel.

[jinsolp]

What is the status of this issue? I was wondering if we have someone looking into this? @viclafargue @jcrist

[viclafargue]

Regarding the larger issue of outliers, my investigation so far suggests that our implementation struggles with imbalanced graphs. Samples with significantly higher number of connections receive disproportionately more gradient updates, and they often emerge as outliers in the projected space. I’ve shared more details in this comment. I'm still exploring the issue further, but feel free to take a look and share your thoughts.