Towards graph-level anomaly detection via deep evolutionary mapping
Authors: Xiaoxiao Ma
Jian Yang
Jia Wu
Quan Z. Sheng
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph anomaly detection
anomaly detection
graph representation
deep learning
graph neural network

Abstract: Graph-level anomaly detection aims at depicting anomalous individual graphs in a graph set. Due to its significance in various real-world application fields, such as identifying rare molecules in chemistry and detecting potential frauds in online social networks, graph-level anomaly detection has received great attention. In distinction from node- and edge-level anomaly detection that is devoted to identifying anomalies on a single graph, graph-level anomaly detection faces more significant challenges because both the intra- and inter-graph structural and attribute patterns need to be taken into account to distinguish anomalies that exhibit deviating structures, rare attributes or the both. Although deep graph representation learning shows effectiveness in fusing high-level representations and capturing characters of individual graphs, most of the existing works are defective in graph-level anomaly detection because of their limited capability in exploring information across graphs, the imbalanced data distribution of anomalies, and low interpretability of the black-box graph neural networks (GNNs). To bridge these gaps, we propose a novel deep evolutionary graph mapping framework named GmapAD, which can adaptively map each graph into a new feature space based on its similarity to a set of representative nodes chosen from the graph set. By automatically adjusting the candidate nodes using a specially designed evolutionary algorithm, anomalies and normal graphs are mapped to separate areas in the new feature space where a clear boundary between them can be learned. The selected candidate nodes can therefore be regarded as a benchmark for explaining anomalies because anomalies are more dissimilar/similar to the benchmark than normal graphs. Through our extensive experiments on nine real-world datasets, we demonstrate that exploring both intra- and inter-graph structural and attribute information are critical to spot anomalous graphs, and our framework outperforms the state of the art on all datasets used in the experiments.

Under review as a conference paper at ICLR 2023
TOWARDS GRAPH-LEVEL ANOMALY DETECTION VIA DEEP EVOLUTIONARY MAPPING
Anonymous authors Paper under double-blind review
ABSTRACT
Graph-level anomaly detection aims at capturing anomalous individual graphs in graph set. Due to its significance in various real-world application fields, such as identifying rare molecules in chemistry and detecting potential frauds in online social networks, graph-level anomaly detection has received great attention. In distinction from node- and edge-level anomaly detection that is devoted to iden- tifying anomalies on a single graph, graph-level anomaly detection faces more significant challenges because both the intra- and inter-graph structural and at- tribute patterns need to be taken into account to distinguish anomalies that exhibit deviating structures, rare attributes or the both. Although deep graph represen- tation learning shows effectiveness in fusing high-level representations and cap- turing characters of individual graphs, most of the existing works are defective in graph-level anomaly detection because of their limited capability in explor- ing information across graphs, the imbalanced data distribution of anomalies, and low interpretability of the black-box graph neural networks (GNNs). To overcome these limitations, we propose novel deep evolutionary graph mapping framework named GmapAD, which can adaptively map each graph into a new feature space based on its similarity set of representative nodes chosen from the graph set. By automatically adjusting the candidate nodes using specially designed evolu- tionary algorithm, anomalies and normal graphs are mapped to separate areas the new feature space where clear boundary between them can be learned. The selected candidate nodes can therefore be regarded as a benehmark for explaining anomalies because anomalies normal graphs. Through our extensive experiments on nine real-world datasets, we demonstrate that exploring both intra- and inter-graph structural and attribute information are critical to spot anomalous graphs, and our framework outperforms the state of the art all datasets used in the experiments
more dissimilar/similar to the benchmark than
INTRODUCTION
Graph-level anomalies are abnormal or rare individual graphs in a graph set. These anomalies can be observed in various application fields, such brain disorders in brain networks/graphs, and frauds in online social networks (Noble & Cook 2003) Akoglu et al. 2015). Detecting this category of anomalies has shown great benefits in facilitating downstream anomaly handling process, alleviating anomalies' detrimental impact on society, and boosting real-world applications (c.g., health monitoring and drug discovery). However, graph-level anomaly detection differs significantly from node- and edge-level anomaly detection that investi- gates an individual graph. Graph-level anomaly detection targets anomalous individuals among various graphs. Not only the unique spatial structure and nodes/edges' attributes associated with each graph, but also the cross-graph structural and attribute patterns should be critically analyzed to identify these potential anomalies in the graph set (Ma et al. 202T).
molecules and abnormal proteins in biochemistry,
Recent studies in deep graph representation have put great effort into encoding both the com- plex graph structural information and attribute information into vectors and then conducting graph analysis within the representation space (Wu et al.) 2020). Although plenty of graph neural net- works (GNNs) have been developed to learn expressive node representations via message passing
'The code is available at hutp://gthhhbccmmm/mmppDDDCaaaan

---

