lmcinnes / lmcinnes/umap

Disconnected_distance can break densMAP

Open
#549 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Python
Stars
8.3k
Forks
871
Avg merge
1d 13h
Merged PRs (30d)
5

Description

Hi gang, it seems that the new disconnected_distance feature I added can interfere with densMAP. It probably doesn't happen very often since folks should mostly be using densMAP on Euclidean style spaces and probably won't mess with the disconnection_distance in such space enough to completely disconnect a point from our graph. That said it can happen.

Here is an easy way to reproduce the error.

```
from sklearn import datasets
iris = datasets.load_iris()
densmap_iris_model = umap.UMAP(
n_neighbors=10, min_dist=0.01, random_state=42, densmap=True, verbose=True,
disconnection_distance=0.5,
).fit(iris.data)
```
:warning: ... umap_.py:1114: RuntimeWarning: invalid value encountered in true_divide

Diving into the code it looks like mu_sum turns out to be zero for those disconnected data points. Not a huge surprise. I'll spend a bit of time working on the right way to fix the bug but wanted to post an issue here in case someone thought of an elegant solution before I get to it.

It can more commonly crop up if one attempts to use densMAP on a bounded metric like jaccard (in a high dimensional space). In that case we are much more likely to disconnect points from our graph with the default settings. I'm not sure that densMAP is particularly well defined for non-Euclidean metrics but it definitely runs on them in our current version. Should we add some sort of gating to prevent this or do folks think that it's fine? Admittedly, I haven't read the densMAP paper in a while...

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Run the provided Iris reproduction with densmap=True and disconnection_distance=0.5. Inspect umap_.py around line 1114, where the RuntimeWarning occurs, and trace how disconnected points affect densMAP's mu_sum. Done means the reproduction no longer emits the invalid true_divide warning and densMAP handles disconnected points consistently.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
machine-learning
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.