NORMAL-REFERENCED DISCRIMINATION FOR OPEN-SET GRAPH ANOMALY DETECTION

Open-set graph anomaly detection uses labeled normal nodes and a few labeled anomalies to detect both the labeled anomaly types and unseen types absent from the training labels. These labels help the detector learn normal and anomalous patterns, improving its detection accuracy. However, a detector fitted to the labeled types may mistake unseen anomalies for normal nodes. To address this problem, we propose Normal-Referenced Discrimination (NoRD), which trains a single anomaly score using both labeled and unlabeled nodes. The unlabeled nodes contain normal nodes and anomalies, including unseen types. Specifically, NoRD learns to distinguish these unlabeled nodes from labeled normal nodes alongside supervised anomaly detection, allowing unlabeled anomalies to contribute to training. Since both groups contain normal nodes, directly separating them would also encourage high anomaly scores for unlabeled normal nodes. Accordingly, NoRD first expresses each anomaly score relative to the labeled normal scores, providing a common reference for the comparison. It then applies a mixture link that accounts for normal nodes in both groups and reduces the pressure to increase already-low anomaly scores on unlabeled nodes. Experiments on seven public graphs demonstrate consistent improvements over competing methods in both overall and unseen-anomaly detection. Code is available at https://anonymous.4open.science/r/NoRD/.