Accelerating hyperbolic t-SNE
- URL: http://arxiv.org/abs/2401.13708v1
- Date: Tue, 23 Jan 2024 12:59:40 GMT
- Title: Accelerating hyperbolic t-SNE
- Authors: Martin Skrodzki, Hunter van Geffen, Nicolas F. Chaves-de-Plaza, Thomas
H\"ollt, Elmar Eisemann, Klaus Hildebrandt
- Abstract summary: This paper introduces the first acceleration structure for hyperbolic embeddings, building upon a polar quadtree.
We demonstrate that it computes embeddings of similar quality in significantly less time.
- Score: 7.411478341945197
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: The need to understand the structure of hierarchical or high-dimensional data
is present in a variety of fields. Hyperbolic spaces have proven to be an
important tool for embedding computations and analysis tasks as their
non-linear nature lends itself well to tree or graph data. Subsequently, they
have also been used in the visualization of high-dimensional data, where they
exhibit increased embedding performance. However, none of the existing
dimensionality reduction methods for embedding into hyperbolic spaces scale
well with the size of the input data. That is because the embeddings are
computed via iterative optimization schemes and the computation cost of every
iteration is quadratic in the size of the input. Furthermore, due to the
non-linear nature of hyperbolic spaces, Euclidean acceleration structures
cannot directly be translated to the hyperbolic setting. This paper introduces
the first acceleration structure for hyperbolic embeddings, building upon a
polar quadtree. We compare our approach with existing methods and demonstrate
that it computes embeddings of similar quality in significantly less time.
Implementation and scripts for the experiments can be found at
https://graphics.tudelft.nl/accelerating-hyperbolic-tsne.
Related papers
- Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure.
We introduce a new class of manifold, named soft manifold, that can solve this situation.
Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
arXiv Detail & Related papers (2023-11-29T12:48:33Z) - Fast hyperboloid decision tree algorithms [0.6656737591902598]
We present hyperDT, a novel extension of decision tree algorithms into hyperbolic space.
Our approach is conceptually straightforward and maintains constant-time decision complexity.
Building upon hyperDT we introduce hyperRF, a hyperbolic random forest model.
arXiv Detail & Related papers (2023-10-20T22:31:10Z) - Hyperbolic vs Euclidean Embeddings in Few-Shot Learning: Two Sides of
the Same Coin [49.12496652756007]
We show that the best few-shot results are attained for hyperbolic embeddings at a common hyperbolic radius.
In contrast to prior benchmark results, we demonstrate that better performance can be achieved by a fixed-radius encoder equipped with the Euclidean metric.
arXiv Detail & Related papers (2023-09-18T14:51:46Z) - Tight and fast generalization error bound of graph embedding in metric
space [54.279425319381374]
We show that graph embedding in non-Euclidean metric space can outperform that in Euclidean space with much smaller training data than the existing bound has suggested.
Our new upper bound is significantly tighter and faster than the existing one, which can be exponential to $R$ and $O(frac1S)$ at the fastest.
arXiv Detail & Related papers (2023-05-13T17:29:18Z) - HRCF: Enhancing Collaborative Filtering via Hyperbolic Geometric
Regularization [52.369435664689995]
We introduce a textitHyperbolic Regularization powered Collaborative Filtering (HRCF) and design a geometric-aware hyperbolic regularizer.
Specifically, the proposal boosts optimization procedure via the root alignment and origin-aware penalty.
Our proposal is able to tackle the over-smoothing problem caused by hyperbolic aggregation and also brings the models a better discriminative ability.
arXiv Detail & Related papers (2022-04-18T06:11:44Z) - Provably Accurate and Scalable Linear Classifiers in Hyperbolic Spaces [39.71927912296049]
We propose a unified framework for learning scalable and simple hyperbolic linear classifiers.
The gist of our approach is to focus on Poincar'e ball models and formulate the classification problems using tangent space formalisms.
The excellent performance of the Poincar'e second-order and strategic perceptrons shows that the proposed framework can be extended to general machine learning problems in hyperbolic spaces.
arXiv Detail & Related papers (2022-03-07T21:36:21Z) - Highly Scalable and Provably Accurate Classification in Poincare Balls [40.82908295137667]
We establish a unified framework for learning scalable and simple hyperbolic linear classifiers with provable performance guarantees.
Our results include a new hyperbolic and second-order perceptron algorithm as well as an efficient and highly accurate convex optimization setup for hyperbolic support vector machine classifiers.
Their performance accuracies on synthetic data sets comprising millions of points, as well as on complex real-world data sets such as single-cell RNA-seq expression measurements, CIFAR10, Fashion-MNIST and mini-ImageNet.
arXiv Detail & Related papers (2021-09-08T16:59:39Z) - Unit Ball Model for Hierarchical Embeddings in Complex Hyperbolic Space [28.349200177632852]
Learning the representation of data with hierarchical structures in the hyperbolic space attracts increasing attention in recent years.
We propose to learn the graph embeddings in the unit ball model of the complex hyperbolic space.
arXiv Detail & Related papers (2021-05-09T16:09:54Z) - A Local Similarity-Preserving Framework for Nonlinear Dimensionality
Reduction with Neural Networks [56.068488417457935]
We propose a novel local nonlinear approach named Vec2vec for general purpose dimensionality reduction.
To train the neural network, we build the neighborhood similarity graph of a matrix and define the context of data points.
Experiments of data classification and clustering on eight real datasets show that Vec2vec is better than several classical dimensionality reduction methods in the statistical hypothesis test.
arXiv Detail & Related papers (2021-03-10T23:10:47Z) - Robust Large-Margin Learning in Hyperbolic Space [64.42251583239347]
We present the first theoretical guarantees for learning a classifier in hyperbolic rather than Euclidean space.
We provide an algorithm to efficiently learn a large-margin hyperplane, relying on the careful injection of adversarial examples.
We prove that for hierarchical data that embeds well into hyperbolic space, the low embedding dimension ensures superior guarantees.
arXiv Detail & Related papers (2020-04-11T19:11:30Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.