OutRank: A GRAPH-BASED OUTLIER DETECTION FRAMEWORK USING RANDOM WALK

H.d.k. Moonesinghe, Pang‐Ning Tan

TL;DR

This paper introduces OutRank, a novel graph-based outlier detection framework that leverages random walks on a Markov chain to identify outliers. OutRank effectively detects both isolated outliers and small clusters of outliers, outperforming existing distance- and density-based methods by achieving higher detection rates and lower false alarm rates.

What Problem Does This Paper Address?

Traditional outlier detection methods often struggle with datasets exhibiting varying densities or containing small, localized clusters of outliers. Many existing algorithms rely on distance or density measures within a predefined neighborhood, which can lead to misclassification when outliers have similar densities to normal points or when trying to identify subtle outlier groups. This paper addresses the challenge of detecting outliers that are not necessarily far from all other points but might be "different" in a more global sense, including those forming small, dense clusters that are hard to distinguish from normal data.

Methods

The core of OutRank is a graph-based approach where data objects are represented as nodes and similarities between objects are represented as weighted edges. This graph is then transformed into a transition probability matrix for a Markov chain, simulating a random walk. The "outlierness" of an object is determined by its stationary distribution (connectivity score) derived from this Markov chain.

Two main variants of OutRank are proposed:

  • OutRank-a (Object Similarity): This variant constructs the graph based on direct similarity measures between objects, such as Cosine Similarity or RBF Kernel. The transition matrix is derived from these similarity scores.
  • OutRank-b (Shared Neighbors): This variant defines similarity based on the number of shared neighbors between objects, after applying a threshold to filter out low-similarity connections. This approach aims to better isolate outliers by focusing on higher-order relationships.

The stationary distribution is computed using an iterative power method, which converges to the dominant eigenvector of the transition matrix. The paper also introduces a data-driven method for selecting the threshold in OutRank-b, based on the mean and standard deviation of similarity values.

Datasets

The paper evaluates OutRank on a combination of synthetic and real-world datasets:

  • 2D-Data: A synthetic dataset designed to have multiple clusters of normal points and several small clusters of outliers, with some normal clusters having similar densities to outliers.
  • Real-world datasets: Austra, Zoo, Diabetic, Led7, Lymph, Pima, Vehicle, Optical, and KDD-99 (intrusion data). These datasets are sourced from the UCI KDD archive and vary in dimensionality, number of instances, and the presence of multiple normal clusters.

Key Insights and Ideas

  • Global Perspective for Outlier Detection: By modeling data as a graph and using random walks, OutRank captures a global view of object relationships, allowing it to detect outliers that might be missed by local neighborhood-based methods.
  • Robustness to Varying Densities: The random walk approach is shown to be more robust to datasets with varying densities, a common challenge for density-based methods.
  • Effective Detection of Outlier Clusters: OutRank excels at identifying small clusters of outliers, which are often indicative of interesting events like attacks in intrusion detection systems.
  • Shared Neighbors for Enhanced Discrimination: The OutRank-b variant, using shared neighbors, further enhances outlier detection by creating a sharper distinction between outlier and normal nodes in the connectivity scores.
  • Automatic Thresholding: The data-driven threshold selection for OutRank-b is a significant advantage, reducing the need for manual parameter tuning, which is often a difficult task for other algorithms.

Key Results

  • Superior Performance: OutRank consistently outperforms existing distance-based (K-dist) and density-based (LOF) algorithms across various datasets.
  • Higher Precision and Lower False Alarm Rate: Empirical studies show significant improvements in detection rate (precision) and a substantial reduction in false alarm rates for OutRank compared to other methods. For instance, on the 2D-Data synthetic dataset, OutRank achieved a precision of 1.0 with a 0.0000 false alarm rate.
  • OutRank-b Advantage: The shared neighbor approach (OutRank-b) generally provides a 20% improvement in precision over OutRank-a and a significant reduction in false alarm rates on several datasets.
  • Robustness to Outlier Percentage: The performance of OutRank-b remains relatively stable even when the percentage of outliers in the dataset varies.

Limitations and Future Work

  • Choice of Similarity Measure: While Cosine Similarity performed well, the paper notes that it might not effectively handle outliers co-aligned with normal points. The RBF kernel was explored as an alternative, but in some cases, it led to lower precision compared to Cosine Similarity.
  • Parameter Sensitivity (OutRank-b): While the threshold selection for OutRank-b is data-driven, the paper acknowledges that the choice of threshold T can influence performance, though it is less sensitive than parameters in other algorithms.
  • Future Work: The authors suggest exploring random walk methods in a semi-supervised setting and investigating their application for detecting anomalous substructures in graph databases. They also plan to further explore random walk based methods in a semi-supervised setting.

Summary updated

Abstract

This paper introduces a stochastic graph-based algorithm, called OutRank, for detecting outliers in data. We consider two approaches for constructing a graph representation of the data, based on the object similarity and number of shared neighbors between objects. The heart of this approach is the Markov chain model that is built upon this graph, which assigns an outlier score to each object. Using this framework, we show that our algorithm is more robust than the existing outlier detection schemes and can effectively address the inherent problems of such schemes. Empirical studies conducted on both real and synthetic data sets show that significant improvements in detection rate and false alarm rate are achieved using the proposed framework.
BibTeX
@article{moonesinghe2008outrank,
  author = {H.D.K. Moonesinghe and Pang‐Ning Tan},
  title = {{OutRank: A GRAPH-BASED OUTLIER DETECTION FRAMEWORK USING RANDOM WALK}},
  journal = {International Journal of Artificial Intelligence Tools},
  year = {2008},
  doi = {10.1142/s0218213008003753},
}
Figure