Uncovering Specific-Shape Graph Anomalies in Attributed Graphs

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.

Authors

• Nannan Wu Tianjin University
• Wenjun Wang Tencent
• Feng Chen
• Jianxin Li Beihang University
• Bo Li Department of Computing, The Hong Kong Polytechnic University
• Jinpeng Huai

Keywords

No keywords are indexed for this paper.