# Geometry-Based Data Generation

Ofir Lindenbaum1,2† Jay S. Stanley III1,3† Guy Wolf2‡ Smita Krishnaswamy1,4‡∗

1Department of Genetics; 2Applied Mathematics Program;
3Computational Biology & Bioinformatics Program;
4Department of Computer Science;
Yale University, New Haven, CT, USA

∗Corresponding author. E-mail<EMAIL_ADDRESS>
Address: 333 Cedar St, New Haven, CT 06510, USA
† These authors contributed equally. ‡ These authors contributed equally

###### Abstract

We propose a new type of generative model of high-dimensional data that learns
a manifold geometry of the data, rather than density, and can generate points
evenly along this manifold. This is in contrast to existing generative models
that represent data density, and are strongly affected by noise and other
artifacts of data collection. We demonstrate how this approach corrects
sampling biases and artifacts, and improves several downstream data analysis
tasks such as clustering and classification. Finally, we demonstrate that this
approach is especially useful in biology where, despite the advent of single-
cell technologies, rare subpopulations and gene-interaction relationships are
affected by biased sampling. We show that SUGAR can generate hypothetical
populations and reveal intrinsic patterns and mutual-information relationships
between genes on a single cell dataset of hematopoiesis.

##  1 Introduction

Manifold learning methods in general, and diffusion geometry ones in
particular (Coifman & Lafon, 2006), are traditionally used to infer latent
representations that capture intrinsic geometry in data, but they do not
relate them to original data features. Here, we propose a novel data synthesis
method, which we call SUGAR (Synthesis Using Geometrically Aligned Random-
walks), for generating data in its original feature space while following its
intrinsic geometry. This geometry is inferred by a diffusion kernel that
captures a data-driven manifold and reveals underlying structure in the full
range of the data space – including undersampled regions that can be augmented
by new synthesized data. Geometry-based data generation with SUGAR is
motivated by numerous uses in data exploration. For instance, in biology,
despite the advent of single-cell technologies such as single-cell RNA
sequencing and mass cytometry, sampling biases and artifacts often make it
difficult to evenly sample the dataspace. Rare populations of relevance to
disease and development are often left out (Grün et al., 2015). By learning
the data geometry rather than density, SUGAR is able to generate hypothetical
cell types for exploration.

Further, imbalanced data is problematic for many machine learning
applications. Class density can strongly bias some classifiers (He & Garcia,
2009; López et al., 2013; Hensman & Masko, 2015). In clustering, imbalanced
sampling of ground truth clusters can lead to distortions in learned clusters
(Xuan et al., 2013; Wu, 2012). Sampling biases can also corrupt regression
tasks; relationship measures such as mutual information are heavily weighted
by density estimates and thus may mis-quantify the strength of dependencies
with data whose density is concentrated in a particular region of the
relationship (Krishnaswamy et al., 2014). SUGAR can aid such machine learning
algorithms by generating data that is balanced along its manifold.

There are several advantages of our approach over contemporary generative
models. Most other generative models attempt to learn and replicate the
density of the data; this approach is intractable in high dimensions.
Distribution-based generative models typically require vast simplifications
such as parametric forms or restriction to marginals in order to become
tractable. Examples for such methods include Gaussian Mixture Models (GMM)
(Rasmussen, 2000), variational Bayesian methods (Bernardo et al., 2003), and
kernel density estimates (Scott, 2008). In contrast to these methods, SUGAR
does not rely on high dimensional probability distributions or parametric
forms. SUGAR selectively generates points to equalize density; as such, the
method can be used generally to compensate for sparsity and heavily biased
sampling in data in a way that is agnostic to downstream application. In other
words, whereas more specialized methods may use prior information (e.g.,
labels) to correct class imbalances for classifier training (Chawla et al.,
2002), SUGAR does not require such information and can apply in cases (such as
for clustering or regression) even when such information does not exist.

Here, we construct SUGAR from diffusion methods and theoretically justify the
density equalization properties of SUGAR. We then demonstrate SUGAR on
imbalanced artificial data. Subsequently, we use SUGAR to improve
classification accuracy on 61 imbalanced datasets. We then provide an
illustrative synthetic example of clustering with SUGAR and show the
clustering performance of the method on 115 imbalanced datasets obtained from
the KEEL-dataset repository (Alcalá-Fdez et al., 2009). Finally, we use SUGAR
for exploratory analysis of a biological dataset, recovering imbalanced cell
types and restoring canonical gene-gene relationships.

##  2 Related Work

Most existing methods for data generation assume a probabilistic data model.
Parametric density estimation methods such as (Rasmussen, 2000; Varanasi &
Aazhang, 1989) find a best fitting parametric model for the data using maximum
likelihood, which is then used to generate new data. Nonparametric density
estimators (Seaman & Powell, 1996; Scott, 1985; Giné & Guillou, 2002) use a
histogram or a kernel (Scott, 2008) to estimate the generating distribution.
Recently, Variational Auto-Encoders (Kingma & Welling, 2013; Doersch, 2016)
and Generative Adversarial Nets (Goodfellow et al., 2014) have been
demonstrated for generating new points from complex high dimensional
distributions.

A family of manifold based Parzen window estimators are presented in (Vincent
& Bengio, 2003; Bengio & Monperrus, 2005; Bengio et al., 2006). These methods
exploit the manifold’s structure to improve a density estimation of high
dimensional data. Markov-chain Monte Carlo on implicitly defined manifolds was
presented in (Girolami & Calderhead, 2011; Brubaker et al., 2012). The authors
use implicit constrains to generate new points that follow a manifold
structure. Another scheme by Öztireli et al. (2010) defines a spectral measure
to resample existing points such that manifold structure is preserved and the
density of points is uniform. These methods differ from the proposed approach
as they either require implicit constraints or they change the values of
existing points in the resampling process.

##  3 Background

###  3.1 Diffusion Geometry

Coifman & Lafon (2006) proposed the non-linear dimensionality reduction
framework called Diffusion Maps (DM). This popular method robustly captures an
intrinsic manifold geometry using a row-stochastic Markov matrix associated
with a graph of the data. This graph is commonly constructed using a Gaussian
kernel

${\cal{K}}({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$x$}}_{j})\triangleq
K_{i,j}=exp\left({-\frac{\|{\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$x$}}_{j}\|^{2}}{2\sigma^{2}}}\right),i,j=1,...,N$
(1)

where $x_{1},\ldots,x_{N}$ are data points, and $\sigma$ is a bandwidth
parameter that controls neighborhood sizes. Then, a diffusion operator is
defined as the row-stochastic matrix
${P_{i,j}={\cal{P}}({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$x$}}_{j})=[{{{\mbox{\boldmath$D$}}}^{-1}{{\mbox{\boldmath$K$}}}}}]_{i,j}$,
$i,j=1,...,N$, where $D$ is a diagonal matrix with values corresponding to the
degree of the kernel
$D_{i,i}=\hat{d}(i)=\sum_{j}{\cal{K}}({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$x$}}_{j})$.
The degree $\hat{d}(i)$ of each point ${\mbox{\boldmath$x$}}_{i}$ encodes the
total connectivity the point has to its neighbors. The Markov matrix $P$
defines an imposed diffusion process, shown by Coifman & Lafon (2006) to
efficiently capture the diffusion geometry of a manifold $\cal{M}$.

The DM framework may be used for dimensionality reduction to embed data using
the eigendecomposition of the diffusion operator. However, in this paper, we
do not directly use the DM embedding, but rather a variant of the operator $P$
that captures diffusion geometry. In Sec. 4, we explain how this operator
allows us to ensure the data we generate follows diffusion geometry and the
manifold structure it represents.

###  3.2 Measure Based Gaussian Correlation

Bermanis et al. (2016) suggest the Measure-based Gaussian Correlation (MGC)
kernel as an alternative to the Gaussian kernel (Eq. 1) for constructing
diffusion geometry based on a measure $\mu$. The measure could be provided in
advance or approximated based on the data samples. The MGC kernel with a
measure $\mu({\mbox{\boldmath$r$}})$, $r\in{\mbox{\boldmath$X$}}$, defined
over a set $X$ of reference points, is
$\hat{\cal{K}}({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$x$}}_{j})=\sum_{{\mbox{\boldmath$r$}}\in{\mbox{\boldmath$X$}}}{\cal{K}}({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$r$}}){\cal{K}}({\mbox{\boldmath$r$}},{\mbox{\boldmath$x$}}_{j})\mu({\mbox{\boldmath$r$}})$,
$i,j=1,...,N$, where the kernel $\cal{K}$ is some decaying symmetric function.
Here, we use a Gaussian kernel for $\cal{K}$ and a sparsity-based measure for
$\mu$.

###  3.3 Kernel Bandwidth Selection

The choice of kernel bandwidth $\sigma$ in Eq. 1 is crucial for the
performance of Gaussian-kernel methods. For small values of $\sigma$ the
resulting kernel $\cal{K}$ converges to the identity matrix; inversely, large
values of $\sigma$ yield the all-ones matrix. Many methods have been proposed
for tuning $\sigma$. A range of values is suggested in (Singer et al., 2009)
based on an analysis of the sum of values in $\cal{K}$. Lindenbaum et al.
(2017) presented a kernel scaling method that is well suited for
classification and manifold learning tasks. We describe here two methods for
setting the bandwidth: a global scale suggested in (Keller et al., 2010) and
an adaptive local scale based on (Zelnik-Manor & Perona, 2005).

