SpaceGNN: Multi-Space Graph Neural Network for Node Anomaly Detection with Extremely Limited Labels

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: SpaceGNN has demonstrated its superior performance under low-resource conditions. How about the performance when more training data are available? This experiment may make SpaceGNN a more general and practical algorithm.

RW1: Thank you for pointing that out, We have updated our manuscript and included performance figures for various datasets across different training set sizes in Appendix K. Through these additional experiments, we can observe that as the size of the training data increases, our proposed SpaceGNN still outperforms all baseline models. For detailed discussions, please kindly refer to our revised manuscript.

Q1: How about the performance when more training data are available?

RQ1: Please kindly refer to RW1.

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

Dear Reviewer,

We sincerely hope that we have addressed all your concerns, and we are glad to answer any additional questions you may have.

Warm regards,

The Authors of Submission6161

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: I think this paper has two important focuses: (1) the anomaly detection task and (2) extremely limited samples. However, after reading the whole methodology section, my personal impression is that the proposed method is designed for a regular binary classification task. I suggest the authors emphasize more on which designs are specialized for few-shot samples and what makes this proposed method specialized for an anomaly detection problem, compared to a regular binary classification task.

RW1: Thanks for pointing that out. However, in our manuscript, we have provided detailed explanations of why our proposed method is specifically designed for graph anomaly detection rather than a simple regular binary classification task.

Firstly, in the real applications of regular binary classification tasks, the complexity of graph structures is typically less pronounced when compared to the intricate structures found in real-world graph anomaly detection tasks, e.g., tree structures in malicious review detection or circle structures in money laundry detection. In Section 1, we have introduced that these structures represent a critical challenge in addressing real graph anomaly tasks. In Section 4, we have also provided both theoretical analyses and empirical evidence to show that it is better to project such complex structures into different spaces using our proposed components.

Secondly, regular binary classification tasks usually do not suffer from the limited supervision problem in the real deployment. However, it is a ubiquitous problem within the area of graph anomaly detection tasks. Building on such a fact, we apply the ensemble technique to collect comprehensive information from different independent spaces to boost the performance. Our theoretical analysis elucidates the efficacy of the ensemble method for tackling such challenges. Thus, From both theoretical and empirical perspectives, our framework is highly correlated to graph anomaly detection tasks.

W2: This paper includes 4 theorems in total, but I found that theorems 3 and 4 are very general theorems, regarding the general ensemble methods for cross-entopy losses, which is irrelevant to the node anomaly detection task. Also, to be frank, I think they are a bit trivial because they are very straightforward and might not be appropriate to be termed as "theorems" (maybe propositions).

RW2: Thanks for pointing that out. The inclusion of these two theoretical analyses serves as a crucial justification, aligning with the subsequent experiments detailed in Section 5. These analyses are not trivial since the most important prerequisite of these two analyses is the independence of different models. Notably, all the previous works in this domain, as discussed in Sections 1 and 2, are designed in a single space, and thus they cannot leverage ensemble methods as our proposed framework. With three independent spaces, i.e., Hyperbolic, Euclidean, and Spherical spaces, our model is designed to employ an ensemble architecture, specifically tailored to address the challenges posed by limited supervision in practical graph anomaly detection tasks. Therefore, it is necessary to present theoretical analyses of the ensemble method, given its significant relevance to our approach. However, in response to your constructive feedback, we have implemented the suggested revisions by transitioning Theorems 3 and 4 to Propositions 1 and 2 in our manuscript. Please kindly refer to our revised manuscript.

W3: Another concern of this paper is its writing. I tried to understand the whole model architecture through the equations in Section 4 but found some notations that were missing or had not been introduced appropriately. Also, it looks like most critical equations are not numbered. I suggest numbering them so they can be quoted when two equations are closely working.

RW3: Thanks for pointing that out. We have revised our manuscript and added numbers to the critical equations. Please kindly refer to the updated version of our manuscript.

W3.1: I found the distance is defined in line 236, but it looks like it is not being used in Eqs between lines 281 and 286.

RW3.1: We have indeed incorporated the distance concept into our framework as a pivotal aspect of our contributions. The definition of distance in Line 236 serves to elucidate a crucial observation we have made, i.e., the Expansion Rate (defined based on the distance in Definition 1) demonstrates that for different data, it is better to project the node features into different spaces to collect comprehensive information, thereby enhancing model performance. In the context of Lines 281-286, where we outline our base GNN architecture in a general form, the coefficient $\omega_{ij}^{\kappa^l}$ in Line 341 is defined based on the distance in Line 236. This linkage ensures that our framework can capture the underlying properties of distances within the neighborhood of all the nodes.

W3.2: Eq. 405 defines the ensemble of models, which is the sum of several functions, but it is unclear how this "addition" operation works for several functions. Do you mean the output of every function from line 286 is added together?

