Rayleigh Quotient Graph Neural Networks for Graph-level Anomaly Detection

We appreciate your comprehensive and constructive review. Your crucial comments on the statistical differences between anomalous graphs and normal graphs are exceedingly helpful for us to improve our manuscript. Our point-to-point responses to your comments are given below.

W1: The insight of this paper seems to be on shaky ground. Figures 1 and 4-12 do not clearly show the statistical difference between anomalous graphs and normal graphs with respect to Rayleigh Quotient. Detailed text description about the ''significant disparity" between two classes is necessary but not found on the current version. (This is the main reason why I currently tend to reject this paper.)

RW1: Thanks for your constructive suggestions. Your feedback will greatly contribute to improving the quality of our manuscript. Our detailed explanation is as follows.

In the field of graph-level anomaly detection, researchers mainly rely on the chemical compound datasets available from TUDataset [2]. To the best of our knowledge, these datasets are the only datasets directly applicable to the graph-level anomaly detection task. Each dataset consists of several chemical compounds (graphs) whose labels are decided by whether they are inactive or active to a tumor. Despite being categorized into two classes, these chemical compounds still share many similar characteristics, so it is natural that the Rayleigh Quotient of these two classes presents similarity in some dimensions, which reflects the reviewer’s concern.

However, it is important to note that the values of Rayleigh Quotient on anomalous graphs and normal graphs can be extremely distinct from each other in some specific dimensions, showing the key differences between the compounds in the two classes. Our proposed model is capable of capturing these differences and hence achieves better performance as shown in the experiment. To better show the “significant disparity” of the Rayleigh Quotient between anomalous graphs and normal graphs, we further add the following experiment.

In particular, we calculate the intra-distance of the normalized Rayleigh Quotient on normal graphs and anomalous graphs, respectively. Besides, we calculate the inter-distance of the normalized Rayleigh Quotient between normal graphs and anomalous graphs.

Due to the time limit, we present the result on the SN12C dataset. We first calculate the pairwise inter-distances and pairwise intra-distances for the normalized Rayleigh Quotient of two classes. To keep consistency with the experiments described in Figure 1 (refer to Section 1), we still construct 10 equal-width bins. Subsequently, we report the results of inter-distances divided by intra-distances of the normalized Rayleigh Quotient for the two classes, respectively. The detailed experimental result is presented below, where $d_i / d_a = \frac{\text{inter-distance between normalized RQ of different classes}}{\text{intra-distance between normalized RQ of anomalous graphs}}$ and $d_i / d_n=\frac{\text{inter-distance between normalized RQ of different classes}}{\text{intra-distance between normalized RQ of normal graphs}}$.

As shown in the above table, the result clearly shows a significant disparity between the inter-distance and intra-distance values. Notice that in certain cases, the values of inter-distances can be 10 times or even 100 times larger than that of intra-distances, and the larger the ratios are, the more distinguishable these two classes are. Moreover, it is apparent that normal and anomalous graphs exhibit different patterns in many cases. which clearly demonstrates the “significant disparity” between the two classes.

[2] https://chrsmrrs.github.io/datasets/docs/datasets/

W2: I recommend briefly introducing Rayleigh Quotient in the introduction or preliminaries section.

RW2: Thanks for your constructive suggestions. We will incorporate the relevant content into our revised manuscript.

Q1: How about the graph-level anomaly detection performance of ChebyNet, BernNet, GMT, Gmixup, and TVGNN if the loss function is replaced by the class-balanced focal loss?

RQ1: We have conducted experiments for GMT, Gmixup, and TVGNN. Please refer to Table 3 in the Appendix in the original manuscript for detailed experimental results.

The following table reports the results of ChebyNet and BernNet, where BernNet-CB and ChebyNet-CB denote the corresponding model with the class-balanced focal loss function, respectively.

As we can see, the class-balanced focal loss does not yield benefits for ChebyNet and BernNet. This further demonstrates that even though tackling the imbalanced problem of datasets, these spectral GNNs fail to capture the properties of anomalous graphs.

We will include these results in our revised manuscript.

Q2: What is the ratio between the normal and anomalous graphs utilized during model training?

RQ2: Please refer to Table 1 in the original manuscript for the statistical information of all datasets, which includes the number of normal and anomalous graphs. The anomalous ratio for each dataset is around 5%. In addition, in Section 4, we have stated that “we randomly divide each dataset into training/validation/test sets with 70%/15%/15%, respectively. During the sampling process, we ensure that each set maintains a consistent ratio between normal and anomalous graphs.” Therefore, the ratio between normal and anomalous graphs utilized during model training for each dataset remains consistent with the original dataset.

