Rayleigh Quotient Graph Neural Networks for Graph-level Anomaly Detection
Authors: Xiangyu Dong
Xingyi Zhang
Sibo Wang
Venue: ICLR 2024 poster (2024)
Keywords: Graph-level anomaly detection
Spectral GNN
Rayleigh Quotient
Primary area: learning on graphs and other geometries & topologies
TL;DR: We propose the first spectral model RQGNN for graph-level anomaly detection.

Abstract: Graph-level anomaly detection has gained significant attention as it finds applications in various domains, such as cancer diagnosis and enzyme prediction. However, existing methods fail to capture the spectral properties of graph anomalies, resulting in unexplainable framework design and unsatisfying performance. In this paper, we re-investigate the spectral differences between anomalous and normal graphs. Our main observation shows a significant disparity in the accumulated spectral energy between these two classes. Moreover, we prove that the accumulated spectral energy of the graph signal can be represented by its Rayleigh Quotient, indicating that the Rayleigh Quotient is a driving factor behind the anomalous properties of graphs. Motivated by this, we propose Rayleigh Quotient Graph Neural Network (RQGNN), the first spectral GNN that explores the inherent spectral features of anomalous graphs for graph-level anomaly detection. Specifically, we introduce a novel framework with two components: the Rayleigh Quotient learning component (RQL) and Chebyshev Wavelet GNN with RQ-pooling (CWGNN-RQ). RQL explicitly captures the Rayleigh Quotient of graphs and CWGNN-RQ implicitly explores the spectral space of graphs. Extensive experiments on 10 real-world datasets show that RQGNN outperforms the best rival by 6.74% in Macro-F1 score and 1.44% in AUC, demonstrating the effectiveness of our framework. Our code is available at https://github.com/xydong127/RQGNN.

Published as a conference paper at ICLR 2024
RAYLEIGH QUOTIENT GRAPH NEURAL NETWORKS FOR GRAPH-LEVEL ANOMALY DETECTION
Xiangyu Dong, Xingyi Zhang, Sibo Wang
Department of Systems Engineering and Engineering Management The Chinese University of Hong Kong (xydong, xyzhang, swang)ese.cum cuhk. edu. .hk
ABSTRACT
Graph-level anomaly detection has gained significant attention as it finds applica- tions various domains, such as cancer diagnosis and enzyme prediction. How- ever, existing methods fail to capture the spectral properties of graph anomalies, resulting in uncxplainable framework design and unsatisfying performance. this paper, we re-investigate the spectral differences between anomalous and nor- mal graphs. Our main observation shows significant disparity in the accumulated spectral energy between these two classes. Moreover, prove that the accumu- lated spectral energy of the graph signal can be represented by its Rayleigh Quo- tient, indicating that the Rayleigh Quotient is driving factor behind the anoma- lous properties of graphs. Motivated by this, we propose Rayleigh Quotient Graph Neural Network (RQGNN), the first spectral GNN that explores the inherent spec- tral features of anomalous graphs for graph-level anomaly detection. Specifi- cally, we introduce novel framework with two components: the Rayleigh Quo- tient learning component (RQL) and Chebyshev Wavelet GNN with RQ-pooling (CWGNN-RQ). RQL explicitly captures the Rayleigh Quotient graphs and CWGNN-RQ implicitly explores the spectral space of graphs. Extensive experi- ments on real-world datasets show that ROGNN outperforms the best rival by 6.74% in Macro-FI score and 1.44% in AUC, demonstrating the effectiveness of our framework. Our code is available at https://ittuub.com/ydygg 22tp://ooooooooo22/2/2/o22 127/RQGNN.
INTRODUCTION
Graph-structure data explicitly expresses complex relations between items, and thus has attracted much attention from the deep learning community. Extensive efforts have been devoted to deploy- ing GNNs (Kipf & Welling
2017 Hamilton et al.] 2017 Velickovic et al. 2018) on node-level tasks. Recently, researchers have started to shift their focus from local properties graph-level
tasks (Wang et al. 2021 Liu et al. 2022 Yue et al. 2022). and graph-level anomaly detection has become one of the most important graph-level tasks with diverse applications (Ma et al.] [022] Zhang et al. 2022 Qiu et al. 2022). such as cancer diagnosis, enzyme prediction, and brain disease detection. In addition, applications of graph-level anomaly detection can be observed in trending
topics, such as spam detection (Li et al. 2019) and rumor detection (Bian et al. 2020).
Following the common design of graph learning models, existing solutions for graph-level anomaly detection mainly employ spatial GNNs with distinct pooling techniques. For example, CAL (Sui al. 2022) and FAITH (Wang et al.) (022) incorporate node features with topological characteris- ties of graphs to generate graph representations. Meanwhile, due to the limitations of the average or sum pooling function certain tasks, researchers have introduced various graph pooling functions (Wu et al. 2022 Hua et al., 2022) Liu et al. 2023). However, to the best of our knowledge, no previous attempt has provided spectral analysis for anomalous graphs, missing an important feature that can help better capture the properties of anomalous graphs.
To address this issue, we start by investigating the spectral energy of the graph Laplacian. Our key findings and theoretical analysis validate that the accumulated spectral energy can be represented by the Rayleigh Quotient, which has been studied in the physics and mathematics area (Pierre 1988 Chan al. 2011). Besides, Tang al. (2022) makes an interesting observation related to the

---

