Exact Community Recovery over Signed Graphs

• URL: http://arxiv.org/abs/2202.12255v1
• Date: Tue, 22 Feb 2022 05:03:25 GMT
• Title: Exact Community Recovery over Signed Graphs
• Authors: Xiaolu Wang, Peng Wang, Anthony Man-Cho So
• Abstract summary: We study the problem of community recovery over signed graphs with two equal-sized communities. Our approach is based on the maximum likelihood estimation (MLE) of the signed block model. It is shown that in the logarithmic degree regime, the proposed algorithm can exactly recover the underlying communities in nearly-linear time.
• Score: 27.2776492470422
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Signed graphs encode similarity and dissimilarity relationships among different entities with positive and negative edges. In this paper, we study the problem of community recovery over signed graphs generated by the signed stochastic block model (SSBM) with two equal-sized communities. Our approach is based on the maximum likelihood estimation (MLE) of the SSBM. Unlike many existing approaches, our formulation reveals that the positive and negative edges of a signed graph should be treated unequally. We then propose a simple two-stage iterative algorithm for solving the regularized MLE. It is shown that in the logarithmic degree regime, the proposed algorithm can exactly recover the underlying communities in nearly-linear time at the information-theoretic limit. Numerical results on both synthetic and real data are reported to validate and complement our theoretical developments and demonstrate the efficacy of the proposed method.

Related papers

• ExDBN: Exact learning of Dynamic Bayesian Networks [2.2499166814992435]
  We propose a score-based learning approach for causal learning from data. We show that the proposed approach turns out to produce excellent results when applied to small and medium-sized synthetic instances of up to 25 time-series. Two interesting applications in bio-science and finance, to which the method is directly applied, further stress the opportunities in developing highly accurate, globally convergent solvers.
  arXiv  Detail & Related papers  (2024-10-21T15:27:18Z)
• Vector-Valued Least-Squares Regression under Output Regularity Assumptions [73.99064151691597]
  We propose and analyse a reduced-rank method for solving least-squares regression problems with infinite dimensional output. We derive learning bounds for our method, and study under which setting statistical performance is improved in comparison to full-rank method.
  arXiv  Detail & Related papers  (2022-11-16T15:07:00Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• Making Linear MDPs Practical via Contrastive Representation Learning [101.75885788118131]
  It is common to address the curse of dimensionality in Markov decision processes (MDPs) by exploiting low-rank representations. We consider an alternative definition of linear MDPs that automatically ensures normalization while allowing efficient representation learning. We demonstrate superior performance over existing state-of-the-art model-based and model-free algorithms on several benchmarks.
  arXiv  Detail & Related papers  (2022-07-14T18:18:02Z)
• 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)
• Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations [57.15855198512551]
  We propose a novel score-based generative model for graphs with a continuous-time framework. We show that our method is able to generate molecules that lie close to the training distribution yet do not violate the chemical valency rule.
  arXiv  Detail & Related papers  (2022-02-05T08:21:04Z)
• A Probabilistic Graph Coupling View of Dimension Reduction [5.35952718937799]
  We introduce a unifying statistical framework based on the coupling of hidden graphs using cross entropy. We show that existing pairwise similarity DR methods can be retrieved from our framework with particular choices of priors for the graphs. Our model is leveraged and extended to address the issue while new links are drawn with Laplacian eigenmaps and PCA.
  arXiv  Detail & Related papers  (2022-01-31T08:21:55Z)
• 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)
• 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)
• GELATO: Geometrically Enriched Latent Model for Offline Reinforcement Learning [54.291331971813364]
  offline reinforcement learning approaches can be divided into proximal and uncertainty-aware methods. In this work, we demonstrate the benefit of combining the two in a latent variational model. Our proposed metrics measure both the quality of out of distribution samples as well as the discrepancy of examples in the data.
  arXiv  Detail & Related papers  (2021-02-22T19:42:40Z)
• Non-Convex Exact Community Recovery in Stochastic Block Model [31.221745716673546]
  Community detection in graphs that are generated according to symmetric block models (SBMs) has received much attention lately. We show that in the logarithmic sparsity regime of the problem, with high probability the proposed two-stage method can exactly recover the two communities down to the information-theoretic limit in $mathcalO(nlog2n/loglog n)$ time. We also conduct numerical experiments on both synthetic and real data sets to demonstrate the efficacy of our proposed method and complement our theoretical development.
  arXiv  Detail & Related papers  (2020-06-29T07:03:27Z)

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.