Subset Node Anomaly Tracking over Large Dynamic Graphs
Subset Node Anomaly Tracking over Large Dynamic Graphs
复制标题
DOI：
10.1145/3534678.3539389
复制
发表时间：
2022-05
期刊：
影响因子：
--
通讯作者：
Xingzhi Guo;Baojian Zhou;S. Skiena
中科院分区：
文献类型：
--
作者：
Xingzhi Guo;Baojian Zhou;S. Skiena
在进化图中跟踪目标节点子集对于许多现实世界的应用来说是重要的。现有的方法通常集中在识别异常边缘或以流的方式发现异常图快照。然而，面向边的方法无法量化单个节点如何随时间变化，而其他方法则需要始终保持整个图的表示，因此计算效率低下。本文提出了DynAnom，一个有效的框架来量化的变化和本地化的每个节点的异常在大型动态加权图。得益于基于Personalized PageRank的动态表示学习的最新进展，DynAnom 1）高效：时间复杂度与边缘事件的数量呈线性关系，与输入图的节点大小无关; 2）有效：DynAnom可以成功跟踪反映真实世界异常的拓扑变化; 3）灵活：可以为各种应用定义不同类型的异常评分函数。实验证明了这些属性的基准图数据集和一个新的大型真实世界的动态图。具体而言，基于DynAnom的实例化方法在节点级异常定位任务上实现了0.5425的准确度，而最佳基线为0.2790，同时运行速度比基线快2.3倍。我们提出了一个真实的案例研究，并进一步证明了DynAnom的可用性异常发现在大规模的图形。
Tracking a targeted subset of nodes in an evolving graph is important for many real-world applications. Existing methods typically focus on identifying anomalous edges or finding anomaly graph snapshots in a stream way. However, edge-oriented methods cannot quantify how individual nodes change over time while others need to maintain representations of the whole graph all the time, thus computationally inefficient. This paper proposes DynAnom, an efficient framework to quantify the changes and localize per-node anomalies over large dynamic weighted-graphs. Thanks to recent advances in dynamic representation learning based on Personalized PageRank, DynAnom is 1) efficient: the time complexity is linear to the number of edge events and independent of node size of the input graph; 2) effective: DynAnom can successfully track topological changes reflecting real-world anomaly; 3) flexible: different type of anomaly score functions can be defined for various applications. Experiments demonstrate these properties on both benchmark graph datasets and a new large real-world dynamic graph. Specifically, an instantiation method based on DynAnom achieves the accuracy of 0.5425 compared with 0.2790, the best baseline, on the task of node-level anomaly localization while running 2.3 times faster than the baseline. We present a real-world case study and further demonstrate the usability of DynAnom for anomaly discovery over large-scale graphs.