Accelerated Local Anomaly Detection via Resolving Attributed Networks

1 Introduction

Anomalies refer to the noteworthy objects with patterns or behaviors that significantly deviate from the background. Anomaly detection has been intensively studied for various applications, such as spam detection [Yang et al., 2012], fraud detection [Rayana and Akoglu, 2015], events detection [Chen et al., 2016] and computer security [Cheng et al., 2016]. Successful anomaly detection plays a critical role in many information systems towards achieving a secure cyberspace.

Due to the data characteristics in many real-world information systems, anomaly detection faces new challenges. First, attributed networks [Huang et al., 2017a; 2017b; Akoglu et al., 2015] have been increasingly used in modeling complex real-world information systems. Different from plain graphs, in attributed networks, both connectivity information and node properties are available. For example, in social networks with friendship relations as links, users can also be characterized by their interests, work background, and user-generated posts. Unfortunately, existing anomaly detection algorithms usually focus on either attribute information [Xiong et al., 2011; Zhao and Fu, 2015; Jiang et al., 2015] or network structure [Xu et al., 2007], or do not provide much interpretation for anomalies beyond visualization [Tong and Lin, 2011; Akoglu et al., 2012]. Furthermore, real-world attributed networks usually contain large-scale data instances and highdimensional features. Given the heterogeneous and largescale attributed networks, existing anomaly detection methods cannot be simply applied.

In addition, it has been observed that some local anomalies well align with the global condition and cannot be easily detected. Take the attributed network in Fig. 1 as an example. There are three clusters in the network. Each node has one continuous numerical attribute a, and pc(a) represents the attribute distribution of the instances in community c. By only looking at node n0 in the overall distribution p(a), it is unlikely to identify it as an anomaly. However, by collectively examining the network structure and attribute information of the node, we can clearly observe that n0 is an anomaly, as it is inconsistent with other nodes in C1 according to the distribution in p1(a). This phenomenon can also be observed in health provider networks, where the records declared by an anomaly provider may look normal among all entities, but its fraud activities can be revealed by a refined inspection in the local community [Akoglu et al., 2015]. Thus, motivated by these observations, we propose to investigate the problem of local anomaly detection in large-scale attributed networks.

To deal with the aforementioned challenges, in this paper, we propose to collectively make use of network and attribute information for effective and efficient anomaly detection. Specifically, we investigate how to extract insightful information from heterogeneous data sources as the basis for spotting local abnormal nodes, as well as design an accelerated algorithm to deal with large-scale data. The contributions are presented as follows:

• An integrated anomaly detection framework for attributed networks is proposed. Network structure and node attribute information are jointly considered for network clustering and attribute distributions estimation. The normality score of a node is measured within its local context.
• The model is interpretable as we are able to identify the abnormal attributes of anomalies and measure their degrees of abnormality.
• A novel parallel algorithm is developed to accelerate the optimization process to resolve networks, especially when the given network is sparse in terms of links or attributes.
• The effectiveness and efficiency of our framework are demonstrated through experiments on real-world and synthetic networks, as well as case studies.

2 Local Anomaly Detection Framework

In this paper, we propose a novel framework for Accelerated Local Anomaly Detection (ALAD) in attributed networks. The notations used in this paper are introduced as follows. We use bold uppercase letters (e.g. A) to denote matrices. We represent the (n,m)th entry of a matrix as Anm, the nth row of a matrix as An∗, and the mth column as A∗m. The (i, j)th block of a matrix is represented using Ai,j . We denote the ℓ2-norm of a vector as ‖ · ‖2, and Frobenius norm of a matrix as ‖ · ‖F . Let N = {V, G, A} be a target attributed network, where V is a set of N nodes, and G ∈ RN×N ≥0 is the weighted adjacency matrix. Gnm equals to the positive edge weight if there is a link between nodes n and m, and 0 otherwise. A ∈ RN×K ≥0 represents the node attribute matrix, where An∗ describes the attributes associated with node n. We assume that the network is undirected, and all attribute values are non-negative.

2.1 Problem Statement

Anomalies are defined as the objects that "arouse suspicions that it was generated by a different mechanism" [Hawkins, 1980]. According to the definition, there are three questions to be answered for designing a detection method: (1) where is the local context in which an object locates; (2) what is the probable data generation mechanism in such local context; (3) how to measure the suspicion of current object with respect to the contextual mechanism. Under this problem setting, each object n can be characterized using two types of features [Chandola et al., 2009]: 1) context features (wn) which determine the location, group or genre of an object, e.g., the spatial coordinates of a city, or the category labels of a commercial product; 2) content features (an) which describe the attributes, behaviors or properties of an object, e.g., the demographics of a city, or the user reviews of a product. The neighbors of object n can be discovered by comparing wn with other wn′ , n′ ̸= n. In attributed networks, the information for determining the context features of a node is not limited to its connection status. The attribute information may also affect the role of a node in its local context. Let hc denote the attribute distributions measured from {an1 , an2 , ...} where objects n1, n2, ... belong to the same context c. The suspicious score of object n being an anomaly with respect to context c can thus be formulated as the disparity between an and hc. Many traditional anomaly detection algorithms, either explicitly or implicitly, have adopted the three factors above [Gao et al., 2010; Liang and Parthasarathy, 2016; Perozzi et al., 2014; Liang et al., 2017]. In some cases, wn and an refer to the same feature set from homogeneous data sources [Breunig et al., 2000; Jiang et al., 2015].

Based on the terminologies described above, we formally define the problem as follows: Given the attributed network N, we aim at developing a framework to identify anomalies as nodes o whose content features ao significantly deviate from the feature distribution hc of their context localized by the context features wo of o.

2.2 Context Extraction and Summarization from Heterogeneous Data

For the given network N, each node n is characterized by both Gn∗ ∈ RN≥0 and An∗ ∈ RK≥0 , which cannot be directly concatenated as wn due to their heterogeneity and high dimensionality. In fact, the number of factors that determine the dependencies in a network is limited [Li et al., 2017]. Therefore, we would like to first transform the original features to a low-dimensional vector Wn∗ ∈ RC≥0 . Then a straightforward solution for anomaly detection is to apply heterogeneous network embedding methods [Chang et al., 2015] to build W, perform clustering on nodes, estimate the data distribution on each cluster (e.g., take the mean values), and at last find anomalies. This pipeline, however, is limited by several problems. The noise in attributes may affect the accuracy of distribution estimation. Moreover, it relies on the performance of specific embedding methods, while the superposition of embedding and clustering also significantly increases the computational cost. The anomaly detection step tends to be a byproduct of embedding and clustering methods.

Because of the reasons above, we propose to map the data to a C-dimensional latent space in which each Wnc already corresponds to a group or topic for c ∈ [1,C]. In the latent space, taking the attribute matrix A as an example, the property of each node can be seen as a weighted linear composition of the aspects from C groups, i.e., An∗ ≈ ∑Cc=1 WncHc∗, where Wnc measures how close is node n affiliated with cluster c, and Hck indicates the degree to which the attribute k is associated with cluster c [Xu et al., 2003]. In another word, Wn∗ represents the context features of object n, while Hc∗ encodes the attribute distributions of cluster c. The problem of learning latent factors, i.e. approximating A ≈ WH, can be solved via non-negative matrix factorization (NMF) [Lee and Seung, 2001]. Here W ∈ RN×C ≥0 , H ∈ RC×K ≥0 , and C is the number of latent factors.

Despite the heterogeneity of the two information sources G and A, both of their row dimensions represent network nodes, which provides the basis for joint consideration. Motivated by symmetric nonnegative matrix factorization [Kuang et al., 2012], we incorporate links information in G and propose the objective function formally as below:

