Generative Semi-supervised Graph Anomaly Detection

Thank you very much for the constructive comments and questions. We are grateful for the positive comments on the novelty and soundness of the experiments. Please see our detailed one-by-one responses below.

Weaknesses #1 The regularization is heavily based on the empirical analysis, which might not transfer to other anomalies.

The graph data is non-i.i.d. data with rich structure information, and the representation of a node should be grounded in a local context. Thus, as shown in Fig.1 and Fig.2 in the uploaded pdf, these two important priors about graph anomalies generally hold in all these real-world graph anomaly detection datasets. This is also one main reason why the popular graph reconstruction and graph contrastive learning methods for GAD are generally effective on various GAD datasets, since their intuitions are essentially based on similar priors as ours (though they did not explicitly summarize and propose the priors).

We agree that there can be some anomalies that may not well conform to these two priors. GGAD can work well for these cases too. This is because the outlier nodes generated by GGAD are essentially located at the fringe of the normal nodes in the representation space, as shown in Fig.3 (c). GGAD then leverages these outlier nodes to build a one-class classifier with a decision boundary tightly circled around the normal nodes. Such decision boundary can discriminate not only the anomalies well simulated by the outlier nodes but also the other anomalies that lie at the same side of the outlier nodes.

Weaknesses #2 and Questions #1 More verification on more datasets and empirical verification of the second prior

Please refer to our reply to Global Response to Share Concern #1 in the overall author Rebuttal section above for this concern.

Weaknesses #3 and Limitations #2 and Questions #5 The lack of diffusion model based generation

Thanks for pointing out the related study, but the work and other diffusion-based GAD methods as well focus on the fully supervised setting where both labeled normal and abnormal nodes are required during the training. This is different from the semi-supervised setting we proposed in our paper. We will discuss and include this work in our revision. Additionally, we have added more ablation studies in the outlier generation module, please refer to the response to Reviewer JEU8's Question #4.

Questions #2 How do we mediate the two assumptions that might be some contradiction and is there any difficulty in optimization?

Please refer to our reply to Global Response to Share Concern #2 in the overall author rebuttal section above for this concern.

Questions #3 Clarification on the joint optimization with anomaly detector

Different from existing augmentation-based generation, since we generate the outliers in the latent space rather than the raw node attribute space, the joint optimization allows the model to impose both anomaly priors more effectively. The total loss generally decreases and converges finally, see Fig. 3 in the uploaded pdf. To further investigate the benefits of joint optimization, we compare the two-step optimization method with our joint optimization approach. The experimental results are shown in Table A1. The results show that the joint optimization significantly outperforms the two-step approach. The main reason is that many more effective outlier samples can be generated during the optimization process of the two anomaly priors. By jointly optimizing with the BCE loss function, these outliers can be fully exploited for the training of the one-class classifier, enabling a mutually enhanced outlier node generation and one-class classification process.

Table A1. Results of two-step training and joint training  (AUPRC/AUROC).

Questions #4 The number of layers of the subgraphs, how should we decide on this parameter

We used one layer subgraph by default as the egonet of the target node to calculate the affinity score, because anomalies are primarily reflected in the relationships among the neighbors immediately connected to themselves [Ref1-2]. We agree that incorporating 2-hop neighbors can include more community information for GAD but might cause more computational overhead. We leave it as a promising future work direction.

Limitations #1 The generation is still operated in the embedding space, heavily based on interactional behavior.

Thank you very much for pointing out this. Generation in the latent space is a simple yet effective way to support efficient generative GAD training. It can also mitigate the notorious over-smoothing representation problem in the GNN aggregation.

Generating in the graph space is also a promising direction that offers a valuable approach for analyzing characteristics and enhancing interpretability. We will include and discuss this limitation in the final paper.

References:

• [Ref1] Addressing Heterophily in Graph Anomaly Detection: A Perspective of Graph Spectrum, WWW2023
• [Ref2] Truncated Affinity Maximization: One-class Homophily Modeling for Graph Anomaly Detection, NIPS2023

We greatly appreciate your further comments and it's great to know that our response has helped address some of your questions. Please find our point-by-point response to your follow-up questions as follows.

Questions #1 Why would adding Gaussian noise make the outlier distribution like a single bar?

