Pairwise Covariates-adjusted Block Model for Community Detection

• URL: http://arxiv.org/abs/1807.03469v5
• Date: Mon, 1 May 2023 21:36:29 GMT
• Title: Pairwise Covariates-adjusted Block Model for Community Detection
• Authors: Sihan Huang, Jiajin Sun and Yang Feng
• Abstract summary: Community detection is one of the most fundamental problems in network study. We introduce a pairwise co-adjusted generalization block model (PCABM) We show that PCABM is consistent under suitable sparsity conditions.
• Score: 9.423321226644891
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: One of the most fundamental problems in network study is community detection. The stochastic block model (SBM) is a widely used model, for which various estimation methods have been developed with their community detection consistency results unveiled. However, the SBM is restricted by the strong assumption that all nodes in the same community are stochastically equivalent, which may not be suitable for practical applications. We introduce a pairwise covariates-adjusted stochastic block model (PCABM), a generalization of SBM that incorporates pairwise covariate information. We study the maximum likelihood estimates of the coefficients for the covariates as well as the community assignments. It is shown that both the coefficient estimates of the covariates and the community assignments are consistent under suitable sparsity conditions. Spectral clustering with adjustment (SCWA) is introduced to efficiently solve PCABM. Under certain conditions, we derive the error bound of community detection under SCWA and show that it is community detection consistent. In addition, we investigate model selection in terms of the number of communities and feature selection for the pairwise covariates, and propose two corresponding algorithms. PCABM compares favorably with the SBM or degree-corrected stochastic block model (DCBM) under a wide range of simulated and real networks when covariate information is accessible.

Related papers

• Selecting the Number of Communities for Weighted Degree-Corrected Stochastic Block Models [5.117940794592611]
  We investigate how to select the number of communities for weighted networks without a full likelihood modeling. We propose a novel weighted degree-corrected block model (DCSBM), in which the mean adjacency matrix is modeled as the same as in standard DCSBM. Our method of selecting the number of communities is based on a sequential testing framework, and in each step the weighted DCSBM is fitted via some spectral clustering method.
  arXiv  Detail & Related papers  (2024-06-08T03:47:38Z)
• VEC-SBM: Optimal Community Detection with Vectorial Edges Covariates [67.51637355249986]
  We study an extension of the Block Model (SBM), a widely used statistical framework for community detection. We propose a novel algorithm based on iterative refinement techniques and show that it optimally recovers the latent communities. We rigorously assess the added value of leveraging edge's side information in the community detection process.
  arXiv  Detail & Related papers  (2024-02-29T02:19:55Z)
• Optimal Estimation in Mixed-Membership Stochastic Block Models [2.474391692385924]
  We consider the Mixed-Membership Block Model (MMSB) first proposed by Airoldi et al. This paper is to reconstruct relations between communities given an observed network. Theoretical results are proved under fairly general conditions on the considered model.
  arXiv  Detail & Related papers  (2023-07-26T22:27:08Z)
• Counterfactual Maximum Likelihood Estimation for Training Deep Networks [83.44219640437657]
  Deep learning models are prone to learning spurious correlations that should not be learned as predictive clues. We propose a causality-based training framework to reduce the spurious correlations caused by observable confounders. We conduct experiments on two real-world tasks: Natural Language Inference (NLI) and Image Captioning.
  arXiv  Detail & Related papers  (2021-06-07T17:47:16Z)
• Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
  This paper investigates fundamental limits of exact recovery in the general d-uniform hypergraph block model (d-HSBM) We show that there exists a sharp threshold such that exact recovery is achievable above the threshold and impossible below it.
  arXiv  Detail & Related papers  (2021-05-11T03:39:08Z)
• Community Detection in the Stochastic Block Model by Mixed Integer Programming [3.8073142980733]
  Degree-Corrected Block Model (DCSBM) is a popular model to generate random graphs with community structure given an expected degree sequence. Standard approach of community detection based on the DCSBM is to search for the model parameters that are the most likely to have produced the observed network data through maximum likelihood estimation (MLE) We present mathematical programming formulations and exact solution methods that can provably find the model parameters and community assignments of maximum likelihood given an observed graph.
  arXiv  Detail & Related papers  (2021-01-26T22:04:40Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  We propose the amortized conditional normalized maximum likelihood (ACNML) method as a scalable general-purpose approach for uncertainty estimation. Our algorithm builds on the conditional normalized maximum likelihood (CNML) coding scheme, which has minimax optimal properties according to the minimum description length principle. We demonstrate that ACNML compares favorably to a number of prior techniques for uncertainty estimation in terms of calibration on out-of-distribution inputs.
  arXiv  Detail & Related papers  (2020-11-05T08:04:34Z)
• Autoregressive Score Matching [113.4502004812927]
  We propose autoregressive conditional score models (AR-CSM) where we parameterize the joint distribution in terms of the derivatives of univariable log-conditionals (scores) For AR-CSM models, this divergence between data and model distributions can be computed and optimized efficiently, requiring no expensive sampling or adversarial training. We show with extensive experimental results that it can be applied to density estimation on synthetic data, image generation, image denoising, and training latent variable models with implicit encoders.
  arXiv  Detail & Related papers  (2020-10-24T07:01:24Z)
• Community Detection in Bipartite Networks with Stochastic Blockmodels [0.0]
  In bipartite networks, community structures are restricted to being disassortative, in that nodes of one type are grouped according to common patterns of connection with nodes of the other type. This makes the block model (SBM) an intuitive choice for bipartite community detection. We introduce a nonparametric formulation of the SBM and a corresponding algorithm to efficiently find communities in bipartite networks.
  arXiv  Detail & Related papers  (2020-01-22T05:58:19Z)
• Adaptive Correlated Monte Carlo for Contextual Categorical Sequence Generation [77.7420231319632]
  We adapt contextual generation of categorical sequences to a policy gradient estimator, which evaluates a set of correlated Monte Carlo (MC) rollouts for variance control. We also demonstrate the use of correlated MC rollouts for binary-tree softmax models, which reduce the high generation cost in large vocabulary scenarios.
  arXiv  Detail & Related papers  (2019-12-31T03:01:55Z)

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.