Zero-shot Generalist Graph Anomaly Detection with Unified Neighborhood Prompts

Thank you very much for the constructive comments and questions. We are grateful for the positive comments on our design and empirical justification. Please see our detailed one-by-one responses below.

Weakness #1 & Question #1: Contribution of coordinate-wise normalization and neighborhood prompting and the unique challenges of prompt learning for GAD.

Please refer to our reply in Global Response to Shared Concerns #1 in the General Response section above for this concern.

We would also like to clarify the differences between our method and the all-in-one method in [Ref1]. First, [Ref1] aims to utilize prompt learning to reformulate various downstream tasks in line with the pre-training task so that the pre-trained model can be applied to downstream applications with efficient fine-tuning or even without any fine-tuning. By contrast, we focus on using neighborhood prompting to capture generalized normal and abnormal patterns so that the anomaly detection model trained on the source graph can be directly applied to target graphs. Second, [Ref1] learns a prompt graph consisting of prompt tokens and token structure. The prompt graph is then inserted into the input graph. Differently, we only devise learnable prompt tokens appending to the attributes of the neighboring nodes of the target nodes for learning robust and discriminative patterns. Therefore, the concept of neighborhood prompting is not encompassed in [Ref1].

There are two unique challenges in prompt learning for graph anomaly detection. First, the unsupervised nature of graph anomaly detection in a target graph implies the lack of labeled data from the target graph datasets, rendering the prompt learning with multi-downstream tasks infeasible. By contrast, UNPrompt is designed to eliminate the tuning on the target graph datasets. Second, the anomalous patterns differ significantly from one graph to another, and thus, to achieve generalized anomaly detection across different graphs, it is crucial that the prompt learning requires a one-class pattern learning approach. Conventional graph prompt learning does not meet this criterion. Our latent node attribute prediction-based prompt learning instead is specifically designed for this purpose, in which strong latent node attribute predictability is expected for normal nodes.

Weakness #2 & Question #4: Inadequate consideration for GAD.

In this paper, we utilize the predictability of latent node attributes as the anomaly criteria instead of using graph uniformity or high node connectivity for anomaly detection. Specifically, the working mechanism of the predictability of latent node attributes is that normal nodes tend to have more connections with normal nodes of similar attributes due to prevalent graph homophily relations. This results in a more homogeneous neighborhood for the normal nodes. By contrast, the presence of anomalous connections and/or attributes makes abnormal nodes deviate significantly from their neighbors. For a target node, its latent attributes (i.e., node embedding) are more predictable based on the latent attributes of its neighbors if the node is a normal node, compared to abnormal nodes. Therefore, both anomalous nodes and edges are considered in our method and the whole process of the anomaly score calculation is formulated in Eq. (3)-Eq. (5).

Weakness #3: Lengthy sentences.

We will modify lengthy sentences to make the paper more readable and understandable in the revised version.

Weakness #4: Source Code.

We will release the source code upon paper acceptance. Currently, to facilitate your review, we have uploaded the code to an anonymous GitHub repository at https://anonymous.4open.science/r/UNPrompt-DB13/README.md.

Thank you very much for the constructive comments and questions. We are grateful for the positive comments on our design and empirical justification. Please see our detailed one-by-one responses below.

Weakness #1 & #3: Contribution of coordinate-wise normalization and neighborhood prompting.

Please refer to our reply in Global Response to Shared Concerns #1 in the General Response section above for this concern.

Weakness #2: More explanation on comparison to TAM.

While both TAM and UNPrompt utilize the features/embeddings of local neighboring nodes to measure the normality of nodes, their working mechanisms are substantially different. The anomaly score function for TAM is $s_i = -\frac{1}{|\mathcal{N}_i|}\sum{v_j \in \mathcal{N}_i} (sim(z_i, z_j))$ where $\mathcal{N}_i$ denotes the neighborhoods of node $i$ and $z_i$ is the GNN-based node embedding. For UNPrompt, the score function is $s_i = sim(z_i, \tilde{z}_i)$ where $\tilde{z}_i$ is the aggregated neighborhood embeddings for node $i$. As indicated by the TAM score function, it explores the local affinity of one node by averaging the similarities between the node and all the neighbors in the latent space. As a result, this function relies on a clean graph structure, i.e., edges only connecting normal and similar nodes, to detect anomalous nodes. The presence of non-homophily edges, i.e., edges that connect normal and abnormal nodes, would degrade the effectiveness of TAM. Differently, for a node, we use the latent node attribution predictability to measure the normality of the node. The neighbors of the nodes are first aggregated in UNPrompt and then fed into a transformation layer to perform the prediction, which reduces the reliance on the clean graph structure.

