SG-t-SNE-Π: Swift Graph Embedding

We provide a Julia interface, i.e., a wrapper to SG-t-SNE-Π, which is a high-performance software for swift embedding of a large, sparse graph $G(V,E,P)$ into a $d$-dimensional space ($d = 1,2,3$) on a shared-memory computer. The algorithm SG-t-SNE and the software t-SNE-Π were first described in Reference (Nikos Pitsianis, Alexandros-Stavros Iliopoulos, Dimitris Floros, Xiaobai Sun (2019)) and released on GitHub in June 2019 (Nikos Pitsianis, Dimitris Floros, Alexandros-Stavros Iliopoulos, Xiaobai Sun (2019)). In fact, the software admits two types of data at input: (i) a graph or network, described in terms of vertices and edges (pairwise relationships among vertices), directed or undirected; (ii) a point-cloud data set, described in terms of feature attributes in numerical values (coordinates), in a metric space. In the second case, the point-cloud data are converted into a kNN graph, in which the data points are vertices, the edges represent k-nearest-neighbor relationships. In other words, the embedding acts as a non-linear dimension reduction. The software renders 2D or 3D embedding of the vertices or the data points. Embedding in 3D allows one to observe connections or disconnections that are obscured in 2D embedding.

SG-t-SNE improves upon two main precursors, t-SNE by Laurens van der Maaten, Geoffrey E. Hinton (2008), Laurens van der Maaten (2014) and FI-t-SNE by George C. Linderman, Manas Rachh, Jeremy G. Hoskins, Stefan Steinerberger, Yuval Kluger (2019), in several aspects. (i) It removes the limitation to regular-degree graphs with t-SNE; (ii) it enables 3D embedding while following the basic method used in FI-t-SNE for calculating repulsive forces; (iii) it surpasses in eﬀiciency, the precursor algorithms and implementations on modern laptop/desktop computers, without compromising accuracy. Recently, SG-t-SNE-Π has been compared favorably to UMAP (Parashar Dhapola, Johan Rodhe, Rasmus Olofzon, Thomas Bonald, Eva Erlandsson, Shamit Soneji, G{\"o}ran Karlsson (2021)). This version makes SG-t-SNE readily deployable to the Julia ecosystem. More information can be found at SG-t-SNE-Π.

Installation

To install SG-t-SNE-Π through Julia, issue

] add SGtSNEpi

We provide two use cases:

Point cloud data embedding Point-cloud data embedding
Graph embedding Graph embedding

For full documentation of the functions exported by SG-t-SNE-Π, see the API

References

hpec: Nikos Pitsianis, Alexandros-Stavros Iliopoulos, Dimitris Floros, Xiaobai Sun, Spaceland Embedding of Sparse Stochastic Graphs, In IEEE High Performance Extreme Computing Conference, 2019.
joss: Nikos Pitsianis, Dimitris Floros, Alexandros-Stavros Iliopoulos, Xiaobai Sun, SG-t-SNE-Π: Swift Neighbor Embedding of Sparse Stochastic Graphs, Journal of Open Source Software, 4(39), 1577, 2019.
bhtsne: Laurens van der Maaten, Accelerating T-SNE Using Tree-Based Algorithms, Journal of Machine Learning Research, 15(Oct), 3221-3245, 2014.
fitsne: George C. Linderman, Manas Rachh, Jeremy G. Hoskins, Stefan Steinerberger, Yuval Kluger, Fast Interpolation-Based t-SNE for Improved Visualization of Single-Cell RNA-Seq Data, Nature Methods, 16(3), 243-245, 2019.
tsne: Laurens van der Maaten, Geoffrey E. Hinton, Visualizing Data Using T-SNE, Journal of Machine Learning Research, 9(Nov), 2579-2605, 2008.
scarf: Parashar Dhapola, Johan Rodhe, Rasmus Olofzon, Thomas Bonald, Eva Erlandsson, Shamit Soneji, G{\"o}ran Karlsson, Scarf: A toolkit for memory efficient analysis of large-scale single-cell genomics data, https://www.biorxiv.org/content/early/2021/05/03/2021.05.02.441899.full.pdf.