Two nodes i and j that are closely correlated in the same context will have similar representation vectors Wi∗ and Wj∗. The regularization terms ‖W‖2F and ‖H‖2F are used to avoid overfitting and the affect of data noise. The elements in W and H are constrained to be non-negative, not only because G and A are non-negative, but also to achieve interpretability. As the solution for NMF is not unique, we further normalize the factor matrices as below:

The proposed model has several nice properties. First, NMF based clustering is semantically interpretable [Kuang et al., 2012]. Second, the model does not have a strong assumption such as positive semidefinite on the network, so it is general to various real-world applications. Third, by applying the bi-factorization scheme instead of its tri-factorization counterpart [Long et al., 2006], we could avoid convoluted interactions between parameters, thus enabling to develop efficient optimization algorithms.

2.3 Local Suspiciousness Evaluation

The suspiciousness of a node should be evaluated within a proper context. As a node n may belong to several groups simultaneously, its suspiciousness can be measured as:

where ˜Wn,c = Wn,c/ ∑c Wn,c is interpreted as the likelihood that node n belongs to group c [Shashanka et al., 2008].

After locating nodes in the latent space, we want to compute how significantly node n deviates from its background condition. To uniformly handle different types of distributions (e.g., Gaussian or Bernoulli) in real-world systems, we transform all types of attributes to categorical ones [Catlett, 1991], so that Ank counts the occurrence of attribute k on node n. As mentioned before, the suspiciousness of node n can be measured by the disparity between an and hc. Here we take content features an = An∗ and distribution vector hc = Hc∗. Some commonly used metrics for quantifying the difference between two vectors include Euclidean distance ‖An∗ -Hc∗‖2, cosine similarity cos(An∗, Hc∗) and Kullback Leibler (KL) divergence D(An∗‖Hc∗). In many real-world networks, the attributes are expected to be high-dimensional and sparse, so Euclidean distance and KL divergence may not perform well [Zimek et al., 2012]. Here we use cosine similarity to calculate the normality score, i.e. inverse of suspiciousness score, between the two vectors:

The intuition behind the score is that, if there is little overlap between the attributes of a node n and the distribution of its local context, then the node should be viewed as abnormal.

After computing the normality score for each node, we can have a ranked list in which nodes are sorted in ascending order with respect to their scores, where nodes ranked higher are considered as anomalies.

3 Accelerated Optimization

Typical optimization algorithms for NMF, such as multiplicative update [Lee and Seung, 2001] and stochastic gradient descent (SGD) [Koren et al., 2009], are computationally expensive and cannot be simply applied to our problem. The former is costly for each round of parameter update, while the latter uses only a small number of data instances at each iteration. In this section, we will introduce a distributed algorithm for accelerated optimization.

3.1 Parallel Optimization Scheme

In parallel algorithms, concurrent implementations are required to be independent of each other to avoid interference. To have a clearer view of the objective function, as well as to schedule the updates of parameter batches, we rewrite Eq. (1) in the block-wise summation form as follows,

where B represents the number of splits on each dimension, and the superscripts denote the position of each block. An intuitive illustration of problem segmentation is shown in Fig.2. To approximate Gi,j ∈ RNi×Nj , we only need to update Wi and Wj , while the local factorization of Ai,k only involves Wi and Hk . The two dimensions of G are identically partitioned due to its symmetry. In practice, G and A can be segmented into nonuniform blocks, depending on the entry density in different matrix regions and computing resources available on different machines in a distributed system.

We design a parallel mini-batch SGD algorithm to efficiently solve the problem. To generalize, let L(θ) denote the objective function, where θ = {W,H} represents the parameters to learn. L(θ) = ∑U∈{i,j,k} LU(θ), in which U represents an instances set {Gi,j ,Ai,k ,Aj,k } across the two matrices. Starting from initial θ0, traditional mini-batch stochastic gradient descent refines the parameter by iterating the update: θt+1 = θt - ϵt∇LU(θt), where -∇LU(θ) is the steepest-descent direction of L(θ) over the data samples in U.

