Dual-discriminative Graph Neural Network for Imbalanced Graph-level Anomaly Detection
Authors: Ge Zhang
Zhenyu Yang
Jia Wu
Jian Yang
Shan Xue
Hao Peng
Jianlin Su
Chuan Zhou
Quan Z. Sheng
Leman Akoglu
Charu C. Aggarwal
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph-level Anomaly Detection
Graph Neural Networks
Imbalanced Data

Abstract: Graph-level anomaly detection aims to distinguish anomalous graphs in a graph dataset from normal graphs. Anomalous graphs represent a very few but essential patterns in the real world. The anomalous property of a graph may be referable to its anomalous attributes of particular nodes and anomalous substructures that refer to a subset of nodes and edges in the graph. In addition, due to the imbalance nature of anomaly problem, anomalous information will be diluted by normal graphs with overwhelming quantities. Various anomaly notions in the attributes and/or substructures and the imbalance nature together make detecting anomalous graphs a non-trivial task. In this paper, we propose a graph neural network for graph-level anomaly detection, namely iGAD. Specifically, an anomalous graph attribute-aware graph convolution and an anomalous graph substructure-aware deep Random Walk Kernel (deep RWK) are welded into a graph neural network to achieve the dual-discriminative ability on anomalous attributes and substructures. Deep RWK in iGAD makes up for the deficiency of graph convolution in distinguishing structural information caused by the simple neighborhood aggregation mechanism. Further, we propose a Point Mutual Information (PMI)-based loss function to target the problems caused by imbalance distributions. PMI-based loss function enables iGAD to capture essential correlation between input graphs and their anomalous/normal properties. We evaluate iGAD on four real-world graph datasets. Extensive experiments demonstrate the superiority of iGAD on the graph-level anomaly detection task.

