Learning Networks from Gaussian Graphical Models and Gaussian Free Fields

• URL: http://arxiv.org/abs/2308.02344v1
• Date: Fri, 4 Aug 2023 14:18:39 GMT
• Title: Learning Networks from Gaussian Graphical Models and Gaussian Free Fields
• Authors: Subhro Ghosh, Soumendu Sundar Mukherjee, Hoang-Son Tran, Ujan Gangopadhyay
• Abstract summary: We propose a novel estimator for the weighted network (equivalently, its Laplacian) from repeated measurements of a GFF on the network. We demonstrate the effectiveness of our estimator with concrete recovery guarantees and bounds on the required sample complexity. In the setting of networks growing with sample size, our results show that for Erdos-Renyi random graphs $G(d,p)$ above the connectivity threshold, we demonstrate that network recovery takes place with high probability.
• Score: 2.294014185517203
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the problem of estimating the structure of a weighted network from repeated measurements of a Gaussian Graphical Model (GGM) on the network. In this vein, we consider GGMs whose covariance structures align with the geometry of the weighted network on which they are based. Such GGMs have been of longstanding interest in statistical physics, and are referred to as the Gaussian Free Field (GFF). In recent years, they have attracted considerable interest in the machine learning and theoretical computer science. In this work, we propose a novel estimator for the weighted network (equivalently, its Laplacian) from repeated measurements of a GFF on the network, based on the Fourier analytic properties of the Gaussian distribution. In this pursuit, our approach exploits complex-valued statistics constructed from observed data, that are of interest on their own right. We demonstrate the effectiveness of our estimator with concrete recovery guarantees and bounds on the required sample complexity. In particular, we show that the proposed statistic achieves the parametric rate of estimation for fixed network size. In the setting of networks growing with sample size, our results show that for Erdos-Renyi random graphs $G(d,p)$ above the connectivity threshold, we demonstrate that network recovery takes place with high probability as soon as the sample size $n$ satisfies $n \gg d^4 \log d \cdot p^{-2}$.

Related papers

• A Bayesian Take on Gaussian Process Networks [1.7188280334580197]
  This work implements Monte Carlo and Markov Chain Monte Carlo methods to sample from the posterior distribution of network structures. We show that our method outperforms state-of-the-art algorithms in recovering the graphical structure of the network.
  arXiv  Detail & Related papers  (2023-06-20T08:38:31Z)
• Is Stochastic Gradient Descent Near Optimal? [0.0]
  We show that gradient descent achieves small expected error with a number of samples and total number of queries. This suggests that SGD nearly achieves the information-theoretic sample complexity bounds of Joen & Van Roy (arXiv:2203.00246) in a computationally efficient manner.
  arXiv  Detail & Related papers  (2022-09-18T18:26:43Z)
• On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
  We show that gradient flow converges in direction when labels are determined by the sign of a target network with $r$ neurons. Our result may already hold for mild over- parameterization, where the width is $tildemathcalO(r)$ and independent of the sample size.
  arXiv  Detail & Related papers  (2022-05-18T16:57:10Z)
• Bayesian Structure Learning with Generative Flow Networks [85.84396514570373]
  In Bayesian structure learning, we are interested in inferring a distribution over the directed acyclic graph (DAG) from data. Recently, a class of probabilistic models, called Generative Flow Networks (GFlowNets), have been introduced as a general framework for generative modeling. We show that our approach, called DAG-GFlowNet, provides an accurate approximation of the posterior over DAGs.
  arXiv  Detail & Related papers  (2022-02-28T15:53:10Z)
• Robust Estimation for Nonparametric Families via Generative Adversarial Networks [92.64483100338724]
  We provide a framework for designing Generative Adversarial Networks (GANs) to solve high dimensional robust statistics problems. Our work extend these to robust mean estimation, second moment estimation, and robust linear regression. In terms of techniques, our proposed GAN losses can be viewed as a smoothed and generalized Kolmogorov-Smirnov distance.
  arXiv  Detail & Related papers  (2022-02-02T20:11:33Z)
• Gaussian Mixture Graphical Lasso with Application to Edge Detection in Brain Networks [21.49394455839253]
  This work is inspired by Latent DirichletAllocation (LDA) We propose a novel model called GaussianMixture Graphical Lasso (MGL) MGL learns the proportionsof signals generated by each mixture component and their parameters iteratively via an EM framework.
  arXiv  Detail & Related papers  (2021-01-13T21:15:30Z)
• Fractal Gaussian Networks: A sparse random graph model based on Gaussian Multiplicative Chaos [12.096252285460814]
  We propose a novel network model, called Fractal Gaussian Network (FGN) FGN embodies well-defined and analytically tractable fractal structures.
  arXiv  Detail & Related papers  (2020-08-07T08:37:36Z)
• Fitting the Search Space of Weight-sharing NAS with Graph Convolutional Networks [100.14670789581811]
  We train a graph convolutional network to fit the performance of sampled sub-networks. With this strategy, we achieve a higher rank correlation coefficient in the selected set of candidates.
  arXiv  Detail & Related papers  (2020-04-17T19:12:39Z)
• Infinitely Wide Graph Convolutional Networks: Semi-supervised Learning via Gaussian Processes [144.6048446370369]
  Graph convolutional neural networks(GCNs) have recently demonstrated promising results on graph-based semi-supervised classification. We propose a GP regression model via GCNs(GPGC) for graph-based semi-supervised learning. We conduct extensive experiments to evaluate GPGC and demonstrate that it outperforms other state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-02-26T10:02:32Z)
• 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.