Streaming Belief Propagation for Community Detection

• URL: http://arxiv.org/abs/2106.04805v2
• Date: Thu, 10 Jun 2021 18:13:03 GMT
• Title: Streaming Belief Propagation for Community Detection
• Authors: Yuchen Wu, MohammadHossein Bateni, Andre Linhares, Filipe Miguel Goncalves de Almeida, Andrea Montanari, Ashkan Norouzi-Fard, Jakab Tardos
• Abstract summary: In real-world applications, the network structure is typically dynamic, with nodes that join over time. We introduce a simple model for networks growing over time which we refer to as streaming block model (StSBM) Within this model, we prove that voting algorithms have fundamental limitations. We also develop a streaming-propagation (StreamBP) approach, for which we prove optimality in certain regimes.
• Score: 16.89299967467454
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The community detection problem requires to cluster the nodes of a network into a small number of well-connected "communities". There has been substantial recent progress in characterizing the fundamental statistical limits of community detection under simple stochastic block models. However, in real-world applications, the network structure is typically dynamic, with nodes that join over time. In this setting, we would like a detection algorithm to perform only a limited number of updates at each node arrival. While standard voting approaches satisfy this constraint, it is unclear whether they exploit the network information optimally. We introduce a simple model for networks growing over time which we refer to as streaming stochastic block model (StSBM). Within this model, we prove that voting algorithms have fundamental limitations. We also develop a streaming belief-propagation (StreamBP) approach, for which we prove optimality in certain regimes. We validate our theoretical findings on synthetic and real data.

Related papers

• Neural-prior stochastic block model [0.0]
  We propose to model the communities as being determined by the node attributes rather than the opposite. We propose an algorithm, stemming from statistical physics, based on a combination of belief propagation and approximate message passing. The proposed model and algorithm can be used as a benchmark for both theory and algorithms.
  arXiv  Detail & Related papers  (2023-03-17T14:14:54Z)
• The Cascaded Forward Algorithm for Neural Network Training [61.06444586991505]
  We propose a new learning framework for neural networks, namely Cascaded Forward (CaFo) algorithm, which does not rely on BP optimization as that in FF. Unlike FF, our framework directly outputs label distributions at each cascaded block, which does not require generation of additional negative samples. In our framework each block can be trained independently, so it can be easily deployed into parallel acceleration systems.
  arXiv  Detail & Related papers  (2023-03-17T02:01:11Z)
• Toward Certified Robustness Against Real-World Distribution Shifts [65.66374339500025]
  We train a generative model to learn perturbations from data and define specifications with respect to the output of the learned model. A unique challenge arising from this setting is that existing verifiers cannot tightly approximate sigmoid activations. We propose a general meta-algorithm for handling sigmoid activations which leverages classical notions of counter-example-guided abstraction refinement.
  arXiv  Detail & Related papers  (2022-06-08T04:09:13Z)
• Equilibrated Zeroth-Order Unrolled Deep Networks for Accelerated MRI [14.586911990418624]
  Recently, model-driven deep learning unrolls a certain iterative algorithm of a regularization model into a cascade network. In theory, there is not necessarily such a functional regularizer whose first-order information matches the replaced network module. This paper propose to present a safeguarded methodology on network unrolling.
  arXiv  Detail & Related papers  (2021-12-18T09:47:19Z)
• VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization [70.8567058758375]
  VQ-GNN is a universal framework to scale up any convolution-based GNNs using Vector Quantization (VQ) without compromising the performance. Our framework avoids the "neighbor explosion" problem of GNNs using quantized representations combined with a low-rank version of the graph convolution matrix.
  arXiv  Detail & Related papers  (2021-10-27T11:48:50Z)
• CREPO: An Open Repository to Benchmark Credal Network Algorithms [78.79752265884109]
  Credal networks are imprecise probabilistic graphical models based on, so-called credal, sets of probability mass functions. A Java library called CREMA has been recently released to model, process and query credal networks. We present CREPO, an open repository of synthetic credal networks, provided together with the exact results of inference tasks on these models.
  arXiv  Detail & Related papers  (2021-05-10T07:31:59Z)
• Spatio-Temporal Inception Graph Convolutional Networks for Skeleton-Based Action Recognition [126.51241919472356]
  We design a simple and highly modularized graph convolutional network architecture for skeleton-based action recognition. Our network is constructed by repeating a building block that aggregates multi-granularity information from both the spatial and temporal paths.
  arXiv  Detail & Related papers  (2020-11-26T14:43:04Z)
• Sketch-based community detection in evolving networks [15.512086254435788]
  We consider an approach for community detection in time-varying networks. At its core, this approach maintains a small sketch graph to capture the essential community structure found in each snapshot of the full network. We formulate a community detection algorithm which can process a network concurrently exhibiting all processes.
  arXiv  Detail & Related papers  (2020-09-24T17:32:57Z)
• Detecting Communities in Heterogeneous Multi-Relational Networks:A Message Passing based Approach [89.19237792558687]
  Community is a common characteristic of networks including social networks, biological networks, computer and information networks. We propose an efficient message passing based algorithm to simultaneously detect communities for all homogeneous networks.
  arXiv  Detail & Related papers  (2020-04-06T17:36:24Z)
• PushNet: Efficient and Adaptive Neural Message Passing [1.9121961872220468]
  Message passing neural networks have recently evolved into a state-of-the-art approach to representation learning on graphs. Existing methods perform synchronous message passing along all edges in multiple subsequent rounds. We consider a novel asynchronous message passing approach where information is pushed only along the most relevant edges until convergence.
  arXiv  Detail & Related papers  (2020-03-04T18:15:30Z)
• Artificial Benchmark for Community Detection (ABCD): Fast Random Graph Model with Community Structure [5.8010446129208155]
  We provide an alternative random graph model with community structure and power-law distribution for both degrees and community sizes, the Artificial Benchmark for Community Detection (ABCD) ABCD is fast, simple, and can be easily tuned to allow the user to make a smooth transition between the two extremes: pure (independent) communities and random graph with no community structure.
  arXiv  Detail & Related papers  (2020-01-14T17:20: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.