ANOMALOUS: A Joint Modeling Approach for Anomaly Detection on Attributed Networks

1 Introduction

Anomaly detection [Chandola et al., 2009; Aggarwal, 2015] aims to spot rare, unexpected and suspicious instances that significantly deviate from the patterns of majority in datasets. It has significant implications in various high-impact domains, such as financial fraud detection, intrusion detection and event detection [Rayana and Akoglu, 2015; Eskin et al., 2002; Chen et al., 2016]. Typically, when an instance is identified as anomalous, we can perform further analysis to investigate why it is abnormal and what makes it different from the other instances in order to gain more insights on the potential risks of the system. Recently, there is a surge of anomaly detection research focusing on attributed networks [S´anchez et al., 2013; Liu et al., 2017; Li et al., 2017] as attributed networks are increasingly used to represent real-world information systems such as social networks, product co-purchase networks and protein-protein interaction networks. Networks of this particular type use edges to describe relationships between data instances, and also collect additional attributes to delineate the properties of nodes. Due to the unique characteristics of attributed networks, anomaly detection faces new challenges. First, how to leverage network structure information and nodal attributes seamlessly for anomaly detection is a crucial yet challenging problem. Secondly, the existence of noisy and structurally irrelevant attributes can impede us to accurately spot anomalies and may even lead to misjudges. Hence, identifying and filtering out these attributes is imperative for anomaly detection.

A vast majority of existing efforts [Davis et al., 2011; Liu et al., 2017; Li et al., 2017] heavily rely on the assumption of Homophily [McPherson et al., 2001] to detect anomalies on attributed networks. The principle of Homophily implies that there exists a strong correlation between network structure and node attributes, instances connected with each other in the network are also similar w.r.t. the nodal attributes. Despite its empirical success, when we conduct further analysis to examine the relations between each attribute and the network structure, we may observe that not all attributes are strongly hinged to the network structure. In other words, there may exist some outlying attributes that do not satisfy the Homophily hypothesis, and the existence of these structurally irrelevant attributes could bring about adverse effects on anomaly detection. Figure 1 illustrates an example of the above-mentioned issues on a real-world social network. In the figure, each node denotes a user and she/he has four attributes (age, gender, income, number of friends), users are interconnected with their acquaintances. When performing anomaly detection with all four attributes, we are most likely to regard each node as an anomaly since each node does not conform to the patterns of the majority. Nonetheless, if we only focus on attributes f1 and f3, it is obvious that node 5 is a community anomaly [Gao et al., 2010] as its third attribute (f3) value is relatively higher than the other nodes within the same community (node 1, 2, 3 and 4). Meanwhile, node 8 is also an anomaly since its first attribute (f1) value deviates significantly from its structurally connected nodes. This phenomenon indicates that not all attributes show dependencies with the network structure, examples include the binary attribute f2, and the numerical attribute f4 which is almost assigned with random values. These noisy and irrelevant attributes hinder us in capturing the correlation between network structure and node attributes, which may further make the true anomalies node 5 and node 8 undiscovered. Therefore, selecting representative attributes that are closely hinged with the network structure is essential for anomaly detection. Although there are a few attempts on performing subspace selection for spotting anomalies, they treat it as a pre-processing step before anomaly detection [S´anchez et al., 2013; 2014] rather than optimizing them as a whole, it may lead to a suboptimal result.

In this paper, we propose a joint modeling approach for anomaly detection on attributed networks, called ANOMALOUS. Specifically, through optimizing attribute selection and anomaly detection as a whole, ANOMALOUS selects a subset of representative instances on the space of representative attributes that are closely hinged with the network topology based on CUR decomposition [Mahoney and Drineas, 2009], and then measures the normality of each instance via residual analysis [She and Owen, 2011]. The main contributions of our work are as follows:

• Examining the issues of existing attempts on performing anomaly detection on attributed networks.
• Introducing a new idea that optimizes attribute selection and anomaly detection as a whole instead of treating them as two separate steps.
• Proposing a novel joint anomaly detection framework ANOMALOUS for attributed networks by CUR decomposition and residual analysis.
• Evaluating the performance of the proposed framework on synthetic datasets and real-world datasets.

