More Like this

1. The Fréchet Mean of Inhomogeneous Random Graphs

   https://doi.org/10.1007/978-3-030-93409-5_18  

   Meyer, Francois G. ( January 2022 , Complex Networks & Their Applications X)

   Benito, Rosa Maria ; Cherifi, Chantal ; Cherifi, Hocine ; Moro, Esteban ; Rocha, Luis M. (Ed.)

   To characterize the “average” of a set of graphs, one can compute the sample Fr ́echet mean. We prove the following result: if we use the Hamming distance to compute distances between graphs, then the Fr ́echet mean of an ensemble of inhomogeneous random graphs is obtained by thresholding the expected adjacency matrix: an edge exists between the vertices i and j in the Fr ́echet mean graph if and only if the corresponding entry of the expected adjacency matrix is greater than 1/2. We prove that the result also holds for the sample Fr ́echet mean when the expected adjacency matrix is replaced with the sample mean adjacency matrix. This novel theoretical result has some significant practical consequences; for instance, the Fr ́echet mean of an ensemble of sparse inhomogeneous random graphs is the empty graph. 

   more » « less
2. Path-Connectivity of Fréchet Spaces of Graphs

   Chambers, Erin ; Fasy, Brittany Terese ; Holmgren, Benjamin ; Majhi, Sushovan ; Wenk, Carola ( January 2022 , Young Researcher's Forum (CG Week))

   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. 

   more » « less
3. Theoretical analysis and computation of the sample Fréchet mean of sets of large graphs for various metrics

   Daniel Ferguson and François G. Meyer ( March 2023 , Information and inference)

   To characterize the location (mean, median) of a set of graphs, one needs a notion of centrality that has been adapted to metric spaces. A standard approach is to consider the Fréchet mean. In practice, computing the Fréchet mean for sets of large graphs presents many computational issues. In this work, we suggest a method that may be used to compute the Fréchet mean for sets of graphs which is metric independent. We show that the technique proposed can be used to determine the Fréchet mean when considering the Hamming distance or a distance defined by the difference between the spectra of the adjacency matrices of the graphs. 

   more » « less
4. Theoretical analysis and computation of the sample Fréchet mean of sets of large graphs for various metrics

   https://doi.org/10.1093/imaiai/iaad002  

   Ferguson, Daniel ; Meyer, François G. ( March 2023 , Information and Inference: A Journal of the IMA)

   To characterize the location (mean, median) of a set of graphs, one needs a notion of centrality that has been adapted to metric spaces. A standard approach is to consider the Fréchet mean. In practice, computing the Fréchet mean for sets of large graphs presents many computational issues. In this work, we suggest a method that may be used to compute the Fréchet mean for sets of graphs which is metric independent. We show that the technique proposed can be used to determine the Fréchet mean when considering the Hamming distance or a distance defined by the difference between the spectra of the adjacency matrices of the graphs.

    

   more » « less
5. Shape and structure preserving differential privacy.

   C. Soto, K. Bharath ( October 2022 , Advances in Neural Information Processing Systems.)

   It is common for data structures such as images and shapes of 2D objects to be represented as points on a manifold. The utility of a mechanism to produce sanitized differentially private estimates from such data is intimately linked to how compatible it is with the underlying structure and geometry of the space. In particular, as recently shown, utility of the Laplace mechanism on a positively curved manifold, such as Kendall’s 2D shape space, is significantly influenced by the curvature. Focusing on the problem of sanitizing the Fr\'echet mean of a sample of points on a manifold, we exploit the characterization of the mean as the minimizer of an objective function comprised of the sum of squared distances and develop a K-norm gradient mechanism on Riemannian manifolds that favors values that produce gradients close to the the zero of the objective function. For the case of positively curved manifolds, we describe how using the gradient of the squared distance function offers better control over sensitivity than the Laplace mechanism, and demonstrate this numerically on a dataset of shapes of corpus callosa. Further illustrations of the mechanism’s utility on a sphere and the manifold of symmetric positive definite matrices are also presented. 

   more » « less