PaperlayerView exact revision on arXiv

Source-linked AI summary

Visualizing Large-scale and High-dimensional Data

Jian Tang, Jingzhou Liu, Ming Zhang, Qiaozhu Mei

arXiv:1602.00370v2cs.LGcs.HC

TL;DR

Large-scale, high-dimensional visualization is limited by the cost of constructing similarity structures and laying them out in low-dimensional space. LargeVis combines accurate approximate KNN construction with probabilistic graph visualization optimized by asynchronous stochastic gradient descent. Experiments report substantially better efficiency and effectiveness than t-SNE, with more stable parameters across data sets.

  • Problem

    Existing similarity-based visualization methods such as t-SNE face computational bottlenecks and parameter sensitivity on millions of points with hundreds of dimensions.

  • Method

    LargeVis constructs an accurately approximated K-nearest neighbor graph and lays it out using a probabilistic model optimized by asynchronous stochastic gradient descent.

  • Results

    LargeVis significantly outperforms t-SNE in graph construction and visualization efficiency, effectiveness, and visualization quality.

  • Takeaways & Limitations

    LargeVis scales to millions of high-dimensional data points, taking only a couple of hours on a single machine in the reported setting.

  • Takeaways & Limitations

    The experiments use fixed-dimensional representations for comparison, and the authors identify dynamically changing data as future work.

Abstract

from arXiv · show

We study the problem of visualizing large-scale and high-dimensional data in a low-dimensional (typically 2D or 3D) space. Much success has been reported recently by techniques that first compute a similarity structure of the data points and then project them into a low-dimensional space with the structure preserved. These two steps suffer from considerable computational costs, preventing the state-of-the-art methods such as the t-SNE from scaling to large-scale and high-dimensional data (e.g., millions of data points and hundreds of dimensions). We propose the LargeVis, a technique that first constructs an accurately approximated K-nearest neighbor graph from the data and then layouts the graph in the low-dimensional space. Comparing to t-SNE, LargeVis significantly reduces the computational cost of the graph construction step and employs a principled probabilistic model for the visualization step, the objective of which can be effectively optimized through asynchronous stochastic gradient descent with a linear time complexity. The whole procedure thus easily scales to millions of high-dimensional data points. Experimental results on real-world data sets demonstrate that the LargeVis outperforms the state-of-the-art methods in both efficiency and effectiveness. The hyper-parameters of LargeVis are also much more stable over different data sets.

1. INTRODUCTION

Large-scale, high-dimensional visualization requires preserving data similarity in low-dimensional layouts, but existing graph-based methods face computational and parameter-sensitivity limitations. LargeVis addresses these challenges with efficient approximate graph construction and probabilistic graph visualization designed to scale to millions of points.

  • Motivation: Large-scale visualization becomes computationally difficult because laying out millions of high-dimensional points and constructing their similarity structure are costly.Existing approaches also suffer from inefficient visualization at large sizes and sensitive parameters across data sets.
  • Existing Pipeline: Graph-based methods first construct a K-nearest neighbor graph and then project it into a 2D or 3D space while preserving similarity relationships.The intended layout keeps similar points close and dissimilar points far apart.
  • LargeVis: LargeVis efficiently computes layouts for millions of data points with hundreds of dimensions.Its contributions include an efficient approximate K-nearest neighbor graph algorithm and a probabilistic model for graph visualization.
  • LargeVis: LargeVis optimizes its graph-visualization objective with asynchronous stochastic gradient descent in O(N) time complexity.The model represents both observed links and unobserved negative links.
  • Evaluation: Experiments compare LargeVis and t-SNE quantitatively and visually on real-world data sets including text, images, and networks.The reported evaluation covers both graph construction and visualization performance.

2. RELATED WORK