2 The ProposedMethodology

The notations used in this paper are introduced as follows. Following the standard notation, we use bold uppercase characters (e.g.,A) to denote matrices and bold lowercase characters (e.g., b) to indicate vectors. Scalars are written as normal lowercase characters (e.g., c) and uppercase italic letters (e.g., F) for sets. Given a matrix A, we use A(i, :), A(:, j) and A(i, j) to denote its i-th row, j-th column and (i, j)-th entry, respectively. As for the vector or matrix norms, the only used vector norm is the ℓ2 norm, denoted by ‖ · ‖2. The ℓ2,1-norm of matrix A ∈ Rd×n is written as ‖A‖2,1 = ∑di=1 √∑nj=1 A(i, j)2 , ‖A‖F = √∑di=1 ∑nj=1 A(i, j)2 represents its Frobenius norm and its ℓ2,0-norm means the number of nonzero rows, denoted by ‖A‖2,0.

2.1 ProblemFormulation

We first give the formal definition of anomaly detection on attributed networks: suppose U = {u1, u2, . . . , un} indicates a set of n instances, each instance is affiliated with a set of d-dimensional attributes F = {f1 , f2 , . . . , fd }. We adopt a matrix X ∈ Rd×n to represent the attribute information of all n instances, where X(:, i) ∈ Rd denotes the attribute information of the i-th instance ui. In addition, these instances are interconnected with each other to form a network, and we use the adjacency matrix A ∈ Rn×n to describe the link relationships between them, where A(i, j) = 1 indicates ui and uj is connected with each other. The goal of anomaly detection is to find a set of instances which are rare and differ significantly from the majority of the reference instances using the attribute information X and the network structure information A.

2.2 Joint Anomaly Detection Framework

Residual analysis which aims to study the residuals between true data and estimated data can be applied to spot anomalies since anomalies usually have large residual errors caused by the huge deviations from majority reference instances in patterns [Tong and Lin, 2011]. A well-known method of building estimated data is by using some instances to reconstruct true data [Yu et al., 2006]. In view of the existence of noisy and irrelevant attributes, we would like to simultaneously select structure-related attributes and representative instances to rebuild true data X. Hence, we decide to expand our view from standard factorizations to CUR decomposition, which has better interpretability for instance and attribute selection. Mathematically, the proposed framework is formulated as:

where C ∈ Rd×m is a subset of m columns of X, R ∈ Rr×n is a subset of r rows of X, U ∈ Rm×r with m, r and rank(U) as small as possible, ˜R is the residual matrix of node attributes and Ψ is a regularization term on ˜R.

It can be observed from the above formulation that the process of finding matrix C and R indicates the selection of m instances and r attributes from the original data and attribute space. Accordingly, CUR is a combination of the selected instances and attributes which is supposed to approximate matrix X as closely as possible, thus the selected instances and attributes can be regarded as representative ones.

Here we give details about the regularization term Ψ as follows:

where L is a Laplacian matrix generated by the adjacency matrix A of networks. The first item ‖ ˜RT ‖2,0 is used to limit the number of anomalies since a large norm of ˜R(:, i) indicates the i-th instance has a higher possibility to be anomalous, and the number of anomalies is much smaller than that of normal instances. The parameter γ controls the column sparsity of the residual matrix ˜R. At this point, we have only dealt with attribute information with neglect of network structure. Nevertheless, network structure information provided by attributed networks is also particularly critical for anomaly detection. Theoretically, we expect attribute modeling can filter out noisy and irrelevant attributes so that the Homophily hypothesis holds for selected attributes. Therefore, Based on Homophily, we require that if two instances are connected in the network, their attribute patterns in the residual matrix ˜R ought to be similar after attribute reconstruction. Formally, we achieve network structure modeling by minimizing 1 2 ∑ni=1 ∑nj=1 ( ˜RT (i, :) - ˜RT (j, :))2A(i, j) = tr( ˜RL ˜RT ). In fact, ϕtr( ˜RL ˜RT ) is modeling the correlation between network structure and node attributes, parameter ϕ controls the contribution of the modeling of this correlation.

