Goodness-of-fit statistics for anomaly detection in Chung-Lu random graphs

Benjamin A. Miller; Lauren H. Stephens; Nadya T. Bliss

doi:10.1109/ICASSP.2012.6288612

Goodness-of-fit statistics for anomaly detection in Chung-Lu random graphs

Benjamin A. Miller, Lauren H. Stephens, Nadya T. Bliss

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Scopus citations

Abstract

Anomaly detection in graphs is a relevant problem in numerous applications. When determining whether an observation is anomalous with respect to the model of typical behavior, the notion of "goodness of fit" is important. This notion, however, is not well-understood in the context of graph data. In this paper, we propose three goodness-of-fit statistics for Chung-Lu random graphs, and analyze their efficacy in discriminating graphs generated by the Chung-Lu model from those with anomalous topologies. In the results of a Monte Carlo simulation, we see that the most powerful statistic for anomaly detection depends on the type of anomaly, suggesting that a hybrid statistic would be the most powerful.

Original language	English (US)
Title of host publication	2012 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2012 - Proceedings
Pages	3265-3268
Number of pages	4
DOIs	https://doi.org/10.1109/ICASSP.2012.6288612
State	Published - 2012
Externally published	Yes
Event	2012 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2012 - Kyoto, Japan Duration: Mar 25 2012 → Mar 30 2012

Publication series

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

Other

Other	2012 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2012
Country/Territory	Japan
City	Kyoto
Period	3/25/12 → 3/30/12

Keywords

Graph theory
anomaly detection
goodness of fit
probabilistic models
signal detection theory

ASJC Scopus subject areas

Software
Signal Processing
Electrical and Electronic Engineering

Access to Document

10.1109/ICASSP.2012.6288612

Cite this

Miller, B. A., Stephens, L. H., & Bliss, N. T. (2012). Goodness-of-fit statistics for anomaly detection in Chung-Lu random graphs. In 2012 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2012 - Proceedings (pp. 3265-3268). Article 6288612 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). https://doi.org/10.1109/ICASSP.2012.6288612

Goodness-of-fit statistics for anomaly detection in Chung-Lu random graphs. / Miller, Benjamin A.; Stephens, Lauren H.; Bliss, Nadya T.
2012 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2012 - Proceedings. 2012. p. 3265-3268 6288612 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Miller, BA, Stephens, LH & Bliss, NT 2012, Goodness-of-fit statistics for anomaly detection in Chung-Lu random graphs. in 2012 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2012 - Proceedings., 6288612, ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, pp. 3265-3268, 2012 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2012, Kyoto, Japan, 3/25/12. https://doi.org/10.1109/ICASSP.2012.6288612

Miller BA, Stephens LH, Bliss NT. Goodness-of-fit statistics for anomaly detection in Chung-Lu random graphs. In 2012 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2012 - Proceedings. 2012. p. 3265-3268. 6288612. (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). doi: 10.1109/ICASSP.2012.6288612

@inproceedings{9eda6e419e8146a899663532ed3f711c,

title = "Goodness-of-fit statistics for anomaly detection in Chung-Lu random graphs",

abstract = "Anomaly detection in graphs is a relevant problem in numerous applications. When determining whether an observation is anomalous with respect to the model of typical behavior, the notion of {"}goodness of fit{"} is important. This notion, however, is not well-understood in the context of graph data. In this paper, we propose three goodness-of-fit statistics for Chung-Lu random graphs, and analyze their efficacy in discriminating graphs generated by the Chung-Lu model from those with anomalous topologies. In the results of a Monte Carlo simulation, we see that the most powerful statistic for anomaly detection depends on the type of anomaly, suggesting that a hybrid statistic would be the most powerful.",

keywords = "Graph theory, anomaly detection, goodness of fit, probabilistic models, signal detection theory",

author = "Miller, {Benjamin A.} and Stephens, {Lauren H.} and Bliss, {Nadya T.}",

year = "2012",

doi = "10.1109/ICASSP.2012.6288612",

language = "English (US)",

isbn = "9781467300469",

series = "ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings",

pages = "3265--3268",

booktitle = "2012 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2012 - Proceedings",

note = "2012 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2012 ; Conference date: 25-03-2012 Through 30-03-2012",

}

TY - GEN

T1 - Goodness-of-fit statistics for anomaly detection in Chung-Lu random graphs

AU - Miller, Benjamin A.

AU - Stephens, Lauren H.

AU - Bliss, Nadya T.

PY - 2012

Y1 - 2012

N2 - Anomaly detection in graphs is a relevant problem in numerous applications. When determining whether an observation is anomalous with respect to the model of typical behavior, the notion of "goodness of fit" is important. This notion, however, is not well-understood in the context of graph data. In this paper, we propose three goodness-of-fit statistics for Chung-Lu random graphs, and analyze their efficacy in discriminating graphs generated by the Chung-Lu model from those with anomalous topologies. In the results of a Monte Carlo simulation, we see that the most powerful statistic for anomaly detection depends on the type of anomaly, suggesting that a hybrid statistic would be the most powerful.

AB - Anomaly detection in graphs is a relevant problem in numerous applications. When determining whether an observation is anomalous with respect to the model of typical behavior, the notion of "goodness of fit" is important. This notion, however, is not well-understood in the context of graph data. In this paper, we propose three goodness-of-fit statistics for Chung-Lu random graphs, and analyze their efficacy in discriminating graphs generated by the Chung-Lu model from those with anomalous topologies. In the results of a Monte Carlo simulation, we see that the most powerful statistic for anomaly detection depends on the type of anomaly, suggesting that a hybrid statistic would be the most powerful.

KW - Graph theory

KW - anomaly detection

KW - goodness of fit

KW - probabilistic models

KW - signal detection theory

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

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

U2 - 10.1109/ICASSP.2012.6288612

DO - 10.1109/ICASSP.2012.6288612

M3 - Conference contribution

AN - SCOPUS:84867595594

SN - 9781467300469

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

SP - 3265

EP - 3268

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

T2 - 2012 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2012

Y2 - 25 March 2012 through 30 March 2012

ER -

Goodness-of-fit statistics for anomaly detection in Chung-Lu random graphs

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this