Under review as a conference paper at ICLR 2023
Graph set
Node representation
Graph representation
Graph anomaly detection
Angmaly
GI
Read out
K
G2
G1
Anomalous graph
G2
Read out
Feature space!
G3
Normal graph
G3
Read out
Feature space
Message passing
Node representation
Graph representation
Figure 1: An overview of the learning feature space for graph-level anomaly detection. Fach graph's 's representation is extracted from its own nodes' representations generated by message passing GNNs. Anomalies are then identified in the feature space. In a better feature space for anomaly detection (Feature Space II), anomalies (G2) and normal graphs (91 and G3) should be well separated.
schema (Kipf & Welling 2017: Veličković et al. 2018 Hamilton et al. 2017) and to read out the
graph representation from nodes comprised in single graph (Baek et al. 2021 Xu et al. 2019 Gal- licchio & Micheli 2020a), there remain significant challenges to directly applying existing GNNs for graph-level anomaly detection. (1) Most importantly, simply reading out graph representations using its own nodes cannot explicitly and fully capture the inter-graph information. For example, G1, G2 and G3'' 's representations shown in Figure only maintain their intra- intra-graph information while the rich cross graph information is lost. This leads unsatisfactory detection results and motivates us to design special read out functions to capture intra- and inter-graph information.
(2) In the feature space, anomalies also expected to locate away from normal graphs such that clear boundary between them can be effectively learned such as Feature space II in Figure [ (3) Lastly, the graph representation or the read out function should be interpretable. Noting that human understandable insights on the detected anomalies are vital for anomaly handling in real applications, but GNNs have been criticized for their low interpretability (Yuan et al. 2022. Pang al. 2021).
To address the above mentioned challenges, in this work, we propose a novel graph mapping tech- nique learn effective representations for graph-level anomaly detection. Unlike the existing works that learn a graph's representation using its own nodes, our devised framework, Graph mapping Anomaly Detection (GmapAD), comprehensively explores both the complicated intra- and inter- graph structural and attribute information to map graphs into an interpretable latent space where anomalies and normal graphs are well separated. Specifically, GmapAD achieves a high degree of discriminativenes: between anomalies and normal graphs by considering all nodes in the graph set and maps each single graph into the designed representation space according to the similarity between the graph and nodes.
Moreover, we notice that applying a simple graph mapping is non-trivial due to the massive number of nodes in the graph set and some nodes might contain non-valuable (or misleading and de- fective) information for distinguishing anomalies, as validated in our experiment in Section [5.2] As result, we further consider the informativeness of each node and propose a differential evolution- ary algorithm to iteratively select the best-performing set of nodes for graph mapping. Eventually, anomalies and normal graphs are projected to different regions in the new feature space and can be distinguished effectively.
For validation, we conduct extensive experiments on nine real-world graph datasets by comparison with the state-of-the-arts using four commonly-use metrics, i.c., precision, recall, Fl-scores and AUC. We also analyze the challenges and show the effectiveness of GmapAD modules through additional ablation tests. The results demonstrate that our proposed framework is superior to the existing works. In a nutshell, the main contributions of this work are as follows:
To the best of our knowledge, this is the first graph-level anomaly detection framework that explores both the intra- and inter-graph information to find clues about anomalous graphs. The structural and attribute information/pattemn within single graphs and cross cross-graphs graphs can be effectively captured by our proposed GmapAD, which is also extendable to work jointly with the oftt--ofthh-art graph neural networks.
2

---

Under review as a conference paper at ICLR 2023
The graph mapping technique devised in this work is also explainable. Each graph's 's repre- sentation in the new feature space denotes its similarities with the most informative nodes chosen from the whole graph set, which is traceable, compared with black-box GNNs.
The experiments real-world datasets and ablation tests demonstrate the greater perfor- mance of GmapAD and validate our approach to the challenges.
2 RELATED WORK
Graph neural networks. To date, graph neural networks are generally implemented following the gressage-passinggg schema that aggregates neighborhoods' attributes for encoding the target node into vector representation. These advanced neural networks, including the popular GCN (Kipf) & Welling ) GAT (Veličković et al. 2018) and GIN (Xu et al.] 2019), have extensively ex- plored the complex correlation between the spatial structure and attributes of single graph and proposed different strategies to guide the information aggregation process. Although they have achieved promising results in various graph analysis tasks, such as link prediction (Wu et al. 2020) and node classification (Hamilton et al. 2017 Zhu el al., (02T), most existing works are limited to represent the whole graph using its own nodes through simple read out functions like mean or max pooling, resulting in sub-optimal solutions to graph-level tasks (Back et al.. 2021).
Graph-level anomaly detection. Graph-level anomaly detection is spot anomalous graphs in a graph set. Different from node- (Dou et al. 2020; Tang et al. [2022] (Bandyopadhyay et al., 2020) and edge-level (Yu et al., 2018: Duan et al., 2020) anomaly detection on a single graph, one should con- sider the complex structural and attribute information of each single graph (i.e., intra-graph informa- tion) as well as the gross-graph patterns graph information) for finding clues about graph-level anomalies. Thanks to the advancement of graph neural networks, recent graph-level anomaly detec- tion techniques, such as OCGIN (Zhao & Akoglu 202I) and OCGLT (Qiu et al. 2022). have ap- plied GNNs to encode the intra- garragggpphhaaa information into a vector and transferred graph-level anomaly detection to a conventional outlying data point detection problem in the representation space (Ma) al.] 2021 Pang et al. 2021). Although these straightforward methods are convenient apply, their capabilities in fusing the affluent inter-graph information is very limited and huge research gaps remain in this field. Nevertheless, these black-box GNN based methods are also criticized because they cannot provide human- uanaaan-nndsttadaablle explanations to the learned representations and detected anomalies (Yuan al., 2022).
Differential evolutionary algorithm. Differential evolution is a widely-used algorithm for finding optimal solutions to specific tasks based on random search (Storn & Price 1997 Wu & Cai 2014 4).
Instead of performing brute-force search on all potential candidates, differential evolution algorithm
adopts specially designed objective functions to guide the searching direction with guaranteed con- vergence (Hu al.] 2013 Vesterstrom & Thomsen 2004 Rudolph] 1994). The key idea behind this algorithm is to simulate the natural evolution process, in which only the best candidates are retained while other candidates
updated through three operators: crossover, mutation and selection. Due to space limitation, we suggest interested readers to start with prior works like Ilonen et al.] (2003); Zhang al. (016)) and Qin et al. (2008) to better understand the evolutionary algorithm.
PRELIMINARIES AND PROBLEM DEFINITION
In this section, we provide the definitions of all related concepts used in the rest of the paper and the problem formulation of graph-level anomaly detection.
Definition Graph Sei and Node Set. Let G = (GI, GC,,,,,... G..) be a graph set containing n individual attributed graphs and all nodes in the graph set form a node set V = U,VB where V, contains nodes an individual graph G, = (A,, X;) whose structure and node attributes are represented by the adjacency matrix A, E {0, 13 and attribute matrix X,, respectively.
Definition 2. Candidate and Candidate Pool. We use candidate C; 3 Uj U/ V to specifically denote a subset of nodes chosen from V, and a candidate pool contains p candidates, denoted as C = (C1, Cz...., Cp). The candidates and candidate pool are utilized to map individual graphs to new feature spaces. They are two key components of the differential evolutionary algorithm, to be detailed in Section 4.22
3

---

Under review as a conference paper at ICLR 2023
Graph set
Anomaly-aware Node representation
Informative Node Selection
Initial Candidates
GI
G2
Most
Informative
Nodes
G3
Similarity Measurement
Graph Mapping
Candidute Optimization
Graph representation
Normal
Anomaly
Normal
Candidate
Cressover
G2
Feature Space
G3
Mutstarl
Graph
Cu
Optimal Feature Space
Representation
(
The GmapAD Framework. Given the graph set, @: GmapAD first encodes intra-gr thira- information into anomaly-aware node representations. ④ The most informative nodes are then selected from the node set based on the similarity between graphs and all nodes in the graph set. C) Initial candidates are chosen from the most informative nodes for graph mapping in step @. Based on the DE objective, candidates the optimal feature space using the optimized candidate and anomalies are detected through @ In D. the a graph is similar node in the candidate, the area covered by the node color in the corresponding dimension.
Figure 2:
optimized through @. Finally, each graph is mapped to
Definition 3. Graph Mapping. Given candidate Cm in C, graph mapping transforms each graph Ga into a new instance hg. in the feature space. hW: (s(G,, )..)..... s(G,, ")E_,.)): where s(),, u denotes the similarity score of graph Gú and the kth node of in C.. We use hy to specifically denote graph G,' 's representation in the feature space that is built based C.m.
Problem Definition. Graph-level anomaly detection defined to identify anomalous individual graphs in the given graph set G. In this work, we learn graph representations in semi-supervised manner. By this, the graph-level anomaly detection problem can be further defined as identifying anomalous graphs G; using small portion of graph labels y; {0, 1), where indicates that the graph is an anomaly.
4 GRAPH MAPPING ANOMALY DETECTION
In this section, we present the technical details of GmapAD, including anomaly-aware node repre- sentation learning in Section 4.1 graph mapping in Section 4.2.1 followed by the details of infor- mative node selection and evolutionary candidate pool optimization in Section and graph-level
anomaly detection in Section 4.3
4.1 ANOMALY-AWARD NODE REPRESENTATION
The spatial graph structure and node attributes encapsulate affluent information for identifying different classes of graphs. Although conventional message-passing graph neural networks have achieved success in encoding the intra-graph information into vector representation for facilitating node-level and graph-level analysis, they usually exhibit defective anomaly detection performance, especially on graph-level anomaly detection (Zhao & Akoglu 2021; Ma et al.) [021] Qiu et al.) 2022]. One major reason the extreme rarity anomalies in the graph set since anomalies only take very small proportion of the graph set (Noble & Cook 2003 Akoglu et al. 2015). To learn more effective node and graph representations that better support graph-level anomaly detection, we first attempt to handle the imbalanced data distribution and learn anomaly- aware node representa- tions such that the read out graph representations are distinguishable for anomaly detection.
For simplicity and extensibility. GmapAD employs the conventional message-passing based GNN (e.g., GCN, GAT) for learning node representations 2G.. G..l in Gi each training iteration by ag-

