Source-linked AI summary
LUNAR: Unifying Local Outlier Detection Methods via Graph Neural Networks
Adam Goodge, Bryan Hooi, See Kiong Ng, Wee Siong Ng
TL;DR
Unsupervised anomaly detection lacks abundant labeled anomalies, while local outlier methods lack trainable adaptation to particular datasets. The paper unifies these methods through GNN message passing and proposes LUNAR, a learnable anomaly detector. LUNAR outperforms the baselines across varied datasets and is more robust to neighbourhood-size choices, subject to assumptions such as normal training data.
Problem
Local outlier methods lack trainable parameters for dataset-specific adaptation, and their important hyperparameters are difficult to validate without labeled anomalies.
Method
The paper unifies local outlier methods as GNN message-passing cases and uses this framework to develop trainable GNN-based detector LUNAR.
Results
LUNAR significantly outperforms classical and deep-learning baselines across a wide variety of datasets and maintains strong performance across neighbourhood sizes.
Takeaways & Limitations
Learnable use of incoming neighbour information makes LUNAR more adaptable across datasets and neighbourhood-size settings than local outlier methods.
Takeaways & Limitations
The method assumes training samples are normal and searches for nearest neighbours only among those training samples.
Abstract
from arXiv · showhide
Many well-established anomaly detection methods use the distance of a sample to those in its local neighbourhood: so-called `local outlier methods', such as LOF and DBSCAN. They are popular for their simple principles and strong performance on unstructured, feature-based data that is commonplace in many practical applications. However, they cannot learn to adapt for a particular set of data due to their lack of trainable parameters. In this paper, we begin by unifying local outlier methods by showing that they are particular cases of the more general message passing framework used in graph neural networks. This allows us to introduce learnability into local outlier methods, in the form of a neural network, for greater flexibility and expressivity: specifically, we propose LUNAR, a novel, graph neural network-based anomaly detection method. LUNAR learns to use information from the nearest neighbours of each node in a trainable way to find anomalies. We show that our method performs significantly better than existing local outlier methods, as well as state-of-the-art deep baselines. We also show that the performance of our method is much more robust to different settings of the local neighbourhood size.
1 Introduction
Unsupervised anomaly detection is important because anomalies are rare and labeled examples are difficult to obtain. The paper unifies local outlier methods through GNN message passing and introduces learnable LUNAR, which improves performance and neighbourhood-size robustness.
- Unsupervised anomaly detection finds anomalies without ground-truth labels, which are difficult to obtain because anomalies are rare.
- Local outlier methods use distances to nearest neighbours and remain popular for their straightforward principles, interpretable outputs, and performance on feature-based data.
- Many local outlier methods, including KNN, LOF, and DBSCAN, are particular cases of a general GNN message-passing framework.
- LUNAR uses trainable GNN parameters to learn and adapt anomaly scoring to a given dataset, addressing local methods' lack of learnability.
- LUNAR performs better than popular classical and state-of-the-art deep methods, while being more robust to different local neighbourhood sizes.
- Local methods include KNN's kth-neighbour distance, DBSCAN's within-radius point count, and LOF's comparison of local densities.
3 Background
Local outlier methods score points using distances or density relationships among nearest neighbours. GNNs provide a message-passing framework that sends, aggregates, and updates neighbourhood information.
- Local Outlier Methods: Local outlier methods determine anomalousness from a point's distance to its k nearest neighbours.
- Local Outlier Methods: KNN assigns each point an anomaly score equal to its distance from its kth nearest neighbour.
- Local Outlier Methods: LOF uses reachability distance and local reachability density, then compares a point's density with those of neighbouring points.
- Graph Neural Networks: GNN message passing consists of message, aggregation, and update functions operating over connected nodes.
- Graph Neural Networks: The message function sends neighbour information, aggregation summarises incoming messages, and update combines that summary with the node representation.
4 Problem Definition
The paper considers unsupervised anomaly detection with normal training samples and potentially normal or anomalous test samples. Its central question is how nearest-neighbour distances should determine anomaly scores, motivating a message-passing formulation.
- The training set contains m normal samples x^(train)_n ∈ R^d, while each test sample may be normal or anomalous.
- The algorithm outputs an anomaly score s(x^(test)_i) that is low for normal samples and high for anomalous samples.
- For local outlier methods, the central problem is deciding how distances from a test sample to its nearest neighbours should contribute to its anomaly score.
- The paper shows that many local outlier methods can be represented as particular cases of the GNN message-passing framework.
5 Unifying Framework
Local outlier methods can be represented as graph neural network message-passing procedures over nearest-neighbour graphs. KNN is a one-layer case, while LOF and DBSCAN use two rounds of message passing.
- Graph construction: Each sample is a graph node connected by directed edges to its k nearest neighbours, with edge features equal to pairwise distances.Information flows from neighbour j to target i along edge (j, i).
- Other local outlier methods: Table 1 formalizes how local outlier methods relate to the message-passing framework.The table caption specifies that H denotes the Heaviside function.
- KNN as message passing: KNN collects neighbour distances, applies max-pooling, and uses the aggregated value as the anomaly score.This implements KNN within the message, aggregation, and update stages.
- KNN as message passing: KNN is a special case of the general message-passing scheme.The proposition follows by substituting KNN’s message, aggregation, and update functions into the framework.
- Other local outlier methods: LOF and DBSCAN can likewise be represented as two-layer methods using two rounds of message passing.For LOF, the first layer computes local reachability density and the second computes the local outlier score.
6 Motivation: The Importance of Learnability
A toy experiment shows that fixed local-outlier heuristics can behave poorly under different neighbourhood sizes. LUNAR’s learnability produces scores that fit the training data more closely and remain more robust across k.
- Experimental setup: The experiment compares LOF and LUNAR on 1000 points from four Gaussian distributions plus 15 uniformly sampled sparse points.The sparse points are intended to represent anomalies without substantially influencing the predicted regions.
- Experimental setup: The methods are tested with both small and large values of k, the nearest-neighbour hyperparameter.Figure 1 uses blue for low scores, red for high scores, and red squares for the top 15 anomaly scores.
- LOF behaviour: With low k, LOF incorrectly assigns low scores to sparse regions far from the clusters, including the central outlying region.The relative sparsity of the few central points strongly influences the score.
- LOF behaviour: With large k, LOF incorrectly assigns a high score to the smaller bottom-left cluster because it contains fewer points than k.LOF fails to recognise that cluster under this neighbourhood setting.
- LUNAR behaviour: LUNAR performs better and more robustly across k, fitting normal and anomalous regions more closely to the training data.Its highest anomaly scores more accurately identify the sparse central points.
7 LUNAR: Methodology
LUNAR represents feature-based data as a nearest-neighbour graph and learns anomaly scores by processing neighbour distances with a graph neural network. It combines learnable aggregation with synthetic negative samples and has theoretical transformation-equivariance properties.
- Graph formulation: LUNAR represents each data sample as a graph node connected to its k nearest neighbours, using pairwise distances as edge features.Nearest neighbours are searched only among normal training samples so anomalies cannot influence the neighbourhood.
- Model design: LUNAR constructs k-NN graphs for feature-based tabular datasets, uses distance inputs instead of feature vectors, and learns its message aggregation function.These choices distinguish it from typical GNN implementations described in the paper.
- Learnable aggregation: Unlike fixed averaging or max-pooling, LUNAR concatenates the k neighbour distances and maps them through a neural network with learnable weights.The resulting scalar represents the anomalousness of node i.
- Negative sampling: Negative samples provide artificial anomalies so the network can learn to distinguish normal samples from anomalous ones rather than outputting zero for every training point.The paper combines uniform samples with more difficult samples generated by perturbing normal data in feature subspaces.
- Computational runtime: 33.71 seconds for LUNAR versus 55.92 seconds for DAGMM on HRSS illustrates the reported runtime advantage over the tested deep methods.The paper attributes this to training on distances rather than directly on high-dimensional feature data.
- Theoretical properties: Distance-preserving transformations leave the anomaly score equivariant, including rotations, translations, and reflections.The property follows because local outlier methods use distances or reachability distances rather than input features in other ways.
8 Experiments
Experiments evaluate LUNAR against classical and deep anomaly-detection baselines, its robustness to neighbourhood size, and ablations of negative samples and network architecture. LUNAR achieves the strongest overall performance and is substantially less sensitive to k than local outlier methods.
- Experimental setup: Experiments use publicly available datasets containing normal and anomaly classes, with unsupervised training on normal samples and AUC as the evaluation metric.The test set uses a 50:50 normal-to-anomaly ratio, and reported results average five trials with different random seeds.
- RQ1: Accuracy: LUNAR gives the best performance on every dataset except SATELLITE, where KNN is slightly better.On HRSS, MI-V, and THYROID, LUNAR exceeds the second-best method by 10–30 percentage points; marked scores are significantly better at p < 0.01.
- RQ2: Robustness to neighbourhood size: As k increases from 2 to 200 on HRSS, LOF, KNN, and DN2 drop by 26, 24, and 25 percentage points, respectively, while LUNAR drops by 3 points.LUNAR performs best across the vast majority of datasets and k settings.
- RQ2: Robustness to neighbourhood size: LUNAR maintains stronger performance across k because it learns from all neighbour information rather than using a preset aggregation rule that discards information.The compared local methods also determine anomalousness from the k nearest neighbours.
- RQ3: Ablation study: Mixing Subspace Perturbation and Uniform negative samples gives the best performance in most cases, although Subspace Perturbation alone performs poorly for small k on OPTDIGITS.The ablation compares SP, U, and mixed negative-sample formulations.
- RQ3: Ablation study: Deeper and wider networks for message aggregation achieve the best performance in the network-size and depth ablations.Additional studies are reported in the supplementary material.
9 Conclusion
The paper unifies many local outlier methods as instances of GNN message passing and uses that framework to develop LUNAR. LUNAR learns to adapt to datasets, significantly outperforms the baselines across varied datasets, and remains stronger across neighbourhood sizes.
- Framework: Many local outlier methods, including KNN, LOF, and DBSCAN, are particular cases of a common GNN message-passing framework.The framework provides a unified view of methods based on distances to nearest neighbours.
- LUNAR: LUNAR uses the shared framework with a graph neural network to learn and adapt to different datasets.Its design addresses the fixed, non-adaptive nature of conventional local outlier methods.
- Results: LUNAR significantly outperforms classical and deep-learning baselines across a wide variety of datasets.The conclusion reports this as the principal empirical outcome.
- Results: LUNAR maintains strong performance across different neighbourhood sizes by learning from all incoming neighbour information.Other local outlier methods are less robust to neighbourhood-size changes.
Supplementary Material
The supplementary-material passage provides the paper’s arXiv identifier, version, subject classification, and posting date.
- The paper is identified as arXiv:2112.05355v1.
- The record assigns the paper the cs.LG subject classification.
- The version was posted on 10 December 2021.
1 Local Outlier Methods
The supplied passages contain fragmented method labels and notation from the local-outlier-method discussion, without enough connected prose to summarize the section reliably.
- Local outlier methods: The supplied fragments mention SIMPLE-LOF and LOOP alongside distance-based notation, but do not explain their roles or relationships.The copyright notice is not substantive section content.
2 Experiments
The experiments evaluate LUNAR’s significance, variability, runtime, sampling choices, and network architecture. Across these analyses, LUNAR generally outperforms comparison methods and remains comparatively robust to neighbourhood-size changes.
- Statistical Significance: LUNAR significantly outperforms the second-best baseline on most datasets according to the reported Wilcoxon and t-tests.The tests compare LUNAR with the best competing method for each dataset using k = 100 for local outlier methods.
- Statistical Significance: Most reported dataset comparisons show extremely small p values, with SATELLITE the main exception in the tabulated results.The SATELLITE row includes an unmarked value of 0.64070398 in the supplied significance values.
- Runtime: Runtime measurements show that LUNAR is faster than every other tested deep method across all datasets.Average runtimes are measured over five trials with k = 100 for local outlier methods.
- Architecture: Wider aggregation layers and deeper networks generally improve LUNAR’s performance across k values for most datasets.The width comparison uses hidden-layer sizes 64 and 128 against the main-paper setting of 256; the depth comparison varies 2 and 3 layers against 4 in the main experiments.