Sensors and Internet-of-Things scenarios promise a wealth of interaction data that can be naturally represented by means of timevarying graphs. This brings forth new challenges for the identi cation and removal of temporal graph anomalies that entail complex correlations of topological features and activity patterns. Here we present an anomaly detection approach for temporal graph data based on an iterative tensor decomposition and masking procedure. We test this approach using highresolution social network data from wearable sensors and show that it successfully detects anomalies due to sensor wearing time protocols.
Emerging applications in the big data and Internet-of-Things domains pose new
problems for data cleaning. Time-resolved interaction data, in particular, are
especially challenging because the relational nature of the data yields anomalies
that entangle temporal and topological aspects. Several studies have focused on
identifying anomalous behaviors in graph-based datasets [
Here we focus on time-varying graphs [
Copyright c 2015 for this paper by its authors. Copying permitted for private and academic purposes.
The extraction of latent structures can then be performed by following the iterative approach described below. This framework allows to carry out the data cleaning by unearthing at each iteration group behaviours of nodes having correlated activities and classifying these patterns of activities as meaningul or anomalous.
Step 1. The Non-negative Tensor Factorization [
R R R
X X X aimajnckl
m=1 n=1 l=1
2
F
s.t. aim; ajn; ckl
0
(1)
is computed by the alternating non-negative least squares method [
Step 2. The extracted components are analysed in order to discriminate between those dominated by anomalous activities or meaningful behaviours. To this end, a classi er working on the temporal activity patterns of each component cr was developed.
Step 3. Spurious contact patterns highlighted by the anomalous components
are combined into a mask, used to clean the original tensor. The nodes involved
in each of these contacts are detected by analysing the level of membership
given by ar. The occurrence times of these contacts are given by the anomalous
windows found in the temporal patterns cr. These windows are recovered by
using a step detection algorithm based on the Otsu threshold [
Step 4. The mask is applied to the tensor T in order to erase the invalid entries. The cleaned tensor T 0 becomes then the input of the consecutive iteration in the iterative framework.
Step 5. The procedure is repeated until no component is classi ed as anomalous in step 2. 3
The current investigation involves the analysis of a high-resolution dataset which
describes the interactions of people in a primary school in Hong Kong. The school
population consisted in 709 children and 65 teachers divided into 30 classes. Data
were collected by using wearable proximity sensors [
The protocol was as follows: the proximity of the sensors was recorded during the whole experiment duration, and the sensors were grouped in each class at the end of the school day. Hence, activity patterns composed by strong steady contacts withinh each class were observed during the school closing time. In order to clean the data, these anomalous patterns must be retrieved. A general methodology is thus developed here to deal with the anomaly detection of temporal graph-based data, and then used to perform the data cleaning of the present problem.
The results after 23 iterations of the iterative framework presented in Section 2 are summarised in Fig. 1, that shows the total contact number evolving in time measured in the original tensor and in the cleaned tensor generated by the iterative process. The total amount of contacts during the school closure is extremely reduced as a result of the cleaning process. Normal interactions belonging to the classes emerge and meaningful patterns are recovered.
In order to validate the method, a reference tensor was created and used as a ground truth. To this end, anomalous behaviours were identi ed and removed from the original dataset by applying the step detection on the temporal contact densities of each class. The ensuing tensor was compared with the cleaned tensor T 0 at each iteration, by computing the relative error with the L1-norm. This quantity, shown in Fig. 2, monotonically decreases with the number of steps of the iterative approach and stabilizes around the low value of 0:2.
The reference tensor was then used to label the entries of the original tensor as anomalous or meaningful, in order to compute the confusion matrix summarizing the performances of the iterative approach. The resulting recall and precision values at each entry level reported in Tab. 1 and the overall accuracy of 0:94 highlight the high performance of the iterative approach. 4
Time-varying graphs can expose both topology and temporal correlations, which make the anomaly detection a major challenge. The iterative approach introduced here captures such correlations and enables to discriminate between meaningful and anomalous patterns. The evaluation measurements of the anomaly detection, achieved on the primary school dataset, highlights the high performance of the implemented method.
This iterative method is a principled approach, which provides an unsupervised way to identify and select meso-scale data anomalies. However, some limitations are worth noting. The method relies on the temporal activity pro le of a latent component to be able to classify it as anomalous or not. Moreover, the implication of the NTF makes the iterative approach computationally costly, in terms of memory and time. The latter problem is being tackled as a lot of research is devoted to improve the e ciency of the implementation.
Finally, the iterative framework could be extended to the case of a greater number of dimensions, e.g. with sensors localized in space. 5
This research was supported by the Lagrange Project of the ISI Foundation funded by the CRT Foundation, by the Q-ARACNE project funded by the Fondazione Compagnia di San Paolo, by the FET Multiplex Project (EU-FET-317532) funded by the European Commission, and by the Harvard Center for Communicable Disease Dynamics from the National Institute of General Medical Sciences (grant no. U54 GM088558). The funding bodies had no role in study design, data collection and analysis, preparation of the manuscript, or the decision to publish.