File(s) under permanent embargo
Node re-ordering as a means of anomaly detection in time-evolving graphs
conference contribution
posted on 2016-09-04, 00:00 authored by L Rashidi, A Kan, J Bailey, J Chan, C Leckie, W Liu, Sutharshan RajasegararSutharshan Rajasegarar, K RamamohanaraoAnomaly detection is a vital task for maintaining and improving any dynamic system. In this paper, we address the problem of anomaly detection in time-evolving graphs, where graphs are a natural representation for data in many types of applications. A key challenge in this context is how to process large volumes of streaming graphs. We propose a pre-processing step before running any further analysis on the data, where we permute the rows and columns of the adjacency matrix. This pre-processing step expedites graph mining techniques such as anomaly detection, PageRank, or graph coloring. In this paper, we focus on detecting anomalies in a sequence of graphs based on rank correlations of the reordered nodes. The merits of our approach lie in its simplicity and resilience to challenges such as unsupervised input, large volumes and high velocities of data. We evaluate the scalability and accuracy of our method on real graphs, where our method facilitates graph processing while producing more deterministic orderings. We show that the proposed approach is capable of revealing anomalies in a more efficient manner based on node rankings. Furthermore, our method can produce visual representations of graphs that are useful for graph compression.
History
Event
European Machine Learning and Data Mining. Conference (15th : 2016 : Riva del Garda, Italy)Volume
9852Series
European Machine Learning and Data Mining ConferencePagination
162 - 178Publisher
SpringerLocation
Riva del Garda, ItalyPlace of publication
Cham, SwitzerlandPublisher DOI
Start date
2016-09-19End date
2016-09-23ISSN
0302-9743eISSN
1611-3349ISBN-13
9783319462264Language
engPublication classification
E1 Full written paper - refereedCopyright notice
2016, Springer International Publishing AGEditor/Contributor(s)
P Frasconi, N Landwehr, G Manco, J VreekenTitle of proceedings
ECML PKDD 2016 : Machine learning and knowledge discovery in databases : Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in DatabasesUsage metrics
Categories
No categories selectedLicence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC