Open-Set Graph Anomaly Detection via Normal Structure Regularisation

We thank the reviewer for the constructive and affirming feedback and address the concerns of the reviewer below.

W1 and Q1. Discussion on the Difference Between Open-Set GAD and Out-of-Distribution (OOD) Detection.

We respectfully disagree with the reviewer’s comment that open-set GAD is very similar to OOD detection; the two tasks are fundamentally different. In OOD detection, the primary objective is to maintain the classification accuracy on in-distribution (ID) while at the same time distinguishing between ID and OOD data, where a pre-trained classifier on ID data and testing data with both ID data and OOD data are involved. In contrast, Open-set supervised GAD aims to identify anomalous nodes among unlabelled nodes, including both seen and unseen anomalies, not involving any pre-trained ID data classifier and thus no objective to maintain the ID classification accuracy. Further, the distributions during training and testing can remain consistent in open-set GAD, while it is the opposite in OOD detection. The unseen anomalies in Open-set GAD do not result from distribution shifts but from the inherent limitation of prior knowledge about the anomaly class, which captures only a subset of potential anomaly patterns. These unseen anomaly patterns may already exist in the graph during training, participate in message passing, and yet remain unaccounted for by the supervised GAD model’s loss function.

Additionally, OOD detection focuses on identifying instances from novel distributions absent during training, typically representing novel classes outside the classes of interest. In open-set supervised GAD, all nodes—labelled or unlabelled—are present during training, though only labelled normal and anomalous nodes are used for supervision.

Nevertheless, we agree that further clarification could benefit the reader. We will include this discussion in the revised version and acknowledge classic OOD works to better position Open-set GAD.

W2. Additional GAD and OOD Baselines.

We have clarified the distinction between open-set GAD and OOD detection and explained why their objectives cannot be used interchangeably in "To Rev. uvQ4" W1 & Q1. Open-set GAD does not deal with out-of-distribution classes, which are not defined in our problem setting. Additionally, we want to emphasise that T-Finance is a human-annotated dataset containing real-world anomalies. Regarding GAD baselines, we have included several recent methods from [4], as noted by the reviewer, and our baseline selection already covers 16 popular approaches. To acknowledge the reviewer’s suggestions, we conducted additional experiments on the two mentioned baselines, XGBGraph and CONSISGAD. The GAD performance results, in terms of AUC-ROC and AUC-PR on all test anomalies, are reported in Table 3. Please refer to the revised paper for the complete results and discussion. Consistent with our observations in the paper, NSReg achieved significantly better performance. This is because the baseline methods primarily focus on fitting seen anomaly patterns but do not effectively generalise to unseen anomaly patterns, since they are also closed-set supervised methods. One exception is that XGBGraph achieved surprisingly high performance on the Yelp dataset. We believe this is incidental, as XGBGraph is a generic hybrid method combining parameter-free node feature propagation with XGBoost, without GAD-specific training. This enables it to perform particularly well on the Yelp dataset. A similar observation was noted in the benchmark paper mentioned by the reviewer [4], where XGBGraph significantly outperformed all state-of-the-art methods on this dataset by a large margin. However, this strong performance is not universal, and NSReg consistently outperforms the baseline methods across other datasets.

Table 3: AUC-ROC and AUC-PR (mean ± std) for detecting all anomalies, comparing CONSISGAD with XGBGraph.

Thank you to Reviewer uvQ4.

The choice of $\alpha$ and the performance of NSReg when it is set to $[0, 0.5]$.

Please note that the requirements for setting $\alpha$ are discussed in our theoretical analysis starting from line 234. There, we stated that the labelling function should ensure that, for a given labelling function, the minimum normality score assigned to relations exclusive to normal nodes should be smaller but closer to or equal to 1 (typically set for relations between two connected normal nodes) while being significantly greater than any score assigned to relations involving an anomaly node. If $\alpha$ is set within the range $[0, 0.5]$, this condition will no longer hold. It would instead suggest that unconnected normal nodes exhibit normalities more similar to those of unlabeled nodes rather than connected normal nodes. Note that $\alpha$ is a relative specification.

