Efficient anomaly detection using bipartite k-NN graphs
Learning minimum volume sets of an underlying nominal distribution is a very effective approach to anomaly detection. Several approaches to learning minimum volume sets have been proposed in the literature, including the K-point nearest neighbor graph (K-kNNG) algorithm based on the geometric entropy minimization (GEM) principle [4]. The K-kNNG detector, while possessing several desirable characteristics, suffers from high computation complexity, and in [4] a simpler heuristic approximation, the leave-one-out kNNG (L1O-kNNG) was proposed. In this paper, we propose a novel bipartite k-nearest neighbor graph (BP-kNNG) anomaly detection scheme for estimating minimum volume sets. Our bipartite estimator retains all the desirable theoretical properties of the K-kNNG, while being computationally simpler than the K-kNNG and the surrogate L1O-kNNG detectors. We show that BP-kNNG is asymptotically consistent in recovering the p-value of each test point. Experimental results are given that illustrate the superior performance of BP-kNNG as compared to the L1O-kNNG and other state of the art anomaly detection schemes.
Code (0)
등록된 구현이 없습니다.
Tasks
Anomaly DetectionSimilar Papers 제목 키워드 기반
Event2Graph: Event-driven Bipartite Graph for Multivariate Time-series Anomaly Detection
Modeling inter-dependencies between time-series is the key to achieve high performance in anomaly detection for multivariate time-series data. The de-facto solution to model the dependencies is to feed the data into a re…
Anomaly DetectionTime SeriesTime Series AnalysisTime Series Anomaly DetectionWBT-BGRL: A Non-Contrastive Weighted Bipartite Link Prediction Model for Inductive Learning
Link prediction in bipartite graphs is crucial for applications like recommendation systems and failure detection, yet it is less studied than in monopartite graphs. Contrastive methods struggle with inefficient and bias…
Inductive Link PredictionRecommendation SystemsContrastive LearningParameterized Correlation Clustering in Hypergraphs and Bipartite Graphs
Motivated by applications in community detection and dense subgraph discovery, we consider new clustering objectives in hypergraphs and bipartite graphs. These objectives are parameterized by one or more resolution param…
ClusteringCommunity DetectionGraph ClusteringSAD: Semi-Supervised Anomaly Detection on Dynamic Graphs
Anomaly detection aims to distinguish abnormal instances that deviate significantly from the majority of benign ones. As instances that appear in the real world are naturally connected and can be represented with graphs,…
Anomaly DetectionContrastive LearningPseudo LabelSemi-supervised Anomaly Detection+1Anomaly Detection in Dynamic Graphs: A Comprehensive Survey
This survey paper presents a comprehensive and conceptual overview of anomaly detection using dynamic graphs. We focus on existing graph-based anomaly detection (AD) techniques and their applications to dynamic networks.…
Anomaly DetectionGraph MiningSurvey