Search for: All records

Graphs in metric spaces appear in a wide range of data sets, and there is a large body of work focused on comparing, matching, or analyzing collections of graphs in different ambient spaces. In this survey, we provide an overview of a diverse collection of distance measures that can be defined on the set of finite graphs immersed (and in some cases, embedded) in a metric space. For each of the distance measures, we recall their definitions and investigate which of the properties of a metric they satisfy. Furthermore we compare the distance measures based on these properties and discuss their computational complexity.

Persistent homology is a tool that can be employed to summarize the shape of data by quantifying homological features. When the data is an object in R d , the (augmented) persistent homology transform ((A)PHT) is a family of persistence diagrams, parameterized by directions in the ambient space. A recent advance in understanding the PHT used the framework of reconstruction in order to find finite a set of directions to faithfully represent the shape, a result that is of both theoretical and practical interest. In this paper, we improve upon this result and present an improved algorithm for graph— and, more generally one-skeleton—reconstruction. The improvement comes in reconstructing the edges, where we use a radial binary (multi-)search. The binary search employed takes advantage of the fact that the edges can be ordered radially with respect to a reference plane, a feature unique to graphs.

Since its introduction in the mid-1990s, DBSCAN has become one of the most widely used clustering algorithms. However, one of the steps in DBSCAN is to perform a range query, a task that is difficult in many spaces, including the space of persistence diagrams. In this paper, we introduce a spanner into the DBSCAN algorithm to facilitate range queries in such spaces. We provide a proof-of-concept implementation, and study time and clustering performance for two data sets of persistence diagrams.

In July 2021, Computer Science (CS) standards were officially added as a subject area within the K-12 Montana content standards. However, due to a lack of professional development and pre-service preparation in CS, schools and teachers in Montana are underprepared to implement these standards. Montana is also a unique state, since American Indian education is mandated by the state constitution in what is known as the Indian Education for All Act. We are developing elementary and middle school units and teacher training materials that simultaneously address CS, Indian Education, and other Montana content standards. In this paper, we present a unit for fourth through sixth grades using a participatory design approach. Through physical computing, students create a visual narrative of their own stories inspired by ledger art, an American Indian art medium for recording lived experiences. We discuss the affordances and challenges of an integrated approach to CS teaching and learning in elementary and middle schools in Montana.

We consider the topological and geometric reconstruction of a geodesic subspace of [Formula: see text] both from the Čech and Vietoris-Rips filtrations on a finite, Hausdorff-close, Euclidean sample. Our reconstruction technique leverages the intrinsic length metric induced by the geodesics on the subspace. We consider the distortion and convexity radius as our sampling parameters for the reconstruction problem. For a geodesic subspace with finite distortion and positive convexity radius, we guarantee a correct computation of its homotopy and homology groups from the sample. This technique provides alternative sampling conditions to the existing and commonly used conditions based on weak feature size and [Formula: see text]–reach, and performs better under certain types of perturbations of the geodesic subspace. For geodesic subspaces of [Formula: see text], we also devise an algorithm to output a homotopy equivalent geometric complex that has a very small Hausdorff distance to the unknown underlying space.

We examine topological properties of spaces of paths and graphs mapped to $\R^d$ under the Fr\'echet distance. We show that these spaces are path-connected if the map is either continuous or an immersion. If the map is an embedding, we show that the space of paths is path-connected, while the space of graphs only maintains this property in dimensions four or higher.

While collapsibility of CW complexes dates back to the 1930s, collapsibility of directed Euclidean cubical complexes has not been well studied to date. The classical definition of collapsibility involves certain conditions on pairs of cells of the complex. The direction of the space can be taken into account by requiring that the past links of vertices remain homotopy equivalent after collapsing. We call this type of collapse a link-preserving directed collapse. In the undirected setting, pairs of cells are removed that create a deformation retract. In the directed setting, topological properties---in particular, properties of spaces of directed paths---are not always preserved. In this paper, we give computationally simple conditions for preserving the topology of past links. Furthermore, we give conditions for when link-preserving directed collapses preserve the contractability and connectedness of spaces of directed paths. Throughout, we provide illustrative examples.

Persistence diagrams have been widely used to quantify the underlying features of filtered topological spaces in data visualization. In many applications, computing distances between diagrams is essential; however, computing these distances has been challenging due to the computational cost. In this paper, we propose a persistence diagram hashing framework that learns a binary code representation of persistence diagrams, which allows for fast computation of distances. This framework is built upon a generative adversarial network (GAN) with a diagram distance loss function to steer the learning process. Instead of using standard representations, we hash diagrams into binary codes, which have natural advantages in large-scale tasks. The training of this model is domain-oblivious in that it can be computed purely from synthetic, randomly created diagrams. As a consequence, our proposed method is directly applicable to various datasets without the need for retraining the model. These binary codes, when compared using fast Hamming distance, better maintain topological similarity properties between datasets than other vectorized representations. To evaluate this method, we apply our framework to the problem of diagram clustering and we compare the quality and performance of our approach to the state-of-the-art. In addition, we show the scalability of our approach on amore »dataset with 10k persistence diagrams, which is not possible with current techniques. Moreover, our experimental results demonstrate that our method is significantly faster with the potential of less memory usage, while retaining comparable or better quality comparisons.« less

The persistence diagram (PD) is an important tool in topological data analysis for encoding an abstract representation of the homology of a shape at different scales. Different vectorizations of PD summary are commonly used in machine learning applications, however distances between vectorized persistence summaries may differ greatly from the distances between the original PDs. Surprisingly, no research has been carried out in this area before. In this work we compare distances between PDs and between different commonly used vectorizations. Our results give new insights into comparing vectorized persistence summaries and can be used to design better feature-based learning models based on PDs