Published as a conference paper at ICLR 2024
Normal Graphs
Anomatowe Graphs
Normalized Prequency
Normalized Frequency
Normalized Frequency
0.2
0.2
0.2
0.1
0
0.2
0.4
0.6
0.8
0
0.2
0.4
0.6
0.8
0.2
0.4
0.6 0.8
Rayleigh Quotient
Rayleigh Quotient
Rayleigh Quotient
(a) Ra 188, The = 9512
(b) Thg = -77,, Rh = 19024 (c) ng 1955, 7n 38049
Figure Normalized Rayleigh Quotient distribution on SN12C.
Rayleigh Quotient for node anomaly detection. However, the inherent properties of the Rayleigh Quotient in the graph domain are still relatively under-explored. Hence, we investigate the Rayleigh Quotient for graphs and further empirically show that the Rayleigh Quotient distributions of normal graphs and anomalous graphs follow different patterns. In particular, we first randomly sample ne anomalous graphs and nh, normal graphs. For each graph, we calculate its corresponding Rayleigh Quotient. Subsequently, we set the maximum and minimum values of the Rayleigh Quotient of graphs as the bounds of the value range, which is then divided into 10 equal-width bins. After that, we assign each value of the Rayleigh Quotient of graphs to its corresponding bin. Finally, we cal- culate the frequency of values that fall into each bin and normalize them, which can be regarded as the normalized Rayleigh Quotient distribution of the sampled dataset. [ Quotient distribution on the SN12C dataset, and the results other datasets can be found in Ap- pendix [..9 As we can observe, regardless of the variations in the sample size, the Rayleigh Quotient distribution of each class exhibits a consistent pattern across different sample sets. In addition, is evident from Figure 1 that the Rayleigh Quotient distribution of anomalous graphs and that of normal ones are distinct from each other statistically. This observation highlights how the Rayleigh Quotient can reveal the underlying differences between normal and anomalous graphs. Hence, the Rayleigh Quotient should be encoded and explored when identifying anomalous graphs. Addition- ally, we establish a connection between the Rayleigh Quotient and the spectral energy of the graph Laplacian, it becomes apparent that the spectral energy distribution exhibits robust statistical patterns. This, in turn, empowers us to leverage spectral graph neural networks for further encoding and utilization of this valuable information.
the Rayleigh
Motivated by the observation and theoretical analysis, in this paper, we propose ROGNN, Rayleigh Quotient-basse GNN framework for graph-level anomaly detection tasks. It consists of two main components: the Rayleigh Quotient learning component (RQL) and Chebyshev Wavelet GNN with RQ-pooling (CWGNN-RQ). Firstly, we adopt RQL to derive the Rayleigh Quotient of each graph and then employ multi-layer perceptron (MIP) generate the representation of each graph, aim- ing to capture explicit differences between anomalous and normal graphs guided by their Rayleigh Quotient. Secondly, obtain the implicit information embedded in the spectral space, we draw inspiration from the Chebyshev Wavelet GNN (CWGNN) and adopt it to learn the inherent in- formation in the graph data. Besides, to alleviate the drawbacks of existing pooling techniques in graph-level anomaly detection, we introduce powerful spectral-related pooling function called RQ-pooling. Furthermore, we address the challenge of imbalanced data in graph-level anomaly detection via a sentations generated by the RQL and CWGNN-RQ. By combining the explicit information from the Rayleigh Quotient and the implicit information from the CWGNN-RQ. RQGNN effectively captures more inherent information for the detection of anomalous graphs.
focal loss. The final graph embedding is the combination of repre-
In experiments, we evaluate RQGNN against 10 alternative frameworks across 10 datasets. Extensive experiments demonstrate that our proposed framework consistently outperforms spec- tral GNNs and the state-of-the-ard (SOTA) GNNs for both graph classification task and graph-level anomaly detection task. We summarize our contributions as follows:
Our main observation and theoretical analysis highlight that the Rayleigh Quotient reveals under- lying properties of graph anomalies, providing valuable guidance for future work in this field.
We propose the first spectral GNNs for the graph-level anomaly detection task, which incorporates explicit and implicit learning components, enhancing the capabilities of anomaly detection.
Comprehensive experiments show that RQGNN outperforms SOTA models on 10 roal-world graph datasets, demonstrating the effectiveness of RQGNN.
2

---

Published as a conference paper at ICLR 2024
2 PRELIMINARIES
Notation. Let G = (A, X) denote a connected undirected graph with nodes and m edges, where X E RnxF" is node features, and A E IR"xn is the adjacency matrix. We set Auj = if there exists an edge between node i and j. otherwise AG = O. Let D be the diagonal degree matrix, the Laplacian matrix L is then defined as D A (regular) or as I,- - D AD (normalized), where I is an identity matrix.
Rayleigh Quotient. The regular Laplacian matrix can be decomposed as L = UAUT, where U = 1 U2..... u,)) represents orthonormal eigenvectors and the corresponding eigenvalues are sorted in ascending order, i.e. A S S An- Let x = #2........ I..) E RR" be a signal on graph F2 Fn ) U x: is the graph Fourier transformation of æ. Following the definition in Horn & Johnson 2012), the Rayleigh Quotient is defined as
G. c
x= ='L_ x"
Next, briefly review spectral GNNs and existing work for graph-level anomaly detection and graph classification.
Spectral GNN. By processing Laplacian matrix, spectral GNNs manipulate the projection of graph spectrum (Defferrard et al., (016) and can be viewed as graph signal processing models. It has drawn much attention in the graph learning community. For instance, ChebyNet (Defferrard al. 2016) and BernNet (He et al. 2021) utilize different approximations of spectral filters to improve the expressiveness of spectral GNN. Specformer (Bo et al., 2023) combines the transformer and spectral GNN to perform self self-attention in the spectral domain. BWGNN (Tang et al. (2022) adopts a wavelet filter to generate advanced node representations for node-level anomaly detection, showing the potential ability of wavelet filter in the anomaly detection area.
Graph-level Anomaly Detection. To the best of our knowledge, OCGIN (Zhao Akoglu 2021)
is the first to explore graph-level anomaly detection, which provides analysis to handle the perfor-
mance flip of several methods on graph classification datasets. After that, OCGTL (Quu et al. 2022)
adopts graph transformation learning to identify anomalous graphs and GLocalKD (Ma et al. 2022) investigates the influence of knowledge distillation on graph-level anomaly detection. A following work, HimNet (Niu et al.) 2023) builds hierarchical memory framework to balance the anomaly- related local and global information. One recent study, iGAD (Zhang et al.] (2022) suggests that the anomalous substructures lead to graph anomalies. It proposes an anomalous substructure-awwar deep random walk kernel and a node-aware kernel to capture both topological and node features, achieving SOTA performance. Yet, existing solutions only explain the anomalous phenomena from spatial perspectives. In contrast, our RQGNN further explores the spectral aspects of anomalous graphs, leading to an explainable model design and satisfying model performance.
Remark. In out-of-distribution datasets, only one class of in-distribution data is given, while anomaly datasets usually contain data with two distinct characteristies. Therefore, out-of- distribution detection focuses on determining whether a new sample belongs to the given class, while anomaly detection aims to determine new sample belongs to which class.
Graph Classification. Graph classification models can also be considered for our task. GMT (Baek et al. (02T) points out that a simple sum or average pooling function is unlikely to fully collect information for graph classification. The authors propose multi-head aatentioo-based global pooling layer to capture the interactions between nodes and the topology of graphs. Afterward, Gmixup (Han et al. 2022 applies data augmentation to improve the general- ization and robustness of GNN models. Moreover, TVGNN (Hansen & Bianchil 2023) gradually distills the global label information from the node representations. Even though these models have achieved SOTA performance on the graph classification task, the imbalanced datasets bring a non- negligible problem for such models. Without specifically paying attention to the imbalanced nature of data, these SOTA graph classification models are not able to meet the requirements of the graph- level anomaly detection task, as we will show during the empirical evaluation.
general framework
3 OUR METHOD: RQGNN
The observation in Section [ highlights the differences between the Rayleigh Quotient distribution of anomalous and normal graphs. In Section 3.1 we further provide theoretical analysis of the
3

---

Published as a conference paper at ICLR 2024
Rayleigh Quotient. This motivates our design of the Rayleigh Quotient learning component (RQL) in our framework, to be elaborated in Section 3.2 Moreover, our theoretical analysis in Section 3.1 further shows that the accumulated energy of the graph can be represented by the Rayleigh Quotient, which motivates us to apply the spectral GNN to capture the spectral energy information, to be detailed in Section 3.3] We further present powerful spectral-related pooling function called
RQ-pooling in Section 3.3 Section 3.4eelabrrasss on the design of class-balanced focal loss.
3.1 RAYLEIGH QUOTIENT AND SPECTRAL ANALYSIS
As described Section T Rayleigh Quotient has been studied in other domains. This inspires us to explore the property of the Rayleigh Quotient in the graph area. Specifically, we further provide analysis to show the connection between the Rayleigh Quotient and the spectrum of graphs. The following two theorems show that the change of the Rayleigh Quotient can be bounded given a small perturbation on graph signal æ and graph Laplacian L, and proofs can be found in Appendix A..]
Theorem 1. For any given graph G. if there exists a perturbation A on L, the change of Rayleigh Quotient can be bounded by ||
Theorem 2. For any given graph G. if there exists a perturbation on x. the change of Rayleigh Quotient can be bounded by 2x Lô + I is small enough, in which case o(ō) can be ignored, the change can be further bounded by 2x Lô.
Theorems 2 provide valuable guidance in exploring the underlying spectral properties behind anomalous and normal graphs based on the Rayleigh Quotient. Recap from Section [] that the normalized Rayleigh Quotient distribution of graphs with the same class label statistically exhibits similar pattern on different sample sizes. If the graph Laplacian L and graph signal æ of two graphs are close, then their Rayleigh Quotients will be close each other and these two graphs will highly likely belong to the same class. This motivates us to design a component to learn the Rayleigh Quotient of each graph directly, as we will show in Section 3.2
Besides, we further analyze the relationship between the Rayleigh Quotient and the spectral energy of graphs, which serves as the rationale for incorporating spectral- rreattel component into our framework. Let / >i=1 2i denote the spectral energy of λς. Although this distribution provides valuable guidance for measuring the graph spectrum in mathematics,
not suitable for GNN training due to the time-consuming eigendecompossitin computation. Therefore, in the following, we introduce the accumulated spectral energy and show that it can be transformed into the Rayleigh Quotient, thereby avoiding the expensive matrix decomposition process.
Let E E. &? denote the accumulated spectral energy from X to AR. According to pre- vious work (Li al. 2022, Luan al. 2022), real-world graph data usually shows heterophily in connection and high-pass graph filters will capture more spectral information. Based on this observation, instead of exploring the original accumulated spectral energy that represents the low- frequency energy, we investigate the high-frequency energy that represents the accumulated spec- tral energy from d An- For any
[Ak. Ak+1), where 1 S k I 1, we denote FE(t) = 1- Σj /3/ E f as the high-frequency energy. Then we can derive:
L. E()dtt
Σj= N 2 +2
xT Lx
(I)
x x
This result demonstrates that the accumulated spectral energy can be exactly represented by the Rayleigh Quotient. We summarize this result in the following proposition.
Proposition 1. Given graph G, the Rayleigh Quotient represents the accumulated spectral energy.
The Proposition T indicates the Rayleigh Quotient represents the accumulated spectral energy of the graph, which motivates us to design a spectral GNN and spectral-related pooling function to capture the inherent properties behind anomalous graphs, as we will show in Section 3.3
3.2 RAYLEIGH QUOTIENT LEARNING COMPONENT
Motivated by Theorems 2 and the observation in Section T a simple yet powerful component is introduced to capture different trends on the Rayleigh Quotient. Specifically, we first use two-layer
4

---

Published as a conference paper at ICLR 2024
MLP to obtain the latent representation of each node. Then, caleulate the Rayleigh Quotient for each graph as the explicit learning component in our RQGNN. Let X denote the node features X after the feature transformation, then the Rayleigh Quotient can be expressed as:
X LX XT
RQ(X, diag
where d-ag(-) denotes the diagonal entries of square matrix. Finally, we employ another two-layer MLP to get the Rayleigh Quotient representation of the entire graph:
RR MLP (RQ(X, L))
Except for explicitly learning from the Rayleigh Quotient, following the common design of GNN, we need to implicitly learn from the topology and node features of graphs, so that we can collect comprchensive information for graph-level anomaly detection. The details are presented as follows.
3.3 CHEBYSHEV WAVELET GNN WITH RQ-POOLING
As described in Section 3.1 the accumulated spectral energy can be represented by the Rayleigh Quotient, which reveals crucial spectral properties for graph-level anomaly detection. This moti- vates us to design a spectral GNN for learning graph representations. Even though existing spectral GNNs, e.g.. ChebyNet (Defferrard al. 2016) and BernNet (He et al. al.] [202]). have achieved notable success in the node classification task, these models fall short in capturing the underlying properties of anomalous graphs, resulting in inferior performance on the graph-level anomaly detection task, as we will show in experiments. This can be attributed to two main reasons. Firstly, simple spectral GNNs can be seen as single low-band or high-band graph filters (He et al. 2021), and each band filter only allows certain spectral energy pass. However, analyzed in Section 3.1 to capture the spectral properties of anomalous graphs, we should consider the spectral energy with respect to each eigenvalue. Therefore, it is necessary to employ multiple graph filters. The graph wavelet convolution model can be considered as a combination of different graph filters, enabling us to con- sider the spectral energy associated with each eigenvalue. Consequently, leveraging graph wavelet convolution provides advantages compared to using single graph filters. Secondly, even using more powerful spectral GNN models, generating improved graph representations remains challenging without a carefully designed pooling function. To address these issues, we present CWGNN-RO. novel component that effectively learns the inherent spectral representations of different graphs.
CWGNN. Following Hammond et al. (2011a), we define vb as the graph wavelet and group of q wavelets can be denoted as W (W w/s V... Ww,). Each wavelet denoted as W..
Ug(AAUT where gi (-) is the kernel function defined on [0, An_ in the spectral domain. Then, the general wavelet GNN of graph signal
be expressed as:
W x
W 1 W Wig
W., x (A)U" a. U2,U2AAAU x, ..9, m]
However, calculating graph wavelets requires decomposing the graph Laplacian, resulting in expen- sive computational costs. To achieve better computational efficiency, we employ Chebyshev polyno- mials to calculate approximate wavelet operators. The following lemma shows that the Chebyshev series can be used to represent any function.
Lemma Rivlin 1974)). There always exists a convergent Chebyshev series for any function f(()):
1 S(1) - 2 + Tc(),,
where cs = 2 5T (o)s and is the order of the Chebyshev polynomials.
In addition, the Chebyshev polynomials on interval [-1, 1] can be iteratively defined as (t) 2fTh-1 (t) ( with initial values of (t) 1 and T; (f) = t. Given that the eigenvalues of the normalized Laplacian matrix fall in the range of [0, 2]. we utilize the shifted Laplacian matrix L I, compute the following shifted Chebyshev polynomials T. Meanwhile, for each wavelet i, we also have a scale function s.(.) to re-scale the eigenvalue so that can fit into the domain of to calculate the following Chebyshev coefficient C.A. By introducing the truncated Chebyshev
5

---

Published as a conference paper at ICLR 2024
polynomials into graph wavelet operators, the i-th kernel function fL( is designed to capture the first -ho information, which can be expressed as follows (Hammond et al. 2011b):
K
1 M(L) 2 J0,0 + Σ TL))
(4)
where (L) = (L 1)Tk- (L) - (L) with initial values of (b()) = In and Ti (L)
th, represents the shifted Chebyshev polynomials and G, = - So cos(k0) (s;(( [= 21)) )d00
with 1 S 3 q. Then, the results of & graph wavelets are concatenated together to generate the representation of node j:
h CONCAT ((I(C))) (B())))) (1a(1))))
(5)
After node representations h generated by CWGNN, pooling function is needed obtain the representation of the entire graph. Commonly used pooling functions such as average pooling and sum pooling functions (Hamilton al. 2017) have achieved satisfactory performance classification tasks. However, as demonstrated in our experiments, these techniques become inef- fective in graph-level anomaly detection. Consequently, this challenge calls for newly designed pooling function that can effectively guide CWGNN to learn better graph representation.
various
RQ-pooling, In order to incorporate spectral information into node weights, we adopt an attention mechanism to generate the graph representation:
G = a Lanh, jEV
(6)
where is the non- non-linear activation function, and a, is the attention coefficient of node Specif- ically, since the spectral energy corresponds to each graph signal, we set the Rayleigh Quotient as the weight of these signals. Then, the attention coefficient for node can be expressed as aj = RQ X, L)hj, which is used as the node importance score in RQ-pooling. Such strategy allows CWGNN capture more underlying spectral information of graphs. The final representation of the graph is the concatenation of both hiq and hau
he MLP (CONCATTATT (h Au (()))
3.4 CLASS-BALANCED FOCAL LOSS
As discussed in Section 2 the imbalanced nature of graph-level anomaly detection brings non- negligible challenges. To tackle this issue, we introduce a re-weighting technique called the class- balanced focal loss, which enhances the anomalous detection capability of our RQGNN.
Expected number (Cui et al., 2019). As the number of training samples increases, there will be more potential information overlap among different samples. Consequently, the marginal benefit that model can extract from the data diminishes. To address this issue, the class-balanced focal loss is designed to capture the diminishing marginal benefits by using more data points of class. This approach ensures that the model effectively utilizes the available data while avoiding redundancy and maximizing its learning potential. Specifically, we deñne the expected number (7())) as the total number samples that can be covered by nt training data and utilize the inverse of this number as the balance factor in our loss function.
Proposition 2.
The expected number T)(r)) 1-3 where B N-1 with N equaling to the total
1-g"t
number of data points in class t.
In practice, without further information of data for each class, it is difficult to empirically find a set of good N for all classes. Therefore, we assume N is dataset-dependent and set the same / for all classes in a dataset. In addition, we also employ focal loss (Lin et al.) 2017). an adjusted version of cross-entropy loss. By combining the expected number and focal loss together, we can achieve the goal of reweighting the loss for each class. The class-balanced focal loss is defined as follows:
C
Lsocal
1-3 3
LCB =
Σ (1 loggp))(
(8)
m(ny) 1 - --

---

Published as a conference paper at ICLR 2024
Table 1: AUC and Macro-FI scores (%) on ten datasets with random split.
Speciaal GNN
Grupli Claviiscation
Grapellevd Anoraly Disevtion
Danasess
Metries
ChehyNer
BernNet
GMF
Gimisup
TVGNN
GOGIN
OCGT)
GilocaiKD
HomNer
KIAD
RQGNN-1
ROGNN.2
ROGNN
MCF-7
F1
0,6612
0.4780
0,4784
0.4744
0.6954
0.4799
0.5594
0,3318
0.3866
0.6363
0.6369
0.6468
0,804
0.6626
0.336
0,7205
0,8354
0.7394
MOLT-4
AUC
0.6617
0.614
0.7906
0.6222
0,7139
0.3299
0.6191
0.6631
0,6633
0.8086
08216
03196
0.8316
0.4854
0.814
0.7119
PC33
ATC
0.6051
0.6084
0.7806
0.008
0.7914
0,5810
0.6349
0,6727
0,603
0.8223
08553
0.8671
0.8782
F1
0.1853
0.4853
04853
048522
0,6206
0.6697
0,7003
0.7241
0.7184
SW-620
ATC
F1
0.6799
0.489M
0.4847
0.6072
0.7467
0.474
0.479
04844
0.7376
0.5365
0,4935
0.6398
0.6542
0.6544
0.6627
08512
0.641
0.401
0.7209
03442
0.7335
0,8550
NCI-123
AUC
0.6728
0.6114
0,000
07722
0,7782
0.4948
0.6122
0.6877
0,0814
0.8297
08413
0.854
0,8650
0-4930
0.4899
0.499
04469
0.5520
0.6646
0.635
0.7349
0.7214
OVCAR-8
AUC
0.6303
0.3850
0.7692
0.5663
0.7653
0,3298
0.8007
0,8750
0.6757
0.8691
08349
D38600
0.8799
0.4900
0.4868
0.4868
0.4869
0,5406
0.6638
0.6776
0.7077
0.7215
PARK
AUC
F1
0.7266
0.5635
0.6707
0.5001
03195
0,6583
0.616
0.4856
0,5557
0.7957
0.5252
0.6501
0.5415
0.0667
0.7437
0.8945
0,7582
03911
0.891
0.2738
0.7963
0,9023
SP-295
AUI
0.6650
0.6353
0.7992
0.7346
0.4774
0.6440
0.7069
0,7073
0.8770
0.8691
0
0.8825
F1
0.4871
0.487]
0.477
044866
0.4935
0.6919
0.7120
0.7335
0,7416
SN12C
AUC
0.6598
0.6014
0,7919
0.721
0.744
0,5004
0.5617
0.6880
0.8747
0.8851
0.3900
0.8861
0.4972
0,4874
0.474
0.5437
0.6714
0.7214
0.7549
0.7660
UACC257
AUC
0.0584
0.6115
0.7735
0.0364
0.7410
0.5411
0.6148
0.6647
0.0659
0.8512
0.8447
0.8596
0.8724
F1
0.4894
0.4895
0.494
0.4004
0:5373
0.6488
0.6889
0.7088
0,7362
where 3 and y are hyperparameters, ny is the number of samples in class y that the current sample belongs to, C' denotes the number of classes, and p; = softmax(h (h"), is the predicted probability for the current sample belonging to class i.
4 EXPERIMENTS
4.1 EXPERIMENTAL SETUP
Datasets. We use 10 woald datasets investigate the performance of RQGNN, including MCF- 7, MOLT-4, PC-3, SW-620, NCI-H23, OVCAR-8, P388, SF-295, SN12C, and UACC257. These datasets are obtained from the TUDataset (Morris et al. 2020), consisting of various chemical com- pounds and their reactions to different cancer cells. We treat inactive chemical compounds as normal graphs and active ones as anomalous graphs.
Baselines. We compare RQGNN against 10 SOTA GNN competitors, including spectral GNNs, graph classification models and graph-level anomaly detection models.
Spectral GNNs with average pooling function: ChebyNet (Defferrard et al.
2016) and BernNet
(He et al. 2021).
Graph classification models: GMT (Back al. 2021 ) Gmixup (Han al. 2022). and TVGNN
(Hansen & Bianchi 2023).
Graph-level anomaly detection models: OCGIN (Zhao & Akoglu 202 , OCGTL Oiu et al.
2022), GLocalKD (Ma et al., 2022), HimNet (Niu et al. 2023). and iGAD (Zhang et al. 2022).
Also, we investigate two variants of RQGNN. We use RQGNN-1 to indicate the model that replaces the RQ-pooling with the average pooling, and use RQGNN-2 to indicate the model without the RQL component. More details of the datasets and baselines can be found in Appendix A.3
Experimental Settings. We randomly divide each dataset into training/validationfees 70%/15%/15%, respectively. During the sampling process, we ensure that each set maintains a consistent ratio between normal and anomalous graphs. We select the epoch where the models achieve the best Macro-FI score on the validation set as the best epoch and use the corresponding model for performance evaluation. We set the learning rate as 0.005, the batch size as 512, the hidden dimension d = 64, the width of CWGNN-RQ q = 4, the depth of CWGNN-RQ K = 6, the dropout rate as 0.4, the hyperparameters normalization for the final graph embeddings. We obtain the source code of all competitors from GitHub and perform these GNN models with default parameter settings suggested by their authors.
sets with
the loss function 3 = 0.999, 7 = 1.5, and we use batch
4.2 EXPERIMENTAL RESULTS
We first evaluate the performance of RQGNN against different SOTA GNN models. Table rreporsss AUC and Macro-F1 scores of each GNN model 10 datasets. The best result on each dataset is
7

