Anomaly Detection in Temporal Graph Data: An Iterative Tensor Decomposition and Masking Approach

Anna Sapienza, André Panisson, Joseph Wu, Laetitia Gauvin, Ciro CattutoAALTD@PKDD/ECML 2015

Introduction

In the era of the Internet of Things (IoT), interaction data is increasingly abundant. From proximity sensors in office environments to traffic flow in smart cities, this data is most effectively represented as temporal graphs—networks that evolve over time. However, real-world data is frequently compromised by sensor failures, protocol deviations, and "mesoscale" anomalies. These anomalies are patterns that appear structurally normal but are actually data artifacts, which can significantly skew downstream analysis.

Researchers from the ISI Foundation and the University of Hong Kong have developed a robust solution: an iterative framework that utilizes Non-negative Tensor Factorization (NTF) to "mask" these anomalies, thereby revealing the true underlying social structure.

The Challenge of Mesoscale Anomalies

Traditional anomaly detection typically focuses on "point" anomalies (isolated outliers) or global shifts. In social networks, however, anomalies are often mesoscale, involving groups of actors behaving in ways that mimic legitimate interaction but are actually artifacts.

For instance, in a dataset involving school children wearing proximity sensors, a common anomaly occurs when teachers collect the sensors and store them together in a box at the end of the day. To a standard algorithm, this appears as a massive, high-density social gathering. These "protocol-induced" anomalies entangle both topology (who is interacting) and time (when it occurs), making them difficult to remove without losing legitimate data.

The Iterative Masking Framework

The proposed method treats the temporal graph as a three-mode tensor ($Nodes \times Nodes \times Time$). To clean this data, the researchers implemented a five-step iterative loop:

  1. Tensor Decomposition: Non-negative Tensor Factorization (NTF) decomposes the data cube into components, each consisting of a membership vector (involved nodes) and a temporal activity pattern.
  2. Classification: A classifier evaluates these temporal patterns to distinguish between normal social activity and anomalous signatures (e.g., the "sensors-in-a-box" pattern).
  3. Masking: For flagged components, a step-detection algorithm (Otsu thresholding) identifies specific time windows to create a "mask" for those interactions.
  4. Cleaning: The mask is applied to the original tensor, effectively erasing the invalid entries.
  5. Iteration: The process repeats with the cleaned tensor to uncover subtler anomalies previously hidden by larger ones.
Comparison of the original temporal profile, the cleaned data (A), and the ground truth metadata.

Experimental Evaluation

The framework was tested on a high-resolution social network dataset from a primary school in Hong Kong, involving 774 nodes (students and teachers) over 10 days. Proximity was recorded every 20 seconds and aggregated into 5-minute windows, resulting in 2,680 snapshots. A reference "clean" tensor was manually created to validate the algorithm's performance.

Results and Discussion

The iterative approach demonstrated a "peeling" effect, where removing dominant anomalies allowed the model to separate signal from noise more effectively. Over 23 iterations, the model showed significant convergence and accuracy.

The relative error (L1-norm) decreases and stabilizes over successive iterations, indicating model convergence.

Key performance metrics include:

  • Precision: 0.98, indicating that the model rarely erased legitimate social interactions.
  • Recall: 0.92, successfully identifying the vast majority of sensor-storage artifacts.
  • Overall Accuracy: 0.94, confirming the effectiveness of iterative masking for IoT data cleaning.

Conclusion

By leveraging the multi-dimensional nature of tensors, this framework successfully links "who" and "when" to identify context-dependent anomalies. While computationally intensive, the method's ability to incorporate domain knowledge through semi-supervised classification makes it a powerful tool for processing complex temporal graph data. Future work may involve incorporating spatial coordinates to further refine the surgical precision of the detection process.

Summary updated

BibTeX
@inproceedings{sapienza2015anomaly,
  author = {Anna Sapienza and André Panisson and Joseph Wu and Laetitia Gauvin and Ciro Cattuto},
  title = {{Anomaly Detection in Temporal Graph Data: An Iterative Tensor Decomposition and Masking Approach}},
  booktitle = {AALTD@PKDD/ECML},
  year = {2015},
}
Figure