Anomaly Detection in Temporal Graph Data: An …

1 Proceedings 1st International Workshop on Advanced Analytics and Learning on Temporal DataAALTD 2015 Anomaly Detection in Temporal Graph Data: an iterative Tensor Decomposition and MaskingApproachAnna Sapienza1,2, Andr e Panisson2, Joseph Wu3,Laetitia Gauvin2, , Ciro Cattuto21 Polytechnic University of Turin, Turin, Italy2 data Science Laboratory, ISI Foundation, Turin, Italy3 School of Public Health, University of Hong Kong, Hong and Internet-of-Things scenarios promise a wealthof interaction data that can be naturally represented by means of time-varying graphs. This brings forth new challenges for the identification andremoval of Temporal Graph anomalies that entail complex correlations oftopological features and activity patterns.

2 Here we present an anomalydetection approach for Temporal Graph data based on an iterative tensordecomposition and masking procedure. We test this approach using high-resolution social network data from wearable sensors and show that itsuccessfully detects anomalies due to sensor wearing time : data cleaning, Anomaly Detection , non-negative tensor fac-torization, high-resolution social networks, sensors, Temporal IntroductionEmerging applications in the big data and Internet-of-Things domains pose newproblems for data cleaning. Time-resolved interaction data , in particular, areespecially challenging because the relational nature of the data yields anomaliesthat entangle Temporal and topological aspects.

3 Several studies have focused onidentifying anomalous behaviors in Graph -based datasets [1] and time-varyingnetworks [2]. However, mesoscale anomalies that mimic normal behaviors areobserved in empirical data and call for further we focus on time-varying graphs [3] represented as three-mode tensorsand we present an semi-supervised Anomaly Detection method based iterativetensor decomposition and masking. We report on the performance of this methodin detecting and removing anomalies in an empirical social network dataset gath-ered by using wearable proximity sensors in a MethodologyA static Graph can be represented by an adjacency matrixM RN N, whereMij= 1 if a contact betweeniandjoccurred andMij= 0 otherwise.

4 Thisdescription can be generalized to the case of a time-varying Graph , by using asequence ofSconsecutive adjacency matrices, that can be easily arranged as atensorT RN N 2015 for this paper by its authors. Copying permitted for private and Sapienza, A. Panisson, J. Wu, L. Gauvin, C. CattutoThe extraction of latent structures can then be performed by following theiterative approach described below. This framework allows to carry out the datacleaning by unearthing at each iteration group behaviours of nodes having cor-related activities and classifying these patterns of activities as meaningul Non-negative Tensor Factorization [6] is used as a powerful toolto approximate the tensorTas a sum ofRrank-one tensorsar br cr, calledcomponents.

5 In the specific case of Temporal networks,arandbrprovide themembership of nodes to the componentr, whereascris the Temporal activitypattern of the component. Moreover, it is possible to considerar brif thegraph is undirected. The components can be recovered by solving an optimizationproblem with non-negative constraints. The minimization problemmin tijk R m=1R n=1R l=1aimajnckl , ajn, ckl 0(1)is computed by the alternating non-negative least squares method [7], solvedby using the block principal pivoting algorithm [8]. The selection of a suitablenumberRof components is guided at each iteration by the Core ConsistencyDiagnostic [9, 10], and performed in order to prevent extracted components are analysed in order to discriminatebetween those dominated by anomalous activities or meaningful behaviours.

6 Tothis end, a classifier working on the Temporal activity patterns of each componentcrwas contact patterns highlighted by the anomalous componentsare combined into a mask, used to clean the original tensor. The nodes involvedin each of these contacts are detected by analysing the level of membershipgiven byar. The occurrence times of these contacts are given by the anomalouswindows found in the Temporal patternscr. These windows are recovered byusing a step Detection algorithm based on the Otsu threshold [11].Step mask is applied to the tensorTin order to erase the invalidentries.

7 The cleaned tensorT becomes then the input of the consecutive iterationin the iterative procedure is repeated until no component is classified as anoma-lous in step Results and ValidationThe current investigation involves the analysis of a high-resolution dataset whichdescribes the interactions of people in a primary school in Hong Kong. The schoolpopulation consisted in 709 children and 65 teachers divided into 30 classes. Datawere collected by using wearable proximity sensors [4, 5] over 10 consecutive daysin March 2013, from Monday 18th to Thursday 27th. These sensors record spatialproximity with a resolution of 20s.

8 As a result, a time-varying network withN= 774 nodes was created. The data were then aggregated over a time-windowof 5min, leading to a division of the overall network inS= 2680 Detection in Temporal Graph Data3 The protocol was as follows: the proximity of the sensors was recorded duringthe whole experiment duration, and the sensors were grouped in each class atthe end of the school day. Hence, activity patterns composed by strong steadycontacts withinh each class were observed during the school closing time. Inorder to clean the data , these anomalous patterns must be retrieved.

9 A gen-eral methodology is thus developed here to deal with the Anomaly Detection oftemporal Graph -based data , and then used to perform the data cleaning of thepresent 1:Total contact number measured in the original, metadata and cleaned(A) tensors with respect to obvious amount of contacts in the originalstate is distributed along the entire time-line. By contrast, the cleaning proceduremanaged to identify and erase most of the results after 23 iterations of the iterative framework presented in Section2 are summarised in Fig. 1, that shows the total contact number evolving intime measured in the original tensor and in the cleaned tensor generated bythe iterative process.

10 The total amount of contacts during the school closureis extremely reduced as a result of the cleaning process. Normal interactionsbelonging to the classes emerge and meaningful patterns are order to validate the method, a reference tensor was created and used asa ground truth. To this end, anomalous behaviours were identified and removedfrom the original dataset by applying the step Detection on the Temporal contact4A. Sapienza, A. Panisson, J. Wu, L. Gauvin, C. CattutoFig. 2: Relative error, computed at eachiteration by using 1: Retrieval measures of tensorentry labelling.