Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper presents a GNN-based framework for graph-level anomaly detection, GmapAD. Specifically, GmapAD encapsulate graph structures and node features into node representations and selects the best subset of informative nodes in all possible nodes in graphs for mapping graphs into the new feature space. Then normal and anormal graphs are mapped to deviating locations in the feature space and classified using machine learning techniques (e.g., SVM). Experiments conducted on 9 benchmarks show the effectiveness of the proposed framework compared to state-of-the-art GNN models and graph-level anomaly detection methods.

strength_and_weaknesses: Strengths

- The idea of node candidate optimization via differential evolutionary algorithm is interesting.

- Experimental results show superior performances of GmapAD compared to existing GNN-based graph-level anomaly detection models.

Weaknesses

- In Eq. (1), the author simply uses the average pooling as a graph pooling operation. But, If using attention-based pooling operations ([1], [2], [3]), I think the globally informative node selection is possible with GNN itself without additional candidate optimization. It would be good to have a comparison between GNNs with attention-based pooling and GNNs with candidate optimization.

- I cannot agree with the author’s statement “Most importantly, simply reading out graph representations using its own nodes cannot capture the inter-graph information.”.  Even though each graph has different nodes, since the features of nodes are in the same space, inter-graph information can be captured with graph representations from GNNs with a readout function.

- The author stated that interpretability is an advantage of a framework that proposes interpretability, but there is no analysis of this. 

[1] Gao, Hongyang, and Shuiwang Ji. "Graph u-nets." international conference on machine learning. PMLR, 2019.

[2] Lee, Junhyun, Inyeop Lee, and Jaewoo Kang. "Self-attention graph pooling." International conference on machine learning. PMLR, 2019.

[3] Ying, Zhitao, et al. "Hierarchical graph representation learning with differentiable pooling." Advances in neural information processing systems 31 (2018).

clarity,_quality,_novelty_and_reproducibility: Clarity: Good

Reproducibility: Excellent

Quality: Good

Novelty: Medium
summary_of_the_review: This paper presents a graph-level anomaly detection framework. The presentation of the paper is clear and easy to follow, and the experimental result is convincing, but the motivation is unclear.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this papers the authors proposed a new methodology for finding anomalies in graph data. The focus of this paper is on detecting anomalies using graph-level classification. 
Graph-level anomaly detection is not a new problem. The authors claimed that previous literature has not addressed both intra-graph and  inter-graph relationships as being important features for finding anomalous graphs. 
This paper clearly explained the issues with the previous methods and pointed to two important aspects lacking in previous solutions. First aspect had to do with not taking into consideration inter-graph relations when finding anomalous graphs. Previous methods focused primarily on intra-graph relations. The second aspect is the GNN's inherent lack of explainability.
To address both problems the authors introduced a pipeline that would link graphs (neighborhood nodes aggregated representations) with the most informative set of nodes (taken from all graphs). They would then transform the graphs into candidate feature space and find the best candidate set by applying differential evolution algorithm. The end stage of their pipeline involves running a classifier on graphs in candidate feature space. 
As a result the authors claim to improve both explainability and model efficacy.
strength_and_weaknesses: This appears to be a well-researched paper. 
The authors clearly defined the problem, motivated their solution and tested their approach 
on nine benchmark datasets. They also performed ablation tests that really help illustrating the importance of each major step in their pipeline. 
In the appending the authors discussed their parameter choices their made for DE algorithm,
clarity,_quality,_novelty_and_reproducibility: Regarding reproducibility, the authors claimed that they provided the full source code for their experiments, however, the link they provided pointed to an empty project.

summary_of_the_review: Overall, I found this paper to be well-written and well-motivated. I believe it addressed an important problem and provided an interesting solution.

I would be interested to learn more about measuring the explaiability of approaches. We know that some methods are black boxes and others can be easily interpreted, but this leaves a lot of ground in between. It would be useful if interpretability could also be expressed more precisely.

Also, I would like to ask the authors about their for the future work. Is there there something in their current method they would like to improve upon?

On more question. Could the authors explain how the negative effect of the curse of dimensionality gets avoided during the informative node selection stage?
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposed a method for graph-level anomaly detection using the idea of evolutionary mapping. The method is a semi-supervised learning method. The numerical results verified the effectiveness of the proposed method.
strength_and_weaknesses: Strengths:
1. The essential idea of the article is to select some best candidate nodes for graph mapping, thus leveraging inter-graph information. The author proposed a novel differential evolutionary algorithm to determine the most supportive candidates.
2. The numerical outcomes are good, especially F1 score.
3. The ablation test shows the differential evolutionary process is essential after selecting k informative nodes as candidates.

