Exact Community Recovery in Correlated Stochastic Block Models

• URL: http://arxiv.org/abs/2203.15736v1
• Date: Tue, 29 Mar 2022 16:44:38 GMT
• Title: Exact Community Recovery in Correlated Stochastic Block Models
• Authors: Julia Gaudio, Miklos Z. Racz, Anirudh Sridhar
• Abstract summary: We study the problem of learning latent community structure from multiple correlated networks. Our main result derives the precise information-theoretic threshold for exact community recovery using multiple correlated graphs. We develop a novel algorithm that carefully synthesizes algorithms from the community recovery and graph matching literatures.
• Score: 6.746400031322727
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of learning latent community structure from multiple correlated networks. We study edge-correlated stochastic block models with two balanced communities, focusing on the regime where the average degree is logarithmic in the number of vertices. Our main result derives the precise information-theoretic threshold for exact community recovery using multiple correlated graphs. This threshold captures the interplay between the community recovery and graph matching tasks. In particular, we uncover and characterize a region of the parameter space where exact community recovery is possible using multiple correlated graphs, even though (1) this is information-theoretically impossible using a single graph and (2) exact graph matching is also information-theoretically impossible. In this regime, we develop a novel algorithm that carefully synthesizes algorithms from the community recovery and graph matching literatures.

Related papers

• Curvature-based Clustering on Graphs [14.136746708037402]
  We study algorithms, which exploit the geometry of the graph to identify densely connected substructures, which form clusters or communities. Our method implements discrete Ricci curvatures and their associated geometric flows, under which the edge weights of the graph evolve to reveal its community structure.
  arXiv  Detail & Related papers  (2023-07-19T17:35:08Z)
• You Only Transfer What You Share: Intersection-Induced Graph Transfer Learning for Link Prediction [79.15394378571132]
  We investigate a previously overlooked phenomenon: in many cases, a densely connected, complementary graph can be found for the original graph. The denser graph may share nodes with the original graph, which offers a natural bridge for transferring selective, meaningful knowledge. We identify this setting as Graph Intersection-induced Transfer Learning (GITL), which is motivated by practical applications in e-commerce or academic co-authorship predictions.
  arXiv  Detail & Related papers  (2023-02-27T22:56:06Z)
• GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
  We consider the problem of modelling high-dimensional distributions and generating new examples of data with complex relational feature structure coherent with a graph skeleton. The model we propose tackles the problem of generating the data features constrained by the specific graph structure of each data point by splitting the task into two phases. In the first it models the distribution of features associated with the nodes of the given graph, in the second it complements the edge features conditionally on the node features.
  arXiv  Detail & Related papers  (2022-12-01T11:49:07Z)
• Fair Community Detection and Structure Learning in Heterogeneous Graphical Models [8.643517734716607]
  Inference of community structure in probabilistic graphical models may not be consistent with fairness constraints when nodes have demographic attributes. This paper defines a novel $ell_$-regularized pseudo-likelihood approach for fair graphical model selection.
  arXiv  Detail & Related papers  (2021-12-09T18:58:36Z)
• Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities [2.7920304852537527]
  We consider the task of learning latent community structure from multiple correlated networks. We show how one can exactly recover the latent communities using multiple correlated graphs in parameter regimes.
  arXiv  Detail & Related papers  (2021-07-14T15:27:15Z)
• Spatial-spectral Hyperspectral Image Classification via Multiple Random Anchor Graphs Ensemble Learning [88.60285937702304]
  This paper proposes a novel spatial-spectral HSI classification method via multiple random anchor graphs ensemble learning (RAGE) Firstly, the local binary pattern is adopted to extract the more descriptive features on each selected band, which preserves local structures and subtle changes of a region. Secondly, the adaptive neighbors assignment is introduced in the construction of anchor graph, to reduce the computational complexity.
  arXiv  Detail & Related papers  (2021-03-25T09:31:41Z)
• Graph Community Detection from Coarse Measurements: Recovery Conditions for the Coarsened Weighted Stochastic Block Model [20.238057838577248]
  We study the problem of community recovery from coarse measurements of a graph. We build on the block model by mathematically formalizing the coarsening process.
  arXiv  Detail & Related papers  (2021-02-25T19:24:33Z)
• Amortized Probabilistic Detection of Communities in Graphs [39.56798207634738]
  We propose a simple framework for amortized community detection. We combine the expressive power of GNNs with recent methods for amortized clustering. We evaluate several models from our framework on synthetic and real datasets.
  arXiv  Detail & Related papers  (2020-10-29T16:18:48Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• Structural Landmarking and Interaction Modelling: on Resolution Dilemmas in Graph Classification [50.83222170524406]
  We study the intrinsic difficulty in graph classification under the unified concept of resolution dilemmas'' We propose SLIM'', an inductive neural network model for Structural Landmarking and Interaction Modelling.
  arXiv  Detail & Related papers  (2020-06-29T01:01:42Z)
• Tensor Graph Convolutional Networks for Multi-relational and Robust Learning [74.05478502080658]
  This paper introduces a tensor-graph convolutional network (TGCN) for scalable semi-supervised learning (SSL) from data associated with a collection of graphs, that are represented by a tensor. The proposed architecture achieves markedly improved performance relative to standard GCNs, copes with state-of-the-art adversarial attacks, and leads to remarkable SSL performance over protein-to-protein interaction networks.
  arXiv  Detail & Related papers  (2020-03-15T02:33:21Z)

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.