More Like this

1. Metric and Path-Connectedness Properties of the Fréchet Distance for Paths and Graphs

   Erin Chambers; Fasy, Brittany Terese; Holmgren, Benjamin; Majhi, Sushovan; Wenk, Carola (July 2023, CCCG)

   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. 

   more » « less
2. Evaluating generative networks using Gaussian mixtures of image features

   https://doi.org/10.1109/WACV56688.2023.00036  

   Luzi, Lorenzo; Marrero, Carlos Ortiz; Wynar, Nile; Baraniuk, Richard G.; Henry, Michael J. (February 2023, 2023 IEEE/CVF Winter Conference on Applications of Computer Vision (WACV))

   We develop a measure for evaluating the performance of generative networks given two sets of images. A popular performance measure currently used to do this is the Fréchet Inception Distance (FID). FID assumes that images featurized using the penultimate layer of Inception-v3 follow a Gaussian distribution, an assumption which cannot be violated if we wish to use FID as a metric. However, we show that Inception-v3 features of the ImageNet dataset are not Gaussian; in particular, every single marginal is not Gaussian. To remedy this problem, we model the featurized images using Gaussian mixture models (GMMs) and compute the 2-Wasserstein distance restricted to GMMs. We define a performance measure, which we call WaM, on two sets of images by using Inception-v3 (or another classifier) to featurize the images, estimate two GMMs, and use the restricted 2-Wasserstein distance to compare the GMMs. We experimentally show the advantages of WaM over FID, including how FID is more sensitive than WaM to imperceptible image perturbations. By modelling the non-Gaussian features obtained from Inception-v3 as GMMs and using a GMM metric, we can more accurately evaluate generative network performance. 

   more » « less
3. The effect of genome graph expressiveness on the discrepancy between genome graph distance and string set distance

   Qiu, Yutong; Kingsford, Carl (January 2022, ISCB ISMB 2022)

   Motivation: Intra-sample heterogeneity describes the phenomenon where a genomic sample contains a diverse set of genomic sequences. In practice, the true string sets in a sample are often unknown due to limitations in sequencing technology. In order to compare heterogeneous samples, genome graphs can be used to represent such sets of strings. However, a genome graph is generally able to represent a string set universe that contains multiple sets of strings in addition to the true string set. This difference between genome graphs and string sets is not well characterized. As a result, a distance metric between genome graphs may not match the distance between true string sets. Results: We extend a genome graph distance metric, Graph Traversal Edit Distance (GTED) proposed by Ebrahimpour Boroojeny et al., to FGTED to model the distance between heterogeneous string sets and show that GTED and FGTED always underestimate the Earth Mover’s Edit Distance (EMED) between string sets. We introduce the notion of string set universe diameter of a genome graph. Using the diameter, we are able to upper-bound the deviation of FGTED from EMED and to improve FGTED so that it reduces the average error in empirically estimating the similarity between true string sets. On simulated T-cell receptor sequences and actual Hepatitis B virus genomes, we show that the diameter-corrected FGTED reduces the average deviation of the estimated distance from the true string set distances by more than 250%. Availability and implementation: Data and source code for reproducing the experiments are available at: https:// github.com/Kingsford-Group/gtedemedtest/. 

   more » « less
4. Computation of the Sample Frechet Mean for Sets of Large Graphs with Applications to Regression

   Ferguson, Daniel; Meyer, Francois G. (June 2022, SIAM International Conference on Data Mining (SDM 2022))

   Banerjee, Arindam; Zhou, Zhi-Hua (Ed.)

   To characterize the location (mean, median) of a set of graphs, one needs a notion of centrality that is adapted to metric spaces, since graph sets are not Euclidean spaces. A standard approach is to consider the Fr ́echet mean. In this work, we equip a set of graph with the pseudometric defined by the l2 norm between the eigenvalues of their respective adjacency matrix. Unlike the edit distance, this pseudometric reveals structural changes at multiple scales, and is well adapted to studying various statistical problems for graph-valued data. We describe an algorithm to compute an approximation to the sample Fr ́echet mean of a set of undirected unweighted graphs with a fixed size using this pseudometric. 

   more » « less
5. Distances Between Immersed Graphs: Metric Properties

   https://doi.org/10.1007/s44007-022-00037-8  

   Buchin, Maike; Chambers, Erin; Fang, Pan; Fasy, Brittany Terese; Gasparovic, Ellen; Munch, Elizabeth; Wenk, Carola (January 2023, La Matematica)

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

   more » « less