Related work spans large-data visualization, approximate KNN construction, dimensionality reduction, network layouts, and graph embedding. These approaches often trade visualization quality or generality against computational scalability, motivating LargeVis.

  • Large-Data Visualization: Few existing techniques efficiently produce meaningful 2D layouts for millions of high-dimensional points without first aggregating or summarizing the data.Large-data visualizations commonly refine only a subset after users zoom in.
  • KNN Graph Construction: KNN graph construction methods include space-partitioning trees, locality-sensitive hashing, and neighbor-exploring techniques.Exact KNN computation has complexity O(N^2d), making approximation important for large, high-dimensional data.
  • KNN Graph Construction: Tree-based and NN-descent methods work efficiently at low dimensionality but deteriorate as dimensionality reaches hundreds.This limitation affects several established approximate-neighbor approaches.
  • Dimensionality Reduction: Nonlinear dimensionality-reduction methods generally outperform linear methods for extremely low-dimensional projections because high-dimensional data often lies near nonlinear manifolds.The related discussion notes limitations in preserving both local and global structure on real high-dimensional data.
  • Network Layouts: Force-directed network layouts can yield better visualizations but have computational complexities ranging from O(N^3) to O(N log^2 N), limiting further scaling.ForceAtlas2 and OpenOrd reduce complexity to O(N log N) but remain constrained for larger graphs.
  • Graph Embedding: LargeVis differs from LINE and Skipgram because those graph-embedding methods are not designed specifically for visualization.They can instead provide preprocessing representations before visualization.

3. LARGEVIS

LargeVis visualizes large-scale, high-dimensional data by constructing an approximate KNN graph and projecting it into a low-dimensional space. Its graph construction improves a less accurate random-projection-tree graph through neighbor exploring, while probabilistic graph modeling and asynchronous optimization support scalable layout.

  • LargeVis overview: LargeVis represents each high-dimensional point with a low-dimensional vector while preserving the data’s intrinsic structure.The target space is typically 2D or 3D.
  • 3.1 Efficient KNN Graph Construction: Exact KNN construction costs O(N^2d), motivating approximate graph construction for large high-dimensional data.The Euclidean distance is used, as in t-SNE.
  • 3.1 Efficient KNN Graph Construction: LargeVis builds random projection trees and improves the resulting approximate graph through neighbor exploring instead of building many trees.The method uses the idea that a neighbor of a neighbor is likely to be a neighbor.
  • 3.1 Efficient KNN Graph Construction: KNN edge weights use t-SNE’s conditional probabilities, with σ_i selected by perplexity and weights then symmetrized.The procedure calculates edge weights after constructing the approximate graph.
  • 3.2 A Probabilistic Model for Graph Visualization: The probabilistic visualization model preserves observed weighted edges while pushing unobserved pairs apart in the low-dimensional layout.Observed edges encourage similar data points to remain close, whereas negative edges encourage dissimilar points to separate.
  • Optimization: Negative sampling and weight-proportional edge sampling make the objective practical, while asynchronous stochastic gradient descent accelerates optimization on sparse graphs.Each stochastic gradient step costs O(sM), and the overall optimization costs O(sMN), linear in N.

4. EXPERIMENTS

The experiments evaluate LargeVis quantitatively and qualitatively, separately measuring its KNN graph construction and graph visualization algorithms.

  • Experimental evaluation: LargeVis is evaluated quantitatively and qualitatively for both KNN graph construction and graph visualization.The two algorithmic components are assessed separately.

4.1 Data Sets

The experiments use diverse large-scale data sets spanning text, images, and networks, with standardized representations and 2D layouts for comparison. Figure 2 evaluates KNN construction by running time and accuracy.

  • Data sets: The evaluation covers text, image, and network data sets, including 20NG, MNIST, WikiWord, WikiDoc, CSAuthor, DBLPPaper, and LiveJournal.The data points represent articles, images, words, authors, papers, or network nodes depending on the data set.
  • Data preparation: The data sets use fixed-dimensional representations for comparison, although this preprocessing is not required by LargeVis.The paper notes that intermediate representations can smooth the original similarity structure.
  • Experimental setup: All visualization experiments learn a 2D layout on a machine with 512GB memory and 32 cores.When multiple threads are used, the experiments use 32 threads.
  • KNN graph construction: Figure 2 compares KNN graph-construction running time against accuracy, with the lower-right region representing optimal performance.The figure compares LargeVis with vantage-point trees and other state-of-the-art methods.

4.2 Results on KNN Graph Construction

