Exact Recovery in the Data Block Model

• URL: http://arxiv.org/abs/2602.05852v1
• Date: Thu, 05 Feb 2026 16:36:57 GMT
• Title: Exact Recovery in the Data Block Model
• Abstract summary: Community detection in networks is a fundamental problem in machine learning and statistical inference.<n>We introduce the Chernoff-TV divergence and use it to characterize a sharp exact recovery threshold for the Data Block Model (DBM)<n>We provide an efficient algorithm that achieves this threshold, along with a matching result showing impossibility below the threshold.
• Score: 1.948261185683419
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Community detection in networks is a fundamental problem in machine learning and statistical inference, with applications in social networks, biological systems, and communication networks. The stochastic block model (SBM) serves as a canonical framework for studying community structure, and exact recovery, identifying the true communities with high probability, is a central theoretical question. While classical results characterize the phase transition for exact recovery based solely on graph connectivity, many real-world networks contain additional data, such as node attributes or labels. In this work, we study exact recovery in the Data Block Model (DBM), an SBM augmented with node-associated data, as formalized by Asadi, Abbe, and Verdú (2017). We introduce the Chernoff--TV divergence and use it to characterize a sharp exact recovery threshold for the DBM. We further provide an efficient algorithm that achieves this threshold, along with a matching converse result showing impossibility below the threshold. Finally, simulations validate our findings and demonstrate the benefits of incorporating vertex data as side information in community detection.

Related papers

• Matrix Factorization Framework for Community Detection under the Degree-Corrected Block Model [48.989531198582704]
  We show that DCBM inference can be reformulated as a constrained nonnegative matrix factorization problem.<n>Our approach is to any specific network structure and applies to graphs with any structure representable by a DCBM.<n> Experiments on synthetic and real benchmark networks show that our method detects communities comparable to those found by DCBM inference.
  arXiv  Detail & Related papers  (2026-01-09T19:16:29Z)
• Adapting HFMCA to Graph Data: Self-Supervised Learning for Generalizable fMRI Representations [57.054499278843856]
  Functional magnetic resonance imaging (fMRI) analysis faces significant challenges due to limited dataset sizes and domain variability between studies.<n>Traditional self-supervised learning methods inspired by computer vision often rely on positive and negative sample pairs.<n>We propose adapting a recently developed Hierarchical Functional Maximal Correlation Algorithm (HFMCA) to graph-structured fMRI data.
  arXiv  Detail & Related papers  (2025-10-05T12:35:01Z)
• Theoretical Insights in Model Inversion Robustness and Conditional Entropy Maximization for Collaborative Inference Systems [89.35169042718739]
  collaborative inference enables end users to leverage powerful deep learning models without exposure of sensitive raw data to cloud servers.<n>Recent studies have revealed that these intermediate features may not sufficiently preserve privacy, as information can be leaked and raw data can be reconstructed via model inversion attacks (MIAs)<n>This work first theoretically proves that the conditional entropy of inputs given intermediate features provides a guaranteed lower bound on the reconstruction mean square error (MSE) under any MIA.<n>Then, we derive a differentiable and solvable measure for bounding this conditional entropy based on the Gaussian mixture estimation and propose a conditional entropy algorithm to enhance the inversion robustness
  arXiv  Detail & Related papers  (2025-03-01T07:15:21Z)
• Energy-based Out-of-Distribution Detection for Graph Neural Networks [76.0242218180483]
  We propose a simple, powerful and efficient OOD detection model for GNN-based learning on graphs, which we call GNNSafe. GNNSafe achieves up to $17.0%$ AUROC improvement over state-of-the-arts and it could serve as simple yet strong baselines in such an under-developed area.
  arXiv  Detail & Related papers  (2023-02-06T16:38:43Z)
• Gait Cycle Reconstruction and Human Identification from Occluded Sequences [2.198430261120653]
  We propose an effective neural network-based model to reconstruct the occluded frames in an input sequence before carrying out gait recognition. We employ LSTM networks to predict an embedding for each occluded frame both from the forward and the backward directions. While the LSTMs are trained to minimize the mean-squared loss, the fusion network is trained to optimize the pixel-wise cross-entropy loss between the ground-truth and the reconstructed samples.
  arXiv  Detail & Related papers  (2022-06-20T16:04:31Z)
• Bayesian community detection for networks with covariates [16.230648949593153]
  "Community detection" has arguably received the most attention in the scientific community. We propose a block model with a co-dependent random partition prior. Our model has the ability to learn the number of the communities via posterior inference without having to assume it to be known.
  arXiv  Detail & Related papers  (2022-03-04T01:58:35Z)
• Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning [50.24174211654775]
  We present a novel contrastive self-supervised learning framework for anomaly detection on attributed networks. Our framework fully exploits the local information from network data by sampling a novel type of contrastive instance pair. A graph neural network-based contrastive learning model is proposed to learn informative embedding from high-dimensional attributes and local structure.
  arXiv  Detail & Related papers  (2021-02-27T03:17:20Z)
• 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)
• Joint Inference of Diffusion and Structure in Partially Observed Social Networks Using Coupled Matrix Factorization [3.399624105745357]
  In this paper, a model is learned from partially observed data to infer unobserved diffusion and structure networks. The interrelations among links of nodes and cascade processes are utilized in the proposed method via learning and low-dimensional latent factors. Experiments on these synthetic and real-world datasets show that the proposed method successfully detects invisible social behaviors, predicts links, and identifies latent features.
  arXiv  Detail & Related papers  (2020-10-03T17:48:57Z)
• Uncertainty Estimation Using a Single Deep Deterministic Neural Network [66.26231423824089]
  We propose a method for training a deterministic deep model that can find and reject out of distribution data points at test time with a single forward pass. We scale training in these with a novel loss function and centroid updating scheme and match the accuracy of softmax models.
  arXiv  Detail & Related papers  (2020-03-04T12:27:36Z)
• Community Detection and Stochastic Block Models [20.058330327502503]
  The geometric block model (SBM) is widely employed as a canonical model to study clustering and community detection. It provides a fertile ground to study the information-theoretic and computational tradeoffs that arise in statistics and data science. This book surveys the recent developments that establish the fundamental limits for community detection in the SBM.
  arXiv  Detail & Related papers  (2017-03-29T17:21:44Z)

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.