---

Published as a conference paper at ICLR 2024
MCF-7
SF-295
SNI2C
UACC257
F/ Score
FI Score
Fl Score
0.8
0.8
0.8
0.75
0.75
0.75
0.7
0.7
0.7
0.65
32
64
128
256
0.65
4
5
6
0.65
5
(a) Varying hidden dimensions
(b) Varying width
(c) Varying depth
Figure 2: Varying the hidden dimension, width, and depth.
highlighted in boldface. Since OCGIN, OCGTL, GLocalKD, and HimNet adopt one-class classi- fication to identify anomalous graphs, we only report their AUC scores. As we can see, RQGNN outperforms all baselines on all datasets. Next, provide our detailed observations.
Firstly, for two SOTA spectral GNNs, ChebyNet and BernNet, they fail to learn the underlying anomalous properties from the spectral perspective. In particular, compared with ChebyNet and BernNet, RQGNN takes the lead by 20.72% and 25.28% on these 10 datasets in terms of aver- these 10 datasets in terms of aver- age AUC score, and takes the lead by 24.40% and 25.33% age Macro-FI score, respectively. These empirical evidences demonstrate that even though graph Laplacian matrix related to graph spectral energy, we still need carefully design graph filters and pooling functions to capture the underlying anomalous properties in the graph.
Secondly, we carefully check the results of GNNs for graph classification to verify whether graph- level anomaly detection can be easily tackled by graph classification models. From Table we can observe that compared to three GNN models, GMT, Gmixup, and TVGNN, RQGNN takes lead by 8.38%, 20.59%, and 11 11.69% in terms of average AUC score and 23. 73,,0% 25.4 25.48%, and 19.67% % in terms of average Macro-F1 score, respectively. These results demonstrate that graph classification models cannot be directly adopted to handle the graph-level anomaly detection task.
Thirdly, we compare RQGNN with SOTA GNN models designed for graph-level anomaly detection. Despite being specialized for graph-level anomaly detection, OCGIN, OCGTL, GLocalKD, and HimNet fail to outperform other GNN baselines terms of AUC scores. This can attributed to their inability effectively capture the important graph anomalous information. In contrast, RQGNN guided by the Rayleigh Quotient successfully captures the spectral differences hetween anomalous and normal graphs, resulting in significantly superior performance compared OCGIN, OCGTL, GLocalKD, and HimNet. In particular, RQGNN takes the lead by an average margin of 34.82%, 25.28% 20.02%, and 19.78% terms of AUC score, respectively. Among all the baselines, iGAD stands out as the most competitive model, which incorporates anomalous-awan sub-structural information into node representations. However, it lacks the incorporation of important properties of anomalous graphs, such as the Rayleigh Quotient and spectral energy of graphs, which leads to relatively unsatisfying Macro-FI scores on all datasets. With the guidance of Rayleigh Quotient, RQGNN outperforms iGAD by 1.44% in terms of AUC score and 6.74% in terms of Macro-F1 score on average across 10 datasets.
4.3 ABLATION STUDY
In this set of experiments, we investigate the effectiveness of each component in RQGNN. Ablation study for the class-balanced focal loss can be found in Appendix A.2 The experimental results of RQGNN variants are shown in Table
Firstly, we use RQGNN-1 to indicate the model that replaces the RQ-pooling with average pooling. Recap from Section 4. that, combines the representation of Rayleigh Quotient and CWGNN with average pooling function. As we can observe, RQGNN-1 outperforms all other baselines datasets in terms of the Macro-Fl scores. In particular, compared with RQGNN-1, ROGNN further boosts the performance and takes the lead by 1.76% in terms of the AUC score and 3.92% in terms of the Macro-F1 score on average. This result demonstrates that the RQ-pooling that introduces Rayleigh Quotient as the node weight captures more crucial information from the spectral domain.
all
8

