skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Probabilistic convergence and stability of random mapper graphs
Abstract We study the probabilistic convergence between the mapper graph and the Reeb graph of a topological space $${\mathbb {X}}$$ X equipped with a continuous function $$f: {\mathbb {X}}\rightarrow \mathbb {R}$$ f : X → R . We first give a categorification of the mapper graph and the Reeb graph by interpreting them in terms of cosheaves and stratified covers of the real line $$\mathbb {R}$$ R . We then introduce a variant of the classic mapper graph of Singh et al. (in: Eurographics symposium on point-based graphics, 2007), referred to as the enhanced mapper graph, and demonstrate that such a construction approximates the Reeb graph of $$({\mathbb {X}}, f)$$ ( X , f ) when it is applied to points randomly sampled from a probability density function concentrated on $$({\mathbb {X}}, f)$$ ( X , f ) . Our techniques are based on the interleaving distance of constructible cosheaves and topological estimation via kernel density estimates. Following Munch and Wang (In: 32nd international symposium on computational geometry, volume 51 of Leibniz international proceedings in informatics (LIPIcs), Dagstuhl, Germany, pp 53:1–53:16, 2016), we first show that the mapper graph of $$({\mathbb {X}}, f)$$ ( X , f ) , a constructible $$\mathbb {R}$$ R -space (with a fixed open cover), approximates the Reeb graph of the same space. We then construct an isomorphism between the mapper of $$({\mathbb {X}},f)$$ ( X , f ) to the mapper of a super-level set of a probability density function concentrated on $$({\mathbb {X}}, f)$$ ( X , f ) . Finally, building on the approach of Bobrowski et al. (Bernoulli 23 (1):288–328, 2017b), we show that, with high probability, we can recover the mapper of the super-level set given a sufficiently large sample. Our work is the first to consider the mapper construction using the theory of cosheaves in a probabilistic setting. It is part of an ongoing effort to combine sheaf theory, probability, and statistics, to support topological data analysis with random data.  more » « less
Award ID(s):
1907591 1661375
PAR ID:
10295929
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
Journal of Applied and Computational Topology
Volume:
5
Issue:
1
ISSN:
2367-1726
Page Range / eLocation ID:
99 to 140
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Mulzer, Wolfgang; Phillips, Jeff M (Ed.)
    Given a map f:X → M from a topological space X to a metric space M, a decorated Reeb space consists of the Reeb space, together with an attribution function whose values recover geometric information lost during the construction of the Reeb space. For example, when M = ℝ is the real line, the Reeb space is the well-known Reeb graph, and the attributions may consist of persistence diagrams summarizing the level set topology of f. In this paper, we introduce decorated Reeb spaces in various flavors and prove that our constructions are Gromov-Hausdorff stable. We also provide results on approximating decorated Reeb spaces from finite samples and leverage these to develop a computational framework for applying these constructions to point cloud data. 
    more » « less
  2. ; ; ; (, 40th International Symposium on Computational Geometry (SoCG 2024), Leibniz International Proceedings in Informatics (LIPIcs))
    Mulzer, Wolfgang; Phillips, Jeff M (Ed.)
    A Reeb graph is a graphical representation of a scalar function on a topological space that encodes the topology of the level sets. A Reeb space is a generalization of the Reeb graph to a multiparameter function. In this paper, we propose novel constructions of Reeb graphs and Reeb spaces that incorporate the use of a measure. Specifically, we introduce measure-theoretic Reeb graphs and Reeb spaces when the domain or the range is modeled as a metric measure space (i.e., a metric space equipped with a measure). Our main goal is to enhance the robustness of the Reeb graph and Reeb space in representing the topological features of a scalar field while accounting for the distribution of the measure. We first introduce a Reeb graph with local smoothing and prove its stability with respect to the interleaving distance. We then prove the stability of a Reeb graph of a metric measure space with respect to the measure, defined using the distance to a measure or the kernel distance to a measure, respectively. 
    more » « less
  3. ; ; (, International Mathematics Research Notices)
    Abstract We propose a new approach to deriving quantitative mean field approximations for any probability measure $$P$$ on $$\mathbb {R}^{n}$$ with density proportional to $$e^{f(x)}$$, for $$f$$ strongly concave. We bound the mean field approximation for the log partition function $$\log \int e^{f(x)}dx$$ in terms of $$\sum _{i \neq j}\mathbb {E}_{Q^{*}}|\partial _{ij}f|^{2}$$, for a semi-explicit probability measure $$Q^{*}$$ characterized as the unique mean field optimizer, or equivalently as the minimizer of the relative entropy $$H(\cdot \,|\,P)$$ over product measures. This notably does not involve metric-entropy or gradient-complexity concepts which are common in prior work on nonlinear large deviations. Three implications are discussed, in the contexts of continuous Gibbs measures on large graphs, high-dimensional Bayesian linear regression, and the construction of decentralized near-optimizers in high-dimensional stochastic control problems. Our arguments are based primarily on functional inequalities and the notion of displacement convexity from optimal transport. 
    more » « less
  4. ; ; (, Pacific Journal of Mathematics)
    Let $$\phi(x,y)$$ be a continuous function, smooth away from the diagonal, such that, for some $$\alpha>0$$, the associated generalized Radon transforms \begin{equation} \label{Radon} R_t^{\phi}f(x)=\int_{\phi(x,y)=t} f(y) \psi(y) d\sigma_{x,t}(y) \end{equation} map $$L^2({\mathbb R}^d) \to H^{\alpha}({\mathbb R}^d)$$ for all $t>0$. Let $$E$$ be a compact subset of $${\mathbb R}^d$$ for some $$d \ge 2$$, and suppose that the Hausdorff dimension of $$E$$ is $$>d-\alpha$$. We show that any tree graph $$T$$ on $k+1$ ($$k \ge 1$$) vertices is realizable in $$E$$, in the sense that there exist distinct $$x^1, x^2, \dots, x^{k+1} \in E$$ and $t>0$ such that the $$\phi$$-distance $$\phi(x^i, x^j)$$ is equal to $$t$$ for all pairs $(i,j)$ corresponding to the edges of the graph $$T$$. 
    more » « less
  5. ; ; ; (, Journal of Applied and Computational Topology)
    Abstract Data consisting of a graph with a function mapping into$${\mathbb {R}}^d$$ R d arise in many data applications, encompassing structures such as Reeb graphs, geometric graphs, and knot embeddings. As such, the ability to compare and cluster such objects is required in a data analysis pipeline, leading to a need for distances between them. In this work, we study the interleaving distance on discretization of these objects, called mapper graphs when$$d=1$$ d = 1 , where functor representations of the data can be compared by finding pairs of natural transformations between them. However, in many cases, computation of the interleaving distance is NP-hard. For this reason, we take inspiration from recent work by Robinson to find quality measures for families of maps that do not rise to the level of a natural transformation, called assignments. We then endow the functor images with the extra structure of a metric space and define a loss function which measures how far an assignment is from making the required diagrams of an interleaving commute. Finally we show that the computation of the loss function is polynomial with a given assignment. We believe this idea is both powerful and translatable, with the potential to provide approximations and bounds on interleavings in a broad array of contexts. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email