Learning From Graph-Graph Relationship: A New Perspective on Graph-Level Anomaly Detection

Graph-level anomaly detection (GLAD) aims to distinguish anomalous graphs that exhibit significant deviations from others. The graph-graph relationship, revealing the deviation and similarity between graphs, offers global insights into the entire graph level for highlighting the anomalies’ divergence from normal graph patterns. Thus, understanding graph-graph relationships is critical to boosting models on GLAD tasks. However, existing deep GLAD algorithms heavily rely on Graph Neural Networks that primarily focus on analyzing individual graphs. These methods overlook the significance of graph-graph relationships in telling anomalies from normal graphs. In this paper, we propose a novel model for Graph-level Anomaly Detection using the Transformer technique, namely GADTrans. Specifically, GADTrans builds the transformer upon crucial subgraphs mined by a parametrized extractor, for modeling precise graph-graph relationships. The learned graph-graph relationships put effort into distinguishing normal and anomalous graphs. In addition, a specific loss is introduced to guide GADTrans in highlighting the deviation between anomalous and normal graphs while underlining the similarities among normal graphs. GADTrans achieves model interpretability by delivering human-interpretable results, which are learned graph-graph relationships and crucial subgraphs. Extensive experiments on six real-world datasets verify the effectiveness and superiority of GADTrans for GLAD tasks.