For degree estimation we use the max-min bandwidth (Keller et al., 2010) as it
is simple and effective. The max-min bandwidth is defined by
$\sigma^{2}_{\text{MaxMin}}={\cal{C}}\cdot\underset{j}{\max}[\underset{i,i\neq
j}{\min}(\|{\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$x$}}_{j}\|^{2})]$, where
${\cal{C}}\in[2,3]$. This approach attempts to force that each point is
connected to at least one other point. This method is simple, but highly
sensitive to outliers. Zelnik-Manor & Perona (2005) propose adaptive bandwidth
selection. At each point ${\mbox{\boldmath$x$}}_{i}$, the scale $\sigma_{i}$
is chosen as the $L^{1}$ distance of ${\mbox{\boldmath$x$}}_{i}$ from its
$r$-th nearest neighbor. This adaptive bandwidth guarantees that at least half
of the points are connected to $r$ neighbors. Since an adaptive bandwidth
obscures density biases, it is more suitable for applying the resulting
diffusion process to the data than for degree estimation.

##  4 Data Generation

###  4.1 Problem Formulation

Let $\mathcal{M}$ be a $d$ dimensional manifold that lies in a higher
dimensional space $\mathbbm{R}^{D}$, with $d<D$, and let
${\mbox{\boldmath$X$}}\subseteq\mathcal{M}$ be a dataset of
$N=\left|{\mbox{\boldmath$X$}}\right|$ data points, denoted
${\mbox{\boldmath$x$}}_{1},\ldots,{\mbox{\boldmath$x$}}_{N}$, sampled from the
manifold. In this paper, we propose an approach that uses the samples in $X$
in order to capture the manifold geometry and generate new data points from
the manifold. In particular, we focus on the case where the points in $X$ are
unevenly sampled from $\mathcal{M}$, and aim to generate a set of $M$ new data
points
${\mbox{\boldmath$Y$}}=\\{{\mbox{\boldmath$y$}}_{1},...,{\mbox{\boldmath$y$}}_{M}\\}\subseteq\mathbbm{R}^{D}$
such that  1. the new points $Y$ approximately lie on the manifold
$\mathcal{M}$, and  2. the distribution of points in the combined dataset
${\mbox{\boldmath$Z$}}\triangleq{\mbox{\boldmath$X$}}\cup{\mbox{\boldmath$Y$}}$
is uniform.  Our proposed approach is based on using an intrinsic diffusion
process to robustly capture a manifold geometry from $X$ (see Sec. 3). Then,
we use this diffusion process to generate new data points along the manifold
geometry while adjusting their intrinsic distribution, as explained in the
following sections.

###  4.2 SUGAR: Synthesis Using Geometrically Aligned Random-walks

SUGAR initializes by forming a Gaussian kernel $G_{X}$ (see Eq. 1) over the
input data $X$ in order to estimate the degree $\hat{d}(i)$ of each
${\mbox{\boldmath$x$}}_{i}\in{\mbox{\boldmath$X$}}$. Because the space in
which degree is estimated impacts the output of SUGAR, $X$ may consist of the
full data dimensions or learned dimensions from manifold learning algorithms.
We then define the sparsity of each point $\hat{s}(i)$ via

$\hat{s}(i)\triangleq[{\hat{d}(i)}]^{-1},i=1,...,N.$ (2)

Subsequently, we sample $\hat{\ell}(i)$ points
${\mbox{\boldmath$h$}}_{j}\in{\mbox{\boldmath$H$}}_{i},j=1,...,\hat{\ell}(i)$
around each ${\mbox{\boldmath$x$}}_{i}\in{\mbox{\boldmath$X$}}$ from a set of
localized Gaussian distributions
$G_{i}={\cal{N}}({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$\Sigma$}}_{i})\in\mathcal{G}$.
The choice of $\hat{\ell}(i)$ based on the density (or sparsity) around
${\mbox{\boldmath$x$}}_{i}$ is discussed in Sec. 4.3. This construction
elaborates local manifold structure in meaningful directions by  1.
compensating for data sparsity according to $f(\hat{s}(i))$, and  2. centering
each $G_{i}$ on an existing point ${\mbox{\boldmath$x$}}_{i}$ with local
covariance ${\mbox{\boldmath$\Sigma$}}_{i}$ based on the $k$ nearest neighbors
of ${\mbox{\boldmath$x$}}_{i}$.  The set of all $M=\sum_{i}\hat{\ell}(i)$ new
points,
${\mbox{\boldmath$Y$}}_{0}=\\{{\mbox{\boldmath$y$}}_{1},...,{\mbox{\boldmath$y$}}_{M}\\}$,
is then given by the union of all local point sets
${\mbox{\boldmath$Y$}}_{0}={\mbox{\boldmath$H$}}_{1}\cup{\mbox{\boldmath$H$}}_{2}\cup...\cup{\mbox{\boldmath$H$}}_{N}$.
Next, we construct a sparsity-based MGC kernel (see Sec. 3.2)
$\hat{\cal{K}}({\mbox{\boldmath$y$}}_{i},{\mbox{\boldmath$y$}}_{j})=\sum_{r}{\cal{K}}({\mbox{\boldmath$y$}}_{i},{\mbox{\boldmath$x$}}_{r}){\cal{K}}({\mbox{\boldmath$x$}}_{r},{\mbox{\boldmath$y$}}_{j})\hat{s}(r)$
using the affinities in the sampled set $X$ and the generated set
${\mbox{\boldmath$Y$}}_{0}$. We use this kernel to pull the new points
${\mbox{\boldmath$Y$}}_{0}$ toward the sparse regions of the manifold
$\cal{M}$ using the row-stochastic diffusion operator $\hat{{P}}$ (see Sec.
3.1). We then apply the powered operator ${\mbox{\boldmath$\hat{{P}}$}}^{t}$
to ${\mbox{\boldmath$Y$}}_{0}$, which averages points in
${\mbox{\boldmath$Y$}}_{0}$ according to their neighbors in $X$.

The powered operator ${\mbox{\boldmath$\hat{{P}}$}}^{t}$ controls the
diffusion distance over which points are averaged; higher values of $t$ lead
to wider local averages over the manifold. The operator may be modeled as a
low pass filter in which higher powers decrease the cutoff frequency. Because
${\mbox{\boldmath$Y$}}_{0}$ is inherently noisy in the ambient space of the
data,
${\mbox{\boldmath$Y$}}_{t}={\mbox{\boldmath$\hat{{P}}$}}^{t}\cdot{\mbox{\boldmath$Y$}}_{0}$
is a denoised version of ${\mbox{\boldmath$Y$}}_{0}$ along $\cal{M}$. The
number of steps required can be set manually or using the Von Neumann Entropy
as suggested by Moon et al. (2017b). Because the filter
${\mbox{\boldmath$\hat{{P}}$}}^{t}\cdot{\mbox{\boldmath$Y$}}_{0}$ is not power
preserving, ${\mbox{\boldmath$Y$}}_{t}$ is rescaled to fit the range of
original values of $X$. A full description of the approach is given in Alg. 1.

Algorithm 1 SUGAR: Synthesis Using Geometrically Aligned Random-walks

Input: Dataset
${\mbox{\boldmath$X$}}=\\{{\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2},\ldots,{\mbox{\boldmath$x$}}_{N}\\},{\mbox{\boldmath$x$}}_{i}\in\mathbb{R}^{D}$.
Output: Generated set of points
${\mbox{\boldmath$Y$}}=\\{{\mbox{\boldmath$y$}}_{1},{\mbox{\boldmath$y$}}_{2},\ldots,$
${\mbox{\boldmath$y$}}_{M}\\},{\mbox{\boldmath$y$}}_{i}\in\mathbb{R}^{D}$.

1: Compute the diffusion geometry operators $K$, $P$, and degrees
$\hat{d}(i)$, $i=1,...,N$ (see Sec. 3)

2: Define a sparsity measure $\hat{s}(i),i=1,...,N$ (Eq. 2).

3: Estimate a local covariance ${\mbox{\boldmath$\Sigma$}}_{i}$, $i=1,...,N$,
using $k$ nearest neighbors around each ${\mbox{\boldmath$x$}}_{i}$.

4: For each point $i=1,...,N$ draw $\hat{\ell}(i)$ vectors (see Sec. 4.3) from
a Gaussian distribution
${\cal{N}}({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$\Sigma$}}_{i})$. Let
$\hat{{\mbox{\boldmath$Y$}}}_{0}$ be a matrix with these
$M=\sum^{N}_{i=1}\hat{\ell}(i)$ generated vectors as its rows.

5: Compute the sparsity based diffusion operator $\hat{{\mbox{\boldmath$P$}}}$
(see Sec 4.2).