2.3 Model Reformulation

Due to the under-determination of a general CUR model, we introduce two indicator vectors v = (v1, . . . , vn)T ∈ {0, 1}n and p = (p1, . . . , pd)T ∈ {0, 1}d to reformulate Eq. (1) as:

where diag(v) is a diagonal matrix with diagonal elements v and 1n is an n-dimensional vector with all elements being 1. Xdiag(v) keeps m columns of X unchanged as selected instances and sets remaining n -m columns to zero vectors. diag(p)X holds r rows of X unaltered as selected attributes and sets the rest d - r rows to zero vectors.

Then we reformulate Eq. (3) by adding the regularization term Φ:

where W = diag(v) ̂Udiag(p) ∈ Rn×d , and it enables the task of selecting representative instances and attributes simultaneously through a regularization term Φ. The regularization term Φ is defined as:

where α and β controls the row sparsity and the column sparsity of matrix W, respectively. Here we make a key observation that the above definition achieves simultaneous instance and attribute selection. On one hand, WX in Eq. (4) can be regarded as a coefficient matrix, and when the i-th row of WX is not a zero vector, X(:, i) is chosen as a representative instance. Apparently, ‖W‖2,0 ensures that only a few instances are chosen to be representative ones. On the other hand, XW can also be viewed as a coefficient matrix, and when the j-th column of XW is not a zero vector, X(j, :) is selected as a representative attribute. Obviously, ‖WT ‖2,0 ensures only part of attributes become representative attributes which are leveraged to reconstruct the original data X.

Considering the ℓ2,0-norm term in Eq. (2) and Eq. (5) will make Eq. (4) NP-hard because of its discrete nature. To address this issue, we relax the ℓ2,0-norm constraint as ‖W‖2,1 which is the minimum convex hull of ‖W‖2,0, the objective function of framework ANOMALOUS can be formulated as:

From a global perspective, the correlation modeling term tr(˜RL˜RT ) imposes constraint on instance and attribute selection. We can understand it that in order to minimize the value of tr(˜RL˜RT ), our framework tends to choose instances which are similar to great majority of instances as representative ones, and simultaneously select representative attributes which are closely hinged with the network structure and can represent the whole dataset most precisely. By analyzing the residual matrix ˜R, we can rank anomalies according to residual errors.

3 Optimization Algorithm

The optimal solution of Eq. (6) is difficult to obtain as the objective function is not convex in terms of bothW and ˜R simultaneously, and it is also not smooth due to ℓ2,1-norm term. Hence, we present an alternating way to solve this problem. Update ˜R: When W is fixed, Eq. (6) is convex w.r.t. ˜R. Therefore, we first fix W to update ˜R, then the objective function can be reformulated as:

By setting the derivative of Eq. (7) w.r.t. ˜R to zero, we get

where DR is a diagonal matrix with diagonal elements DR(i, i) = 1 2‖ ˜RT (i,:)‖2 1 . It can be noticed that matrix ϕL, I and γDR are both positive semidefinite, so the summation of I+γDR+ϕL is also a positive semidefinite matrix. Therefore, we can get a closed-form solution of ˜R as follows:

Update W: When ˜R is fixed, Eq. (6) is convex w.r.t. W. Then the objective function can be reformulated as:

Similarly, by setting the derivative of Eq. (10) w.r.t. W to zero, we arrive at

1 Considering ‖˜RT (i, :)‖2, ‖W(i, :)‖2 and ‖WT (i, :)‖2 could be zero theoretically, we redefine DR(i, i) = 1 2‖ ˜RT (i,:)‖2+ε , D′W(i, i) = 1 2‖W(i,:)‖2+ε and D′′W(i, i) = 1 2‖WT (i,:)‖2+ε in practical programming, where ε is a very small constant.

where H = XT XXT - XT ˜RXT . D′W and D′′W are diagonal matrices with the i-th diagonal element as D′W (i, i) = 1 2‖W(i,:)‖2 and D′′W (i, i) = 1 2‖WT (i,:)‖2 , respectively.

