Two promising dimensionality reduction algorithms were released last year, Ivis and UMAP. The Ivis paper was submitted to Nature Scientific Reports about 6 months after the UMAP paper appeared on arXiv, and before UMAP came into general use. Both papers compare their new techniques favorably to t-distributed Stochastic Neighbor Embedding (t-SNE), which has become one of the most popular nonlinear dimensionality reduction techniques. The Ivis creators have provided some benchmark data for both the execution time and distance preservation relative to several other tehniques, including UMAP, t-SNE, multidimensional scaling and IsoMap, demonstrating that Ivis outperforms UMAP in terms of distance preservation and even execution time for some larger datasets.

In this post, I will compare the performance of Ivis and UMAP using some of the examples used by the Ivis paper to compare the performance of Ivis to t-SNE. For the datasets tested, Ivis is two orders of magnitude slower, but preserves global structure much better than UMAP.

The notebooks used to generate data and perform the dimensionality reductions is provided in this repository.

Background

UMAP

Uniform Manifold Approximation and Projection (UMAP) is a manifold learning technique based on topological data analysis. A fuzzy topological representation of the points is constructed in the higher dimensional space, then a lower-dimensional representation is optimized so that its fuzzy topological representation is as close as possible to that of the original representation, with fuzzy set membership calculated only for the k nearest neighbors of each point.

Further Reading

Ivis

Ivis utilizes a siamese network with a modified form of the triplet loss function to create a lower-dimensional representation that minimizes the distance of each point to its nearest neighbors and maximizes the distance of each point to points which are not its nearest neighbors.

Further Reading

Examples

For these examples, the 2D datasets are expanded into 9 dimensions using the same transformation as the Ivis paper: \((x, y) \rightarrow (x + y, x - y, xy, x^2, y^2, x^2y, xy^2, x^3, y^3)\). To ease the comparison of the embeddings to the original 2D data, a rigid transformation was applied to the embeddings to align them with the 2D data in a least squares sense. This can be done because the axes in both UMAP and Ivis are arbitrary. Standardized the expanded data using sklearn.preprocessing.StandardScaler before fitting the dimensionality reduction did not improve either method, so the data presented is derived from unscaled expanded data.

I used the implementation of UMAP provided by RAPIDS.ai’s cuML library and the Ivis implementation provided by the authors (ivis on PyPi).

Random uniform distribution

We will start with the first example mentioned in the Ivis paper, a random sampling of 5000 points from the uniform distribution.

Like t-SNE, UMAP creates spurious local structure, but the space is more “rectangular”:

As in the Ivis paper, we see that Ivis does not create the spurious local structures created by t-SNE:

“Smiley” dataset

The next example from the Ivis paper is the “smiley” dataset, as generated by the mlbench R package. This data consists of 2 Gaussian eys, a trapezoid nose and a parabula mouth with vertical Gaussian noise. This example consists of 10000 points, with the default standard deviations 0f 0.1 for the eyes and 0.05 for the mouth.

UMAP maintains most local and some global structure, but misplaces the “nose” and the “mouth”.

Again, we see that Ivis does a decent job of preserving global structure.

Using 0.35 as the standard deviation for both the eyes and the mouth creates more overlap between the classes:

The overlap means that the mouth is more likely to appear in the simplicial complexes of the eyes, which results in the relative positions of the eyes to the mouth being preserved. The nose is too far away to be included.

Ivis does a decent job of maintaining global structure without as much distortion to the local structure.

“Cassini problem” dataset

The “Cassini” dataset consists of points uniformly distributed within 3 structures, 2 external “bananas” and an inner circle:

UMAP does not preserve the global structure at all, presenting the three structures as separate spheres:

Ivis does a pretty good job of preserving the overall global structure.

PBMC dataset

This example comes from this R vignette, with the post-processing done using scikit-learn and the python phenograph package in place of the R package Seurat. The PBMC dataset was transformed using PCA, reducing its number of features to the number of samples. The data were then clustered using the PhenoGraph algorithm.

There are two outliers way outside of the range of the other points:

Zooming in to exclude those outliers shows that UMAP performs about as well as Ivis:

Ivis does about as good a job as UMAP and the first two principal components.

Conclusions

Ivis outperforms UMAP at preserving global structure and should be considered for many applications of dimensionality reduction.