In Figure 3(b), we report the results of replacing latent attribute prediction with local affinity and the results, in which we show that the latent attribute predictability consistently and significantly outperforms the local affinity-based measure across all graphs. For this ablation study, we carefully tune the hyperparameters including the number of prompts and learning rate for the local affinity-based UNPrompt variant. The performance gap between latent attribute prediction and local affinity is attributed to the differences discussed above, rather than the training tricks.

Weakness #4: More analysis on hyperparameters.

In the unsupervised graph anomaly detection setting, there is no label information available for the neighborhood prompt learning since we need to train and evaluate UNPrompt and other methods on the same unlabeled graph. To address this issue, we treat the nodes with normal scores greater than a threshold as normal nodes (pseudo labeling of normal nodes) and aim to maximize the latent attribute predictability of these nodes. In our experiments, the threshold is set to be the 40th percentile of all the normal scores due to a prior knowledge that the real anomalous rate is typically very small. We set the threshold to 40% that is far greater than the anomalous rate in real-world datasets, mainly because we want to reduce the chance of mistakenly treating anomalous nodes as normal nodes, i.e., to obtain a set of high-confident normal nodes. Note that the proposed prompt learning only focuses on utilizing normal nodes for the unsupervised graph anomaly detection setting. Setting the threshold to a smaller percentile would increase the change that more abnormal nodes would be treated as normal nodes in our training, misleading the prompt learning in UNPrompt.

Besides, we also evaluate the generalist anomaly detection with different common dimensionalities, with the dimensionality varying in [2, 4, 6, 8, 10, 12]. The results are reported in the following table.

Table A1. AUPRC results of UNPrompt with different common dimensionalities with Facebook as the training graph.

From the table, we can see that small dimensionality leads to poor generalist anomaly detection performance. This is attributed to the fact that much attribute information would be discarded with a small dimensionality. By increasing the common dimensionality, more attribute information is retained, leading to much better performance. More details are reported in Appendix G.1 of the revised paper.

Thanks for your detailed reading and suggestions. Please see our detailed response and clarification below:

Question #1: Sensitivity analysis of the threshold by ranging it from 5% to 50% in unsupervised GAD.

To evaluate the sensitivity of the unsupervised GAD performance of our method w.r.t the threshold, we vary the threshold in the range of [5%, 50%] at a step size of 5%. Without loss of generality, three datasets are employed, including Facebook, Reddit, and Amazon. The results of these datasets are reported in the following table.

Table A5. AUROC results of UNPrompt with different thresholds in unsupervised GAD.

From the table, we can see that the unsupervised performance of UNPrompt can perform well and stably with a sufficiently large threshold (e.g., no less than 30%), but it may drop significantly with a small threshold, e.g., thresholds like 5%-15% that are close to the ground-truth anomaly rate. This is because more abnormal nodes would have a substantially higher chance to be mistakenly treated as normal nodes with such a small threshold, which would in turn mislead the optimization and subsequently degrade the GAD performance. By contrast, increasing the threshold would lift the acceptance bar of normal nodes, allowing the optimization to focus on high-confident normal nodes and effectively mitigate the adverse effects caused by the wrongly labeled normal nodes.

Question #2: Experiments on financial datasets in generalist GAD.

To further evaluate the proposed method, we conduct the experiments on the T-Finance dataset. Specifically, the generalist anomaly detection model is trained on Facebook following the experimental setup on page 8 of the main paper. Then, the learned model is directly applied to the T-Finance dataset. The AUROC results are reported in the following table.

Table A6. AUROC results on the T-Finance dataset with the models trained on Facebook only.

From the table, we can see that all the methods do not achieve promising results on T-Finance. This is attributed to the fact that T-Finance differs significantly from the other datasets used in our paper. Specifically, T-Finance is a highly dense graph with an average degree of 1,079 while the average degree of the training Facebook is 51. Therefore, the model learned on Facebook can not be effectively generalized to T-Finance due to the significant difference. Moreover, the massive neighbors would easily result in low discrimination between nodes if the message-passing mechanism of GNNs is based on the whole neighborhood. This helps explain the poor performance of AnomalyDAE, GCN, and UNPrompt. Meanwhile, GAT, BWGNN, and GHRN achieve better performance as they employ the attention mechanism and graph spectral analysis for GAD. Note that although GADAM employs adaptive message passing for GAD, it also achieves poor performance. This is mainly due to the incompatibility of abnormal patterns between Facebook and T-Finance. We leave the exploration of more effective generalist anomaly detectors on graphs with such contrast structure for future research.