We sincerely appreciate your time, and we are glad to answer any additional questions you may have.

W3: In page 4, authors wrote "If the graph Laplacian and graph signal of two graphs are close, then their Rayleigh Quotients will be close to each other and these two graphs will highly likely belong to the same class." I tend to think this statement is correct, but it seems not applicable for anomalies. Anything that is different from normal can be regarded as an anomaly, but we actually cannot get training data that can represent the full picture of anomalies. In addition, two anomalous graphs can also be very different. This paper uses two-class datasets for experiments, but what will be the result if we regard the third class that has never appeared in the training set as anomalies to test the proposed model?

RW3: Thanks for raising this point. The problem you mentioned can be categorized as an out-of-distribution detection task rather than an anomaly detection task. We acknowledge that this problem is out of the scope of this manuscript since there are notable distinctions between anomaly detection and out-of-distribution detection.

Typically, in out-of-distribution datasets, we only have one class called in-distribution data, so out-of-distribution detection focuses on determining whether a new sample belongs to the in-distribution data. However, anomaly datasets usually contain data with two distinct characteristics. Therefore, anomaly detection aims to determine that a new sample belongs to one of the two classes.

For example, anomaly detection involves identifying all the tigers from a dataset that contains both cats and tigers, whereas out-of-distribution detection focuses on determining whether a new cat sample, such as a Birman cat, can be correctly classified as a cat given training dataset that exclusively contains Ragdoll cats.

In our manuscript, we follow the settings of iGAD and further include additional related baselines to conduct experiments. To the best of our knowledge, the datasets we employ are the only ones available in the field of graph-level anomaly detection.

Despite our primary focus not being on the out-of-distribution task, we still conduct additional experiments to evaluate the performance of our proposed model. We use a modified COLORS-3 [1] dataset from TUDataset [2], which is an 11-class graph classification dataset. We randomly select two classes as out-of-distribution graphs and the remaining classes serve as normal graphs. One of the out-of-distribution classes is included in the training and validation sets, while the other is added to the testing set.

The results of this set of experiments are as follows:

Compared with other baseline models, our proposed RQGNN achieves significant improvements in both AUC and F1 scores although RQGNN does not focus on out-of-distribution detection.

We will include these results in our revised manuscript.

[1] Boris Knyazev, Graham W. Taylor, Mohamed R. Amer. Understanding attention and generalization in graph neural networks. NeurIPS, pages 4204-4214, 2019.

[2] https://chrsmrrs.github.io/datasets/docs/datasets/

W4: In page 5, authors wrote "However, as analyzed in Section 3.1, to capture the spectral properties of anomalous graphs, it is necessary to consider the spectral energy with respect to each eigenvalue." But, the reason for using graph wavelet convolution is still unclear.

RW4: Graph wavelet convolution has been demonstrated to possess a strong capability to learn representations in the spectral domain from previous research, making it a natural choice as our backbone model. We also compared our RQGNN with other spectral GNNs, such as BernNet and ChebyNet, but as shown in our experiments in Section 4, even the state-of-the-art spectral GNN models can not handle complex graph-level anomaly detection tasks.

In addition, as proven in Section 3, we need to consider spectral energy in terms of each eigenvalue. According to BernNet [8], each graph filter can be viewed as a band filter, and each band filter only allows certain spectral energy to pass, so it is necessary to adopt a model with multiple graph filters. The graph wavelet convolution model can be considered as a combination of different graph filters, enabling us to consider the spectral energy associated with each eigenvalue. By employing different band filters, we can focus on the spectral energy of different eigenvalues. Therefore, leveraging graph wavelet convolution provides advantages compared to using single graph filters.

[8] Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. In NeurIPS, pp. 14239–14251, 2021.

We appreciate your comprehensive and constructive review. Your crucial comments on experiments are exceedingly helpful for us to improve our manuscript. Our point-to-point responses to your comments are given below.

W1: The reviewer thinks that the motivation and rationale of Rayleigh Quotient Learning should be emphasized. It is a quite general problem that “existing methods fail to capture the underlying properties of graph anomalies”.

RW1: Thanks for your constructive suggestion. We will revise the claim as “existing methods fail to capture the property of Rayleigh Quotient in graph anomalies” to emphasize it.

As you can observe from Figure 1 in Section 1, a noticeable distinction between the Rayleigh Quotient of the normal graphs and that of the anomalous graphs can be observed. Subsequent experiments have demonstrated that using this characteristic significantly boosts the performance of graph-level anomaly detection tasks. To avoid confusion, we have revised the manuscript as “the spectral property of graph anomalies”. Furthermore, we will incorporate an additional table to emphasize the importance of the Rayleigh Quotient in graph-level anomaly detection. For more detailed information, please refer to RW1 (Reviewer X1rz).

