# HoroPCA

This code is the official PyTorch implementation of the ICML 2021 paper:

HoroPCA: Hyperbolic Dimensionality Reduction via Horospherical Projections

Ines Chami*, Albert Gu*, Dat Nguyen*, Christopher Ré

Stanford University

Paper: https://arxiv.org/abs/2106.03306

Abstract.This paper studies Principal Component Analysis (PCA) for data lying in hyperbolic spaces. Given directions, PCA relies on: (1) a parameterization of subspaces spanned by these directions, (2) a method of projection onto subspaces that preserves information in these directions, and (3) an objective to optimize, namely the variance explained by projections. We generalize each of these concepts to the hyperbolic space and propose HoroPCA, a method for hyperbolic dimensionality reduction. By focusing on the core problem of extracting principal directions, HoroPCA theoretically better preserves information in the original data such as distances, compared to previous generalizations of PCA. Empirically, we validate that HoroPCA outperforms existing dimensionality reduction methods, significantly reducing error in distance preservation. As a data whitening method, it improves downstream classification by up to 3.9% compared to methods that don’t use whitening. Finally, we show that HoroPCA can be used to visualize hyperbolic data in two dimensions.

The code has an implementation of the HoroPCA method, as well as other methods for dimensionality reduction on manifolds, such as Principal Geodesic Analysis and tangent Principal Component Analysis.

## Installation

This code was tested on Python3.7 and Pytorch 1.8.1. Start by installing the requirements:

`pip install -r requirements.txt`

## Usage

### Main script

Run hyperbolic dimensionality reduction experiments using the `main.py`

script.

```
python main.py --help
optional arguments:
-h, --help show this help message and exit
--dataset {smalltree,phylo-tree,bio-diseasome,ca-CSphd}
which datasets to use
--model {pca,tpca,pga,bsa,hmds,horopca}
which dimensionality reduction method to use
--metrics METRICS [METRICS ...]
which metrics to use
--dim DIM input embedding dimension to use
--n-components N_COMPONENTS
number of principal components
--lr LR learning rate to use for optimization-based methods
--n-runs N_RUNS number of runs for optimization-based methods
--use-sarkar use sarkar to embed the graphs
--sarkar-scale SARKAR_SCALE
scale to use for embeddings computed with Sarkar's
construction
```

### Examples

#### 1. Run HoroPCA on the smalltree dataset:

```
python main.py --dataset smalltree --model horopca --dim 10 --n-components 2
```

Output:

```
distortion: 0.19 +- 0.00
frechet_var: 7.15 +- 0.00
```

#### 2. Run Euclidean PCA on the smalltree dataset:

```
python main.py --dataset smalltree --model pca --dim 10 --n-components 2
```

Output:

```
distortion: 0.84 +- 0.00
frechet_var: 0.34 +- 0.00
```

### Datasets

The possible dataset choices in this repo are `{smalltree,phylo-tree,bio-diseasome,ca-CSphd}`

. To add a new dataset, add the corresponding edge list and embedding file in the `data/`

folder.

## Citation

If you use this codebase, or otherwise found our work valuable, please cite:

```
@article{chami2021horopca,
title={HoroPCA: Hyperbolic Dimensionality Reduction via Horospherical Projections},
author={Chami, Ines and Gu, Albert and Nguyen, Dat and R{\'e}, Christopher},
journal={arXiv preprint arXiv:2106.03306},
year={2021}
}
```