Theoretical analysis and computation of the sample Frechet mean for sets of large graphs based on spectral information

• URL: http://arxiv.org/abs/2201.05923v1
• Date: Sat, 15 Jan 2022 20:53:29 GMT
• Title: Theoretical analysis and computation of the sample Frechet mean for sets of large graphs based on spectral information
• Authors: Daniel Ferguson and Francois G. Meyer
• Abstract summary: We equip a set of graphs with the pseudometric defined by the norm between the eigenvalues of their respective adjacency matrix. Unlike the edit distance, this pseudometric reveals structural changes at multiple scales. We describe an algorithm to compute an approximation to the sample Frechet mean of a set of undirected unweighted graphs with a fixed size.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 Frechet mean. In this work, we equip a set of graphs with the pseudometric defined by the 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 Frechet mean of a set of undirected unweighted graphs with a fixed size using this pseudometric.

Related papers

• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure. We introduce a new class of manifold, named soft manifold, that can solve this situation. Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
  arXiv  Detail & Related papers  (2023-11-29T12:48:33Z)
• Graph Fourier MMD for Signals on Graphs [67.68356461123219]
  We propose a novel distance between distributions and signals on graphs. GFMMD is defined via an optimal witness function that is both smooth on the graph and maximizes difference in expectation. We showcase it on graph benchmark datasets as well as on single cell RNA-sequencing data analysis.
  arXiv  Detail & Related papers  (2023-06-05T00:01:17Z)
• Bures-Wasserstein Means of Graphs [60.42414991820453]
  We propose a novel framework for defining a graph mean via embeddings in the space of smooth graph signal distributions. By finding a mean in this embedding space, we can recover a mean graph that preserves structural information. We establish the existence and uniqueness of the novel graph mean, and provide an iterative algorithm for computing it.
  arXiv  Detail & Related papers  (2023-05-31T11:04:53Z)
• Geometric Scattering on Measure Spaces [12.0756034112778]
  We introduce a general, unified model for geometric scattering on measure spaces. We consider finite measure spaces that are obtained from randomly sampling an unknown manifold. We propose two methods for constructing a data-driven graph on which the associated graph scattering transform approximates the scattering transform on the underlying manifold.
  arXiv  Detail & Related papers  (2022-08-17T22:40:09Z)
• Probability density estimation for sets of large graphs with respect to spectral information using stochastic block models [0.0]
  In this work, we equip the set of graphs with the pseudo-metric defined by the $ell$ norm between the eigenvalues of the respective adjacency matrices. We use this pseudo metric and the respective sample moments of a graph valued data set to infer the parameters of a distribution $hatmu$ and interpret this distribution as an approximation of $mu$.
  arXiv  Detail & Related papers  (2022-07-05T16:53:22Z)
• 3D Shape Registration Using Spectral Graph Embedding and Probabilistic Matching [24.41451985857662]
  We address the problem of 3D shape registration and we propose a novel technique based on spectral graph theory and probabilistic matching. The main contribution of this chapter is to extend the spectral graph matching methods to very large graphs by combining spectral graph matching with Laplacian embedding.
  arXiv  Detail & Related papers  (2021-06-21T15:02:31Z)
• Approximate Fr\'echet Mean for Data Sets of Sparse Graphs [0.0]
  In this work, we equip a set of graph with the pseudometric matrix defined by the $ell$ norm between the eigenvalues of their respective adjacency. Unlike the edit distance, this pseudometric reveals structural changes at multiple scales, and is well adapted to studying various statistical problems on sets of graphs. We describe an algorithm to compute an approximation to the Fr'echet mean of a set of undirected unweighted graphs with a fixed size.
  arXiv  Detail & Related papers  (2021-05-10T01:13:25Z)
• Posterior Consistency of Semi-Supervised Regression on Graphs [14.65047105712853]
  Graph-based semi-supervised regression (SSR) is the problem of estimating the value of a function on a weighted graph from its values (labels) on a small subset of the vertices. This paper is concerned with the consistency of SSR in the context of classification, in the setting where the labels have small noise and the underlying graph weighting is consistent with well-clustered nodes. We present a Bayesian formulation of SSR in which the weighted graph defines a Gaussian prior, using a graph Laplacian, and the labeled data defines a likelihood.
  arXiv  Detail & Related papers  (2020-07-25T00:00:19Z)
• Offline detection of change-points in the mean for stationary graph signals [55.98760097296213]
  We propose an offline method that relies on the concept of graph signal stationarity. Our detector comes with a proof of a non-asymptotic inequality oracle.
  arXiv  Detail & Related papers  (2020-06-18T15:51:38Z)
• Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants [94.46276668068327]
  In [1], an ensemble of randomly projected linear discriminants is used to classify datasets. We develop a consistent estimator of the misclassification probability as an alternative to the computationally-costly cross-validation estimator. We also demonstrate the use of our estimator for tuning the projection dimension on both real and synthetic data.
  arXiv  Detail & Related papers  (2020-04-17T12:47:04Z)
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees [106.91654068632882]
  We consider the bipartite graph and formalize its representation learning problem as a statistical estimation problem of parameters in a semiparametric exponential family distribution. We show that the proposed objective is strongly convex in a neighborhood around the ground truth, so that a gradient descent-based method achieves linear convergence rate. Our estimator is robust to any model misspecification within the exponential family, which is validated in extensive experiments.
  arXiv  Detail & Related papers  (2020-03-02T16:40:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.