Stratified Space Learning: Reconstructing Embedded Graphs

Yossi Bokor, Daniel Grixti-Cheng, Markus Hegland, Stephen Roberts, Katharine Turner

Abstract

Many data-rich industries are interested in the efficient discovery and modelling of structures underlying 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 of the abstract graph $G$ structure, and model a linear embedding $|G|$ given only a noisy point cloud sample $X$ of $|G|$.

Introduction

In fields ranging from biology to sensor networks, datasets often appear as high-dimensional "clouds" of points. These points are rarely random; they typically reside on underlying lower-dimensional structures, such as road networks or molecular skeletons. The challenge of "structure recovery" involves identifying the underlying blueprint from a noisy $\epsilon$-sample. This paper specifically addresses the reconstruction of embedded graphs—structures composed of 0D vertices and 1D edges. Traditional methods often struggle to distinguish sharp corners (degree-2 vertices) from straight lines (edges) or fail to provide a clean mathematical model of the embedding.

Methodology

The proposed approach utilizes a two-phase pipeline that transitions from qualitative topology to quantitative geometry, treating the graph as a "stratified space"—a collection of manifolds (edges and vertices) glued together.

1. Topological Classification

The algorithm first determines if a point is near an edge or a vertex using local homology. In an ideal graph, a sphere around an edge point intersects the graph twice, while a sphere around a vertex of degree $k$ intersects it $k$ times. To handle noise, the authors implement an annulus trick, using a thick ring to count connected components of data points.

Local homology analysis using the annulus trick and angle test to classify points as vertices or edges.

To further distinguish between a straight edge and a "corner" (a degree-2 vertex), the algorithm performs an angle test. If the angle between components in the annulus is sharp, the point is labeled a vertex (0-strata); if it is nearly straight, it is labeled an edge (1-strata).

2. Numerical Modeling

After clustering points into vertex and edge groups, the algorithm constructs an abstract graph. It then employs Nonlinear Least Squares regression to determine the optimal spatial coordinates for the vertices that best fit the original noisy point cloud. This ensures that the topology informs the geometry, simplifying the optimization process.

Results and Discussion

The algorithm was evaluated using synthetic datasets in both $\mathbb{R}^2$ and $\mathbb{R}^3$ to demonstrate scalability across ambient dimensions. The primary test case involved a "bow-tie" graph with 5 vertices and 4 edges.

Reconstruction results in 2D: (Left) noisy cloud with fitted graph, (Middle) point partitioning into clusters, (Right) reconstructed graph vs. ground truth.

Simulations confirmed that the algorithm successfully partitions noisy point clouds into distinct clusters, correctly identifies abstract connectivity, and produces a reconstructed linear graph that closely matches the ground truth.

Limitations and Future Work

While effective, the current model assumes linear embeddings (straight edges). Future research will aim to expand this to piecewise linear or curved structures. Additionally, the authors noted a "vertex drift" bias, where vertices slightly migrate toward regions with higher edge density; correcting this bias is a priority for future iterations. Ultimately, the goal is to apply this stratified space learning framework to more complex manifolds, such as surfaces and higher-dimensional structures.

Summary updated

Abstract

Many data-rich industries are interested in the efficient discovery and modelling of structures underlying 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 of the abstract graph $G$ structure, and model a linear embedding $|G|$ given only a noisy point cloud sample $X$ of $|G|$.
BibTeX
@misc{bokor2019stratified,
  author = {Yossi Bokor and Daniel Grixti-Cheng and Markus Hegland and Stephen Roberts and Katharine Turner},
  title = {{Stratified Space Learning: Reconstructing Embedded Graphs}},
  year = {2019},
  eprint = {1909.12474},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.12474},
}

Loading related content...

Figure