Towards an Optimal Bound for the Interleaving Distance on Mapper Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908968475951104 |
|---|---|
| author | Chambers, Erin Wolf Ghosh, Ishika Munch, Elizabeth Percival, Sarah Wang, Bei |
| author_facet | Chambers, Erin Wolf Ghosh, Ishika Munch, Elizabeth Percival, Sarah Wang, Bei |
| contents | Mapper graphs are widely used tools in topological data analysis and visualization. They can be understood as discrete approximations of Reeb graphs, providing insight into the shape and connectivity of complex data. Given a high-dimensional point cloud together with a real-valued function defined on it, a mapper graph summarizes the induced topological structure: each node represents a local neighborhood, and edges connect nodes whose corresponding neighborhoods overlap. Our focus is the interleaving distance for mapper graphs, arising as a discretized analogue of the interleaving distance for Reeb graphs-a quantity known to be NP-hard to compute. This distance measures how similar two mapper graphs are by quantifying how much they must be ``stretched'' to be made comparable. Recent work introduced a loss function that gives an upper bound on this distance. The loss evaluates how far a given collection of maps, called an assignment, is from being a true interleaving. Importantly, it is computationally tractable, offering a practical way to bound the distance, however the quality of the bound is dependent on the choice of assignment. In this paper, we develop the first framework for bounding the interleaving distance on mapper graphs. We present the bound in two ways: first, by formulating an integer linear program (ILP) that determines whether an $n$-interleaving exists for a given $n$; and second, by constructing an ILP that identifies an assignment with minimal loss for that $n$. We also evaluate the method on small examples where the interleaving distance is known, and on benchmark and simulated datasets, demonstrating the utility of the approach for classification tasks based on mapper graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_03865 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Towards an Optimal Bound for the Interleaving Distance on Mapper Graphs Chambers, Erin Wolf Ghosh, Ishika Munch, Elizabeth Percival, Sarah Wang, Bei Computational Geometry 55N31 Mapper graphs are widely used tools in topological data analysis and visualization. They can be understood as discrete approximations of Reeb graphs, providing insight into the shape and connectivity of complex data. Given a high-dimensional point cloud together with a real-valued function defined on it, a mapper graph summarizes the induced topological structure: each node represents a local neighborhood, and edges connect nodes whose corresponding neighborhoods overlap. Our focus is the interleaving distance for mapper graphs, arising as a discretized analogue of the interleaving distance for Reeb graphs-a quantity known to be NP-hard to compute. This distance measures how similar two mapper graphs are by quantifying how much they must be ``stretched'' to be made comparable. Recent work introduced a loss function that gives an upper bound on this distance. The loss evaluates how far a given collection of maps, called an assignment, is from being a true interleaving. Importantly, it is computationally tractable, offering a practical way to bound the distance, however the quality of the bound is dependent on the choice of assignment. In this paper, we develop the first framework for bounding the interleaving distance on mapper graphs. We present the bound in two ways: first, by formulating an integer linear program (ILP) that determines whether an $n$-interleaving exists for a given $n$; and second, by constructing an ILP that identifies an assignment with minimal loss for that $n$. We also evaluate the method on small examples where the interleaving distance is known, and on benchmark and simulated datasets, demonstrating the utility of the approach for classification tasks based on mapper graphs. |
| title | Towards an Optimal Bound for the Interleaving Distance on Mapper Graphs |
| topic | Computational Geometry 55N31 |
| url | https://arxiv.org/abs/2504.03865 |