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.

 

The Fréchet distance is often used to measure distances between paths, with applications in areas ranging from map matching to GPS trajectory analysis to hand- writing recognition. More recently, the Fréchet distance has been generalized to a distance between two copies of the same graph embedded or immersed in a metric space; this more general setting opens up a wide range of more complex applications in graph analysis. In this paper, we initiate a study of some of the fundamental topological properties of spaces of paths and of graphs mapped to R^n under the Fréchet distance, in an eort to lay the theoretical groundwork for understanding how these distances can be used in practice. In particular, we prove whether or not these spaces, and the metric balls therein, are path-connected. 

In 2021, National Science Foundation (NSF) Computer and Information Science and Engineering (CISE) directorate implemented a Broadening Participation in Computing (BPC) plan requirement for all medium and larger research proposals in Core, CPS, and SaTC. This panel comprises faculty and administrators from US computing departments who have participated in the writing of Departmental or Project BPC plans, two in response to NSF’s encouragement and one prior. Panelists represent a range of institutions as well as departmental awareness of BPC prior to writing their plans. Regardless of where they or their departments lie in the spectrum of knowing about and implementing BPC activities, and regardless of the current demographic makeup of the students in their major, they all encountered challenges as they wrote their plans. They all also experienced successes, not the least of which is that they succeeded in getting a plan written in accordance with the current guidelines. With the support of a moderator, the three panelists will share their experiences developing BPC plans with the audience, offering lessons learned and tips for overcoming common challenges. Audience members will also receive helpful links and handouts to facilitate the writing of their own departmental or project plans 

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. 

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. 

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. 

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