Symmetry-driven embedding of networks in hyperbolic space

• URL: http://arxiv.org/abs/2406.10711v1
• Date: Sat, 15 Jun 2024 18:44:02 GMT
• Title: Symmetry-driven embedding of networks in hyperbolic space
• Authors: Simon Lizotte, Jean-Gabriel Young, Antoine Allard,
• Abstract summary: Hyperbolic models can reproduce the heavy-tailed degree distribution, high clustering, and hierarchical structure of empirical networks. Current algorithms for finding the hyperbolic coordinates of networks, however, do not quantify uncertainty in the inferred coordinates. We present BIGUE, a Markov chain Monte Carlo algorithm that samples the posterior distribution of a Bayesian hyperbolic random graph model.
• Score: 0.4779196219827508
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hyperbolic models can reproduce the heavy-tailed degree distribution, high clustering, and hierarchical structure of empirical networks. Current algorithms for finding the hyperbolic coordinates of networks, however, do not quantify uncertainty in the inferred coordinates. We present BIGUE, a Markov chain Monte Carlo (MCMC) algorithm that samples the posterior distribution of a Bayesian hyperbolic random graph model. We show that combining random walk and random cluster transformations significantly improves mixing compared to the commonly used and state-of-the-art dynamic Hamiltonian Monte Carlo algorithm. Using this algorithm, we also provide evidence that the posterior distribution cannot be approximated by a multivariate normal distribution, thereby justifying the use of MCMC to quantify the uncertainty of the inferred parameters.

Related papers

• On Cyclical MCMC Sampling [13.002470980542707]
  We show that cyclical MCMC converges to the desired probability distribution in settings where the Markov kernels used are fast mixing. We also show that cyclical MCMC estimates well the local shape of the target distribution around each mode, even when we do not have convergence to the target.
  arXiv  Detail & Related papers  (2024-03-01T02:20:44Z)
• Reverse Diffusion Monte Carlo [19.35592726471155]
  We propose a novel Monte Carlo sampling algorithm called reverse diffusion Monte Carlo (rdMC) rdMC is distinct from the Markov chain Monte Carlo (MCMC) methods.
  arXiv  Detail & Related papers  (2023-07-05T05:42:03Z)
• 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)
• 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)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• What Are Bayesian Neural Network Posteriors Really Like? [63.950151520585024]
  We show that Hamiltonian Monte Carlo can achieve significant performance gains over standard and deep ensembles. We also show that deep distributions are similarly close to HMC as standard SGLD, and closer than standard variational inference.
  arXiv  Detail & Related papers  (2021-04-29T15:38:46Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  Hybrid Monte Carlo is a powerful Markov Chain Monte Carlo method for sampling from complex continuous distributions. We introduce a new approach based on augmenting Monte Carlo methods with SurVAE Flows to sample from discrete distributions. We demonstrate the efficacy of our algorithm on a range of examples from statistics, computational physics and machine learning, and observe improvements compared to alternative algorithms.
  arXiv  Detail & Related papers  (2021-02-04T02:21:08Z)
• Stacking for Non-mixing Bayesian Computations: The Curse and Blessing of Multimodal Posteriors [8.11978827493967]
  We propose an approach using parallel runs of MCMC, variational, or mode-based inference to hit as many modes as possible. We present theoretical consistency with an example where the stacked inference process approximates the true data. We demonstrate practical implementation in several model families.
  arXiv  Detail & Related papers  (2020-06-22T15:26:59Z)
• A Dynamical Mean-Field Theory for Learning in Restricted Boltzmann Machines [2.8021833233819486]
  We define a message-passing algorithm for computing magnetizations in Boltzmann machines. We prove the global convergence of the algorithm under a stability criterion and compute convergence rates showing excellent agreement with numerical simulations.
  arXiv  Detail & Related papers  (2020-05-04T15:19:31Z)

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.