6: Apply the operator $\hat{{\mbox{\boldmath$P$}}}$ at time instant $t$ to the
new generated points in $\hat{{\mbox{\boldmath$Y$}}}_{0}$ to get diffused
points as rows of
${{\mbox{\boldmath$Y$}}}_{t}=\hat{{\mbox{\boldmath$P$}}}^{t}\cdot{{\mbox{\boldmath$Y$}}}_{0}$.

7: Rescale ${\mbox{\boldmath$Y$}}_{t}$ to get the output
${\mbox{\boldmath$Y$}}[\cdot,j]={\mbox{\boldmath$Y$}}_{t}[\cdot,j]\cdot\frac{\text{percentile}({\mbox{\boldmath$X$}}[\cdot,j],.99)}{\max{{\mbox{\boldmath$Y$}}_{t}[\cdot,j]}}$,
$j=1,\ldots,D$, in order to fit the original range of feature values in the
data.

###  4.3 Manifold Density Equalization

The generation level $\hat{\ell}(i)$ in Alg. 1 (step 4), i.e., the amount of
points generated around each ${\mbox{\boldmath$x$}}_{i}$, determines the
distribution of points in ${\mbox{\boldmath$Y$}}_{1}$. Given a biased dataset
$X$, we wish to generate points in sparse regions such that the resulting
density over $\cal{M}$ becomes uniform. To do this we have proposed to draw
$\hat{\ell}(i)$ points around each point ${\mbox{\boldmath$x$}}_{i},i=1,...,N$
from ${\cal{N}}({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$\Sigma$}}_{i})$ (as
described in Alg. 1). The following proposition provides bounds on the
“correct” number of points $\hat{\ell}(i),i=1,...,N$ required to balance the
density over the manifold by equalizing the degrees $\hat{d}(i)$.

######  Proposition 4.1.

The generation level $\hat{\ell}(i)$ required to equalize the degree
$\hat{d}(i)$, is bounded by

$\det\left({\mbox{\boldmath$I$}}+\frac{{\mbox{\boldmath$\Sigma$}}_{i}}{2\sigma^{2}}\right)^{\frac{1}{2}}\frac{\max(\hat{d}(\cdot))-\hat{d}(i)}{\hat{d}(i)+1}-1\leq\;\hat{\ell}(i)\;\leq\det\left({\mbox{\boldmath$I$}}+\frac{{\mbox{\boldmath$\Sigma$}}_{i}}{2\sigma^{2}}\right)^{\frac{1}{2}}[{\max(\hat{d}(\cdot))-\hat{d}(i)}]\,,$

where $\hat{d}(i)$ is the degree value at point ${\mbox{\boldmath$x$}}_{i}$,
$\sigma^{2}$ is the bandwidth of the kernel $K$ (Eq. 1) and
${\mbox{\boldmath$\Sigma$}}_{i}$ is the covariance of the Gaussian designed
for generating new points (as described in Algorithm 1).

###### Proof.

Given ${\mbox{\boldmath$x$}}_{i}\in\mathbb{R}^{D},i=1,...,N$, the degree at
point ${\mbox{\boldmath$x$}}_{i}$ (section 4.2). SUGAR (Algorithm 1) generates
$\hat{\ell}(i)$ points around ${\mbox{\boldmath$x$}}_{i}$ from a Gaussian
distribution $N({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$\Sigma$}})$. After
generating $\hat{\ell}(i)$ points, the degree at point
${\mbox{\boldmath$x$}}_{i}$ is defined as

$\bar{d}(i)=\sum^{N}_{j=1}e^{-\frac{||{\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$x$}}_{j}||^{2}}{2\sigma^{2}}}+\sum^{\hat{\ell}(i)}_{\ell=1}e^{-\frac{||{\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$y$}}^{i}_{\ell}||^{2}}{2\sigma^{2}}}+\sum_{\tilde{\ell}}e^{-\frac{||{\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$y$}}_{\tilde{\ell}}||^{2}}{2\sigma^{2}}}.$
(3)

In order to equalize the distribution, we require that the expectation of the
degree be independent of ${\mbox{\boldmath$x$}}_{i}$, thus, we set
$\mathrm{E}\Big{[}\bar{d}(i)\Big{]}=\text{C},i=1,...,N$, where C is a constant
that will be addressed later in the proof. Further, we notice that the first
term on the right hand side of Eq. 3 can be substituted by $\hat{d}(i)$, while
the second term is a sum of $\hat{\ell}(i)$ random variables. The third term
accounts for the influence of points generated around
${\mbox{\boldmath$x$}}_{j},j\neq i$ on the degree at point
${\mbox{\boldmath$x$}}_{i}$. It is hard to find a closed form solution for the
number of points required at each $i$, however, based on two simple
assumptions we can derive bounds on the required value. First, to find an
upper bound, we assume that the points generated around
${\mbox{\boldmath$x$}}_{i}$ have negligible effect on the $\hat{d}(j)$ at
point $j\neq i$. This leads to an upper bound, because in practice the degree
is affected by other points as well. We note that this assumption should hold
with proper choices of $\sigma$ and
${\mbox{\boldmath$\Sigma$}}_{i},i=1,...,N$. By substituting the constant $C$,
the term $\hat{d}(i)$, and using the independence assumption, the expectation
of Eq. 4 can be written as

$\text{C}-\hat{d}(i)=\mathrm{E}\Big{[}\sum^{\hat{\ell}(i)}_{\ell=1}e^{-\frac{||{\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$y$}}^{i}_{\ell}||^{2}}{2\sigma^{2}}}\Big{]}.$
(4)

Then, since the variables ${\mbox{\boldmath$y$}}^{i}_{\ell}$ are i.i.d., then
the right hand side of Eq. 4 becomes

$\hat{\ell}(i)\mathrm{E}\Big{[}e^{-\frac{||{\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$y$}}^{i}||^{2}}{2\sigma^{2}}}\Big{]}=$
$\frac{\hat{\ell}(i)}{\det(2\pi{\mbox{\boldmath$\Sigma$}}_{i})^{1/2}}\int_{\mathbb{R}^{D}}{e^{-\frac{||{\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$y$}}^{i}||^{2}}{2\sigma^{2}}}}e^{-{({\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$y$}}^{i})^{T}{\mbox{\boldmath$\Sigma$}}^{-1}_{i}({\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$y$}}^{i})}}d{\mbox{\boldmath$y$}}^{i},$

and then using a change of variables
$\tilde{{\mbox{\boldmath$y$}}}={\mbox{\boldmath$y$}}^{i}-{\mbox{\boldmath$x$}}_{i}$,
the integral simplifies to

$\frac{\hat{\ell}(i)}{\det(2\pi{\mbox{\boldmath$\Sigma$}}_{i})^{1/2}}\int_{\mathbb{R}^{D}}e^{-{({\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$y$}}^{i})^{T}({\mbox{\boldmath$\Sigma$}}^{-1}_{i}+\frac{{\mbox{\boldmath$I$}}}{2\sigma^{2}})({\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$y$}}^{i})}}d{\mbox{\boldmath$y$}}^{i}=$
$\frac{\hat{\ell}(i)}{\det({\mbox{\boldmath$I$}}+\frac{\det({\mbox{\boldmath$\Sigma$}}_{i})}{2\sigma^{2}})^{0.5}},$

where the final step is based on the integral of a Gaussian and a change of
variables. Finally, this leads to an upper bound on the number of points
$\hat{\ell}(i)$ is
$\hat{\ell}(i)\leq\det({\mbox{\boldmath$I$}}+\frac{\det({\mbox{\boldmath$\Sigma$}}_{i})}{2\sigma^{2}})^{0.5}[C-\hat{d}(i)]$.
By choosing $C=\max(\hat{d}(\cdot))$ we guarantee that $\hat{\ell}(i)\geq 0$
(which means that we are not removing points).

Now, by considering the third term on the right side of Eq. 3 we derive a
lower bound on $\hat{\ell}(i)$. The term
$\sum_{\tilde{\ell}}e^{-\frac{||{\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$y$}}_{\tilde{\ell}}||^{2}}{2\sigma^{2}}}$
accounts for points generated around neighbor points around
${\mbox{\boldmath$x$}}_{i}$. The number of points in the region of
$||{\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$x$}}_{j}||^{2}\sim\sigma^{2}$ is
proportional to the degree $\hat{d}(i)$. For the lower bound, we assume that
the number of points generated by each neighbor of ${\mbox{\boldmath$x$}}_{i}$
is no more than $\hat{\ell}(i)+1$. This assumption becomes realistic by
imposing smoothness on the function $\hat{\ell}(i)$. Plugging this assumption
and the degree value as a measure of connectivity into Eq. 3 we get that

$\bar{d}(i)\leq\hat{d}(i)+\sum^{\hat{\ell}(i)}_{\ell=1}e^{-\frac{||{\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$y$}}^{i}_{\ell}||^{2}}{2\sigma^{2}}}+\hat{d}(i)\sum^{\hat{\ell}(i)+1}_{\tilde{\ell}=1}e^{-\frac{||{\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$y$}}_{\tilde{\ell}}||^{2}}{2\sigma^{2}}},$

we now take the expectation of both sides