Weakness:
1. There are some confusing notations in Section 4.2.2. For inforamtive node selection, the author states the top k nodes most similar to normal graph, but only gives the similarity calculation between a node j and a graph G_i , with no clue how node score is aggregated (by summation?) (2) For candidate initialization, rigorously speaking, it should be $\{0, 1\}^{| C_i |}$ not $\{0, 1\}^{| C_p |\}$; the parameter $p_s$ in Bernoulli distribution is unstated in the experiment setting. For updating a set of candidates, the subscript of diagonal matrix $I^t$ is supposed to range from 1 to p, according to the (1) Initialization. However, the author claims to select r1, r2, r3, r4, r5 from [1, $| C_i^t |$], where $| C_i^t |$ represents the size of candidate nodes. By the way, why the author chooses 5 candidates to mutate? There is no stated evidence to determine five. 
2. In Section 4.2.2., the author says that DE algorithm guaranteed convergence, however, metaheuristics such as DE do not guarantee an optimal solution is ever found. Some sufficient conditions must be verified before claiming (global) convergence. 
3. In Section 4.2.2., the evaluation score is suspected to be wrong. Because when true y = 1, the successful prediction with \hat{y}=1 yields score as 0, while the failed prediction with \hat{y}=0 has a score as 1. It is strange to see when true y = 0, the positive result (\hat{y}=0) is scored as 1, wheras the score of negative prediction is equal to 2. The scores are inconsistent and biased, without much explanation.
4. In the evaluation step, the author states to implement SVM on every mutation. Considering there are $p$ condidates and $et$ iterations, it will be very time-consuming and not scalable to large number of graphs.
5. In the abstract, it was claimed that the paper aims to address the low interpretability of GNN. However, in the main context, it is not clear which characteristic of the proposed method can address the problem. And there is also no numerical result to support the claim.
6. It seems that the baselines OCGIN and OCGTL are unsupervised methods. It is not clear how the authors perform them in comparison to the proposed semi-supervised method.
7. It is not clear why the authors didn't use AUC as an evaluation metric. The F1 score, precision, and recall are not good enough for imbalanced classification and usually depend on a classification threshold.
clarity,_quality,_novelty_and_reproducibility: The clarity can be improved. The novelty is enough to some extent. 
summary_of_the_review: Some important points of the paper were not clearly explained. Currently, it is a borderline paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a graph-level anomaly detection method, called GmapAD. The proposed method performs the standard message passing procedure by considering anomalous labels to incorporate intra-graph information, followed by applying the differential evolutionary mapping to the obtained node representations to obtain graph representations incorporating inter-graph information. Finally, any ML algorithms such as SVM can be applied to the obtained graph representations to detect anomalies. The proposal is empirically evaluated on real-world datasets.

### Strength

- The idea of using differential evolutionary mapping to optimize node candidates to explicitly incorporate inter-graph information is novel and interesting. 

- After the authors' rebuttal and revision of the paper, the paper is now clearly written and easy to follow.

### Weakness

- As reviewers pointed out, the interpretability issue should be further elaborated. Currently it is unclear how the proposal is more interpretable than other approaches. 

- The problem setting is unclear. The authors mention that the proposal is semi-supervised in the last paragraph in Section 3. However, this setting is never considered afterwards and it seems that any class labels are assumed to be available. Moreover, the standard SVM is used at the final step, which also indicates that the task is fully supervised. This point should be clarified. 

- Related to the above point, empirical comparison is unfair. The proposed method and three GNNs use class label information in the node embedding process and the final classification step. However, the two graph-level anomaly detection methods OCGIN and OCGLT work in an unsupervised manner (or partially supervised in the sense that only normal data are available in training), and one-class SVM is used for anomaly detection instead of the standard SVM.

- Important baselines, graph kernels, are missing in experiments. In particular, the Weisfeiler-Lehman graph kernel often shows competitive performance compared to GNN-based methods. Since one can explicitly obtain feature representations of graphs via such graph kernels, it should be considered as one of comparison partners.
justification_for_why_not_higher_score: As I have stated in the meta-review and the AC-reviewer meeting report, this paper has several crucial concerns, which may change the conclusion of the paper after fixing them. Therefore the current version is not ready for publication. Since the proposed approach is potentially interesting and novel, I strongly recommend revising the paper according to reviewers' comments and re-submitting it.
Decision: Reject