{'fraction_non_alphanumeric': 0.030426405903522483, 'fraction_numerical': 0.009596859209713185, 'mean_word_length': 4.701554404145078, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
ShapeVis: High-dimensional Data Visualization at Scale

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.


INTRODUCTION
With ever-increasing amounts of data and advances in hardware to store and query such datasets, it has become critical to have scalable and robust systems for analyzing big data. Understanding and mining insights from the massive amount of data has made a significant impact in fields like marketing, business, education and healthcare. However, we continue to lack the tools and techniques to produce insight-generating visualizations of large-scale and highdimensional data. Traditional visualization approaches like scatter plots and heat-maps have been proven to be effective only for small or intermediate sizes of data. These techniques are extremely intuitive and can be used to determine the bivariate relationships between variables. However, they require laying out the data points on a lower-dimensional space which is computationally intractable when data is large-scale and high-dimensional. Moreover, in some cases, these visualizations can lead to inconclusive results. * authors contributed equally Dimensionality reduction is the transformation of highdimensional data into a low dimensional representation while preserving some desirable structure of data. It is a core problem in machine learning and data mining since, generally, real-world data is found to lie on a low-dimensional manifold embedded in highdimensional space [2]. Of late, the usage of dimensionality reduction for visualization of high-dimensional data has become common practice following the success of techniques such as PCA [50], MDS [23] t-SNE [31], tsNET [22], and UMAP [32]. These techniques are being applied in a wide range of fields and on ever-increasing sizes of datasets. Broadly, dimension reduction algorithms tend to fall into two categories. Algorithms such as PCA [50] and MDS [23] seek to preserve the distance structure within the data whereas algorithms like t-SNE [31], Isomap [38], LargeVis [44], UMAP [32] and Laplacian Eigenmaps [1] favor the preservation of local distances over global distance.
The class of techniques known as Stochastic Neighbor Embedding (SNE) [20] are considered the current state-of-the-art in dimension reduction for visualization. Intuitively, SNE [20] techniques encode local relationships in the original and embedding spaces as probability distributions. Then it minimizes the loss of information between the two distributions with respect to the locations of points in the map. SNE-based approaches have revealed many interesting structures in real-world and synthetic data [39].
However, there are issues with dimensionality reduction methods. Since these methods compress a large number of attributes down to a few, they suffer from projection losses. As a result, points well separated in high-dimensional space might appear to be in the same neighborhood in the lower-dimensional projection. In particular, due to local neighborhood preservation SNE techniques might miss structures at different sizes. Though SNE is fairly robust to changes in perplexity [31], multiple plots with different perplexities are typically needed to arrive at a conclusively useful embedding [49]. They are also known to not always produce similar output on successive runs making them hard to use. Moreover, application of SNE techniques to large datasets is problematic, as the computational complexity is usually O(n 2 ) [31]. Using approximations it can be reduced to O(n log(n)) [48]. Even when appropriately projected onto lower-dimensional spaces, interpreting and extracting insights can be cumbersome when there are too many data points or when the data is high-dimensional. This is largely because 2D and 3D representations do not provide any obvious means to explore and understand critical patterns and global relationships in the data.
Visualization approaches that make use of abstractions and concise representations are, therefore, essential in capturing and interpreting structural information in high-dimensional data. In this paper, we propose ShapeVis, that tries to address this issue by computing a compressed representation of large-scale and highdimensional data in the form of a graph. One important goal of data visualization is to let the user obtain knowledge about the intrinsic structure of data, i.e. to understand how it is organized on a large scale. To this end, our proposed algorithm focuses on preserving global distances and topology. ShapeVis encodes the geometric properties of the original data by capturing small-neighborhood relationships within its nodes and topological features like connected components and loops in the graph structure. ShapeVis first finds a subset of points called landmarks along the data manifold and constructs a weighted graph over it that approximates a 1-witness complex [13] on the landmarks. A second level of landmarks are selected in such a manner that their neighborhoods partition the witness graph. The weights between these landmarks are determined by modelling the random movement of a hypothetical particle on the landmarks using a Finite Markov Chain similar to hSNE [37]. This graph is compressed by applying induced maps from standard community detection algorithms. We then prune and reinstate edges in the induced graph based on their modularity to summarize the shape of data. Given its construction, it is scalable to millions of data-points, and the final visualization graph is easy to analyze.
We perform extensive experiments on real-world, large-scale and high-dimensional data sets, including images, text (word embedding) and networks. Experimental results show that our proposed algorithm for constructing the compressed representation captures concise and intuitive visualizations. We compare our approach to Mapper [43] with standard dimensionality reduction functions like LargeVis, UMAP and tSNE as its filter function. We find ShapeVis to be much more efficient when the dataset size is huge. To summarize, we make the following contributions: (1) We propose a visualization technique that captures the intrinsic shape of large-scale and high-dimensional data efficiently (2) We propose a weighting scheme based on a Finite Markov Chain (FMC) built on a witness complex to encode similarities between landmarks (3) We propose a manifold tearing procedure that captures essential loops and connectivity of the data manifold. (4) We conduct experiments on large, real-world data sets and compare ShapeVis with Mapper on LargeVis, UMAP and tSNE, both computationally and visually.

RELATED WORK
Mapper. Techniques in Topological Data Analysis (TDA) compute and analyze topological features of generally high-dimensional and possibly noisy data sets. In particular, the mapper algorithm [43] is the most scalable among TDA approaches. It converts data into a graphical representation where nodes represent collections of similar data points and edges between nodes represent the existence of shared data points between the nodes. It discreetly approximates the Reeb graph [3] of a filter function on the manifold. Despite its success in several business problems, Mapper is an ad hoc technique requiring a significant amount of parameter tuning [8]. Also, Mapper only provides a global scale selection for the covers of data which often results in bad visualizations when data is of non-uniform density. Multimapper [15] tried to address this issue by a scale selection scheme sensitive to the local density of data points. Moreover, when using standard dimensionality reduction algorithms for filter function, Mapper suffers from considerable computational cost. TDA techniques like Mapper has been applied to a variety of domains namely shape analysis [10], sensor-network coverage [14], proteins [21], images [7] [29], social network analysis [9][36], computational neuroscience [25], genomics [6] [5], periodicity in time series [40], cancer [35], materials science [4] [27], financial networks [17] and more.
Landmark selection. Manifold landmarking has been widely used to find a subset of data-points that capture the structural characteristics of the underlying manifold. This helps in reducing the time and space complexity of the subsequent steps in the algorithm. So far, several landmark selection methods have been proposed. Landmarks can be selected randomly from the given data as given in [42]. Another interesting approach is the landmarking procedure described in Fast-Isomap proposed in [28] based on integer optimization. In [30], landmarks are chosen from a central part of the given data.
Witness complex. The witness complex [13] is a computationally feasible approximation of the underlying topological structure of a point cloud. It is built in reference to a subset of points, the landmarks, rather than considering all the points as in the Čech and Vietoris-Rips complexes [19]. The witness complex is a weak approximation [18] of the Delaunay triangulation [11] on the data.
Manifold tearing. Lee and Verleysen [26] introduce a manifold tearing procedure to cut out essential loops to aid in downstream dimensionality-reduction. First, a k-nearest neighbor (kNN) graph on the point cloud sample is constructed. Then, a minimum spanning tree (MST) or a shortest path tree (SPT) containing no cycles is computed on this kNN graph. Finally, edges not generating noncontractible cycles with more than 4 edges are reintroduced to form the final torn graph for downstream dimensionality reduction.

SHAPEVIS
Given a large-scale and high-dimensional dataset X = {x i ∈ R d , i = 1, 2, ..., N }, our goal is to create a compressed graphical representation G of X while preserving the intrinsic structure of the data. Below, we explain the components of our visualization technique.

Manifold landmarking
Our landmark selection procedure proceeds in two stages. In the first stage, for the given original input data X ∈ R d ×N with N records, points in d dimensional space, we uniformly sample M points, X M . We then construct an undirected, unweighted neigh- This graph is further augmented using the remaining points in X \ X M to build a 1-witness complex. For a point x r ∈ X \ X M let x p , x q be its 2-nearest neighbors from X M . Then, we say the point x r is witnessing the 1-simplex {x p , x q } and we add an edge e x p ,x q if not already present in the edge set E M . In the second stage, we select the landmarks L from X M using an inductive procedure similar to the one proposed in [41]. We start by selecting the first landmark l 1 from X M uniformly at random. At the i-th iteration, we mark the k ′ -neighbors of the previously selected landmark l i−1 as covered and remove them from X M . These k ′ -neighbors are termed as neighborhood set of landmark l i−1 . We then inductively select another random point from the remaining set to be l i until all points in X M are marked. This algorithm ensures a selection of landmarks whose neighborhood-sets partition the graph.

Random-walk based weighting
Once we have sampled landmarks L covering the underlying manifold, we construct a weighted, undirected graph G L on this set using the graph G M to capture its topology. Let G L = (V L , E L ,W ) where each node v i ∈ V L corresponds to the landmark l i . The edges E L and their weights W are determined using a Finite Markov Chain to model the random movement of a hypothetical particle on the data manifold. The states are given by the landmarks. For each landmark l i , we start β random walks of fixed length θ 1 ≤ θ ≤ θ 2 on G M . We now define where n i j denotes the number of random walks that started from landmark L i and have their endpoint in the neighborhood set of landmark L j . This method generates a sparse asymmetric matrix A = [a i j ] and the final weight matrix is given by the symmetric

Nerve complex of the graph
Nerve of a cover [19]. An open cover of a space X is a collection of open sets such that each point in the space is in at least one of these open sets. We shall refer to the individual elements of open cover as bins. We can conceptualize covering a space as putting each element in the space in one or more of these bins. Given a cover U of a space X , the nerve N (U) is a simplicial complex constructed as follows: • The vertices (nodes) of N (U) correspond to bins of U Algorithm 1: ShapeVis random walk p of length θ 1 ≤ θ ≤ θ 2 let l i ∈ X L and l ∈ X M be the starting and ending points of p resp. let RevNeigh(l ) = l j set n i j = n i j + 1 end let a i j := n i j / k n ik let w i j := a i j + a ji − a i j · a ji let G L be the graph with adjacency matrix W =  Graph G L obtained in Section 3.2 captures the shape of data, but we only want the higher-level homological features for insightful visualization. Nerve Theorem [19, Corollary 4G.3], as explained above, provides a way to capture the topological structure of a space through a covering of the space. Inspired by this, we want to find a good covering of X that captures its shape through the graph G L . We use community detection algorithms [12,46] to partition the graph into well-separated communities. An induced graph is constructed on this partition whose nodes represent the communities and an edge of weight w exists between partitions if the sum of the weights of the edges between their elements is w. Using techniques from manifold tearing, we remove redundant/weak edges from the induced graph while preserving as much as possible the structural characteristics of the data manifold.

Community Detection on Landmark graph.
Community detection is performed on the graph G L obtained in Section 3.2 to obtain sets {C i } that cover the set V L . This cover partitions the graph such that each node belongs to only one community. Since our visualization technique is unsupervised, we use modularitybased community-detection algorithms that use network structure properties, such as edges and node degrees to find communities. We can use any of the following standard algorithms for community detection: Louvain. [12] This method uses a greedy optimization method that maximizes the modularity of a partition of the network. The optimization is done in two phases. First, individual nodes are moved to a neighboring community that yields the largest increase in modularity. Then an induced graph is created based on the partition obtained in the first phase. Each community in this partition then becomes a node in the induced network. These two phases are repeated until the modularity cannot be increased further.
Leiden. [46] This method is similar to Louvain except for a refinement phase. Here the optimization proceeds in three phases. First, nodes are moved based on modularity optimizations. In the refinement phase, nodes are not necessarily greedily merged with the community that yields the largest increase in modularity. Instead, a node may be merged with any community for which the modularity simply increases. The community with which a node is merged is selected randomly. The aggregation phase then proceeds similarly to the one in Louvain.
Both these methods give rise to a dendrogram structure where each level is a partition of the graph nodes. At the zeroth level is the first partition, which contains the smallest communities, and the final level contains the coarsest communities. The higher the level is, the bigger are the communities. Let the induced graph at partition level p be IG p .

Modularity-based Manifold Tearing
The induced graph IG p = (V p ; E p ) obtained in Section 3.3 is dense with spurious edges and hence does not lead to a comprehensible representation of the data. This step aims at determining a graph G = (V ; E), having the same vertices as the graph IG p , but with a smaller edge set E, such that G represents the overall topological structure of G L . We introduce a two-phase tearing procedure to construct G.
In the first phase we construct a spanning sub-graph G S on IG p . For each edge of the graph IG p , its modularity is computed and inserted in an ordered heap of edges. We then iteratively pop from the heap and introduce the corresponding edge into G S if it results in increased connectivity of the graph until the graph has as many connected components as IG p . This phase results in a sub-graph G S = (V ; E 1 ) that spans the vertices of the induced graph. This procedure differs significantly from the classical manifold tearing one in the following sense. Instead of constructing a minimum spanning tree (MST) or a shortest path tree (SPT) with no cycles on the graph; our procedure constructs a spanning subgraph whose edges are chosen based on their modularity.
Once the spanning subgraph G S is computed, we execute the second phase of the tearing procedure. Whereas classical techniques cut out essential loops to aid in downstream dimensionalityreduction, we introduce as few loops as possible to capture the structure of the data manifold as much as possible. We initialize G with the spanning subgraph G S and gather the edges discarded during the first phase in a set S = E p \ E 1 . In this phase, our procedure only reintroduces those edges from S that generate essential loops. By essential loops we mean those cycles whose sum of edge modularities is more than or equal to c, a user-defined hyperparameter. The idea is to preserve the homological characteristics of the data manifold like connected components and loops.
Thus, the final output is the graph G = (V , E) where local coverings of data are represented as nodes and edges represent the geodesic proximity between them. Branches and loops reflect the topological features of data manifold and are useful in the interactive and unsupervised discovery of segments. In the next section, we show the visualization graph obtained through our approach on high-dimensional and large scale datasets. An example pipeline on synthetic data is shown in Fig 1.

EXPERIMENTS
In this section, we evaluate the effectiveness of our approach in visualizing high-dimensional and large-scale datasets. We compare our visualization approach with the following approaches: We choose these baselines as Mapper also returns a compressed visualization of data in the form of a graph similar to ShapeVis. Dimensionality reduction algorithms are a standard choice of filter function in Mapper to compress the data into a 2-dim space, and t-SNE [31], UMAP [32], LargeVis [44] are widely used state-of-the-art dimensionality reduction algorithms. More details about Mapper algorithm can be found in [43]. In the next section, we show that visualization quality of our approach is comparable and sometimes on-par to the above-mentioned approaches while being scalable to millions of data-points.

Datasets
We use the following datasets for comparison and visualization purposes. It includes both high-dimensional and large-scale realworld datasets.
• MNIST [24]. The dataset consists of 70000 28x28images of handwritten digits (0-9). Each data-point is a 784dimensional vector. • F-MNIST [51]. Fashion MNIST is a dataset of 28x28images of fashion items like clothing, shoes etc. There are 10 classes and total of 70000 images. • GoogleNews Vectors [33]. It is a dataset of 3 million words and phrases from GoogleNews dataset. Each word is embedded into a 300-dimensional vector space using word2vec [33] approach.
• LiveJournal [52]. It is a social network dataset from an online blogging community with around 4 million nodes. For common comparison with other methods, we first learn a 100-dimensional representation of each node using LINE [45] algorithm before visualizing it. Note that our algorithm can be easily modified to work directly over graphs as well.

Implementation Details
We explain our choice of hyperparameters for ShapeVis implementation. We initialize M, which is the number of points sampled for creating witness complex G M , as a minimum of 1 Million or N /3. N is the total number of data points. For the construction of k-nn graph G M we keep the number of nearest neighbours k fixed at 10 for all datasets. Note that k should be such that G M captures the local connectivity in the dataset and therefore a small value of k is good if the sample size is large enough. For finding k-nearest neighbors we use the nn-descent algorithm of [16]. Number of random walks β is 1000 and θ 1 , θ 2 is fixed as l/2, l where l = 50 for all datasets. We found the algorithm to be stable for various choices of l and β greater than a threshold and chose the minimum to optimize time. For IG p we choose partition level p as 0 and find it to work best for all datasets. Similarly, the parameter c during manifold tearing step is kept fixed at 2 * loд(Modularity of IG p ). For Mapper, we show the best visualization obtained by tuning hyper-parameters wherever possible. For LargeVis and UMAP we use the reference implementation of [44] and [32], and for t-SNE, we use Multicore t-SNE package [47].

Qualitative Comparison
Labeled datasets. For comparing visualization quality on datasets with ground truth labels, we color each node in the visualization graph with its dominant label. Fig 2 shows the visualization obtained on MNIST dataset. We can see that ShapeVis as well as Mapper(UMAP) and Mapper(LargeVis) coherently capture the global relationship between different digits with clusters of (1,2), (3,5,8), (0,6) and (4,7,9). But ShapeVis also captures the local within-cluster relationships, e.g. the two branches of '4' in Fig 2 (a) corresponds to the two different ways of writing it: upside-down lower-case 'h' and closed digit '4'. Fig 3 shows the visualization obtained on F-MNIST dataset. Though all the visualizations show the separation between the two broad category clothing and footwear, ShapeVis captures the relationship between different classes more coherently. For example, Trouser class is connected to Dress class through a single node instead of being disconnected with the graph as is in Mapper(UMAP) and Mapper(LargeVis). Similarly Bag class is connected with T-shirt/Top as compared to Ankle-Boot class. The loop in ShapeVis visualization captures the similarity chain of the classes Dress, T-shirt, Pullover and Coat, which other approaches fail to capture. Another detail which ShapeVis captures more vividly is that images of sleeveless tees though labeled T-shirt is clubbed with Dress nodes because of its visual similarity to short dresses than the T-shirt node.
Unlabeled datasets. For LiveJournal and GoogleNews vectors, no ground truth class label is available. Therefore, for comparing the visualization quality of ShapeVis to other approaches, we assign  pseudo labels to each data point and then color each with its dominant pseudo label. For assigning a pseudo label, we run Louvain community detection [12] on ShapeVis (Mapper) graph to partition it into segments, and each data point is assigned the label of the segment to which it belongs. Fig 4, rows 1 and 2, show the visualization on LiveJournal dataset when pseudo labels are assigned using segments of Mapper(UMAP) and ShapeVis, respectively. We can see in Fig 4 row 1, that the segments found through ShapeVis correspond well with the segments in Mapper(UMAP) and Mapper(LargeVis). Similarly, segments of Mapper (UMAP) align with the segments of ShapeVis and Mapper(LargeVis). This shows that visualization obtained through our approach is qualitatively similar to Mapper with UMAP or LargeVis filter functions. We do not show Mapper(t-SNE) as we were unable to run t-SNE on these datasets because of its huge time-complexity. Fig 4, rows 3 and 4, show the visualization on GoogleNews vectors. Both Mapper(UMAP) and Mapper(LargeVis) fail to bring any clear segmentation of dataset in the visualization. Moreover, we do not see any alignment between segments of different visualizations. We also compute the average cosine similarity between word-vectors belonging to the same segments for all three visualizations. For ShapeVis, Mapper(UMAP) and Mapper(LargeVis) average cosine similarity between words of a segment is 0.224, 0.186 and 0.132, respectively. Thus ShapeVis performs slightly better by this measure.

Time Comparison
We compare the running time of ShapeVis against other approaches on all the above mentioned datasets. All the results are executed on a machine with 48GB memory and 6 cores. For LiveJournal and GoogleNews vectors, we compare on 2 million and 1 million subsets respectively since UMAP returned memory overflow error on the complete dataset. Table 1 shows the running time of all approaches in seconds. We can see that ShapeVis significantly outperforms other methods for large datasets and is comparable on smaller datasets.
We further analyze the scalability of ShapeVis with dataset size by running it on random samples of points from a uniform sphere of 25-dimension. Fig 5 shows the plot of running time (in seconds) vs the number of sampled points for all approaches. It shows that as the dataset size increases ShapeVis is more and more efficient as compared to Mapper with t-SNE, UMAP or LargeVis filter functions.

CONCLUSION
In this paper, we proposed ShapeVis, a graph-based visualization technique that aims to preserve the topological structure of data in the form of a summarized graph. The 2-step landmark sampling in ShapeVis helps it to scale to millions of data-points with consistency. Experiments on labeled real-world datasets show that ShapeVis captures the global relationship between different labels coherently. For unlabeled datasets, the visualization of ShapeVis is qualitatively similar to existing approaches. It captures the relationship between different local neighourhoods of data in a concise manner and scales with significantly lower running time. In the future, we aim to incorporate hierarchical visualization into ShapeVis. Although we show only high level details in the current visualization, it can be easily extended to interactively explore the segments of the graph at a finer scale.