Pre-Conference Talk by QIAO Hezhe | Truncated Affinity Maximization: One-class Homophily Modeling for Graph Anomaly Detection

Graph anomaly detection (GAD) aims to identify abnormal nodes that are different from the majority of the nodes in a graph. It has attracted great research interest in recent years due to its broad real-world applications, e.g., detection of abusive reviews or malicious/fraudulent users. Since graph data is non-Euclidean with diverse graph structure and node attributes, it is challenging to effectively model the underlying normal patterns and detect abnormal nodes in different graphs. To address this challenge, graph neural networks (GNNs) have been widely used for GAD. The GNN-based methods are often built using a data reconstruction or self-supervised learning  objective. These approaches, however, ignore one prevalent anomaly-discriminative property we find empirically in real-world GAD datasets, namely one-class homophily, i.e., normal nodes tend to have strong connection/affinity with each other, while the homophily in abnormal nodes is significantly weaker. In this work, we empirically reveal the one-class homophily phenomenon that provides an anomaly-discriminative property for GAD. Motivated by this property, we introduce a novel unsupervised anomaly scoring measure, local node affinity. We then introduce Truncated Affinity Maximization (TAM) that learns tailored node representations for the proposed anomaly measure. TAM makes full use of the one-class homophily to learn expressive normal representations by maximizing local node affinity on truncated graphs, offering discriminative local affinity scores for accurate GAD.  We further introduce two novel components namely Local Affinity Maximization based graph neural networks and Normal Structure-preserved Graph Truncation, to implement TAM. Empirical results on ten real-world GAD datasets show that our TAM model substantially outperforms seven competing models.

This is a Pre-Conference talk for Thirty-seventh Conference on Neural Information Processing Systems (NeurIPS 2023).