---

Published as a conference paper at ICLR 2024
Train
Test True
Test False
Normalized Frequency
Normalized Frequency
0.3
0.2
0.2
0.1
0.1
0.2 0.4
0.6
0.8
0
0.2
0.4
0.6
0.8
Rayleigh Quotient
Rayleigh Quotient
(a) Normal Graphs
(b) Anomalous Graphs
Figure 3: Normalized Rayleigh Quotient distribution on SN12C.
Then, we use RQGNN-2 to indicate the model with only CWGNN-RQ. Specifically, remove the RQL component that explicitly calculates the Rayleigh Quotient each graph. Instead. we only compute the Rayleigh Quotient the node weights for CWGNN. As observe. RQGNN-2 outperforms all the other baselines in terms the Macro-F1 scores, which again shows the effec- tiveness of the RQ-pooling. Besides, according to Table than RQGNN-2 terms of AUC score and 1.08% higher than RQGNN-2 in terms of Macro-F1 score average, which further shows the effectiveness of the RQL component. In summary, these results demonstrate the effectiveness of each component in RQGNN.
that ROGNN is 0.09% higher
4.4 PARAMETER ANALYSIS
Next, conduct experiments to analyze the effect of representative parameters: the hidden di- mension d of RQGNN, the width g and depth K CWGNN-RO on MCF-7, SF-295, SN12C, and UACC257 datasets. Figure reports the Macro-F1 score of ROGNN sion from 32 to 256, the width q from 3 to 6, and the depth from 5 to 8. As we can observe, when we set the hidden dimension 64, ROGNN achieves relatively satisfactory performances on these four datasets. When the width of CWGNN-RQ is set to 4, RQGNN achieves the best results on all four datasets. Hence, we the width to in our experiments. Meanwhile, as we can observe, RQGNN shows a relatively stable and high performance in terms of all four presented datasets when we set the depth As a result, the depth is set in ROGNN.
vary the hidden dimen-
4.5 CASE STUDY
In this set of experiments, we conduct experiments to investigate whether RQGNN learns the trends of Rayleigh Quotient on anomalous and normal graphs. If RQGNN successfully detects anomalous graphs, the samples in the test set that can be classified correctly by converged model should have similar Rayleigh Quotient distribution that in the training set. Figure 3 illustrates the Rayleigh Quotient distribution of the normal and anomalous graphs in the training and test set on the SN12C dataset. As we can see, graphs that can be classified correctly in the test set exhibit a similar Rayleigh Quotient distribution to that in the training set. Meanwhile, those graphs that our RQGNN can not classify correctly, display different distributions from the train graphs. These results demonstrate that Rayleigh Quotient is an intrinsic characteristic of the graph-level anomaly detection task for the application studied. Our RQGNN can effectively learn the Rayleigh Quotient as a discriminative feature and thus outperforms SOTA competitors.
5 CONCLUSION
In this paper, we introduce spectral analysis into the graph-level anomaly detection task. We dis- cover differences in the spectral energy distributions between anomalous and normal graphs and further demonstrate the observation through comprehensive experiments and theoretical analysis. The combination of the RQL component that explicitly captures the Rayleigh Quotient of the graph and CWGNN-RQ that implicitly explores graph anomalous information provides different spectral perspectives for this task. Extensive experiments demonstrate that RQGNN consistently outper- forms other SOTA competitors by significant margin.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work was supported by Hong Kong RGC GRF (Grant No. 14217322) and Hong Kong ITC ITF (Grant No.MRP/071/20X), Sibo Wang is the corresponding author.
REFERENCES
Jinheon Back, Minki Kang, and Sung Ju Hwang. Accurate learning of graph representations with graph multiset pooling. In ICLR, 2021.
Tian Bian, Xi Xiao, Tingyang Xu, Peilin Zhao, Wenbing Huang, Yu Rong, and Junzhou Huang- Rumor detection on social media with bi-directional graph convolutional networks. In AAAI, pp- 549-556, 2020.
Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao. Specformer: Spectral graph neural networks meet transformers. In ICLR, 2023.
K.T. Chan, N.G. Stephen, and K. Young. Perturbation theory and the rayleigh quotient. Journal of Sound and Vibration, 330:2073-2078, 2011.
Yin Cui, Menglin Jia, Tsung Yi Lin, Yang Song, and Serge J. Belongie. Class-balanced loss based effective number of samples. In CVPR, pp. 9268-9277, 2019.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NeurlPS, pp. 3837-3845, 2016.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, pp. 1024-1034, 2017.
David K. Hammond, Pierre Vandergheynst, and Rémi Gribonval, Wavelets on graphs via spectral graph theory. Appl. Comput. Harmon. Anal., 30(2):1299 150, 2011a.
David K. Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30:129-150, 2011b.
Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-mixup: Graph data augmentation for graph classification. In ICML, pp. 8230-8248, 2022.
Jonas Berg Hansen and Filippo Maria Bianchi. Total variation graph neural networks. In ICML, pp. 12445-12468, 2023.
Mingguo He, Zhewei Wei, Zengfeng Huang, and Hongteng Xu. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. In NeurIPS, pp. 14259- 2021.
Roger Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
Chenqing Hua, Guillaume Rabusseau, and Jian Tang. High-order pooling for graph neural networks
with tensor decomposition. In NeurIPS, 2022.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Boris Knyazev, Graham W. Taylor, and Mohamed R. Amer. Understanding attention and gener- alization in graph neural networks. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 4204 2414, 2019.
Ao Li, Zhou Qin, Runshi Liu, Yiqun Yang, and Dong Li. Spam review detection with graph convo- lutional networks. In CIKM, pp.
2019.
Mingjie Li, Xiaojun Guo, Yifei Wang, Yisen Wang, and Zhouchen Lin. G2on: Graph gaussian convolution networks with concentrated graph filters. In ICMI, 2022.
10

---

Published as a conference paper at ICLR 2024
Tsung- Yi Lin, Priya Goyal, Ross B. Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. In ICCV, pp. 1999-3007, 2017.
Chuang Liu, Yibing Zhan, Jia Wu, Chang Li, Bo Du, Wenbin Hu, Tongliang Liu, and Dacheng Tao. Graph pooling for graph neural networks: Progress, challenges, and opportunities. In IJCAI, pp. 67 6712-6722, 2023.
Zemin Liu, Qiheng Mao, Chenghao Liu, Yuan Fang, and Jianling Sun. On size-oriented long-tailed graph classification of graph neural networks. In www, pp. 1506-1516, 2022.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-War Chang, and Doina Precup. Revisiting heterophily for graph neural networks. In NeurlPS, 2022.
Rongrong Ma, Guansong Pang, Ling Chen, and Anton van den Hengel. Deep graph-level anomaly detection by glocal knowledge distillation. In WSDM, pp. 704-714, 2022.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML Workshop GRL+ 2020.
Chaoxi Niu, Guansong Pang, and Ling Chen. Graph-level anomaly detection via hierarchical mem- ory networks. In ECML-PKDD, 2023.
Shirui Pan, Xingquan Zhu, Chengqi Zhang, and Philip S. Yu. Graph stream classification using labeled and unlabeled graphs. In 29th IEEE International Conference on Data Engineering, ICDE 2013, Brisbane, Australia, April 8-12, 2013, pp. 398-409, 2013.
Christophe Pierre. Comments rayleigh's quotient and perturbation theory for the eigenvalue problem. Journal of Applied Mechanics, 55:986-988, 1988.
Chen Qiu, Marius Kloft, Stephan Mandt, and Maja Rudolph. Raising the bar in graph-level anomaly detection. In IJCAI, pp. 2196-2203, 2022.
GTheodore J. Rivlin. The Chebyshev polynomials. John Wiley & Sons, 1974.
Yongduo Sui, Xiang Wang, Jiancan Wu, Min Lin, Xiangnan He, and Tat-Seng Chua. Causal atten- tion for interpretable and generalizable graph classification. In SIGKDD, pp. 1696-1705, 2022.
Jianheng Tang, Jiajin Li, Ziqi Gao, and Jia Li. Rethinking graph neural networks for anomaly detection. In ICML, pp. 21076-21089, 2022.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Song Wang. Yushun Dong, Xiao Huang, Chen Chen, and Jundong Li. Faith: Few-shot graph classi- fication with hierarchical task graphs. In IJCAI, pp. 228222282222 2290, 2022.
Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Curgraph: Curriculum learning for graph classification. WwW, pp. 1238-1248, 2021.
Junran Wu, Xueyuan Chen, Ke Xu, and Shangzhe Li. Structural entropy guided graph hierarchical pooling. In ICML, pp. 24017-24030, 2022.
Han Yue, Chunhui Zhang, Chuxu Zhang, and Hongfu Liu. Label-invariant augmentation for semi- supervised graph classification. In NeurlPS, 2022.
Ge Zhang, Zhenyu Yang, Jia Wu, Jian Yang. Shan Xue, Hao Peng, Jianlin Su, Chuan Zhou, Quan Z. Sheng, Leman Akoglu, and Charu C. Aggarwal. misl-discriminative graph neural network for imbalanced graph-level anomaly detection. In NewrIPS, 2022.
Lingxiao Zhao and Leman Akoglu. On using classification datasets to evaluate graph outlier detec- tion: Peculiar observations and new insights. Big Data, 11(3):151-188 2021.
11

---

Published as a conference paper at ICLR 2024
A
APPENDIX
A.1 PROOFS
Proof of Theorem 1. The following lemma is used for the proof.
Lemma 2 (Courant-Fischer Theorem). Let M E Ruxa be a symmetric matrix with eigenvalues In S P2 S ... S Pn- Then,
x. T M
x. Mx
min Ak SCR" (dimddm)mkmsss......
min TÇRn dim((T)=nnk+ h+1 TT
xx
x
where the maximization and minimization are over subspaces and T of
Let A₂(-) denote the i-th eigenvalue of the input matrix, where the eigenvalue is in ascending order according to the index. For symmetric matrix L and A, according to Lemma we have:
x² (L (L+ A)æ
AL + +A)
max TCR" dim (aaa(()))--a) m ME
min
x² x a La:
xe A..
min TCR dim(()==n-itt)) 2ET x+00
max
max
x x x² Læ
a x'x x
min TCR" dim
max #ET
Am()))
x x
(L) + An
Similarly, by employing the other format of Lemma from which it follows that
we can derive (A) (L++A))
max -) AL(L)) S max (A) ||
Hence, we can rewrite the inequality as:
max(1A, A₂ + A]D S |2
Considering the change of Rayleigh Quotient, have:
xt
(L + A x
x La
Σ ly + A)
E (L)
T
TT.
EL
E 57
(y A) X (L))
E
(Ae A) - (L) E3 $3}
max
E a2
<max(>(LL+)) A) (L) & |
Proof of Theorem 2. For simplicity, let be a normalized vector so that the Rayleigh Quotient has the form as xx Læc. Then, we have:
TTTT. La: =x" " La + 5T L xT A5 + 8 Lō x=" Læ:
(x: 5)T L 5) -x-
=2x T L6 + o())
If o()) is small enough, in which case o()) can be ignored, the change is bounded by 2x Lő. O Proof of Proposition 2. The result can be derived by mathematical induction. Let = be the initial case. It is obvious that 17(1) = 1-8
1-3' 1, so n holds. Assume that this proposition holds
for n = k - 1, and the probability of sampling k-th data is p = r7(k 1)/N. Therefore, the expected number after sampling je-th data is:
N N
ryk) = (n 1) + (1 p)( 1) 1))
77 - 1)
12

---

