EagleMine: Vision-Guided Mining in Large Graphs

Abstract

Given a graph with millions of nodes, what patterns exist in the distributions of node characteristics, and how can we detect them and separate anomalous nodes in a way similar to human vision?

In this paper, we propose a vision-guided algorithm, EagleMine, to recognize and summarize graph node groups in feature spaces. EagleMine hierarchically discovers node groups, and each group is an internally connected dense area in some feature space. EagleMine utilizes a water-level tree to capture group structures according to vision-based intuition at multiple resolutions. EagleMine traverses the water-level tree, applying statistical hypothesis test to determine the optimal node groups that should be fitted along the path. Moreover, EagleMine can identify anomalous micro-clusters (i.e., micro-size groups), who exhibit very similar behavior in some feature space, and deviate away from the majority. Experiments on real-world data show that our method can recognize intuitive groups as human vision does, and achieve the best performance in summarization compared to baselines. In terms of anomaly detection, EagleMine also outperforms well-known state-of-the-art graph-based methods by significantly improving accuracy in a microblog dataset.

KDD ODD v5.0 2018 [ paper | appendix | poster | slides | code and datasets ]