Merge-split Markov chain Monte Carlo for community detection

• URL: http://arxiv.org/abs/2003.07070v4
• Date: Mon, 13 Jul 2020 16:45:49 GMT
• Title: Merge-split Markov chain Monte Carlo for community detection
• Authors: Tiago P. Peixoto
• Abstract summary: We present a Markov chain Monte Carlo scheme based on merges and splits of groups that is capable of efficiently sampling from the posterior distribution of network partitions. We demonstrate how schemes based on the move of single nodes between groups systematically fail at correctly sampling from the posterior distribution even on small networks.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We present a Markov chain Monte Carlo scheme based on merges and splits of groups that is capable of efficiently sampling from the posterior distribution of network partitions, defined according to the stochastic block model (SBM). We demonstrate how schemes based on the move of single nodes between groups systematically fail at correctly sampling from the posterior distribution even on small networks, and how our merge-split approach behaves significantly better, and improves the mixing time of the Markov chain by several orders of magnitude in typical cases. We also show how the scheme can be straightforwardly extended to nested versions of the SBM, yielding asymptotically exact samples of hierarchical network partitions.

Related papers

• Symmetry-driven embedding of networks in hyperbolic space [0.4779196219827508]
  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.
  arXiv  Detail & Related papers  (2024-06-15T18:44:02Z)
• Ai-Sampler: Adversarial Learning of Markov kernels with involutive maps [28.229819253644862]
  We propose a method to parameterize and train transition kernels of Markov chains to achieve efficient sampling and good mixing. This training procedure minimizes the total variation distance between the stationary distribution of the chain and the empirical distribution of the data.
  arXiv  Detail & Related papers  (2024-06-04T17:00:14Z)
• Parallel Affine Transformation Tuning of Markov Chain Monte Carlo [1.0923877073891446]
  In particular, we propose a flexible and user-friendly scheme for adaptively learning the affine transformation during sampling. The combination of our scheme with Gibbsian polar slice sampling is shown to produce samples of high quality at comparatively low computational cost.
  arXiv  Detail & Related papers  (2024-01-29T21:06:25Z)
• Generative Flow Networks: a Markov Chain Perspective [93.9910025411313]
  We propose a new perspective for GFlowNets using Markov chains, showing a unifying view for GFlowNets regardless of the nature of the state space. Positioning GFlowNets under the same theoretical framework as MCMC methods also allows us to identify the similarities between both frameworks.
  arXiv  Detail & Related papers  (2023-07-04T01:28:02Z)
• Joint Bayesian Inference of Graphical Structure and Parameters with a Single Generative Flow Network [59.79008107609297]
  We propose in this paper to approximate the joint posterior over the structure of a Bayesian Network. We use a single GFlowNet whose sampling policy follows a two-phase process. Since the parameters are included in the posterior distribution, this leaves more flexibility for the local probability models.
  arXiv  Detail & Related papers  (2023-05-30T19:16:44Z)
• Unsupervised Deep Probabilistic Approach for Partial Point Cloud Registration [74.53755415380171]
  Deep point cloud registration methods face challenges to partial overlaps and rely on labeled data. We propose UDPReg, an unsupervised deep probabilistic registration framework for point clouds with partial overlaps. Our UDPReg achieves competitive performance on the 3DMatch/3DLoMatch and ModelNet/ModelLoNet benchmarks.
  arXiv  Detail & Related papers  (2023-03-23T14:18:06Z)
• Finite Sample Complexity of Sequential Monte Carlo Estimators on Multimodal Target Distributions [0.0]
  We prove finite sample complexities for sequential Monte Carlo (SMC) algorithms which require only local mixing times of the associated kernels. Our bounds are particularly useful when the target distribution is multimodal and global mixing of the kernel is slow.
  arXiv  Detail & Related papers  (2022-08-13T15:06: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)
• Curved Markov Chain Monte Carlo for Network Learning [0.0]
  We present a geometrically enhanced Markov chain Monte Carlo sampler for networks based on a discrete curvature measure defined on graphs. We show that integrating curvature into the sampler results in faster convergence to a wide range of network statistics demonstrated on deterministic networks drawn from real-world data.
  arXiv  Detail & Related papers  (2021-10-07T12:59:02Z)
• 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)
• Kernel learning approaches for summarising and combining posterior similarity matrices [68.8204255655161]
  We build upon the notion of the posterior similarity matrix (PSM) in order to suggest new approaches for summarising the output of MCMC algorithms for Bayesian clustering models. A key contribution of our work is the observation that PSMs are positive semi-definite, and hence can be used to define probabilistically-motivated kernel matrices.
  arXiv  Detail & Related papers  (2020-09-27T14:16:14Z)

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.