An example of instances set can be found in in Fig.2, where U = {G1,2 ,A1,3 ,A2,3 } makes W1 ,W2 ,H3 to be updated. However, sequential SGD does not fully utilize the computation bandwidth. Motivated by the concept of instance-level interchangeability [Gemulla et al., 2011], we propose the definition of interchangeable sets as below:

Definition 1. U1, U2 are interchangeable sets concerning a loss function L if any two instances u1 ∈ U1 and u2 ∈ U2 are interchangeable, where u1, u2 are interchangeable if

Interchangeable sets can be processed in parallel without interference. Two sets U1 = {Gi1,j1 ,Ai1,k1 ,Aj1,k1 } and U2 = {Gi2,j2 ,Ai2,k2 ,Aj2,k2 } are guaranteed to be interchangeable if i1 ̸= i2, j1 ̸= j2, k1 ̸= k2, i1 ̸= j2 and i2 ̸= j1. To fully utilize the computation resources and to guarantee interchangeability between instance sets, the parallel optimization scheme with three interchangeable sets is shown in Fig.2. Instance sets in different colors can be processed in parallel. Picking one data block will lock all other blocks in the same row or column at current iteration. The detailed optimization process can be found from line 2 ∼ 9 in Alg. 1. After obtaining the factor matrices W and H, we calculate the suspiciousness score of each node within various groups, and return the sorted node list where anomalies are ranked higher than normal objects (from line 10 ∼ 15 in Alg. 1).

3.2 Efficient Computation for Sparse Data

Many real-world networks are sparse, meaning that the number of links is usually very small [Zhang and Yu, 2015]. As a result, the gradient computation involving the blocks in G can be processed more efficiently as below:

where er is the column vector of length Ni with one 1 at position r and 0s otherwise. Here Gi,j is separated into two parts, a matrix of all zeros 0G ∈ RNi×Nj and a sparse matrix SG = {(r1, c1, g1), (r2, c2, g2), ...} in the form of the Algorithm 1: Accelerated Local Anomaly Detection in Attributed Networks Input: G, A, C, α, γ.

Output: A node list l sorted based on normality score.

• 1 InitializeW, H, and segment G, A,Wand H;
• 2 while not converged do
• 3 Randomly generate a set of 3-tuples: S = {(i1, j1, k1), (i2, j2, k2), ...} where any two instance sets are interchangeable;

4

7

9

Non-negativity projection for Wi , Wj and Hk ;

10 Normalize W and H according to Eq. (2);

11 for c = 1 : C do

12

Find members in group c: groupc = {nc1, nc2, ...}, so that

˜Wn,c ≥ τ for n ∈ groupc , where τ is the threshold;

13 Compute local normality score s(n, c), n ∈ groupc ;

14 Compute s(n) according to Eq. (3) as the global normality score for each n ∈ [1, N];

15 Return the sorted list of nodes l = {n1, n2, ..., nN} so that

s(n1) ≤ s(n2) ≤ ... ≤ s(nN).

(row, column, value) list. It is convenient for processing large sparse datasets since Gi,j can be stored in its sparse form throughout the computation. To approximate the matrix in which zero entries are dominant, we can randomly sample only a portion of zero entries as 0′G for parameters update at each iteration [Devooght et al., 2015], so that:

If we set the size of 0′G to be comparable to that of SG, then for each task, the time complexity for parameter update is linear to the number of links included in Gi,j , i.e. O(‖Gi,j ‖0), where ‖ · ‖0 means the 0-norm of a matrix. Similar strategies can be applied for factorizing blocks in A if it is sparse, then the time complexity for its update is O(‖Ai,k ‖0 + ‖Aj,k ‖0). Therefore, the time complexity of each iteration is O(‖Gi,j ‖0 + ‖Ai,k ‖0 + ‖Aj,k ‖0), which is linear to the number of data instances.

4 Experiments

In this section, we conduct experiments for evaluating the effectiveness and efficiency of ALAD compared with other baseline methods. We also perform case studies to illustrate how ALAD achieves interpretability.

4.1 Datasets

The experiments are conducted on both synthetic and real datasets. We generate a series of synthetic attributed networks with known clusters and ground-truth anomalies. The network generation algorithm is based on the partition model [Perozzi et al., 2014]. Once the total number of nodes N, the number of clusters C and the number of members in each cluster NC are determined, the adjacency matrix is partitioned into blocks. Let pij be the link density for (i, j)th block, where pii > pij(i ̸= j), so that diagonal blocks correspond to actual clusters. The number of connections per node is constrained to follow Zipf's law. We only consider undirected networks here. Unless otherwise stated, we set pi,i = 0.2 and pi,j = 0.5pi,i/C. To make the problem closer to real situations, we let each community i have a probability of 0.2 to have an exceptionally high connection rate (p′ij = 40pij) to another community j. Each cluster is assigned with a set of key attributes, and nodes within the same cluster are more likely to have similar attribute patterns. Only categorical attributes are considered. For attribute k, its value is drawn from a Bernoulli distribution with success probability of pc,k for cluster c. Key attributes are assigned with larger pc,k value. We set 10% of attributes to be key attributes, and pc,k = 0.3 for key attributes and pc,k = 0.02 for others. We generate five networks in the experiment. We fix N = 10,000, C = 100, and vary K = {100, 200, 300, 400, 500}. In each network, 100 anomaly nodes are randomly generated by distorting their attributes.

Besides synthetic networks, we employ four real-world datasets: Disney, Books [Muller et al., 2013], PolBlog [Perozzi et al., 2014] and DBLP [Silva et al., 2012]. Disney and Books are co-purchase networks extracted from Amazon. PolBlog is a citation network of online blogs. DBLP is an academic co-authorship network. The first two are used for quantitative comparison between our model and baseline methods, while the rest are applied in case studies. The statistics of these datasets are listed in Table 1. ra denotes the ratio of anomalies. Numerical attributes are transformed into categorical ones in preprocessing [Catlett, 1991].

4.2 Baseline Methods

The proposed anomaly detection algorithm ALAD is compared with the following baseline methods:

• CODA is a community-based anomaly detection algorithm on attributed networks using Hidden Markov Random Fields (HMRF) [Gao et al., 2010].
• LOF identifies contextual outliers using only attribute information based on the k-Nearest Neighbors algorithm [Breunig et al., 2000].
• GOutRank measures anomaly score of each node based on the statistics of its cluster [Muller et al., 2013].
• NrMF applies NMF for low-rank approximation, and uses residuals to measure anomaly score [Tong and Lin, 2011]. Here we use the sum of row-residuals as the anomaly score of each node.
• GLOB is the non-clustering version of ALAD, which detects global anomalies instead of local ones.
• ALAD TS is a two-stage variation of ALAD, where we first partition the network only using G and then detect outliers in each community using A. The hc of each cluster is the averaged attribute value over all members.

For each method, nodes are ranked in ascending order according to their normality (or abnormal) scores as the output, where a decent detection model would be able to rank the true anomalies earlier (or later) than normal ones. To evaluate the performance quantitatively, we use the Area Under PrecisionRecall Curve (AUC-PR) as the metric.

4.3 Effectiveness Evaluation

We first analyze the anomaly detection accuracy on synthetic attributed networks as shown in Fig.3. Some observations can be drawn as follows:

• ALAD outperforms baseline methods in most cases. The approaches that utilize both links and attributes information (CODA, NrMF, ALAD TS, ALAD) generally have better performance, which validates the importance of applying heterogeneous information sources.
• The advantage of ALAD and NrMF is more obvious as the number of attributes increases because of: (1) the promotion of the attributes' roles in discovering neighborhood; (2) the attenuated effect of noise from sampling process so that more accurate community structures are extracted.
• The performance of GLOB is worse than that of most other methods which perform anomaly detection regionally in networks. It thus justifies the importance of identifying anomalies within certain structural or semantic groups.
• The proposed ALAD is better than its two-stage variation, which validates the effectiveness of combining heterogeneous information for jointly determining neighborhoods and their internal attribute distributions.

