A Survey on Social Media Anomaly Detection <s> Activity-based Group Anomaly Detection <s> We introduce a theory of scan statistics on graphs and apply the ideas to the problem of anomaly detection in a time series of Enron email graphs. <s> BIB001 </s> A Survey on Social Media Anomaly Detection <s> Activity-based Group Anomaly Detection <s> Statistical anomaly detection typically focuses on finding individual point anomalies. Often the most interesting or unusual things in a data set are not odd individual points, but rather larger scale phenomena that only become apparent when groups of points are considered. In this paper, we propose generative models for detecting such group anomalies. We evaluate our methods on synthetic data as well as astronomical data from the Sloan Digital Sky Survey. The empirical results show that the proposed models are effective in detecting group anomalies. <s> BIB002 </s> A Survey on Social Media Anomaly Detection <s> Activity-based Group Anomaly Detection <s> An important task in exploring and analyzing real-world data sets is to detect unusual and interesting phenomena. In this paper, we study the group anomaly detection problem. Unlike traditional anomaly detection research that focuses on data points, our goal is to discover anomalous aggregated behaviors of groups of points. For this purpose, we propose the Flexible Genre Model (FGM). FGM is designed to characterize data groups at both the point level and the group level so as to detect various types of group anomalies. We evaluate the effectiveness of FGM on both synthetic and real data sets including images and turbulence data, and show that it is superior to existing approaches in detecting group anomalies. <s> BIB003 </s> A Survey on Social Media Anomaly Detection <s> Activity-based Group Anomaly Detection <s> We propose a novel approach which combines the use of Bayesian network and probabilistic association rules to discover and explain anomalies in data. The Bayesian network allows us to organize information in order to capture both correlation and causality in the feature space, while the probabilistic association rules have a structure similar to association mining rules. In particular, we focus on two types of rules: (i) low support & high confidence and, (ii) high support & low confidence. New data points which satisfy either one of the two rules conditioned on the Bayesian network are the candidate anomalies. We perform extensive experiments on well-known benchmark data sets and demonstrate that our approach is able to identify anomalies in high precision and recall. Moreover, our approach can be used to discover contextual information from the mined anomalies, which other techniques often fail to do so. <s> BIB004 </s> A Survey on Social Media Anomaly Detection <s> Activity-based Group Anomaly Detection <s> We propose one-class support measure machines (OCSMMs) for group anomaly detection which aims at recognizing anomalous aggregate behaviors of data points. The OCSMMs generalize well-known one-class support vector machines (OCSVMs) to a space of probability measures. By formulating the problem as quantile estimation on distributions, we can establish an interesting connection to the OCSVMs and variable kernel density estimators (VKDEs) over the input space on which the distributions are defined, bridging the gap between large-margin methods and kernel density estimators. In particular, we show that various types of VKDEs can be considered as solutions to a class of regularization problems studied in this paper. Experiments on Sloan Digital Sky Survey dataset and High Energy Particle Physics dataset demonstrate the benefits of the proposed framework in real-world applications. <s> BIB005
Activity-based group anomaly detection approaches usually assume that the group information is given beforehand and devote the most effort to model the activities within groups. Those approaches also imply that groups are marginal independent with each other. [19] proposes a probabilistic model to detect group of anomalies in categorical data sets. It generalizes the spatial scan statistic in BIB001 for dynamic graphs to non-spatial data sets with discrete valued attributes. It uses Bayesian networks to model the relationship between the attributes and computes the group score for all subsets of the data S based on the model likelihood: F (S) = P (Data|H 1 (S) P (Data|H 0 ) . Under this definition, H 0 is the null hypothesis that no anomalies are present, and H 1 (S) is the alternative hypothesis specifying subset S is an anomalous group. Then it performs a heuristic search over arbitrary subsets of the data to find the groups that maximize the likelihood. At the final stage, it performs randomization testing to evaluate the statistical significance of the detected groups. For spatial data, the computation of scan statistics involves a definition of scanning region, which is often based on geographical properties. Non-spatial categorical data has the difficulty in defining local statistics based on geographical properties. Therefore, the efficient search heuristic is critical to the performance of algorithm. On the other hand, it lacks the solid theoretical justification and is sensitive to model mis-specification. [18] considers the anomalies in categorical data sets and tries to detect anomalous attributes or combinations of attributes. The paper proposes two algorithms to test for anomalous records, i.e Conditional Probability Test and Marginal Probability Test. Conditional probability test uses conditional probability as the testing statistic. For two attributes a t , b t , the algorithm considers the ration r(a t , b t ) = P (at)P (bt) P (at,bt) . Marginal probability computes a quantity called the q-value, which is the cumulative probability mass of all the attributes q-val(a t ) = x∈X P (x) where X = {x : P (x) ≤ P (a t )}. Q-value is in parallel with the p-value. This approach concerns with empirical distribution functions and is parameter free. But the underlying distributions of the attributes would heavily depend on the sample size of the data. Another line of work formulates the group anomaly detection problem as a density estimation task. It imposes a hierarchical probabilistic model on the normal groups and estimates the distribution of the latent variables in the model. It evaluates the likelihood of the estimated latent variables for individual group and use it as a test statistic. The Multinomial Genre Model (MGM) proposed in BIB002 first investigates the problem following the paradigm of latent models. MGM models groups as a mixture of Gaussian distributions with different mixture rates. Formally, given M groups, each of which has N m objects. MGM assumes that the object features X m.n are generated from a mixture of K Gaussian, m = 1, 2, · · · , M , n = 1, 2, · · · , N m with a set of stereotypical mixture rates χ. The mixture rates of the M groups belong to one of the stereotypical mixture rates in χ. Figure 3 .1 depicts the graphical model of the proposed model. The method then performs Bayesian inference to estimate the density of the mixture rate for each group. Then group anomaly detection is conducted by scoring the mixture rate likelihood of each group. This method finds groups whose topic variables {Z m , n} are not compatible with any of the stereo-typical topic distributions in χ. In MGM, groups share the candidate topics β globally, which leads to bad performance when groups have different sets of topics. BIB003 further extends MGM to Flexible Genre Model (FGM) with more flexibility in the generation of topic distributions, as shown in Figure 4 . The motivation of FGM is to allow each group to have its own topics. Specifically, they change the set of topics β from model hyper-parameters to random variables, depending on the genre parameter η. This extension enables the model to adapt to more diverse genres in groups. Apart from the generative approach used in MGM and FGM, BIB005 takes a discriminative approach to estimate the density of the mixture model. It uses the same definition of group anomaly from BIB002 and represents groups as probability distributions. The authors consider kernel embedding of those probabilistic distributions. For two probabilities P 1 and P 2 , the kernel on probability distributions is defined as K(P 1 , P 2 ) = k(x, y)dP i (x)dP j (y), where k is a reproducing kernel in reproducing kernel Hilbert space (RKHS). They generalize the technique of one-class support vector machine (OCSVM) for point anomaly detection to group anomaly detection. Similar to OCSVM with translation invariant kernels, the authors compute the kernel of Gaussian distributions and apply SVM in a probability measure space. Interestingly, the proposed one class support measure machine (OCSMM) algorithm has inherent correspondence to the kernel density estimation, which is theoretically more attractive. Compared with generative approaches in BIB002 BIB003 , OCSMM does not make assumptions on the underlying distribution of the data and is generally less computational expensive. However, due to the use of Gaussian RBF kernels and support vector machine, the algorithm is inevitably sensitive to the selection of kernels as well as the soft margin parameter. BIB004  and a covariance matrix (β Σ i ∈ R f ×f ), and our observations are given by: We call this model Gaussian-LDA (GLDA). With GLDA we can model real, vector-valued observations, but it has a serious problem when we want to apply it for group anomaly detection. GLDA learns that each group is a certain mixture of K Gaussian components, but it also assumes that there is only one "best" mixture (topic distribution) for all groups, because Dir(π), the distribution of topic distributions θ ∈ S K , is uni-modal i.e. it peaks at a single point. While this is acceptable when used as the prior in LDA, it is too restrictive when used to model multimodal distributions of topic distributions. To address this issue we extend the GLDA model with the previously mentioned χ term, the set of the typical topic distributions (proportions of the Gaussian components).