$C\leq\hat{d}(i)+\mathrm{E}\Big{[}\sum^{\hat{\ell}(i)}_{\ell=1}e^{-\frac{||{\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$y$}}^{i}_{\ell}||^{2}}{2\sigma^{2}}}\Big{]}+\hat{d}(i)\mathrm{E}\Big{[}\sum^{\hat{\ell}(i)+1}_{\tilde{\ell}=1}e^{-\frac{||{\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$y$}}_{\tilde{\ell}}||^{2}}{2\sigma^{2}}}\Big{]}\leq\hat{d}(i)+[\hat{d}(i)+1]\mathrm{E}\Big{[}\sum^{\hat{\ell}(i)+1}_{{\ell}=1}e^{-\frac{||{\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$y$}}^{i}_{{\ell}}||^{2}}{2\sigma^{2}}}\Big{]},$

by replacing ${\mbox{\boldmath$y$}}_{\tilde{\ell}}$ by
${\mbox{\boldmath$y$}}^{i}_{\tilde{\ell}}$ we increase the expectation value.
Finally, exploiting the i.i.d assumption and the Gaussian distribution we
conclude that by replacing the mean with similar steps as used for the upper
bound we conclude that

$\det({\mbox{\boldmath$I$}}+\frac{{\mbox{\boldmath$\Sigma$}}_{i}}{2\sigma^{2}})^{0.5}[{\max(\hat{d}(\cdot))-\hat{d}(i)}]/[\hat{d}(i)+1]-1\leq\hat{\ell}(i).$

∎

In practice we suggest to use the mean of the upper and lower bound to set the
number of generated points $\hat{\ell}(i)$. In Sec. 5.1 we demonstrate how the
proposed scheme enables density equalization using few iterations of SUGAR.

##  5 Experimental Results

###  5.1 Density Equalization

Given the circular manifold recovered in Sec. 5.4, we next sought to evaluate
the density equalization properties proposed in Sec. 4.3. We begin by sampling
one hundred points from a circle such that the highest density is at the
origin ($\theta=0$) and the density decreases away from it (Fig. 1, colored by
degree $\hat{d}(i)$). SUGAR was then used to generate new points based on
$\hat{\ell}(i)$ around each original point (Fig. 1, before diffusion, 1, after
diffusion). We repeat this process for different initial densities and
evaluate the resulting distribution of point against the amount of iteration
of SUGAR. We perform a Kolmogorov-Smirnov (K-S) test to determine if the
points came from a uniform distribution. The resulting P-values are presented
in Fig. 1.

Figure 1: Density equalization demonstrated on a circle shaped manifold. 1 The
original non-uniform samples of $X$. 1 The original points $X$ (black
asterisks) and set of new generated points ${\mbox{\boldmath$Y$}}_{0}$ (blue
circles). 1 The final set of points $Z$, original points $X$ (black asterisks)
and set of new generated points ${\mbox{\boldmath$Y$}}_{t}$ (blue circles). In
this example only one diffusion time step is required (i.e. $t=1$). 1 The
p-values of a Kolmogorov-Smirnov (K-S) test comparing to a uniform
distribution, the x-axis represents the number of SUGAR iterations ran.

###  5.2 Artificial Manifolds

In the next experiment, we evaluate SUGAR on a Swiss roll, a popular manifold
widely used for non-linear dimensionality reduction. We apply SUGAR to a non-
uniformly generated Swiss roll. The Swiss roll $X$ is generated by applying
the following construction steps:

  * •

The random variables $\theta_{i},h_{i},i=1,...,N$, are drawn from the
distributions ${P(\theta)},P(h)$ respectively.

  * •

A 3-dimensional Swiss roll is constructed based on the following function

${{\mbox{\boldmath$X$}}_{i}=\begin{bmatrix}{x_{i}}^{1}\\\ {x_{i}}^{2}\\\
{x_{i}}^{3}\\\ \end{bmatrix}=\begin{bmatrix}{6\theta_{i}\cos(\theta_{i})}\\\
{h_{i}}\\\ {6\theta_{i}\sin(\theta_{i})}\\\ \end{bmatrix},i=1,...,N.}$ (5)

In Fig. 2 we show a Swiss roll where $\theta_{i},i=1,...,N$ is drawn from a
nonuniform distribution within the range
$[\frac{3\cdot\pi}{2},\frac{9\cdot\pi}{2}]$. Density of points decreases at
higher values of $\theta_{i}$. The values $h_{i},i=1,...,N$ are drawn from a
uniform distribution within the range $[0,20]$ and we use $N=600$ points.

(a)

Figure 2: 2 A Swiss roll generated using Eq. 5. The variables $h_{i}$ are
drawn from uniform distribution within the interval $[0,100]$, while
$\theta_{i}$ are drawn from a nonuniform distribution. Points are colored by
their degree value $\hat{d}(i)$. 2(a) The Swiss roll $X$ (black asterisk) and
new generated points ${\mbox{\boldmath$Y$}}_{0}$ (blue circle). Points are
generated based on step 4 in Alg. 1. 2 The points after applying the MGC
operator $\hat{{\mbox{\boldmath$P$}}}^{t}$ (steps 6-7 Alg. 1). Only one
diffusion time step is required (i.e. $t=1$). 2 An estimate of the CDF based
on the first embedding (DM) coordinate of
${\mbox{\boldmath$X$}}\cup{\mbox{\boldmath$Y$}}$.

The Swiss roll is 3-dimensional but governed by one angular parameter. Thus,
it allows us to evaluate whether SUGAR generates points uniformly along the
Swiss roll’s angular parameter. In the following, we apply Alg. 1 to the Swiss
roll presented in Fig. 2. In Fig. 2(a) we present the original data $X$ and
the generated points ${\mbox{\boldmath$Y$}}_{0}$. The points are generated
based on steps 1-4 in Alg. 1. After applying the MGC diffusion operator the
points are pulled toward the Swiss roll structure. The points after applying
the MGC operator $\hat{{\mbox{\boldmath$P$}}}$ are presented in Fig. 2. In
these figures the points are colored by their degree value $\hat{d}(i)$. In
Fig. 2 we present the estimated CDF before and after applying SUGAR to $X$.
The resulted CDF resembles the CDF of a uniform distribution plotted in red.
The variance of the degree $\hat{d}(i)$ drops from 0.19 to 0.09 when comparing
$X$ and $Z$.

###  5.3 Bunny Manifold

In the following experiment, we evaluate the performance of SUGAR on the
“Stanford Bunny”. The “Stanford Bunny” is a set of points representing a 3-d
surface of a bunny. We subsample the points on the surface such that the
unevenly sampled set of points $X$ consists of 900 points. The data set $X$
colored by the degree estimate at each point is presented in Fig. 3(a). Then,
we generate a set of new points ${\mbox{\boldmath$Y$}}_{0}$ based on steps 1-4
of Algorithm 1. The unified set of points
${\mbox{\boldmath$X$}}\cup{\mbox{\boldmath$Y$}}_{0}$ is presented in Fig.
3(b). In the final step, we apply the MGC operator
${\mbox{\boldmath$P$}}^{t}$, at $t=1$, the final set of points
${\mbox{\boldmath$Z$}}={\mbox{\boldmath$X$}}\cup{\mbox{\boldmath$Y$}}$ is
presented in Fig. 3(c). The set $Z$ colored by the degree value $\hat{d}(i)$
is presented in Fig. 3(d).

(a)

.

(b)

(c)

(d)

Figure 3: 3(a) A subset $X$ with 900 points from the Stanford Bunny. Points
are colored by their degree value $\hat{d}(i)$. 3(b) The original and
generated points ${\mbox{\boldmath$X$}}\cup{\mbox{\boldmath$Y$}}_{0}$, black
asterisks- $X$ original points, blue circles - new points
${\mbox{\boldmath$Y$}}_{0}$. 3(c) The original $X$ and the set $Y$. $Y$ is the
set of generated points after applying the MGC diffusion operator
$\hat{{\mbox{\boldmath$P$}}}$ (steps 6-7 of Alg. 1). 3(d) The final set again
colored by the degree value $\hat{d}(i)$ at each point.

In this experiment, the output of SUGAR has preserved the complex structure of
the 3-d Bunny manifold. The variance of the degree $\hat{d}(i)$ in this
example, drops from 0.24 to 0.019 when comparing $X$ and $Z$.

###  5.4 MNIST Manifold

In the following experiment we empirically demonstrate ability of SUGAR to
fill in missing samples and compare it to a Variational Autoencoder (VAE)
(Kingma & Welling, 2013) which has an implicit probabilistic model of the
data. Note that we are not able to use other density estimates in general due
to the high dimensionality of datasets and the inability of density estimates
to scale to high dimensions. To begin, we rotated an example of a handwritten
‘6’ from the MNIST dataset in $N=320$ different angles non-uniformly sampled
over the range $[0,2\pi]$. This circular construction was recovered by the
diffusion maps embedding of the data, with points towards the undersampled
regions having a lower degree than other regions of the embedding (Fig. 4,
left, colored by degree). We then generated new points around each sample in
the rotated data according to Alg. 1. We show the results of SUGAR before and
after diffusion in Fig. 4 (top and bottom right, respectively).

