lmcinnes / lmcinnes/umap

alignedUMAP ignores Disconnected_distance?

Open
#592 2 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,

From what I understand, when UMAP builds its knn-graph, it does not introduce edges between points at maximal distance (Disconnection_distance = 1 in case of Jaccard). I've observed that alignedUmap does not treat maximally distant points the same way and introduces edges between these points (and clusters these dissimilar points together).

```
from scipy import sparse
import numpy as np
import umap
import umap.aligned_umap

# Matrix M has 9 rows:
# points 6,7,8 are maximally dissimilar to all other points (Jaccard similarity of 0)
i_index = [0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,7,8]
j_index = [1,2,3,0,2,3,0,1,3,4,5,6,4,6,7,5,6,7,8,9,10]
v_index = [1]*len(i_index)
M = sparse.csr_matrix((v_index,(i_index, j_index)))

# Align M with itself
slices = [M, M]
relations = [dict((i,i) for i in range(M.get_shape()[0]))]
embed = umap.AlignedUMAP(n_neighbors=3, metric='jaccard').fit(slices, relations=relations).embeddings_

# Visualize aligned embeddings
import matplotlib.pyplot as plt
plt.scatter(embed[0][:, 0],embed[0][:, 1])
plt.scatter(embed[1][:, 0],embed[1][:, 1], color='orange')
for i in [6,7,8]:
plt.annotate(str(i), (embed[0][i, 0], embed[0][i, 1]))
plt.annotate(str(i), (embed[1][i, 0], embed[1][i, 1]))
plt.title('Points 6,7 and 8 are clustered/aligned despite maximal pairwise distances.')

#Compare to:
M_embed = umap.UMAP(metric='jaccard', n_neighbors=3).fit_transform(M)
plt.scatter(M_embed[:, 0], M_embed[:, 1])
```

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 with the reproduced umap.AlignedUMAP call in the issue and compare its behavior with umap.UMAP using the supplied Jaccard-distance example. Trace how aligned embeddings handle maximally distant points, then verify that points 6, 7, and 8 are not incorrectly clustered or aligned when their pairwise distance is maximal.

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
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.