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

Fingerprint

Composite materials
Testing
Error probability

Keywords

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

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Electrical and Electronic Engineering

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

A controlled sensing approach to graph classification. / Ligo, Jonathan G.; Atia, George K.; Veeravalli, Venugopal Varadachari.

2013 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 - Proceedings. 2013. p. 5573-5577 6638730 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

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

Ligo, JG, Atia, GK & Veeravalli, VV 2013, A controlled sensing approach to graph classification. in 2013 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 - Proceedings., 6638730, ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, pp. 5573-5577, 2013 38th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013, Vancouver, BC, Canada, 5/26/13. https://doi.org/10.1109/ICASSP.2013.6638730
Ligo JG, Atia GK, Veeravalli VV. A controlled sensing approach to graph classification. In 2013 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 - Proceedings. 2013. p. 5573-5577. 6638730. (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). https://doi.org/10.1109/ICASSP.2013.6638730
Ligo, Jonathan G. ; Atia, George K. ; Veeravalli, Venugopal Varadachari. / A controlled sensing approach to graph classification. 2013 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 - Proceedings. 2013. pp. 5573-5577 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).
@inproceedings{2c5e705caef6498791e40a3f0da4474c,
title = "A controlled sensing approach to graph classification",
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{\"o}s-R{\`e}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.",
keywords = "Complex Networks, Controlled Sensing, Estimation Theory, Graph Classification, Social Networks",
author = "Ligo, {Jonathan G.} and Atia, {George K.} and Veeravalli, {Venugopal Varadachari}",
year = "2013",
month = "10",
day = "18",
doi = "10.1109/ICASSP.2013.6638730",
language = "English (US)",
isbn = "9781479903566",
series = "ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings",
pages = "5573--5577",
booktitle = "2013 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 - Proceedings",

}

TY - GEN

T1 - A controlled sensing approach to graph classification

AU - Ligo, Jonathan G.

AU - Atia, George K.

AU - Veeravalli, Venugopal Varadachari

PY - 2013/10/18

Y1 - 2013/10/18

N2 - 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.

AB - 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.

KW - Complex Networks

KW - Controlled Sensing

KW - Estimation Theory

KW - Graph Classification

KW - Social Networks

UR - http://www.scopus.com/inward/record.url?scp=84890482974&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84890482974&partnerID=8YFLogxK

U2 - 10.1109/ICASSP.2013.6638730

DO - 10.1109/ICASSP.2013.6638730

M3 - Conference contribution

AN - SCOPUS:84890482974

SN - 9781479903566

T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings

SP - 5573

EP - 5577

BT - 2013 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 - Proceedings

ER -