Belief Propagation for Subgraph Detection with Imperfect Side-information

Arun Kadavankandy 1 Konstantin Avrachenkov 1 Laura Cottatellucci 2 Rajesh Sundaresan 3
1 NEO - Network Engineering and Operations
CRISAM - Inria Sophia Antipolis - Méditerranée
2 Eurecom [Sophia Antipolis]
3 ECE - Department of Electrical Communication Engineering [Bangalore]
Abstract : We propose a local message passing algorithm based on Belief Propagation (BP) to detect a small hidden Erdos-Renyi (ER) subgraph embedded in a larger sparse ER random graph in the presence of side-information. We consider side-information in the form of revealed subgraph nodes called cues, some of which may be erroneous. Namely, the revealed nodes may not all belong to the subgraph, and it is not known to the algorithm a priori which cues are correct and which are incorrect. We show that asymptotically as the graph size tends to infinity, the expected fraction of misclassified nodes approaches zero for any positive value of a parameter λ, which represents the effective Signal-to-Noise Ratio of the detection problem. Previous works on subgraph detection using BP without side-information showed that BP fails to recover the subgraph when λ < 1/e. Our results thus demonstrate the substantial gains in having even a small amount of side-information.
Keywords : Belief Propagation BP Subgraph detection Erdos-Renyi random graph
Type de document :
Communication dans un congrès
IEEE International Symposium on Information Theory (ISIT 2017), Jun 2017, Aachen, Germany
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01647878
Contributeur : Konstantin Avrachenkov <>
Soumis le : vendredi 24 novembre 2017 - 16:15:56
Dernière modification le : lundi 30 avril 2018 - 14:30:10

Fichier

ISIT2017paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01647878, version 1

Collections

INSMI | INRIA | INRIA2017 | EURECOM | UNIV-COTEDAZUR

Citation

Arun Kadavankandy, Konstantin Avrachenkov, Laura Cottatellucci, Rajesh Sundaresan. Belief Propagation for Subgraph Detection with Imperfect Side-information. IEEE International Symposium on Information Theory (ISIT 2017), Jun 2017, Aachen, Germany. 〈hal-01647878〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

213

Téléchargements de fichiers

35

Contact


archive-ouverte@inria.fr