The extraction of clusters from a dataset which includes multiple clusters and another significant portion of "background" samples is a task of practical importance. The traditional spectral clustering algorithm, relying on the leading @math eigenvectors to detect the @math clusters, fails in such cases. This paper proposes the spectral embedding norm which sums the squared values of the first @math (normalized) eigenvectors, where @math can be larger than @math . We prove that the quantity can be used to separate clusters from the background under generic conditions motivated by applications such as anomaly detection. The performance of the algorithm is not sensitive to the choice of @math , and we present experiments on synthetic and real-world datasets.
Spectral methods for anomaly detection . The following papers have employed spectral embeddings for anomaly detection in different applications: in images @cite_40 @cite_22 , fraud detection @cite_9 , in graphs @cite_42 @cite_39 , sensor networks @cite_3 , computer systems @cite_38 and in general applications @cite_6 @cite_17 @cite_30 . For a general review of anomaly detection methods, the interested reader is referred to @cite_25 @cite_7 @cite_34 . As has been shown in @cite_39 @cite_31 @cite_9 @cite_42 , and we will demonstrate, the eigenvectors in an anomaly setting can lie deep within the spectrum of the affinity matrix. This gives rise to the notion of abandoning the guideline of focusing on @math eigenvectors and rather choosing to look deeper into the spectrum, both for clustering and for anomaly detection. Similar to the embedding norm which we propose, the square sum of principle components (called leverage score'') has been used in a different setting as a indicator of outlier sample points for linear regression and other applications in statistics @cite_13 .
@cite_30 @cite_38 @cite_22 @cite_7 @cite_9 @cite_42 @cite_3 @cite_39 @cite_6 @cite_40 @cite_31 @cite_34 @cite_13 @cite_25 @cite_17
2227768973 1964274671 2695617904 2337344967 2333568743 2075861172 2406320566 2162384258 2964175430 1963586106 1583657896 2089554624 1983350937 2122646361
Dimensionality reduction methods are very common in the field of high dimensional data analysis. Typically, algorithms for dimensionality reduction are computationally expensive. Therefore, their applications for the analysis of massive amounts of data are impractical. For example, repeated computations due to accumulated data are computationally prohibitive. In this paper, an out-of-sample extension scheme, which is used as a complementary method for dimensionality reduction, is presented. We describe an algorithm which performs an out-of-sample extension to newly-arrived data points. Unlike other extension algorithms such as Nystr "om algorithm, the proposed algorithm uses the intrinsic geometry of the data and properties for dimensionality reduction map. We prove that the error of the proposed algorithm is bounded. Additionally to the out-of-sample extension, the algorithm provides a degree of the abnormality of any newly-arrived data point. We report on an automated runtime anomaly detection method at the application layer of multi-node computer systems. Although several network management systems are available in the market, none of them have sufficient capabilities to detect faults in multi-tier Web-based systems with redundancy. We model a Web-based system as a weighted graph, where each node represents a "service" and each edge represents a dependency between services. Since the edge weights vary greatly over time, the problem we address is that of anomaly detection from a time sequence of graphs.In our method, we first extract a feature vector from the adjacency matrix that represents the activities of all of the services. The heart of our method is to use the principal eigenvector of the eigenclusters of the graph. Then we derive a probability distribution for an anomaly measure defined for a time-series of directional data derived from the graph sequence. Given a critical probability, the threshold value is adaptively updated using a novel online algorithm.We demonstrate that a fault in a Web application can be automatically detected and the faulty services are identified without using detailed knowledge of the behavior of the system. Diffusion maps, when applied to large datasets, are typically constructed by a process of sampling and out-of-sample function extension. However, the performance of anomaly detection in large data when using diffusion maps is sensitive to the chosen samples. In this paper we propose an iterative data-driven approach to improve the sample set and diffusion maps representation. By updating the sample set with suspicious points detected in the previous iteration, the constructed diffusion maps better separate the anomaly from the normal points in each iteration. Experimental results in side-scan sonar images demonstrate the improvement gained by our iterative sampling compared to random sampling and other competing detection algorithms. Anomaly detection is the process of identifying unexpected items or events in datasets, which differ from the norm. In contrast to standard classification tasks, anomaly detection is often applied on unlabeled data, taking only the internal structure of the dataset into account. This challenge is known as unsupervised anomaly detection and is addressed in many practical applications, for example in network intrusion detection, fraud detection as well as in the life science and medical domain. Dozens of algorithms have been proposed in this area, but unfortunately the research community still lacks a comparative universal evaluation as well as common publicly available datasets. These shortcomings are addressed in this study, where 19 different unsupervised anomaly detection algorithms are evaluated on 10 different datasets from multiple application domains. By publishing the source code and the datasets, this paper aims to be a new well-funded basis for unsupervised anomaly detection research. Additionally, this evaluation reveals the strengths and weaknesses of the different approaches for the first time. Besides the anomaly detection performance, computational effort, the impact of parameter settings as well as the global local anomaly detection behavior is outlined. As a conclusion, we give an advise on algorithm selection for typical real-world tasks. Abstract For many data mining problems, obtaining labels is costly and time consuming, if not practically infeasible. In addition, unlabeled data often includes categorical or ordinal features which, compared with numerical features, can present additional challenges. We propose a new unsupervised spectral ranking method for anomaly (SRA). We illustrate that the spectral optimization in SRA can be viewed as a relaxation of an unsupervised SVM problem. We demonstrate that the first non-principal eigenvector of a Laplacian matrix is linked to a bi-class classification strength measure which can be used to rank anomalies. Using the first non-principal eigenvector of the Laplacian matrix directly, the proposed SRA generates an anomaly ranking either with respect to the majority class or with respect to two main patterns. The choice of the ranking reference can be made based on whether the cardinality of the smaller class (positive or negative) is sufficiently large. Using an auto insurance claim data set but ignoring labels when generating ranking, we show that our proposed SRA significantly surpasses existing outlier-based fraud detection methods. Finally we demonstrate that, while proposed SRA yields good performance for a few similarity measures for the auto insurance claim data, notably ones based on the Hamming distance, choosing appropriate similarity measures for a fraud detection problem remains crucial. In this paper we investigate the problem of detecting small and subtle subgraphs embedded into a large graph with a common structure. We call the embedded small and subtle subgraphs as signals or anomalies and the large graph as background. Those small and subtle signals, which are structurally dissimilar to the background, are often hidden within graph communities and cannot be revealed in the graph's global structure. We explore the minor eigenvectors of the graph's adjacency matrix to detect subtle anomalies from a background graph. We demonstrate that when there are such subtle anomalies, there exist some minor eigenvectors with extreme values on some entries corresponding to the anomalies. Under the assumption of the Erdos---Renyi random graph model, we derive the formula that show how eigenvector entries are changed and give detectability conditions. We then extend our theoretical study to the general case where multiple anomalies are embedded in a background graph with community structure. We develop an algorithm that uses the eigenvector kurtosis to filter out the eigenvectors that capture the signals. Our theoretical analysis and empirical evaluations on both synthetic data and real social networks show effectiveness of our approach to detecting subtle signals. We propose a learning framework, which is based on diffusionmethodology, that performs data fusion and anomalydetection in multi-dimensional time series data. Real lifeapplications and processes usually contain a large numberof sensors that generate parameters (features), where eachsensor collects partial information about the running process.These input sensors are fused to describe the behaviorof the whole process. The proposed data fusing algorithmis done in an hierarchial fashion: first it re-scales the inputsensors. Then, the re-formulated inputs are fused togetherby the application of the diffusion maps to reveal the nonlinearrelationships among them. This process constructsby embedding a low-dimensional description of the system.The embedding separates between sensors (parameters) thatcause stable and instable behavior of the system.This unsupervised algorithm first studies the system’sprofile from a training dataset by reducing its dimensions.Then, the coordinates of newly arrived data points are determinedby the application of multi-scale Gaussian approximation.To achieve this, an hierarchial processing of theincoming data is introduced. When working with network datasets, the theoretical framework of detection theory for Euclidean vector spaces no longer applies. Nevertheless, it is desirable to determine the detectability of small, anomalous graphs embedded into background networks with known statistical properties. Casting the problem of subgraph detection in a signal processing context, this article provides a framework and empirical results that elucidate a "detection theory" for graph-valued data. Its focus is the detection of anomalies in unweighted, undirected graphs through L1 properties of the eigenvectors of the graph's so-called modularity matrix. This metric is observed to have relatively low variance for certain categories of randomly-generated graphs, and to reveal the presence of an anomalous subgraph with reasonable reliability when the anomaly is not well-correlated with stronger portions of the background graph. An analysis of subgraphs in real network datasets confirms the efficacy of this approach. Abstract Let ( M , g ) be a compact manifold and let − Δ ϕ k = λ k ϕ k be the sequence of Laplacian eigenfunctions. We present a curious new phenomenon which, so far, we only managed to understand in a few highly specialized cases: the family of functions f N : M → R ≥ 0 f N ( x ) = ∑ k ≤ N 1 λ k | ϕ k ( x ) | ‖ ϕ k ‖ L ∞ ( M ) and their extrema seem strangely suited for the detection of anomalous points on the manifold. It may be heuristically interpreted as the sum over distances to the nearest nodal line and potentially hints at a new phenomenon in spectral geometry. We give rigorous statements on the unit square [ 0 , 1 ] 2 (where minima localize in Q 2 ) and on Paley graphs (where f N recovers the geometry of quadratic residues of the underlying finite field F p ). Numerical examples show that the phenomenon seems to arise on fairly generic manifolds. We propose a multiscale approach to anomaly detection in images, combining spectral dimensionality reduction and a nearest-neighbor-based anomaly score. We use diffusion maps to embed the data in a low dimensional representation, which separates the anomaly from the background. The diffusion distance between points is then used to estimate the local density of each pixel in the new embedding. The diffusion map is constructed based on a subset of samples from the image and then extended to all other pixels. Due to the interpolative nature of extension methods, this may limit the ability of the diffusion map to reveal the presence of the anomaly in the data. To overcome this limitation, we propose a multiscale approach based on Gaussian pyramid representation, which drives the sampling process to ensure separability of the anomaly from the background clutter. The algorithm is successfully tested on side-scan sonar images of sea-mines. We aim to understand and characterize embeddings of datasets with small anomalous clusters using the Laplacian Eigenmaps algorithm. To do this, we characterize the order in which eigenvectors of a disjoint graph Laplacian emerge and the support of those eigenvectors. We then extend this characterization to weakly connected graphs with clusters of differing sizes, utilizing the theory of invariant subspace perturbations and proving some novel results. Finally, we propose a simple segmentation algorithm for anomalous clusters based off our theory. Detecting anomalies in data is a vital task, with numerous high-impact applications in areas such as security, finance, health care, and law enforcement. While numerous techniques have been developed in past years for spotting outliers and anomalies in unstructured collections of multi-dimensional points, with graph data becoming ubiquitous, techniques for structured graph data have been of focus recently. As objects in graphs have long-range correlations, a suite of novel technology has been developed for anomaly detection in graph data. This survey aims to provide a general, comprehensive, and structured overview of the state-of-the-art methods for anomaly detection in data represented as graphs. As a key contribution, we give a general framework for the algorithms categorized under various settings: unsupervised versus (semi-)supervised approaches, for static versus dynamic graphs, for attributed versus plain graphs. We highlight the effectiveness, scalability, generality, and robustness aspects of the methods. What is more, we stress the importance of anomaly attribution and highlight the major techniques that facilitate digging out the root cause, or the why', of the detected anomalies for further analysis and sense-making. Finally, we present several real-world applications of graph-based anomaly detection in diverse domains, including financial, auction, computer traffic, and social networks. We conclude our survey with a discussion on open theoretical and practical challenges in the field. Abstract In least-squares fitting it is important to understand the influence which a data y value will have on each fitted y value. A projection matrix known as the hat matrix contains this information and, together with the Studentized residuals, provides a means of identifying exceptional data points. This approach also simplifies the calculations involved in removing a data point, and it requires only simple modifications in the preferred numerical least-squares algorithms. Anomaly detection is an important problem that has been researched within diverse research areas and application domains. Many anomaly detection techniques have been specifically developed for certain application domains, while others are more generic. This survey tries to provide a structured and comprehensive overview of the research on anomaly detection. We have grouped existing techniques into different categories based on the underlying approach adopted by each technique. For each category we have identified key assumptions, which are used by the techniques to differentiate between normal and anomalous behavior. When applying a given technique to a particular domain, these assumptions can be used as guidelines to assess the effectiveness of the technique in that domain. For each category, we provide a basic anomaly detection technique, and then show how the different existing techniques in that category are variants of the basic technique. This template provides an easier and more succinct understanding of the techniques belonging to each category. Further, for each category, we identify the advantages and disadvantages of the techniques in that category. We also provide a discussion on the computational complexity of the techniques since it is an important issue in real application domains. We hope that this survey will provide a better understanding of the different directions in which research has been done on this topic, and how techniques developed in one area can be applied in domains for which they were not intended to begin with.