Division by zero (densmap + cosine similarity)

Greetings!

I wanted to report a division by zero error I'm getting for certain datasets, when using metric="cosine" and densmap=True.

In this case, the problematic dataset is a sparse np.float32 dataset with 492391 rows x 768 columns, and the error is raised during a call to optimize_layout_euclidean().

Parameters:

UMAP(densmap=True, metric='cosine', n_neighbors=50, random_state=321)

Stack trace:

OMP: Info #271: omp_set_nested routine deprecated, please use omp_set_max_active_levels instead.
umap_.py:125: UserWarning: A few of yourvertices were disconnected from the manifold.  This shouldn't cause problems.
Disconnection_distance = 1 has removed 3605 edges.
It has only fully disconnected 30 vertices.
Use umap.utils.disconnected_vertices() to identify them.
  warn(
umap_.py:1114: RuntimeWarning: invalid value encountered in true_divide
  ro = np.log(epsilon + (ro / mu_sum))
---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
File reduce_dimension.py, in <module>

---> 69     embedding = reducer.fit_transform(dat)

File ~/.local/lib/python3.9/site-packages/umap/umap_.py:2634, in UMAP.fit_transform(self, X,y)
   2604 def fit_transform(self, X, y=None):
   2605     """Fit X into an embedded space and return that transformed
   2606     output.
   2607
   (...)
   2632         Local radii of data points in the embedding (log-transformed).
   2633     """
-> 2634     self.fit(X, y)
   2635     if self.transform_mode == "embedding":
   2636         if self.output_dens:

File ~/.local/lib/python3.9/site-packages/umap/umap_.py:2553, in UMAP.fit(self, X, y)
   2550     print(ts(), "Construct embedding")
   2552 if self.transform_mode == "embedding":
-> 2553     self.embedding_, aux_data = self._fit_embed_data(
   2554         self._raw_data[index], n_epochs, init, random_state,  # JH why raw data?
   2555     )
   2556     # Assign any points that are fully disconnected from our manifold(s) to have embedding
   2557     # coordinates of np.nan.  These will be filtered by our plotting functions automatically.
   2558     # They also prevent users from being deceived a distance query to one of these points.
   2559     # Might be worth moving this into simplicial_set_embedding or _fit_embed_data
   2560     disconnected_vertices = np.array(self.graph_.sum(axis=1)).flatten() == 0

File ~/.local/lib/python3.9/site-packages/umap/umap_.py:2580, in UMAP._fit_embed_data(self, X, n_epochs, init, random_state)
   2576 def _fit_embed_data(self, X, n_epochs, init, random_state):
   2577     """A method wrapper for simplicial_set_embedding that can be
   2578     replaced by subclasses.
   2579     """
-> 2580     return simplicial_set_embedding(
   2581         X,
   2582         self.graph_,
   2583         self.n_components,
   2584         self._initial_alpha,
   2585         self._a,
   2586         self._b,
   2587         self.repulsion_strength,
   2588         self.negative_sample_rate,
   2589         n_epochs,
   2590         init,
   2591         random_state,
   2592         self._input_distance_func,
   2593         self._metric_kwds,
   2594         self.densmap,
   2595         self._densmap_kwds,
   2596         self.output_dens,
   2597         self._output_distance_func,
   2598         self._output_metric_kwds,
   2599         self.output_metric in ("euclidean", "l2"),
   2600         self.random_state is None,
   2601         self.verbose,
   2602     )

File ~/.local/lib/python3.9/site-packages/umap/umap_.py:1132, in simplicial_set_embedding(data, graph, n_components, initial_alpha, a, b, gamma, negative_sample_rate, n_epochs, init, random_state, metric, metric_kwds, densmap, densmap_kwds, output_dens, output_metric, output_metric_kwds, euclidean_output, parallel, verbose)
   1125 embedding = (
   1126     10.0
   1127     * (embedding - np.min(embedding, 0))
   1128     / (np.max(embedding, 0) - np.min(embedding, 0))
   1129 ).astype(np.float32, order="C")
   1131 if euclidean_output:
-> 1132     embedding = optimize_layout_euclidean(
   1133         embedding,
   1134         embedding,
   1135         head,
   1136         tail,
   1137         n_epochs,
   1138         n_vertices,
   1139         epochs_per_sample,
   1140         a,
   1141         b,
   1142         rng_state,
   1143         gamma,
   1144         initial_alpha,
   1145         negative_sample_rate,
   1146         parallel=parallel,
   1147         verbose=verbose,
   1148         densmap=densmap,
   1149         densmap_kwds=densmap_kwds,
   1150     )
   1151 else:
   1152     embedding = optimize_layout_generic(
   1153         embedding,
   1154         embedding,
   (...)
   1168         verbose=verbose,
   1169     )

File ~/.local/lib/python3.9/site-packages/umap/layouts.py:325, in optimize_layout_euclidean(head_embedding, tail_embedding, head, tail, n_epochs, n_vertices, epochs_per_sample, a, b, rng_state, gamma, initial_alpha, negative_sample_rate, parallel, verbose, densmap, densmap_kwds)
    318 densmap_flag = (
    319     densmap
    320     and (densmap_kwds["lambda"] > 0)
    321     and (((n + 1) / float(n_epochs)) > (1 - densmap_kwds["frac"]))
    322 )
    324 if densmap_flag:
--> 325     dens_init_fn(
    326         head_embedding,
    327         tail_embedding,
    328         head,
    329         tail,
    330         a,
    331         b,
    332         dens_re_sum,
    333         dens_phi_sum,
    334     )
    336     dens_re_std = np.sqrt(np.var(dens_re_sum) + dens_var_shift)
    337     dens_re_mean = np.mean(dens_re_sum)

ZeroDivisionError: division by zero

System info:

• Arch Linux (5.17.1)
• Python 3.9.10
• umap-learn 0.5.2 (conda)

Thanks for all of your great work on this package, and for the clear explanations in your talks! I've learned a lot from them.

Start in umap/layouts.py at optimize_layout_euclidean and the densmap path reaching dens_init_fn, then trace how umap/umap_.py calls it. Reproduce the failure with the reported sparse np.float32 dataset and UMAP parameters, and confirm that fit_transform completes without the division-by-zero error.