The experimental results of different methods on realworld networks are presented in Table 2. Similar observations can also be drawn as synthetic data experiments. For examples, approaches accumulating the effect of individual attributes have better performance, and ALAD is better than its two-stage variation. The former phenomenon is more obvious in Books dataset where the network size is relatively larger, which is in accordance with the perception limitation of human labellers since it is more difficult for people to get a panoramic view as the network size grows.

To further investigate the significance of involving links in solving our problem, we remove the adjacency matrix from the datasets, and apply CODA, NrMF and ALAD on only the attribute matrix. Fig. 4 indicates the difference between jointly using heterogeneous information sources and using only attribute information. The absence of structural information weakens the capability of all detectors as reflected by lower AUC scores. It is also worth noting that the performances of CODA and ALAD are similar when only considering attribute information, which is reasonable since they are relevant with the K-means algorithm on attributes in this case.

4.4 Efficiency of ALAD

In this section, we study the efficiency of our model. The experiments are run on a Linux machine with 8 Intel i7 CPUs with 3.40GHz. The multiprocessing module in Python is used for parallel data processing. Although theoretically the distributed implementation of optimization processes can reduce the time of each iteration, we can benefit from it only when the computational load per task is not too small that the communication overheads start to dominate.

To evaluate the efficiency of our framework, we compare ALAD with its sequential version ALAD SEQ and CODA. LOF is not considered because it does not leverage structural information. GOutRank and NrMF are not included because they rely on the clustering result of ALAD. For ALAD SEQ, different blocks are processed sequentially. When implementing ALAD, we set B = 8 for Disney and Books, B = 16 for Polblog and Synthetic, and B = 24 for DBLP. The synthetic attributed network with 500 attributes is used. The running times of each method on different datasets are shown in Table 3. We do not obtain reasonable results of CODA on DBLP. The result shows that, when the dataset is relatively small, CODA is advantageous in speed since they do not have communication costs. However, as the data size grows larger, ALAD becomes more advantageous than the baseline methods. The speed-up effect of parallel implementation, especially when computational cost on each task is dominant over the system overhead.

4.5 Case Studies

The first case study we consider is on PolBlog dataset. As shown in Table 4, four sampled anomalies are listed for explanations. The attributes of each node are the words appeared in the text samples of blog websites. Here abnormal keywords refer to those with low frequency in the whole dataset corpus, but appear in the anomaly blogger. Therefore, the words of anomalies listed are lack of political flavor. Some of their posts actually focus on other topics such as wedding description (thepatriette.com), physics (opiniontimes.com) or food (ewackos.blogspot.com), which are not commonly discussed in political events. The result of the second case study on DBLP is shown in Table 5. We run ALAD on the network to detect research communities and internal outliers. The top frequent technical terms occurring in each community are shown in the right column. The anomalies are shown in the left column followed by their representative keywords. The anomalies are researchers whose research topic differs from those of their peers in the same community. For example, the papers of Marcel Dasen included in the dataset focus on computer networks, which is a less studied topic in information retrieval community. Therefore, ALAD can effectively summarize the topic distributions of network communities, and spot anomalies with different attribute patterns.

5 Conclusions and FutureWork

In this paper, we introduce an effective and efficient framework for identifying anomalies in attributed networks, where heterogeneous information sources are collectively used for determining refined neighborhood and locally assessing the normality of internal node entities. We develop a mini-batch SGD based method to accelerate the optimization and handle large datasets in real-world scenarios. Experiments on real and synthetic datasets indicate the effectiveness and efficiency of our approach. The future extensions of this work include studying the correlation between different attributes, dealing with dynamic networks that evolve over time, as well as detecting anomaly clusters instead of individuals.

Acknowledgments

The work is, in part, supported by DARPA (#N66001-17-24031, #W911NF-16-1-0565) and NSF (#IIS-1657196). The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.