Advanced search
1 file | 2.23 MB Add to list

Local topological data analysis to uncover the global structure of data approaching graph-structured topologies

Robin Vandaele (UGent) , Tijl De Bie (UGent) and Yvan Saeys
Author
Organization
Abstract
Gene expression data of differentiating cells, galaxies distributed in space, and earthquake locations, all share a common property: they lie close to a graph-structured topology in their respective spaces [1, 4, 9, 10, 20], referred to as one-dimensional stratified spaces in mathematics. Often, the uncovering of such topologies offers great insight into these data sets. However, methods for dimensionality reduction are clearly inappropriate for this purpose, and also methods from the relatively new field of Topological Data Analysis (TDA) are inappropriate, due to noise sensitivity, computational complexity, or other limitations. In this paper we introduce a new method, termed Local TDA (LTDA), which resolves the issues of pre-existing methods by unveiling (global) graph-structured topologies in data by means of robust and computationally cheap local analyses. Our method rests on a simple graph-theoretic result that enables one to identify isolated, end-, edge- and multifurcation points in the topology underlying the data. It then uses this information to piece together a graph that is homeomorphic to the unknown one-dimensional stratified space underlying the point cloud data. We evaluate our method on a number of artificial and real-life data sets, demonstrating its superior effectiveness, robustness against noise, and scalability. Code related to this paper is available at: https://bitbucket.org/ghentdatascience/gltda-public.

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 2.23 MB

Citation

Please use this url to cite or link to this publication:

MLA
Vandaele, Robin, et al. “Local Topological Data Analysis to Uncover the Global Structure of Data Approaching Graph-Structured Topologies.” Machine Learning and Knowledge Discovery in Databases, edited by Michele Berlingerio et al., vol. 11052, Springer International Publishing, 2019, pp. 19–36.
APA
Vandaele, R., De Bie, T., & Saeys, Y. (2019). Local topological data analysis to uncover the global structure of data approaching graph-structured topologies. In M. Berlingerio, F. Bonchi, T. G{\"a}rtner, N. Hurley, & G. Ifrim (Eds.), Machine Learning and Knowledge Discovery in Databases (Vol. 11052, pp. 19–36). Cham: Springer International Publishing.
Chicago author-date
Vandaele, Robin, Tijl De Bie, and Yvan Saeys. 2019. “Local Topological Data Analysis to Uncover the Global Structure of Data Approaching Graph-Structured Topologies.” In Machine Learning and Knowledge Discovery in Databases, edited by Michele Berlingerio, Francesco Bonchi, Thomas G{\"a}rtner, Neil Hurley, and Georgiana Ifrim, 11052:19–36. Cham: Springer International Publishing.
Chicago author-date (all authors)
Vandaele, Robin, Tijl De Bie, and Yvan Saeys. 2019. “Local Topological Data Analysis to Uncover the Global Structure of Data Approaching Graph-Structured Topologies.” In Machine Learning and Knowledge Discovery in Databases, ed by. Michele Berlingerio, Francesco Bonchi, Thomas G{\"a}rtner, Neil Hurley, and Georgiana Ifrim, 11052:19–36. Cham: Springer International Publishing.
Vancouver
1.
Vandaele R, De Bie T, Saeys Y. Local topological data analysis to uncover the global structure of data approaching graph-structured topologies. In: Berlingerio M, Bonchi F, G{\"a}rtner T, Hurley N, Ifrim G, editors. Machine Learning and Knowledge Discovery in Databases. Cham: Springer International Publishing; 2019. p. 19–36.
IEEE
[1]
R. Vandaele, T. De Bie, and Y. Saeys, “Local topological data analysis to uncover the global structure of data approaching graph-structured topologies,” in Machine Learning and Knowledge Discovery in Databases, 2019, vol. 11052, pp. 19–36.
@inproceedings{8592098,
  abstract     = {Gene expression data of differentiating cells, galaxies distributed in space, and earthquake locations, all share a common property: they lie close to a graph-structured topology in their respective spaces [1, 4, 9, 10, 20], referred to as one-dimensional stratified spaces in mathematics. Often, the uncovering of such topologies offers great insight into these data sets. However, methods for dimensionality reduction are clearly inappropriate for this purpose, and also methods from the relatively new field of Topological Data Analysis (TDA) are inappropriate, due to noise sensitivity, computational complexity, or other limitations. In this paper we introduce a new method, termed Local TDA (LTDA), which resolves the issues of pre-existing methods by unveiling (global) graph-structured topologies in data by means of robust and computationally cheap local analyses. Our method rests on a simple graph-theoretic result that enables one to identify isolated, end-, edge- and multifurcation points in the topology underlying the data. It then uses this information to piece together a graph that is homeomorphic to the unknown one-dimensional stratified space underlying the point cloud data. We evaluate our method on a number of artificial and real-life data sets, demonstrating its superior effectiveness, robustness against noise, and scalability. Code related to this paper is available at: https://bitbucket.org/ghentdatascience/gltda-public.},
  author       = {Vandaele, Robin and De Bie, Tijl and Saeys, Yvan},
  booktitle    = {Machine Learning and Knowledge Discovery in Databases},
  editor       = {Berlingerio, Michele and Bonchi, Francesco and G{\"a}rtner, Thomas and Hurley, Neil and Ifrim, Georgiana},
  isbn         = {9783030109271},
  language     = {eng},
  pages        = {19--36},
  publisher    = {Springer International Publishing},
  title        = {Local topological data analysis to uncover the global structure of data approaching graph-structured topologies},
  url          = {http://dx.doi.org/10.1007/978-3-030-10928-8_2},
  volume       = {11052},
  year         = {2019},
}

Altmetric
View in Altmetric