The evaluation compares KNN graph construction methods and shows that LargeVis combines random projection trees with neighbor exploration to achieve accurate graphs efficiently. Its accuracy improves rapidly with only a few exploration iterations, enabling scaling to millions of high-dimensional points.

  • LargeVis improves random projection trees with neighbor exploration for approximate KNN graph construction.
  • 25 minutes at 95% accuracy on WikiDoc versus 16 hours for vantage-point trees, a 37× speed difference.WikiDoc contains around 3 million data points; LargeVis uses one neighbor-exploration iteration in this comparison.
  • LargeVis consistently achieves the best running-time-versus-accuracy performance across all four evaluated data sets.The comparison uses curves of running time over KNN accuracy, with each point having 150 neighbors.
  • On WikiDoc, one neighbor-exploration iteration raises approximate-KNN accuracy from 0.4 to almost 1.
  • On LiveJournal, at most three iterations achieve very high accuracy even when initialization starts from a very inaccurate KNN graph.Similar behavior is reported for other data sets.
  • The resulting KNN graph construction algorithm scales to millions of data points with hundreds of dimensions, addressing a visualization bottleneck.

4.3 Graph Visualization

LargeVis uses a probabilistic graph-visualization model and is evaluated against SNE, t-SNE, and LINE under shared graph inputs and quantitative classification and runtime tests. It remains effective across data sets while requiring less tuning and less time on large data.

  • 4.3.1 Comparing Different Probabilistic Functions: The long-tailed function f(x) = 1/(1+x^2) achieves the best result among the tested probabilistic functions.The function is used in subsequent experiments and is described as addressing the crowding problem.
  • 4.3.2 Results on Different Data Sets: On million-point data sets, LargeVis is more effective or comparable to t-SNE with optimal learning rates and significantly outperforms t-SNE at its default rate.On smaller data sets, t-SNE’s default learning rate is comparable to LargeVis.
  • 4.3.2 Results on Different Data Sets: t-SNE’s optimal learning rates range from around 200 on 20NG and MNIST to 3000 on WikiDoc and LiveJournal, whereas LargeVis uses a stable default.The optimal t-SNE values vary significantly across data sets and require repeated training to tune.
  • 4.3.2 Results on Different Data Sets: 6.6 times faster on LiveJournal, where the data set contains 4 million points, LargeVis outpaces t-SNE in graph-visualization runtime.The two methods have comparable runtime on the smaller 20NG and MNIST data sets.
  • 4.3.2 Results on Different Data Sets: As data size increases, LargeVis’s default-rate performance improves while t-SNE’s decreases; exhaustively tuned t-SNE remains comparable to LargeVis.
  • With at least five negative samples, LargeVis performance becomes very stable, so only a few negative edges need to be sampled per data point.

4.4 Visualization Examples

The visualization examples compare LargeVis and t-SNE qualitatively across small and very large data sets, using category or high-dimensional K-means cluster colors. LargeVis is comparable on the smallest data and more intuitive on large data.

  • The examples use category colors for 20NG and K-means clusters from high-dimensional representations for WikiWord, WikiDoc, CSAuthors, and LiveJournal.The four clustered data sets use 200 clusters each.
  • On the smallest data set, 20NG, LargeVis and t-SNE produce meaningful visualizations that are comparable to each other.
  • On WikiDoc and LiveJournal, which contain at least 2.8 million points, LargeVis visualizations look much more intuitive than t-SNE’s.
  • A DBLP visualization illustrates conference-colored structure, including WWW’s connection to its companion volume and nearby information-retrieval conferences.The example identifies ICWSM north of WWW and SIGIR and ECIR to the west.

5. CONCLUSION

LargeVis lays out large-scale and high-dimensional data in low-dimensional spaces, with real-world experiments showing advantages over t-SNE. The paper identifies advanced visualizations and dynamically changing data as future directions.

  • LargeVis visualizations of WikiWord and CSAuthor use colors for clusters learned by K-means from high-dimensional representations.
  • LargeVis visualizes DBLP papers with colors corresponding to conferences.
  • LargeVis lays out large-scale and high-dimensional data in 2D or 3D spaces.
  • Experiments on real-world data sets show that LargeVis significantly outperforms t-SNE in graph construction and visualization.
  • The authors plan to use LargeVis layouts for advanced visualizations and to handle data changing dynamically over time.
Loading 1602.00370v2…