Uncovering Specific-Shape Graph Anomalies in Attributed Graphs
Uncovering Specific-Shape Graph Anomalies in Attributed Graphs
复制标题
DOI：
10.1609/aaai.v33i01.33015433
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Nannan Wu;Wenjun Wang;Feng Chen;Jianxin Li;B. Li;J. Huai
中科院分区：
文献类型：
--
作者：
Nannan Wu;Wenjun Wang;Feng Chen;Jianxin Li;B. Li;J. Huai
随着网络在现代社会的普遍存在，点异常已经被改变为异常形状的图形异常。然而，传统的方法在检测属性图中的子图时很少考虑感兴趣的异常子图的特定形状先验（例如，计算机网络、比特币网络等）。提出了一种非线性的特定形状图异常检测方法。非线性方法的重点是通过属性图中的特定形状约束来优化广泛的一类非线性成本函数。我们的方法可以用于许多不同的图形异常设置。传统的方法只能支持线性成本函数（例如，用于节点权重求和的聚集函数）。然而，我们的方法可以采用更强大的非线性成本函数，并享有严格的理论保证的几何收敛速度的近最优解。
As networks are ubiquitous in the modern era, point anomalies have been changed to graph anomalies in terms of anomaly shapes. However, the specific-shape priors about anomalous subgraphs of interest are seldom considered by the traditional approaches when detecting the subgraphs in attributed graphs (e.g., computer networks, Bitcoin networks, and etc.). This paper proposes a nonlinear approach to specific-shape graph anomaly detection. The nonlinear approach focuses on optimizing a broad class of nonlinear cost functions via specific-shape constraints in attributed graphs. Our approach can be used to many different graph anomaly settings. The traditional approaches can only support linear cost functions (e.g., an aggregation function for the summation of node weights). However, our approach can employ more powerful nonlinear cost functions, and enjoys a rigorous theoretical guarantee on the near-optimal solution with the geometrical convergence rate.