In this paper we consider the task of detecting abnormal communication volume occurring at node-level in communication networks. The signal of the communication activity is modeled by means of a clique stream: each occurring communication event is instantaneous and activates an undirected subgraph spanning over a set of equally participating nodes. We present a probabilistic framework to model and assess the communication volume observed at any single node. Specifically, we employ non-parametric regression to learn the probability that a node takes part in a certain event knowing the set of other nodes that are involved. On the top of that, we present a concentration inequality around the estimated volume of events in which a node could participate, which in turn allows us to build an efficient and interpretable anomaly scoring function. Finally, the superior performance of the proposed approach is empirically demonstrated in real-world sensor network data, as well as using synthetic communication activity that is in accordance with that latter setting.
A feature-based approach for detecting anomalies in such time-series of graphs, is to compute several graph features for each @math , such as the node degree or centrality, and then apply standard anomaly detection techniques on the derived multivariate time-series of these features @cite_3 @cite_19 @cite_10 . More generally, the literature of anomaly detection in time-series of graphs varies in three aspects: : Semi-supervised (access to a dataset of system operation) @cite_25 @cite_23 @cite_1 or unsupervised (no label available) @cite_4 @cite_11 . : Probabilistic model-based @cite_6 @cite_26 @cite_30 @cite_7 @cite_9 @cite_27 @cite_22 , distance based @cite_4 , decomposition-based @cite_0 @cite_5 , compression-based @cite_13 , : Node Edge-level @cite_18 @cite_22 , subgraph-level @cite_27 , or whole network-level @cite_7 . The reader should refer to @cite_16 for a more detailed survey on anomaly detection in dynamic graphs.
@cite_30 @cite_22 @cite_3 @cite_5 @cite_10 @cite_18 @cite_4 @cite_23 @cite_26 @cite_7 @cite_6 @cite_19 @cite_27 @cite_16 @cite_25 @cite_9 @cite_1 @cite_0 @cite_13 @cite_11
1964274671 2026565928 1961165281 2949350626
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. Learning the network structure of a large graph is computationally demanding, and dynamically monitoring the network over time for any changes in structure threatens to be more challenging still. This paper presents a two-stage method for anomaly detection in dynamic graphs: the first stage uses simple, conjugate Bayesian models for discrete time counting processes to track the pairwise links of all nodes in the graph to assess normality of behavior; the second stage applies standard network inference tools on a greatly reduced subset of potentially anomalous nodes. The utility of the method is demonstrated on simulated and real data sets. This work presents a novel modeling and analysis framework for graph sequences which addresses the challenge of detecting and contextualizing anomalies in labeled, streaming graph data. We introduce a generalization of the BTER model of by adding flexibility to community structure, and use this model to perform multi-scale graph anomaly detection. Specifically, probability models describing coarse subgraphs are built by aggregating node probabilities, and these related hierarchical models simultaneously detect deviations from expectation. This technique provides insight into the graphs' structure and helps contextualized detected event. For evaluation, two new hierarchical detectors are tested against a baseline Gaussian method on a synthetic graph sequence with seeded anomalies. We demonstrate that in a labeled setting with community structure, our graph statistics-based approach outperforms both a distribution-based detector and the baseline, accurately detecting anomalies at the node, subgraph, and graph levels. This paper introduces a novel graph-analytic approach for detecting anomalies in network flow data called GraphPrints. Building on foundational network-mining techniques, our method represents time slices of traffic as a graph, then counts graphlets -- small induced subgraphs that describe local topology. By performing outlier detection on the sequence of graphlet counts, anomalous intervals of traffic are identified, and furthermore, individual IPs experiencing abnormal behavior are singled-out. Initial testing of GraphPrints is performed on real network data with an implanted anomaly. Evaluation shows false positive rates bounded by 2.84 at the time-interval level, and 0.05 at the IP-level with 100 true positive rates at both.