Figure 4: A 2-dimensional DM representation of: (left) Original data, 320
rotated images of handwritten ’6’ colored by the degree value $\hat{d}(i)$.
(middle) VAE output; (right, top) SUGAR augmented data before diffusion (i.e.
$t=0$); (right,bottom) SUGAR augmented data with one step of diffusion
($t=1$). Black asterisks - original data; Blue circles - output data.

Next, we compared our results to a 2-layer VAE trained over the original data
(Fig. 4, middle). Both SUGAR ($t=1$) and the VAE generated points along the
circular structure of the original manifold. Examples images from both
techniques are presented in Fig. 4. Notably, the VAE generated images similar
to the original angle distribution, such that sparse regions of the manifold
were not filled. In contrast, points generated by SUGAR occupied new angles
not present in the original data but clearly present along the circular
manifold. This example illustrates the ability of SUGAR to recover sparse
areas of a data manifold.

###  5.5 Classification of Imbalanced Data

The loss functions of many standard classification algorithms are global;
these algorithms are thus easily biased when trained on imbalanced datasets.
Imbalanced training typically manifests in poor classification of rare
samples. These rare samples are often important (Weiss, 2004). For example,
the preponderance of healthy individuals in medical data can obscure the
diagnosis of rare diseases.

Resampling and boosting strategies have been used to combat data imbalance.
Removing points (undersampling) is a simple solution, but this strategy leads
to information loss and can decrease generalization performance. RUSBoost
(Seiffert et al., 2010) combines this approach with boosting, a technique that
resamples the data using a set of weights learned by iterative training.
Oversampling methods remove class imbalance by generating synthetic data
alongside the original data. Synthetic Minority Over-sampling Technique
(SMOTE) (Chawla et al., 2002) oversamples by generating points along lines
between existing points of minority classes.

We compared SUGAR, RUSBoost, and SMOTE for improving k-NN and kernel SVM
classification of 60 imbalanced data sets of varying size (from hundreds to
thousands) and imbalance ratio (1.8–130) (Alcalá-Fdez et al., 2009).
$\text{Precision}=\frac{TP}{TP+FP}$ and $\text{Recall}=\frac{TP}{TP+FN}$ were
chosen to quantify classification performance. These metrics capture
classification accuracy in light of data imbalance; precision measures the
fraction of true positives to false positives, while recall measures the
fraction of true positives identified. These measures are extended to multiple
classes via average class precision and recall (ACP and ACR), which are
defined as $\text{ACP}=\sum^{C}_{c=1}{\text{Precision}(class=c)}/C$ and
$\text{ACR}=\sum^{C}_{c=1}{\text{Recall}(class=c)}/C$. These measure ignore
class population biases by equally weighting classes. This experiment is
summarized in Table 1 (see appendix for full details).

|  | Knn |  |  | SVM |  | RusBOOST
---|---|---|---|---|---|---|---
| Orig | SMOTE | SUGAR | Orig | SMOTE | SUGAR |
ACP | 0.67 | 0.76 | 0.78 | 0.77 | 0.77 | 0.77 | 0.75
ACR | 0.64 | 0.73 | 0.77 | 0.78 | 0.78 | 0.84 | 0.81
Table 1: Average class precision (ACP) and class recall (ACR) for KNN (10-fold
cross validation) and kernel SVM classifiers before and after SMOTE, SUGAR,
and RusBOOST(SVM only)

###  5.6 Clustering of Imbalanced Data

In order to examine the effect of SUGAR on clustering, we performed spectral
clustering on a set of Gaussians in the shape of the word “SUGAR” (top panel,
Fig. 5(a)). Next, we altered the mixtures to sample heavily towards points on
the edges of the word (middle panel, Fig. 5(a)). This perturbation disrupted
letter clusters. Finally, we performed SUGAR on the biased data to recreate
data along the manifold. The combined data and its resultant clustering is
shown in the bottom panel of Fig. 5(a) revealing that the letter clustering
was restored after SUGAR.

The effect of sample density on spectral clustering is evident in the
eigendecomposition of the graph Laplacian, which describes the connectivity of
the graph and is the basis for spectral clustering. We shall focus on the
multiplicity of the zero eigenvalue, which codes for the number of connected
components of a graph. In our example, we see that the zero eigenvalue for the
ground truth and SUGAR graphs has a multiplicity of $5$ whereas the corrupted
graph only has a multiplicity of $4$ (see Fig. 5(b)). This connectivity
difference arises from the $k$-neighborhoods of points in each ground truth
cluster. We note that variation in sample density disrupts the
$k$-neighborhood of points in the downsampled region to include points outside
of their ground truth cluster. These connections across the letters of “SUGAR”
thus lead to a lower multiplicity of the zero eigenvalue, which negatively
affects the spectral clustering. Augmenting the biased data via SUGAR
equalizes the sampling density, restoring ground-truth neighborhood structure
to the graph built on the data.

(a)

(b)

(c)

Figure 5: Augmented clustering using SUGAR. 5(a) Spectral clustering of a
mixed Gaussian (top panel) with uneven sample density(middle panel). After
SUGAR(bottom panel), the original cluster geometries are recovered. 5(b) Graph
Laplacian eigenvalues from 5(a). The corrupted graph has a lower multiplicity
of the 0 eigenvalue, indicating fewer components. 5(c) Rand Index of 115 data
sets clustered by k-means before and after applying SUGAR. (Alcalá-Fdez et
al., 2009)

Next, we explored the effects of SUGAR on traditional k-means across 115
datasets obtained from Alcalá-Fdez et al. (2009). K-means was performed using
the ground truth number of clusters, and the Rand Index (RI) (Hubert & Arabie,
1985) between the ground truth clustering and the empirical clustering was
taken (Fig. 5(c), x-axis). Subsequently, SUGAR was used to generate new points
for clustering with the original data. The RI over the original data was again
computed, this time using the SUGAR clusters (Fig. 5(c), y-axis). Our results
indicate the SUGAR can be used to improve the cluster quality of k-means.

###  5.7 Biological Manifolds

Next, we used SUGAR for exploratory analysis of a biological dataset. In
Velten et al. (2017), a high dimensional yet small
($\mathbf{X}\in\mathbb{R}^{1029\times 12553}$) single cell RNA sequencing
dataset was collected to elucidate the development of human blood cells, which
is posited to form a continuum of development trajectories from a central
reservoir of immature cells. This dataset thus represents an ideal substrate
to explore manifold learning (Moon et al., 2017a). However, the data presents
two distinct challenge due to 1) undersampling of cell types and 2) dropout
and artifacts associated with single cell RNA sequencing (Kim et al., 2015).
These challenges stand at odds with a central task of computational biology,
the characterization of gene-gene interactions which foment phenotypes.

We first sought to enrich rare phenotypes in the Velten data by generating
$\mathbf{Y}\in\mathbb{R}^{4116\times 12553}$ new points with SUGAR. A useful
tool for this analysis is the ’gene module’, a pair or set of genes that are
expressed together to drive phenotype development. K-means clustering of the
augmented data over 14 principal gene modules (32 dimensions) revealed 6 cell
types described in Velten et al. (2017) and a 7th cluster consisting of mature
B-cells (Fig. 6(a)). Analysis of population prevalence before and after SUGAR
revealed a dramatic enrichment of mature B and pre-B cells,
eosinophil/basophil/mast cells (EBM), and neutrophils (N), while previously
dominant megakaryocytes (MK) became a more equal portion of the post-SUGAR
population (Fig. 6(b)). These results demonstrate the ability of SUGAR to
balance population prevalence along a data manifold.

In Fig. 6(c), we examine the effect of SUGAR on intra-module relationships.
Because expression of genes in a module are molecularly linked, intra-module
relationships should be strong in the absence of sampling biases and
experimental noise. After SUGAR, we note an improvement in linear regression
($r^{2}$) and scaled mutual information coefficients. We note that in some
cases the change in mutual information was stronger than linear regression,
likely due to nonlinearities in the module relationship. Because this
experiment was based on putative intra-module relationships we next sought to
identify strong improvements in regression coefficients de novo. To this end,
we compared the relationship of the B cell maturation marker CD19 with the
entire dataset before and after SUGAR. In Fig. 6(d) we show three
relationships with marked improvement from the original data (top panel) to
the augmented data (bottom panel). The markers uncovered by this search,
HOXA3, CASP1, and EAF2, each have disparate relationships with CD19. HOXA3
marks stem cell immaturity, and is negatively correlated with CD19. In
contrast, CASP1 is known to mark commitment to the B cell lineage (Velten et
al., 2017). After SUGAR, both of these relationships were enhanced. EAF2 is a
part of a module that is expressed during early development of neutrophils and
monocytes; we observe that its correlation and mutual information with B cell
maturation are also increased after SUGAR. We note that in light of the early
development discussed by Velten et al. (2017), this new relationship seems
problematic. In fact, Li et al. (2016) showed that EAF2 is upregulated in
mature B cells as a mechanism against autoimmunity. Taken together, our
analyses show that SUGAR is effective for bolstering relationships between
dimensions in the absence of prior knowledge for exploratory data analysis.