To further validate this point, we conducted additional experiments by running NSReg with $\alpha$ set to 0, 0.2, and 0.4, and reported the results in Table A and Table B. These tables include the performance of NSReg when $\alpha$ is set to 0, 0.2, 0.4, 0.6, 0.8, and 1.0. It can be seen that, on average, the performance for both metrics is better when $\alpha$ is set to larger values, especially compared to $\alpha = 0$. Although a general trend of performance decline is observed across all datasets as $\alpha$ decreases, fluctuations can occur due to the randomness involved in the training process and the heterogeneity between different graphs.

Table A: AUC-ROC of NSReg using different $\alpha$ values on all test anomalies.

Table A: AUC-PR of NSReg using different $\alpha$ values on all test anomalies.

We hope this explanation clarifies the question.

We thank the reviewer for the constructive and affirming feedback and address the concerns of the reviewer below.

W1. The concept of structural normality refers to the graph structural relationships defined by the labelled normal nodes. This concept is explained in lines 76–97 and 184–190, and is further elaborated in Section 3.3. We kindly ask the reviewer to provide more specific feedback regarding this comment if we do not address the concern well. The paper’s clarity has been appreciated by other reviewers, such as Reviewers KzVj and uvQ4. We would greatly appreciate more detailed suggestions if otherwise.

W2. We would like to point out that Figure 2 contains only one dashed box filled in teal, while all other dashed shapes are spherocubes. We have improved the clarity of this distinction in the revised version. Regarding the use of the term “discriminative,” we believe it is necessary in this context. In GAD, a detector can be either supervised or unsupervised. Unsupervised graph anomaly detectors are not inherently discriminative—for example, autoencoder-based models are not discriminative by nature but can still achieve end-to-end anomaly scoring.

W3. Our apologies for unable to include hardward details due to space limit, we have included it in the revised version. Our results are gathered using a single NVIDIA A100 GPU and 28 CPU cores from an AMD EPYC 7663 Processor. We would like to point out that our datasets are publicly available, we have provided reference to all of them (in between line 327 and 338) and dataset details in Appendix B.2. Our code is included in supplementary materials.

Q1. We would like to point out that these terms are defined between line 267-268. Although we are more than happy to include an illustrative diagram, due to the page limit, we have included it in the appendix in the revised version.

Q2. This denotes the element-wise product (i.e., Hadamard product), which has been clarified in the revised version.

Q3. We kindly ask the reviewer to clarify the second question, as we are unable to locate the relationship description in line 2. The “two types of relations" refers to “the relations between normal nodes and the relations between normal and anomaly nodes," as they are discussed in close proximity within the same subsection. Please note that this subsection develops the theoretical support for NSReg, where we demonstrate that only two distinct and broad types of relations—those exclusive to normal nodes and those between normal and anomaly nodes—are necessary for our derivation. The specific connectivity between normal nodes does not affect our final conclusions. In principle, multiple types of relations among normal nodes could be defined, provided the labelling function satisfies the condition in line 231, i.e., the lowest normality score for relations exclusively among normal nodes remains significantly higher than that for relations between normal and anomaly nodes. The three types of relations mentioned in line 267 represent the default configuration in NSReg, an instance of the theoretical model. This configuration aligns with our theoretical analysis and has shown strong empirical performance.

Q4. This means that Z serves as the shared representation space for the mapping g and a supervised anomaly scoring function. In this context, the two components simply receive their input from Z, with no additional operations required.

Q5. We have labelled the equation in the revised version. Please refer to "To Reviewer VYmz Q2" for a detailed discussion of the choice.

Q6. There are only two types of arrows—orange and teal. We noticed that the orange arrows may appear slightly different due to variations in sizes and colour profiles across different monitors. However, in our plotting software, they are set to the same colour code. We have double-checked and ensured visual consistency in the revised version.

