Incremental commute time using random walks and online anomaly detection

Nguyen Lu Dang Khoa; Sanjay Chawla

doi:10.1007/978-3-319-46128-1_4

Incremental commute time using random walks and online anomaly detection

Nguyen Lu Dang Khoa^*, Sanjay Chawla

^*Corresponding author for this work

Qatar Computing Research Institute

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

1 Citation (Scopus)

Abstract

Commute time is a random walk based metric on graphs and has found widespread successful applications in many application domains. However, the computation of the commute time is expensive, involving the eigen decomposition of the graph Laplacian matrix. There has been effort to approximate the commute time in offline mode. Our interest is inspired by the use of commute time in online mode. We propose an accurate and efficient approximation for computing the commute time in an incremental fashion in order to facilitate real-time applications. An online anomaly detection technique is designed where the commute time of each new arriving data point to any data point in the current graph can be estimated in constant time ensuring a real-time response. The proposed approach shows its high accuracy and efficiency in many synthetic and real datasets and takes only 8 milliseconds on average to detect anomalies online on the DBLP graph which has more than 600,000 nodes and 2 millions edges.

Original language	English
Title of host publication	Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2016, Proceedings
Editors	Jilles Giuseppe, Niels Landwehr, Giuseppe Manco, Paolo Frasconi
Publisher	Springer Verlag
Pages	49-64
Number of pages	16
ISBN (Print)	9783319461274
DOIs	https://doi.org/10.1007/978-3-319-46128-1_4
Publication status	Published - 2016
Event	15th European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2016 - Riva del Garda, Italy Duration: 19 Sept 2016 → 23 Sept 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9851 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	15th European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2016
Country/Territory	Italy
City	Riva del Garda
Period	19/09/16 → 23/09/16

Keywords

Commute time
Incremental learning
Online anomaly detection
Random walk

Access to Document

10.1007/978-3-319-46128-1_4

Cite this

Khoa, N. L. D., & Chawla, S. (2016). Incremental commute time using random walks and online anomaly detection. In J. Giuseppe, N. Landwehr, G. Manco, & P. Frasconi (Eds.), Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2016, Proceedings (pp. 49-64). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9851 LNAI). Springer Verlag. https://doi.org/10.1007/978-3-319-46128-1_4

Khoa, Nguyen Lu Dang ; Chawla, Sanjay. / Incremental commute time using random walks and online anomaly detection. Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2016, Proceedings. editor / Jilles Giuseppe ; Niels Landwehr ; Giuseppe Manco ; Paolo Frasconi. Springer Verlag, 2016. pp. 49-64 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e4bd2c71b36b4902b0abed16dcd4294a,

title = "Incremental commute time using random walks and online anomaly detection",

abstract = "Commute time is a random walk based metric on graphs and has found widespread successful applications in many application domains. However, the computation of the commute time is expensive, involving the eigen decomposition of the graph Laplacian matrix. There has been effort to approximate the commute time in offline mode. Our interest is inspired by the use of commute time in online mode. We propose an accurate and efficient approximation for computing the commute time in an incremental fashion in order to facilitate real-time applications. An online anomaly detection technique is designed where the commute time of each new arriving data point to any data point in the current graph can be estimated in constant time ensuring a real-time response. The proposed approach shows its high accuracy and efficiency in many synthetic and real datasets and takes only 8 milliseconds on average to detect anomalies online on the DBLP graph which has more than 600,000 nodes and 2 millions edges.",

keywords = "Commute time, Incremental learning, Online anomaly detection, Random walk",

author = "Khoa, {Nguyen Lu Dang} and Sanjay Chawla",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2016.; 15th European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2016 ; Conference date: 19-09-2016 Through 23-09-2016",

year = "2016",

doi = "10.1007/978-3-319-46128-1_4",

language = "English",

isbn = "9783319461274",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "49--64",

editor = "Jilles Giuseppe and Niels Landwehr and Giuseppe Manco and Paolo Frasconi",

booktitle = "Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2016, Proceedings",

address = "Germany",

}

Khoa, NLD & Chawla, S 2016, Incremental commute time using random walks and online anomaly detection. in J Giuseppe, N Landwehr, G Manco & P Frasconi (eds), Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9851 LNAI, Springer Verlag, pp. 49-64, 15th European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2016, Riva del Garda, Italy, 19/09/16. https://doi.org/10.1007/978-3-319-46128-1_4

Incremental commute time using random walks and online anomaly detection. / Khoa, Nguyen Lu Dang; Chawla, Sanjay.
Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2016, Proceedings. ed. / Jilles Giuseppe; Niels Landwehr; Giuseppe Manco; Paolo Frasconi. Springer Verlag, 2016. p. 49-64 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9851 LNAI).

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

TY - GEN

T1 - Incremental commute time using random walks and online anomaly detection

AU - Khoa, Nguyen Lu Dang

AU - Chawla, Sanjay

N1 - Publisher Copyright: © Springer International Publishing AG 2016.

PY - 2016

Y1 - 2016

N2 - Commute time is a random walk based metric on graphs and has found widespread successful applications in many application domains. However, the computation of the commute time is expensive, involving the eigen decomposition of the graph Laplacian matrix. There has been effort to approximate the commute time in offline mode. Our interest is inspired by the use of commute time in online mode. We propose an accurate and efficient approximation for computing the commute time in an incremental fashion in order to facilitate real-time applications. An online anomaly detection technique is designed where the commute time of each new arriving data point to any data point in the current graph can be estimated in constant time ensuring a real-time response. The proposed approach shows its high accuracy and efficiency in many synthetic and real datasets and takes only 8 milliseconds on average to detect anomalies online on the DBLP graph which has more than 600,000 nodes and 2 millions edges.

AB - Commute time is a random walk based metric on graphs and has found widespread successful applications in many application domains. However, the computation of the commute time is expensive, involving the eigen decomposition of the graph Laplacian matrix. There has been effort to approximate the commute time in offline mode. Our interest is inspired by the use of commute time in online mode. We propose an accurate and efficient approximation for computing the commute time in an incremental fashion in order to facilitate real-time applications. An online anomaly detection technique is designed where the commute time of each new arriving data point to any data point in the current graph can be estimated in constant time ensuring a real-time response. The proposed approach shows its high accuracy and efficiency in many synthetic and real datasets and takes only 8 milliseconds on average to detect anomalies online on the DBLP graph which has more than 600,000 nodes and 2 millions edges.

KW - Commute time

KW - Incremental learning

KW - Online anomaly detection

KW - Random walk

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

U2 - 10.1007/978-3-319-46128-1_4

DO - 10.1007/978-3-319-46128-1_4

M3 - Conference contribution

AN - SCOPUS:84988622219

SN - 9783319461274

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 49

EP - 64

BT - Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2016, Proceedings

A2 - Giuseppe, Jilles

A2 - Landwehr, Niels

A2 - Manco, Giuseppe

A2 - Frasconi, Paolo

PB - Springer Verlag

T2 - 15th European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2016

Y2 - 19 September 2016 through 23 September 2016

ER -

Khoa NLD, Chawla S. Incremental commute time using random walks and online anomaly detection. In Giuseppe J, Landwehr N, Manco G, Frasconi P, editors, Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2016, Proceedings. Springer Verlag. 2016. p. 49-64. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-46128-1_4

Incremental commute time using random walks and online anomaly detection

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this