RW3.2: The “addition” operation is similar to the soft-voting algorithm. In the design of ensemble models, the soft-voting algorithm is one of the most prevalent techniques. Initially, each classifier assigns probabilities to individual classes, and their averages are computed. The ensemble prediction is then determined by the class with the highest cumulative probability. Notably, while the original soft-voting algorithm computes the arithmetic average of all classifiers, we implement a weighted average soft-voting to better adjust the weights of different classifiers. For example, consider a scenario with three classifiers trained to classify nodes as anomalies or normal. If the first classifier predicts anomaly with a probability of 0.7 and normal with 0.3, the second classifier predicts anomaly with a probability of 0.4 and normal with 0.6, and the third classifier predicts anomaly with a probability of 0.9 and normal with 0.1. Assigning weights of 0.1, 0.5, and 0.4 to the first, second, and third classifiers, respectively, the ensemble would predict that the node is an anomaly based on weighted probabilities: $0.7 * 0.1 + 0.4 * 0.5 + 0.9 * 0.4 = 0.63$ for anomaly and $0.3 * 0.1 + 0.6 * 0.5 + 0.1 * 0.4 = 0.37$ for normal class probabilities.

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

Dear Reviewer,

We sincerely hope that we have addressed all your concerns, and we are glad to answer any additional questions you may have.

Warm regards,

The Authors of Submission6161

Q1: GADBench adopts AUC, AUPRC, and Rec@K as metrics for comprehensive evaluation. Is there any particular reason you use AUC and F1 instead?

RQ1: There are three main reasons for using AUC and F1 as our performance metrics.

First, in the field of supervised graph anomaly detection, researchers commonly adopt AUC with one of the metrics in F1 and AUPRC to evaluate the performance of their frameworks, as evidenced in previous studies [1, 2, 3, 4, 5]. Note that the authors of BWGNN [4], who are also the authors of GADBench, select AUC and F1 as evaluation metrics. Hence, in the literature, it is quite standard to adopt AUC and F1 as the metrics to show the effectiveness of our proposed model.

In addition, F1 is the combination of precision and recall into one metric by calculating the harmonic mean between those two, which can reflect both AUPRC and Rec@K to some extent.

Third, according to Appendix A in GADBench, the baseline model, XGBOD, is an unsupervised framework. It is hard to report a reasonable F1 for such unsupervised models, as calculating F1 requires selecting a specific threshold. This might be the reason why GADBench utilizes AUPRC and Rec@K as their metrics, which are the most commonly used evaluation metrics for unsupervised graph anomaly detection models [6, 7, 8].

In conclusion, in the literature, F1 can provide a clear, interpretable, and balanced evaluation of precision and recall for a specific threshold selected based on the validation set, making it a practical and widely used metric in the area of supervised graph anomaly detection tasks, while AUPRC and Rec@K are more suitable for the unsupervised graph anomaly detection tasks.

Q2: GADBench also provides a semisupervised setting with limited labels. Instead of using a random split, it will be more convincing and reproducible to run experiments on the public split provided by GADBench.

RQ2: There are two main reasons for not using the data split in GADBench.

First, while the authors of GADBench provided a preprocess.ipynb file for data split preprocessing in their official GitHub repository, the splits outlined in this file are not aligned with our focused settings. For instance, the training and validation ratio of Tolokers and Questions are 50% and 25%, respectively; those of T-Social, T-Finance, Reddit, and Weibo are 40% and 20%, respectively; and those of Amazon, YelpChi, and DGraph-Fin follow the original data split from their corresponding papers, which do not adhere to our limited supervision split criteria. Therefore, we cannot track the official GADBench split with limited labels.

Second, the authors of GADBench only specify the training set size in the semi-supervised setting, leaving the validation set size unspecified. Consequently, in the absence of this crucial information, we are unable to determine the appropriate validation set size for such a scenario. According to the fully-supervised setting, the validation set size is set at 20%, this does not align with our objective of a limited supervision setting due to the substantial size of the validation set. Our study focuses specifically on extreme cases where both training and validation data are severely constrained. Specifically, as we mentioned in Section 5.1, we randomly divide each dataset into 50/50 for training/validation, with the remaining nodes reserved for testing. This methodology mirrors real-world graph anomaly detection tasks where limited training and validation data are common challenges.

Q3: Line 292 claims $\kappa$ is learnable, but line 405 seems to restrict $\kappa$ either positive or negative.

