Nonparametric Detection of Geometric Structures over Networks

Shaofeng Zou, Yingbin Liang, H. Vincent Poor

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


Nonparametric detection of the possible existence of an anomalous structure over a network is investigated. Nodes corresponding to the anomalous structure (if one exists) receive samples generated by a distribution q, which is different from a distribution p generating samples for other nodes. If an anomalous structure does not exist, all nodes receive samples generated by p. It is assumed that the distributions p and q are arbitrary and unknown. The goal is to design statistically consistent tests with probability of errors converging to zero as the network size becomes asymptotically large. Kernel-based tests are proposed based on maximum mean discrepancy, which measures the distance between mean embeddings of distributions into a reproducing kernel Hilbert space. Detection of an anomalous interval over a line network is first studied. Sufficient conditions on minimum and maximum sizes of candidate anomalous intervals are characterized in order to guarantee that the proposed test is consistent. It is also shown that certain necessary conditions must hold in order to guarantee that any test is universally consistent. Comparison of sufficient and necessary conditions yields that the proposed test is order-level optimal and nearly optimal respectively in terms of minimum and maximum sizes of candidate anomalous intervals. Generalization of the results to other networks is further developed. Numerical results are provided to demonstrate the performance of the proposed tests.

Original languageEnglish (US)
Article number7955000
Pages (from-to)5034-5046
Number of pages13
JournalIEEE Transactions on Signal Processing
Issue number19
StatePublished - Oct 1 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Electrical and Electronic Engineering


  • Anomalous structure detection
  • consistency
  • maximum mean discrepancy
  • nonparametric test


Dive into the research topics of 'Nonparametric Detection of Geometric Structures over Networks'. Together they form a unique fingerprint.

Cite this