We'd like to clarify that the Gaussian noise works like a hyperparameter in the feature interpolation in Eq. (5) to diversify the outlier nodes in the feature representation space. Changes of this noise distribution do not affect the superiority of the detection performance of GGAD over the competing methods (please see the results in Table A1 in our response to Reviewer JEU8 for empirical justification). Further, the outliers are generated based on the neighbors of some sampled normal nodes, so the number of the outlier nodes is far less than that of all normal samples, leading to a relatively sparse distribution of the outlier nodes in the affinity density map compared to the normal nodes in the figure. However, this does not affect their effectiveness in serving as negative samples for training the one-class classifier.

Questions #2 Concern on two constraints

We achieve the mediation of two constraints by jointly minimizing $L_{ala}$ and $L_{ec}$. The mediation leads to a result where the generated outlier nodes lie at the fringe of the normal nodes in the feature representation space, as illustrated in Fig. 1(b) and Fig. 3(c). Such outlier nodes meet the two criteria evenly you mentioned in the above comment. In terms of optimization, from Fig.3 in the uploaded pdf, we can see that the overall loss and the two individual losses gradually converge at around similar epochs where both constants are satisfied for the generated outliers; not unstable or fluctuated bounces are found after these epochs. Thus, we didn't experience any difficulty in the optimization of GGAD across all the datasets used.

Questions #3 How do we select the initial normal nodes?

As mentioned in lines 202-204, We randomly sample a set of S normal nodes and respectively generate an outlier node for each of them based on its ego network. In line 300, we indicate the size of the generated outlier node S is set to 5% of by default. As shown in Fig. 6 and Fig. 7 in App C.1 of the paper, the performance of GGAD generally remains stable w.r.t the number of the generated outlier nodes.

We hope the above replies help address your concerns. We're more than happy to engage in more discussion with you to address any further concerns you may have.

Thank you very much for helping enhance our paper again!

Question #1: Why would adding Gaussian noise make the outlier distribution like a single bar?

My question here is not whether tweaking the Gaussian noise would enhance previous baseline performance but more like if we can tweak the added Gaussian noise, would the motivation figure also suffer from this issue (the distribution of generated outliers in previous methods are further away than ground truth ones compared to the proposed methods)? However, since the presented results show significantly better performance of the proposed method, I guess it should be that no matter what level of Gaussian noise we add, they would still not be more like the ones generated by the proposed method.

Question #3: How do we select the initial normal nodes? This makes sense to me. Thanks!

Question #2 Concern with two constraints I am still confused here and would hear more guidance on this point. Because neighbors embeddings and original node embeddings are fixed and assuming we are working on the homophily social networks (which is a widely adopted property in real-world datasets), how could we enforce the generated outlier node embeddings to be further away from neighbors but at the same time be close to the original center node.

Although I still have questions on Question #2 Concern with two constraints. Overall, I appreciate the authors' response and think the observation of this paper would still be useful in future research in anomaly detection. I increase my score but hope authors could further address my questions here Question #2 Concern with two constraints.

Thank you very much for the constructive comments. We are grateful for the positive comments on our paper clarity, research motivation, and empirical justification. Please see our response to your comments one-by-one below.

Questions #1 The anomalies do not conform to the prior knowledge

Please also refer to the response to Review 7mdh Question #1 for detailed clarification.

Questions #2 Analysis of the results of the Photo and the results at the overall data level

Thank you very much for the comment and suggestion. GGAD yields the best AUROC on the Photo while yielding the second-best in AUPRC, underperforming OCGNN. Having the best AUROC while less effective AUPRC indicates that GGAD can detect some anomalies very accurately in Photo, but it is less effective than OCGNN to get a bit more anomalies rank in the top of normal nodes in terms of their anomaly score. We will add the above discussion into the final paper.

Questions #3 How the model overcome mislabeled positive samples

To consider this issue, we introduce a certain ratio of anomaly contamination into the training normal node set to simulate the normal nodes that are mislabeled in our experiments. The results of the models under different ratios of contamination in Fig. 5. and App. C.3 shows that with increasing anomaly contamination, the performance of all methods decreases. Despite the decreased performance, our method GGAD consistently maintains the best performance under different contamination rates, showing good robustness w.r.t. the contamination/noise. The main reason is that, unlike most unsupervised methods, GGAD not only learns normal patterns through normal models but also learns abnormalities by generating anomalies based on two priors, which reduces the dependency on the quality of normal data.