RQ3: As shown in Section 4.4 of our manuscript, we utilize an ensemble way to collect comprehensive information from Hyperbolic, Euclidean, and Spherical spaces. The reason why we restrict $\kappa$ either positive or negative is that we aim to employ several independent GNNs to learn from independent spaces, instead of mixing various spaces in different layers of each single GNN. The preservation of the independence of different spaces perfectly satisfies the requirement of ensemble methods, as shown in our theoretical analysis in Section 4.4. To sum up, we restrict each single GNN in a single space (one of Hyperbolic, Euclidean, and Spherical spaces) with learnable $\kappa$ to provide comprehensive independent information collected from independent spaces for ensembling.

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

Reference:

1. Nan Chen, Zemin Liu, Bryan Hooi, Bingsheng He, Rizal Fathony, Jun Hu, Jia Chen. Consistency Training with Learnable Data Augmentation for Graph Anomaly Detection with Limited Supervision. ICLR 2024.

2. Yuan Gao, Xiang Wang, Xiangnan He, Zhenguang Liu, Huamin Feng, Yongdong Zhang. Addressing Heterophily in Graph Anomaly Detection: A Perspective of Graph Spectrum. WWW 2023.

3. Yuchen Wang, Jinghui Zhang, Zhengjie Huang, Weibin Li, Shikun Feng, Ziheng Ma, Yu Sun, Dianhai Yu, Fang Dong, Jiahui Jin, Beilun Wang, Junzhou Luo. Label Information Enhanced Fraud Detection against Low Homophily in Graphs. WWW 2023.

4. Jianheng Tang, Jiajin Li, Ziqi Gao, Jia Li. Rethinking Graph Neural Networks for Anomaly Detection. ICML 2022.

5. Ziwei Chai, Siqi You, Yang Yang, Shiliang Pu, Jiarong Xu, Haoyang Cai, Weihao Jiang. Can Abnormality be Detected by Graph Neural Networks? IJCAI 2022.

6. Jingyan Chen, Guanghui Zhu, Chunfeng Yuan, Yihua Huang. Boosting Graph Anomaly Detection with Adaptive Message Passing. ICLR 2024.

7. Hezhe Qiao, Guansong Pang. Truncated Affinity Maximization: One-class Homophily Modeling for Graph Anomaly Detection. NeurIPS 2023.

8. Dmitrii Gavrilev, Evgeny Burnaev. Anomaly Detection in Networks via Score-Based Generative Models. ICML 2023 Workshop SPIGM.

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 paper has no details on what $\kappa$ is like after learning.

RW1: Thanks for pointing that out, we have revised our manuscript and included Table 11 of learned $\kappa$ in Appendix I. Please kindly refer to our revised manuscript.

W2: The Multiple Space Ensemble may increase the computational complexity. There is neither theoretical analysis nor efficiency experiments to show how much additional cost is compared to a single model.

RW2: Thanks for pointing that out, we have revised our manuscript and included the theoretical analysis of time complexity in Appendix J. According to our analysis of the updated manuscript, the computational complexity will not increase compared to a single model, e.g. GAT, with proper hyperparameters. Please kindly refer to our revised manuscript.

W3: The authors have not released code for reproducibility.

RW3: Thanks for pointing that out, we have uploaded our source code for reproducibility, attached with detailed steps in README. Please kindly refer to the supplemental materials on OpenReview.

W4: Although the paper is understandable, there are several minor presentation issues that reduce readability:

The captions of figures are usually at the bottom of the figure instead of on the top in ICLR format.

The sections in the Appendix are not necessarily subsections in a single Section A.

The abbreviation of Multiple Space Ensemble (MSE) may be confusing to the audience and can be misinterpreted as another commonly used term Mean Squared Error.

Line 281: avoid in-place operation to $H^l$

Line 313: $s_{ij}$ is not clear defined

RW4: Thanks for pointing that out, we have revised our manuscript based on your constructive suggestions. Please kindly refer to the latest version of our manuscript.

Dear Reviewer,

We sincerely hope that we have addressed all your concerns, and we are glad to answer any additional questions you may have.

Warm regards,

The Authors of Submission6161

Dear reviewers,

The ICLR author discussion phase is ending soon. Could you please review the authors' responses and take the necessary actions? Feel free to ask additional questions during the discussion. If the authors address your concerns, kindly acknowledge their response and update your assessment as appropriate.

Best, AC

I appreciate authors' response. Although some of my concerns have been addressed, I still cannot agree with some of authors' claims on evaluation:

• Evaluation metrics: existing supervised benchmark GADBench adopts AUC, AUPRC, and Rec@K. It is not convincing to have a different metric.
• Dataset split: the semi-supervised setting in GADBench has 20 positive labels (anomalous nodes) and 80 negative labels (normal nodes) for both the training set and the validation set in each dataset, which is not so different from 50/50 in authors' setting. The public split should be used.

Therefore, I am going to keep my score for now and reserve my right adjust the score.

I appreciate the authors' additional experiments. I will keep my score positive and suggest a weak accept (between 6 and 8) for this paper.