(a)

(b)

(c)

(d)

Figure 6: SUGAR was used to augment a biological dataset collected by Velten
et al. (2017). 6(a) Augmented data embedded with PHATE (Moon et al., 2017b)
and colored by k-means over the gene module dimensions identified by Velten et
al. (2017). 7 canonical cell types are present. EBM: eosinophil/basophil/mast
cells; N: neutrophils; MD: monocytes/dendritic cells; E: erythroid cells; MK:
megakaryocytes; Pre-B: immature B cell; B: mature B cell. 6(b) Cell type
prevalence before and after applying SUGAR. 6(c) Explained variation (linear
regression) and scaled mutual information
($\frac{\text{MI}_{i}}{\max{\text{MI}}}$) between the components of the 14
coexpression modules identified by Velten et al. (2017). 6(d) Relationship
between CD19 (a B cell maturation marker) and HOXA3 (a cell immaturity
marker), CASP1 (a B cell linear commitment marker), and EAF2 (a marker for two
non-B cell types)

##  6 Conclusion

We proposed SUGAR as a new type of generative model for data, based on
learning geometry rather than the density of the data. This enables us to
compensate for sparsity and heavily biased sampling in many data types of
interest, especially biomedical data. We assume that the training data lies on
a low-dimensional manifold. The manifold assumption is usually valid in many
datasets (e.g., single cell RNA sequencing (Moon et al., 2017a)) as they are
globally high-dimensional but locally generated by a small number of factors.
We use a diffusion kernel to capture the manifold structure. Then, we generate
new points along the incomplete manifold by randomly generating points at
sparse areas. Finally, we use a weighted transition kernel to pull the new
points towards the structure of the manifold. The method demonstrated
promising results on synthetic data, MNIST images, and high dimensional
biological datasets in applications such as clustering, classification and
mutual information relationship analysis. Future work will apply SUGAR to
study extremely biased biological datasets and improve classification and
regression performance on them.

## References

  * Alcalá-Fdez et al. (2009) Alcalá-Fdez, Jesús, Sanchez, Luciano, Garcia, Salvador, del Jesus, Maria Jose, Ventura, Sebastian, Garrell, Josep Maria, Otero, José, Romero, Cristóbal, Bacardit, Jaume, Rivas, Victor M, et al.  Keel: a software tool to assess evolutionary algorithms for data mining problems.  _Soft Computing_ , 13(3):307–318, 2009.
  * Bengio & Monperrus (2005) Bengio, Yoshua and Monperrus, Martin.  Non-local manifold tangent learning.  In _Advances in Neural Information Processing Systems_ , pp. 129–136, 2005.
  * Bengio et al. (2006) Bengio, Yoshua, Larochelle, Hugo, and Vincent, Pascal.  Non-local manifold parzen windows.  In _Advances in neural information processing systems_ , pp. 115–122, 2006.
  * Bermanis et al. (2016) Bermanis, Amit, Wolf, Guy, and Averbuch, Amir.  Diffusion-based kernel methods on euclidean metric measure spaces.  _Applied and Computational Harmonic Analysis_ , 41(1):190–213, 2016.
  * Bernardo et al. (2003) Bernardo, JM, Bayarri, MJ, Berger, JO, Dawid, AP, Heckerman, D, Smith, AFM, West, M, et al.  The variational bayesian em algorithm for incomplete data: with application to scoring graphical model structures.  _Bayesian statistics_ , 7:453–464, 2003.
  * Brubaker et al. (2012) Brubaker, Marcus, Salzmann, Mathieu, and Urtasun, Raquel.  A family of mcmc methods on implicitly defined manifolds.  In _Artificial Intelligence and Statistics_ , pp. 161–172, 2012\.
  * Chawla et al. (2002) Chawla, Nitesh V, Bowyer, Kevin W, Hall, Lawrence O, and Kegelmeyer, W Philip.  Smote: synthetic minority over-sampling technique.  _Journal of artificial intelligence research_ , 16:321–357, 2002.
  * Coifman & Lafon (2006) Coifman, Ronald R. and Lafon, Stéphane.  Diffusion maps.  _Applied and Computational Harmonic Analysis_ , 21(1):5 – 30, 2006.
  * Doersch (2016) Doersch, Carl.  Tutorial on variational autoencoders.  _arXiv preprint arXiv:1606.05908_ , 2016.
  * Giné & Guillou (2002) Giné, Evarist and Guillou, Armelle.  Rates of strong uniform consistency for multivariate kernel density estimators.  In _Annales de l’Institut Henri Poincare (B) Probability and Statistics_ , volume 38, pp. 907–921. Elsevier, 2002.
  * Girolami & Calderhead (2011) Girolami, Mark and Calderhead, Ben.  Riemann manifold langevin and hamiltonian monte carlo methods.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 73(2):123–214, 2011.
  * Goodfellow et al. (2014) Goodfellow, Ian, Pouget-Abadie, Jean, Mirza, Mehdi, Xu, Bing, Warde-Farley, David, Ozair, Sherjil, Courville, Aaron, and Bengio, Yoshua.  Generative adversarial nets.  In _Advances in neural information processing systems_ , pp. 2672–2680, 2014.
  * Grün et al. (2015) Grün, Dominic, Lyubimova, Anna, Kester, Lennart, Wiebrands, Kay, Basak, Onur, Sasaki, Nobuo, Clevers, Hans, and van Oudenaarden, Alexander.  Single-cell messenger rna sequencing reveals rare intestinal cell types.  _Nature_ , 525(7568):251, 2015.
  * He & Garcia (2009) He, Haibo and Garcia, Edwardo A.  Learning from imbalanced data.  _IEEE Transactions on knowledge and data engineering_ , 21(9):1263–1284, 2009.
  * Hensman & Masko (2015) Hensman, Paulina and Masko, David.  The impact of imbalanced training data for convolutional neural networks.  _Degree Project in Computer Science, KTH Royal Institute of Technology_ , 2015.
  * Hubert & Arabie (1985) Hubert, Lawrence and Arabie, Phipps.  Comparing partitions.  _Journal of classification_ , 2(1):193–218, 1985\.
  * Keller et al. (2010) Keller, Yosi, Coifman, Ronald R, Lafon, Stéphane, and Zucker, Steven W.  Audio-visual group recognition using diffusion maps.  _IEEE Transactions on Signal Processing_ , 58(1):403–413, 2010.
  * Kim et al. (2015) Kim, Jong Kyoung, Kolodziejczyk, Aleksandra A, Ilicic, Tomislav, Teichmann, Sarah A, and Marioni, John C.  Characterizing noise structure in single-cell rna-seq distinguishes genuine from technical stochastic allelic expression.  _Nature communications_ , 6:8687, 2015.
  * Kingma & Welling (2013) Kingma, Diederik P and Welling, Max.  Auto-encoding variational bayes.  _arXiv preprint arXiv:1312.6114_ , 2013.
  * Krishnaswamy et al. (2014) Krishnaswamy, Smita, Spitzer, Matthew H, Mingueneau, Michael, Bendall, Sean C, Litvin, Oren, Stone, Erica, Pe’er, Dana, and Nolan, Garry P.  Conditional density-based analysis of t cell signaling in single-cell data.  _Science_ , 346(6213):1250689, 2014.
  * Li et al. (2016) Li, Yingqian, Takahashi, Yoshimasa, Fujii, Shin-ichiro, Zhou, Yang, Hong, Rongjian, Suzuki, Akari, Tsubata, Takeshi, Hase, Koji, and Wang, Ji-Yang.  Eaf2 mediates germinal centre b-cell apoptosis to suppress excessive immune responses and prevent autoimmunity.  _Nature communications_ , 7:10836, 2016.
  * Lindenbaum et al. (2017) Lindenbaum, Ofir, Salhov, Moshe, Yeredor, Arie, and Averbuch, Amir.  Kernel scaling for manifold learning and classification.  _arXiv preprint arXiv:1707.01093_ , 2017.
  * López et al. (2013) López, Victoria, Fernández, Alberto, García, Salvador, Palade, Vasile, and Herrera, Francisco.  An insight into classification with imbalanced data: Empirical results and current trends on using data intrinsic characteristics.  _Information Sciences_ , 250:113–141, 2013.
  * Moon et al. (2017a) Moon, Kevin R, Stanley, Jay, Burkhardt, Daniel, van Dijk, David, Wolf, Guy, and Krishnaswamy, Smita.  Manifold learning-based methods for analyzing single-cell rna-sequencing data.  _Current Opinion in Systems Biology_ , 2017a.
  * Moon et al. (2017b) Moon, Kevin R, van Dijk, David, Wang, Zheng, Burkhardt, Daniel, Chen, William, van den Elzen, Antonia, Hirn, Matthew J, Coifman, Ronald R, Ivanova, Natalia B, Wolf, Guy, et al.  Visualizing transitions and structure for high dimensional data exploration.  _bioRxiv_ , pp. 120378, 2017b.
  * Öztireli et al. (2010) Öztireli, A Cengiz, Alexa, Marc, and Gross, Markus.  Spectral sampling of manifolds.  In _ACM Transactions on Graphics (TOG)_ , volume 29, pp. 168. ACM, 2010.
  * Rasmussen (2000) Rasmussen, Carl Edward.  The infinite gaussian mixture model.  In _Advances in neural information processing systems_ , pp. 554–560, 2000.
  * Scott (1985) Scott, David W.  Averaged shifted histograms: effective nonparametric density estimators in several dimensions.  _The Annals of Statistics_ , pp. 1024–1040, 1985.
  * Scott (2008) Scott, David W.  Kernel density estimators.  _Multivariate Density Estimation: Theory, Practice, and Visualization_ , pp. 125–193, 2008.
  * Seaman & Powell (1996) Seaman, D Erran and Powell, Roger A.  An evaluation of the accuracy of kernel density estimators for home range analysis.  _Ecology_ , 77(7):2075–2085, 1996.
  * Seiffert et al. (2010) Seiffert, Chris, Khoshgoftaar, Taghi M, Van Hulse, Jason, and Napolitano, Amri.  Rusboost: A hybrid approach to alleviating class imbalance.  _IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans_ , 40(1):185–197, 2010.
  * Singer et al. (2009) Singer, Amit, Erban, Radek, Kevrekidis, Ioannis G, and Coifman, Ronald R.  Detecting intrinsic slow variables in stochastic dynamical systems by anisotropic diffusion maps.  _Proceedings of the National Academy of Sciences_ , 106(38):16090–16095, 2009.
  * Varanasi & Aazhang (1989) Varanasi, Mahesh K and Aazhang, Behnaam.  Parametric generalized gaussian density estimation.  _The Journal of the Acoustical Society of America_ , 86(4):1404–1415, 1989.
  * Velten et al. (2017) Velten, Lars, Haas, Simon F, Raffel, Simon, Blaszkiewicz, Sandra, Islam, Saiful, Hennig, Bianca P, Hirche, Christoph, Lutz, Christoph, Buss, Eike C, Nowak, Daniel, et al.  Human haematopoietic stem cell lineage commitment is a continuous process.  _Nat. Cell Biol_ , 19:271–281, 2017.
  * Vincent & Bengio (2003) Vincent, Pascal and Bengio, Yoshua.  Manifold parzen windows.  In _Advances in neural information processing systems_ , pp. 849–856, 2003.
  * Weiss (2004) Weiss, Gary M.  Mining with rarity: a unifying framework.  _ACM Sigkdd Explorations Newsletter_ , 6(1):7–19, 2004.
  * Wu (2012) Wu, Junjie.  The uniform effect of k-means clustering.  In _Advances in K-means Clustering_ , pp. 17–35. Springer, 2012\.
  * Xuan et al. (2013) Xuan, Li, Zhigang, Chen, and Fan, Yang.  Exploring of clustering algorithm on class-imbalanced data.  In _Computer Science & Education (ICCSE), 2013 8th International Conference on_, pp. 89–93. IEEE, 2013.
  * Zelnik-Manor & Perona (2005) Zelnik-Manor, Lihi and Perona, Pietro.  Self-tuning spectral clustering.  In _Advances in neural information processing systems_ , pp. 1601–1608, 2005.

