Unveiling rare or anomalous data is of paramount importance in numerous applications such as recommender systems, finance, security, health care, autonomous driving and insurance [1]. Anomaly identification methods can spot network intrusions and failures, spam reviews, credit card frauds, malware and rare disease outbreaks.
The present work focuses on anomalies that appear in data adhering to a graph structure. Consider a graph that consists of nodes and edges, where each node is associated with an attributed vector. In an IoT network for example, the nodes represent mobile devices and the edges capture the communication among devices. The graph connectivity may be perturbed e.g. by an adversary who adds edges possibly at random. Examples of such anomalous edges include links among nodes belonging to different communities or among nodes with uncorrelated attributes. Leveraging the graph structure and the correlation of nodal features will enable identification of anomalous edges.
Anomalies can emerge in either static or dynamic graphs. Dynamic ones comprise sequences of graphs and the corresponding methods leverage temporal correlation too [2], [3],
The work in this paper was supported by the NSF grants 1901134, 171141, and 1500713.
Emails: {polyz003, mavro016, ioann006, georgios}@umn.edu * Equal Contribution. [4], [5], [6], [7], [8]. The focus here will be on static graphs, but dynamic graphs are also included in our future research agenda.
Most anomaly detection methods for static graphs pursue community-based approaches. They primarily rely on matrix factorization techniques that decompose the graph matrix into a low rank component and a residual matrix [9], [10]. Matrix factorization is widely employed for dimensionality reduction [11], [12] and (graph) clustering [13]. The approach in [10] spots anomalous connections if they appear in the residual matrix, after the non-negative matrix factorization.
Albeit interesting, the aforementioned methods do not account for attributes. On the other hand, approaches have been reported that incorporate nodal features to unveil anomalous nodes [14], [15], [16], [17], [18], [19], [20]. These are suitable to spot anomalous nodes within a certain community, but not anomalous edges across communities [21].
Contribution. The present work proposes two novel approaches that rely on low rank and sparse factorization, and judiciously account for nodal attributes to spot anomalous edges in a given perturbed graph. The second approach further recovers the ground-truth topology, which turns out to markedly enhance identification performance. Accounting for smoothness across nodal features also boosts identification performance. Different from existing approaches, the novel methods not only identify anomalous links between different communities, but also mendacious edges between any two nodes based on the nodal features. Finally, two optimization methods with complementary strengths are developed to unveil the anomalous edges and robustly recover the underlying nominal topology. Although the first method is computationally more efficient, the second unveils more accurately the perturbed edges. Complexity analysis of the developed methods is also provided.
Consider a graph that consists of N nodes and E edges connecting pairs of nodes. Connectivity is captured by the N × N adjacency matrix A. The initial (a.k.a. nominal) graph is perturbed by inserting (anomalous) edges linking nodes with correlated or uncorrelated nodal features. Let à denote the perturbed adjacency, and Ẽ the set of perturbed edges. The N × N Laplacian matrix is where 1 is the all-ones vector and diag(•) is a diagonal matrix. Each node n also holds an F × 1 feature vector x n , and all feature vectors are collected in the N × F feature matrix X. For example, in a network that consists of voters, attributes may correspond to each voter's age and state of residency. Goal. Given the perturbed Laplacian matrix L ∈ R N ×N and the feature matrix X, this paper aims to unveil the anomalous edges in Ẽ and recover the unperturbed Laplacian matrix L. Fig. 1 shows a perturbed social voting network.
Anomalous edges often connect nodes belonging to different communities [1], [7], [9], [10]. For example, in a typical social voting network, each node is either Republican or Democrat, and connections between nodes across the isle are rare [1].
Factorizing the Laplacian matrix of a graph is known to reveal the community structure [7], [13], [10], [22]. Specifically, the low-rank approximation of the Laplacian yields the communities, while the low rank captures the number of communities. To retrieve anomalous edges connecting different clusters, it is possible to augment the decomposition with a sparse matrix containing edges that connect different communities, and hence do not obey the low-rank model [3], [7], [10]. Upon accounting for the low-rank approximation matrix R and the sparse matrix S, our formulation amounts to
where • F denotes the Frobenius norm; • 1 the 1 norm;
• * the nuclear norm; and, λ, µ > 0 are properly chosen regularization parameters. The 1 norm controls sparsity of S, while the nuclear norm equals the 1 norm applied to the vector of singular values of R, which promotes R to be low rank [23]. The nonzero entries of S reveal the anomalous edges that do not adhere to the low rank model.
Albeit interesting, the approach in (2) does not leverage the feature matrix X. In the social voting network paradigm, two individuals with opposing political views may be friends because they live in the same state or belong to the same age group (cf. Fig. 1). The next section outlines our modeling approach that incorporates nodal features when available.
Smoothness of signal models has been widely adopted by several learning methods in the form of regularization for e.g., (semi-)supervised learning over graphs [24]. Intuitively, X is deemed smooth if features of connected vertices have similar values. This principle suggests, for instance, estimating one person's age by looking at their friends' age [25], [26].
Smooth features among neighboring nodes are captured by the so-termed Laplacian regularizer [25], [26], [27]
where a ij = 0 only if nodes i and j are connected, Tr denotes matrix trace, and T stands for transposition. The value of ( 3) is small if neighboring vertices have similar signal values and high otherwise. Thus, minimizing (3) penalizes differences between features of connected nodes.
Incorporating feature smoothness, (2) boils down to (cf. ( 3))
where γ > 0 tunes the degree of smoothness. The nonzero entries of S reveal edges that do not adhere to the low rank model with smooth features. The next subsections provide alternative formulations of (4), and corresponding optimization solvers with complementary benefits.
As both the nuclear and 1 norms are non-differentiable at the origin, the optimization problem (4) is convex but nonsmooth. Although iterative solvers of (4) are available, they rely on performing a costly singular value decomposition per iteration, which incurs prohibitive computational complexity, especially for large-scale graphs [2], [28].
A prudent strategy to bypass this hurdle relies on the factorization R = UV T , where U, V are N ×R matrices with R denoting an upper bound on the rank of R. Specifically, it holds that [29], [30]
Combining ( 5) with ( 4), the optimization in (4) reduces to
Although ( 6) is non-convex, alternating minimization solvers can be employed with closed-form updates. Different from (4), problem ( 6) can be solved in a distributed fashion.
We developed an alternating least-squares (ALS) solver of (6) whose steps are listed under Algorithm 1. Our ALS is provably convergent, but the proof is omitted due to space limitations.
The formulation in (4), focused solely on retrieving the anomalous edges. However, one can also approximate the unperturbed graph structure, and thus aid the identification of anomalous edges. This subsection deals with robust estimation of the nominal graph topology too, and further improving identification of the anomalous edges.
Graph connections capture correlations among nodal feature vectors; see [31] for a comprehensive survey. Learning the graph structure by leveraging the statistical properties of the features will endow estimation with increased robustness to anomalies. Popular approaches to estimating graph structure are closely related to the sparse inverse covariance matrix estimation [32], [33], [34]. The graph Laplacian can be approximated similarly by estimating the sparse inverse covariance matrix [35], [32], [36]. Specifically, the sparse inverse covariance selection problem [35] is formulated as follows
where Tr(XX T Θ) -log det(Θ) minimizes the negative log-likelihood, while Θ 1 promotes sparsity. The term Tr(XX T Θ) is closely related to the smoothing term Tr(X T RX) of ( 4), and holds the feature correlation information. Although Θ captures feature correlations (Θ ij = 0 if nodes i and j have conditionally correlated features), it is not necessarily a valid Laplacian.
To cope with this challenge, we couple ( 2) and ( 7), and introduce due constraints to recover the unperturbed graph Laplacian and the anomalies min R,S,Θ 0
where (8b), (8c), (8d) constrain the learned R to be positive semidefinite and thus a valid Laplacian, while R -Θ 2 F seeks a Laplacian that stays close to Θ but also couples ( 2) with ( 7) (closeness is tuned by the scalar κ > 0). The number of edges in the sought Laplacian is benchmarked by m (cf. (8b)), while α > 0 weighs the degree of smoothness in ( 2) and (7).
The problem in ( 8) is convex and can be solved using either well known optimization solvers (e.g interior point schemes), or, the alternating direction method of multipliers (ADMM) method that can also afford for distributed implementation; we will henceforth refere to this ADMM solver of ( 8)) as Algorithm 2. Note also that upon recovering the Laplacian, the adjacency matrix can be readily obtained.
Algorithm 1 ALS for (6) 1: Initialize l = 0, U (l) , V (l) , S (l) 2: while not converged do 3:
6: l = l + 1 7: end while Computational complexity. The U and V updates under Algorithm 1 are available in closed form, while S is updated entry wise using the soft threshold operator [37]. Considering R F N , the most computationally expensive operation is matrix multiplication between N × N and N × R matrices. Therefore, the overall complexity per step is O(N 2 R) [38].
Algorithm 2 minimizes a convex function under (8b), (8c), and (8d) that can be expressed as linear constraints [39]. This implies that (8) can be efficiently solved in O(log( 1)) interior point sub-iterations; see e.g., [40], [41], [42], [43], [44]. Accounting also for the SVD computations O(N 3 ), and matrix multiplications, the overall complexity is O(log( 1 )N 3 ).
This section evaluates the anomaly identification performance of the novel methods with real and synthetic graph datasets.
Stochastic block model (SBM). SBMs are synthetic networks that consist of C communities. The feature matrix is formed by the F eigenvectors of the Laplacian matrix that correspond to the F smallest eigenvalues. Such features are smooth with respect to the graph [25]. The generated stochastic block model networks are denoted as SBM(C,F ).
Aarhus network. The Aarhus dataset is a social network that consists of 32 employees (nodes) from the Computer Science Department of Aarhus University and represents their lunch relations (edges) [45]. The 32×26 feature matrix X is a binary matrix that represents the lunch relationships between the 32 employees from Computer Science department and another group of 26 people.
In the SBM, anomalous edges are randomly added between nodes that belong to different communities, while in the Aarhus dataset, anomalous edges are inserted randomly between any two nodes. After the optimization, edges with negative (nonzero) values in S are collected in the set Ê. Edges in Ê are sorted in ascending order so that possible anomalous edges are ordered by probability of correct detection. The tests are repeated 10 times and the average percentage values of the following metrics are reported. Hit rate@10 (H@10), which indicates how many edges are correctly identified as anomalous, given the first 10 candidate anomalous edges of Ê.
Mean reciprocal rank (MRR). Each edge of Ê receives a reciprocal rank score (if correctly identified as anomalous) based on its position in Ê: 1 for first place, 1/2 for second place, 1/3 for third place, and so on. MRR is the average of reciprocal ranks of all correctly identified anomalous edges.
Table I illustrates the best evaluation results for different methods after systematic parameter search. The following baseline methods are considered. The method in (2) that is employed by various approaches, e.g [7], and does not consider feature smoothness and a random-guess method that selects a random subset of the edges as anomalous.
Both proposed methods significantly outperform the baseline, which speaks for the importance of smoothness constraints for anomaly identification. The improvements on H@10 accuracy metric compared to the baseline ranges from 1.9 times higher (Aarhus, Algorithm 1) to 3.8 times higher (SBM(8,4), Algorithm 2). Improvements on MRR ranges from 1.2 times (SBM (8,4), Algorithm 1) to 3.5 times higher (Aarhus, Algorithm 2). The highest values of H@10 and MRR are observed in the Aarhus dataset (∼ 72% and 88.4% respectively). In all cases, our second algorithm outperforms the first one in the MRR metric due to its ability to approximate the exact topology of the original graph, which enhances the anomaly identification performance. On the other hand, although Algorithm 2 achieves better anomaly identification performance, it is less computationally efficient compared to Algorithm 1.
Finally, Figure 2 illustrates the estimated graph topology by the second method, compared to the ground truth topology on two datasets. As a baseline method, method (7) is used, which is employed by various approaches, e.g. [46]. These qualitative results confirm that the second method captures the main topological structure of the original graph, while its topology estimation is closer to the ground truth topology than the baseline method.
The present work aims at identifying anomalous edges on attributed networks. Two novel approaches are formulated to jointly leverage the low rank plus sparse decomposition of the Laplacian of the perturbed graph, along with feature smoothness. Extensive numerical tests corroborate that the novel adaptation of feature smoothness markedly improves the anomaly identification performance and the proposed methods outperform the baseline. Future research directions include robust topology identification, robust community detection by employing ego-tensors [47], and anomaly identification on dynamic and knowledge graphs.
Authorized licensed use limited to: University of Minnesota. Downloaded on July 09,2021 at 00:39:30 UTC from IEEE Xplore. Restrictions apply.