The Power of Side-information in Subgraph Detection

Abstract

In this work, we tackle the problem of hidden community detection. We consider Belief Propagation (BP) applied to the problem of detecting a hidden Erdős-Rényi (ER) graph embedded in a larger and sparser ER graph, in the presence of side-information. We derive two related algorithms based on BP to perform subgraph detection in the presence of two kinds of side-information. The first variant of side-information consists of a set of nodes, called cues, known to be from the subgraph. The second variant of side-information consists of a set of nodes that are cues with a given probability. It was shown in past works that BP without side-information fails to detect the subgraph correctly when an effective signal-to-noise ratio (SNR) parameter falls below a threshold. In contrast, in the presence of non-trivial side-information, we show that the BP algorithm achieves asymptotically zero error for any value of the SNR parameter. We validate our results through simulations on synthetic datasets as well as on a few real world networks.

References in corpus (8)

• Signal Recovery on Graphs: Variation Minimization
• Local-set-based Graph Signal Reconstruction
• Stochastic Block Models and Reconstruction
• Finding One Community in a Sparse Graph
• Inference via Message Passing on Partially Labeled Stochastic Block Models
• Bayesian Discovery of Threat Networks
• Network Detection Theory and Performance
• Recovering a Hidden Community Beyond the Kesten-Stigum Threshold in $O(|E|{\log }^{\ast }|V|)$ Time

Cited by in corpus (1)

• Side Information in the Binary Stochastic Block Model: Exact Recovery