---

Under review as a conference paper at ICLR 2023
gregating node k's neighborhood information via 2k
G.. Agg(a 2
E)ENo, (R) 852,
where Agg(-) is an aggregation function, such as sum or node pair-wise attentions. or and B3 con- trol the weights of 2k G and 2 20: for learning G respectively. Ng, (k) denotes the neighbors G..0 is node k's attribute vector, a row vector in X;- of l in graph G. and =
To ensure the learned node representations can preserve valuable intra-graph information for anomaly detection, we apply an anomaly-aware objective function to train the GNN by follow- ing Zhang et al. (202I). Specifically, given each individual training graph G; and its label yo the representation of each node within the graph is learned via minimizing:
J
Σ Cl
G... mk
W), vil
Σ C
Cloí
Σ kEC,
9, 2B
w). (1)
G.EG
kEB:
where G1 and Go contain normal and anomalous training graphs, respectively. 9, E G y; otherwise 9j E Go. Φ(-) predicts the probabilities of each graph G; to be normal and anoma- lous. C(-) measures the cross-entropy loss between the predicted graph labels and the ground truth. This class-wise training objective adaptively balances the weights of normal and anomalous training graphs for capturing the patterns of nodes within them.
4.2 GRAPH REPRESENTATION VIA DIFFERENTIAL EVOLUTIONARY GRAPH MAPPING
While the prior detailed node representation learning is capable to generate graph representations through special designed read out functions, such approaches are limited to extracting graph repre- sentations only considering intra-graph information, which inherently ignores valuable cross cross-graph information the whole graph set and leads to sub-optimal solutions. Nevertheless, directly reading an individual graph's 's representation from node representations generated by graph neural networks also encounters severe low interpretability due to the black-box GNNs.
Driven by existing works in multi-instance learning and the feature mapping criteria between bags and instances (Wu et al. 20188; Zhang et al. 2016), we repurpose the mapping criteria for graph representation learning by exploring the correlation between a single graph and set of nodes. Specifically, given the generated anomaly-
node representations, we first select the most in- formative nodes in V as candidate, and then adopt a specially designed differential evolutionary algorithm (DE) to find the optimal graph mapping strategy for the eventual graph representation that will be used for distinguishing anomalies the graph set as illustrated in steps ( in Figure 2 We start with our proposed graph mapping method, followed by explanations on how we use DE to find the best performing candidate.
4.2.1 EXPLAINABLE GRAPH MAPPING
Graph mapping aims at encoding individual graph G. into new instance hm E R Cml in g, the new feature space given a set of nodes in candidate Cy- Notably, nodes in C. are col- lected from different graphs, as shown in Figure 2 Each dimension in the new feature hy (s(G,, of"),..., (G, v'C.))) denotes the proximity of graph G. and corresponding node v in Cm. For simplicity, in GmapAD, the similarity is measured as:
s(G,, = [V
Σ
G.d 2k
9m.
REG.
where zi. denotes the learned representation of node in graph G. while 2] 2gmm the represen- tation of node j. which belongs to candidate C. Through graph mapping, graphs can be clustered into different groups regarding their similarities to nodes in the candidate, which can be inherently utilized as a benchmark and normal graphs and anomalies will show divergent similarity patterns the candidate is carefully selected.
Compared to conventional GNN-based models that generate graph-level representations through black-box neural networks, this graph mapping process is traceable and explainable. The value of each dimension in the graph representation explicitly denotes the proximity between the graph and specific candidate node. Each candidate node, whilst, is ultimately selected from the graph set and can be traced back to its belonging graph, which is achieved by our specially designed DE algorithm detailed in the following section.
5

---

Under review as a conference paper at ICLR 2023
4.2.2 CANDIDATE SELECTION AND OPTIMIZATION
To facilitate better anomaly detection performance, anomalies and normal graphs are expected to lo- cate far away in the feature space so that their boundaries are clear and easy to identify (e.g.. Feature Space II in Figure TT. The chosen candidate for graph mapping is critical to gain such discrimina- tiveness and we achieve this by first selecting the most informative nodes from all normal graphs and then find the best candidate for graph mapping through a specially designed DE algorithm.
Informative node selection. Since normal graphs are the majority in the graph set, instead of using all nodes in the node set V for graph mapping, we only select the top k nodes that are most similar to normal graphs such that the computational and storage cost of graph mapping is minimized and the negative effect introduced by the curse of dimensionality (Bellman (966) can be alleviated. Practically, GmapAD selects the top k nodes from normal graphs based on the cosine similarity,
Mo. E.eo, h. A.. gm.
1ipa Eieo, h.. "11""-116mm.11 and for each node j. we take the sum of its similarity scores with all normal graphs as its final score. Eventually, the top k nodes with the highest scores become the initial candidate Cinit leveraged in the following DE algorithm.
which measures a node and normal graph Gi's similarity score as
Differential evolutionary candidate optimization. Given the initial candidate selected from the whole graph set, although each node in the candidate has high proximity to normal graphs, it is not guaranteed that conducting graph-node feature mapping using all of them will lead to the best detection performance (as validated in our ablation test in Section 5.2). Thus, we further establish a rule optimize the candidate that all normal graphs should be similar in the new feature space while normal graphs and anomalies are dissimilar. Accordingly, due to DE's guaranteed convergence (Hu al. 2013; Rudolph] 1994), we propose a novel objective function for guiding the DE algorithm and adaptively learn the best candidate Cop from different combinations of nodes in Cinse through mutation, crossover, and selection (as shown in @ in Figure D. More specifically, given a candidate Cm. our objective is to find the best diagonal node selection matrix Lop that maps graphs into a distinguishable space with the best anomaly detection performance, where diag (oo)) an indicator vector and diag( (Tp)e = 1 if te E Cap, otherwise O. We obtain Top following:
(1) Initialization. In this stage, we randomly initialize p different candidate selection matrices II" = [...... 19] for generating p divergent candidates that forms set C = [C), ..... Cp) Specifically, for candidate selection matrix 10, each entry e in its indicator vector d E 1) Cona is drawn from Bernoulli distribution d ~ B(p.). This intuitive binary selection process directly chooses nodes from the graph set and the selected node can be easily traced back to its belonging graph.
(2) Evaluation. Given the candidates in C² where 0 S t S et denotes the evolution iteration, we then map all graphs to p feature spaces following the graph mapping detailed in Section 4.2.1 using each candidate C; in C³ and apply binary SVM (Chang & Lin 2011) to classify graphs as anomalies or normal in each space. A performance score assigned each candidate according to the anomaly detection performance, which is quantified as:
score(C))
Σ GLE
ClVar Nan),
(3)
Gtrain
and
max((0 1 - Vou Úc.), yo. = max(O, (0, (g. )
L(ys. Do..)
(4)
yg. 0
where y% and iN are the ground truth and predicted label of a training graph Gs. respectively.
(3) Updating. Given the score of each candidate, we then generate an updated set of candidates C++1 based on C through mutation and crossover. In the mutation process, a new candidate prototype is created using candidate selection matrix I+ which is created as:
11 d 2
diag (1t1))
(5)
0, d <<2
where d = diag(T;))) p(diag 122) (iag(((s))))))) + (Ia4) + diag( (T;s)) fl is the predefined mutation rate, and r1, r2, r3, r4, and r5 are divergent integers randomly selected between [1,p) to

---

Under review as a conference paper at ICLR 2023
maintain the diversity of candidates, as specified in existing works (Ahmad et al. 2021: Deng al.
2021 Zhang et al. 2016). We set the threshold of as 2 to ensure d new)) has equal possibilities to be or 0 in setting μ 0.5, A binominal crossover is then applied to get the final candidate
selection matrix Mt-1 new as:
diag ne = diogf Ittt new)e: p(r) < CRor-=
(6)
ddagg T newwe: otherwise
where p(r) is random number drawn in range [0.1] following the uniform distribution, CR is predefined crossover rate, r is a random integer between [C]]C Once the new candidate is generated, we quantify its score following the prior evaluation step and replace less performing candidate Cj by C since score(C) < score(C)).
This evolutionary candidate optimization is applied to find the most supportive candidate within et iterations, Finally, Cop is chosen for mapping all graphs into a new feature space in which anomalies and normal graphs can be best separated. And, graph Gj's representation can be generated using Cop with candidate selection matrix Lop as the following:
hg. [s(Gs, of" diag((op)
s(9,, oi..p -diag( (op) Conl))
4.3 GRAPH-LEVEL ANOMALY DETECTION
After the last evolution iteration of DE, GmapAD eventually learns the best candidate and a SVM classifier for assigning graph labels. Given test graphs in the input set, the model maps each graph into the new feature space and labels them regarding their locations in the space.
EXPERIMENTS
For validating the performance and key modules of GmapAD, we 1) conduct extensive experiments for detecting anomalies on nine commonly used graph datasets by comparison with the state-of the arts, and 2) perform thorough ablation test on the devised model.
5.1
ANOMALY DETECTION PERFORMANCE
5.1.1 DATASETS
The nine benchmark datasets include two mostly-used brain networks datasets") fi.e., KKI and OHSU), and seven repurposed binary graph classification datasets published on sitę Specifically, AIDS, MUTAG, Mutagenicity, NCII and PROTEINS are collected from biochemistry while IMDB- BINARY and REDDIT-BINARY are from online social networks (Cai & Wang 2018 Wu et al.,
2018a Sa
Gallicchio & Micheli 2020b a)) The KKI and OHSU brain network datasets are constructed from the functional magnetic resonance image (fMRI) atlas of the whole brain for brain disorder analysis (Van Den Heuvel Pol. 2010 Pan et al. 2016: Hernández-Péree et al.) 2021), )). and since them directly without any further processing. For the 7 graph classification datasets, we follow previous works (Zhao & Akoglu [202]] and (Qiul al. 2022) and repurposed them for graph-level anomaly detection by downsampling the deviating
their labels indicate abnormal brain disorders,
class. The detailed descriptions and statistics of these datasets are given in Appendix A
5.1.2 BASELINES
We compare our devised framework GmapAD with six state-of the art GNN models, GCN (Kipf & Welling 2017), GAT (Velčkkvić et al. 2018), g- U-U-Nets (Gao & Ji. 2019), SAGPool (Lee et al.) 2019), DIFFPOOL (Ying al. 2018)) and GMT Baek et al. (2021). and two graph-level anomaly detection methods, OCGIN (Zhao & Akoglu 2021) and OCGTL QQu et al. (0222.. For a fair com- parison, we add the anomaly-aware loss function proposed in Section 4.1 to the six GNN models for reassigning them for graph anomaly detection and use GCN and GAT as the basis of GmapAD for graph mapping. g-U-Nets, SAGPool, DIFFPOOL and GMT adopt different pooling strategies
hhtp:///ghhbb.cmm///RAADDaaal datasets https:/cccmaamrssgiihhuuioaaaaa

---

Under review as a conference paper at ICLR 2023
Table I: Detection precision scores on nine datasets. (Best in bold)
Dataset
GCN
GAT
g-U-Nets
Difffool
SAGPool
GMT
OCGIN
OCGLT
GmmpAAD-GCN
GmupAD-GAT
KKI
0.53.0033
0.54...3
0.381002
0.46.0011
0.36:102
0.46.002
0.3020.2
0.4310.22
0.631003
0.6710.4
DHSU
0.58-003
0.55+0.2
0.51+0.3
0.48+02
046+002
043+02
0.57-0.1
0.64-1.2
0.59++..1
0.66+1L22
AIDS
0.97.0.1
0.9710.1
097.0..1
0.9710.1
0.9210.1
0.98.0.3
0.96.0.11
0.96.0.2
0.9810.1
0.9610.1
MUTAG
0.
0.7720.3
03820.1
0.752011
03022011
0.7920.1
0.9920.1
0.722:.11
0.93:0.3
0.542:122
Munaggnicitt
6.87+0.1
0.58+0.1
088+0.1
0.7+0.1
088+01
0.90-011
0.89-0.2
0.88+0.1
0,90+0.1
0.91+0..
NCII
0.85+0.3
0.87+0.2
039+0.1
0.1+011
091+01
0.1+001
0.90+0.1
0.92-0.1
0,933-022
0.93+LL3
PROTEINS
0.6710.1
0.85.0.2
087.103
0.7510.1
087.10
0.8810.1
0.8510.1
0.36.0.2
0.89.0.1
0.8110.2
INDE BINARY
0.9120.1
0.720033
09469.1
0300001
0.53:0.1
0.3320.1
0.858111
0.96::0.1
0.928011
REDDIT-RINARY
0.88+0.1
0.85+0.1
0.0+0.1
091401
0.93-0.2
0.83-0.1
0.50+0.1
0.93-0.1
0,91+0.1
and specially designed pooling layers for learning graph-level representations. Both baseline graph anomaly detection models, OCGIN and OCGLT, apply a one-class SVDD classifier to learn a hy- persphere using only normal graphs, and anomalies are distinguished those lying outside the hypersphere. Open-sourced implementations of these baselines are provided in Appendix B
5.1.3 EXPERIMENTAL SETTINGS
In our experiment, we denote GmapAD-GCN and GmapAD-GAT as variants of our model using GCN and GAT as basis, respectively. We use Adam (Kingma & Ba 2014) (learning rate is 0.005, weight decay is 0.0005) as the optimizer for fine-tuning GNN parameters. In GmapAD-GCN, we stack 2 GCN layers, while in GmapAD--GN GATT, we use GAT layers, each of which uses 8 heads. The dimensions of GNN layers are set to 128 and 64, respectively, and the dimension of W in Equation [ is 64. For the evolutionary graph-node feature mapping, we set k to 64 when selecting the top- most informative nodes and set the size of candidate pool to 30. For DE, we set the possibility p, of the Bernoulli distribution as 0.5, mutate rate as 0.5, crossover rate 0.9 and iterations for evolution as 2, 000 (following previous DE works (Zhang et al.) 2016 Wu & Cai 2014)). Each dataset is randomly shuffled and split for training, validation and test with ratios of 80%. 10%. and 10%. For the baselines, we use their published settings unless the parameters are specially identified in the original paper. All the experiments are conducted on a Rocky Linux 8.6 (Green Obsidian) server with a 12-core CPU, 1 Nvidia V100 GPU and 60Gb RAM. The average and standard deviation of 10-fold test results are reported. The additional parameter sensitivity test results are provided in Appendix D
5.1.4 RESULT ANALYSIS
From the results in Tables and 3 the two variants of GmapAD, namely GmapAD-GG and GmapAD-GAT, achieve better results compared to other baselines on all datasets regarding preci- sion, recall and Fl Fl-scores, because all baselines only consider intra-graph information for detecting anomalies in the graph set, which inherently indicates that one should explore the inter-graph in- formation more comprehensively for generating graph representations so that potential graph-level anomalies can be more effectively identified. The conventional GCN and GAT models we utilize for validation can also achieve comparative results to other fate-of-theeart detection when trained with the anomaly- loss detailed in Section 4.1] g- g-U-Nets, SAGPool, DIFFPOOL and GMT obtain the second- best results which can be attributed to their specially de- signed pooling methods for reading graph-level representations using nodes within the graph, while GmapAD explores the most informative nodes considering the whole graph set. We can also that there remain significant gaps to improve the detection performance on the two brain networks and the low results of all methods on them can be reasoned the relatively smaller size of datasets. Nevertheless, the higher recall scores of all methods compared to their precision and Fl-scores im- ply the methods can capture most of the true anomalies while the number of predicted false positives by different models is relatively high. Both problems can be future research in this direction. Due to space limitation, AUC results are reported in Appendix
graph-level anomaly
5.2 ABLATION TESTS
Apart from anomaly detection performance validation, we perform further ablation tests to validate our approach to the challenges pinpointed in Section Since GmapAD's 's training process comprises two main stages, i.e., anomaly-awee awwre node representation learning and evolutionary graph mapping, we report GNN basis' detection performance to show the effectiveness of the learned node represen- tations and then validate the differential evolutionary graph mapping method by conducting graph
8

