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.
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.
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