The Power of Side-information in Subgraph Detection
This addresses the problem of subgraph detection in networks for researchers and practitioners, offering a method that overcomes limitations of existing approaches, though it is incremental as it builds on prior Belief Propagation work.
The paper tackles hidden community detection by using Belief Propagation with side-information to detect a subgraph embedded in a larger graph, showing that it achieves asymptotically zero error for any signal-to-noise ratio, unlike methods without side-information which fail below a threshold.
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.