Probability density estimation for sets of large graphs with respect to spectral information using stochastic block models

• URL: http://arxiv.org/abs/2207.02168v1
• Date: Tue, 5 Jul 2022 16:53:22 GMT
• Title: Probability density estimation for sets of large graphs with respect to spectral information using stochastic block models
• Authors: Daniel Ferguson and Fran\c{c}ois G. Meyer
• Abstract summary: 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$.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: For graph-valued data sampled iid from a distribution $\mu$, the sample moments are computed with respect to a choice of metric. In this work, we equip the set of graphs with the pseudo-metric defined by the $\ell_2$ 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 $\hat{\mu}$ and interpret this distribution as an approximation of $\mu$. We verify experimentally that complex distributions $\mu$ can be approximated well taking this approach.

Related papers

• Compressive Recovery of Sparse Precision Matrices [5.557600489035657]
  We consider the problem of learning a graph modeling the statistical relations of the $d$ variables from a dataset with $n$ samples $X in mathbbRn times d$. We show that it is possible to estimate it from a sketch of size $m=Omegaleft((d+2k)log(d)right)$ where $k$ is the maximal number of edges of the underlying graph. We investigate the possibility of achieving practical recovery with an iterative algorithm based on the graphical lasso, viewed as a specific denoiser.
  arXiv  Detail & Related papers  (2023-11-08T13:29:08Z)
• On the Equivalence of Graph Convolution and Mixup [71.8932383179048]
  This paper investigates the relationship between graph convolution and Mixup techniques. Under two mild conditions, graph convolution can be viewed as a specialized form of Mixup. We establish this equivalence mathematically by demonstrating that graph convolution networks (GCN) and simplified graph convolution (SGC) can be expressed as a form of Mixup.
  arXiv  Detail & Related papers  (2023-09-29T23:09:54Z)
• 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)
• Unsupervised Learning of Sampling Distributions for Particle Filters [80.6716888175925]
  We put forward four methods for learning sampling distributions from observed measurements. Experiments demonstrate that learned sampling distributions exhibit better performance than designed, minimum-degeneracy sampling distributions.
  arXiv  Detail & Related papers  (2023-02-02T15:50:21Z)
• A Robust and Flexible EM Algorithm for Mixtures of Elliptical Distributions with Missing Data [71.9573352891936]
  This paper tackles the problem of missing data imputation for noisy and non-Gaussian data. A new EM algorithm is investigated for mixtures of elliptical distributions with the property of handling potential missing data. Experimental results on synthetic data demonstrate that the proposed algorithm is robust to outliers and can be used with non-Gaussian data.
  arXiv  Detail & Related papers  (2022-01-28T10:01:37Z)
• Theoretical analysis and computation of the sample Frechet mean for sets of large graphs based on spectral information [0.0]
  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.
  arXiv  Detail & Related papers  (2022-01-15T20:53:29Z)
• 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)
• An MCMC Method to Sample from Lattice Distributions [4.4044968357361745]
  We introduce a Markov Chain Monte Carlo algorithm to generate samples from probability distributions supported on a $d$-dimensional lattice $Lambda. We use $pi$ as the proposal distribution and calculate the Metropolis-Hastings acceptance ratio for a well-chosen target distribution.
  arXiv  Detail & Related papers  (2021-01-16T15:01:53Z)
• Lipschitz regularity of graph Laplacians on random data clouds [1.2891210250935146]
  We prove high probability interior and global Lipschitz estimates for solutions of graph Poisson equations. Our results can be used to show that graph Laplacian eigenvectors are, with high probability, essentially Lipschitz regular with constants depending explicitly on their corresponding eigenvalues.
  arXiv  Detail & Related papers  (2020-07-13T20:43:19Z)
• Profile Entropy: A Fundamental Measure for the Learnability and Compressibility of Discrete Distributions [63.60499266361255]
  We show that for samples of discrete distributions, profile entropy is a fundamental measure unifying the concepts of estimation, inference, and compression. Specifically, profile entropy a) determines the speed of estimating the distribution relative to the best natural estimator; b) characterizes the rate of inferring all symmetric properties compared with the best estimator over any label-invariant distribution collection; c) serves as the limit of profile compression.
  arXiv  Detail & Related papers  (2020-02-26T17:49:04Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

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.