Published as a conference paper at ICLR 2024
Table 2: Ablation study for class-balanced focal loss.
Dinasess
Meniss
ChewyNer CeecwNN-CC
BernNer
BeraNe--C
TVGNN
TVGNN-CB
Gmixap
GMT
GMFECH
ROGNN:3
ROGNN
MCF-7
ALC
F1
D0612
04780
0
0,804
0.6172
0.4784
002255
0.4784
0.778
0.5894
117309
0.5608
0.8055
0,4779
0.479
0.7206
0.4744
0.7670
0.4784
0.7293
0,520
D.85
0,7894
MOLT4
AUC
D4854
0.6500
04875
0.4944
0.4794
0.739
0.4916
0.7574
0.5793
0.6232
0.789
0.4789
0.4814
0.4994
0.213
0331
0,8366
0,7240
PC-3
AUC
F1
0.0511
0.4853
0.853
0.0065
0.4853
0.804
0.6030
0.4853
0.7975
06206
06136
0,7722
0,4852
0,8900
0.6592
0.4852
0.4853
0.7896
0.7877
0.4853
0,7287
03530
0.8782
0,7184
SW-620
AUC
0,6072
0.0081
0.7326
0.3332
0.6202
0,7467
0,7620
0.504
0.8550
R1
0.4898
0.4947
0.4847
0.4847
0.5365
0.5547
0.4844
0.4844
0.4874
0.4847
0.7081
0.7535
NCI-1123
AUC
0.6728
0.0734
0.6114
0,6289
0,7782
0,7810
0.7524
0.6793
0,8030
0,780S
03539
0.8690
0.4860
0.5484
0.4869
0.4860
0.734
0.7314
OVCAR-8
AUC
F1
0.4900
0.6303
0,624
0.4902
0.4868
0,5830
0.5805
0.4868
0,7655
0.5406
0.5938
0,7330
0.5663
0.4869
0.699
0.4869
0.4868
0.7692
0.7713
D.4868
0.7126
03563
0.8799
0.7215
P388
AUC
F1
0,7366
0.7321
0,5656
0.6701
0,500]
0.6694
0.1957
0.557
0,7757
0.5549
0.6516
0.4856
0.6562
0.8:99
0.8633
03583
0.887
0,9023
0.793
S1-295
AUC
F1
0.4871
0.0650
0.4871
0.0670
0.487]
0.6333
0,68122
0.1871
0.7336
0.4935
0.7722
0,5779
0.4866
0.6471
0.1866
0,7070
0.4871
0.7992
0.4871
0.8004
0.7074
03792
0.8825
0,7416
SN12C
AUC
0.0634
0.6014
0,7710
0.2017
0,7919
0,7983
0.8861
0.4972
0.4970
0,4574
0.4874
0.5437
0.5736
0.4871
0.4871
0,4874
0,9875
0.7554
0,7660
UACC2257
ADC
D.6584
0.0645
0.6115
0.6130
0,7410
0.7450
0.6564
0.6897
0.7735
0.7845
0.3337
0.8724
0.4894
0.4933
0.4895
0.4895
0.5375
0,5330
0,4904
0.4904
0.4894
0,4895
0,7058
0,7902
Table 3: Tumor description of the 10 datasets
Datasel MCF-7
MOLT-
PC-3
SWW622
NCT-H23
OVCAR-8
P388
SF-295
SNT2C UACO-257
Tomor
Breast
Leukemia
Prostate
Colon Non-Small Cell Lung
Ovartan
Leukemia Central Nervous System
Rental Mclanoma
1-gh-1
Since we assume that 1)(k- - 1) = 1-3
so we can derive:
rkk) = 1 1- 1- 1 Bk
1-B
1 8
which proves the expected number of samples is 17(k)
1
1-B"
A.2 ABLATION STUDY FOR BLASS-BALANCED FOCAL LOSS
In this set of experiments, we explore the impact of replacing the cross-entropy loss function with the class-balanced focal loss in spectral GNN, Le..ChebyNet (Defferrard et al. (016) and BernNet (He et al. 2021) and GNN models designed for graph classification tasks, i.c., TVGNN-CB (Hansen & BBanchi 2023), Gmixup-CB (Han et al. )022). and GMT-CB (Back et al. 2021 In addition, we introduce RQGNN-3 as a variant of ROGNN that uses the cross-entropy loss instead of the class-balanced focal loss during training. The results of these models are summarized in Table [ As we can see, the class-balanced focal loss does not yield benefits for ChebyNet, BernNet, BG- mixup, and GMT. This further demonstrates that even though tackling the imbalanced problem of datasets, these spectral GNNs and graph classification models fail to capture the underlying proper- ties of anomalous graphs. For TVGNN, balsneel focal loss improves the performance some extent. However, it still falls way behind models specifically designed for graph-level anomaly de- tection. This observation highlights the differences between graph classification and graph-level anomaly detection tasks. When comparing RQGNN-3 with RQGNN, we notice the performance drops on almost all dltasetss, This indicates that the balance focal loss can indeed benefit graph anomaly detection models.
A.3 BASELINES AND DATASETS
Baselines. The first group is Spectral GNNs;
ChebyNet (Defferrard et al. 2016): a GNN with Chebyshev polynomials as convolution kernels;
2021): a GNN which utilizes Bernstein approximation of spectral filters. BernNet (He et al.
The second group is GNN models designed for graph classification:
GMT (Back et al. 2021 : a GNN with multi-head attention-bast global pooling layer to capture
the interactions between nodes and topology of graphs;
Gmixup (Han al. 2022): GNN with data augmentation to improve the robustness;
TVGNN (Hansen& Bianchi 2023): a GNN with knowledge distillation of node representations.
The third group is SOTA GNN models for graph-level anomaly detection:
13

---

Published as a conference paper at ICLR 2024
Table 4: Statistics of 10 real-world datasets, where n. the number of normal graphs, na is the number of anomalous graphs, h m is the average number of edges, and F is the number of attributes.
nha ,,**. is the anomalous ratio, ñt is the average number of nodes,
Dataset
MCF-7
MOLT-4
PC-3
SW-620
NCI-H23
OVCAR-8
P388
SF-295
SNI2C
UACC257
25476
36625
25941
38122
38296
38437
39174
38246
38049
38345
Th
2294
3140
1568
2410
2057
2079
2298
2025
1955
1643
0.0826
0.079
0.057
0.0595
0.051
0.0513
0.0554
0.0503
0.0489
0.0411
26.4
26.1
26.36
26.06
26.07
26.08
22.11
26.06
26.08
262.09
28.53
28.14
28.49
28.09
28.1
28.11
23.56
28.09
28.11
28.13
F
46
64
45
65
65
65
72
65
65
64
OCGIN Zhao & Akoglu
2021 I: the first GNN to explore graph-level anomaly detection;
OCGTL Qiu et al. 2022): a GNN with graph transformation learning:
GLocalKD (Ma et al. 2022); : a GNN with the random distillation technique;
HimNet (Niu et al.
2023): GNN with a hierarchical memory framework to balance the anomaly-
related local and global information;
iGAD Zhang et al., 2022): a GNN with a substructure- aware component to capture topological features and node-aware component capture node features.
The datasets used our experiments are collected from PubChem by TUDataset (Morris et al., 2020). According to PubChem, these 10 datasets provide information on the biological activi- ties of small molecules, where nodes denote atoms the chemical compounds, and edges represent the chemical bonds between two atoms. These datasets contain the bioassay records for anticancer screen tests with different cancer cell lines. Each dataset belongs to a certain type of cancer screen with the outcome active or inactive. We treat inactive chemical compounds as normal graphs and active ones as anomalous graphs. In addition, the attributes are generated from node labels using one-hot encoding.
Datasets.
The statistics these 10 real-world datasets are shown in Table4 and Table provides brief tumor description of these datasets.
A.4 DATASETS BEYOND BIOGRAPHYY DOMAIN
Table 5: Datasets beyond the biography domain
Datasets
Metries
ChebyNet
BernNet
TVGNN
GMT
HimNet
iGAD
ROGNN
AUC
0.6192
0.6136
0.5000
0.5063
0.5129
0.7385
0.9378
COLORS-3
F1
0.4764
0.4764
0.4764
0.4764
0.5934
0.5301
0.7640
AUC
0.8369
0.8549
0.8455
0.8234
0.6656
0.7346
0.8808
DBLP.v1
F1
0.5472
0.4877
0.6449
0.4877
0.6133
0.6648
0.7709
AUC
0.6500
0.6486
0,5000
0,5000
0.4522
0,7630
0.9421
COLORS-3-ind
F1
0.3710
0.3710
0.3710
0.3710
0.4707
0.6674
0.8423
Although the main application of graph-level anomaly detection is typically focused on detecting chemical compounds, there are still applications in other domains such as social networks. However, due to the lack of datasets specifically collected for graph-level anomaly detection in other domains, we construct new datasets and conduct experiments on them. To be comprehensive, we use two graph classification datasets to evaluate our RQGNN, one COLORS-3 (Knyazev et al., 2019), which is synthetic dataset in TUDataset repository (Morris et al. 2020), and the other is DBLP.v1 Pan et al. 2013) which is a social network dataset as classified in TUDataset.
Specifically, we first conduct experiments on the COLORS-3 dataset, which contains 11 classes. We use 10 classes to form normal graphs and use the remaining class as anomalous graphs.
Then, we conduct additional experiments in the social network domain using the DBLP_v1 dataset, which is bell-balanced social network classification dataset in the field computer science. In this dataset, each graph denotes research paper belonging to either DBDM (database and data mining) or CVPR (computer vision and pattern recognition) field, where each node denotes paper ID or a keyword and each edge denotes the citation relationship between papers or keyword relations in the
14

---

