% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/uwot.R
\name{similarity_graph}
\alias{similarity_graph}
\title{Similarity Graph}
\usage{
similarity_graph(
  X = NULL,
  n_neighbors = NULL,
  metric = "euclidean",
  scale = NULL,
  set_op_mix_ratio = 1,
  local_connectivity = 1,
  nn_method = NULL,
  n_trees = 50,
  search_k = 2 * n_neighbors * n_trees,
  perplexity = 50,
  method = "umap",
  y = NULL,
  target_n_neighbors = n_neighbors,
  target_metric = "euclidean",
  target_weight = 0.5,
  pca = NULL,
  pca_center = TRUE,
  ret_extra = c(),
  n_threads = NULL,
  grain_size = 1,
  kernel = "gauss",
  tmpdir = tempdir(),
  verbose = getOption("verbose", TRUE),
  pca_method = NULL,
  binary_edge_weights = FALSE,
  nn_args = list()
)
}
\arguments{
\item{X}{Input data. Can be a \code{\link{data.frame}}, \code{\link{matrix}},
\code{\link[stats]{dist}} object or \code{\link[Matrix]{sparseMatrix}}.
Matrix and data frames should contain one observation per row. Data frames
will have any non-numeric columns removed, although factor columns will be
used if explicitly included via \code{metric} (see the help for
\code{metric} for details). A sparse matrix is interpreted as a distance
matrix, and is assumed to be symmetric, so you can also pass in an
explicitly upper or lower triangular sparse matrix to save storage. There
must be at least \code{n_neighbors} non-zero distances for each row. Both
implicit and explicit zero entries are ignored. Set zero distances you want
to keep to an arbitrarily small non-zero value (e.g. \code{1e-10}).
\code{X} can also be \code{NULL} if pre-computed nearest neighbor data is
passed to \code{nn_method}.}

\item{n_neighbors}{The size of local neighborhood (in terms of number of
neighboring sample points) used for manifold approximation. Larger values
result in more global views of the manifold, while smaller values result in
more local data being preserved. In general values should be in the range
\code{2} to \code{100}.}

\item{metric}{Type of distance metric to use to find nearest neighbors. For
 \code{nn_method = "annoy"} this can be one of:
\itemize{
  \item \code{"euclidean"} (the default)
  \item \code{"cosine"}
  \item \code{"manhattan"}
  \item \code{"hamming"}
  \item \code{"correlation"} (a distance based on the Pearson correlation)
  \item \code{"categorical"} (see below)
}
For \code{nn_method = "hnsw"} this can be one of:
\itemize{
  \item \code{"euclidean"}
  \item \code{"cosine"}
  \item \code{"correlation"}
}
If \href{https://cran.r-project.org/package=rnndescent}{rnndescent} is
installed and \code{nn_method = "nndescent"} is specified then many more
metrics are avaiable, including:
\itemize{
\item \code{"braycurtis"}
\item \code{"canberra"}
\item \code{"chebyshev"}
\item \code{"dice"}
\item \code{"hamming"}
\item \code{"hellinger"}
\item \code{"jaccard"}
\item \code{"jensenshannon"}
\item \code{"kulsinski"}
\item \code{"rogerstanimoto"}
\item \code{"russellrao"}
\item \code{"sokalmichener"}
\item \code{"sokalsneath"}
\item \code{"spearmanr"}
\item \code{"symmetrickl"}
\item \code{"tsss"}
\item \code{"yule"}
}
For more details see the package documentation of \code{rnndescent}.
For \code{nn_method = "fnn"}, the distance metric is always "euclidean".

If \code{X} is a data frame or matrix, then multiple metrics can be
specified, by passing a list to this argument, where the name of each item in
the list is one of the metric names above. The value of each list item should
be a vector giving the names or integer ids of the columns to be included in
a calculation, e.g. \code{metric = list(euclidean = 1:4, manhattan = 5:10)}.

Each metric calculation results in a separate fuzzy simplicial set, which are
intersected together to produce the final set. Metric names can be repeated.
Because non-numeric columns are removed from the data frame, it is safer to
use column names than integer ids.

Factor columns can also be used by specifying the metric name
\code{"categorical"}. Factor columns are treated different from numeric
columns and although multiple factor columns can be specified in a vector,
each factor column specified is processed individually. If you specify
a non-factor column, it will be coerced to a factor.

For a given data block, you may override the \code{pca} and \code{pca_center}
arguments for that block, by providing a list with one unnamed item
containing the column names or ids, and then any of the \code{pca} or
\code{pca_center} overrides as named items, e.g. \code{metric =
list(euclidean = 1:4, manhattan = list(5:10, pca_center = FALSE))}. This
exists to allow mixed binary and real-valued data to be included and to have
PCA applied to both, but with centering applied only to the real-valued data
(it is typical not to apply centering to binary data before PCA is applied).}

\item{scale}{Scaling to apply to \code{X} if it is a data frame or matrix:
\itemize{
  \item{\code{"none"} or \code{FALSE} or \code{NULL}} No scaling.
  \item{\code{"Z"} or \code{"scale"} or \code{TRUE}} Scale each column to
  zero mean and variance 1.
  \item{\code{"maxabs"}} Center each column to mean 0, then divide each
  element by the maximum absolute value over the entire matrix.
  \item{\code{"range"}} Range scale the entire matrix, so the smallest
  element is 0 and the largest is 1.
  \item{\code{"colrange"}} Scale each column in the range (0,1).
}
For \code{method} \code{"umap"}, the default is \code{"none"}. For
\code{"largevis"}, the default is \code{"maxabs"}.}

\item{set_op_mix_ratio}{Interpolate between (fuzzy) union and intersection as
the set operation used to combine local fuzzy simplicial sets to obtain a
global fuzzy simplicial sets. Both fuzzy set operations use the product
t-norm. The value of this parameter should be between \code{0.0} and
\code{1.0}; a value of \code{1.0} will use a pure fuzzy union, while
\code{0.0} will use a pure fuzzy intersection. Ignored if
\code{method = "largevis"}}

\item{local_connectivity}{The local connectivity required -- i.e. the number
of nearest neighbors that should be assumed to be connected at a local
level. The higher this value the more connected the manifold becomes
locally. In practice this should be not more than the local intrinsic
dimension of the manifold. Ignored if \code{method = "largevis"}.}

\item{nn_method}{Method for finding nearest neighbors. Options are:
\itemize{
  \item \code{"fnn"}. Use exact nearest neighbors via the
    \href{https://cran.r-project.org/package=FNN}{FNN} package.
  \item \code{"annoy"} Use approximate nearest neighbors via the
    \href{https://cran.r-project.org/package=RcppAnnoy}{RcppAnnoy} package.
  \item \code{"hnsw"} Use approximate nearest neighbors with the
    Hierarchical Navigable Small World (HNSW) method (Malkov and Yashunin,
    2018) via the
    \href{https://cran.r-project.org/package=RcppHNSW}{RcppHNSW} package.
    \code{RcppHNSW} is not a dependency of this package: this option is
    only available if you have installed \code{RcppHNSW} yourself. Also,
    HNSW only supports the following arguments for \code{metric} and
    \code{target_metric}: \code{"euclidean"}, \code{"cosine"} and
    \code{"correlation"}.
  \item \code{"nndescent"} Use approximate nearest neighbors with the
    Nearest Neighbor Descent method (Dong et al., 2011) via the
    \href{https://cran.r-project.org/package=rnndescent}{rnndescent}
    package. \code{rnndescent} is not a dependency of this package: this
    option is only available if you have installed \code{rnndescent}
    yourself.
 }
By default, if \code{X} has less than 4,096 vertices, the exact nearest
neighbors are found. Otherwise, approximate nearest neighbors are used.
You may also pass pre-calculated nearest neighbor data to this argument. It
must be one of two formats, either a list consisting of two elements:
\itemize{
  \item \code{"idx"}. A \code{n_vertices x n_neighbors} matrix
  containing the integer indexes of the nearest neighbors in \code{X}. Each
  vertex is considered to be its own nearest neighbor, i.e.
  \code{idx[, 1] == 1:n_vertices}.
  \item \code{"dist"}. A \code{n_vertices x n_neighbors} matrix
  containing the distances of the nearest neighbors.
}
or a sparse distance matrix of type \code{dgCMatrix}, with dimensions
\code{n_vertices x n_vertices}. Distances should be arranged by column,
i.e. a non-zero entry in row \code{j} of the \code{i}th column indicates
that the \code{j}th observation in \code{X} is a nearest neighbor of the
\code{i}th observation with the distance given by the value of that
element.
The \code{n_neighbors} parameter is ignored when using precomputed
nearest neighbor data. If using the sparse distance matrix input, each
column can contain a different number of neighbors.}

\item{n_trees}{Number of trees to build when constructing the nearest
neighbor index. The more trees specified, the larger the index, but the
better the results. With \code{search_k}, determines the accuracy of the
Annoy nearest neighbor search. Only used if the \code{nn_method} is
\code{"annoy"}. Sensible values are between \code{10} to \code{100}.}

\item{search_k}{Number of nodes to search during the neighbor retrieval. The
larger k, the more the accurate results, but the longer the search takes.
With \code{n_trees}, determines the accuracy of the Annoy nearest neighbor
search. Only used if the \code{nn_method} is \code{"annoy"}.}

\item{perplexity}{Used only if \code{method = "largevis"}. Controls the size
of the local neighborhood used for manifold approximation. Should be a
value between 1 and one less than the number of items in \code{X}. If
specified, you should \emph{not} specify a value for \code{n_neighbors}
unless you know what you are doing.}

\item{method}{How to generate the similarities between items. One of:
\itemize{
  \item \code{"umap"} The UMAP method of McInnes et al. (2018).
  \item \code{"largevis"} The LargeVis method of Tang et al. (2016).
}}

\item{y}{Optional target data to add supervised or semi-supervised weighting
  to the similarity graph . Can be a vector, matrix or data frame. Use the
  \code{target_metric} parameter to specify the metrics to use, using the
  same syntax as \code{metric}. Usually either a single numeric or factor
  column is used, but more complex formats are possible. The following types
  are allowed:
  \itemize{
    \item Factor columns with the same length as \code{X}. \code{NA} is
    allowed for any observation with an unknown level, in which case
    UMAP operates as a form of semi-supervised learning. Each column is
    treated separately.
    \item Numeric data. \code{NA} is \emph{not} allowed in this case. Use the
    parameter \code{target_n_neighbors} to set the number of neighbors used
    with \code{y}. If unset, \code{n_neighbors} is used. Unlike factors,
    numeric columns are grouped into one block unless \code{target_metric}
    specifies otherwise. For example, if you wish columns \code{a} and
    \code{b} to be treated separately, specify
    \code{target_metric = list(euclidean = "a", euclidean = "b")}. Otherwise,
    the data will be effectively treated as a matrix with two columns.
    \item Nearest neighbor data, consisting of a list of two matrices,
    \code{idx} and \code{dist}. These represent the precalculated nearest
    neighbor indices and distances, respectively. This
    is the same format as that expected for precalculated data in
    \code{nn_method}. This format assumes that the underlying data was a
    numeric vector. Any user-supplied value of the \code{target_n_neighbors}
    parameter is ignored in this case, because the the number of columns in
    the matrices is used for the value. Multiple nearest neighbor data using
    different metrics can be supplied by passing a list of these lists.
  }
Unlike \code{X}, all factor columns included in \code{y} are automatically
used. This parameter is ignored if \code{method = "largevis"}.}

\item{target_n_neighbors}{Number of nearest neighbors to use to construct the
target simplicial set. Default value is \code{n_neighbors}. Applies only if
\code{y} is non-\code{NULL} and \code{numeric}.  This parameter is ignored
if \code{method = "largevis"}.}

\item{target_metric}{The metric used to measure distance for \code{y} if
using supervised dimension reduction. Used only if \code{y} is numeric.
This parameter is ignored if \code{method = "largevis"}.}

\item{target_weight}{Weighting factor between data topology and target
topology. A value of 0.0 weights entirely on data, a value of 1.0 weights
entirely on target. The default of 0.5 balances the weighting equally
between data and target. Only applies if \code{y} is non-\code{NULL}. This
parameter is ignored if \code{method = "largevis"}.}

\item{pca}{If set to a positive integer value, reduce data to this number of
columns using PCA. Doesn't applied if the distance \code{metric} is
\code{"hamming"}, or the dimensions of the data is larger than the
number specified (i.e. number of rows and columns must be larger than the
value of this parameter). If you have > 100 columns in a data frame or
matrix, reducing the number of columns in this way may substantially
increase the performance of the nearest neighbor search at the cost of a
potential decrease in accuracy. In many t-SNE applications, a value of 50
is recommended, although there's no guarantee that this is appropriate for
all settings.}

\item{pca_center}{If \code{TRUE}, center the columns of \code{X} before
carrying out PCA. For binary data, it's recommended to set this to
\code{FALSE}.}

\item{ret_extra}{A vector indicating what extra data to return. May contain
any combination of the following strings:
\itemize{
 \item \code{"nn"} nearest neighbor data that can be used as input to
    \code{nn_method} to avoid the overhead of repeatedly calculating the
    nearest neighbors when manipulating unrelated parameters. See the
    "Value" section for the names of the list items. Note that the nearest
    neighbors could be sensitive to data scaling, so be wary of reusing
    nearest neighbor data if modifying the \code{scale} parameter.
 \item \code{"sigma"} the normalization value for each observation in the
    dataset when constructing the smoothed distances to each of its
    neighbors. This gives some sense of the local density of each
    observation in the high dimensional space: higher values of
    \code{sigma} indicate a higher dispersion or lower density.
}}

\item{n_threads}{Number of threads to use. Default is half the number of
concurrent threads supported by the system. For nearest neighbor search,
only applies if \code{nn_method = "annoy"}. If \code{n_threads > 1}, then
the Annoy index will be temporarily written to disk in the location
determined by \code{\link[base]{tempfile}}.}

\item{grain_size}{The minimum amount of work to do on each thread. If this
value is set high enough, then less than \code{n_threads} will be used for
processing, which might give a performance improvement if the overhead of
thread management and context switching was outweighing the improvement due
to concurrent processing. This should be left at default (\code{1}) and
work will be spread evenly over all the threads specified.}

\item{kernel}{Used only if \code{method = "largevis"}. Type of kernel
function to create input similiarties. Can be one of \code{"gauss"} (the
default) or \code{"knn"}. \code{"gauss"} uses the usual Gaussian weighted
similarities. \code{"knn"} assigns equal similiarties. to every edge in the
nearest neighbor graph, and zero otherwise, using \code{perplexity} nearest
neighbors. The \code{n_neighbors} parameter is ignored in this case.}

\item{tmpdir}{Temporary directory to store nearest neighbor indexes during
nearest neighbor search. Default is \code{\link{tempdir}}. The index is
only written to disk if \code{n_threads > 1} and
\code{nn_method = "annoy"}; otherwise, this parameter is ignored.}

\item{verbose}{If \code{TRUE}, log details to the console.}

\item{pca_method}{Method to carry out any PCA dimensionality reduction when
the \code{pca} parameter is specified. Allowed values are:
\itemize{
  \item{\code{"irlba"}}. Uses \code{\link[irlba]{prcomp_irlba}} from the
  \href{https://cran.r-project.org/package=irlba}{irlba} package.
  \item{\code{"rsvd"}}. Uses 5 iterations of \code{\link[irlba]{svdr}} from
  the \href{https://cran.r-project.org/package=irlba}{irlba} package.
  This is likely to give much faster but potentially less accurate results
  than using \code{"irlba"}. For the purposes of nearest neighbor
  calculation and coordinates initialization, any loss of accuracy doesn't
  seem to matter much.
  \item{\code{"bigstatsr"}}. Uses \code{\link[bigstatsr]{big_randomSVD}}
  from the \href{https://cran.r-project.org/package=bigstatsr}{bigstatsr}
  package. The SVD methods used in \code{bigstatsr} may be faster on
  systems without access to efficient linear algebra libraries (e.g.
  Windows). \strong{Note}: \code{bigstatsr} is \emph{not} a dependency of
  uwot: if you choose to use this package for PCA, you \emph{must} install
  it yourself.
  \item{\code{"svd"}}. Uses \code{\link[base]{svd}} for the SVD. This is
  likely to be slow for all but the smallest datasets.
  \item{\code{"auto"}} (the default). Uses \code{"irlba"}, unless more than
  50% of the full set of singular vectors would be calculated, in which
  case \code{"svd"} is used.
}}

\item{binary_edge_weights}{If \code{TRUE} then edge weights of the returned
graph are binary (0/1) rather than reflecting the degree of similarity.}

\item{nn_args}{A list containing additional arguments to pass to the nearest
neighbor method. For \code{nn_method = "annoy"}, you can specify
\code{"n_trees"} and \code{"search_k"}, and these will override the
\code{n_trees} and \code{search_k} parameters.
For \code{nn_method = "hnsw"}, you may specify the following arguments:
\itemize{
\item \code{M} The maximum number of neighbors to keep for each vertex.
Reasonable values are \code{2} to \code{100}. Higher values give better
recall at the cost of more memory. Default value is \code{16}.
\item \code{ef_construction} A positive integer specifying the size of
the dynamic list used during index construction. A higher value will
provide better results at the cost of a longer time to build the index.
Default is \code{200}.
\item \code{ef} A positive integer specifying the size of the dynamic
list used during search. This cannot be smaller than \code{n_neighbors}
and cannot be higher than the number of items in the index. Default is
\code{10}.
}
For \code{nn_method = "nndescent"}, you may specify the following
arguments:
\itemize{
\item \code{n_trees} The number of trees to use in a random projection
forest to initialize the search. A larger number will give more accurate
results at the cost of a longer computation time. The default of
\code{NULL} means that the number is chosen based on the number of
observations in \code{X}.
\item \code{max_candidates} The number of potential neighbors to explore
per iteration. By default, this is set to \code{n_neighbors} or \code{60},
whichever is smaller. A larger number will give more accurate results at
the cost of a longer computation time.
\item \code{n_iters} The number of iterations to run the search. A larger
number will give more accurate results at the cost of a longer computation
time. By default, this will be chosen based on the number of observations
in \code{X}. You may also need to modify the convergence criterion
\code{delta}.
\item \code{delta} The minimum relative change in the neighbor graph
allowed before early stopping. Should be a value between 0 and 1. The
smaller the value, the smaller the amount of progress between iterations is
allowed. Default value of \code{0.001} means that at least 0.1% of the
neighbor graph must be updated at each iteration.
\item \code{init} How to initialize the nearest neighbor descent. By
default this is set to \code{"tree"} and uses a random project forest.
If you set this to \code{"rand"}, then a random selection is used. Usually
this is less accurate than using RP trees, but for high-dimensional cases,
there may be little difference in the quality of the initialization and
random initialization will be a lot faster. If you set this to
\code{"rand"}, then the \code{n_trees} parameter is ignored.
\item \code{pruning_degree_multiplier} The maximum number of edges per node
to retain in the search graph, relative to \code{n_neighbors}. A larger
value will give more accurate results at the cost of a longer computation
time. Default is \code{1.5}. This parameter only affects neighbor search
when transforming new data with \code{\link{umap_transform}}.
\item \code{epsilon} Controls the degree of the back-tracking when
traversing the search graph. Setting this to \code{0.0} will do a greedy
search with no back-tracking. A larger value will give more accurate
results at the cost of a longer computation time. Default is \code{0.1}.
This parameter only affects neighbor search when transforming new data with
\code{\link{umap_transform}}.
\item \code{max_search_fraction} Specifies the maximum fraction of the
search graph to traverse. By default, this is set to \code{1.0}, so the
entire graph (i.e. all items in \code{X}) may be visited. You may want to
set this to a smaller value if you have a very large dataset (in
conjunction with \code{epsilon}) to avoid an inefficient exhaustive search
of the data in \code{X}. This parameter only affects neighbor search when
transforming new data with \code{\link{umap_transform}}.
}}
}
\value{
A sparse symmetrized matrix of the similarities between the items in
  \code{X} or if \code{nn_method} contains pre-computed nearest neighbor
  data, the items in \code{nn_method}. Because of the symmetrization, there
  may be more non-zero items in each column than the specified value of
  \code{n_neighbors} (or pre-computed neighbors in \code{nn_method}).
  If \code{ret_extra} is specified then the return value will be a list
  containing:
  \itemize{
    \item \code{similarity_graph} the similarity graph as a sparse matrix
    as described above.
    \item \code{nn} (if \code{ret_extra} contained \code{"nn"}) the nearest
    neighbor data as a list called \code{nn}. This contains one list for each
    \code{metric} calculated, itself containing a matrix \code{idx} with the
    integer ids of the neighbors; and a matrix \code{dist} with the
    distances. The \code{nn} list (or a sub-list) can be used as input to the
    \code{nn_method} parameter.
    \item \code{sigma} (if \code{ret_extra} contains \code{"sigma"}),
    a vector of calibrated parameters, one for each item in the input data,
    reflecting the local data density for that item. The exact definition of
    the values depends on the choice of the \code{method} parameter.
    \item \code{rho} (if \code{ret_extra} contains \code{"sigma"}), a
    vector containing the largest distance to the locally connected neighbors
    of each item in the input data. This will exist only if
    \code{method = "umap"}.
    \item \code{localr} (if \code{ret_extra} contains \code{"localr"}) a
    vector of the estimated local radii, the sum of \code{"sigma"} and
    \code{"rho"}. This will exist only if \code{method = "umap"}.
  }
}
\description{
Create a graph (as a sparse symmetric weighted adjacency matrix) representing
the similarities between items in a data set. No dimensionality reduction is
carried out. By default, the similarities are calculated using the merged
fuzzy simplicial set approach in the Uniform Manifold Approximation and
Projection (UMAP) method (McInnes et al., 2018), but the approach from
LargeVis (Tang et al., 2016) can also be used.
}
\details{
This is equivalent to running \code{\link{umap}} with the
\code{ret_extra = c("fgraph")} parameter, but without the overhead of
calculating (or returning) the optimized low-dimensional coordinates.
}
\examples{

iris30 <- iris[c(1:10, 51:60, 101:110), ]

# return a 30 x 30 sparse matrix with similarity data based on 10 nearest
# neighbors per item
iris30_sim_graph <- similarity_graph(iris30, n_neighbors = 10)

# Default is to use the UMAP method of calculating similarities, but LargeVis
# is also available: for that method, use perplexity instead of n_neighbors
# to control neighborhood size. Use ret_extra = "nn" to return nearest
# neighbor data as well as the similarity graph. Return value is a list
# containing similarity_graph' and 'nn' items.
iris30_lv_graph <- similarity_graph(iris30,
  perplexity = 10,
  method = "largevis", ret_extra = "nn"
)
# If you have the neighbor information you don't need the original data
iris30_lv_graph_nn <- similarity_graph(
  nn_method = iris30_lv_graph$nn,
  perplexity = 10, method = "largevis"
)
all(iris30_lv_graph_nn == iris30_lv_graph$similarity_graph)

}
\references{
Dong, W., Moses, C., & Li, K. (2011, March).
Efficient k-nearest neighbor graph construction for generic similarity measures.
In \emph{Proceedings of the 20th international conference on World Wide Web}
(pp. 577-586).
ACM.
\doi{10.1145/1963405.1963487}.

Malkov, Y. A., & Yashunin, D. A. (2018).
Efficient and robust approximate nearest neighbor search using hierarchical
navigable small world graphs.
\emph{IEEE transactions on pattern analysis and machine intelligence}, \emph{42}(4), 824-836.

McInnes, L., Healy, J., & Melville, J. (2018).
UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction
\emph{arXiv preprint} \emph{arXiv}:1802.03426.
\url{https://arxiv.org/abs/1802.03426}

Tang, J., Liu, J., Zhang, M., & Mei, Q. (2016, April).
Visualizing large-scale and high-dimensional data.
In \emph{Proceedings of the 25th International Conference on World Wide Web}
(pp. 287-297).
International World Wide Web Conferences Steering Committee.
\url{https://arxiv.org/abs/1602.00370}
}
