Summary
Graph anomaly detection aims to identify abnormal nodes in a given graph. The manuscript argues that the existing graph anomaly detection datasets have one-class homophily where the homophily of normal nodes is much stronger than abnormal nodes. To utilize the one-class homophily phenomenon in graph anomaly detection, a new similarity-based anomaly scoring measure, named local node affinity, is proposed. The proposed method, TAM, learns the parameters of multiple graph neural networks called LAMNets by maximizing the sum of local node affinity on the original graph. The iterative graph truncation technique (NSGT) removes the links between normal and abnormal nodes in each step, and the resulting graphs are fed into LAMNets. During the message passing, LAMNet uses the truncated adjacency matrix. The local node affinity-based anomaly score is measured on the original graph using node representations generated by LAMNets. Experimental results show that TAM achieves high AUROC and AUPRC values compared to seven graph anomaly detection methods on six benchmark datasets.
Strengths
1. NSGT introduces randomness by removing the non-homophily edges in a probabilistic approach. To utilize such randomness, TAM uses an ensemble strategy by performing NSGT multiple times and feeding the resulting graphs to multiple LAMNets. Table 2 in Appendix C shows that the ensemble strategy improves the performance of TAM.
2. The manuscript provides empirical justifications for the major claims. For instance, the homophily distribution in Figure 1(a) supports the one-class homophily phenomenon. Figure 3(a) and Figure 3(b) show that the Euclidean distance between the nodes connected by a non-homophily edge tends to be greater than that between the nodes connected by a homophily edge.
3. Ablation studies with various variants of TAM and hyperparameter sensitivity analyses show that each component of TAM is effective.
Weaknesses
1. It is not guaranteed that the one-class homophily property holds for all graph anomaly detection datasets. For instance, both normal and abnormal nodes in the YelpChi-RUR dataset are homophilic, as shown in Figure 1 (d) in Appendix A.
2. The performance of NSGT might depend on the quality of the node attributes. NSGT performs the graph truncation by considering the node attributes of the original graph. As mentioned in lines 170-171, if the original node features contain many irrelevant attributes, NSGT might not work well. Furthermore, features of abnormal nodes can be intentionally camouflaged [1, 2].
[1] Liu et al., Alleviating the Inconsistency Problem of Applying Graph Neural Network to Fraud Detection, SIGIR 2020.
[2] Dou et al., Enhancing Graph Neural Network-based Fraud Detectors against Camouflaged Fraudsters, CIKM 2020.
- One suggestion is to utilize the node representation vectors calculated by LAMNets. In addition, an attribute selection strategy can be introduced to remove irrelevant or redundant node attributes.
3. While this manuscript assumes an unsupervised learning setting, one of my concerns is that most state-of-the-art methods assume a semi-supervised learning setting. Indeed, in many real practices, some supervision can be provided for graph anomaly detection, e.g., labeling undesirable nodes or patterns. Given this, the benefit of the proposed method can be limited.
4. Existing studies [3] convert YelpChi by merging different relations into a single relation. Why YelpChi-RUR and Amazon-UPU are used instead of the full datasets? Instead of selecting one particular relation, the authors can utilize all relations and treat them as a single relation.
[3] Chen et al., GCCAD: Graph Contrastive Learning for Anomaly Detection, TKDE 2022.
5. The statistics of Amazon and YelpChi differ from the actual ones. For Amazon, the number of nodes is 10,224, and the number of anomalies is 693 (6.78%). For YelpChi, the number of nodes is 23,831, and the number of anomalies is 1,217 (5.11%).
6. Minor Comments:
- Lines 206-207 are confusing. According to lines 206-207, the truncated adjacency matrix instead of the original adjacency matrix is used to optimize LAMNets. However, the local affinity is calculated based on the original adjacency matrix during optimization, as stated in lines 261-262.
- In lines 215-221, it is not specified how to handle the case where $d_{i, max}$ is less than $d_{mean}$.
- In lines 116-117, "such degree" should be modified to "such as degree".
Questions
1. Why does NSGT utilize raw attributes instead of node representations learned from LAMNet?
2. Is there any experimental result on large-scale graph anomaly detection datasets?
3. Isolated nodes can appear after performing NSGT. How does TAM-T compute the anomaly scores of such isolated nodes?
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
1. As the TAM model works solely on the assumption of one-class homophily, it might not perform effectively on the graphs where abnormal nodes are homophilic, e.g., YelpChi-RUR.
2. Since NSGT directly utilizes the raw node features to truncate the graph, the quality of the graph truncation might be affected by the quality of the raw features. However, there can be many irrelevant or redundant attributes in the original features.
3. Due to the definition of local node affinity measure, TAM cannot handle isolated nodes in the graph even though the node features are available.