Published as a conference paper at ICLR 2024
title. To create graph-level anomaly detection dataset, randomly sample 5% of one class as the anomaly class and use the other class as the normal class.
In addition, despite primary focus not being the out-of-distribution task, still conduct additional experiments to evaluate the performance of our proposed model. use a modified COLORS-3 dataset construct COLORS-3-ine dataset. We randomly select two classes out-of- distribution graphs and the remaining classes serve as normal graphs. One of the out-of-distribution classes is included in the training and validation sets, while the other added to the testing
Table 5 presents the results of this set of experiments. Compared with other baseline models, our proposed RQGNN achieves significant improvements in both AUC and F1 scores in these datasets, which demonstrates the effectiveness of our ROGNN in detecting anomalies beyond the application considered.
A.5 ALGORITHM
Algorithm 1: RQL
Input: (Ga), where i 1,
Output: HRQ RQ
for i = to do
X +- MIP(G;.X))
RQ + diag( XTLX
)
XTX RRQ MLP(RQ):;
(HR)): ): + niqq
Return H RQ:
Algorithm 2: CWGNN with RQ-pooling
Input: {G:]. where i 1, ".
Output: HG
for i 1 to n do
X + MLP(G,,X))
RQ + diag
8 LX
X"LX X
h Att f- 0; for node j in G2 do
hj + (ONCAT((1(L)))), (
6
a₂ +- RQ hji
h Ast + aajh;;
hG
o (h Amt);
ALl
(HG Att); h Atti
10
11 Return HG
AtL
Algorithm 3: ROGNN
Input: {G:}. where i = -1,...,7
Output: H
H
RQQ + RQL((G;;);
HG +- CWGNN with RQ-pooling((G.)):
HG CONCAT C.:):
Return HG:
As described in Section RQGNN contains two components, RQL and Chebyshev Wavelet GNN with RQ-pooling. The ROL leams the explicit representation of the Rayleigh Quotient graphs while the Chebyshev Wavelet GNN with RQ-pooling learns the implicit representation of graphs
15

---

Published as a conference paper at ICLR 2024
guided by the Rayleigh Quotient. After getting the two representations, combine them to obtain the final representation of graphs.
A.6
PARAMETER ANALYSIS
MCF-7
SF-295
SN12C
UACC257
0.8
FI Score
FI Score
0.75
0.75
0.7
0.7
0.65
2.5
0.65
.99
.999
9999
.99999
gammaa
beta
(a) Varying 7
(b) Varying 3
Figure 4: Varying the y and B3.
Other than the hyperparameters for the Chebyshev Wavelet GNN with RQ-pooling, we also investi- gate the impact of varying ? and |3 in the class-balanced focal loss on the performance of RQGNN. The results are shown in Figure 4 As we can see, when the y is set to 1.5, RQGNN achieves relatively satisfactory performance on these four datasets. Meanwhile, ROGNN relatively satis- factory when 3 is set to 0.999, Hence, we choose 1.5 for yy and 0.999 for 3 in our experiments on all datasets.
A.7 PERTURBATION ON SN12C
Normal Graphs
Anomalous Grapks
Normalized Frequency
Normalized Frequency
Normalited Frequency
0.2
0.2
0.2
0.1
0.1
0.1
0.4
0.6
0.2
0.4
0.6
0.2
0.4
0.6
Rayleigh Quotient
Rayleigh Quotient
Rayleigh Quotient
(a) 5% perturbation
(b) 10% perturbation
(c) 15% perturbation
Normalized Frequency
Normalized Frequency
0.2
0.2
0.4
0.6
0.8
0.4
0.6
0.8
Rayleigh Quotient
Rayleigh Quotient
(d) 20% perturbation
(e) 25% perturbation
Figure 5: Normalized Rayleigh Quotient distribution perturbated SN12C.
Recap from Section 3.1 that Theorem D and Theorem 2 show that the change of the Rayleigh Quo- tient can be bounded given small perturbation on graph signal æ and graph Laplacian L. In this section, we further conduct experiments to explore how much perturbation detectable by the pro- posed RQGNN. We use SN12C to create 5 new synthetic datasets. Specifically, we first randomly select 5% normal graphs to perform perturbations. For these graphs, each edge is changed with prob- ability where p 0.05, 00 0.15, 0.20, 0.25. Then use these perturbed samples anomalous graphs and all the remaining 95 % normal graphs in SN12C to construct these five new datasets. The corresponding normalized Rayleigh Quotient shown in Figure
As we can see from Figure 6 even with a perturbation probability as low as 0.05, ROGNN can still achieve reasonable result. As the perturbation probability increases to 0.15, our RQGNN achieves an AUC score around and an Fl score exceeding 0.9, which clearly demonstrates that RQGNN accurately distinguish the two classes.
16

---

Published as a conference paper at ICLR 2024
AUC
F1
Performance
0.9
0.8
0.7
0.055
0.1
0.15
0.2
0.25
Perturbation
Figure 6: Performance of SN12C with different ratios of perturbation.
A.8 DISTANCE RATIO BETWEEN DIFFERENT CLASSES
We calculate pairwise inter-distances and pairwise intra-distances for the normalized Rayleigh Quo- tient values of two classes. To keep consistency with the experiments shown Figure [I. we still construct 10 equal-width bins. Subsequently, we report the results of inter-distances divided by intra-distances of the normalized Rayleigh Quotient for two classes, respectively. The detailed ex- perimental results are presented in Table 6 where d; is the inter-distance between normalized values of Rayleigh Quotient of different classes, do the intra-distance between normalized values of Rayleigh Quotient values of anomalous graphs, and dn is the intra-distance between normalized values of Rayleigh Quotient values of normal graphs.
Table 6: Distance ratio between different classes of different datasets.
Dasasets
Rañi
MCF-7
di fdn
4,
2,1631
2.7014
5,2946
1.0262
1.1659
4.2198
5,4295
4,5321
7,5492
3,5399
3,4830
1,7034
0.8756
1.8955
0.9013
1.3387
17.6960
7,8023
MOLT-4
d.fdn
3,4383
7,0977
0,4858
36.840
14,8213
7,1185
3.8252
2,2033
1,197
1.8906
0,2170
1,9966
4, /4
188.9639
4.8383
0.56m
4.4561
16,9500
4.5858
2.2441
0.7786
0.9906
7.2704
PC-3
2,7716
8.9202
0.8078
4.309
6,1323
11,7506
4,3151
20075
1,6180
6.4001
4./da
6,4050
22.7
2,4499
2,3840
50.2978
20.2884
299.8220
34,37006
6.0213
1.3747
1.3095
7.0025
NC1-123
dddd,
d./d.
6.4151
7,6155
0,1815
9,6685
34,4588
13,3045
6.8839
2,150
0.3466
1.4374
38. 36.5
6.3351
DVCAR-8
d./da
d,7da
2.6150
4,9951
19.767
299819
10,5372
1.2632
14,8965
8.2019
103,3491
19,3335
35,3553
3.9137
4,6184
2.1373
0.8568
1,7530
0.8122
1.6122
113.692Y
6,51588
0.4619
0.7943
11.0056
0.2758
1,1250
fd
2,0826
6,9907
1,1292
2.1624
4,6504
0.8967
10.5379
3,2803
1,3869
8,633
SF-295
d,
11,2380
5.22%
0.2051
81,8188
3,7652
3,7051
2,4429
0.6470
0.9760
17,3201
d./dm
12,9510
1.2385
7.4618
SN12C
d.ddn
4,7da
3.0953
5,2410
8.3300
2,4437
16.7566
0.5253
17.5996
8.9315
114.7633
11,8474
30.4557
6.2311
1,9101
5.3002
0.6942
1.2671
0,7775
1.4012
114,3876
5,6286
UACC257
4,/d.
0.2014
8.8750
0.9534
1.3980
38.5248
2,4816
25.3848
52,8003
4.7289
1,8897
2.1000
6.1325
Additionally, we present the distance ratios between different classes of different perturbations (re- cap from Section A.7 on SN12C in Table
Table 7: Distance ratio between different classes of different perturbations
Duiisets
Rano
bing
bing
bing
bing
bing
d. /d
1.335
0.0833
0.8025
2,1850
13:6557
0.1622
1.3157
29775
0.785
1.0092
5% pertursation
d
0.6507
2,6996
2,8406
4,8837
9.9019
1,1670
1.3218
1.1467
0.6322
8.0939
10% perturisation
d,/da
6,/4n
23.2792
1,2710
2,1388
10.3101
2,2364
37.7347
164515
8.5852
1.0900
1,0230
2.7819
25552
6,6939
2
9.5345
40627
9.0571
15% perturbation
4,/da
d./da
24,8115
2,2010
5,0908
0.3802
18,0752
4.8122
23,4784
27.4591
11,9045
16,0009
18211
L88243
3,4373
5,2649
35.0538
3.6316
30019225
6.2111
15,2569
0.4652
20% perturistiion
d:/dg
d,/da
16.477
2.7813
23.0458
18:3563
3.1912
43.5881
25,3389
14.4079
2,6532
3,3765
33,8295
4.8426
12.6984
5 84888
30,6888
8,5227
27,8905
0.4820
25% perturisation
d,7da 20.5731
d,/dn
T.0082
6,9359
29,0320
19,3459
5,1918
7,7015
16.7929
8.3995
23,0523
14,150
7.9395
31.4415
0.4837
As we can see, there is no consistent pattern in the numerical data presented in the two tables. Nevertheless, RQGNN successfully learns the Rayleigh Quotient of the graphs and effectively dis- tinguishes between the two classes. This demonstrates that a consistent pattern in the ratio is not necessary for accurate classification. The key to differentiating between the classes is capturing and leveraging such gaps certain dimensions, rather than relying on consistent patterns in the data.
17

---

Published as a conference paper at ICLR 2024
A.9 RAYLEIGH QUOTIENT DISTRIBUTION ON OTHER DATASETS
To further demonstrate the Rayleigh Quotient can be applied to any graph-level anomaly detection datasets, we calculate the normalized Rayleigh Quotient distribution of all the other datasets. which are shown in Figures sample size, the normalized Rayleigh Quotient distribution of each class exhibits consistent pattern across different sample sets. Besides, the normalized Rayleigh Quotient distribution of anomalous graphs and that of normal ones are statistically distinct from each other on all datasets. These results again demonstrate that the Rayleigh Quotient can reveal the underlying differences between normal and anomalous graphs.
15 As we can observe, for each dataset, regardless of the variations in the
Normal Graphs
Anomalous Gruphs
Normalized Frequency
Normalized Frequency
Normalized Frequency
0.2
0.2
0.2
0.1
0.1
0
0.4 0.6
0.8
0.2
0.4
0.6
0.8
0.2 0.4 0.6
0.8
Rayleigh Quotient
Rayleigh Quotient
Rayleigh Quotient
(a) na 573, n. 6369
(b) na
1147, nr
12738
(c) na 2294, nhe 25476
Figure 7: Normalized Rayleigh Quotient distribution MCF-7.
Normalized Frequency
Normalized Frequency
Normalized Frequency
0.2
0.2
0.2
0.1
0.1
0
0.2
01.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Rayleigh Quotient
Rayleigh Quotient
Rayleigh Quotient
(a) flg 785, Thy 9156
(b) na
1570, 70
18312
(c) n2 -3140, nh 36625
Figure 8: Normalized Rayleigh Quotient distribution MOLT-4
Normalized Frequency
Normalized Frequency
Normalized Frequency
0.2
0.2
0.1
0.1
01.4 0.6
0.3
0.2
0.6
0.2
0.6
0.8
Rayleigh Quatient
Rayleigh Quotient
Rayleigh Quotient
(a) Tla
392, nt,,
6485
(b) Yd.,
784, Y4,,
12970
(c) Yd, 1568, Yo,, 25941
Figure 9: Normalized Rayleigh Quotient distribution PC-3.
18

---

Published as a conference paper at ICLR 2024
Normal Graphs
Anomalous Grapha
Normalized Frequency
Normalized Frequency
Normalized Frequency
0.2
0.2
0.1
0.1
0.2
01.4
0.6
0.8
0.2
0.6
0.2
0.6
0.8
Rayleigh Quotient
Rayleigh Quotien!
Rayleigh Quotient
(a) fla
602, Iin
9530
(b) Yla
1205, Via
19061
(c) Yia 2410, Yén 38122
Figure 10: Normalized Rayleigh Quotient distribution SW-620.
Normalized Frequency
Normalized Frequency
Normalized Frequency
0.2
0.2
0.2
0.1
0.1
0.1
0
01.4
0.6
0.8
0.2
11.4
0.6
0.8
0.2
0.4
0.6
0.8
Rayleigh Quotient
Rayleigh Quotient
Rayleigh Quotient
(a)
574,
9793
(b)
1149,
19587
(c) T2g 2229,,
39174
Figure 11: Normalized Rayleigh Quotient distribution on P388
Normalized Frequency
Normalized Frequency
Normalized Frequeney
0.2
0.2
0.2
0.1
0.1
0
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Rayleigh Quotient
Rayleigh Quotient
Rayleigh Quotient
(a) ng 514, nr 9574
(b) na 1028, 74
19148
(c) ng 2057, ni 38296
Figure 12: Normalized Rayleigh Quotient distribution NCI-H23.
Normalized Frequency
Normalized Frequency
Normalized Frequency
0.2
0.2
0.1
0.1
0.1
0.4 0.6
0.8
0
0.2
0.6
0.2 0.4 0.6
0.8
Rayleigh Quorient
Rayleigh Quotient
Rayleigh Quotient
(a) na 519, n., 9609
(b)
1039,
19218
(c) n. 2079, 38437
Figure 13: Normalized Rayleigh Quotient distribution on OVCAR-8.
Normalized Frequency
Normatized Frequency
Normalized Frequency
0.2
0.2
M
0.2
0.1
0.1
0 0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4 0.6
0.8
Rayleigh Quotient
Rayleigh Quotient
Rayleigh Quotient
(a) na 506, n., = 9561
(b) na.
1012, n2,
19123
(c) n. 2025, nu, 38246
Figure 14: Normalized Rayleigh Quotient distribution on SF-295.
Normalized Frequency
Normalized Frequency
Normalized Frequency
0.2
0.2
0.1
0.1
0.4 0.6
0.8
0.2
0.6
0.8
0.2
0.6
0.8
Rayleigh Quotient
Rayleigh Quotient
Rayleigh Quotient
(a) Phe 410, n..
9586
(b)
821,
19172
(c) n..
1643, 38345
Figure 15: Normalized Rayleigh Quotient distribution on UACC257.
19


Reviews:
[{"review_id": "p4Mp4BhNnd", "reviewer": "Reviewer_qWnD", "summary": "This paper considers the problem of detecting anomalies in graphs.  Related work in GNNs is reviewed, and it is argued that the Rayleigh quotient (RQ) supplies feature information that is useful and hasn’t been adequately explored.  This is based on some data exploration of a chemical dataset.  The authors set up a learning problem that incorporates the RQ, and incorporates several pieces including graph wavelets and using the RQ as an attention mechanism.  Experiments compare baseline GNNs, including GNN classifiers and GNN anomaly detectors, and show the benefits of the proposed approach for the datasets studied.", "questions": "Given the large literature on RQ’s it seems likely that eqn (1) is well known?\n\nLemma 1 and leading to eqn (4), using L – I_n to compute is from Rivlin or some other reference?\n\nSection 4.5 (and throughout the paper).  “Rayleigh Quotient is an intrinsic characteristic of the graph-level anomaly detection task.”  Should this be altered to say “for the application studied”?  How general is the claim?\n\nIsn’t the anomaly for this application the same as an “out of distribution” test?  \n\nIt seems this area of study would benefit from good baseline data sets.  For example, for what random classes of graphs is the RQ approach well founded?  This could be studied through simulation and theory.  \n\nSection 4.1: Perhaps you could say a little more about “various chemical compounds and their reactions to different cancer cells”, and how a chemical leads to a graph?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper is well written and provides a good statement of the problem, prior GNN related work, and the motivation for the approach.   Exploring the Rayleigh quotient in this context is well motivated and interesting.\n\nThe paper has some nice innovation, incorporating RQ pooling for example, and the use of RQ as a means of attention in the context of the graph wavelet.  The use of wavelets seems well motivated for this “step change” problem, when the change is an anomaly.\n\nThe comparisons with other GNN-based methods are well documented and show the benefit of the proposed method for the datasets considered.  The hyperparameter choices are well described, and the ablation studies are useful indicators.", "weaknesses": "The relation between Rayleigh quotient and perturbation is well known and studied, for example, in physics.  For example:  Pierre, C. (December 1, 1988). \"Comments on Rayleigh’s Quotient and Perturbation Theory for the Eigenvalue Problem.\" ASME. J. Appl. Mech. December 1988; 55(4): 986–988. When the vector is close to an eigenvector, then the RQ has a value that is close to the corresponding eigenvector.  There is also the Rayleigh-Schrödinger procedure that yields approximations to the eigenvalues and eigenvectors of a perturbed matrix by a sequence of successively higher order corrections to the eigenvalues and eigenvectors of the unperturbed matrix.\n\nThe paper explores an important application and datasets, and experimentally shows that the RQ provides a useful feature for detecting change.  However, it isn’t clear how general this is beyond the application considered.  \n\nThe anomaly here is a change detector between the baseline distribution (the normal graph class), and some deviation from this graph.  Apparently for this data there is no clear class after change (so it isn’t surprising that the graph classifiers don’t work well).", "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": "", "extra_scores": {}}, {"review_id": "DXN6FQ1PJj", "reviewer": "Reviewer_oJCz", "summary": "In this paper, the authors introduce spectral analysis and identify significant differences in the spectral energy distributions between anomalous and normal graphs, leading to the development of the Rayleigh Quotient Graph Neural Network (RQGNN). This approach combines the explicit capture of the Rayleigh Quotient and implicit spectral exploration, outperforming existing methods in comprehensive experiments.", "questions": "1. Can the Rayleigh Quotient Learning be used to detect node anomalies?\n2. The authors should show the ratio between normal and anomalous graphs. Are they balanced or not?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well-organized and easy to follow.\n2. Investigate Rayleigh Quotient Learning to graph anomaly detection is promising.\n3. The experiment demonstrates the effectiveness of the proposed method.", "weaknesses": "1. The reviewer thinks that the motivation and rationale of Rayleigh Quotient Learning should emphasized. It is a quite general problem that “existing methods fail to capture the underlying properties of graph anomalies”. \n2. An algorithm describing the training process is required.\n3. From the objective function in Section 3, the method proposed in this paper is a supervised method. This implies that some of the comparisons in the experiments are unfair because many graph-level anomaly detection methods are fully unsupervised to my knowledge, e.g., OCGIN, OCGTL, GlocalKD, etc.\n4. The authors only test on chemical datasets in this paper, while there are other data types that are constructed as graphs, such as social networks.\n5. It seems that the proposed RQGNN fluctuates a lot with the change of hyperparameters and shows instability. The authors should explain the reasons for this observation.\n6. The impact of hyperparameters on loss function is encouraged to be explored.\n7. From the ablation study results, the performance of RQGNN does not consistently outperform the other degradation models, and their performance is quite close in many cases. It seems the improvement from the several proposed components is somewhat limited.", "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": "", "extra_scores": {}}, {"review_id": "USbvd2yjQC", "reviewer": "Reviewer_X1rz", "summary": "This paper proposes the first spectral GNN-based graph-level anomaly detection method named RQGNN. Considering the disparity in the accumulated spectral energy between the anomalies and normal graphs, RQGNN leverages the Rayleigh Quotient learning component to capture the accumulated spectral energy of graphs. In addition, RQGNN also proposes the Chebyshev Wavelet GNN to represent nodes. RQ-pooling that regards the Rayleigh Quotient coefficient as the node importance score will be employed to obtain graph representation. The final graph representation is the concatenation of the Rayleigh Quotient learning component and the Chebyshev Wavelet GNN. Finally, class-balanced focal loss is introduced to optimize RQGNN and obtain graphs’ binary labels.", "questions": "1. How about the graph-level anomaly detection performance of ChebyNet, BernNet, GMT, Gmixup, and TVGNN if the loss function is replaced by the class-balanced focal loss?\n2. What is the ratio between the normal and anomalous graphs utilized during model training?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1.\tThe topic of graph-level anomaly detection focused by this paper is an interesting but under-explored research area.\n2.\tThis paper is the first to consider solving the problem of graph-level anomaly detection from the perspective of spectral graph. Before this, leveraging graph wavelet to identify anomalous nodes within a single graph has achieved empirical successes [1].\n3.\tThis paper proposes a sufficient survey on graph anomaly detection.\n\n[1] Tang et al. Rethinking Graph Neural Networks for Anomaly Detection. ICML 2022.", "weaknesses": "1.\tThe insight of this paper seems to be on shaky ground. Figures 1 and 4-12 do not clearly show the statistical difference between anomalous graphs and normal graphs with respect to Rayleigh Quotient. Detailed text description about the ''significant disparity\" between two classes is necessary but not found on the current version. (This is the main reason why I currently tend to reject this paper.)\n2.\tI recommend briefly introducing Rayleigh Quotient in the introduction or preliminaries section.\n3.\tIn page 4,  authors wrote  \"If the graph Laplacian $\\mathbf L$ and graph signal $\\mathbf x$ of two graphs are close, then their Rayleigh Quotients will be close to each other and these two graphs will highly likely belong to the same class.\" I tend to think this statement is correct, but it seems not applicable for anomalies. Anything that is different from normal can be regarded as an anomaly, but we actually cannot get training data that can represent the full picture of anomalies. In addition, two anomalous graphs can also be very different. This paper uses two-class datasets for experiments, but what will be the result if we regard the third class that has never appeared in the training set as anomalies to test the proposed model?\n4.\tIn page 5, authors wrote \"However, as analyzed in Section 3.1, to capture the spectral properties of anomalous graphs, it is necessary to consider the spectral energy with respect to each eigenvalue.\" But, the reason for using graph wavelet convolution is still unclear.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)