Stratified space learning: Reconstructing embedded graphs

Y. Bokor*, D. Grixti-Cheng, M. Hegland, S. Roberts, K. Turner

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    1 Citation (Scopus)

    Abstract

    Many data-rich industries are interested in the efficient discovery and modelling of structures under-lying large data sets, as it allows for the fast triage and dimension reduction of large volumes of data embedded in high dimensional spaces. The modelling of these underlying structures is also beneficial for the creation of simulated data that better represents real data. In particular, for systems testing in cases where the use of real data streams might prove impractical or otherwise undesirable. We seek to discover and model the structure by combining methods from topological data analysis with numerical modelling. As a first step in combining these two areas, we examine the recovery a linearly embedded graph jGj given only a noisy point cloud sample X of jGj. An abstract graph G consists of two sets: A set of vertices V and a set of edges E. An embedded graph jGj in n dimensions is a geometric realisation of an abstract graph obtained by assigning to each vertex a unique coordinate vector in Rn and then each edge is the line segment between the coordinate vectors of the corresponding vertices. Given an embedded graph jGj-Rn, a point cloud sample of jGj consists of a finite collection of points in Rn sampled from jGj, potentially with noisy perturbations. We will suppose that this sample has bounded noise of-and is sufficiently sampled so every point in jGj is within-of some sample. Such a sample is called an-sample. We can view this as a semiparametric model. Once the abstract graph is fixed we have a parametric model where the parameters are the locations of the vertices. In order to guarantee correctness of our algorithm, we will need to make some reasonable geometric assumptions on the embedded graph. To learn the embedded graph jGj, we first learn the structure of the abstract graph G. We do this by assigning a dimension of either 0 or 1 to each x 2 X (depending on local topological structure) and then cluster points into groups representing embedded vertices or edges. Using local topological structure, we then assign to each abstract edge cluster a pair of abstract vertex clusters, to obtain the incidence relations of the abstract graph. Finally, we use nonlinear least squares regression to model the embedded graph jGj. The approach presented in this paper relies on topological concepts, such as stratification and local homology, which will be used in future research that will generalise this approach to embeddings on more general structures, in particular stratified spaces. A stratified space X is a topological space with a partition into topological manifolds fXigi2I , called strata, such that for all i and j, Xi \ Xj = ;, and if Xi \ Xj 6= ;, then Xi-Xj . If we are interested in a specific topological structure, we can require that the strata satisfy aditional criteria, so that this structure is constant across each strata. In the case presented in this paper, the vertices of a graph (abstract or embedded) are the 0-strata, and the (open) edges are 1-strata. The authors are unaware of any algorithms which recover both the abstract graph, and model its embedding.

    Original languageEnglish
    Title of host publication23rd International Congress on Modelling and Simulation - Supporting Evidence-Based Decision Making
    Subtitle of host publicationThe Role of Modelling and Simulation, MODSIM 2019
    EditorsS. Elsawah
    PublisherModelling and Simulation Society of Australia and New Zealand Inc (MSSANZ)
    Pages69-75
    Number of pages7
    ISBN (Electronic)9780975840092
    Publication statusPublished - 2019
    Event23rd International Congress on Modelling and Simulation - Supporting Evidence-Based Decision Making: The Role of Modelling and Simulation, MODSIM 2019 - Canberra, Australia
    Duration: 1 Dec 20196 Dec 2019

    Publication series

    Name23rd International Congress on Modelling and Simulation - Supporting Evidence-Based Decision Making: The Role of Modelling and Simulation, MODSIM 2019

    Conference

    Conference23rd International Congress on Modelling and Simulation - Supporting Evidence-Based Decision Making: The Role of Modelling and Simulation, MODSIM 2019
    Country/TerritoryAustralia
    CityCanberra
    Period1/12/196/12/19

    Fingerprint

    Dive into the research topics of 'Stratified space learning: Reconstructing embedded graphs'. Together they form a unique fingerprint.

    Cite this