W2: An algorithm describing the training process is required.

RW2: Thanks for your valuable suggestion. We will include an algorithm in the Appendix of our revised manuscript to provide a detailed description of the training process.

W3: From the objective function in Section 3, the method proposed in this paper is a supervised method. This implies that some of the comparisons in the experiments are unfair because many graph-level anomaly detection methods are fully unsupervised to my knowledge, e.g., OCGIN, OCGTL, GlocalKD, etc.

RW3: Yes, almost all graph-level anomaly detection methods tested in our paper are fully unsupervised. Indeed, the lack of fairness in this area is primarily due to its under-exploration. The main reason is the scarcity of supervised learning methods that can serve as baseline models. To the best of our knowledge, iGAD is the only supervised learning model available for the graph-level anomaly detection task. Consequently, we follow the experimental settings of iGAD. Furthermore, we include more baselines that are related to this task to demonstrate the effectiveness of our proposed model. The existence of this phenomenon also highlights the urgent need to develop new and robust supervised learning models, showing the importance of our work.

W4: The authors only test on chemical datasets in this paper, while there are other data types that are constructed as graphs, such as social networks.

RW4: Since there is currently no existing dataset specifically designed for graph-level anomaly detection in other domains, we modify a synthetic dataset (COLORS-3) and a social network classification dataset (DBLP_v1) to conduct additional experiments. For more detailed information regarding this set of experiments, please refer to RW2 (Reviewer qWnD).

W5: It seems that the proposed RQGNN fluctuates a lot with the change of hyperparameters and shows instability. The authors should explain the reasons for this observation.

RW5: Despite observing variations in the model performance, our model still outperforms other baselines in almost all datasets. Notice that other baselines, such as iGAD, also display performance variations in their experiments when varying hyperparameters.

W6: The impact of hyperparameters on loss function is encouraged to be explored.

RW6: Thanks for your valuable suggestion. Due to the time limit, we conduct experiments of parameter analysis on four datasets. The experimental results of varying hyperparameters are as follows. To summarize, when the $\gamma$ is set to 1.5, RQGNN achieves a relatively stable performance on these datasets. Meanwhile, RQGNN presents a relatively satisfactory when $\beta$ is set to 0.999.

The results of varying the hyperparameter $\beta$:

The results of varying the hyperparameter $\gamma$:

We will add these experimental results in the Appendix of our revised manuscript.

W7: From the ablation study results, the performance of RQGNN does not consistently outperform the other degradation models, and their performance is quite close in many cases. It seems the improvement from the several proposed components is somewhat limited.

RW7: Not exactly. In contrast, the conclusion can be quite the opposite. Our experiments reveal that both RQGNN-1 and RQGNN-2 achieve improvements compared to other baselines, clearly demonstrating the effectiveness of each proposed component in boosting graph-level anomaly detection performance. By combining these two powerful components, we get our proposed RQGNN model.

As we can observe from experiments conducted in Section 4, there are several reasons to highlight the necessity of combining these two components: RQGNN vs. RQGNN-1 RQGNN outperforms RQGNN-1 in all the datasets in terms of both metrics. RQGNN vs. RQGNN-2 RQGNN outperforms RQGNN-2 in 7 datasets in terms of both metrics. Although RQGNN-2 slightly outperforms RQGNN in 3 datasets in terms of one metric, it significantly falls behind RQGNN in terms of the other metric.

These findings clearly demonstrate the necessity of combining both components to achieve superior and more stable performance in the graph-level anomaly detection task. Besides, we aim to find the unified hyperparameters that can achieve good performance for all datasets.

In summary, the proposed two components demonstrate their individual strengths, and we can even combine them together to achieve superior and more stable performance. It is evident that the improvement is not limited, instead, each of the proposed components will provide a new design direction for future research in this area.

Q1: Can the Rayleigh Quotient Learning be used to detect node anomalies?

RQ1: Yes, the Rayleigh Quotient can be used to detect node anomalies. In the original manuscript, we have cited Tang et al. [7] where the authors introduce an interesting idea for node anomaly detection related to the Rayleigh Quotient. However, their focus primarily lies on designing a spectral GNN for node anomaly detection, rather than delving into the properties of the Rayleigh Quotient in the context of anomaly detection. As shown in our paper, Rayleigh Quotient can reveal the properties underlying anomalies and can be further explored in the GNN design for node-level anomaly detection.

