When Dimensionality Reduction Meets Graph (Drawing) Theory: Introducing a Common Framework, Challenges and Opportunities Volume: 22 Issue: 22
F. V. Paulovich 1 , A. Arleo 1 , and S. van den Elzen 1 1 Eindhoven University of Technology (TU/e), The Netherlands · 2024
Read When Dimensionality Reduction Meets Graph (Drawing) Theory: Introducing a Common Framework, Challenges and Opportunities Volume: 22 Issue: 22 by F. V. Paulovich 1 , A. Arleo 1 , and S. van den Elzen 1 1 Eindhoven University of Technology (TU/e), The Netherlands (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-06555.txt.
Introduction
Fernando Paulovich, Alessio Arleo, and Stef van den Elzen argue, in a 2024 paper, that two chart-making fields long kept apart should share one framework. One field flattens high-dimensional data so people can see clusters and likeness. The other draws networks so their structure and key nodes stand out. Both, the authors say, solve near kin problems.
Their framework splits flattening into clear stages, from pulling out structure to placing points and checking the result. Graph tools slot into each stage: drawing methods can seed layouts, and network measures can test whether key shapes survived. The paper maps current techniques onto the stages and names hard parts and chances for joint work ahead.
Catalog record
| CREATOR | F. V. Paulovich 1 , A. Arleo 1 , and S. van den Elzen 1 1 Eindhoven University of Technology (TU/e), The Netherlands |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-06555
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
When Dimensionality Reduction Meets Graph (Drawing) Theory: Introducing a Common Framework, Challenges and Opportunities Volume: 22 Issue: 22 F. V. Paulovich 1 , A. Arleo 1 , and S. van den Elzen 1 1 Eindhoven University of Technology (TU/e), The Netherlands Abstract In the vast landscape of visualization research, Dimensionality Reduction (DR) and graph analysis are two popular subfields, often essential to most visual data analytics setups. DR aims to create representations to support neighborhood and similarity analysis on complex, large datasets. Graph analysis focuses on identifying the salient topological properties and key actors within networked data, with specialized research on investigating how such features could be presented to the user to ease the comprehension of the underlying structure. Although these two disciplines are typically regarded as disjoint subfields, we argue that both fields share strong similarities and synergies that can potentially benefit both. Therefore, this paper discusses and introduces a unifying framework to help bridge the gap between DR and graph (drawing) theory. Our goal is to use the strongly math-grounded graph theory to improve the overall process of creating DR visual representations. We propose how to break the DR process into well-defined stages, discussing how to match some of the DR state-of-the-art techniques to this framework and presenting ideas on how graph drawing, topology features, and some popular algorithms and strategies used in graph analysis can be employed to improve DR topology extraction, embedding generation, and result validation. We also discuss the challenges and identify opportunities for implementing and using our framework, opening directions for future visualization research. \SpecialIssuePaper \CGFccby † † year: 2002 † † year: 2002 † † editors: 22 † † orcid: 0000-0002-2316-760X † † orcid: 0000-0003-2008-3651 † † orcid: 0000-0003-1245-0503 † † teaser: Our approach explores the integration and alignment of the various stages in Dimensionality Reduction (DR) and Graph Drawing, demonstrating that strategies and algorithms in both areas share similar objectives but use complementary methods. With topology extraction techniques, high-dimensional data can be converted into graph data and vice versa. In the context of DR, distances are defined based on facets of the data, creating a matrix that simulates a weighted, fully-connected graph. The relationships facilitate the creation of a mapping, with subsequent quality analysis comparing the two, and enabling iterative updates. The outcome of this mapping is visualized, offering interaction for human-in-the-loop analytics. Linking concepts and stages from both domains creates substantial opportunities for cross-fertilization. 1 Introduction Dimensionality Reduction (DR) is commonly described by the visualization community as the process of mapping data items from a high-dimensional space to points in a lower dimensional visual space, usually 2D or 3D [ EMK∗21 , NA19 ] . The resulting visual representations aim to capture some trait of the data structure (either a local or global structure). On the other hand, Graph Drawing (GD) is the discipline rooted in graph theory and information visualization that investigates how to construct readable geometric visual representations of graphs in the 2D plane such that the geometry of the drawing faithfully resembles the topology of the original data structure [ DGLT17 ] . Although somewhat separate disciplines, GD has already benefited from strategies introduced by DR methods. For instance, DRGraph [ ZCH∗21 ] accelerates the embedding of large graphs using a multi-level methodology based on t-SNE [ vdMH08 ] , borrowing ideas early introduced by Walshaw [ Wal03 ] to improve running times and drawing quality. The opposite perspective, benefiting DR from GD has also been implicitly and explicitly discussed, among others, in the t-SNE [ vdMH08 ] and UMAP papers [ MHM18 ] . Drawing methods, however, are not the only algorithms in the intersection of DR and GD. Topology transformation has also been considered. In a recent paper, Bot et al. [ BHA∗24 ] , introduce a minimum-spanning-tree-based manifold approximation capable of crossing sampling gaps without introducing shortcuts, increasing robustness of DR algorithms in case of non-uniformly sampled manifolds. These examples suggest a strong interconnection between the two disciplines that goes beyond just the calculation of the embedding. Our claim is that GD and DR methods are not alternatives but rather complementary strategies and that their interplay, although already considered, remains largely unexplored. In this paper, our focus is to better formalize the interactions between DR and GD, focusing on leveraging the opportunities concerning the integration of GD theory and techniques within the DR visualization pipeline. We use the visualization reference model as a theoretical basis on which to ground our work [ Maz09 ] . This model describes the generation of a visual representation of data as a multi-stage process: (i) data preparation, including processing and transformations; (ii) visual mapping and view creation; and (iii) insight generation through analysis and (iv) exploration. Given the networked nature of the data at hand, we rename these stages as follows: Relationships (or topology extraction ), Mapping (or embedding generation ), Quality Analysis (or result validation ), and Visualization & Interaction (see Figure ). Within this context, we outline how GD theory and drawing techniques can contribute to the efficacy of DR approaches in generating, validating, and visualizing an embedding of a DR layout in the plane. Our contributions are as follows. We introduce and formalize a framework to map the interplay between DR and GD. Within this framework, we outline both acknowledged methodologies and new opportunities from graph theory to integrate within the DR pipeline, with potential new ideas for further work. Our goal is to raise awareness of unexploited opportunities at the intersection of DR, GD, and network visualization, defining a common terminology to foment opportunities to exploit the synergies between both fields. 2 Related Work and Background In this section, the literature related to our solution is discussed. It is not our intention to survey the DR and GD field to map it within our proposed framework, but rather to present the important terminology and concepts that delineate our approach. For an extensive and detailed discussion of technical aspects, applications, and comparison of DR techniques, we suggest [ VDMPVDH∗09 , NA19 , EMK∗21 ] . For GD and network visualization, we refer the interested reader to the meta-survey by Filipov et al. [ FAM23 ] . Dimensionality Reduction (DR) has multiple definitions. In mathematical terms, let’s {\mathcal{X}=\{x_{i},\ldots,x_{N}\}\in\mathbb{R}^{m}} be a set of N data items represented in an m -dimensional space and {\mathcal{Y}=\{y_{i},\ldots,y_{N}\}\in\mathbb{R}^{n=\{2,3\}}} their mappings to the visual space. A DR technique can be viewed as a function {f:\mathcal{X}\rightarrow\mathcal{Y}} , which maps each data item x_{i} into a point y_{i} , seeking to preserve relationships between items defined on the high-dimensional space as much as possible on the mapped points [ EMK∗21 ] . The existing literature on DR offers different taxonomies and categorizations of the existing techniques. A common classification splits the techniques into two major groups: global and local techniques [ MHM18 ] . While in global techniques, full pairwise relationships among data items are considered, in local, only neighborhoods are used to represent how data items are related, for instance, how data items are similar or dissimilar. Examples of global techniques involve classical Multidimensional Scaling (MDS) [ Tor52 ] , Random Projection (RP) [ Ach03 ] , Part-linear Multidimensional Projections (PLMP) [ PSN10 ]