Then W in Eq. (11) can be solved easily according to the following lemmas and theorem:

Lemma 1. For any matrix B ∈ Rm×n right multiplied by a diagonal matrix D ∈ Rn×n , the expression BD can be rewritten as D∗ ⊙B, where ⊙ denotes the Hadamard product (component-wise multiplication) and D∗ ∈ Rm×n is defined as D∗ (i, j) = D(j, j), ∀i = 1, 2, . . . , m, ∀j = 1, 2, . . . , n.

Lemma 2. For the following matrix equation on U:

where C1 and C2 are symmetric and positive semidefinite matrices, D1 and D2 are diagonal matrices, a and b are scalers, ⊙ denotes the Hadamard product. We can reformulate Eq. (12) as follows:

where we decompose C1 and C2 by non-negative eigenvalues such that C1 = PΘ1PT , C2 = QΘ2QT , P and Q are both orthogonal matrices, Θ1 and Θ2 are two diagonal matrices composed of the eigenvalues. In addition, K = PT UQ.

Theorem 1. The closed-form solution of W in optimization problem Eq. (10) is

Proof. Based on Lemma 1 and Lemma 2, Eq. (11) becomes

where XT X = PΘ1PT , XXT = QΘ2QT , Y = PT WQ, Z = PT D′W P and M = PT HQ. For a better representation, we denote Y = [y1, y2, . . . , yd] ∈ Rn×d , M = [m1,m2, . . . ,md] ∈ Rn×d , Z = [z1 ; z2 ; . . . ; zn ] ∈ Rn×n , then the first three terms of Eq. (15) can be rewritten as

Plugging the equations above into Eq. (15), we find that Eq. (15) can be decomposed into d equations with respect to d column vectors of matrix Y, i.e.,

for i = 1, 2, · · · , d. As a result, we have

Integrating each yi obtained by Eq. (17), we achieve the closed-form solution of Y. Recall Y = PT WQ, it is accessible to W through basic matrix operations.

Algorithm 1 ANOMALOUS: A joint modeling approach for anomaly detection on attributed networks

Input: Adjacency matrix A, attribute matrix X, parameters α, β, γ, ϕ.

Output: Top t instances with the highest abnormal scores.

• 1: Build Laplacian matrix L from the adjacency matrix A;
• 2: Initialize DR, D′W and D′′W to be identity matrix.
• 3: Initialize ˜R=X(I +γDR +ϕL)-1 .
• 4: Build orthogonal matrix P, Q and diagonal matrix Θ1, Θ2 based on Lemma 2.
• 5: while objective function in Eq. (6) not converge do
• 6: UpdateWby Eq. (14);
• 7: Update D′W by setting D′W (i, i) = 1 2‖W(i,:)‖2 ;
• 8: Update D′′W by setting D′′W (i, i) = 1 2‖WT (i,:)‖2 ;
• 9: Update ˜R by Eq. (9);
• 10: Update DR by setting DR(i, i) = 1 2‖ ˜RT (i,:)‖2 ;
• 11: end while
• 12: Compute the abnormal score for the i-th instance as ‖ ˜R(:, i)‖2;
• 13: Output top t instances with the highest abnormal scores.

The key steps of framework ANOMALOUS spotting anomalies on representative attributes via CUR decomposition and residual analysis are summarized in Algorithm1. At each iteration, the most cost operation is the matrix inverse operation requiring O(n3 ) caused by matrix update. Fortunately, the linear equation system can speed up the update of ˜R, only needing O(n2d) (d is usually smaller than n). Similarly, the update of W requires O(n2 ) which can be accelerated through calculating each column of Y in parallel. Consequently, the total time complexity is #iterations∗(O(n2d)+ O(n2 )), i.e., #iterations ∗ O(n2d).

4 Experiments

In this section, we empirically evaluate the effectiveness of the proposed framework ANOMALOUS on both synthetic and real-world datasets. Specifically, we compare our approach with six state-of-the-art methods which are popular in the field of anomaly detection. Here, the compared methods in experiments are listed as follows:

• SCAN [Xu et al., 2007]: SCAN only considers the network structure information. It detects anomalies in a structural level.
• LOF [Breunig et al., 2000]: LOF only considers attributes of nodes and makes use of all attributes. It detects anomalies in a contextual level.
• ConSub+CODA [S´anchez et al., 2013]: ConSub performs the statistical selection of congruent subspaces as a pre-processing step and then uses CODA to detect subspace community anomalies.
• ConOut [S´anchez et al., 2014]: For each node, ConOut determines its subgraph and its statistically relevant subset of attributes locally and then detects anomalies in selected local context.

• AMEN [Perozzi and Akoglu, 2016]: AMEN uses both attribute information and network structure information to detect anomalous neighborhoods. Since it is designed to detect an abnormal cluster rather than a single node, we regard all nodes in anomalous clusters as anomalies for comparison.
• Radar [Li et al., 2017]: Radar detects anomalies by learning and analyzing the residuals of attribute information and its coherence with network information.

In these algorithms listed above, the latter four take both attribute information and structure information into consideration. Only ConSub+CODA, ConOut and AMEN carry out attribute selection, but they perform it as pre-processing step independently of the following anomaly detection which may easily lead to suboptimal results. We adopt the criteria of AUC which is the area under the ROC curve to evaluate the quality of various anomaly detection methods. The closer the AUC value is to 1, the better performance of the algorithm is. In addition, the parameter settings of these baseline methods excluding AMEN and Radar follow the settings of [S´anchez et al., 2013]. For AMEN and Radar, we choose the parameter settings which can get the best experimental results. Considering the proposed framework has four different regularization parameters, we tune these parameters by a "grid-search" strategy from {10-4 , 10-3 , . . . , 103 , 104 }. The detailed experimental results will be demonstrated later.

4.1 Synthetic Datasets

Considering the detection performance may be affected by irrelevant attributes and increased attribute dimensions, we design an experiment to evaluate the performance of each baseline method and the proposed framework ANOMALOUS w.r.t. different attribute dimensions. In order to make our experiment more convincing, we adopt a public synthetic dataset 2 in [S´anchez et al., 2013] which contains attribute information with five different dimensions as well as the ground truth labels of anomalies. The generated network diagrams follow a power law distribution in order to reproduce the properties observed in real-world networks. Node attribute information is divided into network structure related and network structure irrelevant following uniform random distribution, each accounting for 50%. A brief description of this synthetic datasets is shown in Table 1.

Performance Evaluation

The experimental results of all seven algorithms w.r.t. different attribute dimensions are depicted in Figure 2. We can observe from the figure that our framework ANOMALOUS achieves the best performance on five different dimensions of attributes. Hence, it is safe to obtain the conclusion that our proposed algorithm is most robust to the increase of attribute dimensions and irrelevant attributes. The main reason is that ANOMALOUS can effectively filter out irrelevant attributes and select representative attributes and instances simultaneously for anomaly detection. In addition, we can clearly see that the performance of LOF tends to decrease with increased attribute dimensions. Especially, since SCAN only considers the structure information for anomaly detection, the change in attribute dimensions has no effect on it.

2 http://www.ipd.kit.edu/∼muellere/consub/

4.2 Real-World Datasets

We adopt three attributed networks that have been widely used in the previous research [S´anchez et al., 2015; Li et al., 2017] to evaluate ANOMALOUS on real-world datasets. Among them, Disney dataset is a network of movies including many attributes such as ratings, prices and the number of reviews. Amazon dataset is a network which contains various books as nodes and has similar attributes as Disney. And Enron is a communication network with email transmission as edges between email addresses, the attributes include average content length, average number of recipients, etc. Details about these three datasets are listed in Table 2.

Performance Comparison

