Deakin University
Browse

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 Ramamohanarao
Anomaly 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

Volume

9852

Pagination

162-178

Location

Riva del Garda, Italy

Start date

2016-09-19

End date

2016-09-23

ISSN

0302-9743

eISSN

1611-3349

ISBN-13

9783319462264

Language

eng

Publication classification

E1 Full written paper - refereed

Copyright notice

2016, Springer International Publishing AG

Editor/Contributor(s)

Frasconi P, Landwehr N, Manco G, Vreeken J

Title 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 Databases

Event

European Machine Learning and Data Mining. Conference (15th : 2016 : Riva del Garda, Italy)

Publisher

Springer

Place of publication

Cham, Switzerland

Series

European Machine Learning and Data Mining Conference