##  7 Appendix

Table 2: Classification recall on the 60 imbalanced datasets. |  |  | Recall |  |  |  |
---|---|---|---|---|---|---|---
|  | Knn |  |  | SVM |  |
| Orig | SMOTE | SUGAR | Orig | SMOTE | SUGAR | RusBOOST
ecoli-013 | 0.50 | 0.67 | 0.72 | 0.63 | 0.64 | 0.70 | 0.66
ecoli-013 | 0.61 | 0.66 | 0.71 | 0.65 | 0.64 | 0.71 | 0.66
ecoli1 | 0.57 | 0.57 | 0.66 | 0.58 | 0.57 | 0.65 | 0.57
ecoli2 | 0.51 | 0.56 | 0.63 | 0.62 | 0.61 | 0.68 | 0.54
ecoli3 | 0.80 | 0.73 | 0.79 | 0.85 | 0.84 | 0.89 | 0.85
glass-0123 | 0.73 | 0.89 | 0.90 | 0.94 | 0.94 | 0.95 | 0.92
glass-0162 | 0.50 | 0.53 | 0.60 | 0.69 | 0.70 | 0.67 | 0.74
glass-0165 | 0.50 | 0.64 | 0.70 | 0.69 | 0.69 | 0.80 | 0.75
glass0 | 0.72 | 0.73 | 0.80 | 0.83 | 0.83 | 0.80 | 0.83
glass1 | 0.61 | 0.74 | 0.70 | 0.74 | 0.76 | 0.80 | 0.77
glass2 | 0.58 | 0.63 | 0.64 | 0.72 | 0.74 | 0.69 | 0.74
glass4 | 0.52 | 0.78 | 0.78 | 0.71 | 0.71 | 0.87 | 0.84
glass5 | 0.54 | 0.68 | 0.71 | 0.67 | 0.67 | 0.76 | 0.74
glass6 | 0.83 | 0.86 | 0.93 | 0.82 | 0.82 | 0.93 | 0.87
haberman | 0.52 | 0.59 | 0.63 | 0.62 | 0.59 | 0.66 | 0.59
new-thyroid1 | 0.88 | 0.91 | 0.95 | 0.99 | 0.99 | 0.99 | 0.95
new-thyroid2 | 0.75 | 0.85 | 0.93 | 0.99 | 0.99 | 0.99 | 0.95
pb-134 | 0.61 | 0.82 | 0.94 | 0.78 | 0.91 | 0.93 | 0.95
pb-0 | 0.85 | 0.88 | 0.90 | 0.95 | 0.95 | 0.95 | 0.94
pima | 0.63 | 0.63 | 0.66 | 0.73 | 0.71 | 0.74 | 0.71
segment0 | 0.96 | 0.99 | 0.99 | 0.99 | 1.00 | 1.00 | 0.99
shuttle-c24 | 0.70 | 0.70 | 0.70 | 0.65 | 0.68 | 0.70 | 0.50
vehicle0 | 0.86 | 0.92 | 0.92 | 0.92 | 0.91 | 0.97 | 0.95
vehicle1 | 0.56 | 0.57 | 0.62 | 0.68 | 0.69 | 0.85 | 0.67
vehicle2 | 0.78 | 0.84 | 0.86 | 0.94 | 0.92 | 0.97 | 0.93
vehicle3 | 0.56 | 0.56 | 0.61 | 0.67 | 0.69 | 0.85 | 0.68
vowel0 | 0.90 | 0.99 | 0.99 | 0.98 | 1.00 | 1.00 | 0.98
wisconsin | 0.95 | 0.96 | 0.96 | 0.97 | 0.97 | 0.97 | 0.96
yeast-0567 | 0.51 | 0.60 | 0.65 | 0.74 | 0.73 | 0.79 | 0.80
yeast-1289 | 0.50 | 0.50 | 0.66 | 0.60 | 0.57 | 0.69 | 0.71
yeast-1458 | 0.50 | 0.50 | 0.57 | 0.61 | 0.59 | 0.60 | 0.65
yeast-17 | 0.50 | 0.54 | 0.65 | 0.64 | 0.63 | 0.71 | 0.79
yeast-24 | 0.62 | 0.77 | 0.78 | 0.81 | 0.83 | 0.89 | 0.85
yeast-28 | 0.63 | 0.68 | 0.73 | 0.61 | 0.57 | 0.74 | 0.72
yeast1 | 0.62 | 0.65 | 0.68 | 0.71 | 0.70 | 0.71 | 0.72
yeast3 | 0.81 | 0.81 | 0.90 | 0.88 | 0.87 | 0.92 | 0.87
yeast4 | 0.63 | 0.66 | 0.71 | 0.72 | 0.73 | 0.81 | 0.84
yeast5 | 0.71 | 0.82 | 0.87 | 0.90 | 0.91 | 0.95 | 0.88
yeast6 | 0.70 | 0.78 | 0.79 | 0.80 | 0.79 | 0.86 | 0.84
ecoli-0145 | 0.73 | 0.83 | 0.90 | 0.84 | 0.84 | 0.93 | 0.84
ecoli-0-147 | 0.56 | 0.77 | 0.77 | 0.80 | 0.81 | 0.85 | 0.85
ecoli-01475 | 0.54 | 0.83 | 0.85 | 0.87 | 0.88 | 0.92 | 0.92
ecoli-0123 | 0.74 | 0.82 | 0.88 | 0.80 | 0.82 | 0.92 | 0.88
ecoli-015 | 0.76 | 0.82 | 0.90 | 0.83 | 0.83 | 0.92 | 0.85
ecoli-0234 | 0.74 | 0.81 | 0.87 | 0.83 | 0.83 | 0.92 | 0.85
ecoli-0267 | 0.57 | 0.76 | 0.75 | 0.79 | 0.78 | 0.83 | 0.83
ecoli-0346 | 0.77 | 0.83 | 0.88 | 0.84 | 0.84 | 0.94 | 0.85
ecoli-0347 | 0.59 | 0.83 | 0.81 | 0.86 | 0.87 | 0.89 | 0.88
ecoli-0345 | 0.71 | 0.80 | 0.87 | 0.82 | 0.82 | 0.91 | 0.82
ecoli-0465 | 0.74 | 0.82 | 0.88 | 0.84 | 0.85 | 0.93 | 0.86
ecoli-0673 | 0.60 | 0.74 | 0.78 | 0.79 | 0.80 | 0.87 | 0.81
ecoli-0675 | 0.58 | 0.75 | 0.79 | 0.82 | 0.81 | 0.89 | 0.85
glass-0146 | 0.50 | 0.51 | 0.57 | 0.69 | 0.70 | 0.67 | 0.72
glass-015 | 0.50 | 0.50 | 0.54 | 0.66 | 0.66 | 0.68 | 0.70
glass-045 | 0.50 | 0.73 | 0.80 | 0.70 | 0.70 | 0.83 | 0.84
glass-065 | 0.50 | 0.67 | 0.73 | 0.66 | 0.66 | 0.76 | 0.76
led7digit | 0.50 | 0.59 | 0.63 | 0.85 | 0.85 | 0.88 | 0.88
yeast-0256 | 0.54 | 0.74 | 0.81 | 0.74 | 0.74 | 0.83 | 0.80
yeast-0257 | 0.69 | 0.86 | 0.92 | 0.86 | 0.85 | 0.92 | 0.89
yeast-0359 | 0.52 | 0.61 | 0.61 | 0.62 | 0.62 | 0.73 | 0.74
Average | 0.64 | 0.73 | 0.77 | 0.78 | 0.78 | 0.84 | 0.81
Table 3: Classification precision on the 60 imbalanced datasets. |  |  | Precision |  |  |  |
---|---|---|---|---|---|---|---
|  | Knn |  |  | SVM |  |
| Orig | SMOTE | SUGAR | Orig | SMOTE | SUGAR | RusBOOST
ecoli-013 | 0.49 | 0.66 | 0.67 | 0.61 | 0.62 | 0.61 | 0.57
ecoli-013 | 0.65 | 0.67 | 0.70 | 0.64 | 0.64 | 0.69 | 0.67
ecoli1 | 0.54 | 0.55 | 0.62 | 0.54 | 0.54 | 0.59 | 0.55
ecoli2 | 0.59 | 0.61 | 0.64 | 0.59 | 0.60 | 0.60 | 0.50
ecoli3 | 0.75 | 0.72 | 0.74 | 0.73 | 0.74 | 0.74 | 0.78
glass-0123 | 0.88 | 0.94 | 0.94 | 0.90 | 0.90 | 0.91 | 0.89
glass-0162 | 0.46 | 0.50 | 0.58 | 0.65 | 0.67 | 0.61 | 0.64
glass-0165 | 0.48 | 0.66 | 0.67 | 0.69 | 0.69 | 0.72 | 0.72
glass0 | 0.73 | 0.73 | 0.76 | 0.79 | 0.82 | 0.77 | 0.82
glass1 | 0.65 | 0.75 | 0.78 | 0.74 | 0.76 | 0.78 | 0.78
glass2 | 0.59 | 0.64 | 0.64 | 0.66 | 0.67 | 0.62 | 0.62
glass4 | 0.51 | 0.80 | 0.77 | 0.76 | 0.75 | 0.78 | 0.82
glass5 | 0.53 | 0.68 | 0.67 | 0.69 | 0.69 | 0.69 | 0.73
glass6 | 0.92 | 0.92 | 0.93 | 0.90 | 0.90 | 0.90 | 0.84
haberman | 0.56 | 0.59 | 0.61 | 0.60 | 0.57 | 0.66 | 0.58
new-thyroid1 | 0.90 | 0.91 | 0.93 | 0.97 | 0.98 | 0.95 | 0.92
new-thyroid2 | 0.90 | 0.95 | 0.98 | 0.96 | 0.96 | 0.95 | 0.93
pb-134 | 0.70 | 0.89 | 0.91 | 0.89 | 0.95 | 0.92 | 0.92
pb-0 | 0.87 | 0.87 | 0.89 | 0.84 | 0.84 | 0.89 | 0.91
pima | 0.63 | 0.62 | 0.65 | 0.72 | 0.71 | 0.73 | 0.70
segment0 | 0.94 | 0.96 | 0.97 | 0.99 | 1.00 | 0.99 | 0.99
shuttle-c24 | 0.70 | 0.70 | 0.70 | 0.69 | 0.70 | 0.70 | 0.48
vehicle0 | 0.85 | 0.89 | 0.89 | 0.93 | 0.95 | 0.93 | 0.93
vehicle1 | 0.56 | 0.57 | 0.61 | 0.68 | 0.69 | 0.84 | 0.67
vehicle2 | 0.76 | 0.82 | 0.83 | 0.95 | 0.94 | 0.95 | 0.92
vehicle3 | 0.57 | 0.56 | 0.61 | 0.68 | 0.69 | 0.84 | 0.68
vowel0 | 0.89 | 0.93 | 0.97 | 1.00 | 1.00 | 1.00 | 0.95
wisconsin | 0.94 | 0.96 | 0.95 | 0.95 | 0.96 | 0.96 | 0.95
yeast-0567 | 0.50 | 0.67 | 0.76 | 0.67 | 0.68 | 0.68 | 0.68
yeast-1289 | 0.48 | 0.49 | 0.68 | 0.54 | 0.53 | 0.60 | 0.54
yeast-1458 | 0.48 | 0.49 | 0.57 | 0.54 | 0.54 | 0.53 | 0.53
yeast-17 | 0.47 | 0.59 | 0.67 | 0.62 | 0.57 | 0.62 | 0.60
yeast-24 | 0.80 | 0.91 | 0.89 | 0.82 | 0.84 | 0.85 | 0.84
yeast-28 | 0.68 | 0.69 | 0.72 | 0.63 | 0.56 | 0.71 | 0.61
yeast1 | 0.63 | 0.64 | 0.67 | 0.68 | 0.68 | 0.69 | 0.70
yeast3 | 0.82 | 0.81 | 0.82 | 0.81 | 0.82 | 0.77 | 0.85
yeast4 | 0.64 | 0.66 | 0.66 | 0.63 | 0.62 | 0.60 | 0.60
yeast5 | 0.79 | 0.82 | 0.83 | 0.83 | 0.82 | 0.72 | 0.86
yeast6 | 0.66 | 0.68 | 0.72 | 0.65 | 0.64 | 0.61 | 0.60
ecoli-0145 | 0.83 | 0.87 | 0.86 | 0.89 | 0.86 | 0.83 | 0.77
ecoli-0-147 | 0.59 | 0.86 | 0.86 | 0.82 | 0.86 | 0.84 | 0.79
ecoli-01475 | 0.57 | 0.90 | 0.87 | 0.86 | 0.90 | 0.84 | 0.86
ecoli-0123 | 0.82 | 0.89 | 0.92 | 0.88 | 0.84 | 0.86 | 0.83
ecoli-015 | 0.83 | 0.88 | 0.89 | 0.89 | 0.88 | 0.85 | 0.83
ecoli-0234 | 0.80 | 0.88 | 0.87 | 0.89 | 0.87 | 0.87 | 0.82
ecoli-0267 | 0.61 | 0.81 | 0.80 | 0.84 | 0.84 | 0.80 | 0.81
ecoli-0346 | 0.87 | 0.88 | 0.88 | 0.90 | 0.88 | 0.86 | 0.81
ecoli-0347 | 0.61 | 0.89 | 0.88 | 0.89 | 0.89 | 0.84 | 0.84
ecoli-0345 | 0.78 | 0.83 | 0.86 | 0.87 | 0.86 | 0.86 | 0.80
ecoli-0465 | 0.83 | 0.86 | 0.86 | 0.88 | 0.87 | 0.88 | 0.82
ecoli-0673 | 0.63 | 0.85 | 0.84 | 0.84 | 0.84 | 0.85 | 0.82
ecoli-0675 | 0.64 | 0.84 | 0.83 | 0.82 | 0.82 | 0.82 | 0.86
glass-0146 | 0.46 | 0.51 | 0.60 | 0.64 | 0.67 | 0.59 | 0.61
glass-015 | 0.45 | 0.50 | 0.55 | 0.65 | 0.67 | 0.61 | 0.62
glass-045 | 0.48 | 0.73 | 0.79 | 0.70 | 0.70 | 0.80 | 0.82
glass-065 | 0.46 | 0.67 | 0.74 | 0.68 | 0.68 | 0.74 | 0.76
led7digit | 0.46 | 0.72 | 0.77 | 0.78 | 0.78 | 0.79 | 0.76
yeast-0256 | 0.70 | 0.88 | 0.88 | 0.71 | 0.68 | 0.75 | 0.71
yeast-0257 | 0.95 | 0.93 | 0.93 | 0.90 | 0.88 | 0.85 | 0.87
yeast-0359 | 0.53 | 0.71 | 0.71 | 0.59 | 0.59 | 0.64 | 0.61
Average | 0.67 | 0.76 | 0.78 | 0.77 | 0.77 | 0.77 | 0.75