Fundamental limits of community detection from multi-view data: multi-layer, dynamic and partially labeled block models

• URL: http://arxiv.org/abs/2401.08167v1
• Date: Tue, 16 Jan 2024 07:13:32 GMT
• Title: Fundamental limits of community detection from multi-view data: multi-layer, dynamic and partially labeled block models
• Authors: Xiaodong Yang, Buyu Lin, Subhabrata Sen
• Abstract summary: We study community detection in multi-view data in modern network analysis. We characterize the mutual information between the data and the latent parameters. We introduce iterative algorithms based on Approximate Message Passing for community detection.
• Score: 7.778975741303385
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Multi-view data arises frequently in modern network analysis e.g. relations of multiple types among individuals in social network analysis, longitudinal measurements of interactions among observational units, annotated networks with noisy partial labeling of vertices etc. We study community detection in these disparate settings via a unified theoretical framework, and investigate the fundamental thresholds for community recovery. We characterize the mutual information between the data and the latent parameters, provided the degrees are sufficiently large. Based on this general result, (i) we derive a sharp threshold for community detection in an inhomogeneous multilayer block model \citep{chen2022global}, (ii) characterize a sharp threshold for weak recovery in a dynamic stochastic block model \citep{matias2017statistical}, and (iii) identify the limiting mutual information in an unbalanced partially labeled block model. Our first two results are derived modulo coordinate-wise convexity assumptions on specific functions -- we provide extensive numerical evidence for their correctness. Finally, we introduce iterative algorithms based on Approximate Message Passing for community detection in these problems.

Related papers

• Community detection in complex networks via node similarity, graph representation learning, and hierarchical clustering [4.264842058017711]
  Community detection is a critical challenge in analysing real graphs. This article proposes three new, general, hierarchical frameworks to deal with this task. We compare over a hundred module combinations on the Block Model graphs and real-life datasets.
  arXiv  Detail & Related papers  (2023-03-21T22:12:53Z)
• Unified Multi-View Orthonormal Non-Negative Graph Based Clustering Framework [74.25493157757943]
  We formulate a novel clustering model, which exploits the non-negative feature property and incorporates the multi-view information into a unified joint learning framework. We also explore, for the first time, the multi-model non-negative graph-based approach to clustering data based on deep features.
  arXiv  Detail & Related papers  (2022-11-03T08:18:27Z)
• Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold [3.6052935394000234]
  Block model is a canonical random graph model for clustering and community detection on network-structured data. No estimator based on the network topology can perform substantially better than chance on sparse graphs if the model parameter is below a certain threshold. We prove that with an arbitrary fraction of the labels feasible throughout the parameter domain.
  arXiv  Detail & Related papers  (2022-05-24T00:03:25Z)
• 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)
• Multiway Spherical Clustering via Degree-Corrected Tensor Block Models [8.147652597876862]
  We develop a degree-corrected block model with estimation accuracy guarantees. In particular, we demonstrate that an intrinsic statistical-to-computational gap emerges only for tensors of order three or greater. The efficacy of our procedure is demonstrated through two data applications.
  arXiv  Detail & Related papers  (2022-01-19T03:40:22Z)
• 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)
• A Multi-Semantic Metapath Model for Large Scale Heterogeneous Network Representation Learning [52.83948119677194]
  We propose a multi-semantic metapath (MSM) model for large scale heterogeneous representation learning. Specifically, we generate multi-semantic metapath-based random walks to construct the heterogeneous neighborhood to handle the unbalanced distributions. We conduct systematical evaluations for the proposed framework on two challenging datasets: Amazon and Alibaba.
  arXiv  Detail & Related papers  (2020-07-19T22:50:20Z)
• Bayesian Sparse Factor Analysis with Kernelized Observations [67.60224656603823]
  Multi-view problems can be faced with latent variable models. High-dimensionality and non-linear issues are traditionally handled by kernel methods. We propose merging both approaches into single model.
  arXiv  Detail & Related papers  (2020-06-01T14:25:38Z)
• Heterogeneous Graph Neural Networks for Malicious Account Detection [64.0046412312209]
  We present GEM, the first heterogeneous graph neural network approach for detecting malicious accounts. We learn discriminative embeddings from heterogeneous account-device graphs based on two fundamental weaknesses of attackers, i.e. device aggregation and activity aggregation. Experiments show that our approaches consistently perform promising results compared with competitive methods over time.
  arXiv  Detail & Related papers  (2020-02-27T18:26:44Z)
• Seismic horizon detection with neural networks [62.997667081978825]
  This paper is an open-sourced research of applying binary segmentation approach to the task of horizon detection on multiple real seismic cubes with a focus on inter-cube generalization of the predictive model. The main contribution of this paper is an open-sourced research of applying binary segmentation approach to the task of horizon detection on multiple real seismic cubes with a focus on inter-cube generalization of the predictive model.
  arXiv  Detail & Related papers  (2020-01-10T11:30:50Z)
• 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.