Please note that we are the very first work on zero-shot GAD, and UNPrompt shows promising performance across a number of popular GAD datasets from social networks, co-review networks, co-purchase networks, and payment flow networks. Such impressive zero-shot GAD performance, together with its flexibility in gaining new state-of-the-art unsupervised GAD performance, makes a significant contribution to the GAD community. The contribution should be not weakened in any way due to its less effective performance on this very unusual GAD dataset.

As for the two larger datasets with millions of nodes, DGraph-Fin and T-Social, the experiments can not be conducted due to the out-of-memory issue on our Linux server. We will include these results in the final version.

Thank you very much for the constructive comments and questions. We are grateful for the positive comments on our design and empirical justification. Please see our detailed one-by-one responses below.

Weakness #1: More Experimental details.

For experimental results reported in Table 1, the proposed UNPrompt and all competing methods are trained on Facebook and then directly tested on the other six datasets without involving any further training or label information of the target graphs. The training stage in UNPrompt involves pre-training and prompt learning. The Facebook dataset is used for both pre-training and prompt learning in UNPrompt but in a sequential order, as stated in Algorithm 1 in Appendix C.

Weakness #2: More datasets from different domains.

Please refer to our reply in Global Response to Shared Concerns#2 in the General Response section above for this concern.

Weakness #3: More explanation on coordinate-wise normalization.

The proposed method aims to learn a generalist anomaly detection model based on one source graph and then directly apply the learned model to diverse target graphs from different domains and distributions. To achieve this goal, it is critical to learn a generalized anomaly measure across graphs, and we show that the predictability of latent node attributes can serve as such a generalized anomaly measure. However, the inconsistent node attribute dimensionality and semantics between the source graph and target graphs hinder the utilization of this generalized measure. These discrepancies are visualized and analyzed in Figure 1 (a) and Appendix A respectively. To tackle these issues, the proposed coordinate-wise normalization transforms the semantics of different graphs into a common space, as shown in Figure 1 (a) and Appendix A. In this way, the diverse distributions of node attributes are calibrated into the same semantic space and the anomaly measure learned on the source graph can effectively generalize to target graphs. The effectiveness of coordinate-wise normalization is also evaluated in the ablation study (Table 2) where the performance of generalist anomaly detection drops significantly without the normalization.

Question #1: Discuss the difference between UNPrompt and ARC.

While both ARC and our UNPrompt focus on generalist graph anomaly detection, they have significant differences between them in terms of problem setting, methodology and experimental setup.

• Problem setting: ARC addresses a few-shot graph anomaly detection setting that a small number of labeled normal nodes in each target graph is made available during inference, whereas UNPrompt addresses a zero-shot graph anomaly detection setting that does not require access to any labeled data in the target graph during inference.

• Methodology: To align the node attributes of different graph datasets, ARC proposes to sort the attributes based on feature smoothness while we employ a simple yet efficient coordinate-wise normalization module. For anomaly measure, ARC utilizes in-context learning to calculate the anomaly score based on the reconstruction errors of query node embeddings w.r.t. in-context node embeddings. Differently, UNPrompt proposes a novel generalized anomaly measure, the predictability of latent node attributes, to support the learning of generalized prompt embeddings for generalist anomaly detection. In particular, UNPrompt learns graph-agnostic normal and abnormal patterns via a neighborhood-based latent attribute prediction task, in which we incorporate learnable prompts into the normalized attributes of the neighbors of a target node to predict the latent attributes of the target node. Therefore, ARC and UNPrompt takes significantly different methods to achieve the generalist models due to the difference in the problem setting.

• Experimental Setup: The training datasets for ARC consist of a collection of the largest graphs from all multiple graph types/domains. The test graphs from the same types/domains as the training data are used during inference. By contrast, UNPrompt learns the generalist model solely on the Facebook dataset which is a small social network and the testing datasets contain both social networks and co-review networks, resulting in a more challenging and practical scenario for generalist graph anomaly detection.

As we discussed above, ARC is a few-shot method that requires some labeled normal nodes in the target graphs to perform the detection task, which is not viable in the zero-shot setting used in UNPrompt. Therefore, it is not possible to compare these two methods together.

Thank you very much for the constructive comments and questions. We are grateful for the positive comments on our design and empirical justification. Please see our detailed one-by-one responses below.

Weakness and Question: The difference between the zero-shot methodology and inductive settings.

Despite our method and inductive graph learning are both focused on evaluating the learned models on unseen graph data during inference, there are fundamental differences between our zero-shot learning and the inductive graph learning. We clarify the differences as follows:

• For inductive graph learning, the training dataset and testing dataset come from the same graph source. For example, for the graph classification task in [Ref1], 20 graphs of protein-protein interaction (PPI) datasets are used for training, and 2 other graphs are used for testing. These graphs both belong to the same protein-protein interaction graph dataset with the same attribute distribution and semantics. Therefore, the learned model can be easily generalized to the test graphs.

• In our zero-shot setting, the training dataset and testing dataset are from different domains and distributions. They differ in the dimensionality of node attributes and graph semantics. For example, as a shopping network dataset, Amazon contains the relationships between users and reviews, and the node attribute dimensionality is 25. Differently, Facebook, a social network dataset, describes relationships between users with 576-dimensional attributes (please refer to the visualization of the distribution discrepancy in Appendix A). This is one fundamental difference between the inductive setting and our zero-shot setting. Moreover, our zero-shot setting requires the learned models to be directly applied to other graphs from different domains without any further tuning/training or labeled nodes of the target graphs. This requires the learned model to capture the more generalized patterns for anomaly detection based on only one training graph, resulting in a task being more challenging than the mentioned inductive learning.

• There are also studies [Ref2] on inductive graph anomaly detection, but the problem setting is also fundamentally different from our setting. In particular, to allow the evaluation of inductive detection, [Ref2] samples nodes from the same graph to construct two graph datasets, with one graph used for training and another used for testing, leading to the fact that the training and test datasets are essentially from the same distribution. This is fundamentally different from our settings, where training and testing datasets are separately from highly heterogeneous distributions and domains.

Moreover, our problem setting is the same as existing work on zero-shot image anomaly detection [Ref3, Ref4], with the only difference in the data type used. Considering all these factors, we think "zero-shot" is more suitable for characterizing the nature of the problem complexity and more consistent with the terms/concepts used in the anomaly detection community.

Reference

• [Ref1] Xu, Keyulu, et al. "Representation learning on graphs with jumping knowledge networks." International Conference on Machine Learning, 2018.
• [Ref2] Ding, Kaize, et al. "Inductive anomaly detection on attributed networks." Proceedings of the twenty-ninth international conference on international joint conferences on artificial intelligence. 2021.
• [Ref3] Jeong, Jongheon, et al. "Winclip: Zero-/few-shot anomaly classification and segmentation." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2023.
• [Ref4] Zhou, Qihang, et al. "Anomalyclip: Object-agnostic prompt learning for zero-shot anomaly detection." ICLR 2024.

To further demonstrate the difference between inductive learning and zero-shot generalist learning, we adopt the inductive learning methods to the zero-shot setting. Specifically, two representative inductive methods, GraphSage [Ref5] and AEGIS [Ref2], are used and we follow the experimental setup in the main paper. The AUROC results of GraphSage and AEGIS are reported in the following table.

Table A1. AUROC results on six real-world GAD datasets with the generalist model trained on Facebook.

From the table, we can see that either the general inductive graph learning method or the inductive GAD method does not achieve promising performance for the zero-shot generalist GAD task. This highlights the difference and incompatibility between inductive learning and the problem studied in this paper. The results of AUPRC are reported in Appendix H of the revised paper and we will include a subsection in related work to discuss the graph inductive learning studies and our differences to them.

Reference

• [Ref5] Hamilton, Will, Zhitao Ying, and Jure Leskovec. "Inductive representation learning on large graphs." Advances in neural information processing systems 30 (2017).

You haven't addressed my original concern, but I’ve uncovered even more serious issues. This makes the other questions seem less significant by comparison.

First, just because the proposed method didn’t report the optimal results doesn’t mean the results are valid. The fact that no method is optimal is not a reasonable justification for comparing experimental results in a research paper.

Second, you know that this parameter has the most significant impact on the results. You ran your method with this parameter and claimed that the results improve as the parameter increases. But is this true for other methods as well? Have you conducted experiments to verify this?

Third, regarding your use of SVD to reduce the dimensions of other methods—do you really think this is the best approach? It might work best for your method, but is it also the best for the baselines? Have you conducted ablation studies to confirm this?

Finally, even if I reluctantly accept your use of SVD, it’s unreasonable that you’ve arbitrarily chosen the parameter value. Don’t you think that’s odd? At the very least, you should run experiments with different parameter values and compare the results.

Another significant contribution made by UNPrompt is its applicability to work as a conventional unsupervised graph anomaly detector, as shown in Table 3 in the main text. This offers the very first method that not only works effectively under the zero-shot setting but also achieves the new state-of-the-art performance under the conventional full-shot setting.

As for Individual Response, we have provided a detailed one-by-one response to answer/address your questions/concerns after the post of your review.

We very much hope our responses have cleared the confusion, and addressed your concerns. We're more than happy to take any further questions if otherwise. Please kindly advise!

Best regards,

Authors of Paper 4040

Reference

• [Ref1] Aodong Li, Chen Qiu, Marius Kloft, Padhraic Smyth, Maja Rudolph, and Stephan Mandt. Zero-shot anomaly detection via batch normalization. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.