---

Under review as a conference paper at ICLR 2023
Table 2: Detection recall scores on nine datasets. (Best in bold)
GAT
B-U-Nets
DirPPool
SAGPool
GMT
OCGIN
OCGLT
GmapAD-GGN
GaapAD-GAT
0.35+0.1
0.62-0.4
0.32+0.1
0.46+0.1
068+0.5
083+04
0.38+0.2
0.4+-0.2
0,80+004
OISU
0.70.00.2
0.4910.2
0.4510.4
0.89102
0.6510.2
0.8.104
0.57.0..1
0.22.0.2
0.22102
0.68.0022
AIDS
0.58-20.1
0.72+1.11
0.344022
055401
08240.
11::00
0.49-2011
0.9==0.1
059441.1
0.99:2:11
MUTAG
0.82:002
0.6::0.11
085100.1
0.001011
082:10
076:00
0.36:0.1
0.73:0.11
0:95
0.89::0.22
Munagemicaty
0.71=0.1
0.70+0.1
096+0.2
0.74+01
095++0.1
095+01
0.49-0.1
0.88+0.1
0.98-1.11
0.98+H01
NCII
0.75
0.78200.1
0.96.10.1
0,582011
0.95.0.11
0.98.0.11
0.48.10.1
0.9210.1
0.99.0.11
0.9910.11
PROTEINS
0.57=0.1
0.6+014
0.1+00.1
0.6++011
0.92+011
0,95=011
0.48=0.1
0.87=0.1
0.99:0.1
0.97+:122
IMDB- BINARY
0,70:0011
0.5510.3
0.9810.1
0.770011
0
0.95:0.1
0.98:0.1
0.8910.11
0.99:0.1
0.9410.1
REDDEF-BLARRY
0.8320.1
0.924011
0.78102
0.0840.1
09120.1
0.3450.1
0.45.0.1
0.392001
0.4400111
0.961011
Table 3: Detection F1 scores on nine datasets. (Best in bold)
Dataset
GCN
GAT
g-U-Nets
Difffool
SAGPool
GMT
OCGIN
OCGLT
GmmpADD-GCN
GmupAAD-GAT
KKI
0.35.20.2
0.56.20.3
0.341:0.1
0,46:0.1
0.36:10.3
0.58:10.3
0.38-10.2
0.43:0.22
0.713:03
0.7310.3
DHSU
0.59-002
0.51+08.2
0.36+00.3
0447002
0.51+022
0.51=0.3
0.57-0.1
061+002
0.68+6.77
0.63+8-22
AIDS
0.73-00.1
0.3++0.1
083+0.11
0.8++01
0.6420.1
LI++00
0.65-2011
0.66t.11
0.9+3.11
0.99::111
MUTAG
0.86:0011
0.751:0.1
08210..1
0.83.0.1
081:10.1
0.78:001
0.44:0.1
0.71::0.2
0.9610.3
0.86:10.1
Munagenicaty
0.8120.11
0.8720.1
092210.1
0.7240.1
09120.1
0.22:0.1
0.63:0.1
0.872:222
0.94::.11
0.942:0.1
NCTI
0.84-003
0.85+0.1
014+0.1
0.99+01
095++a1
0.94+011 1
0.63-6.1
0.92-6.1
0.9++0.2
0.97+4L2
PROTEINS
0.71100.1
0.3310..3
0.78.10.1
0,71
0.9210
0.9110.11
0.61.0.1
0.85.0.3
0.94.0.1
0.9510.2
IMDE BINARY
0.8120.1
0.36:012
099420.1
0.1
0.8:0.1
0.95:0.1
0.61-0.1
0.8720.2
0,5::0.1
0.942:111
REDDIT-RINARY
0.88-0.1
0.92+0.1
082++..1
0,93+0.1
0.93-0.2
0.58-0.11
0.58+0.1
094+0.1
0.95+0.1
mapping using all top-k informative nodes in the whole graph set without further optimization (de- noted as + Full mapping), followed by graph mapping using the best candidate selected through differential evolution (denoted as +DE).
Graph mapping performance. As illustrated Tables] 2 a GmapAD-GCN's supe-
Table 4: Ablation test (Best in bold).
Dutaset
Variunts
Fl-score
Precision
Recall
rior detection performance mainly comes from our proposed differential evolutionary graph mapping method, improved more than 10% and 2% on the GCN basis and full mapping, re- spectively, on the three datasets. By compar- ing GCN and full mapping, we find that the straightforward graph mapping using all top-k informative nodes cannot guarantee a satisfying detection performance. For example, GCN outper- forms full mapping regarding the precision and recall scores on KKI dataset. This is because some nodes might contain non- non-informative or even defective information that may blur the boundary be- tween anomalies and normal graphs, as prior mentioned Section 4.2.T
GCN
0,36=002
0.53-40.3
0.80
KKI
Full mapping
0.3-0033
0.40+0.5
0.74+00.4
DE
0.71-0.3
0.63+0.3
083+0.3
GCN
0.86-0.11
0.8310.2
082102
MUTAG
Full mapping DE
0.91-0.1
0.91:00.2
09120.3
0.96-0.3
0.9310.3
0,9100.3
GCN Pull mapping
0.81=0.1
0.87+0.1
0.710011
Mutagenielty
0.93-0.1
034+0.1
+ DE
0.94-0.1
0.90:001
0.9810.1
Differential evolutionary algorithm's performance. +DE's better performance over full mapping demonstrates that our devised DE algorithm can further improve the detection performance by iter- atively selecting the best candidate nodes for graph mapping while maintaining the traceability of graph mapping for representation explanation.
6 CONCLUSION
In this paper, we have devised a novel graph-level anomaly detection framework based on graph representations learned through deep evolutionary graph mapping. From our study, we pinpoint that investigating both the abundant inter- and intru-graph information in the graph set is mandatory for capturing the deviating patterns of anomalies, which however has not yet been sufficiently studied in existing works. To bridge the gap, our developed framework, GmapAD, first utilizes a GNN to encapsulate the spatial graph structure and attributes into node representations and then iteratively selects the best subset of informative nodes in the graph set for mapping graphs into the new feature space (according to the similarity between each graph and nodes in the subset). Eventually, anoma- lies and normal graphs will be mapped to the deviating locations in the feature space and thus can be classified effectively using conventional machine learning techniques such as SVM. The extensive experiments nine widely- used real-world datasets show that GmapAD outperforms the five state- th-thee-rt art baselines, and our approach to the challenges discussed early in the paper is validated through the additional ablation tests.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Mohamad Faiz Ahmad, Nor Ashidi Mat Isa, Wei Hong Lim, and Koon Meng Ang. Differential evolution: recent review based on state-of-the-art works. Alexandria Engineering Journal, 2021.
Leman Akoglu, Hanghang Tong. and Danai Koutra. Graph based anomaly detection and description: survey, Data Mining and Knowledge Discovery, 29(3):626 688, 2015.
Jinheon Baek, Minki Kang, and Sung Ju Hwang. Accurate learning of graph representations with graph multiset pooling. In International Conference on Learning Representationss 2021.
Sambaran Bandyopadhyay, Saley Vishal Vivek, and MN Murty. Outlier resistant unsupervised deep architectures for attributed network embedding. In Proceedings of the 13th International Confer- ence on Web Search and Data Mining, pp. 25-33, 2020.
Richard Bellman. Dynamic programming. Science, 153(3731):34-37, 1966.
Chen Cai and Yusu Wang. A simple yet effective baseline for non-attributed graph classification. arXiv preprint arXiv: 1811.03508, 2018
Chih Chun-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM Trans- actions on Intelligent Systems and Technology (TIST), 2(3):1227, 2011.
Wu Deng, Shifan Shang, Xing Cai, Huimin Zhao, Yingjie Song, and Junjie Xu. An improved differential evolution algorithm and its application in optimization problem. Soft Computing, 25 (7):5277-5298, 2021.
Yingtong Dou, Zhiwei Liu, Li Sun, Yutong Deng, Hao Peng, and Philip S Yu. Enhancing graph neural network-based fraud detectors against camouflaged fraudsters. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pp. 315-324, 2020.
Dongsheng Duan, Lingling Tong, Yangxi Li, Jie Lu, Lei Shi, and Cheng Zhang. Aane: Anomaly aware network embedding for anomalous link detection. In 2020 IEEE International Conference on Data Mining (ICDM), pp. 1002-1007. IEEE, 2020.
Claudio Gallicchio and Alessio Micheli. Fast and deep graph neural networks. Proceedings of the AAAI conference Artificial Intelligence, volume 34, pp. 3898-3905, 2020a.
Claudio Gallicchio and Alessio Micheli. Ring reservoir neural networks for graphs. In 2020 Inter- national Joint Conference on Neural Networks (IJCNN), pp. 1-7. IEEE, 2020b.
Hongyang Gao and Shuiwang Ji. Graph u-nets. In Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2083-2092. PMLR, 09-15 Jun 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems, 30, 2017.
Heivet Hernández-Peen Pééez,, Jason Mikiel-Hunter, David McAlpine, Sumitrajit Dhar, Sriram Boothalingam, Jessica JM Monaghan, and Catherine M McMahon. Understanding degraded speech leads to perceptual gating of a brainstem reflex in human listeners. PLoS Biology, 19(10):
e3001439, 2021.
Zhongbo Hu, Shengwu Xiong, Qinghua Su, and Xiaowei Zhang. Sufficient conditions for global convergence of differential evolution algorithm. Journal of Applied Mathematicx, 2013, 2013.
Jarmo Ilonen, Joni-Kristian Kamarainen, and Jouni Lampinen. Differential evolution training algo- rithm for feed-forward neural networks. Neural Processing Letters, 17(1)93-105, 2003.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1412,6640 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In International Conference on Learning Representations, 2017.
10

