A Survey on Social Media Anomaly Detection <s> Static Graph <s> Anomaly detection is an area that has received much attention in recent years. It has a wide variety of applications, including fraud detection and network intrusion detection. A good deal of research has been performed in this area, often using strings or attribute-value data as the medium from which anomalies are to be extracted. Little work, however, has focused on anomaly detection in graph-based data. In this paper, we introduce two techniques for graph-based anomaly detection. In addition, we introduce a new method for calculating the regularity of a graph, with applications to anomaly detection. We hypothesize that these methods will prove useful both for finding anomalies, and for determining the likelihood of successful anomaly detection within graph-based data. We provide experimental results using both real-world network intrusion data and artificially-created data. <s> BIB001 </s> A Survey on Social Media Anomaly Detection <s> Static Graph <s> A significant portion of knowledge discovery and data mining research focuses on finding patterns of interest in data. Once a pattern is found, it can be used to recognize satisfying instances. The new area of link discovery requires a complementary approach, since patterns of interest might not yet be known or might have too few examples to be learnable. We present an unsupervised link discovery method aimed at discovering unusual, interestingly linked entities in multi-relational datasets. Various notions of rarity are introduced to measure the "interestingness" of sets of paths and entities. These measurements have been implemented and applied to a real-world bibliographic dataset where they give very promising results. <s> BIB002 </s> A Survey on Social Media Anomaly Detection <s> Static Graph <s> Graphs arise in numerous applications, such as the analysis of the Web, router networks, social networks, co-citation graphs, etc. Virtually all the popular methods for analyzing such graphs, for example, k-means clustering, METIS graph partitioning and SVD/PCA, require the user to specify various parameters such as the number of clusters, number of partitions and number of principal components. We propose a novel way to group nodes, using information-theoretic principles to choose both the number of such groups and the mapping from nodes to groups. Our algorithm is completely parameter-free, and also scales practically linearly with the problem size. Further, we propose novel algorithms which use this node group structure to get further insights into the data, by finding outliers and computing distances between groups. Finally, we present experiments on multiple synthetic and real-life datasets, where our methods give excellent, intuitive results. <s> BIB003 </s> A Survey on Social Media Anomaly Detection <s> Static Graph <s> Many real applications can be modeled using bipartite graphs, such as users vs. files in a P2P system, traders vs. stocks in a financial trading system, conferences vs. authors in a scientific publication network, and so on. We introduce two operations on bipartite graphs: 1) identifying similar nodes (Neighborhood formation), and 2) finding abnormal nodes (Anomaly detection). And we propose algorithms to compute the neighborhood for each node using random walk with restarts and graph partitioning; we also propose algorithms to identify abnormal nodes, using neighborhood information. We evaluate the quality of neighborhoods based on semantics of the datasets, and we also measure the performance of the anomaly detection algorithm with manually injected anomalies. Both effectiveness and efficiency of the methods are confirmed by experiments on several real datasets. <s> BIB004 </s> A Survey on Social Media Anomaly Detection <s> Static Graph <s> How does the Web look? How could we tell an abnormal social network from a normal one? These and similar questions are important in many fields where the data can intuitively be cast as a graph; examples range from computer networks to sociology to biology and many more. Indeed, any M : N relation in database terminology can be represented as a graph. A lot of these questions boil down to the following: “How can we generate synthetic but realistic graphs?” To answer this, we must first understand what patterns are common in real-world graphs and can thus be considered a mark of normality/realism. This survey give an overview of the incredible variety of work that has been done on these problems. One of our main contributions is the integration of points of view from physics, mathematics, sociology, and computer science. Further, we briefly describe recent advances on some related and interesting graph problems. <s> BIB005 </s> A Survey on Social Media Anomaly Detection <s> Static Graph <s> The ability to mine data represented as a graph has become important in several domains for detecting various structural patterns. One important area of data mining is anomaly detection, particularly for fraud, but less work has been done in terms of detecting anomalies in graph-based data. While there has been some work that has used statistical metrics and conditional entropy measurements, the results have been limited to certain types of anomalies and specific domains. In this paper we present graph- based approaches to uncovering anomalies in domains where the anomalies consist of unexpected entity/relationship deviations that resemble non- anomalous behavior. Using synthetic and real-world data, we evaluate the effectiveness of these algorithms at discovering anomalies in a graph-based representation of data. <s> BIB006 </s> A Survey on Social Media Anomaly Detection <s> Static Graph <s> When monitoring interactions within a social network, meetings or contacts between different members of the network are recorded. This paper addresses the problem of using the recorded meetings to determine (a) whether each meeting is anomalous and (b) the degree to which each meeting is anomalous. Performing robust statistical analysis on such data is particularly challenging when the number of observed meetings is much smaller than the number of people in the network. Our novel approach to anomaly detection in this high-dimensional setting is based on hypergraphs, an important extension of graphs which allows edges to connect more than two vertices simultaneously. In particular, the distribution of meetings is modeled as a two-component mixture of a nominal distribution and a distribution of anomalous events. A variational Expectation-Maximization algorithm is then used to assess the likelihood of each observation being anomalous. The computational complexity of the proposed method scales linearly with both the number of observed events and the number of people in the network, making it well-suited to very large networks, and it requires no tuning. The algorithm is validated on synthetic data and it is shown that, for a useful class of distributions, it can outperform related state-of-the-art methods in terms of both detection performance and computational complexity. <s> BIB007 </s> A Survey on Social Media Anomaly Detection <s> Static Graph <s> The vast majority of earlier work has focused on graphs which are both connected (typically by ignoring all but the giant connected component), and unweighted. Here we study numerous, real, weighted graphs, and report surprising discoveries on the way in which new nodes join and form links in a social network. The motivating questions were the following: How do connected components in a graph form and change over time? What happens after new nodes join a network -- how common are repeated edges? We study numerous diverse, real graphs (citation networks, networks in social media, internet traffic, and others); and make the following contributions: (a) we observe that the non-giant connected components seem to stabilize in size, (b) we observe the weights on the edges follow several power laws with surprising exponents, and (c) we propose an intuitive, generative model for graph growth that obeys observed patterns. <s> BIB008 </s> A Survey on Social Media Anomaly Detection <s> Static Graph <s> Modern applications such as web knowledge base, network traffic monitoring and online social networks have made available an unprecedented amount of network data with rich types of interactions carrying multiple attributes, for instance, port number and time tick in the case of network traffic. The design of algorithms to leverage this structured relationship with the power of computing to assist researchers and practitioners for better understanding, exploration and navigation of this space of information has become a challenging, albeit rewarding, topic in social network analysis and data mining. The constantly growing scale and enriching genres of network data always demand higher levels of efficiency, robustness and generalizability where existing approaches with successes on small, homogeneous network data are likely to fall short. We introduce MultiAspectForensics, a handy tool to automatically detect and visualize novel sub graph patterns within a local community of nodes in a heterogenous network, such as a set of vertices that form a dense bipartite graph whose edges share exactly the same set of attributes. We apply the proposed method on three data sets from distinct application domains, present empirical results and discuss insights derived from these patterns discovered. Our algorithm, built on scalable tensor analysis procedures, captures spectral properties of network data and reveals informative signals for subsequent domain-specific study and investigation, such as suspicious port-scanning activities in the scenario of cyber-security monitoring. <s> BIB009 </s> A Survey on Social Media Anomaly Detection <s> Static Graph <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> BIB010 </s> A Survey on Social Media Anomaly Detection <s> Static Graph <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> BIB011 </s> A Survey on Social Media Anomaly Detection <s> Static Graph <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> BIB012 </s> A Survey on Social Media Anomaly Detection <s> Static Graph <s> Traditional anomaly detection on social media mostly focuses on individual point anomalies while anomalous phenomena usually occur in groups. Therefore it is valuable to study the collective behavior of individuals and detect group anomalies. Existing group anomaly detection approaches rely on the assumption that the groups are known, which can hardly be true in real world social media applications. In this paper, we take a generative approach by proposing a hierarchical Bayes model: Group Latent Anomaly Detection (GLAD) model. GLAD takes both pair-wise and point-wise data as input, automatically infers the groups and detects group anomalies simultaneously. To account for the dynamic properties of the social media data, we further generalize GLAD to its dynamic extension d-GLAD. We conduct extensive experiments to evaluate our models on both synthetic and real world datasets. The empirical results demonstrate that our approach is effective and robust in discovering latent groups and detecting group anomalies. <s> BIB013
Compared with activity-based approaches, which simplify the social network as categorical or sequential activities of individuals, graph-based approaches further take into account the relational information represented by the graph. BIB001 immerses as one of the earliest work focusing on graph-based anomaly detection. It introduces two techniques for graph-based anomaly detection. One is to detect anomalous substructures within a graph and the other is to detect unusual patterns in distinct sets of vertices (subgraphs). Substructure is a connected component in the overall graph. Subgraph is obtained by partitioning the graph into distinct structures. Each substructure is evaluated using the Minimum Description Length metric for anomalousness. In real social graphs, intensive research efforts have been devoted to study the graph properties (see references in BIB005 ). One famous example is the power law, which describes the relationship among various attributes, namely the number of nodes (N ), number of edges (E), total weight (W ) and the largest eigen-value of the adjacency matrix (λ). Based on these observations,  proposes to study each node by looking at power law property in the domain of its "egonet", which is the subgraph of the node and its direct neighbors. For a given graph G, denote the egonet of node i as G i , the paper describes the "OddBall" algorithm. The algorithm starts by investigating the number of nodes N i , the weight W i and number of edges E i of the egonet G i . It then defines the normal neighborhoods patterns with respect to these quantities. For example, the authors report the Egonet Density Power Law (EDPL) pattern for N i and E i : ; the Egonet Weight Power Law (EWPL) pattern for W i and E β i , β ≥ 1. Given the normal patterns, the paper takes the distance-to-fitting-line as a measure to score the nodes in the graph. The algorithm can detect anomalous nodes whose neighbors are either too sparse (Near-star) or too dense (Near-clique). By studying both the total weight W and the number of edges E, it can detect anomalous nodes whose interactions with others are extremely intensive. By analyzing the relationship between the largest eigenvalue λ and the total weight W , it can detect dominant heavy link, or a single highly active link in an egonet. The "OddBall" algorithm builds on power law properties of complex networks, which haven been verified in various real world applications. Moreover, the fitting of power law and the calculation of anomaly score is computationally efficient, which makes the algorithm a good fit for large scale network analysis. However, the algorithm would easily fail if the network does not obey the power law, then the detected anomalies would be less meaningful. Also, the paper focuses only on the static network and generalization the algorithm to dynamic network is non-trivial. Besides the power law, random walk is also adapted for graph-based anomaly detection between neighbors. The general idea is that if a node is hard to reach during the random walk, it is likely to be an anomaly. Random walk calculates a steady state probability vector, each element of which represents the probability of reaching other nodes. Following the idea of random walk, BIB004 focuses on the anomaly detection on bipartite graph, denoted as G = V 1 V 2 , E , where node sets V 1 has k nodes, V 2 has n nodes and E are the edges between them. It detects anomalies by first forming the neighborhood and then computing the normality scores. During neighborhood formation stage, the algorithm computes the relevance score for a node b ∈ V 1 to a ∈ V 1 as the number of times that one visit b during multiple random walks starting from a. In this case, the steady state vector represents the probability of being reached from V 1 in a random walk with restart model, and the algorithm detects anomalies linked to the query nodes. Random walk model stresses the graph structure while ignores the nodes' attributes. Sometimes, it might be an over-simplification of the underlying network generating process, which would lead to high false positive ratio. [48] uses similar random walk guideline to detect outliers in a database and proposes the "OutRank" algorithm. It first constructs a graph from the objects where each node represents a data object and each edge represents the similarity between them. For every pair of the objects X, Y ∈ R d , the algorithm computes the similarity Sim(X, Y ) and normalizes the resulting similarity matrix to obtain a random walk transition matrix S. Then it defines the following connectivity metric based on how well this node is connected to the other nodes: Definition.(Connectivity) Connectivity c(u) of node u at tth iteration is defined as follows: where a is its initial value, adj(u) is the set of nodes linked to node u, and |v| is the node degree. This recursive definition of connectivity is also known as the power method for solving eigenvector problem. Upon convergence, the stationary distribution can be written as c = S T c. The algorithm detects the objects (nodes) with low connectivity to other objects as anomalies. "OutRank" solves individual activity-based anomaly detection problem using a graph-based anomaly detection method. As a general outlier detection framework, it requires the construction of the graph from data objects. Thus its performance can heavily rely on the type of similarity measurement adopted for computing the edges. Despite a wealth of theoretical work in graph theory, standard graph representation only allows each edge to connect to two nodes, which cannot encode potentially critical information regarding how ensembles of networked nodes interacting with each other  . Given this consideration, a generalized hypergraph representation is formulated which allows edges to connect with multiple vertices simultaneously. In hypergraph, each hyperedge is a representation of a binary string, indicating whether the corresponding vertex participates in the hyperedge. Figure  2 provides an example for comparing the graph and the hypergraph representation of two observations 111111000 and 000101111, with p = 9, using a graph and a hypergraph. With the graph, representing one observation of an interaction requires multiple edges. With a hypergraph, one hyperedge suffices. Due to the mapping between binary strings and hyperedges, the paper formulates the graph-based anomaly detection problem in the corresponding discrete space.  and BIB007 address the problem of detecting anomalous meetings in very large social networks based on hypergraphs. In their papers, a meeting is encoded as a hyperedge x and g(x) is the probability mass function of the meetings evaluated at x. The distribution of the meetings is modeled as a two-component mixture of a non-anomalous distribution and an anomalous event distribution g(x) = (1 − π)f (x) + πµ(x), with π as the mixture parameter. Then the paper learns the likelihood of each observation using variational EM algorithm with a multivariate Bernoulli variational approximation. The likelihood is subsequently used for the evaluation of the anomalousness. Hypergraph is specifically designed for high dimensional data in the graph. It provides a concise representation of the complex interactions among multiple nodes. But the representation only applies to binary relationships where an edge is either present or missing.  Anomalous edge detection has been proposed in BIB003 based on graph partitioning. The algorithm aims to detect anomalous edges that deviate from the overall clustering structure. The rationale behind this method is that if the removal of an edge can significantly make the graph easier to partition, then the two linked nodes may have an anomalous relation. The partitioning algorithm tries to find the best number of partitions so that the Minimal Description Length (MDL) needed to encode and transmit all the partitions of the graph is minimized. For a graph with n nodes, the paper defines the group mapping G : {1, 2, ..., n} → {1, 2, · · · , k} to assign nodes into k clusters. Thus, the Total Encoding Cost for the graph T (D; k, G) in the form of the adjacency matrix D = [d i,j ] depends on the number of the clusters k as well as the group mapping of the nodes G. Anomalous edges are those edges whose removal would significantly reduce the total graph encoding cost. In the paper, the anomaly score of an edge is defined as the total encoding cost difference to transmit the new partitions when the edge is removed, i.e, "outlierness" of edge (u, v) := T (D ; k, G) − T (D; k, G). D and D are equal of all edges except that d u,v = 0. Other similar work includes BIB002 , which defines a rarity measure to discover unusual links, and  , which uses a Katz measurement to statistically predict the likelihood of a link. Edge anomaly detection focus merely on pair-wise relationship and is not feasible for detecting more complicated anomalous behaviors with more than two people involved. Finding anomalous substructure in graphs is another topic of attention. For example, in the scenario of email exchanges within a company, email correspondence between managers and their secretaries should be normal (frequent pattern), while email exchange between assembly line workers and secretaries could be an anomalous pattern. BIB001 presents an iterative expanding algorithm to look for rare substructures using their SubDue system  . Given a labeled graph, where each node has a label identifying its type, the system starts with a list holding 1-vertex substructures for each unique vertex label. It modifies the list by generating, extending, deleting or inserting vertices and edges. One central issue is how to measure the anomalousness of a substructure. Simply counting the number of occurrences for substructures is not enough, as larger substructures tend to have low occurrences. BIB001 intuitively defines a score for a substructure S in a graph G as F 2 = Size(S) · Occurrences(S, G), which is simply the product of the total number of nodes within a substructure and its occurrences. A smaller value of F 2 indicates a more abnormal substructure. Another issue of the problem is the computational complexity of the algorithm. Although  shows that in practice the system runs in polynomial time, theoretically it faces exponential number of substructures. The pioneering work of BIB001 sees the rise of mining substructures in graphs. BIB009 leverages the structural information in the heterogeneous networks to detect unusual subgraph patterns. The algorithm encodes the graph using a tensor and focuses on finding the suspicious spikes via tensor decomposition. Formally, given an M-mode tensor X of size I 1 × I 2 × · · · × I M , the algorithm performs CP decomposition of the tensor of rank R as X ≈ R r=1 λ r (a where {a (i) r } are rank-1 eigenscore vectors. The approximation would be exact when R equals the true rank of the tensor. Next the algorithm transforms the eigenscore vector plot (absolute value of eigenscore vs. attribute index) into the eigenscore histogram (absolute value of eigenscore vs. frequency count) and conducts spike detection on the histogram. The proposed approaches bridges graph mining and tensor analysis. Tensor decomposition is able to capture the complex structure in heterogeneous networks. But tensor decomposition problem itself can be NP-hard to solve. And the lack of explicit objective in the proposed anomaly detection framework would create difficulties in the final evaluation of the algorithm's performance. In the setting of fraudulent activity detection, BIB006 jointly considers anomalous substructure and the criteria of MDL. Specifically, they run the SUBDUE system with MDL heuristics to find the normative pattern in the graph. Instances of substructure are evaluated against the normative pattern with a match cost. Anomalous substructures are the ones with the lowest matches. Based on this definition of group anomaly, BIB006 presents three slightly different algorithms, i.e. GBAD-MDL, GBAD-P and GBAD-MPS to detect anomalies. These methods first find all the instances of frequent substructures and evaluate the frequency of the abnormal structure multiplied by the match cost. A key drawback of this method is that it assumes that the degree of nodes in a graph is uniformly distributed, which is almost impossible in most social networks. As shown in BIB008 BIB005 , real graphs usually follow power law degree distribution instead of uniform distribution. In social media, two forms of data coexist: one is the point-wise data, which characterize the features of an individual person. The other is pair-wise relational data, which describe the properties of social ties. Density estimation methods for group anomaly detection BIB010 BIB011 BIB012 emphasize on the point-wise data and usually overlook the pair-wise relational data. Graphbased methods highlight the graph structure but usually fail to account for the attributes of individual nodes. Additionally, existing group anomaly detections algorithms are all two-stage approaches: (i) identify groups, (ii) detect group anomalies. This strategy assumes that the point-wise and pair-wise data are marginally independent. However, such independence assumption might underestimate the mutual influence between the group structure and the feature attributes. The detected group anomalies can hardly reveal the joint effect of these two forms of data. With those considerations, BIB013 proposes to build an alla prima that can accomplish the tasks of group discovery and anomaly detection all at once. They develop a hierarchical Bayes model: the GLAD model, for detecting the group anomaly. The GLAD model utilizes both the pair-wise and point-wise data and automatically infers the group membership and the role at the same time. It models a social network with N individuals. Assuming that each person p is associated with a group identity G p and a role identity R p . By groups, it means the clusters that capture the similarity suggested by the pair-wise communications. By roles, it refers to the mixture components that categorize the point-wise feature values of the nodes. For simplification, they fix the number of groups as M and the number of roles as K. Figure 5 shows the plate notation for the GLAD model. For each person p, he joins a group according to the membership probability distribution π p . GLAD imposes a Dirichlet prior on the membership distribution. It is well known that the Dirichlet distribution is conjugate to the multinomial distribution. It assumes the pair-wise link Y p,q between person p and person q depends on the group identities of both p and q with the parameter B. Furthermore, it models the dependency between the group and the role using a multinomial distribution parameterized by a set of role mixture rate {θ 1:M }. The role mixture rate characterizes the constitution of the group: the proportion of the population that plays the same role in the group. Finally, it models the activity feature vector of the individual X p as the dependent variable of his role with parameter set {β 1:K }. GLAD defines the group anomaly based on the role mixture rates, it scores the group anomalousness using − p∈G log p(R p |Θ) p . The most anomalous group will have the highest anomaly score. In practice, it approximates the true log likelihood with the variational log likelihood to get − p∈G log p(R p |Θ) q . A limitation of GLAD is that it only models the static network. This might be restrictive if we want to further consider dynamic networks. Besides the anomaly group whose mixture rate deviates significantly from other groups, it is also interesting to study how the mixture rate evolves over time.