The Inverse Mapper Problem for Two-Dimensional Data

Abstract

The Mapper algorithm is a popular graphical tool for data visualization and exploration in topological data analysis (TDA). It takes as input a data set $X$ and returns a graph that aims to capture the underlying topological features of these data. The Mapper algorithm has several parameters that need to be specified by the user: a $\text{filter function}$ $f:X\to Y$ where $X$ is often a point cloud data set in ${\mathbb{R}}^n$ and $Y$ is the $\text{reference space}$ that is often a lower dimensional Euclidean space, a $\text{cover}$ of $f(X)$, and a $\text{clustering algorithm}$ that is applied to the pre-image of each element in the cover. In this paper, we consider the following question: What graphs can occur as the output of the Mapper algorithm? It is known that when $Y={\mathbb{R}}^3$, any graph can be a Mapper graph. In this work, we focus on a more practical case where the filter function is $f:{\mathbb{R}}^2\to \mathbb{R}$. We consider two different scenarios. In the first scenario, we fix the parameters of the Mapper algorithm, but vary the data. This way we characterize exactly the graphs that can occur for several choices of parameters. In the second scenario, we fix the data set but vary the parameters. This can be seen as a way to understand how much the output can differ depending on the choices of parameters.In both settings, we find close connections to classical topics in graph drawing.

arXiv comment17 pages, 7 figures