A graph-based N-body approximation with application to stochastic neighbor embedding

Abstract

We propose a novel approximation technique, bubble approximation (BA), for repulsion forces in an N-body problem, where attraction has a limited range and repulsion acts between all points. These kinds of systems occur frequently in dimension reduction and graph drawing. Like tree codes, the established N-body approximation method, BA replaces several point-to-point computations by one area-to-point computation. Novelty of BA is to consider not only the magnitudes but also the directions of forces from the area. Therefore, its area-to-point approximations are applicable anywhere in the space. The joint effect of forces from inside the area is calculated analytically, assuming a homogeneous mass of points inside the area. These two features free BA from hierarchical data structures and complicated bookkeeping of interactions, which plague tree codes. Instead, BA uses a simple graph to control the computations. The graph provides a sparse matrix, which, suitably weighted, replaces the full matrix of pairwise comparisons in the N-body problem. As a concrete example, we implement a sparse-matrix version of stochastic neighbor embedding (a dimension reduction method), and demonstrate its good performance by comparisons to full-matrix method, and to three different approximate versions of the same method.

Introduction

Problems defined on a matrix of pairwise comparisons, so called N-body problems (Gray & Moore, 2001), are ubiquitous in machine learning. Solving them on large data sets is challenging, because memory requirements and running times scale quadratically with the number of data points $n$.

One commonly occurring N-body problem is to find coordinates $y_r$ and $y_c$ that minimize a force system

$$F=\sum _{r=1}^n(A_r-R_r)\text{,}$$$$A_r=\sum _{\left\{c\right|(r,c)\in \mathcal{L}\}}g\left(\Vert y_r-y_c\Vert \right)(y_r-y_c)\text{,}$$$$R_r=\sum _{c=1}^{n}f\left(\Vert y_r-y_c\Vert \right)(y_r-y_c)\text{.}$$

A point at coordinates $y_r$ experiences attractive forces $g$ from a limited set of points (collected in $\mathcal{L}$) and repulsive forces $f$ from all points. Typical examples occur in force systems of graph drawing methods (Eades, 1984, Fruchterman and Reingold, 1991, Hu, 2006, Noack, 2007, Quigley and Eades, 2001, Walshaw, 2001), where edges connect a node to a limited set of other nodes, and in gradients of cost functions in dimension reduction (Carreira-Perpiñán, 2010, Hinton and Roweis, 2003, Lee and Verleysen, 2009b, van der Maaten and Hinton, 2008, Yang et al., 2009), where the attractive forces outside of a local neighborhood are small enough to be ignored.

The set $\mathcal{L}$  of local relationships is small, so the attractive forces can be evaluated exactly. Straightforward evaluation of the repulsion term Eq. (3), on the contrary, would lead to quadratic scaling with $n$. We propose a novel type of approximation, bubble approximation (BA), for computing the repulsions. It is applicable in situations, where the overall computation is organized as in Eq. (1). In this work we derive formulas for the two-dimensional $y_r$. We demonstrate the practical usefulness of BA by showing how the cost function gradient of stochastic neighbor embedding (SNE) (Hinton and Roweis, 2003, van der Maaten and Hinton, 2008), a much-used nonlinear dimension reduction method, can be approximated with BA.

BA replaces several point-to-point computations by one area-to-point computation, as do tree codes (Appel, 1985, Barnes and Hut, 1986, Callahan and Kosaraju, 1995, Gray and Moore, 2003, Greengard and Rokhlin, 1987, Greengard and Strain, 1991, Yang et al., 2003), the established N-body approximation technique. Tree codes use hierarchical data structures to manage space: to determine, when an area is far enough (compared to its size) from a point to qualify for approximation, and to find the points $y_r$ to be replaced. BA considers not only the magnitudes but also the directions of forces from the area. Therefore, its area-to-point approximations are applicable for any areas, not only for those far away. The joint effect of forces from inside the area is calculated analytically, assuming homogeneous mass of points inside the area, so bookkeeping over individual points is not needed.

Because of these two features, BA does not need hierarchical division of space, but uses a simple graph to control its computations. The graph is turned into a sparse matrix, which replaces the full matrix of pairwise comparisons in the computations. Randomly picked global links (G-links) of the graph encode the area-to-point relationships. As global links represent forces from several points, they give rise to weighted entries. The graph is complemented by local links (L-links). They cover the local regions where the attractive forces are strong, and where exact point-to-point interactions are used.

Resembling divisions in local and global graph links have been used to improve quality of graph embeddings (Andersen, Chung, & Lu, 2007), as heuristics to reduce the amount of computation in dimension reduction (Chalmers, 1996, Parviainen, 2011), and to introduce long-range interactions to speed up convergence of image processing algorithms (Grady & Schwarz, 2004).

We start by introducing the general idea of BA in Section  2. The main contribution of the work is Section  3, where formulas for the bubble approximation are derived. In Section  4 we apply BA to build a large-scale dimension reduction method sparse t-SNE. Section  5 introduces some earlier approximations that serve as comparison methods. Experiments in Section  6 establish the good performance of sparse t-SNE in comparison to the original method, which uses exact computation, and to three earlier approximation methods. Some limitations and directions for future development of BA are discussed in Section  7.