---

Under review as a conference paper at ICLR 2023
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. 17734-3743, PMLR, 09-15 Jun 2019.
Xiaoxiao Ma, Jia Wu, Shan Xue, Jian Yang, Chuan Zhou, Quan Z Sheng, Hui Xiong. and Leman Akoglu. A comprehensive survey graph anomaly detection with deep learning. IEEE Trans- actions on Knowledge and Data Engineering, 2021.
Caleb C Noble and Diane Cook. Graph-based anomaly detection. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 631- 636, 2003.
Shirui Pan, Jia Wu, Xingquan Zhu, Guodong Long, and Chengqi Zhang. Task sensitive feature exploration and learning for multitask graph classification. IEEE Transactions on Cybernetics, 47 (3):744-758, 2016.
Guansong Pang, Chunhua Shen, Longbing Cao, and Anton Van Den Hengel. Deep learning for anomaly detection: A review. ACM Computing Surveys (CSUR), 54(2):1-38, 2021.
A Kai Qin, Vicky Ling Huang, and Ponnuthurai N Suganthan. Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEETtransactions on Evolutionary Computation, 13(2):398-417, 2008.
Chen Qiu, Marius Kloft, Stephan Mandt, and Maja Rudolph. Raising the bar in graph-level anomaly detection. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelli- gence, IJCAI-22, pp. 2196-229100 2203. International Joint Conferences on Artificial Intelligence Orga- nization, 2022.
Günter Rudolph. Convergence analysis of canonical genetic algorithms. IEEE Transactions on Neuural Networks, 5(1):96-101.. 101, 1994.
Rainer Storn and Kenneth Price. Differential evolution-a a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4):341-35 1997.
Jianheng Tang, Jiajin Li, Ziqi Gao, and Jia Li. Rethinking graph neural networks for anomaly detection. In International Conference on Machine Learning, 2022.
Martijn P Van Den Heuvel and Hilleke E Hulshoff Pol. Exploring the brain network: a review on resting-state fmri functional connectivity. European Neurosschhophamaccooeyy 2098):519-534, 2010.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2018.
Jakob Vesterstrom and Rene Thomsen. A comparative study of differential evolution, particle swarm optimization, and evolutionary algorithms on numerical benchmark problems. In Proceedings of the 2004 Congress on Evolutionary Computation, volume 2, pp. 1980-1987. IEEE, 2004.
Bo Wu, Yang Liu, Bo Lang, and Lei Huang. Dgenn: Disordered graph convolutional neural network based the gaussian mixture model. Neurocomputing, 321:346-355 356, 2018a.
Jia Wu and Zhihua Cai. A naive bayes probability estimation model based on self-adaptive differ- ential evolution. Journal of Intelligent Information Systems, 42(3):671166) 2014.
Jia Wu, Shirui Pan, Xingquan Zhu, Chengqi Zhang, and Xindong Wu. Multi-instance learning with discriminative bag mapping. IEEE Transactions Knowledge and Data Engineering, 30(6): 1085-1080, 2018b.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4-24 2020.
11