The anomaly detection performance of different approaches on three real-world datasets is shown in Figure 3. Compared to other methods, ANOMALOUS achieves the best performance on all three datasets. We can attribute this improvement to the joint selection of representative attributes and instances for anomaly detection. In particular, the instances that deviate significantly from the representative instances are recorded as anomalies and the selection of representative attributes can help us target for these representative instances more accurately. As for ConSub+CODA, ConOut and AMEN, they treat subspace selection and anomaly detection as two independent steps, there is no guarantee that the sub- Real-World Data space selection made by these methods can effectively improve the performance of anomaly detection. Moreover, Figure 4 shows the three detected anomalies by our method on Disney dataset. Specifically, node N1 corresponds to the film The Many Adventures of Winnie the Pooh and node N2 corresponds to the film Buzz Lightyear of Star Command, these two nodes deviate significantly in the rating attributes from the other co-purchased products. Node N3 corresponds to the film The Nightmare Before Christmas / James and the Giant Peach is a typical structural anomaly since it is an isolated co-purchase product. In a nutshell, our framework ANOMALOUS can help us find anomalies of different formats.

Figure 4: Visualization of three anomalies detected by ANOMALOUS on Disney dataset.

Effects of Instance Selection and Attribute Selection

Among the four parameters in Eq. (6), α and β are relatively more important since they control instance selection and attribute selection respectively. In this subsection, we investigate the impact of instance selection and attribute selection on anomaly detection performance. We compare ANOMALOUS with the following methods by varying α and β:

• Instance selection-based method: We set the parameter β to be zero, therefore, only instance selection is taken into consideration in the reconstruction phase.
• Attribute selection-based method: We set the parameter α to be zero, therefore, only attribute selection is taken into consideration in the reconstruction phase.

We show anomaly detection performance of each method in Figure 5. As can be observed, the AUC values of instance selection-based method and attribute selection-based method are both lower than ANOMALOUS on all three datasets. This phenomenon indicates that compared to only selecting instances or attributes, considering both instance selection and attribute selection can indeed improve the performance since they choose representative instances and attributes simultaneously for anomaly detection which can alleviate the negative effects brought from the noisy and irrelevant attributes.

5 RelatedWork

Typically, existing efforts on anomaly detection for networked data are broadly divided into two classes: (1) anomaly detection on plain networks; and (2) anomaly detection on attributed networks [Akoglu et al., 2015]. For a plain network, the only available information we can collect is the network topology. Therefore, detecting anomalies using structure information such as node degree and subgraph centrality is a major feature of this kind of algorithms. Existing methods such as [Xu et al., 2007; Akoglu et al., 2010; Tong and Lin, 2011] focus on spotting structural anomalies in networks which do not belong to any communities. As for an attributed network, it can be regarded as a richer graph representation having both structure information and attribute information. Hence, anomaly detection algorithms exploit the structure as well as the coherence with node attributes to detect anomalies. There are many existing methods [Long et al., 2006; Gao et al., 2010; Akoglu et al., 2012] working on attributed networks attempt to partition the given graph into structurally dense and attributewise homogeneous clusters to find anomalies. But recently, researchers find that not all attributes are correlated to the network structure, thus they conduct unsupervised feature selection (a.k.a. subspace selection) [Gunnemann et al., 2010; Tang and Liu, 2012] to find relevant attributes for anomaly detection. Among them, Consub+CODA carries out subspace selection first and then use CODA detects anomalies [S´anchez et al., 2013]. ConOut determines a local context for each node and then calculates the anomaly score within the local context [S´anchez et al., 2014]. However, these algorithms regard subspace selection and anomaly detection as two independent steps which may lead to suboptimal results. Different from existing works, our proposed algorithm treats anomaly detection and attribute selection in a joint optimization framework.

6 Conclusions and FutureWork

In this work, we introduce a joint framework ANOMALOUS based on CUR decomposition and residual analysis for spotting anomalies on attributed networks, where attribute and network structure information are collectively used for simultaneous attribute selection and anomaly detection. Experiments on both synthetic and real-world datasets indicate the effectiveness of our approach. Future work will concentrate on including edge attributes or finding adaptive methods [Anava and Levy, 2016] to remodel the network structure.

Acknowledgments

This work is supported by National Key Research and Development Program of China (2016YFB1000903), National Nature Science Foundation of China (61502377, 61532015, 61572399 and 61672418), Innovative Research Group of the National Natural Science Foundation of China (61721002), Innovation Research Team of Ministry of Education (IRT 17R86), Project of China Knowledge Center for Engineering Science and Technology.