Uncovering Specific-Shape Graph Anomalies in Attributed Graphs


  • Nannan Wu Tianjin University
  • Wenjun Wang Tianjin University
  • Feng Chen State University of New York at Albany
  • Jianxin Li Beihang University
  • Bo Li Beihang University
  • Jinpeng Huai Beihang University




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.




How to Cite

Wu, N., Wang, W., Chen, F., Li, J., Li, B., & Huai, J. (2019). Uncovering Specific-Shape Graph Anomalies in Attributed Graphs. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 5433-5440. https://doi.org/10.1609/aaai.v33i01.33015433



AAAI Technical Track: Machine Learning