---

Under review as a conference paper at ICLR 2023
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? International Conference on Learning Representations. 2019.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hier- archical graph representation learning with differentiable pooling, Advances in neural information processing systems, 31, 2018.
Wenchao Yu, Wei Cheng, Charu C Aggarwal, Kai Zhang, Haifeng Chen, and Wei Wang. Netwalk: A flexible deep embedding approach for anomaly detection dynamic networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2672-2681, 2018.
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Ge Zhang, Jia Wu, Jian Yang, Amin Beheshti, Shan Xue, Chuan Zhou, and Quan Z Sheng. Fraudre: fraud detection dual-resistant to graph inconsistency and imbalance. In 2021 IEEE International Conference on Data Mining (ICDM), pp. 867-876. IEEE, 2021.
Yongshan Zhang, Jia Wu, Chuan Zhou, Peng Zhang, and Zhihua Cai. Multiple-instance learning with evolutionary instance selection. In International Conference Database Systems for Ad- vanced Applicationn pp. 229-241. Springer, 2016.
Lingxiao Zhao and Leman Akoglu. On using classification datasets to evaluate graph outlier detec- tion: Peculiar observations and new insights. Big Data, 2021.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In Proceedings of the Web Conference 2021, pp. 2069-2262 2080, 2021.
12

