Anomaly Detection Using Graph Anomaly Rules

Anomaly detection in attribute networks is utilized to discover patterns of individuals or groups that deviate from the majority, and is widely used in areas such as e-commerce and social media. We define a new graph rule system for the detection of anomalies in graphs, referred to as Anomaly Graph Rules (AGRs). Using the mechanism of rule inference, AGRs describe anomaly nodes and structures in the form of graph patterns, and express the logic of anomaly generation through different types of literals. In addition to enhancing the ability of the rules to capture information about complete graph features, the literals support the embedding of machine learning models. Moreover, we propose a rule-matching algorithm that applies AGRs to the entire graph for anomaly detection. This algorithm innovatively incorporates conditional determination into pattern matching, employing conditional verification to aid the pruning operation of pattern matching and thus improving efficiency. In contrast to most previous studies, both anomalous nodes and anomalous structures can be detected simultaneously, and the results can be logically interpreted. We demonstrate the accuracy and efficiency of the algorithm using both real and synthetic datasets.