Graph Community Detection from Coarse Measurements: Recovery Conditions for the Coarsened Weighted Stochastic Block Model

• URL: http://arxiv.org/abs/2102.13135v1
• Date: Thu, 25 Feb 2021 19:24:33 GMT
• Title: Graph Community Detection from Coarse Measurements: Recovery Conditions for the Coarsened Weighted Stochastic Block Model
• Authors: Nafiseh Ghoroghchian, Gautam Dasarathy, and Stark C. Draper
• Abstract summary: 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.
• Score: 20.238057838577248
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of community recovery from coarse measurements of a graph. In contrast to the problem of community recovery of a fully observed graph, one often encounters situations when measurements of a graph are made at low-resolution, each measurement integrating across multiple graph nodes. Such low-resolution measurements effectively induce a coarse graph with its own communities. Our objective is to develop conditions on the graph structure, the quantity, and properties of measurements, under which we can recover the community organization in this coarse graph. In this paper, we build on the stochastic block model by mathematically formalizing the coarsening process, and characterizing its impact on the community members and connections. Through this novel setup and modeling, we characterize an error bound for community recovery. The error bound yields simple and closed-form asymptotic conditions to achieve the perfect recovery of the coarse graph communities.

Related papers

• Contrastive Graph Clustering in Curvature Spaces [74.03252813800334]
  We present a novel end-to-end contrastive graph clustering model named CONGREGATE. To support geometric clustering, we construct a theoretically grounded Heterogeneous Curvature Space. We then train the graph clusters by an augmentation-free reweighted contrastive approach.
  arXiv  Detail & Related papers  (2023-05-05T14:04:52Z)
• Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
  This paper focuses on creating a small graph to represent the original graph, so that GNNs trained on the size-reduced graph can make accurate predictions. We view the original graph as a distribution of receptive fields and aim to synthesize a small graph whose receptive fields share a similar distribution.
  arXiv  Detail & Related papers  (2022-06-28T02:10:05Z)
• Exact Community Recovery in Correlated Stochastic Block Models [6.746400031322727]
  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.
  arXiv  Detail & Related papers  (2022-03-29T16:44:38Z)
• 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)
• Generating the Graph Gestalt: Kernel-Regularized Graph Representation Learning [47.506013386710954]
  A complete scientific understanding of graph data should address both global and local structure. We propose a joint model for both as complementary objectives in a graph VAE framework. Our experiments demonstrate a significant improvement in the realism of the generated graph structures, typically by 1-2 orders of magnitude of graph structure metrics.
  arXiv  Detail & Related papers  (2021-06-29T10:48:28Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  multilayer graph clustering aims at dividing the graph nodes into categories or communities. We propose a clustering-friendly embedding of the layers of a given multilayer graph. Experiments show that our method leads to a significant improvement.
  arXiv  Detail & Related papers  (2021-03-30T17:36:40Z)
• Community Detection: Exact Recovery in Weighted Graphs [29.326472933292607]
  In community detection, the exact recovery of communities (clusters) has been investigated under the general block model with edges drawn from Bernoulli distributions. This paper considers the exact recovery of communities in a complete graph in which the graph edges are drawn from either a set of Gaussian distributions with community-dependent means and variances, or a set of exponential distributions with community-dependent means.
  arXiv  Detail & Related papers  (2021-02-08T18:54:29Z)
• 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)

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.