We present ShapeVis, a scalable visualization technique for point cloud data
inspired from topological data analysis. Our method captures the underlying
geometric and topological structure of the data in a compressed graphical
representation. Much success has been reported by the data visualization
technique Mapper, that discreetly approximates the Reeb graph of a filter
function on the data. However, when using standard dimensionality reduction
algorithms as the filter function, Mapper suffers from considerable
computational cost. This makes it difficult to scale to high-dimensional data.
Our proposed technique relies on finding a subset of points called landmarks
along the data manifold to construct a weighted witness-graph over it. This
graph captures the structural characteristics of the point cloud, and its
weights are determined using a Finite Markov Chain. We further compress this
graph by applying induced maps from standard community detection algorithms.
Using techniques borrowed from manifold tearing, we prune and reinstate edges
in the induced graph based on their modularity to summarize the shape of data.
We empirically demonstrate how our technique captures the structural
characteristics of real and synthetic data sets. Further, we compare our
approach with Mapper using various filter functions like t-SNE, UMAP, LargeVis
and show that our algorithm scales to millions of data points while preserving
the quality of data visualization.

本文提出了一种基于拓扑数据分析的可扩展点云数据可视化技术 ——ShapeVis，通过构建数据流形上的加权见证图和从标准社区检测算法中引入的感应映射来压缩表示点云特征，并使用模块化方法剪枝和重建图形以总结数据的形状。与 Mapper 方法相比，我们的算法可以适用于成百万点数据的可视化展示。