Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Convolutional persistence transforms

  • Published:
Journal of Applied and Computational Topology Aims and scope Submit manuscript

Abstract

In this paper, we consider topological featurizations of data defined over simplicial complexes, like images and labeled graphs, obtained by convolving this data with various filters before computing persistence. Viewing a convolution filter as a local motif, the persistence diagram of the resulting convolution describes the way the motif is distributed across the simplicial complex. This pipeline, which we call convolutional persistence, extends the capacity of topology to observe patterns in such data. Moreover, we prove that (generically speaking) for any two labeled complexes one can find some filter for which they produce different persistence diagrams, so that the collection of all possible convolutional persistence diagrams is an injective invariant. This is proven by showing convolutional persistence to be a special case of another topological invariant, the Persistent Homology Transform. Other advantages of convolutional persistence are improved stability, greater flexibility for data-dependent vectorizations, and reduced computational complexity for certain data types. Additionally, we have a suite of experiments showing that convolutions greatly improve the predictive power of persistence on a host of classification tasks, even if one uses random filters and vectorizes the resulting diagrams by recording only their total persistences.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17

Similar content being viewed by others

Notes

  1. The main theorem of (Cohen-Steiner et al. 2007) is much more general, applying to tame functions on triangulable spaces, conditions which are automatically satisfied in the simplicial setting.

  2. The symbol \(\odot \) refers to the Hadamard product, which performs componentwise multiplication between vectors.

  3. See (Hewitt and Ross 2012), Theorem 20.18 on page 296, for a proof of Young’s inequality for locally compact groups, which in particular includes \(\mathbb {Z}^d\).

