ARC: A Generalist Graph Anomaly Detector with In-Context Learning

We appreciate Reviewer B6wn for the insightful feedback and acknowledge our contributions. The responses to the reviewer are as follows.

Q1: Which type of feature projection method is used in the experiment should be given

A1: Thanks for your valuable suggestion. In our experiments, we used a dimensionality reduction method based on principal component analysis (PCA). We will re-emphasize this in the manuscript.

Q2: The definitions of the concept of single-class normal and multi-class normal

A2: We appreciate your suggestion. We will add the following definitions in the revised manuscript:

Dataset with single-class normal: In this type of dataset, the normal samples share the same pattern or characteristics. For example, in a network traffic monitoring system dataset, normal behavior might be defined by regular patterns of data packets exchanged between a specific set of IP addresses. Any deviation from this single, well-defined pattern, such as an unexpected spike in data volume or communication with unknown IP addresses, can be flagged as anomalous.

Dataset with multi-class normal: In this type of dataset, the normal samples are divided into multiple classes, each with distinct patterns or characteristics. For example, in a corporate email communication network dataset, normal data might be defined by regular patterns of email exchanges within specific departments, such as HR, IT, and Finance. Any deviation from these well-defined patterns, such as a sudden spike in emails between normally unconnected departments or an unusual volume of emails from an individual employee to external addresses, can be detected as anomalous.

Q3: More annotations can be provided in Figure 2

A3: Thanks for the valuable comment! We will add more annotations into Figure 2, including the annotations of $\mathbf{X}$, $\mathbf{R}$, and $\mathbf{H}$ in the "R" block, as well as the annotations of $\mathbf{Q}$, $\mathbf{K}$, $\mathbf{H}_q$, and $\tilde{\mathbf{H}}_q$ in the "C" block.

Q4: In Eq. 6, the anomaly label is denoted by a bold letter y. Does that mean it's a vector? However, should it be a value actually?

A4: Thanks for your careful review. In fact, $\mathbf{y}_{i}$ is the label of sample (node) i, which is a specific value, and $\mathbf{y}$ is a vector consisting of the labels for all samples.

Q5: The reason for the unstable performance under different number of context nodes

A5: Thanks for the valuable question! The instability in anomaly detection performance with varying numbers of context nodes can be attributed to several factors:

Contextual Information Variability: The number of context nodes directly influences the amount of contextual information available for anomaly detection. With too few context nodes, the model may lack sufficient information to accurately distinguish between normal and anomalous nodes. Conversely, with too many context nodes, the model might include irrelevant or noisy information, which can degrade performance.

Dataset Characteristics: Different datasets have varying structures and anomaly distributions, which can affect how context nodes contribute to anomaly detection. The optimal number of context nodes may vary depending on the specific characteristics of each dataset.

We appreciate Reviewer VWTk for the valuable feedback and acknowledge our technical contributions and the effectiveness of the proposed method. We address the concerns raised by the reviewer as follows.

Q1:Why Use a shared MLP in the encoder

A1: Thanks for the insightful comment! According to the empirical analysis in the previous studies [*3,*4], GNNs benefit mainly from propagation and require only a small number of MLPs to increase their nonlinear capabilities. Therefore, we increase the nonlinear capability of the propagating features for different neighborhoods by a shared MLP. In addition, the design of the shared MLP allows the model parameters to be drastically reduced, especially when the number of propagations is large.

[*3] Wu F, Souza A, Zhang T, et al. Simplifying graph convolutional networks[C]//International conference on machine learning. PMLR, 2019: 6861-6871.

[*4] Nt H, Maehara T. Revisiting graph neural networks: All we have is low-pass filters[J]. arXiv preprint arXiv:1905.09550, 2019.

Q2: Reason for value-based attention mechanism

A2: Thanks for the valuable question! As shown in the Discussion in Sec. 4.3 of the paper, in ARC we follow a basic assumption: normal query nodes have similar patterns to several context nodes, and hence their embeddings can be easily represented by the linear combination of context node embeddings. Therefore, the node anomaly score is obtained based on the error before and after the reconstruction. In this case, it is necessary to ensure that the reconstructed features are in the same embedding space as the original features, so we discard the value-based attention. We will add this explanation to the paper.

Q3: How to define the projected dimension?

A3: Thanks for your insightful comment. The projection size of our ARC model is flexible and can be determined based on a balance between computational efficiency and the ability to capture the underlying anomaly-related features. Specifically, we perform a grid search over a range of dimensions and select the one that yields the best loss on a training set. This approach ensures that the chosen dimension is optimal for capturing the necessary information while maintaining computational feasibility.

Q4: Will it require a lot of epochs to get the fine-tuned results for the baseline methods?

A4: We appreciate your insightful question. The cost of fine-tuning for baseline methods indeed varies depending on the complexity of the model and the dataset. In our experiments, we observed that baseline methods generally require a significant number of epochs to achieve optimal performance, which contributes to their high training costs. In contrast, our ARC model leverages in-context learning with few-shot normal samples, allowing it to adapt to new datasets without extensive retraining or fine-tuning. This results in a more efficient and cost-effective approach to graph anomaly detection.

We appreciate Reviewer bLtA for the positive review and constructive comments. We provide our responses as follows.

Q1: If the original feature dimension is smaller than the predefined projected dimension

A1: Thanks for the thoughtful comment! When the original feature dimension is smaller than the predefined projection dimension, we use a random projection (e.g., Gaussian random projection) to upscale the feature into a higher dimensionality and then unify the dimensions into $d_u$ with the projection strategy. We will add these implementation details to the manuscript.

Q2: The reason for using non-value-based cross attention

A2: Thanks for the valuable question. As shown in the Discussion in Sec. 4.3 of the paper, in ARC we follow a basic assumption: normal query nodes have similar patterns to several context nodes, and hence their embeddings can be easily represented by the linear combination of context node embeddings. Therefore, the node anomaly score is obtained based on the error before and after the reconstruction. In this case, it is necessary to ensure that the reconstructed features are in the same embedding space as the original features, so we discard the value-based attention. We will add this explanation to the paper.

Q3: Why unsupervised methods perform better than the supervised methods

A3: We appreciate your insightful question. The possible reasons are two-fold. Firstly, most supervised GAD methods rely on the binary classification paradigm. This means that supervised GAD is trained based on specific anomalies in the training data, which may result in overfitting the anomaly patterns of the trained dataset. In addition, supervised GAD cannot be fine-tuned on the test set using "normal" samples, which also limits its generalizability to new-coming datasets.

Q4: Why Figure 5 (b) has a dropping trend at $n_k$=20?

A4: Thanks for your careful review. As in-context node information is variable, the performance of anomaly detection can be affected by the quality of context node information. In our experiments, we sample normal nodes randomly, so there is randomness due to sample-specific sampling bias. This randomness leads to instability in the model's performance at a particular number of context nodes. Despite this, we can still observe that the overall trend of performance is gradually increasing with increasing $n_k$.

Q5: Why "pre-train & fine-tune" only includes unsupervised methods

A5: Thanks for your insightful comment. To fine-tune the supervised GAD methods on the target dataset, they require both labeled normal samples and anomalies. However, the labeled anomalous samples are not available in our test scenario for fine-tuning by supervised methods. On the other hand, unsupervised methods are label-free and thus can be fine-tuned on the testing dataset.

Q6: Does large number of context nodes cause ARC to become time-costly?

A6: Thanks for the valuable question. As can be seen from the section Complexity Analysis in Appendix E.2 of the paper, the model inference mainly consists of two parts, node embedding generation and anomaly scoring, $\mathcal{O}(L(md_u + nd_uh + nh^2))$ and $\mathcal{O}(n_q(n_k+1)h)$, respectively. It is worth noting that $n_k \ll n$, thus complexity mainly depends on the node embedding generation. Therefore, a larger number of context nodes does not make ARC time-costly.

In addition, we compare the test times (in second) of ARC for datasets with different numbers of context nodes, and the results are shown in the table below. We can see that the effect of different numbers of context nodes on ARC is almost negligible, indicating the high running efficinecy of ARC when $n_k$ is large.

We are grateful to Reviewer HCAf for providing insightful feedback. The detailed responses are provided below.

Q1: Details of feature alignment with sorting

A1: Thank you for the thoughtful comment. In ARC, the smoothness-based feature sorting is performed on the projected features rather than the raw features (please see Line 209 and Algorithm 1 for details). In this context, the projected features of different datasets can be aligned in the same order. We understand that Equation (2) may mislead readers into thinking that $s_k$ is calculated from raw features; but actually, it can be calculated from projected features as well. We will further emphasize this to prevent such misunderstandings.

Q2: Confusing statement of "raw features"

A2: We appreciate the reviewer for pointing out the confusing sentence! This is a wrong statement. The right process is that "the MLP transformation is conducted on the aligned and propagated features", rather than the raw features. Here we denote the raw, projected, and aligned features as $\mathbf{X}$, $\tilde{\mathbf{X}}$, and $\mathbf{X}'$, respectively, so $\mathbf{X}^{[0]}=\mathbf{X}'$. Algo. 1 and Algo. 2 can better demonstrate the operation of this part. We thank the reviewer again for carefully finding this issue and will definitely fix it in the later version.

Q3: How the encoder capture high-frequency signals

A3: Thanks for the insightful comment. In ARC, Eq.(3) is similar to a traditional GNN and can be viewed as low-pass filters. However, with the first sub-formula in Eq.(4), i.e., $\mathbf{R}^{[l]} = \mathbf{Z}^{[l]} - \mathbf{Z}^{[0]}$, the final residual representation $\mathbf{R}^{[l]}$ can capture high-frequency signals. Specifically, if we omit the non-linear transformation in MLP, then $\mathbf{R}^{[l]}=\tilde{\mathbf{A}}^l\mathbf{X}\mathbf{W} - \mathbf{X}\mathbf{W}=(\tilde{\mathbf{A}}^l-\mathbf{I})\mathbf{X}\mathbf{W}$. Here, $(\tilde{\mathbf{A}}^l-\mathbf{I})$ can typically serve as a high-pass filter according to [*1, *2]. Especially when $l=1$, $(\tilde{\mathbf{A}}-\mathbf{I})$ can serve as Laplacian graph filter, a classic high-pass filter. A detailed discussion is also given in the final paragraph of Appendix C. We hope this answer can address the reviewer's concern.

[*1] Zhu, Meiqi, et al. "Interpreting and unifying graph neural networks with an optimization framework." WebConf'21.

[*2] Bo, Deyu, et al. "Beyond low-frequency information in graph convolutional networks." AAAI'21.

Q4: Few-shot setting meets unseen normal class

A4: Thanks for raising this valuable question! Theoretically, the unseen classes may lead to confusing predictions; however, in practice, we find that this issue does not affect the performance a lot. Taking the performance on Cora dataset (which has 7 normal classes) as an example (see Fig. 5 (a)), when shot number $n_k$ is smaller than 7, which means the labeled samples must not cover all classes, the performance is still acceptable and significantly better than the baselines in Table 1. Potential reasons are: 1) the difference between anomalies and normal samples is significantly larger than the intra-class difference of normal samples; 2) the normal samples belonging to unseen classes can be easily represented by the few-shot normal samples.

However, to mitigate the potential negative impact of this issue, we can also employ the following extra strategies: 1) Increase the number of few-shot normal samples as much as possible to cover all normal classes; 2) Enhance the diversity of the few-shot normal samples; 3) Integrate active learning techniques into ARC, which allows the model to select the most confusing sample to be annotated.

Q5: Implementation details of supervised baselines

A5: Thanks for the valuable question. As the reviewer mentioned, the supervised baselines require both labeled normal samples and anomalies for training. However, in the setting of generalist anomaly detection, only few-shot normal samples are available, making it difficult to fine-tune the supervised baselines on the testing datasets. Hence, we only pre-train them on the training datasets and directly apply the pre-trained models to the testing datasets. Note that, in the datasets for pre-training, both labeled anomalies and normal samples are available, ensuring effective pre-training for supervised baselines and ARC. We will add the implementation details to the revised manuscript.

We are grateful to Reviewer HCAf for the valuable feedback. Please find our responses to your new questions below. We hope that our response addresses your concerns.

Q6: Impact of unseen normal class problem

A6: We appreciate you once again for highlighting the unseen normal class problem. We agree that a deeper discussion on the impact of this issue is necessary. As shown in Fig. 5 and Fig. 9, the performance gaps between $n_k=2$ (where normal classes should not be fully covered) and $n_k=100$ (where normal classes should be covered) are generally within the range of $0.5$% - $5$% in terms of AUROC. This indicates that the unseen normal class problem may be a factor affecting the performance of ARC. However, we would like to note that the unseen normal class problem is not a fatal issue of ARC, since the performance when $n_k=2$ remains generally acceptable and won't collapse to indistinguishable prediction (e.g., AUROC=50% and AUPRC=0%).

We want to express our appreciation to the reviewer once again for identifying the potential unseen normal class problem in ARC. We will definitely discuss the potential limitations caused by this issue in the revised manuscript and provide possible strategies (in A4) for users/readers to mitigate this problem.

Q7: Codes of propagation in ARC

A7: Thank you for your detailed observation regarding the implementation of the Ego-Neighbor Residual Graph Encoder in the ARC model.

The reason the adjacency matrix is not directly used in the forward function (Lines 21-39 in model.py) is due to our decoupled architecture in Eq.(3), i.e., the propagation is directly conducted on the features without learnable parameters. In this case, we can move the propagation step into the codes of data preprocessing to enhance the running efficiency (since we can only run it once). Specifically, the codes of propagation are in the "propagated" function (Lines 143-148 in utils.py), which is called in Lines 53-57 in main.py before the training of the encoder. Then, the propagated features (saved in Dataset.graph.x_list) are subsequently used in the forward function (Lines 21-39 in model.py) for downstream residual encoding.

We appreciate your suggestion, and to prevent potential misunderstandings, we will incorporate more comments in the publicly released code for interpretation.

Thanks for the detailed reply. I am still concerned about the generalization of the proposed method as the generalization capability is the major contribution in this paper. I agree with the comment by reviewer RwhU that "The method section did not provide a solid theoretical analysis to support this claim." when dealing with the new dataset. In addition, the experimental results are not sufficient to demonstrate the capability of the proposed method on the unseen tasks.

In addition, I have one more question regarding your response to Reviewer RwhU about the results of few-shot samples. Why does the performance of ARC achieve the best performance with limited number of pseudo samples (e.g., #Pseudo Normal = 2) on some datasets, such as Amazon, Facebook and Weibo? As you mention during the rebuttal that "the advantage of having a larger number of normal samples reduces the impact of anomalies within the pseudo normal samples.", while the performance of ARC tends to decrease on these datasets when the number of pseudo normal samples increases. Do you have any explanation or thoughts to this observation?

We appreciate Reviewer RwhU for the perception of our contributions and thank the reviewer for the insightful feedback. The detailed responses are provided below.

Q1: Ambitious statement of the learning target

A1: Thank you for raising this valuable comment. While we cannot guarantee that the proposed method will perform well on every new dataset, it is capable of generating reliable predictions through in-context learning on unseen datasets. Our experiments also demonstrate the generalizability of the proposed method. To clarify the capabilities of ARC, we will carefully revise the statement to ensure it is more precise.

Q2: Declare the scope of this work

A2: Thank you for the insightful suggestion! In the revised manuscript, we will further emphasis the scope of this work (node-level generalist GAD) in the introduction section.

Q3: Diversity of datasets

A3: We appreciate the reviewer’s valuable suggestion. We recognize the importance of dataset diversity in the generalist GAD setting, and we have included datasets from three different domains (Citation network, Social network, and Co-review network) with both real and injected anomalies. To further evaluate the generalizability of ARC, we have added four additional datasets from four new domains as test datasets for ARC. These new datasets exhibit significant diversity compared to the training datasets, as they come from diverse, new, and unseen domains. The statistics are as follows.

The AUROC comparison on the four new datasets is shown in the following table. As seen in the table, the proposed method ARC demonstrates competitive performance on all new datasets, showcasing its strong generalizability to unseen domains. Additionally, ARC exhibits excellent scalability on large datasets (e.g., T-Finance). We hope that these additional experiments on unseen domains and datasets address your concerns about dataset diversity.

Q4: Requirement on few-shot samples

A4: Thank you for the thoughtful comment. In-context learning is a critical mechanism in ARC to ensure the model can receive basic patterns of test datasets. Since we only require a few normal samples, the annotation cost of ARC can be low. In parctice, it is easier to find some normal data in a real-world graph because they are more numerous and their patterns are more representative. Also, according the results in Fig.5, ARC can also work well when the shot number is quite small, which further shows its label efficiency.

In cases where labeled samples are not available, we can introduce a "pseudo normal trick". This involves randomly sampling nodes from the test graph to serve as "pseudo normal samples". Given the assumption that the number of normal samples is significantly larger than that of anomalies, most of the pseudo normal samples will actually be true normal samples. The advantage of having a larger number of normal samples reduces the impact of anomalies within the pseudo normal samples. We can then use these pseudo normal samples as context nodes in ARC.

The experimental results of using different numbers of pseudo normal samples are shown in the table above. Surprisingly, ARC demonstrates competitive performance with the pseudo normal trick. It is important to note that no labeled data is used at all in this case. However, for several datasets (e.g., Weibo and Amazon), the performance is still inferior to that of the few-shot counterpart, highlighting the importance of in-context normal samples in generalist GAD.

Dear Reviewer RwhU,

We sincerely appreciate your time and expertise in reviewing our submission. Acknowledging the demands on your schedule, we are mindful not to intrude on your time. However, we would be grateful if you confirm that our rebuttal adequately addresses your concerns.

Thank you in advance for your consideration.

Authors