Wed, 10/02/2013 - 11:59 — zhe.yao

Title | Anomaly Detection using Proximity Graph and PageRank Algorithm |

Publication Type | Journal Article |

Year of Publication | 2012 |

Authors | Yao, Z., P. Mark, and M. G. Rabbat |

Journal | IEEE Transactions on Information Forensics and Security |

Volume | 7 |

Issue | 4 |

Start Page | 1288 |

Date Published | 08/2012 |

Keywords | Anomaly Detection, Personalized PageRank, Proximity Graph |

Abstract | Anomaly detection techniques are widely used in a variety of applications, e.g., computer networks, security systems, etc. This paper describes and analyzes an approach to anomaly detection using proximity graphs and the PageRank algorithm. We run a variant of the PageRank algorithm on top of a proximity graph comprised of data points as vertices, which produces a score quantifying the extent to which each data point is anomalous. Previous work in this direction requires first forming a density estimate using the training data, e.g., using kernel methods, and this step is very computationally intensive for high-dimensional data sets. Under mild assumptions and appropriately chosen parameters, we show that PageRank produces point-wise consistent probability density estimates for the data points in an asymptotic sense, and with much less computational effort. As a result, big improvements in terms of running time are witnessed while maintaining similar detection performance. Experiments with synthetic and real-world data sets illustrate that the proposed approach is computationally tractable and scales well to large high-dimensional data sets. |

Attachment | Size |
---|---|

yao2012pagerank.pdf | 1.19 MB |

- Login to post comments
- Tagged
- XML
- BibTex
- Google Scholar