References

  • Acharya, S., Pant, AK., Gyawali, PK.: Deep learning based large scale handwritten devanagari character recognition. In: 2015 9th International Conference on Software, Knowledge, Information Management and Applications (SKIMA), pp. 1–6 IEEE (2015)

  • Adams, H., Emerson, T., Kirby, M., et al.: Persistence images: a stable vector representation of persistent homology. J Mach Learn Res 18, 1–35 (2017)

    MathSciNet  Google Scholar 

  • Alpaydin, E., Kaynak, C.: Optical Recognition of Handwritten Digits Data Set. UCI Machine Learning Repository (1998)

  • Aukerman, A., Carrière, M., Chen, C., et al.: Persistent homology based characterization of the breast cancer immune microenvironment: a feasibility study. In: 36th International Symposium on Computational Geometry (SoCG) (2020)

  • Belton, RL., Fasy, BT., Mertz, R., et al.: Learning Simplicial Complexes from Persistence Diagrams (2018). arXiv preprint arXiv:1805.10716

  • Belton, R.L., Fasy, B.T., Mertz, R., et al.: Reconstructing embedded graphs from persistence diagrams. Comput. Geom. 90(101), 658 (2020)

    MathSciNet  Google Scholar 

  • Bendich, P., Bubenik, P., Wagner, A.: Stabilizing the unstable output of persistent homology computations. J. Appl. Comput. Topol. 4(2), 309–338 (2020)

    Article  MathSciNet  Google Scholar 

  • Bestvina, M., Brady, N.: Morse theory and finiteness properties of groups. Invent. Math. 129(3), 445–470 (1997)

    Article  MathSciNet  Google Scholar 

  • Bleile, B., Garin, A., Heiss, T., et al.: The Persistent Homology of Dual Digital Image Constructions (2021). arXiv preprint arXiv:2102.11397

  • Botnan, MB., Lesnick, M.: An Introduction to Multiparameter Persistence (2022). arXiv preprint arXiv:2203.14289

  • Bubenik, P., Wagner, A.: Embeddings of persistence diagrams into Hilbert spaces. J. Appl. Comput. Topol. 4(3), 339–351 (2020)

    Article  MathSciNet  Google Scholar 

  • Bubenik, P., et al.: Statistical topological data analysis using persistence landscapes. J. Mach. Learn. Res. 16(1), 77–102 (2015)

    MathSciNet  Google Scholar 

  • Buchet, M., Chazal, F., Dey, TK., et al.: Topological Analysis of Scalar Fields with Outliers (2014). arXiv preprint arXiv:1412.1680

  • Calcina, S.S., Gameiro, M.: Parameter estimation in systems exhibiting spatially complex solutions via persistent homology and machine learning. Math. Comput. Simul. 185, 719–732 (2021)

    Article  MathSciNet  Google Scholar 

  • Carlsson, G.: Topology and data. Bull. Am. Math. Soc. 46(2), 255–308 (2009)

    Article  MathSciNet  Google Scholar 

  • Carlsson, G., Ishkhanov, T., De Silva, V., et al.: On the local behavior of spaces of natural images. Int. J. Comput. Vis. 76(1), 1–12 (2008)

    Article  MathSciNet  Google Scholar 

  • Carrière, M., Oudot, SY., Ovsjanikov, M.: Stable topological signatures for points on 3D shapes. In: Computer graphics forum, pp. 1–12. Wiley Online Library (2015)

  • Carriere, M., Chazal, F., Glisse, M., et al.: Optimizing persistent homology based functions. In: International Conference on Machine L0earning, pp. 1294–1303. PMLR (2021)

  • Chung, Y.M., Day, S.: Topological fidelity and image thresholding: a persistent homology approach. J. Math. Imaging Vis. 60(7), 1167–1179 (2018)

    Article  MathSciNet  Google Scholar 

  • Chung, Y.M., Day, S., Hu, C.S.: A multi-parameter persistence framework for mathematical morphology. Sci. Rep. 12(1), 1–25 (2022)

    Article  Google Scholar 

  • Cohen-Steiner, D., Edelsbrunner, H., Harer, J.: Stability of persistence diagrams. Discrete Comput. Geom. 37(1), 103–120 (2007)

    Article  MathSciNet  Google Scholar 

  • Crawford, L., Monod, A., Chen, A.X., et al.: Predicting clinical outcomes in glioblastoma: an application of topological and functional data analysis. J. Am. Stat. Assoc. 115(531), 1139–1150 (2020)

    Article  MathSciNet  Google Scholar 

  • Cuerno, R., Barabási, A.L.: Dynamic scaling of ion-sputtered surfaces. Phys. Rev. Lett. 74(23), 4746 (1995)

    Article  Google Scholar 

  • Curry, J.: The fiber of the persistence map for functions on the interval. J. Appl. Comput. Topol. 2(3), 301–321 (2018)

    Article  MathSciNet  Google Scholar 

  • Curry, J., Mukherjee, S., Turner, K.: How Many Directions Determine a Shape and Other Sufficiency Results for Two Topological Transforms (2018). arXiv preprint arXiv:1805.09782

  • Deng, L.: The mnist database of handwritten digit images for machine learning research [best of the web]. IEEE Signal Process. Mag. 29(6), 141–142 (2012)

    Article  Google Scholar 

  • Di Fabio, B., Ferri, M.: Comparing persistence diagrams through complex vectors. In: International Conference on Image Analysis and Processing, pp. 294–305. Springer (2015)

  • Edelsbrunner, H., Harer, J.: Computational Topology: An Introduction (2010)

  • Fasy, BT., Micka, S., Millman, DL., et al.: Persistence diagrams for efficient simplicial complex reconstruction (2019). arXiv preprint arXiv:1912.12759 1:5

  • Gabrielsson, RB., Nelson, BJ., Dwaraknath, A., et al.: A topology layer for machine learning. In: International Conference on Artificial Intelligence and Statistics, pp. 1553–1563. PMLR (2020)

  • Gameiro, M., Hiraoka, Y., Obayashi, I.: Continuation of point clouds via persistence diagrams. Physica D 334, 118–132 (2016)

    Article  MathSciNet  Google Scholar 

  • Ghrist, R.: Barcodes: the persistent topology of data. Bull. Am. Math. Soc. 45(1), 61–75 (2008)

    Article  MathSciNet  Google Scholar 

  • Ghrist, R., Levanger, R., Mai, H.: Persistent homology and Euler integral transforms. J. Appl. Comput. Topol. 2(1), 55–60 (2018)

    Article  MathSciNet  Google Scholar 

  • Giunti, B., Houry, G., Kerber, M.: Average Complexity of Matrix Reduction for Clique Filtrations (2021). arXiv preprint arXiv:2111.02125

  • Golovin, A.A., Davis, S.H.: Effect of anisotropy on morphological instability in the freezing of a hypercooled melt. Physica D 116(3–4), 363–391 (1998)

    Article  MathSciNet  Google Scholar 

  • Hewitt, E., Ross, K.A.: Abstract Harmonic Analysis: Volume I Structure of Topological Groups Integration Theory Group Representations, vol. 115. Springer Science & Business Media, Berlin (2012)

    Google Scholar 

  • Hiraoka, Y., Nakamura, T., Hirata, A., et al.: Hierarchical structures of amorphous solids characterized by persistent homology. Proc. Natl. Acad. Sci. 113(26), 7035–7040 (2016)

    Article  Google Scholar 

  • Hu, X., Li, F., Samaras, D., et al.: Topology-preserving deep image segmentation. Adv. Neural Inf. Process. Syst. 32 (2019)

  • Jiang, Q., Kurtek, S., Needham, T.: The weighted Euler curve transform for shape and image analysis. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pp. 844–845 (2020)

  • Kaczynski, T., Mischaikow, K.M., Mrozek, M.: Computational Homology, vol. 3. Springer, Berlin (2004)

    Book  Google Scholar 

  • Khramtsova, E., Zuccon, G., Wang, X., et al.: Rethinking Persistent Homology for Visual Recognition (2022). arXiv e-prints arXiv: 2207.04220

  • Kim, K., Kim, J., Zaheer, M., et al.: PLLay: efficient topological layer based on persistent landscapes. Adv. Neural Inf. Process. Syst. 33, 15965–15977 (2020)

    Google Scholar 

  • Kipf, TN., Welling, M.: Semi-Supervised Classification with Graph Convolutional Networks (2016). arXiv preprint arXiv:1609.02907

  • Lacombe, T., Cuturi, M., Oudot, S.: Large scale computation of means and clusters for persistence diagrams using optimal transport. Adv. Neural Inf. Process. Syst. 31 (2018)

  • Leygonie, J., Henselman-Petrusek, G.: Algorithmic Reconstruction of the Fiber of Persistent Homology on Cell Complexes (2021). arXiv preprint arXiv:2110.14676

  • Leygonie, J., Tillmann, U.: The fiber of persistent homology for simplicial complexes. J. Pure Appl. Algebra 266, 107099 (2022)

    Article  MathSciNet  Google Scholar 

  • Lindenstrauss, W.J.J.: Extensions of Lipschitz maps into a Hilbert space. Contemp. Math. 26(189–206), 2 (1984)

    Google Scholar 

  • Maria, C., Oudot, S., Solomon, E.: Intrinsic topological transforms via the distance kernel embedding (2019). arXiv preprint arXiv:1912.02225

  • Milosavljević, N., Morozov, D., Skraba, P.: Zigzag persistent homology in matrix multiplication time. In: Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry, pp. 216–225 (2011)

  • Monod, A., Kalisnik, S., Patino-Galindo, J.Á., et al.: Tropical sufficient statistics for persistent homology. SIAM J. Appl. Algebra Geom. 3(2), 337–371 (2019)

    Article  MathSciNet  Google Scholar 

  • Motta, F.C., Shipman, P.D., Bradley, R.M.: Highly ordered nanoscale surface ripples produced by ion bombardment of binary compounds. J. Phys. D Appl. Phys. 45(12), 122001 (2012)

    Article  Google Scholar 

  • Nazarpour, K., Chen, M.: Handwritten Chinese Numbers (2017). https://doi.org/10.17634/137930-3. https://data.ncl.ac.uk/articles/dataset/Handwritten_Chinese_Numbers/10280831

  • Otter, N., Porter, M.A., Tillmann, U., et al.: A roadmap for the computation of persistent homology. EPJ Data Sci. 6, 1–38 (2017)

    Article  Google Scholar 

  • Oudot, S., Solomon, E.: Barcode Embeddings for Metric Graphs (2017). arXiv preprint arXiv:1712.03630

  • Oudot, S., Solomon, E.: Inverse problems in topological persistence. In: Topological Data Analysis, pp. 405–433. Springer (2020)

  • Oudot, S.Y.: Persistence Theory: From Quiver Representations to Data Analysis, vol. 209. American Mathematical Society Providence, Providence (2015)

    Book  Google Scholar 

  • Oudot, S.Y.: Persistence Theory: From Quiver Representations to Data Analysis, vol. 209. American Mathematical Society, Providence (2017)

    Google Scholar 

  • Pham, K., Le, K., Ho, N., et al.: On unbalanced optimal transport: an analysis of Sinkhorn algorithm. In: International Conference on Machine Learning, pp. 7673–7682. PMLR (2020)

  • Poulenard, A., Skraba, P., Ovsjanikov, M.: Topological function optimization for continuous shape matching. In: Computer Graphics Forum, pp. 13–25. Wiley Online Library (2018)

  • Russakovsky, O., Deng, J., Su, H., et al.: Imagenet large scale visual recognition challenge. Int. J. Comput. Vis. 115(3), 211–252 (2015)

    Article  MathSciNet  Google Scholar 

  • Skraba, P., Turner, K.: Wasserstein Stability for Persistence Diagrams (2020). arXiv preprint arXiv:2006.16824

  • Solomon, E., Wagner, A., Bendich, P.: From Geometry to Topology: Inverse Theorems for Distributed Persistence (2021a). arXiv preprint arXiv:2101.12288

  • Solomon, E., Wagner, A., Bendich, P.: From geometry to topology: inverse theorems for distributed persistence. In: Goaoc, X., Kerber, M. (eds.) 38th International Symposium on Computational Geometry (SoCG 2022), Leibniz International Proceedings in Informatics (LIPIcs), vol. 224, pp 61:1–61:16. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2022). https://doi.org/10.4230/LIPIcs.SoCG.2022.61, https://drops.dagstuhl.de/opus/volltexte/2022/16069

  • Solomon, Y., Wagner, A., Bendich, P.: A fast and robust method for global topological functional optimization. In: International Conference on Artificial Intelligence and Statistics, PMLR, pp. 109–117 (2021b)

  • Suzuki, A., Miyazawa, M., Minto, J.M., et al.: Flow estimation solely from image data through persistent homology analysis. Sci. Rep. 11(1), 1–13 (2021)

    Article  Google Scholar 

  • Tauzin, G., Lupo, U., Tunstall, L., et al.: giotto-tda: a topological data analysis toolkit for machine learning and data exploration. J. Mach. Learn. Res. 22(39), 1–6 (2021)

    MathSciNet  Google Scholar 

  • Turner, K., Mukherjee, S., Boyer, D.M.: Persistent homology transform for modeling shapes and surfaces. Inf Inference A J. IMA 3(4), 310–344 (2014)

    Article  MathSciNet  Google Scholar 

  • Villain, J.: Continuum models of crystal growth from atomic beams with and without desorption. J. Phys. I 1(1), 19–42 (1991)

    Google Scholar 

  • Villani, C.: Topics in Optimal Transportation, vol. 58. American Mathematical Society, Providence (2021)

    Google Scholar 

  • Wagner, A.: Nonembeddability of persistence diagrams with p> 2 Wasserstein metric. Proc. Am. Math. Soc. 149(6), 2673–2677 (2021)

    Article  MathSciNet  Google Scholar 

  • Wolf, D.E.: Kinetic roughening of vicinal surfaces. Phys. Rev. Lett. 67(13), 1783 (1991)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Mathematics, Duke University, Durham, NC, USA

    Yitzchak Elchanan Solomon & Paul Bendich

  2. Geometric Data Analytics, Durham, NC, USA

    Paul Bendich

Authors
  1. Yitzchak Elchanan Solomon
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Paul Bendich
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yitzchak Elchanan Solomon.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The authors were partially supported by the Air Force Office of Scientific Research under the grant “Geometry and Topology for Data Analysis and Fusion”, AFOSR FA9550-18-1-0266. They would also like to extend their thanks to Alexander Wagner, for helpful conversations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Solomon, Y.E., Bendich, P. Convolutional persistence transforms. J Appl. and Comput. Topology 8, 1981–2013 (2024). https://doi.org/10.1007/s41468-024-00164-x

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s41468-024-00164-x

Keywords

Mathematics Subject Classification

Search

Navigation