Compressive Embedding and Visualization using Graphs

Johan Paratte, Nathanaël Perraudin, Pierre VandergheynstarXiv 2017 · arXiv

Authors: Johan Paratte, Nathanaël Perraudin, and Pierre Vandergheynst

Introduction

Visualizing high-dimensional data is a cornerstone of modern data science, yet it faces a significant "scalability wall." Popular algorithms such as t-SNE, Isomap, and Sammon mapping are computationally intensive, often scaling at $O(N^2)$ or $O(N \log N)$. As datasets expand into the millions of points, these methods become unmanageably slow or exceed memory limits.

In "Compressive Embedding and Visualization using Graphs," the authors present Compressive Embedding (CE), a framework designed to bypass this bottleneck. By combining Graph Signal Processing (GSP) with traditional dimensionality reduction, CE allows for the visualization of massive datasets by processing only a tiny fraction of the total points and propagating the results through a similarity graph.

The Scalability Challenge

The fundamental bottleneck in visualization is the similarity matrix. To determine a point's position in 2D or 3D space, an algorithm must calculate its relationship to other points. Computing these relationships for every pair creates an "intrinsic quadratic regime." The authors propose a shift in perspective: instead of computing a full embedding for the entire dataset, can we compute a high-quality embedding for a small "sketch" and use the underlying graph structure to infer the rest?

The Compressive Embedding (CE) Framework

The CE framework accelerates any existing visualization algorithm through a six-step pipeline:

  1. Graph Construction: An approximate k-nearest-neighbor (k-NN) graph is built for the entire dataset using fast libraries like FLANN or ANNOY. This graph serves as a structural prior.
  2. Sampling: A small subset of $M$ representative nodes is selected. Using GSP theory, the authors demonstrate that $O(\log N)$ samples are often sufficient to capture the data's energy.
  3. Sketching: High-dimensional features are extracted specifically for these $M$ nodes.
  4. Embedding: A standard visualization algorithm (e.g., t-SNE, LargeVis) is run on the small sketch to generate low-dimensional coordinates ($E_S$).
  5. Transductive Learning: The coordinates of the sampled points are treated as "labels."
  6. Diffusion: A diffusion operator, such as a low-pass graph filter, is applied to smooth and propagate these coordinates across the entire graph.

Technical Innovations

To ensure the quality of the final visualization, the authors introduced two key techniques:

  • Convex Hull Diffusion (CHD): Standard graph diffusion often causes points to collapse toward the origin. CHD constrains the diffused points to remain within the convex hull of the sampled points, preserving the visual spread and cluster separation.
  • GSP Theory Integration: The framework leverages Graph Signal Processing to determine the precise number of samples required to diffuse information across the graph without significant loss of structural energy.

Experimental Evaluation

The authors evaluated CE using synthetic datasets (dynamic point clouds) and the MNIST dataset (70,000 handwritten digits).

Quantitative Metrics

To move beyond subjective "visual inspection," the authors proposed two objective metrics:

  • Average Clusterability Index (ACI): Measures the degree of class separation.
  • Average Cluster Concentration (ACC): Measures the compactness of individual classes.

Key Results

  • Efficiency: On the MNIST dataset, the CE-accelerated version of t-SNE completed in 157 seconds, compared to 1,815 seconds for the standard implementation—a speedup of over 10x.
  • Sample Efficiency: Remarkably, for MNIST ($N=70,000$), a sketch of only 550 points (0.008% of the data) was sufficient to produce a recognizable, clustered visualization.
  • Memory Management: CE enabled the use of algorithms like Sammon Mapping on large datasets that would otherwise exceed 128 GB of RAM, as the heavy computation is restricted to the small sketch.

Limitations and Future Work

While CE offers massive scalability, there is a trade-off in visual refinement. The resulting embeddings can appear "noisier" or show more overlap than those generated by full-scale algorithms. Additionally, the diffusion step itself can become a bottleneck; in MNIST trials, diffusion accounted for the majority of the processing time (139 out of 161 seconds).

Future research may focus on "active sampling"—selecting sketch points based on graph topology rather than random adaptive sampling—to further enhance visualization quality while maintaining the framework's speed advantages.

Conclusion

Compressive Embedding provides a robust path forward for high-dimensional data exploration. By treating the similarity graph as a structural prior and utilizing graph diffusion, the framework allows researchers to scale sophisticated visualization techniques to millions of points with minimal loss in cluster integrity.

Summary updated

Abstract

Visualizing high-dimensional data has been a focus in data analysis communities for decades, which has led to the design of many algorithms, some of which are now considered references (such as t-SNE for example). In our era of overwhelming data volumes, the scalability of such methods have become more and more important. In this work, we present a method which allows to apply any visualization or embedding algorithm on very large datasets by considering only a fraction of the data as input and then extending the information to all data points using a graph encoding its global similarity. We show that in most cases, using only $\mathcal{O}(\log(N))$ samples is sufficient to diffuse the information to all $N$ data points. In addition, we propose quantitative methods to measure the quality of embeddings and demonstrate the validity of our technique on both synthetic and real-world datasets.
BibTeX
@misc{paratte2017compressive,
  author = {Johan Paratte and Nathanaël Perraudin and Pierre Vandergheynst},
  title = {{Compressive Embedding and Visualization using Graphs}},
  year = {2017},
  eprint = {1702.05815},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1702.05815},
}

Loading related content...

Figure