Questions #4 The connection between the outliers and the normal node is not well-illustrated

In the initialization step, we first sample some normal nodes and generate the outliers based on the representations of the neighbors of each target normal node, so the generated outlier nodes share similar neighborhood information as the target normal nodes. We will add more detailed explanations for Fig.2 in the final paper to clarify this point.

Thank you very much for the constructive suggestions. We are grateful for the positive comments on our readability and empirical justification. Please see our response to your comments one by one below.

Weakness in Summary Minimal differentiation with existing generation pseudo-anomaly samples (Benefits to unsupervised GAD).

Our work is the first method that leverages the priors related to graph anomalies into the outlier node generation, which enables the generation of outlier nodes considering both graph structure and feature representations of real abnormal nodes, which is not viable to any existing outlier/pseudo-anomaly generation methods (We will show how GGAD can benefit unsupervised GAD as an outlier generation module in our reply to Question #2 below).

Weaknesses #1 and Questions #1 The motivation of Semi-supervised GAD and labeling cost

Thank you very much for the comment. Most of the methods are based on unsupervised scenarios since it requires no labeling cost. However, they are too restricted in the real applications, because labels for a small set of normal nodes are easy to obtain. This is mainly due to the fact that the number of normal nodes typically overwhelmingly dominates the full graph. Thus, for example, one can randomly sample some nodes from the graph as the normal nodes, without any human manual labeling (the same labeling cost as unsupervised GAD). The quality of this 'random' normal labeling is high considering the scarcity of anomalies. Even involving human checking, such a small node set does not require much effort.

The randomly labeled normal nodes may include a very small number of abnormal samples in some cases. This is also why we perform extensive experiments on such cases in Fig. 6, where the detectors are evaluated on anomaly-contaminated normal data.

In line 31, we stated that the normal nodes are easier to obtain due to their overwhelming presence in the graph. We will rephrase that a small part of normal nodes is easier to obtain to avoid misunderstanding. In lines 268-269 we meant that human checking of large-scale normal nodes can be costly, contrasting to that for a small part of the normal nodes.

Weaknesses #2 Optimize these two losses seems to conflict and they should correspond to different outliers

Please refer to our reply to Global Response to Share Concern #2 in the overall author Rebuttal section.

Weaknesses #3 and Questions #2 Ignore the fact that unsupervised GAD methods do not obtain the outlier like GGAD and if GGAD can benefit existing unsupervised methods as a general module

Incorporating the outlier generation into existing unsupervised methods would lead to fairer empirical comparison. To allow the unsupervised methods to exploit the generated outliers, we first utilize GGAD to generate outlier nodes by training on randomly sampled nodes from a graph (which can be roughly treated as all normal nodes due to anomaly scarcity) and then remove possible abnormal nodes from the graph dataset by filtering out Top-K most similar nodes to the generated outlier nodes. By removing these suspicious abnormal nodes, the unsupervised method is expected to train on the cleaner graph (i.e., with less anomaly contamination).
This approach to improve unsupervised GAD methods is referred to as GGAD-enabled unsupervised GAD. We evaluate their effectiveness on three large-scale datasets. Please refer to global response for the results in Table A1, where #Anomalies/#Top-K Node in the table respectively represents the number of real abnormal nodes we successfully filter out and the number of nodes we choose to filter out (i.e., K).

For example, we use the outlier nodes generated by GGAD to filter out 500 nodes from the Amazon dataset, of which there are 387 real abnormal nodes. This helps largely reduce the anomaly contamination rate in the graph. The results show that this approach can significantly improve the performance of three different representative unsupervised GAD methods, including DOMINATE, OCGNN, and AEGIS.

Note that although the GGAD-enabled unsupervised methods achieve better performance, their performance still largely underperforms GGAD, which provides stronger evidence for the effectiveness of GGAD.

Qestions #3 The role of Gaussian noise in Eq.5

This simple perturbation can help maintain the affinity separability while enforcing the egocentric closeness constraint.

Questions #4 Compare with more advanced methods for generating outliers similar to GGAD

Apart from the outlier generation in the ablation study, we further employ two advanced generation approaches, VAE and GAN. In VAE, we generate the outlier representations by reconstructing the raw attributes of selected nodes where our two anomaly prior-based constraints are applied to the generation. For GAN. we generate the embedding from the noise and add an adversarial function to discriminate whether the generated node is fake or real, with our two prior constraints applied in the generation as well. As shown in Tab.1 in uploaded pdf. These two advanced generation approaches can work well on some datasets, which indicates two priors help them learn relevant outlier representations. But both of them are still much lower than GGAD, showcasing that the outlier generation approach in GGAD can leverage the two proposed priors to generate better outlier nodes.

Dear Reviewer JEU8,

We're very pleased that our clarification is helpful, and thank you for increasing the rating to an acceptance score.

We will add the intuition of "hard" outlier nodes and its difference to "trivial" outlier nodes in Sec. 3.4 to clarify why the loss in Eq. 5 is important in our method. The discussions have been very helpful for enhancing our paper. Many thanks again for your time and effort on our paper. We're happy to take any further questions you might have.

Thank you for raising the score. Please find our point-by-point replies as follows.

Questions #1 Ignore the fact that many anomaly detection methods are based on the structure of the graph, which may affect the scope of the method (it cannot be used on graphs without attributes)

As mentioned above, our GGAD generates outlier nodes that assimilate the real anomaly nodes in both graph structure and feature representations, where the structure information of the graph has been fully considered in our methodology design (i.e., through Eqs. (2) and (3) in the asymmetric local structural affinity prior). As emphasized in many GAD studies, anomalies in the graph are primarily reflected in the relationships of a node to its neighboring nodes immediately connected to themselves [Ref1-2] and many other methods reviewed in [Ref3]. That's why we consider generating the outlier nodes based on the egonet of target normal nodes.

Currently, to our best knowledge, most GAD methods are focused on attributed graph datasets (please see the survey and benchmark papers in [Ref3-5] for more details). As for the graph without attributes, the methods for attributed graphs can be applied by augmenting the graph with node attributes based on, e.g., one-hot encoding based on neighborhood information or feature construction using graph structure information (see [Ref3]). Thus, this should not be seen as a limitation of our method and numerous existing GAD methods.

Questions #2 The implementation of Gaussian noise

This simple perturbation can help maintain the affinity separability while enforcing the egocentric closeness constraint. It is a hyperparameter in GGAD and the default value was presented in the implementation. Gaussian noise-based perturbation is commonly used in existing feature interpolation techniques, including those in GAD methods [Ref6-7], and it is used as a way to diversify the generated outlier nodes only, not having catastrophic impacts on the performance of GGAD. This is justified by the newly added results in Table A1 below where we change the mean and variance of the Gaussian noise and replace the Gaussian noise with uniform noise. The results show that, regardless of the distribution of the noise, GGAD remains very effective, demonstrating similar superiority over the competing methods in Table 1 in the paper.

Table A1. The performance of GGAD under different scales of Gaussian noise and uniform noise (AUPRC/AUROC).

Overall, in our paper and the rebuttal here, we have examined the feasibility of a very wide range of methods that are related to our method GGAD from diverse aspects, e.g., different ways of exploiting graph structure information, generating outlier nodes, implementing GGAD with various alternative methods, and utilizing the generated outlier nodes in unsupervised/semi-supervise settings, etc. Thus, we would greatly appreciate if you could provide other unexplored directions for us to further evaluate the effectiveness of our method GGAD. We would kindly request your reconsideration of your current rating of our paper if otherwise. Thank you very much again!

References:

• [Ref1] Addressing Heterophily in Graph Anomaly Detection: A Perspective of Graph Spectrum, WWW2023
• [Ref2] Truncated Affinity Maximization: One-class Homophily Modeling for Graph Anomaly Detection, NIPS2023
• [Ref3] A comprehensive survey on graph anomaly detection with deep learning, TKDE 2021
• [Ref4] GADBench: Revisiting and Benchmarking Supervised Graph Anomaly Detection, NIPS2023
• [Ref5] BOND: Benchmarking Unsupervised Outlier Node Detection on Static Attributed Graphs NIPS2022
• [Ref6] Perturbation learning based anomaly detection, NIPS2022
• [Ref7] DAGAD: Data Augmentation for Graph Anomaly Detection， ICDM2022
• [Ref8] Consistency Training with Learnable Data Augmentation for Graph Anomaly Detection with Limited Supervision, ICLR2024

Thank you very much for the constructive comments. We are grateful for the positive comments on our studied problem, technical contribution, and empirical justification. Please see our detailed response below

Weaknesses #1 The generation may cause non-trivial computational

We agree that GGAD may cause computational overhead due to the outlier node generation. However, the overhead is small. This is justified by the time complexity analysis and running time statistical results in Appendix D, where GGAD runs much faster than many competing methods and it is comparable efficiency to the remaining methods.

Weaknesses #2 Low AUC on Reddit and DGraph

Thank you very much for the comment. Reddit and DGraph are two challenging datasets in GAD. DGraph is a very large-scale graph that includes more than millions of nodes where the anomalies only account for 1.3 %. The fully supervised methods only yield an average of 0.02/0.67 in AUPRC and AUROC on this dataset [Ref1-2]. Similarly, Photo is a user-subreddit graph network on which fully supervised methods only yield an average of 0.06/0.65 in AUPRC and AUROC [Ref1-2]. Although our GGAD achieved low AUROC/AUPRC on these two datasets, not as high as the other datasets, it still shows good improvement compared to other state-of-the-art unsupervised and semi-supervised methods.

Weaknesses #3 The reason behind the flat performance of other methods

The main reason is that these competing methods are trained based on their unsupervised proxy GAD tasks, so they have limited capability to increase their discriminability with increasing the number of normal nodes. On the contrary, our GGAD utilizes partially labeled normal nodes and two important anomaly priors to generate outlier nodes as negative samples to train a discriminative one-classifier. As the number of normal nodes increases, the generated outliers become more diverse, closely aligning with the real abnormal nodes in the dataset, thereby resulting in better discriminability and thus better AUPRC.

References:

• [Ref1] GADBench: Revisiting and Benchmarking Supervised Graph Anomaly Detection, NIPS2023
• [Ref2] BOND: Benchmarking Unsupervised Outlier Node Detection on Static Attributed Graphs, NIPS2022

The reply has addressed my questions.

Thank you very much for the constructive comments. We are grateful for the positive comments on our studied problem, technical contribution, and empirical justification. Please see our detailed response below

Weaknesses #1 There is no theoretical analysis to guarantee the effectiveness of the proposed method

We encapsulate two important anomaly priors to generate the outliers that are similar in the local structure and feature representation as real abnormal nodes. This provides a principled framework for generative GAD. To further verify the intuition of the priors and our proposed method, we have added empirical evidence that justifies the two priors in more real-world GAD datasets in the uploaded pdf. Please refer to our reply to Global Response to Share Concern #1 in the overall author rebuttal section above for details. Overall, our method, as the first piece of work explicitly designed for the semi-supervised GAD problem, presents solid findings and interesting insights into the problem, laying a good foundation for future work on theoretical analysis and more advanced methods in this research line.

Weaknesses #2 and Q3 More analysis on the generated outliers like shot the generated outliers can capture the characteristic of anomalous in addition to comparing their representations

Thank you very much for the suggestion. Please see Fig.3 in the paper and Fig. 1 in the uploaded pdf for the visualization based on the local structure information of the generated outlier nodes. We further employ the Maximum Mean Discrepancy (MMD) distance to measure the distance between the generated outliers and the real abnormal nodes (and the normal data as well) to illustrate more in-depth characteristics of the generated outlier nodes. As shown in Table A1 below, it is clear that the distribution of the generated outliers have much smaller MMD distance to the real abnormal nodes than the normal nodes, indicating the good alignment of the distribution of the generated outliers with the real abnormal nodes.

Table A1. Analysis of the generated outlier nodes using MMD distance

We will add this MMD distance-based outliers analysis into the final paper.

Weaknesses #3 and Questions #2 Clarification on the setting of contamination

Thanks for pointing out the issue. When studying the semi-supervised GAD, it's important to consider that some normal nodes may be mislabeled or affected by some noise interference. To introduce a certain ratio of anomaly contamination, we randomly sample $V_l$ nodes from the real abnormal nodes set in the dataset and add them as the contaminated nodes into the training data. The rest of the abnormal nodes are used as part of the test dataset. We will add these details of the contamination setting in the final paper.

Weaknesses #4 and Questions #2 Overall experimental settings. Provide more information about the hardware and why the experiments are conducted on the CPU.

The existing baseline methods require different GPU memory and environments depending on their methodology design. To conduct a unified comparison of operational efficiency, we chose an AMD EPYC 7443P 24-core CPU with 125G memory as the running platform. We also provided a computational efficiency analysis in Appendix D.