Q7. We would like to clarify that $g$, as a discriminative mapping, is a fundamental component of our theoretical model and an intentional design choice for enforcing normal-node-oriented relations. We demonstrate that a discriminative mapping satisfying our conditions can effectively displace misplaced anomalies from the normal subspace when trained to differentiate normal-node relations jointly with the supervised GAD loss. NSReg serves as an instantiation of this theoretical model.

Q8. As mentioned in line 278, the equation represents the first sub-mapping of $F − F_E$ for generating relation representations. Here, $F$ and $F_E$ are instantiated from $G$ and $G_E$ , respectively, in the form of neural networks.

W3. The meaning of symbol $\circ$ and the use of notation $V$.

The symbol represents the element-wise (Hadamard) product. We have added an explanation in the revised version. The use of $V$ is correct. As mentioned in line 307, $V$ refers to a batch of training nodes. In our paper, the set of all node is denoted as $\mathcal{V}$.

W4. Clarifications on the reason why gradient updates of NSReg's components are presented separately in the pseudocode.

The pseudocode is reflective for the training process. We would like to clarify that this is consistent with the joint learning objective, and the pseudocode is written specifically to align with the framework’s architecture and code implementation. $F$ and $E$ are the two transformations within the relation modelling module, and $\eta$ refers to the anomaly scoring network. These components operate independently, as they both take input from the graph representation space $\psi$. As a result, their parameters can be updated independently, and their order in the pseudocode is interchangeable. On the other hand, $\psi$ is jointly optimised based on the losses from both objectives. It receives gradients propagated from subsequent modules and is therefore updated last.

W5. NSReg's improvement appears less significant on the Yelp dataset compared to the other datasets.

• NSReg is effective on all datasets. We are uncertain about the reviewer’s interpretation of "displays less sensitivity to the hyper-parameter." Our best understanding is that the reviewer is asking why NSReg demonstrates greater improvement, in terms of raw values, across the three datasets. The effectiveness of NSReg depends on several factors inherent to the datasets, such as the type of graph, connection characteristics, quality of node attributes, the discrepancy between seen and unseen anomaly classes, and the capacity of the backbone GAD model. Below are some possible explanations: First, the performance of our default backbone, as well as other baseline methods, on Yelp is generally lower than on the other datasets. NSReg still achieves significant improvement, which is more pronounced in terms of the rate of improvement. Additionally, as shown in Table 2, when other GAD models are used as backbones, their NSReg-enabled variants achieve comparable or even greater improvements on Yelp compared to the other datasets. This further supports the notion that factors beyond our design influence the degree of improvement.
• GraphSMOTE’s performance on Yelp for unseen anomalies. Regarding why GraphSMOTE performs better on the unseen classes in the Yelp dataset, we would like to emphasise that the ultimate performance metric considers all test anomalies. While GraphSMOTE may achieve better results on unseen anomalies, this improvement comes at the cost of fitting seen anomalies and the overall performance. It is important to note that GraphSMOTE is an augmentation-based method. Although augmented samples can mimic certain patterns, they may also introduce noise. From its less optimal overall performance, we infer that the augmented examples might partially align with the patterns of unseen anomalies but negatively impact the model’s ability to fit seen anomalies, ultimately doing more harm than good.

W6. Code release.

We would like to clarify that we have submitted code in the attachment of supplementary material and will make the code publicly available on github after acceptance.

We thank the reviewer for the constructive and affirming feedback and address the concerns of the reviewer below.

W1 Discussion on the difference between the core idea of NSReg and closed-set GAD baselines and additional baselines

• The core idea of NSReg. We respectfully disagree with the reviewer and believe that describing our key contributions as the "core idea of using neighbourhood information" is inaccurate. Regarding the additional reference provided by the reviewer and the other supervised GAD baselines included in our experiments, while they somehow incorporate neighbourhood information, they do not enforce any type of explicit structure-wise normality-based regularization during GAD training. It is fair to state that almost all graph learning methods leverage neighbourhood information, either implicitly or explicitly, as this is a fundamental characteristic that distinguishes graph learning from learning on non-graph data. However, attributing our contribution and novelty solely to the use of local information disregards the unique aspect of our approach: the explicit regularisation via enforcing structural normality, specifically tailored for supervised GAD in the open-set setting. Please note that the definition of structural normality based on neighbourhood connectivity is a design choice that is both efficient and highly effective. As we mentioned in Section 5, it is entirely possible to extend the scope of relations. However, our primary goal is to emphasise the importance and usefulness of graph-structure-based regularisation for supervised GAD in the open-set setting.

