Unsupervised Anomalous Vertices Detection Utilizing Link Prediction Algorithms

Dima Kagan, Michael Fire, Yuval EloviciarXiv 2016 · arXiv

Introduction

In the era of massive social and computer networks, detecting "bad actors"—such as bots, intruders, or fake reviewers—is a persistent challenge. Traditional detection systems often rely on supervised learning, which requires extensive labeled data that is difficult and expensive to obtain. Furthermore, many existing methods are domain-specific, limiting their applicability across different types of networks.

Kagan, Elovici, and Fire (2017) propose a novel, unsupervised approach that utilizes the inherent structural logic of a network to identify anomalies. Their method assumes that anomalous nodes, such as bots or hackers, exhibit connection patterns that deviate significantly from the natural "social logic" of the graph.

Methodology: The Two-Layered Framework

The proposed algorithm operates in two distinct stages to identify outliers based purely on network topology.

The system first trains a link predictor (typically a Random Forest classifier) using topological features such as Jaccard’s Coefficient, the Adamic-Adar Index, and Preferential Attachment. This predictor learns the "rules" of connectivity within the specific network, assigning a probability score to the existence of any potential edge.

Layer 2: Anomaly Meta-Classification

Instead of predicting new links, the second layer evaluates existing edges. It aggregates the confidence scores from the link predictor for all edges connected to a specific vertex. The researchers introduced several meta-features, most notably the Abnormality Vertex Probability, which represents the average probability that a node's existing connections are "improbable" according to the network's learned logic.

Final classification of vertices, where red nodes indicate detected anomalies based on aggregated link probabilities.

Experimental Results

The algorithm was tested on ten different networks, ranging from fully synthetic Barabási-Albert models to real-world datasets like Twitter and a 19th-century school friendship network.

  • High Precision: In semi-simulated networks (e.g., ArXiv, DBLP), the method achieved an average AUC of 0.99.
  • Real-World Efficacy: On Twitter data, the algorithm significantly outperformed baseline methods, achieving a precision of 35% at 100 samples compared to 8% for the "Stranger" algorithm.
  • Low False Positives: The method maintained a very low average False Positive Rate (FPR) of 0.006, which is crucial for practical deployment in security contexts where false alarms are costly.

Discussion and Conclusion

A key insight of this research is that link prediction—traditionally used for recommendation systems—serves as an excellent diagnostic tool for anomalies. If a node's neighbors are individuals the algorithm would rarely suggest, that node is likely acting randomly or maliciously.

Because the method relies solely on network topology, it is content-agnostic and resilient to privacy restrictions. However, future work is needed to address "strategic" anomalies that intentionally mimic normal patterns and to incorporate temporal dynamics in evolving networks.

Reference: Kagan, D., Elovici, Y., & Fire, M. (2017). Generic Anomalous Vertices Detection Utilizing a Link Prediction Algorithm. arXiv:1610.07525v4 [cs.SI].

Summary updated

BibTeX
@misc{kagan2016unsupervised,
  author = {Dima Kagan and Michael Fire and Yuval Elovici},
  title = {{Unsupervised Anomalous Vertices Detection Utilizing Link Prediction Algorithms}},
  year = {2016},
  eprint = {1610.07525},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1610.07525},
}
Figure