lmcinnes / lmcinnes/umap

Could spectral initialization give unexpectedly large initial coordinates?

Open
#212 1 comment 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

This might not be a bug: I haven't seen it cause a problem in practice, but I also haven't tried very hard to trigger it.

The spectral initialization involves rescaling the eigenvectors by maximum value, then multiplying by 10:
https://github.com/lmcinnes/umap/blob/d04006e6399f02a70bc831dd969a119e86048de4/umap/umap_.py#L945
(finally, some noise is added, but that's not germane to the current discussion)

I think the idea here is rescale the coordinates so that the largest value is 10. But if the coordinates can take negative values (which they can) and if the magntiude of the most negative coordinate is larger than that of the most positive coordinate (this bit I don't know about), the actual rescaling could result in the negative coordinates being much larger than 10.

I mention this because just such an unfortunate state of affairs has occurred in uwot, leading to horrible outliers in some embeddings (obviously, the fix is to use the maximum absolute value). I don't know much about the scipy implementation of the eigenvector routines that prevent negative values being larger than the positive ones, but I thought I would ask.

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

Start in umap/umap_.py at the spectral initialization code around line 945. Inspect how the scipy eigenvectors are rescaled and whether negative coordinates can exceed the intended bound. Reproduce or construct an asymmetric-coordinate case if possible, then verify the initialization remains bounded and add a regression test if the behavior is confirmed.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
machine-learning
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.