Ecole d'ingénieur et centre de recherche en Sciences du numérique

Subgraph detection with cues using belief propagation

Kadavankandy, Arun; Avrachenkov, Konstantin; Cottatellucci, Laura; Rajesh, Sundaresan

Research Report, October 2016

We consider an Erdos-Renyi graph with n" role="presentation" style="box-sizing: border-box; display: inline; line-height: normal; font-size: 13px; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; color: rgb(54, 56, 66); font-family: arial, verdana, sans-serif; position: relative;">nn nodes and edge probability q" role="presentation" style="box-sizing: border-box; display: inline; line-height: normal; font-size: 13px; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; color: rgb(54, 56, 66); font-family: arial, verdana, sans-serif; position: relative;">qq that is embedded with a random subgraph of size K" role="presentation" style="box-sizing: border-box; display: inline; line-height: normal; font-size: 13px; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; color: rgb(54, 56, 66); font-family: arial, verdana, sans-serif; position: relative;">KK with edge probabilities p" role="presentation" style="box-sizing: border-box; display: inline; line-height: normal; font-size: 13px; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; color: rgb(54, 56, 66); font-family: arial, verdana, sans-serif; position: relative;">pp such that p>q." role="presentation" style="box-sizing: border-box; display: inline; line-height: normal; font-size: 13px; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; color: rgb(54, 56, 66); font-family: arial, verdana, sans-serif; position: relative;">p>q.p>q. We address the problem of detecting the subgraph nodes when only the graph edges are observed, along with some extra knowledge of a small fraction of subgraph nodes, called cued vertices or cues. We employ a local and distributed algorithm called belief propagation (BP). Recent works on subgraph detection without cues have shown that global maximum likelihood (ML) detection strictly outperforms BP in terms of asymptotic error rate, namely, there is a threshold condition that the subgraph parameters should satisfy below which BP fails in achieving asymptotically zero error, but ML succeeds. In contrast, we show that when the fraction of cues is strictly bounded away from zero, i.e., when there exists non-trivial side-information, BP achieves zero asymptotic error even below this threshold, thus approaching the performance of ML detection.

Document Hal Bibtex

Titre:Subgraph detection with cues using belief propagation
Type:Rapport
Langue:English
Ville:
Date:
Département:Systèmes de Communication
Eurecom ref:5051
Copyright: © INRIA. Personal use of this material is permitted. The definitive version of this paper was published in Research Report, October 2016 and is available at :
Bibtex: @techreport{EURECOM+5051, year = {2016}, title = {{S}ubgraph detection with cues using belief propagation}, author = {{K}adavankandy, {A}run and {A}vrachenkov, {K}onstantin and {C}ottatellucci, {L}aura and {R}ajesh, {S}undaresan}, number = {EURECOM+5051}, month = {11}, institution = {Eurecom}, url = {http://www.eurecom.fr/publication/5051},, }
Voir aussi: