In search of the most efficient and memory-saving visualization of high dimensional data

Abstract

Interaktywna, wizualna eksploracja dużych, wielowymiarowych zbiorów danych odgrywa bardzo ważną rolę w różnych dziedzinach nauki, która wymaga zagregowanej informacji o wzajemnych relacjach między wieloma obiektami. Umożliwia ona nie tylko rozpoznanie ich istotnych cech i form strukturalnych, takich jak skupiska wierzchołków i ich wzorce połączeń, ale także ocenę ich wzajemnych relacji w zakresie położenia, odległości, kształtu i gęstości połączeń. Twierdzimy, że wizualizacja wielowymiarowych danych (AD) jest dobrze przybliżana przez problem dwuwymiarowego (2D) osadzania nieukierunkowanych grafów najbliższych sąsiadów (ang. kNN graphs). W dzisiejszych czasach, rozmiar złożonych sieci (zbiorów danych) G(V,E) (\V=M~106+) stanowi duże wyzwanie dla dzisiejszych systemów komputerowych i wciąż wymaga bardziej wydajnych algorytmów osadzania danych wielowymiarowych. Istniejące metody redukcji wymiarowości danych, które wymagają większej złożoności obliczeniowej i pamięciowej niż O(M), są zbyt wolne do interaktywnej manipulacji na dużych sieciach obejmujących miliony wierzchołków. Pokazujemy, że osadzenia wysokiej jakości mogą być produkowane przy minimalnej złożoności czasowej i pamięciowej. Przedstawiamy bardzo wydajne algorytmy IVHD oraz IVHD-CUDA, a następnie porównujemy je z najnowszymi i najpopularniejszymi metodami redukcji wymiarowości (zarówno w wersji dla CPU, jak i GPU): t-SNE, UMAP, TriMAP, PaCMAP, BH-SNE-CUDA oraz AtSNE-CUDA. Pokazujemy, że wymagania pamięciowe i czasowe dla IVHD są radykalnie niższe niż dla kodów bazowych. Na przykład, IVHD-CUDA jest prawie 30 razy szybsza w osadzaniu (bez procedury generowania grafu najbliższych sąsiadów, która jest taka sama dla wszystkich metod) jednego z największych użytych zbiorów danych, YAHOO (M=1.4x106), niż AtSNE-CUDA. Stwierdzamy, że kosztem niewielkiego pogorszenia jakości osadzania, w porównaniu do algorytmów bazowych, IVHD dobrze zachowuje główne własności strukturalne danych ND w 2D przy znacznie niższym budżecie czasowym. Przedstawiamy również meta-algorytm, który umożliwia wykorzystanie dowolnej nienadzorowanej metody osadzania danych w sposób nadzorowany i w rezultacie pozwala na elastyczną kontrolę globalnych i lokalnych własności osadzenia. Dzięki temu, nasze metody mogą być dobrym kandydatem do interaktywnej wizualizacji naprawdę dużych zbiorów danych (M=108+) i mogą być dalej wykorzystywane do inspekcji i interpretacji zależności pomiędzy alternatywnymi reprezentacjami obserwacji wyuczonymi przez sztuczne sieci neuronowe (ang. ANN). Interactive visual exploration of large, high-dimensional datasets plays a very important role in various fields of science, which requires aggregated information about mutual relationships between numerous objects. It enables not only to recognize their important structural features and forms, such as clusters of vertices and their connectivity patterns, but also to assess their mutual relationships in terms of position, distance, shape, and connection density. The structural properties of these large datasets can be scrutinized throughout their interactive visualization. We argue that the visualization of very high-dimensional data is well approximated by the two-dimensional (2D) problem of embedding undirected ANN-graphs. In the advent of the big data era, the size of complex networks (datasets) G(V,E) (\V=M~106+) represents a great challenge for today's computer systems and still requires more efficient ND to 2D dimensionality reduction (DR) algorithms. The existing DR methods, which involve more computational and memory complexities than O(M), are too slow for interactive manipulation on large networks that involve millions of vertices. We show that high-quality embeddings can be produced with minimal time&memory complexity. Very efficient IVHD (interactive visualization of high-dimensional data) and IVHD-CUDA algorithms are presented and then compared to the state-of-the-art DR methods (both CPU and GPU versions): t-SNE, UMAP, TriMAP, PaCMAP, BH-SNE-CUDA, and AtSNE-CUDA. We show that the memory and time requirements for IVHD are radically lower than those for the baseline codes. For example, IVHD-CUDA is almost 30 times faster in embedding (without the ANN graph generation procedure, which is the same for all methods) of one of the largest datasets used, YAHOO (M=1.4x106), than AtSNE-CUDA. We conclude that at the expense of a minor deterioration of embedding quality, compared to baseline algorithms, IVHD well preserves the main structural properties of ND data in 2D for a significantly lower computational budget. We also present a meta-algorithm that enables using any unsupervised DR method in supervised fashion and as a result allows for flexible control of global and local properties of the embedding. Thus, our methods can be a good candidate for an interactive visualization of truly big data (M=108+) and can be further used to inspect and interpret relationships between alternative representations of observations learned by artificial neural networks (ANN). Additionally, we have provided a framework for testing the trade-off between preservation of global structure and local structure of DR.