• Additional baselines. We want to point out that our baseline selection already includes a broad range of recent approaches from related fields, including but not limited to both supervised and unsupervised GAD methods (16 in total). To acknowledge the importance of the suggested baselines, we have incorporated them into the related work and conducted additional experiments on CONSISGAD [2] and PMP [3] (which significantly outperforms [1] in its comparison). At a high level, these methods are closed-set supervised GAD approaches, similar to those already discussed in the paper. As shown in the Table 1, NSReg consistently achieves superior overall performance in detecting both all test anomalies and unseen anomalies. Please refer to the revised paper for complete results and discussion. It is also worth noting that while CONSISGAD leverages both data augmentation and label information for supervision, NSReg relies solely on label information.

Table 1. UC-ROC and AUC-PR (mean ± std) for detecting all anomalies, comparing NSReg with CONSISGAD and PMP.

W2. Discussion on the potential implications of unconnected normal nodes in $\mathcal{R}(n,u,u)$.

The third case $\mathcal{R}(n,u,u)$ works collaboratively with the first two cases to distinguish unlabelled normal nodes from unseen anomalies. We agree with the reviewer that most relations of this type are between labelled and unlabelled normal nodes. Consequently, the unlabelled normal nodes in the third case may slightly interfere the normal relation score of the labelled normal nodes, which is an unavoidable but worthwhile trade-off. However, their scores remain higher than those of unseen anomalies due to their similarity and structural connections with labelled normal nodes in the first two cases. This distinction does not apply to unseen anomalies, which consequently receive low normal relation scores. Additionally, the supervised GAD loss is sufficiently powerful to produce a dense normal region, further mitigating any unwanted effects. We report the percentages of anomaly node in $\mathcal{R}(n,u,u)$ in the table below. It is worth noting that other factors, such as graph properties and the backbone GAD model, also influence the effectiveness of NSReg.

Thank you for your detailed response.

Overall, I am satisfied with your responses to Weaknesses 1–5. However, I share Reviewer JRAN's concern regarding the source code. Specifically, the README file and the training procedure for the model appear to be missing, with only the inference procedure provided. This level of detail is insufficient for full reproducibility.

Based on your clarifications and improvements, I am inclined to increase my rating to support this work, albeit with some reservations.

We thank the reviewer for the constructive and affirming feedback and address the concerns of the reviewer below.

W1. Discussion on unsupervised GAD methods for open-set GAD.

We would like to kindly ask the reviewer to clarify the meaning of “considerable inductive performance." Additionally, we would like to point out that, as mentioned in lines 41, 43, and 138, while it is possible to apply unsupervised GAD methods, they are far less effective than supervised methods due to the lack of prior knowledge about the anomalies of interest. This is further validated by our experimental results, which include seven widely used recent unsupervised baselines. As shown in Table 1, these methods exhibit significantly lower performance compared to supervised approaches. Furthermore, in line 94, we clearly defined the scope of our study, emphasising that it focuses on supervised methods in open-set settings. We also highlighted that unsupervised methods face different challenges when no label information is available. Please refer to our General Rebuttal above.

W2, Clearer discussion on the difference between enforcing structural normality and existing one-class classification or anomaly detection methods.