Dual-discrimnnative Graph Neural Network for Imbalanced Graph-level Anomaly Detection
Ge Zhang'
Zhenyu Yang'
Jia Wu²
Jian Yang'
Xue Shan
Hao Peng Jianlin Su
Chuan Zhou Quan Z. Sheng' Leman Akoglu Charu C. Aggarwal
Macquarie University University of Wollongong Beihang University
*Zhuiyi Technology AAMSS, Chinese Academy of Sciences
CCrnegie Mellon University 'IBM J. Watson Research Center mq. ew..mu..u.......... au, edu.. edu. au, sxue@uor. edu. au, penghao@buaa, edu. en, boj joojoe@ueezuui com, com, michael shenggmq. edu. au, lakoglu@andrew cmu edu, charu@us ibm com
zhang,, 2angy yang3)aatuueen {ji
zhouchuan@amse ac en,
Abstract
Graph-level anomaly detection aims to distinguish anomalous graphs in a graph dataset from normal graphs. Anomalous graphs represent very few but essential patterns in the real world. The anomalous property of a graph may be referable to its anomalous attributes of particular nodes and anomalous substructures that refer a subset of nodes and edges in the graph. In addition, due to the imbalance nature of anomaly problem, anomalous information will be diluted by normal graphs with overwhelming quantities. Various anomaly notions in the attributes and/or substructures and the imbalance nature together make detecting anomalous graphs non-trivial task. In this paper, we propose graph neural network for graph-level anomaly detection, namely iGAD. Specifically, an anomalous graph attribute-aware graph convolution and an anomalous graph substructure- Walk Kernel (deep RWK) are welded into a graph neural network to achieve the dual-discriminative ability on anomalous attributes and substructures, Deep RWK iGAD makes up for the deficiency graph convolution distinguishing structural information caused by the simple neighborhood aggregation mechanism. Further, we propose a Point Mutual Information (PMI)-based loss function to target the problems caused by imbalance distributions. PMI-based loss function enables iGAD to capture essential correlation between input graphs and their anomalous/normal properties. We evaluate iGAD four real-world graph datasets. Extensive experiments demonstrate the superiority iGAD on the graph-level anomaly detection task.
deep Random
Introduction
Graphs have been used as indispensable tool to describe relational data, such as chemical com- pounds, transport networks, and social networks. For instance, in a graph that models a chemical compound, nodes represent atoms and edges describe chemical bonds between atoms. Learning graphs to understand the world has been drawing considerable attention in recent years [5] 14 [5] 51
Given a graph dataset containing a set of graphs, graph-level anomaly detection aims to identify graphs with anomalous information. Generally, these anomalous graphs with special characteristics or functions are the minority in a graph dataset. For example, among all antibody molecules, only
*Corresponiing Author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

few of them exhibit anti-cancer activity on a specific type of cancer cell line [55]. Graph-level anomaly detection a research topic of great practical value, say, it can support cancer drug discovery by identifying molecules with anti-cancer activity from other antibody molecules [48] Also, the research can help to reveal pathogenic brain mechanisms by distinguishing the brain structures of patients with neurological disorders from healthy individuals 21
In practice, the attributes of partieular nodes are contributing factor to graph's anomalous properties. For example, the hydrogen and oxygen atoms at the end of molecules are the key to discriminating between Alcohol and Alkane 445. Graph substructures can be another factor for a graph's is anomalous properties. For instance, pharmacophores composed of some particular substructures can induce molecular toxicity. These graph attributes and substructures that are essential for distinguishing anomalous graphs from normal graphs are regarded as anomalous attributes and anomalous substructures, respectively. Most existing graph mining methods, especially those graph convolution- based models which have achieved state-of-the-art performance [54] [59] 30, focus on the aggregation of neighborhood-strruee information could be all possible substructures, In addition, anomalous attributes and substructures will be diluted by the information of normal graphs with overwhelming quantities, which is the imbalance nature of the anomaly problem. In summary, various anomaly notions in attributes and/or substructures and the imbalance nature make graph-level anomaly detection an important yet challenging problem.
information. However, the anomalous structure
In this paper, we propose a disermmiiiieeeeev graph neural network for imbalanced Graph-level Anomaly Detection (iGAD). Specifically, iGAD investigates a novel anomalous attribute-aware graph convolution. The final node representation the concatenation of the independent encoding on a node itself and the independent encoding on its neighborhoods from different hops. In this way, the attributes of center nodes can evolve independently over the graph convolution process and the anomalous attributes on particular nodes can get exposure. However, it is intractable to enable graph convolution to be aware anomalous substructures. Due to the high dependence on neighborhood aggregation, graph convolution can only capture very limited substructures in graphs. Moreover, even the simple substructures such as triangles, graph convolution cannot count them in a graph (3. RWK [47), as type of Graph Kernels (GKs), learns graphs by exploring common random walk sequences among all input graphs, which naturally involves the comparison about diverse substructures in different graphs. To embed the information of anomalous substructures into graph representations, we propose to compare random walk sequences of input graphs against anomalous substructures. By modeling anomalous substructures as parameters, they became learnable and can get updated through mack-propagation. We entitle this design anomalous substructure-aware deep RWK. In addition, we propose new loss function to target the imbalance distribution caused by the great difference in the number of normal and anomalous graphs. The newly proposed loss function models the PMI between graphs and their normal/anomalou properties and enables iGAD to capture anomalous information from an imbalanced graph dataset. Welding three designs mentioned above into graph neural network, the graph-level anomaly detection model iGAD is achieved. We conclude the contributions of iGAD as follows:
The anomalous attribute-aware graph convolution exposes anomalous attributes by keeping the independent evolution of center node's s attributes.
Anomalous substructures are modeled as learnable parameters. Substructure-awwer deep RWK embeds the information of anomalous substructures into graph representations by comparing the random walk sequences from input graphs and anomalous substructures.
The PMI-based loss function addresses issues brought by the imbalance nature of the anomaly problem and enables iGAD to learn anomalous graphs as a minority effectively.
Comprehensive experiments demonstrate the effectiveness of iGAD, which outperforms state-of the-trtttt- graph convolution- based graph classification models and graph-level anomaly detection algorithms on four real-world graph datasets. The code is available at httpss//gttbbbboooommmmm//ww//os
2 Related Work
Anomaly Detection. The task aims to identify anomalies that deviate from the majority of samples. Early anomaly detection algorithms use different metrics, such distance-based [18] and density-

---

based 17], to measure the deviation degree among samples to detect anomalies. For example, isolation forest-based algorithms [25] 26] identify anomalous by building the binary search tree structure to isolate samples. In addition, anomaly detection algorithms based on one-class classification [ and autoencoder 22 64 have also been the spotlight. For the graph-structured data, most graph anomaly detection algorithms dedicate to detect anomalies (e.g., anomalous nodes (88 and edges [36 (7]) in a single graph [.]
40 [3 37
44
13
The anomaly notions of graph-level anomalies are more diversified than those of node-level anomalies. For example, node-level anomaly detection methods usually regard nodes that betray network homophily" as anomalies [44]. However, at the graph level, nodes that can achieve an anomalous graph go far beyond the nodes that do not meet homophily. Node-level anomaly detection methods identify anomaly nodes from a micro perspective (e.g.. neighborhood structures) while identifying anomalous graphs needs learning graphs the macro level. Employing node-level anomaly detection methods to detect graph-level anomalies could capture some anomalies, but only small part. Moreover, graph-level anomaly detection algorithms need to consider anomaly notions related to graph substructures. Hence, it is necessary to propose anomaly detection methods that are specialized in detecting graph-level anomalies.
Graph-level Anomaly Detection. To the best of our knowledge, there are only several preliminary research on graph-level anomaly detection. Zhao et al. [62] investigate a research question of "should we use the data for the graph classification task to evaluate graph-level anomaly detection models?", followed by which two graph-level anomaly detection algorithms (27 35 combine Graph Neural Networks (GNNs) with knowledge distillation and one-class classification respectively to detect anomalous graphs.
Graph-level anomaly detection can be regarded as a special case of graph classification. There is a huge gap between the number of graphs belonging to the normal class versus the anomalous ones. But, graph classification algorithms usually assume that the number of graphs in each class is close. GKs [47 16 42 4T used to be the mainstream graph classification methods. Generally, GKs use the kernel function to calculate kernel values (i.e., similarityy between pair-wised graphs. Afterward, an off-the-shelf classifier is applied to the graph similarity matrix to perform the classification task. Graph classification algorithms based on GKs cannot learn graph representations explicitly and be optimized in an end-to-end fashion. In recent years, graph mining practitioners pay more attention to 38 GNNs with spatial graph convolution 200, 46 19] are summarized as message-
GNNs B,
56 52]. general, MPNNs update the representation of each node by iteratively aggregating information coming from their neighbors. To represent graph, MPNNs apply the readout function or pooling operation on node embeddings. The spatial graph convolution that mix the representation of nodes and their neighborhoods to represent nodes will smooth node attributes 61,44 4. In addition, [31] 28 60) proved that spatial graph convolution has limited power in distinguishing graph structures. Performing message passing between subgraphs can enable spatial graph convolution to capture more graph structural information. But such a solution exponentially consumes memory resources and computation complexities (3].
passing framework (MPNNs) 17 54
59
Graph classification methods mentioned above are likely to underfit anomalous graphs since they do not have any intrinsic mechanism to target the imbalanced distributions. In iGAD, novel loss is presented for the imbalanced distributions by modeling PMI. In addition, different from existing graph-level anomaly methods (62 27 35 that employ the off-the-shelff MPNNs (e.g.. GIN (54)) to represent graphs, iGAD can embed the information of anomalous attributes and substructures into graph representations.
Imbalanced Learning. Learning data with imbalanced distribution can be divided into data- and algorithm-lens level approaches. The former alleviates the imbalanced distribution of the original data by either under-sampling the majority [49 or over-sampling the minority 9 However, modifying the original distribution of data will bring a lot of drawbacks inevitably, such as over-fitting and discarding important samples. There are different types of approaches to address the issue the algorithm level. The typical approaches include employing post-hoc correction 300 aligning data distribution, [53]. and modifying the loss function [24 (2). In the real-world application, considering the different consequences of false-positive identification (e.g., predicting an inactive chemical compound to be
'I graph with high homophily, nodes tend to have the same label and similar features as their neighbors. Node-level anomaly detection methods focus on the neighborhood structure and usually identify the nodes which do not have the same label or similar features with most of their neighbors anomalies.
3

---

active) and false-new -elltive identification (e.g.. predicting a cancer patient as healthy individual), the situation will be more complicated [33]. In this paper, iGAD introduces PMI the cross-entropy loss function to solve this problem.
3 Preliminaries
Notations. graph dataset consisting of N graphs can be denoted as G [G1,..., G }. where G = [V, } is an unweighted and undirected graph in G. V; and E; are the node and the edge set, respectively. The topology of G, can be modeled as an adjacency matrix A, {0, 1) nxx,, where (M, v) = if there is an edge between nodes u and u, otherwise O. A; does not consider the self-loop, A,, u) = 0, Vu E V₁. We use Xx RR denote the attribute vector of node u E V, X, E _axe is the attribute matrix of G, G {V E can be regarded as substructure in G,, iff V S V; and Σ E, y is the label set of G. G2 is labeled by yı E {0, 1), where represents anomalous and 0 represents normal.
Problem Definition. This paper concentrates on the supervised graph-level anomaly detection problem. Given the training set == [G1 y1), (2). h. we aim to train a model to predict the normal/anomalous propricties of unseen graphs. T contains N1 anomalous graphs and Ng normal graphs (N1 No). The imbalanced ratio of T is defined (ó No-N,)
Spatial Graph Convolution. A graph convolution layer updates node representations by iteratively aggregating information coming from its one-hop neighborhood. The formulation is:
h (k+1) (u) = (CoMMIINE (h (u), AAGORnATE (*h (v), ((())))) , (u) = xx,, (1)
where S S K 1, (V)) denotes the 1-hop neighborhood of node u. f'AGRRECATE denotes how to aggregate neighbors of node u, and SCoMMINe defines how to combine the immediate representations of node u and its neighbors. a is the activation function. Generally, the final representation of node is (w).
Random Walk Kernels (RWK), RWK measures graph similarities by counting common random
walk sequences among graphs. There two graphs G1 {V1, E2 and G2 (V2, E2). Gx
{Vx, Ex } denotes the direct product graph about G and G2. where Vx = {(u, w') E Vi,u' E V2) and Ex {(u, u'), (v, o') (u,, v) Ei, (u', v') E2 Performing random walking on Gx is equivalent to doing random walking on G, and G2 simultaneously. The adjacency matrix of direct product graph Ax
be obtained by the Kronecker product operation @ on A₁ and A2, that is Ax = A1 X A2. The number of l-length common walk sequences between G1 and G2 is R (G, G2) = q (Ax) where Px and qx are the vector about the starting and stopping probabilities of random walks on Gx, respectively. The elements in Px and qx are all ones when there is no prior knowledge. Overall, the RWK about GJ and G2 can be defined as:
K(G1, G2) = Σ
k (GI,
E
4 iGAD
In this section, we will describe iGAD in detail (see Figure ffo an illustration). iGAD contains three key designs: (1) anomalous graph attribute-awar graph convolution; (2) anomalous substructure- aware deep RWK; and (3) PMI-based loss function. The first two designs encode the anomalous information graph attributes and substructures into graph embeddings. The loss function makes the training on iGAD not completely dominated by normal graphs.
4.1 iGAD: Anomalous Attribute-aware Graph Convolution
As aforementioned in Section I the attributes of particular nodes can achieve an anomalous graph. The graph convolution which iteratively updates node representations by performing feature trans- formation on the concatenated information about nodes and their neighborhoods will make node representations over-smoothed [61]. Under such graph convolution mechanism, only limited anoma- lous information can be manifest in corresponding node representations. We argue that making each

---

Graph Attribute-aware Graph Convolution (K=2)
PMI-based Loss Function
Conco oo Intttiooo
Prediction
Gj Normal Graph
e
G₁
snigewoor
BBI
Anomatous Attrbuut
Anomalous Substructuro-nae Deep RWK (M=2, L=d)
Bigs
Suherrantir
(G. SD)
Update
Updane
GN
Anomalous
Figure 1: Taking learning the graph Gr in a graph dataset as an example, we illustrate the framework of iGAD with three designs. I. Anomalous Attribute-aware Graph Convolution, which concatenates the independent encoding on nodes and their k-hop neighborhoods to represent nodes in G.v. To obtain the graph representation h readout function is applied to all node representations. II. Deep RWK, which performs random walks on two learnable
The Anomalous Substructure-awe anomalous substructures (i.e., S and S2) and the input graph Gvv simultaneously. Deep RWK obtains b based on kernel values 1e (G,, Sm). | {1..., L), m = {1...., M) III. The basebdsed Loss Function. iGAD concatenates CoNv and h to obtain the final graph representation hG Finally, a MLP is applied to bay to predict GN. The model training guided by PMI-based loss function.
node's attributes evolve independently over the graph convolution process critical for capturing anomalous attributes. To achieve it, anomalous attribute-award aware graph convolution concatenates the independent encoding on the node itself and the independent encoding on its k-hop neighborhood (1 < k < K) to represent each node in a graph. Formally,
(u), (u), h (K)(
h fCOMBINE
(3)
where h, is the final node representation of the node u, (u) is the representation of node u's k- hop neighborhood, and /COMRINE is the concatenation operation. h (n()))) and ((*) (u) are formulated
as:
h (w) MLP((x.,,
(4)
and
w())
=
(5)
respectively, where H X,, MI.P denotes multi-layer perceptron, a represents the activation function, and (kk) is the trainable weight matrix. To obtain the entire graph representation h we apply the permutation invariant Readout function R(-) on nodes the graph G, That is,
Cony
bg.
CONV
R ((h,l E V.)),,
where R(-) can be the sum-based or mean-based global pooling operation.
4.2 iGAD: Anomalous Substructure-aware Deep RWK
Generally, the neighborhood aggregation mechanism adopted by existing GNNs only depends on local neighborhood structures to perform message passing [60]), which leads to the deficiency of graph convolution in distinguishing substructures [O]. To make iGAD to be aware of anomalous substructures, resort to RWK that can explore diverse substructures through random walking sequences. There pioneering work [32] that represents graphs by calculating RWK values between input graphs and some substructures. It inspires to embed information about anomalous substructures into graph representations by performing random walks in input graphs and learnable anomalous substructures simultaneously.
present an anomalous substructure-aware deep RWK, which models elements the adjacency matrices of anomalous substructures learnable parameters. Supposed that {S SM } is the set
5

---

of M anomalous substructures, and the size of Sm is n'. Pm E F xn' is the adjacency matrix of S.. where the matric element Pm Pm(u' , v²) denotes the possibility that an edge exists between nodes
u' and in Sm. As the adjacency matrix is symmetric, Pm contains n (n 2 parameters. Referring to Eq. and supposing that the starting and the stopping possibilities each node are all ones, the number of 1-length common random walk sequences between the input graph G; and the anomalous substructure S. is:
x - & ΣE (Pm)) J'((A)))
where 1 E R"'n is column vector full of I, and E E [2"'X" is matrix in which all elements are 1. The proof of Eq. can be found in Appendix A.1. RWK with infinite random walk lengths will often meet the halting issue [33. Therefore, iGAD only considers the random walk length from 1 to L. As the size of anomalous substructures (n') is small, optimizing (P )m)) is not necessary. The adjacency matrix A, is sparse, and we compute (A,)' by the sparse matrix multiplication in PyTorch [34]. That where A is the sparse version of A, Afterward, deep RWK values ( (G,, Sm)) about G2 and Sm, fl.... M7.1 {I. L} will be assembled into a vector ag. That is,
(A (A(AA...AA(AA.)
aG, = (n (1,, xO (G, Sm)j...; (G,
(G,, St)..,,)), (G,, SM)).
(8)
KER based on deep RWK is: where ac, E RRML The graph representation h.
KER G = MLP((G.).
(9)
The final graph representation ba; for G G can be obtained by concatenating h and b together. The anomalous attribute-aware graph convolution and anomalous substructure-aware deep RWK are welded into a graph neural network together through hg.
4.3 iGAD: PMI-based Loss Function
The number of normal graphs much more than that of anomalous graphs. Under the imbalance nature of the anomaly problem, normal graphs will dominate model training. Targeting this issue, we propose a new loss function that can model the PMI between input graphs and their anomalous/normal properties. Specifically, we use f(; Q) to denote the proposed model iGAD, where θ represents model parameters. Modeling the PMI between the input graph G2 and its anomalous/normal properties can be formulated as:
fu. (G;; θ) log PG.... P(G.)P((s))
(10)
where the right part represents the PMI between G, and Ui, P(ys) is the proportion of anomalous graphs or normal graphs in the training set T. Compared with most existing loss functions, especially the loss function that models the conditional distribution about yi given G3 (i.e., Jy, (G +) Pe (yai G.)). PMI enables iGAD to give priority to learning the information that reveals the essential correlation between graphs and their labels. Eq. 10 can be reformatted
log (v. Gv, fy. (G,, θ) log P(y.).
(11)
After softmax normalization, the distribution of given G, is formulated as: (G, P().)
(Gt Ey, e/n, (Go P(y))
(12)
Incorporating (e) in to the framework of the cross-entropy loss function, obtain the PMI-based loss function L:
C
log Pe (..
(13)
T=1
Specifically, iGAD predict the graph G;;

---

Table 1: Statistical information of four real-world datasets. We regard the one-hot encoding of node labels (e.g., carbon (C), nitrogen (N), oxygen (O)) as node attributes.
DATASET AGRAPHS (N) #ANOMALOUS
AvG. #NODES
AVG, REDGES (AVG,
NODE LABBLS
TUMOR
MOLT-4
39,765
2,904
7.90%
26.07
28. 15
64
LEUKEMIA
MCF-7
27.770
2.293
8.26%
26.39
28.52
46
BREAST
PROSTATE
argmax fy. (G,; log P(n), during training.
V:
(14)
argmax fy. (G,; θ)
during testing.
y1
The reason that use argmax, f (G;; θ) to predict graph in test time can be found in Appendix A.2.
Many other loss functions target the difficulties brought by imbalanced distributions, such as the cost-sensitive loss function that assigns or learns different weights to the majority and minority samples [29 50 [2]. Compared with them, the PMI-based loss function does not introduce any new parameters that need to be carefully tuned. comes the form of the most widely used cross-entropy loss function and gives prediction results that achieve maximized PMI between inputs and predictions.
4.4 Algorithm Description & Computational Complexity
The pseudocode of iGAD is included in Algorithm in Appendix A.I. We divide graphs in 9 into different
to train iGAD 233 But for illustrating how iGAD predicts graph more clearly, the batch size is set as Algorithm 1. Given the training set, we initialize anomalous substructures and other parameters (Line in Algorithm 1) and calculate the proportion of normal and anomalous graphs (Line 2). For each graph, iGAD learns its graph representation (Lines 3 to 15). Based on the graph representation, MLP equipped with the PMI-based loss function gives predictions graphs (Lines 16 and 17). At the propppropngttion stage, anomalous substructures and other parameters will get updated. At each epoch, deep RWK performs random walking on input graphs and anomalous substructures that get updated during the previous epoch.
Lemma The computational complexity of iGAD is O(n + [ET,, where n and |E] are the number of nodes and edges, respectively. (The detailed analysis can be found Appendix A.3).
5 Experiments
In this section, conduct series of experiments study the performance of iGAD the graph- level anomaly detection task. Specifically, we investigate the following six questions:
QI. How about the performance of iGAD the graph-level anomaly detection task?
Q2. Does iGAD benefit from the PMI-based loss function?
Q3. How about the performance of the anomalous graph attribute-aware graph convolution in iGAD?
Q4. How about the performance of iGAD when it utilizes pre-defined anomalous substructures?
Q5. Can the anomalous substructure-awee deep RWK in iGAD learn anomalous substructures?
Q6. How does the maximum length of random walk sequences affect the performance iGAD?
The questions from Q2 to Q4 can be regarded as the ablation study our three main design elements, they are: (a). cross-entropy loss function versus the proposed PMI-based loss function; (b). general graph convolution versus the proposed graph convolution; (c). RWK versus the proposed deep RWK.
7

---

Table 2: Graph-level anomaly detection performance (%) of five graph classification methods, their GAD variants, iGAD, and iGAD's two variants on four datasets. The value behind + denotes the standard deviation (mean + std) over different data splits. The best result is highlighted in gray. The description about evaluation metrics AUC, Recall, Recall(A), and F-score is in Appendix B.
Doca
OCN
GCN-GAD
GIN
GIN-OAD
DOCNN
BOCNN-GAD SOPOCL
5OPoOL-GAD RWGNN
XWGNN-OAD
IQAD-1 IGAD-1
10AD
Aue
74.00a54
76.83151
7861azas
76.22220
79.36.124
75.51 Sos
76.99220
73.57
74924100
65.40
83.77am1
85.82aas
S4.520
RECALL
51.79
09651129
50621500
70.38111
5602
5601123
00977100
51.33o0T
68.32117
7800 79081121
79664.10
1.7rem
67 26
6111
67 Stree
63.82es
14 2er
71.M
F-scors
50 30.00
52.441133
58472543
35,002333
5K73
56.1
35
51.31a1
52,47x31
61
63.561154
63.861
Auc
72.55
75 15
76 M0
74. 10
T1. 11.00175
71.51ear
$1.50w.m
Mou74
REcaLL
51 25005
50877a0s
69.00a247
55.35mm
70.4
55 3531
51 31.02r4
76.331111
76.82
RS0411GA)
67.52esza
64.36ess
12.25
18 20.54ease
23.10022
F-scoun
50,53a10
$1.251130
55.43522
$3.86221
$1.33a120
56 1232
56.20.1
$6.023317
50.67.234
52,69220
12 22:0.
63.122121
63.30
Alic
15.96eax
18.24
16.20ans
RECALL
90.72a02
00461157
57.4344
71APA127
$2.88
12531149
56.78
71441125
51.02.155
69.90L174
78.3 16.3
(9.941064
79.59La4
Recati(A)
1.53a1
165tama 09.27035
700650
15,67
2/17:355
06/25300
75.35
75.0
P-rcous
17
63.0eam
Aue 77.00a10
73800059
75
75645217
71.25rr s
183 8330011
83.70aM
Mcr-3
RECALL 6L791234
69/4baaz
70.4euu
9677aas
RECALL(A)
294811844
11,07.20
09 00,37135
15
68,927720
4.971524
57.231111
67.67.254
71.99121 23.38LA3
F-scors
44 46760009
$337,139
38.73223 5659:170
55.74114
5480
51.00:33
56,060299
61.501100
637751.1
(4.77uam
5.1 Experimental Setup
Datasets. SW-610, MOLT-4, PC-3, and MCF-7 are four real-world graph datasets. These datasets are collected from PubChen which records a tremendous amount of chemical compounds and their anti-cancer activity testing results ("active" or "inactive") on different types of cancer cell lines. We regard the chemical compounds with the outcome "active" as anomalous, and "inactive" as normal. For example, the graph dataset SW-620 records 40,532 chemical formulas and their anti-cancer activity testing results on the colon cancer cell line. Chemical compounds that exhibit antibody activity against colon cancer are labeled as anomalous graphs, otherwise normal graphs. The statistical information about these four datasets is shown in Table
Baselines & Experimental Settings. To investigate Q1, we compare iGAD with the following baseline Readout function (abbreviated 54 These two algorithms employ spatial graph convolution learn node representation and apply the readout function to node representations to obtain graph representations and classify graphs; (2)
models: (1) GCN 20
Table 3: The performance (%) of two graph- level anomaly detection methods (i.e., GLo-
GCN) and GIN
calKD and OCGTL) and iGAD w.r.f AUC.
DATA
GLOCALKD
OCGTL
IGAD
Sw-620
64.14:1.92
67.691000
85.821069
DGCNN [59] and SOPool (52). In these two models, spatial graph convolution and the graph pooling opera- tion are employed to downsize graphs and complete the graph classification task; (3) RWGNN (32). It employs
MOLT-4
61.43+1.26
57.42+2388
+3.59+100
PC-3
64.79:1..2
68.42:1173
86.04:114
MCF-7
61.43+1.26
64.92+122
83.224064
random walk sequences to represent graphs and then classify graphs based on graph representations. All the above baselines are supervised and use the cross-entropy loss function; (4) The graph-level anomaly detection methods GLo 27 and OCGTL 35 The former adopts random distillation to detect the locally- and tion and graph transformation learning to identify anomalous graphs. Both of them only use normal graphs to train models. They learn anomaly scores for graphs to measure each graph' anomaly degree and do not provide any criterion to determine whether graph is anomalous or not.
graphs and the latter combines the one-class classifica-
For the fairness of experiments and to answer Q2, we also compare iGAD with GCN-GAD, GIN- GAD, DGCNN-GAD, SOPool-GAD and RWGNN-GAD These algorithms are the graph anomaly detection (GAD) variants of GCN, GIN, DGCNN, SOPool, and RWGNN. We replace the cross- entropy loss in these algorithms with the proposed PMI-based loss function. To answer Q3, we consider a variant of iGAD -GADD1 that only utilizes the anomalous graph attribute-wware graph convolution to represent graphs and detect anomalous graphs. To answer Q4, we consider the other variant named iGAD-2 in which the random walking performs on input graphs and pre-defined anomalous graph substructures simultaneously. Specifically, we use 3-star, triangle, tailed triangle,
fatps://pubchemmnccbii wwtp://ww....mmmminn......e www.:nnn....iiii....mmm nig.oo
8

---

SW 620 ('-8)
MOLT-4 (M=5. n'
PCB (M+5, n'=B)
MCF-7 (M+5, n'=8)
Mean
Mean
Mean
Mean
0.71
0.71
0.72
0.71
F-ccore
0.69
F-coure
F-score
F-ccore
0.69
0.68
0.67
5
maximum random longth
maximum random longth
maximum random longth
maximum random longth
(M=5.n' n'000
(M-5, n'-10)
(Y-0)
n'=10)
0.72
Mean
0.72
Mean
Mean
Mean
STD
STD
0.72
STD
STD
0.70
F-50re
0.60
F-SCOPe
0.68
F-scoe
0.68
F-ccre
0.66
0.66
0.66
0.67
0.64
0.65
0.62
5
9
10
0.62
4
5
10
0.62
5
6
10
0.63
5
6
10
maximum fandom walk length maximum fandom walk length
maximum random walk length
maximum random walk langth
Figure 3: The impact of different maximum random walk length on the performance of iGAD. The first row reports the performance of iGAD under the setting M=5 and n'=8. The second row reports performance of iGAD under the setting M=5 and n/=10.
and 4-cycle graphlets as pre-defined graph anomalous substructures (see Figure 4 in Appendix B for these substructures). Information about parameter setting and algorithm implementation can be found in Appendix B.1. We report experimental results under 5-fold cross-validation.
5.2 Experimental Results
This section answers Q1 Q6 by Al - A6, respectively. We put extra experiments in Appendix B.2.
MCF-7
PC-3
A1. iGAD demonstrates superior performance in identify- ing graph-level anomalies. Observed from Table 2 1) Com- pared with the graph classification baselines GCN, GIN, DGCNN, SOPool, and RWGNN, iGAD demonstrates sig- nificant advantages on four real world datasets in terms all evaluation metrics; 2) iGAD also beats the above base- lines' GAD variants, GCN-GAD, GIN-GAD, DGCNN- GAD, SOPool- GADD, and RWGNN-GAD in terms of all evaluation metrics. addition, as shown in Table iGAD outperforms two graph-level anomaly detection methods GLocalKD and OCGTL concerning AUC.
MOLT-4
SW-420
A2. PMI-based loss function can capture essential corre- lations between graphs and their anomalous/normal pro- prieties even if the data distribution is imbalanced. As shown in Table 2 compared with GNNs with the cross- entropy loss function (GCN, GIN, DGCNN, SOPOOL and RWGNN), their GAD variants equipped with the newly proposed PMI-based loss function (GCN-GAD, GIN-GAD, DGCNN-GAD, SOPOOL-GAD. and RWGNN-GAD) witness a significant performance improvement regarding Recall and Recall(A) over all datasets. For example, the value of Recall and Recall(A) achieved by DGCNN over the dataset SW-620 are 56,02+1.1 is and 12.74 respectively. In contrast, 72.65 and 67. 84 are reported by DGCNN-GAD, PMI-based loss function greatly improve GNN-based based graph classification model datasets with highly imbalanced class distributions.
Figure 2:
The anomalous substructures learned by iGAD under the experimental setting M=1, n'=10, L=5. We only draw the edge (u', x') with the leamed weight Pmm (u', over 0.5. 0.5.
A3. The anomalous attribute-waar graph convolution can embed anomalous attributes into graph rep- resentations and improve graph-level anomaly detection. shown in outperforms all baseline algorithms four graph datasets in terms of AUC, Recall, and F-score.
Table 2 iGAD-1 significantly

---

Concerning Recall(A), on the dataset MCF-7, iGAD-1 has little performance degradation compared with DGCNN-GAD. Specifically, DGCNN-GAR achieves 69.37=3305 on MCF-7, while iGAD-1 gets 25. But iGAD-1 beats DGCNN-GAD on other datasets in terms of Recall(A).
A4. iGAD is also effective when it is equipped with pre-defined anomalous substructures. As shown in T iGAD-2 demonstrates significant advantages against all baseline models. Moreover, iGAD- 2 also beats iGAD-1 concerning all metrics over datasets MOLT-4, PC-3, and MCF-7. iGAD-2 does not outperform than iGAD on all datasets concerning AUC, Recall(A), and F-score. But, on PC-3 and MCF-7, iGAD-2 has a slight lead over iGAD regarding Recall. The experiment results demonstrate that, in most cases, the performance of iGAD equipped with deep RWK is better than iGAD-2 using pre-defined anomalous substructures and algorithms that do not consider anomalous substructures. Based on the above analysis, we can conclude that comparing the random walk sequences between the input graph and pre-defined substructure can improve graph-level anomaly detection to a certain extent, but the algorithm that can automatically learn the anomalous substructures is better.
A5. The anomalous substructures learned by iGAD are demonstrated in Figure 2 anomalous graph substructures on four datasets are composed of the triangle, the tailed triangle, and the 4-cycle graphlets. It explains why iGAD-2 can achieve competitive results compared with iGAD (as shown in T and A4). We can draw preliminary conclusion that the graph substructures having the triangle, the tailed triangle, and the 4-cycle graphlets are important for distinguishing anomalous graphs from normal graphs on these four graph datasets.
We can observe that
A6. The performance of iGAD under different maximum random walk lengths L is shown in Figure 3 Under the setting that iGAD with 5 anomalous substructures and each of substructures has 8 nodes, on these four graph datasets SW-620, MOLT-4, PC-3, and MCF-7, iGAD can achieve the highest F-score value when the maximum random walk length ranges from 4 to 8. In addition, when each anomalous substructure contains 10 nodes, iGAD can reach the best F-score score the maximum random walk length from 5 to 9. The results verify that appropriately increasing the maximum length of random walking can improve the performance of iGAD since more much longer random walk sequences can capture more graph structure information.
Finally, we discuss the limitations of the proposed graph-level anomaly detection model iGAD. In practice, the nodes and/or substructures at a particular position in a graph can also be the reason for the graph's 's anomalous properties. For example, Alcohol compound can be obtained by replacing the hydrogen atom at the end of the Alkane compound with a hydroxy group (i.e., -OH). But, iGAD cannot capture the position information of nodes and substructures in graphs. In addition, iGAD is a supervised algorithm. It may not be able to achieve superior performance in identifying the graph-level anomalies that follow the anomaly distributions that have never been exposed in the training graph anomalies. In the future, we will propose specific solutions to this problem.
6 Conclusion
This paper proposes method named iGAD for graph-level anomaly detection. We highlight the challenges brought by imbalanced distributions and various anomaly notions in graph attributes and substructures. In addition, the significant differences between detecting anomalous graphs in graph dataset and identifying anomalous nodes in single graph are also introduced in detail. iGAD treats graph-level anomaly detection as a special case of graph classification and learns binary labels for graphs. In iGAD, the anomalous attribute-aware graph convolution and anomalous substructure-awer deep RWK embed graph-level anomaly information into graph representations. A PMI-based loss function guides iGAD identify anomalous samples from large number of normal samples. We do extensive experiments on four real-world graph datasets, and iGAD achieves superior performance on the geeph anomaly detection task.
Acknowledge
We greatly appreciate the constructive and insightful comments from reviewers. This work is funded by the Australian Research Council Discovery Early Career Researcher Award (ARC DECRA) Project (No. DE200100964) and the NSFC (No. 61872360).
10

---

References
[1] Leman Akoglu, Hanghang Tong, and Danai Koutra. Graph based anomaly detection and description: survey, Data Min Knowl Discov, 29(3):626-688 2015.
[2] Jinwon An and Sungzoon Cho. Variational autoencoder based anomaly detection using reconstruction probability, Special Lecture on IE, 2(1)11188, 2015.
[3] Muhammet Balcilar, Pierre Héroux, Benoit Gauzere, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In ICML, pages 599-608, 2021.
[4] Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Séhastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in spectral perspective. ICLR, 2021.
[5] John Adrian Bondy, Uppaluri Siva Ramachandra Murty, al. J. Graph Theory Appl., volume 290. Macmillan London, 1976.
[6] Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-path kernels on graphs. In ICDM, pages 74-81. IEEE, 2005.
[7] Markus M Breunig, Hans-Peter Kriegel, Raymond T Ng, and Jörg Sander. Lof: identifying density-hased local outliers. In SIGMOD, pages 93-104, 2000.
[8] Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv: 1312.623,, 2013.
[9] Jonathon Byrd and Zachary Lipton. What is the effect of importance weighting in deep learning? In ICMI., pages 872-881, 2019.
[10] Pim de Haan, Taco S Cohen, and Max Welling. Natural graph networks. In NeurlPS, pages 3636-3646, 2020.
[11] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In NeurlPS, pages 3837-384S, 2016.
[12] Jacek P Dmochowski, Paul Sajda, and I Lucas C Parra. Maximum likelihond in cost-sensitive learning: Model specification, approximations, and upper bounds. Mach. Learn. Res., 11((2), 2010.
[13] 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 CIKM, pages 315-324, 2020.
[14] David Duvenaud, Dougal Maclaurin, Jorge Aguilera-lparrauurre, et al. Convolutional networks graphs for learning molecular fingerprints. In NeurIPS, pages 2224-2232, 2015.
[15] Alex Fout, Jonathon Byrd, Basir Shariat, et al. Protein interface prediction using graph convolutional networks. In NeurlPS, pages 6530-6539, 2017.
[16] Thomas Gärtner, Peter Flach, and Stefan Wrobel. On graph kernels: Hardness results and efficient alternatives. In Learning theory and kernel machines, pages 129-143. Springer, 2003.
[17] Justin Gilmer, Samuel S Schoenholz. Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In ICML, pages 1263-1272, 2017.
[18] Markus Goldstein and Seichh Uchida. A comparative evaluation of unsupervised anomaly detection algorithms for multivariate data. PloS one, 11(4))o152173, 2016.
[19] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs In NeurIPS, pages
2017.
[20] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[21] Tommaso Lanciano, Francesco Bonchi, and Aristides Gionis. Explainable classification of brain networks via contrast subgraphs. In KDD, pages 3308 3318, 2020.
[22] Buyu Li, Yu Liu, and Xiaogang Wang. Gradient harmonized single-stage detector. In AAAI, pages 2019.
[23] Mu Li, Tong Zhang, Yugiang Chen, and Alexander J Smola. Efficient mini batch training for stochastic optimization. In KDD, pages 661-670, 2014.

---

[24] Tsung- Yi Lin, Priya Goyal, Ross Girshick. Kaiming He, and Piotr Dollár. Focal loss for dense object detection. In CVPR, pages 2980-2988, 2017.
[25] Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. Isolation forest. In ICDM, pages 113-422. IEEE, 2008.
[26] Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. Isolation- anomaly detection. ACM Trans. Knowl. Discov. Data, 6(1):1-39, 2012.
[27] Rongrong Ma, Guansong Pang, Ling Chen, and Anton van den Hengel. Deep graph-level anomaly detection by glocal knowledge distillation. In WSDM, pages 704-714, 2022.
[28] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In NeurlPS, pages 2153-2164 2019.
[29] Hamed Masnadi- Masnadi-Shirazii and Nuno Vasconcelos. Risk minimization, probability elicitation, and cost- sensitive svms. In ICML, pages 759-766, 2010.
[30] Aditya Krishna Menon, Sadcep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar. Long-tail learning via logit adjustment. In ICLR, 2020.
[31] Christopher Morris, Martin Ritzert, Matthias Fey, William I. Hamilton, Jan Eric Lenssen, Gauray Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, pages 4602-4609, 0222-460,2220 2019.
[32] Giannis Nikolentzos and Michalis Vazirgiannis. Random walk graph neural networks. NeurlPS, pages 16211-16224 2020.
[33] Shirui Pan, Jia Wu, and Xingquan Zhu. Cogboost: Boosting for fast cost-sensitive graph classification. IEEE Trans. Knowl. Data Eng., 27(11) (111):233329444 2015.
[34] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. NeurIPS, 32, 2019.
[35] Chen Qiu, Marius Kloft, Stephan Mandt, and Maja Rudolph. Raising the bar in graph-level anomaly detection. In ICCAI, pages 2196-2203, 2022.
[36] Stephen Ranshous, Steve Harenberg, Kshitij Sharma, and Nagiza Samatova. scalable approach for outlier detection in edge streams using sketch-based approximations. SDM, pages 189-197, 2016.
[37] Lukas Ruff, Rohert Vandermeulen, Nico Goernitz, Lucas Deecke, Shoaib Ahmed Siddiqui, Alexander Binder, Emmanuel Müller, and Marius Kloft. Deep one-class classification. In ICMI., pages 4393-4402, 2018.
[38] Saurabh Sawlani, Lingxiao Zhao, and Leman Akoglu. Fast attributed graph embedding via density of states. In ICDM, pages 559-568. IEEE, 2021.
[39] Berhard Schölkopf, John C Platt, John Shawe-Taylor Alex J Smola, and Robert C Williamson. Estimating the support of a high-dimensional distribution. Neural Comput., 13(7):1443- 444-1141, 2001.
[40] Bernhard Schölkopf, Robert C Williamson, Alex Smola, John Shawe-Taylon and John Platt. Support vector method for novelty detection. In NeurlPS, pages 582-588, 1999.
[41] Nino Shervashidze and Karsten Borgwardt. Fast subtree kernels on graphs. In NeurlPS, pages 1660-1668. 2009.
[42] Nino Shervashidze, SVN Vishwanathan. Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. In AISTATS, pages 488 188-495, 2009.
[43] Mahito Sugiyama and Karsten Borgwardt. Halting in random walk kernlls. In NeurlPS, pages 1639-1647, 2015.
[44] Jianheng Tang, Jiajin Li, Ziqi Gao, and Jia Li. Rethinking graph neural networks for anomaly detection. In ICML, pages 21076-21089, 2022.
[45] Ruo-Chun Tzeng and Shan-Hung Wu. Distributed. egocentric representations of graphs for detecting critical structures. In ICML, pages 6354-6362. 2019.
[46] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2017.
12

---

[47] S Vichy N Vishwanathan. Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. J. Mach. Learn. Res., 11:1201-1242, 2010.
[48] H Gerhard Vogel, Wolfgang H Vogel, H Gerhard Vogel, Günter Müller, Jürgen Sandow, and Bernward A Schölkens. Drug discovery and evaluation: pharmacological assays, volume 2. Springer, 1997.
[49] Byron C Wallace, Kevin Small, Carla E Brodley, and Thomas A Trikalinos. Class imbalance, redux. In ICDM, pages 754-763, 2011.
[50] Jiaqi Wang, Wenwei Zhang, Yuhang 7ang, Yuhang Cao, Jiangmiao Pang, Tao Gong, Kai Chen, Ziwei Liu, Chen Change Loy, and Dahua Lin. Seesaw loss for long-tailed instance segmentation. In CVPR, pages 9695-9704, 2021.
[51] Shen Wang, Lifang He, Bokai Cao, Chun-Ta Lu, Philip S Yu, and Ann B Ragin. Structural deep brain network mining. In KDD, pages 475 484, 2017.
[52] Zhengyang Wang and Shuiwang Ji. Second-order pooling for graph neural networks. IEEE Trans. Puttern Anal. Mach. Intell., 2020.
[53] Gang Wu and Edward Chang. Kba: Kernel houndary alignment considering imhalanced data distribution. IEEE Trans. Knowl. Data Eng., 1766):786-775, 2005.
[54] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? ICLR, 2019.
[55] Xifeng Yan, Hong Cheng, Jiawei Han, and Philip Yu. Mining significant graph patterns by leap search. SIGMOD, pages 433-444, 2008.
[56] Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hicrarchical graph representation learning with differentiable pooling. NeurlPS, pages 4805-4815, 2018.
[57] Ge Zhang, Zhao Li, Jiaming Huang, Jia Wu, Chuan Zhou, Jian Yang. and Jianliang Gao. efraudcom: An e-commerce fraud detection system via competitive graph neural networks. ACM Trans Inf Syst, 40(3):1-29, 2022.
[58] Zhang, Jia Wu, Jian Yang, Amin Beheshti, Shan Xue, Chuan Zhou, and Quan 7 Sheng. Fraudre: Fraud detection dual-rcsistant to graph inconsistency and imbalance. In ICDM, pages 867-876. IEEF, 2021.
[59] Muhan Zhang, Zhicheng Cui, Marion Neumann, et An end-to-end deep learning architecture for graph classification. In AAAI, pages 4438-4445, 2018.
[60] Muhan Zhang and Pan Li. Nested graph neural networks. In NewrlPS, pages 15734-15747, 2021.
[61] Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. ICLR, 2020.
[62] Lingxiao Zhao and Leman Akoglu. On using classification datasets to evaluate graph outlier detection: Peculiar observations and new insights. Big Data, 2021.
[63] Panpan Zheng, Shuhan Yuan, Xintao Wu, Jun Li, and Aidong Lu. One-class adversarial nets for fraud detection. In AAAL pages 1286-1293, 2019.
[64] Bo Zong, Qi Song, Martin Renqiang Min, Wei Cheng, Cristian Lumezanu, Dacki Cho. and Haifeng Chen. Deep autoencoding gaussian mixture model unsupervised anomaly detection. ICLR, 2018
13

---

Checklist
1. For all authors...
(a) Do the main claims made the abstract and introduction accurately reflect the paper's contribu- tions and scope? [Yes]
(b) Did you describe the limitations your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report bars (e.g.. with respect the random seed after running experiments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) your work uses existing assets, you cite the creators? [N/A]
(h) Did you mention the license of the assets? [N/A]
(c) Did you include any
either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're 'r us-
ing/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable informa- tion offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable?
[N/A]
(b) you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "nSeKi0ZcwV", "reviewer": "Reviewer_yeLE", "summary": "This paper  is applied in the imbalance problem of graph-level anomaly detection, they propose a dual-discriminative graph neural network for graph-level anomaly detection. The first module is a novel anomalous attribute-aware graph convolution, which separates self representation and neighborhood-representation when representing a node in a graph. The second module is  an anomalous graph\nsubstructure-aware deep Random Walk Kernel to  encode anomalous structural information into graph representations.  Further,  they propose a Point Mutual Information-based loss function to address the imbalance nature of anomaly problem. ", "questions": "1. I think anomaly detection task  is originally a problem of label imbalance, and the author should not repeatedly emphasize this.\n\n2. This paper has limited application value. Due to there are very few anomaly detection labels, although supervised learning can also solve this problem, it is difficult to obtain labels of anomaly patterns in practical applications. The author should consider methods that do not rely on label information as much as possible, such as semi-supervised and unsupervised learning, e.g.\n\n3. The authors should compare with the most advanced methods for graph-level AD task, instead of GCN, GIN, SOPool, e.g.\n\nFor example: \n\n1): Ma R, Pang G, Chen L, et al. Deep Graph-level Anomaly Detection by Glocal Knowledge Distillation[C]//Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining. 2022: 704-714.\n\n2): Qiu C, Kloft M, Mandt S, et al. Raising the Bar in Graph-level Anomaly Detection[J]. arXiv preprint arXiv:2205.13845, 2022.\n", "limitations": "Please see Questions part", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Experiment are done on extensive real-world graph datasets and  evaluations are sufficient, moreover achieve great performance improvement.\n\n2. The idea is relatively novel， which couples  attribute-aware and  substructure-aware knowledge for graph-level AD problem.\n\nWeaknesses:\n\n1. The paper is not organized well, especially in the section of  Introduction and Related Work.\n\n2. Figure 1 is not intuitive enough to understand the intention of the authors.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "lnv70fjc_8V", "reviewer": "Reviewer_qTND", "summary": "In this paper the problem of graph level anomaly detection is studied, for imbalanced data, and a dual discriminative graph neural network is proposed, called iGAD. The proposed method focus on two main aspects of anomaly detection in graphs; (i) anomalous nodes attributes, and (ii) anomalous graph structures. For this reason, the method uses (i) anomalous attribute-aware graph convolution and (ii) anomalous substructure-aware deep random walk graph kernels. To deal with the imbalance that appears usually in anomaly detection scenarios, a point wise mutual information (PMI) loss function is used between the input graphs and their anomalous/normal attributes. A series of experiments have been conducted to study the performance of iGAD against other state of the art comparison methods in four real world chemical compound datasets and investigate a couple of research questions.", "questions": "- In Table 2: Why the authors do not give also the results for the Precision metric?\n\n- In Table 2: Are all these results tested for statistical significance? It is important to mention the statistical test and score for these results, as the 20% of the datasets that is being tested, is a small dataset.\n\n- Did the authors try bigger size of random walks (> 8 nodes)? To better understand this experiment, it would be useful to add in the Table 1 with the dataset statistics: the number of connected components in each graph and the avg. min. max. size of the connected components in each graph.", "limitations": "The authors did not address the potential negative societal impact of the work, however there is no potential negative impact.\nThe authors did address some of the limitations of the work and they leave them for future work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) The studied problem and the proposed method are very interesting to the research community. This work combines two main features in anomalous graphs with a novel loss function. The paper is well-written, well-structured and easy to follow.\n\n2) The methodology is sound and the proposed components could be used in different use cases. \n\n3) The authors did a good job in the related work section, organizing and covering some of the related literature to give the reader more motivation. It can be improved if the authors mention the contribution of their method after every limitation shoed in the related works.\n\n4) Experimental setup is very thorough and to the detail. The authors provide six research questions, and they show a detailed comparison with five comparison methods, five variants of the comparison methods and three variations of their method to prove the effectiveness of all the components combined.\n\nWeaknesses:\n1) The novelty of this work is limited, as most of the proposed methodology is either already published, or with small modifications from published methodology.\n\nMinor comments:\n1) In Figure 1, the step III is confusing, as it appears above step II. In step II, the light blue nodes (that show the random walks) is not clear to which paths they refer to from the graph G_S. I would suggest adding the node id to help the reader follow the thought.\n\n2) In Table 2, in MCF-7 dataset, the best result is not highlighted (iGAD-2).\n\n3) It would help if the authors repeat what M and n’ refer to in the caption of Figure 3.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8yz5cdpaQjv", "reviewer": "Reviewer_eQtL", "summary": "The paper proposes iGAD, a supervised anomaly detection model for distinguishing anomalous graphs from normal graphs. This paper identifies anomalous attributes and/or anomalous substructures as the anomaly notions of graphs, and also notices the imbalance nature of the anomaly problem. The authors employed three designs to achieve the graph-level anomaly detection model iGAD: a. Let the attributes of each node evolve individually in the graph convolution process to emphasize the anomalous attributes; b. Considering the defect of message passing-based GNNs in learning structural information, iGAD employs a deep random walk kernel that utilizes discriminative substructure learning and structure comparison to explore anomalous substructures; c. A new loss function was proposed to enable the proposed model to fit the minority class samples (i.e., anomalous graphs) well. Experimentally, iGAD shows strong performances in classifying anomalous and normal graphs on four graph datasets.", "questions": "Some questions to help authors further improve their research:\n1. The authors put forward a simple and general solution for learning the imbalanced data distribution. But different downstream application tasks have different tolerance for the false-positive rate and the false-negative rate. Considering it may help improve the applicability of iGAD.\n2. The datasets used for model verification are all molecular graphs. Why did not the author use the graph dataset from other application domains and have multi labels and specify one of the labels as anomalous and others as normal to conduct experiments?\n3. I suggest authors give more detailed explanations on why the cross-entropy loss cannot work on imbalanced data distribution in the main content or the appendix.", "limitations": "The authors clearly call out the limitation of their work.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: This paper proposes an interesting method to detect anomalous graphs in a graph dataset. It is a topic neglected by the anomaly detection and graph mining communities. The method comprehensively considers the anomalous notions in attributes and substructures of graphs, and the imbalance nature of the graph dataset with anomaly graph samples. \nQuality: The proposed method is technically sound, and the authors have basically made experimental verification of the proposed designs including the message passing graph convolution, deep RWK, and the PMI-based loss function. \nClarity: This paper has good organization and writing. The author gives detailed preliminaries corresponding to the method to help readers understand the proposed algorithm. In terms of experiments, the author gives the details of parameter settings for readers to reproduce the experiments.\nSignificance: Few deep graph learning practitioners consider how to detect anomaly graphs. Most graph anomaly detection work focuses on detecting anomaly nodes in a single graph. This paper extends the graph anomaly detection to the whole graph level. Although the anomalous information/notions of a graph may reflect in other aspects in addition to its node attributes and graph structure (authors also admitted this viewpoint in the discussion about the limitations of this work). The learned discriminative substructures provide explainable information for anomalous graph detection.  In addition, the PMI-based loss proposed in this paper has a good generalization, it can be extended to other imbalanced classification problems easily. Overall, this paper can be a good starting point for graph-level anomaly detection topic.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1Nr2n8jmO5t", "reviewer": "Reviewer_653N", "summary": "This paper focuses on a problem of graph-level anomaly detection that distinguish anomalous graphs from a set of graphs. For one graph, it could be considered as anomaly due to the anomalous attributes of certain nodes and the anomalous substructures. It is argued in the paper that generally GNNs will aggregate the information of neighbors resulting the relatively poor representation for anomaly graph detection. Thus, the authors investigate an anomalous attribute-aware graph convolution and anomalous substructure-ware deep RWK to detect the anomalies. Specifically, in anomalous attribute-aware graph convolution, the node representation and the representation of its neighbor will be separately encoded instead of merging together as GCN. To detect the anomalous substructure, the paper proposes a way to compare the random walk paths of graphs and the anomalous substructure. The anomalous substructure's adjacency matrix is learned in an end-to-end manner.  A PMI-based loss function is used to balance the contributions of normal graphs and anomalous graphs. Experiments are conducted several large-scale real-world to evaluate the effectiveness of the proposed method.", "questions": "1. It is highly suggested to clarify  the technical contribution of the proposed iGAD and have more discussions about the differences of iGAD with existing anomaly detection methods on graphs.\n2. It would be more convincing if experiments in comparing the potential baselines mentioned above in graph-level node classification can be added.", "limitations": "Please refer to the weaknesses for details.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n1. The graph-level anomaly detection is an important problem to be solved. And the existing work generally focus on node-level anomaly detection in graph. The proposed iGAD can give some insights for the community.\n2. The challenges of  graph-level anomaly detection are discussed. And the proposed mechanisms are convincing in detecting the anomalous attributes and anomalous sub-structures.\n3. The paper is well organized and easy to follow. \n4. Based on the current results, the iGAD seems promising in detecting anomalous graphs on the real-world datasets.\n\n**Weaknesses***\n1. Though the iGAD focuses on a novel problem of graph-level anomaly detection, there are concerns of technical contributions of the proposed method. \n    * Firstly, as node-level anomaly detection also faces the anomalous nodes and anomalous graphs, many methods in node anomaly detection share similar high-level idea with iGAD. For example, the anomaly scores based on the aspects of attribute matrix and adjacency matrix are separately considered in [1,2] for node anomaly detection. Thus, it is suggested to have more discussions about how the iGAD can address the unique challenges of graph-level anomaly detection. \n    * Secondly, it is argued that GNNs will aggregate the information of neighbors resulting the relatively poor representation for anomaly graph detection. To address this challenge, the graph convolution in iGAD separates the encoding on a node itself from its neighborhood when representing nodes. This design also have been widely known in GraphSage and H2GCN [3] to avoid mixing dissimilar nodes in H2GCN.\n\n2. Some important references and potential baselines are not covered. There are already works [4,5] noticed that the GNNs may not work well for anomaly detection because of the aggregation mechanism. They have proposed some special aggregation mechanism for anomaly detection. Though they are originally designed for node-level anomalies, it would be easy to extend for graph-level anomaly by adding readout function. I would suggest to compare with these state-of-the-art anomaly detection methods.\n\nReferences\n[1] Bandyopadhyay, Sambaran, Saley Vishal Vivek, and M. N. Murty. \"Outlier resistant unsupervised deep architectures for attributed network embedding.\" Proceedings of the 13th international conference on web search and data mining. 2020.\n[2]  Kumagai, Atsutoshi, Tomoharu Iwata, and Yasuhiro Fujiwara. \"Semi-supervised anomaly detection on attributed graphs.\" 2021 International Joint Conference on Neural Networks (IJCNN). IEEE, 2021.\n[3] Zhu, Jiong, et al. \"Beyond homophily in graph neural networks: Current limitations and effective designs.\" Advances in Neural Information Processing Systems 33 (2020): 7793-7804.\n[4] Kumagai, Atsutoshi, Tomoharu Iwata, and Yasuhiro Fujiwara. \"Semi-supervised anomaly detection on attributed graphs.\" 2021 International Joint Conference on Neural Networks (IJCNN). IEEE, 2021.\n[5] Dou, Yingtong, et al. \"Enhancing graph neural network-based fraud detectors against camouflaged fraudsters.\" Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 2020.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept