A controlled sensing approach to graph classification

Jonathan G. Ligo, George K. Atia, Venugopal Varadachari Veeravalli

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The problem of classifying graphs with respect to connectivity via partial observations of nodes is posed as a composite hypothesis testing problem with controlled sensing. An observation at a node is a subset of edges incident to the node on the complete graph drawn according to a probability model, which are modeled as conditionally independent given their neighborhoods. Connectivity is measured through average node degree and is classified with respect to a threshold. A simple approximation of the controlled sensing test is derived and simulated on Erdös-Rènyi Model A graphs to characterize error probabilities as a function of expected stopping times. It is shown that the proposed test achieves favorable tradeoffs between the classification error and the number of measurements and further outperforms existing approaches, especially at low target error rates. Furthermore, the proposed test achieves asymptotically optimal error performance, as the error rate goes to zero.

Original languageEnglish (US)
Title of host publication2013 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 - Proceedings
Pages5573-5577
Number of pages5
DOIs
StatePublished - Oct 18 2013
Event2013 38th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 - Vancouver, BC, Canada
Duration: May 26 2013May 31 2013

Publication series

NameICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
ISSN (Print)1520-6149

Other

Other2013 38th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013
CountryCanada
CityVancouver, BC
Period5/26/135/31/13

Keywords

  • Complex Networks
  • Controlled Sensing
  • Estimation Theory
  • Graph Classification
  • Social Networks

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'A controlled sensing approach to graph classification'. Together they form a unique fingerprint.

  • Cite this

    Ligo, J. G., Atia, G. K., & Veeravalli, V. V. (2013). A controlled sensing approach to graph classification. In 2013 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 - Proceedings (pp. 5573-5577). [6638730] (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). https://doi.org/10.1109/ICASSP.2013.6638730