---

Under review as a conference paper at ICLR 2023
A DOWNSAMPLED DATASET DESCRIPTION
Statistics of the nine raw datasets, including the number of graphs in each class, the average num- ber of nodes and edges are given Table 5 For the KKI and OHSU datasets, Go denotes brain networks/graphs with disorders while G1 denotes the normal class. For the rest seven datasets, we follow previous works in Zhao Akoglu (202T): [Qiu al. (2022) and downsample Go as anomalies (only 10% data samples are kept). The meanings of Go and G) are also summarized in Table
Table 5: Dataset statistics
Dataset
OHSU
AIDS
MUTAG
Mutagrnieity
PROTEINS
IMD8
9r
56
9o
9.
9.
5.
91
37
35
400
63
1936
500
1000)
1000
641.3
2180
2574
4003
800
1936
14719
319T
B BASELINE IMPLEMENTATIONS
In our experiment, we strictly follow the official implementations of the baselines and their corre-
sponding code repository are as follows:
g g-U-Nets.
SAGPool. httD:://gthhu..co////yeeee/////2
GMT. htMppppss///shaec.cccc////hlooas
OCGIN. http://ss.gggggee.oo/////a/aaaaa
OCGLT. hCC.://hwe/gg.a...oooooeeeeeeeea SoomalyDeeectiii
C ADDITIONAL EXPERIMENTAL RESULTS
We provide experimental results regarding the ROC-AUC score here. Specifically, as our proposed GmapAD learns an SVM classifier and directly assigns labels for graphs as anomalies or normal, use the distance between each graph representation and the margin learned by SVM as its score. As can be seen in Table GmapAD achieves the best performance in most cases.
D PARAMETER SENSITIVITY
GmapAD's main hyper- parameters are: 1) dimensions of the GNN layers, & value used for selecting the top-k most informative nodes in the graph set, and 3) mutation rate and crossover rate in the differential evolu- tionary algorithm. For validation purposes and because GmapAD two-staged, we test GmapAD's sensitivity to GNN parameters and & value separately. We set l as 64 when testing GNN dimen- sions' impacts. Similarly, we set the GNN dimensions as 128 and 64 when testing different & values. To be noticed, for the DE algorithm-related parameters, we follow previous works in Zhang et al. (016) and Wu & Cai (2014) since both rates have already been validated. All tests are conducted representative dataset MUTAG and GmapAD's detection performance regarding precision, recall and F1 scores are reported.
As detailed in Section and the experimental settings in Section 5.1.3
D.1 GNN PARAMETER SENSITIVITY
In this experiment, we use GCN as the basis GmapAD and conduct grid search on the dimen- sions of the two GCN layers, where each layer's dimension is set [32, 64, 128, 256). As can be seen from Figure 3 the settings GCN dimensions have little impact on GmapAD- DD--G'N's perfor- mance. This maybe because the graph mapping takes the similarities between graph and candidate
13