We would like to point out that this has been discussed in Section 4.2, where we highlighted the importance and advantages of enforcing structural normality compared to other one-class classification and anomaly detection objectives, such as Deep-SAD (hypersphere-based) and contrastive learning. Additionally, our unsupervised baselines encompass a wide range of GAD objectives, including one-class classification (OCGNN), contrastive learning (COLA), and reconstruction loss (ADA-GAD). These methods are significantly less effective than NSReg. These approaches primarily focus on node attributes or the volume of the normal region in the representation space, without fully utilising the valuable anomaly-discriminating information embedded in the graph structure. The key innovation of NSReg lies in capturing this information by modelling normal-node-oriented relations. Furthermore, as demonstrated through the theoretical analysis in Section 3.3, we provide a rigorous foundation for the effectiveness of structural regularisation, whereas the effectiveness of other objectives remains largely heuristic.

W3. The presentation of the paper needs to be improved.

We would like to kindly ask the reviewer to provide more specific feedback regarding this comment. We are more than happy to clarify and improve any aspects of the presentation if the reviewer could kindly point them out.

Q1. Inclusion of AEGIS as a baseline.

We would like to clarify that we have explicitly stated in the paper that our primary focus is on the supervised setting, as noted in response to "To Rev. VYmz" W1. The inclusion of unsupervised baselines is intended for comprehensiveness. According to Table 1 in the main paper, supervised GAD baseline methods consistently demonstrate significantly better performance compared to their unsupervised counterparts. For comprehensiveness, we have already included seven unsupervised baselines, including recent methods such as CoLA, CONDA, TAM, and ADA-GAD, which are more recent than AEGIS. Additionally, we included GGAN, a GAN-based unsupervised method with a similar learning scheme to AEGIS, as part of our baseline comparisons. However, to acknowledge the reviewer’s input, we have now included the results for AEGIS. The overall GAD performance of AEGIS, in terms of AUC-ROC and AUC-PR, is reported in Table 2. Please refer to the revised paper for results on unseen anomalies. Similar to the other unsupervised baselines, AEGIS achieves significantly less optimal performance than the supervised methods. This is because its augmentation process is heuristic, lacking anomaly prior knowledge, which makes it challenging to generate data samples that accurately mimic actual anomalies.

Table 2: AUC-ROC and AUC-PR (mean ± std) for detecting all anomalies, comparing NSReg with AEGIS. “-” denotes unavailable result due to out-of-memory.

Q2. Clearer discussion on the choice of $\alpha$.

The parameter $\alpha$ specifies the relative normality of relations between unconnected normal nodes with respect to other types of relations. It is designed to define the normality hierarchy we aim to enforce, such that the relation scores satisfy the following order: connected normal nodes > unconnected normal nodes $\gg$ unconnected normal and unlabelled nodes. This hierarchy is based on the assumption of homophilic behaviour among normal nodes, distinguishing between the most related normal nodes and other, less related normal nodes. We find that the performance of our model is not sensitive to the choice of $\alpha$, as long as this hierarchy is maintained. As noted in the paper (line 375), we reported this observation, and due to space constraints, the parameter sensitivity analysis is provided in Appendix C.5.

Q3. Understandability of Figure 3.

Figure 3 shows the data efficiency plot of NSReg compared to supervised GAD baselines in terms of AUC-PR on all test anomalies. Due to space constraints, the complete results—including both AUC-ROC and AUC-PR for all test anomalies and unseen anomalies—are presented in Figures 8 and 9 in Section C.6.

These plots adhere to standard practices commonly used in many supervised AD and GAD studies to comprehensively evaluate model performance under varying levels of data availability. Our results demonstrate that NSReg consistently outperforms the supervised baselines across different numbers of labelled seen anomalies.

If this response does not help address the concern, we would like to kindly ask the reviewer to provide more specific feedback for us to better clarify the confusion/misunderstanding.

Dear Reviewer VYmz,

We sincerely appreciate the time and effort you’ve devoted to reviewing our paper and providing valuable feedback. As the discussion period is coming to a close in a few hours, we kindly request your acknowledgment of our responses.

Many of your questions are similar to those raised by other reviewers, who have expressed satisfaction with our responses and supported the paper by increasing their ratings. We hope our clarifications address your concerns as well.

Your acknowledgment or any feedback at this stage would be greatly appreciated. Thank you once again for your time and thoughtful insights.

Best regards,

Authors of #7056