[7] Jianheng Tang, Jiajin Li, Ziqi Gao, and Jia Li. Rethinking graph neural networks for anomaly detection. In ICML, pp. 21076–21089, 2022.

Q2: The authors should show the ratio between normal and anomalous graphs. Are they balanced or not?

RQ2: We have provided the number of normal and anomalous graphs of each dataset in Table 1 in the original manuscript. The anomalous ratio of each dataset is around 5%, which shows that these datasets are highly imbalanced. Please refer to Table 1 in Section 4 for more details.

We sincerely appreciate your time, and we are glad to answer any additional questions you may have.

We sincerely hope that we have addressed your concerns satisfactorily, and we will gladly answer any additional questions you may have.

We appreciate your comprehensive and constructive review. Your crucial comments on experiments are helpful for us to improve our manuscript. Our point-to-point responses to your comments are given below.

W1: The relation between Rayleigh quotient and perturbation is well known and studied, for example, in physics. For example: Pierre, C. (December 1, 1988). "Comments on Rayleigh’s Quotient and Perturbation Theory for the Eigenvalue Problem." ASME. J. Appl. Mech. December 1988; 55(4): 986–988. When the vector is close to an eigenvector, then the RQ has a value that is close to the corresponding eigenvector. There is also the Rayleigh-Schrödinger procedure that yields approximations to the eigenvalues and eigenvectors of a perturbed matrix by a sequence of successively higher order corrections to the eigenvalues and eigenvectors of the unperturbed matrix.

RW1: Thanks for bringing that up. We acknowledge that the relation between Rayleigh Quotient and perturbation is well known and studied in physics. However, the inherent properties of the Rayleigh Quotient in the graph domain are still relatively under-explored. Furthermore, to the best of our knowledge, no previous work has considered using Rayleigh Quotient for the graph-level anomaly detection task. Our key observation of Rayleigh Quotient on graph-level anomaly detection as shown in Figure 1 in the original manuscript can provide a new direction for this under-explored field. We will ensure to cite these related papers in our revised manuscript.

W2: The paper explores an important application and datasets, and experimentally shows that the RQ provides a useful feature for detecting change. However, it isn’t clear how general this is beyond the application considered. The anomaly here is a change detector between the baseline distribution (the normal graph class), and some deviation from this graph. Apparently for this data there is no clear class after change (so it isn’t surprising that the graph classifiers don’t work well).

RW2: Thanks for the constructive suggestions. Indeed, although the main application of graph-level anomaly detection is typically focused on detecting chemical compounds, there are still applications in other domains such as social networks. However, due to the lack of datasets specifically collected for graph-level anomaly detection in other domains, we construct our own datasets and conduct experiments on them. To be comprehensive, we use two graph classification datasets to evaluate our RQGNN, one is COLORS-3 [1], which is a synthetic dataset in the TUDataset repository [2], and the other is DBLP_v1 [3], which is a social network dataset as classified in TUDataset [2].

Specifically, we first conduct experiments on the COLORS-3 [1] dataset, which contains 11 classes. We use 10 classes to form normal graphs and use the remaining class as anomalous graphs. The experimental results are as follows:

Then, we conduct additional experiments in the social network domain using the DBLP_v1 [3] dataset, which is a well-balanced social network classification dataset in the field of computer science. In this dataset, each graph denotes a research paper belonging to either DBDM (database and data mining) or CVPR (computer vision and pattern recognition) field, where each node denotes a paper ID or a keyword and each edge denotes the citation relationship between papers or keyword relations in the title. To create a new graph-level anomaly detection dataset, we randomly sample 5% of one class as the anomaly class and use the other class as the normal class. The experimental results are as follows:

Compared with other baseline models, our proposed RQGNN achieves significant improvements in both AUC and F1 scores in these two new domains, which demonstrates the effectiveness of our RQGNN in detecting anomalies beyond the application considered.

[1] Boris Knyazev, Graham W. Taylor, Mohamed R. Amer. Understanding attention and generalization in graph neural networks. NeurIPS, pages 4204-4214, 2019.

[2] https://chrsmrrs.github.io/datasets/docs/datasets/

[3] Shirui Pan, Xingquan Zhu, Chengqi Zhang, and Philip S. Yu. Graph Stream Classification using Labeled and Unlabeled Graphs, ICDE, pages 398-409, 2013.

Q1: Given the large literature on RQ’s it seems likely that eqn (1) is well known?

RQ1: Yes. We acknowledge that the relation between Rayleigh Quotient and perturbation is well known and studied in physics. However, the inherent properties of the Rayleigh Quotient in the graph domain are still relatively under-explored. Furthermore, to the best of our knowledge, no previous work has considered using Rayleigh Quotient for the graph-level anomaly detection task. Our key observation of Rayleigh Quotient on graph-level anomaly detection as shown in Figure 1 in the original manuscript can provide a new direction for this under-explored field.

Q2: Lemma 1 and leading to eqn (4), using L – I_n to compute is from Rivlin or some other reference?

RQ2: The theory of Chebyshev’s series comes from Rivlin et al. [4], and the Eqn. 4 is mainly from Hammond et al. [5]. We will cite this paper in our revised manuscript.

[4] GTheodore J. Rivlin. The Chebyshev polynomials. John Wiley & Sons, 1974.

[5] Hammond D K, Vandergheynst P, Gribonval R. Wavelets on graphs via spectral graph theory[J]. Applied and Computational Harmonic Analysis, 2011, 30(2): 129-150.

Q3: Section 4.5 (and throughout the paper). “Rayleigh Quotient is an intrinsic characteristic of the graph-level anomaly detection task.” Should this be altered to say “for the application studied”? How general is the claim?

RQ3: We admit that we should add the description to weaken the claim and we have revised the description as “Rayleigh Quotient is an intrinsic characteristic of the graph-level anomaly detection task for the application studied”. However, in addition to its application in detecting chemical compounds, Rayleigh Quotient can also be applied in various other domains such as social network areas. Please refer to RW2 for more details.

Q4: Isn’t the anomaly for this application the same as an “out of distribution” test?

RQ4: Not exactly, there are notable distinctions between anomaly detection and out-of-distribution detection.

Typically, in out-of-distribution datasets, we only have one class called in-distribution data, so out-of-distribution detection focuses on determining whether a new sample belongs to the in-distribution data. However, anomaly datasets usually contain data with two distinct characteristics. Therefore, anomaly detection aims to determine that a new sample belongs to one of the two classes.

For example, anomaly detection involves identifying all the tigers from a dataset that contains both cats and tigers, whereas out-of-distribution detection focuses on determining whether a new cat sample, such as a Birman cat, can be correctly classified as a cat given training dataset that exclusively contains Ragdoll cats.

Q5: It seems this area of study would benefit from good baseline data sets. For example, for what random classes of graphs is the RQ approach well founded? This could be studied through simulation and theory.

RQ5: We conduct additional experiments on both a synthetic dataset and a social network classification dataset. For more detailed information regarding these experiments, please refer to RW2.

Q6: Section 4.1: Perhaps you could say a little more about “various chemical compounds and their reactions to different cancer cells”, and how a chemical leads to a graph?

RQ6: The raw data is collected from the PubChem website [6]. This website provides comprehensive information on the biological activities of small molecules, including bioassay records for anti-cancer screen tests with different cancer cell lines. Each dataset corresponds to a specific type of cancer screen with the outcomes categorized as either active or inactive, where the active instances are labeled as 1 and the inactive ones are labeled as 0. Please refer to the Appendix for detailed information on the specific tumor associated with each dataset.

To represent the chemical compounds as graphs, we can consider the atoms in the chemical compounds as nodes, and the chemical bonds between two atoms as edges. Therefore, each chemical compound can be represented as a graph.

We will include these discussions in the Appendix of our revised manuscript.

[6] http://pubchem.ncbi.nlm.nih.gov.

We sincerely appreciate your time, and we are glad to answer any additional questions you may have.

We sincerely hope that we have addressed your concerns satisfactorily, and we will gladly answer any additional questions you may have.

Q5: It seems this area of study would benefit from good baseline data sets. For example, for what random classes of graphs is the RQ approach well founded? This could be studied through simulation and theory.

RQ5: To further address your concern, we show how much perturbation is detectable by RQGNN by simulation. We use SN12C to create 5 new synthetic datasets. Specifically, we first randomly select 5% of normal graphs to perform perturbations. For these graphs, each edge is changed with probability $p$, where $p=0.05, 0.10, 0.15, 0.20,$ or $0.25$. Then we use these perturbed samples as anomalous graphs and all the remaining 95% normal graphs in SN12C to construct these five new datasets. We present the results in the following table:

As we can see from the table, Even if the perturbation probability is only 0.05, RQGNN can still achieve a reasonable result. When the probability of perturbation reaches 0.15, our RQGNN achieves AUC around 1 and F1 over 0.9, which means RQGNN can nicely distinguish the two classes.

We sincerely hope that we have addressed your concerns satisfactorily, and we will gladly answer any additional questions you may have.