---

Under review as a conference paper at ICLR 2023
Table 6: Graph label description
Dataset
Class
Description
Go
Brain networks with attention deficit hyperactivity disorder
KKI
91
Health brain networks
Go
Brain networks with hyperactive-impulsive disorder
OHSU
G1
Health brain networks
Go
Chemical compounds inactive against HIV
AIDS
91
Chemical compounds active against HIV
Go
Nitroaromatic compounds mutagenicity on Salmonella typhimurium
MUTAG
91
Nitroaromatic compounds non-mutagenicity Salmonella typhimurium
Go
Chemical compounds categorized as mutagen drugs
Mutagenicity
G1
Chemical compounds categorized non-mutagen Enzymes proteins
9o
PROTEINS
G1
Non-enzymes proteins
9o
Chemical compounds active for non-small cell lung cancer
NCII
91
Chemical compounds inactive for non-small cell lung cancer
Go
Movie collaboration network extracted from romance movies
IMDB-BINARY
G1
Movie collaboration network extracted from action movies Discussion- communities extracted from Reddit
90
REDDIT-BINARY
91
Question/answer--bssed communities extracted from Reddit
Table 7: Detection AUC scores on nine datasets. (Best in bold)
Dataset
GCN
GAT
g-U-Nets
DifPoool
SAGPool
GMT
OCGIN
OCGLT
GmspAD-GGCN
GmapAD-GAT
KK1
0.52-0.1
0.4+0.22
0335+0.2
0.50+02
0.50+0.1
0.52+0
0.44-0.1
0.35+0.1
0.64-112
0.55+a
DISSU
0.62.10.2
0.5110..1
0.53.10.1
0,5910.
0.53.0.2
0,57.002
0.50.0.2
0/46.0.2
0.6900.2
0.6110.3
AIDS
0.6420.1
0.6el1.1
098280.1
09820.1
09330.1
0.98:0.1
03662011
05722.11
0.225:
MUTAG
0.54-0.1
0.50+0.1
076++0.1
0.7++0.1
0.3+00
0.72-0 1
0.63-0.4
0.66-0.1
0.79-0.1
0.73+0.22
Munagencctty
0.46-0.1
0.6+-0.1
068+0.1
0.62+011
0.6++0
0.69-8.1
0.47-0.1
0.55-6.1
0.69-0.1
0,67+0.
NCII
0.6210.11
0.6210.1
065.10.1
0.6610.1
0.6710.1
0.6610.1
0.3510.1
0.310..1
6.67.0.1
0.6110.1
0.65g0.1
0.1:0.1
0X350.1
0.8N:0.1
0.39:0.1
0.028111
6.84:4.11
0.792:12
IMDB- INDE-BINARY
0.67=0.1
0.69:0.1
07611.1
0.85:0
0.670033
6.8::0.1
081:10.1
DINARY
0.7510.1
0.7610.1
nodes for generating graph representations. Although the dimension of GNN varies, the similarities among graphs and the selected candidate nodes are rarely affected by
Precision
Recall
F1-score
1.
1.1
1.1
1.0
0.9
0.9
0.9
256
256
256
GNN dim1
128
0.8
GNN diml
128
0.8
GNN dim1
128
0.8
64
64
64
32256
128
GNN dim2
32 256
128
GNN dim2
32 256
128
GNN dim2
Figure 3: GNN parameter sensitivity.
14

---

Under review as a conference paper at ICLR 2023
Validation set
Testset
1.0
1.-
Score
0.8
Score
0.7
0.8
precision recall fl-score
precision
0.6
recall
fi-score
16
128
256
32
128
256
k
Figure 4: k value sensitivity.
D.2 A VALUE SENSITIVITY
The value of k determines the number of the most informative nodes for graph mapping and optimization. To validate k's impact on GmapAD, use GmapAD-GCN with fixed dimen- sions (128, 64) and report the detection performance on validation and test sets under settings k [8, 16, 32, 64, 128, 256] Figure
We can observe slight changes in the precision, recall and F1-scor under different k values. This implies GmapAD can eventually find the best candidate from the given graph set for graph mapping and the best & for MUTAG is 64. Meanwhile, since high value of k will result in high dimen- sional graph representations, which introduces more computation cost, balance between and the performance should be made when applied to real applications.
15


Reviews:
[{"review_id": "X0ayTiNCcwa", "reviewer": "Reviewer_H8Au", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. \nGraph-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. \nThis 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.\nTo 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. \nAs a result the authors claim to improve both explainability and model efficacy.", "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.\n\nI 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.\n\nAlso, 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?\n\nOn more question. Could the authors explain how the negative effect of the curse of dimensionality gets avoided during the informative node selection stage?\n", "strength_and_weaknesses": "This appears to be a well-researched paper. \nThe authors clearly defined the problem, motivated their solution and tested their approach \non nine benchmark datasets. They also performed ablation tests that really help illustrating the importance of each major step in their pipeline. \nIn the appending the authors discussed their parameter choices their made for DE algorithm,", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PiqLQSQNUZ", "reviewer": "Reviewer_eKPL", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.\n", "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.", "strength_and_weaknesses": "Strengths\n\n- The idea of node candidate optimization via differential evolutionary algorithm is interesting.\n\n- Experimental results show superior performances of GmapAD compared to existing GNN-based graph-level anomaly detection models.\n\nWeaknesses\n\n- 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.\n\n- 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.\n\n- The author stated that interpretability is an advantage of a framework that proposes interpretability, but there is no analysis of this. \n\n[1] Gao, Hongyang, and Shuiwang Ji. \"Graph u-nets.\" international conference on machine learning. PMLR, 2019.\n\n[2] Lee, Junhyun, Inyeop Lee, and Jaewoo Kang. \"Self-attention graph pooling.\" International conference on machine learning. PMLR, 2019.\n\n[3] Ying, Zhitao, et al. \"Hierarchical graph representation learning with differentiable pooling.\" Advances in neural information processing systems 31 (2018).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JgLv2RQDgI-", "reviewer": "Reviewer_BQDF", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "summary_of_the_review": "Some important points of the paper were not clearly explained. Currently, it is a borderline paper.", "strength_and_weaknesses": "Strengths:\n1. 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.\n2. The numerical outcomes are good, especially F1 score.\n3. The ablation test shows the differential evolutionary process is essential after selecting k informative nodes as candidates.\n\nWeakness:\n1. 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. \n2. 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. \n3. 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.\n4. 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.\n5. 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.\n6. 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.\n7. 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject