Graduate School and Research Center in Digital Sciences

Belief propagation for subgraph detection with imperfect side-information

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

ISIT 2017, IEEE International Symposium on Information Theory, June 25-30, 2017, Aachen, Germany

We propose a local message passing algorithm based on Belief Propagation (BP) to detect a small hidden Erd˝os-R´enyi (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.

Document Doi Hal Bibtex

Title:Belief propagation for subgraph detection with imperfect side-information
Keywords:Subgraph detection, Erdos-Renyi, Belief Propagation
Department:Communication systems
Eurecom ref:5129
Copyright: © 2017 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Bibtex: @inproceedings{EURECOM+5129, doi = {}, year = {2017}, title = {{B}elief propagation for subgraph detection with imperfect side-information}, author = {{K}adavankandy, {A}run and {A}vrachenkov, {K}onstantin and {C}ottatellucci, {L}aura and {S}undaresan, {R}ajesh}, booktitle = {{ISIT} 2017, {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, {J}une 25-30, 2017, {A}achen, {G}ermany}, address = {{A}achen, {GERMANY}}, month = {06}, url = {} }
See also: