  Graph anomaly detection (GAD) has been widely applied in many areas, e.g.,
fraud detection in finance and robot accounts in social networks. Existing
methods are dedicated to identifying the outlier nodes that deviate from normal
ones. While they heavily rely on high-quality annotation, which is hard to
obtain in real-world scenarios, this could lead to severely degraded
performance based on noisy labels. Thus, we are motivated to cut the edges of
suspicious nodes to alleviate the impact of noise. However, it remains
difficult to precisely identify the nodes with noisy labels. Moreover, it is
hard to quantitatively evaluate the regret of cutting the edges, which may have
either positive or negative influences. To this end, we propose a novel
framework REGAD, i.e., REinforced Graph Anomaly Detector. Specifically, we aim
to maximize the performance improvement (AUC) of a base detector by cutting
noisy edges approximated through the nodes with high-confidence labels. (i) We
design a tailored action and search space to train a policy network to
carefully prune edges step by step, where only a few suspicious edges are
prioritized in each step. (ii) We design a policy-in-the-loop mechanism to
iteratively optimize the policy based on the feedback from base detector. The
overall performance is evaluated by the cumulative rewards. Extensive
experiments are conducted on three datasets under different anomaly ratios. The
results indicate the superior performance of our proposed REGAD.
