Rayleigh Quotient Graph Neural Networks for Graph-level Anomaly
  Detection
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.
Xiangyu Dong, Xingyi Zhang, Sibo Wang
# Rayleigh Quotient Graph Neural Networks for Graph-level Anomaly Detection

###### Abstract

Graph-level anomaly detection has gained significant attention as it finds many applications in various domains, such as cancer diagnosis and enzyme prediction. However, existing methods fail to capture the underlying properties of graph anomalies, resulting in unexplainable framework design and unsatisfying performance. In this paper, we take a step back and 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 for graph-level anomaly detection, providing a new perspective on exploring the inherent spectral features of anomalous graphs. Specifically, we introduce a novel framework that consists of 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.

## 1 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 deploying GNNs (Kipf and 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 to 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., 2022; 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 et al., 2022) and FAITH (Wang et al., 2022) incorporate node features with topological characteristics of graphs to generate graph representations. Meanwhile, due to the limitations of the average or sum pooling function in 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. With this connection, we further empirically show that the Rayleigh Quotient distributions of normal graphs and anomalous graphs follow different patterns. In particular, we first
randomly sample \(n_{a}\) anomalous graphs and \(n_{n}\) 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 calculate 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. Figure 1 reports the Rayleigh Quotient distribution on the SN12C dataset, and the results on other datasets can be found in Appendix A.4. 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, it 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. Additionally, as 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.

Motivated by the observation and theoretical analysis, in this paper, we propose RQGNN, a Rayleigh Quotient-based 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 a multi-layer perceptron (MLP) to generate the representation of each graph, aiming to capture explicit differences between anomalous and normal graphs guided by their Rayleigh Quotient. Secondly, to 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 information in the graph data. Besides, to alleviate the drawbacks of existing pooling techniques in graph-level anomaly detection, we introduce a powerful spectral-related pooling function called RQ-pooling. Furthermore, we address the challenge of imbalanced data in graph-level anomaly detection via a class-balanced focal loss. The final graph embedding is the combination of representations 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.

In our experiments, we evaluate RQGNN against 10 alternative frameworks across 10 datasets. Extensive experiments demonstrate that our proposed framework consistently outperforms spectral GNNs and the state-of-the-art (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 underlying 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 real-world graph datasets, demonstrating the effectiveness of RQGNN.

Figure 1: Normalized Rayleigh Quotient distribution on SN12C.
## 2 Preliminaries

**Notation.** Let \(G=(\mathbf{A},\mathbf{X})\) denote a connected undirected graph with \(n\) nodes and \(m\) edges, where \(\mathbf{X}\in\mathbb{R}^{n\times F}\) is node features, and \(\mathbf{A}\in\mathbb{R}^{n\times n}\) is the adjacency matrix. We set \(\mathbf{A}_{ij}=1\) if there exists an edge between node \(i\) and \(j\), otherwise \(A_{ij}=0\). Let \(\mathbf{D}\) be the diagonal degree matrix, the Laplacian matrix \(\mathbf{L}\) is then defined as \(\mathbf{D}-\mathbf{A}\) (regular) or as \(\mathbf{I}_{n}-\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}}\) (normalized), where \(\mathbf{I}_{n}\) is an \(n\times n\) identity matrix. The Laplacian matrix can be eigen-decomposed as \(\mathbf{L}=\mathbf{U}\mathbf{\Lambda}\mathbf{U}^{T}\), where the diagonal matrix \(\mathbf{\Lambda}\) consists of real eigenvalues (graph spectrum).

Next, we 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., 2016) and can be viewed as graph signal processing models. It has drawn much attention in the graph learning community. For instance, ChebyNet (Defferrard et 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-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 performance flip of several methods on graph classification datasets. After that, OCGTL (Qiu 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 a 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-aware 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.

**Graph Classification.** Graph classification models can also be considered as a general framework for our task. GMT (Baek et al., 2021) points out that a simple sum or average pooling function is unlikely to fully collect information for graph classification. The authors propose a multi-head attention-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 generalization and robustness of GNN models. Moreover, TVGNN (Hansen & Bianchi, 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.

## 3 Our Method: RQGNN

The observation in Section 1 highlights the differences between the Rayleigh Quotient distribution of anomalous and normal graphs. In Section 3.1, we further provide a theoretical analysis of the 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 a powerful spectral-related pooling function called RQ-pooling in Section 3.3. Section 3.4 elaborates on the design of class-balanced focal loss.
### Rayleigh Quotient and Spectral Analysis

As described in Section 2, the regular Laplacian matrix can be decomposed as \(\mathbf{L}=\mathbf{U}\mathbf{\Lambda}\mathbf{U}^{T}\), where \(\mathbf{U}=(\mathbf{u}_{1},\mathbf{u}_{2},...,\mathbf{u}_{n})\) represents orthonormal eigenvectors and the corresponding eigenvalues are sorted in ascending order, i.e. \(\lambda_{1}\leq...\leq\lambda_{n}\). Let \(\mathbf{x}=(x_{1},x_{2},...,x_{n})^{T}\in\mathbb{R}^{n}\) be a signal on graph \(G\). Then \(\mathbf{\hat{x}}=(\hat{x_{1}},\hat{x_{2}},...,\hat{x_{n}})^{T}=\mathbf{U}^{T}\mathbf{x}\) is the graph Fourier transformation of \(\mathbf{x}\). Following the definition in Horn & Johnson (2012), we define the Rayleigh Quotient as \(\frac{\mathbf{x}^{T}\mathbf{L}\mathbf{x}}{\mathbf{x}^{T}\mathbf{x}}\), where \(\mathbf{L}\) represents the Laplacian matrix of graph \(G\) and \(\mathbf{x}\) is a signal on graph \(G\). The following two theorems show that the change of the Rayleigh Quotient can be bounded given a small perturbation on graph signal \(\mathbf{x}\) and graph Laplacian \(\mathbf{L}\), and proofs can be found in Appendix A.1.

**Theorem 1**.: _For any given graph \(G\), if there exists a perturbation \(\mathbf{\Delta}\) on \(\mathbf{L}\), the change of Rayleigh Quotient can be bounded by \(||\mathbf{\Delta}||_{2}\)._

**Theorem 2**.: _For any given graph \(G\), if there exists a perturbation \(\mathbf{\delta}\) on \(\mathbf{x}\), the change of Rayleigh Quotient can be bounded by \(2\mathbf{x}^{T}\mathbf{L}\mathbf{\delta}+o(\mathbf{\delta})\). If \(\mathbf{\delta}\) is small enough, in which case \(o(\mathbf{\delta})\) can be ignored, the change can be further bounded by \(2\mathbf{x}^{T}\mathbf{L}\mathbf{\delta}\)._

Theorems 1-2 provide valuable guidance in exploring the underlying spectral properties behind anomalous and normal graphs based on the Rayleigh Quotient. Recap from Section 1 that the normalized Rayleigh Quotient distribution of graphs with the same class label statistically exhibits a similar pattern on different sample sizes. 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. 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 a spectral-related component into our framework. Let \(\hat{x}_{k}^{2}/\sum_{i=1}^{n}\hat{x}_{i}^{2}\) denote the spectral energy of \(\lambda_{k}\). Although this distribution provides valuable guidance for measuring the graph spectrum in mathematics, it is not suitable for GNN training due to the time-consuming eigendecomposition 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 \(\sum_{j=1}^{k}\hat{x}_{j}^{2}/\sum_{i=1}^{n}\hat{x}_{i}^{2}\) denote the accumulated spectral energy from \(\lambda_{1}\) to \(\lambda_{k}\). According to previous work (Li et al., 2022; Luan et 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 spectral energy from \(\lambda_{k}\) to \(\lambda_{n}\). For any \(t\in[\lambda_{k},\lambda_{k+1})\), where \(1\leq k\leq n-1\), we denote \(E(t)=1-\sum_{j=1}^{k}\hat{x}_{j}^{2}/\sum_{i=1}^{n}\hat{x}_{i}^{2}\) as the high-frequency energy. Then we can derive:

\[\int_{0}^{\lambda_{n}}E(t)dt=\frac{\sum_{j=1}^{n}\lambda_{j}\hat{x}_{j}^{2}}{ \sum_{i=1}^{n}\hat{x}_{i}^{2}}=\frac{\mathbf{x}^{T}\mathbf{L}\mathbf{x}}{\mathbf{x}^{T}\mathbf{x}}. \tag{1}\]

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 1 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.

### Rayleigh Quotient Learning Component

Motivated by Theorems 1-2 and the observation in Section 1, a simple yet powerful component is introduced to capture different trends on the Rayleigh Quotient. Specifically, we first use a two-layer MLP to obtain the latent representation of each node. Then, we calculate the Rayleigh Quotient for each graph as the explicit learning component in our RQGNN. Let \(\mathbf{\tilde{X}}\) denote the node features
after the feature transformation, then the Rayleigh Quotient can be expressed as:

\[RQ(\mathbf{X},\mathbf{L})=diag\left(\frac{\mathbf{\tilde{X}}^{T}\mathbf{L}\mathbf{\tilde{X}}}{\mathbf{ \tilde{X}}^{T}\mathbf{\tilde{X}}}\right), \tag{2}\]

where \(diag(\cdot)\) denotes the diagonal entries of a square matrix. Finally, we employ another two-layer MLP to get the Rayleigh Quotient representation of the entire graph:

\[h_{RQ}^{G}=\text{MLP}\left(RQ(\mathbf{X},\mathbf{L})\right). \tag{3}\]

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 comprehensive information for graph-level anomaly detection. The details are presented as follows.

### 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 motivates us to design a spectral GNN for learning graph representations. Even though existing spectral GNNs, e.g., ChebyNet (Defferrard et al., 2016) and BernNet (He et al., 2021), 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 our 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). 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. 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-RQ, a novel component that effectively learns the inherent spectral representations of different graphs.

**CWGNN.** Following Hammond et al. (2011), we define \(\psi\) as the graph wavelet and a group of \(q\) wavelets can be denoted as \(\mathbf{W}=(\mathbf{W}_{\psi_{1}},\mathbf{W}_{\psi_{2}},\cdots,\mathbf{W}_{\psi_{q}})\). Each wavelet is denoted as \(\mathbf{W}_{\psi_{i}}=\mathbf{U}g_{i}(\mathbf{\Lambda})\mathbf{U}^{T}\), where \(g_{i}(\cdot)\) is the kernel function defined on \([0,\lambda_{n}]\) in the spectral domain. Then, the general wavelet GNN of a graph signal \(\mathbf{x}\) can be expressed as:

\[\mathbf{W}\mathbf{x}=\left[\mathbf{W}_{\psi_{1}},\mathbf{W}_{\psi_{2}},\cdots,\mathbf{W}_{\psi_{q }}\right]\mathbf{x}=\left[\mathbf{U}g_{1}(\mathbf{\Lambda})\mathbf{U}^{T}\mathbf{x},\mathbf{U}g_{2}( \mathbf{\Lambda})\mathbf{U}^{T}\mathbf{x},\cdots\mathbf{U}g_{q}(\mathbf{\Lambda})\mathbf{U}^{T}\mathbf{x} \right].\]

However, calculating graph wavelets requires decomposing the graph Laplacian, resulting in expensive computational costs. To achieve better computational efficiency, we employ Chebyshev polynomials to calculate approximate wavelet operators. The following lemma shows that the Chebyshev series can be used to represent any function.

**Lemma 1** (Rivlin (1974)).: _There always exists a convergent Chebyshev series for any function \(f(t)\):_

\[f(t)=\frac{1}{2}c_{0}+\sum_{k=1}^{\infty}c_{k}T_{k}(t),\]

_where \(c_{k}=\frac{2}{\pi}\int_{0}^{\pi}cos(k\theta)f(cos(\theta))d\theta\), and \(k\) is the order of the Chebyshev polynomials._

In addition, the Chebyshev polynomials on interval \([-1,1]\) can be iteratively defined as \(T_{k}(t)=2tT_{k-1}(t)-T_{k-2}(t)\) with initial values of \(T_{0}(t)=1\) and \(T_{1}(t)=t\). Given that the eigenvalues of the normalized Laplacian matrix fall in the range of \([0,2]\), we utilize the shifted Laplacian matrix \(\mathbf{L}-\mathbf{I}_{n}\) to compute the following shifted Chebyshev polynomials \(\bar{T}\). Meanwhile, for each wavelet \(i\), we also have a scale function \(s_{i}(\cdot)\) to re-scale the eigenvalue so that it can fit into the domain of \(f\) to calculate the following Chebyshev coefficient \(\bar{c}_{i,k}\). By introducing the truncated Chebyshev polynomials into graph wavelet operators, the \(i\)-th kernel function \(f_{i}(\mathbf{L})\) is designed to capture the first \(iK\)-hop information, which can be expressed as follows:

\[f_{i}(\mathbf{L})=\frac{1}{2}\bar{c}_{i,0}\mathbf{I}_{n}+\sum_{k=1}^{iK}\bar{c}_{i,k} \bar{T}_{k}(\mathbf{L}), \tag{4}\]
where \(\bar{T}_{k}(\mathbf{L})=\frac{4}{\lambda_{n}}(\mathbf{L}-\mathbf{I})\bar{T}_{k-1}(\mathbf{L})- \bar{T}_{k-2}(\mathbf{L})\) with initial values of \(\bar{T}_{0}(\mathbf{L})=\mathbf{I}_{n}\) and \(\bar{T}_{1}(\mathbf{L})=t\mathbf{I}_{n}\) represents the shifted Chebyshev polynomials and \(\bar{c}_{i,k}=\frac{2}{\pi}\int_{0}^{\pi}cos(k\theta)f(s_{i}(\frac{\lambda_{n} (cos(\theta)+1)}{2}))d\theta\) with \(1\leq i\leq q\). Then, the results of \(q\) graph wavelets are concatenated together to generate the representation of node \(j\):

\[\mathbf{h}_{j}=\text{CONCAT}\left(\left(f_{1}(\mathbf{L})\mathbf{\tilde{X}}\right)_{j}, \left(f_{2}(\mathbf{L})\mathbf{\tilde{X}}\right)_{j},\cdots,\left(f_{q}(\mathbf{L})\mathbf{ \tilde{X}}\right)_{j}\right). \tag{5}\]

After node representations \(\mathbf{h}\) are generated by CWGNN, a pooling function is needed to obtain the representation of the entire graph. Commonly used pooling functions such as average pooling and sum pooling functions (Hamilton et al., 2017) have achieved satisfactory performance in various classification tasks. However, as demonstrated in our experiments, these techniques become ineffective in graph-level anomaly detection. Consequently, this challenge calls for a newly designed pooling function that can effectively guide CWGNN to learn better graph representation.

**RQ-pooling.** In order to incorporate spectral information into node weights, we adopt an attention mechanism to generate the graph representation:

\[\mathbf{h}_{Att}^{G}=\sigma\left(\sum_{j\in V}a_{j}\mathbf{h}_{j}\right), \tag{6}\]

where \(\sigma\) is the non-linear activation function, and \(a_{j}\) is the attention coefficient of node \(j\). Specifically, 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 \(j\) can be expressed as \(a_{j}=RQ(\mathbf{X},\mathbf{L})\mathbf{h}_{j}\), which is used as the node importance score in RQ-pooling. Such a strategy allows CWGNN to capture more underlying spectral information of graphs. The final representation of the graph is the concatenation of both \(\mathbf{h}_{RQ}^{G}\) and \(\mathbf{h}_{Att}^{G}\):

\[\mathbf{h}^{G}=\text{MLP}\left(\text{CONCAT}\left(\mathbf{h}_{Att}^{G},\mathbf{h}_{RQ}^{G }\right)\right). \tag{7}\]

### 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.** As the number of training samples increases, there will be more potential information overlap among different samples. Consequently, the marginal benefit that a 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 a class. This approach ensures that the model effectively utilizes the available data while avoiding redundancy and maximizing its learning potential. Specifically, we define the expected number \(\eta(n_{t})\) as the total number of samples that can be covered by \(n_{t}\) training data and utilize the inverse of this number as the balance factor in our loss function.

**Proposition 2**.: _The expected number \(\eta(n_{t})=\frac{1-\beta^{n_{t}}}{1-\beta}\), where \(\beta=\frac{N-1}{N}\) with \(N\) equaling to the total 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 \(\beta\) 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:

\[\mathcal{L}_{CB_{focal}}=\frac{\mathcal{L}_{focal}}{\eta(n_{y})}=\frac{1-\beta }{1-\beta^{n_{y}}}\sum_{i=1}^{C}(1-p_{i})^{\gamma}log(p_{i}), \tag{8}\]

where \(\beta\) and \(\gamma\) are hyperparameters, \(n_{y}\) is the number of samples in class \(y\) that the current sample belongs to, \(C\) denotes the number of classes, and \(p_{i}=\text{softmax}(\mathbf{h}^{G})_{i}\) is the predicted probability for the current sample belonging to class \(i\).
## 4 Experiments

### Experimental Setup

**Datasets.** We use 10 real-world datasets to 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 compounds and their reactions to different cancer cells. We treat inactive chemical compounds as normal graphs and active ones as anomalous graphs. The anomalous level is measured using the anomalous ratio \(h=\frac{n_{a}}{n_{n}+n_{a}}\). In addition, the attributes are generated from node labels using one-hot encoding. The statistics of these 10 real-world datasets are shown in Table1.

**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 (Baek et al., 2021), Gmixup (Han et al., 2022), and TVGNN (Hansen and Bianchi, 2023).
* Graph-level anomaly detection models: OCGIN (Zhao and Akoglu, 2021), OCGTL (Qiu 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/validation/test sets with 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-F1 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

\begin{table}
\begin{tabular}{c c c c c c c c c c c c} \hline \hline Dataset & MCF-7 & MOLT-4 & PC-3 & SW-620 & NCI-H23 & OVCAR-8 & P388 & SF-295 & SN12C & UACC257 \\ \hline \(n_{a}\) & 25476 & 36625 & 25941 & 38122 & 38296 & 38437 & 39174 & 38246 & 38049 & 38345 \\ \(n_{a}\) & 2294 & 3140 & 1568 & 2410 & 2057 & 2079 & 2298 & 2025 & 1955 & 1643 \\ \(h\) & 0.0826 & 0.079 & 0.057 & 0.0595 & 0.051 & 0.0513 & 0.0554 & 0.0503 & 0.0489 & 0.0411 \\ \(\bar{n}\) & 26.4 & 26.1 & 26.36 & 26.06 & 26.07 & 26.08 & 22.11 & 26.06 & 26.08 & 26.09 \\ \(\bar{m}\) & 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 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Statistics of 10 real-world datasets, where \(n_{n}\) is the number of normal graphs, \(n_{a}\) is the number of anomalous graphs, \(h\) is the anomalous ratio, \(\bar{n}\) is the average number of nodes, \(\bar{m}\) is the average number of edges, and \(F\) is the number of attributes.

\begin{table}
\begin{tabular}{c c c|c c c c c c c c c} \hline \hline  & \multicolumn{3}{c|}{Spectral GNN} & \multicolumn{3}{c|}{Geap Classification} & \multicolumn{3}{c}{Graph-level Anomaly Detection} \\ \hline Datasets & Metrics & ChebyNet & BernNet & GMT & Gmixup & TVGNN & OCGIN & OCGTL & GLocalKD & HimNet & iGAD & RQGNN-1 & RQGNN-2 & RQGNN \\ \hline MCF-7 & AUC & 0.6612 & 0.6172 & 0.7706 & 0.6974 & 0.7180 & 0.5348 & 0.5866 & 0.6363 & 0.6369 & 0.8146 & 0.8994 & 0.8346 & **0.854** \\  & F1 & 0.4780 & 0.4784 & 0.4784 & 0.4779 & 0.5984 & - & - & - & - & 0.6468 & 0.6266 & 0.7205 & **0.794** \\ \hline MOLT-4 & AUC & 0.6647 & 0.6144 & 0.7660 & 0.6232 & 0.7159 & 0.5259 & 0.6191 & 0.6631 & 0.6633 & 0.8068 & 0.8246 & 0.8196 & **0.8316** \\  & F1 & 0.4858 & 0.4794 & 0.4814 & 0.4789 & 0.4916 & - & - & - & - & 0.6671 & 0.7119 & 0.7113 & **0.7240** \\ \hline PC-3 & AUC & 0.6051 & 0.6084 & 0.7896 & 0.6098 & 0.7974 & 0.3810 & 0.5489 & 0.6277 & 0.6703 & 0.8722 & 0.8533 & 0.8671 & **0.8782** \\  & F1 & 0.4853 & 0.4853 & 0.4853 & 0.4853 & 0.6206 & - & - & - & - & 0.6697 & 0.7003 & **0.7324** & 0.7184 \\ \hline SW-620 & AUC & 0.6759 & 0.6072 & 0.7467 & 0.6479 & 0.7326 & 0.4995 & 0.6398 & 0.6542 & 0.6544 & 0.8512 & 0.8401 & 0.8427 & **0.8560** \\  & F1 & 0.4898 & 0.4847 & 0.4844 & 0.5365 & - & - & - & - & 0.6627 & 0.6941 & 0.7209 & **0.7335** \\ \hline NCI-H23 & AUC & 0.6728 & 0.6114 & 0.8030 & 0.7324 & 0.7782 & 0.4948 & 0.6122 & 0.6837 & 0.6814 & 0.8297 & 0.8413 & 0.8354 & **0.8680** \\  & F1 & 0.4930 & 0.4869 & 0.4869 & 0.4869 & 0.5500 & - & - & - & 0.6646 & 0.6735 & **0.7349** & 0.7214 \\ \hline OVCAR-8 & AUC & 0.6330 & 0.3580 & 0.7692 & 0.3660 & 0.7653 & 0.5298 & 0.6007 & 0.6750 & 0.6570 & 0.8691 & 0.8549 & 0.8560 & **0.8799** \\  & F1 & 0.4900 & 0.4868 & 0.4868 & 0.4869 & 0.5406 & - & - & - & 0.6683 & 0.6866 & 0.6707 & **0.77215** \\ \hline P388 & AUC & 0.7266 & 0.6707 & 0.8498 & 0.6166 & 0.7957 & 0.5252 & 0.6501 & 0.6445 & 0.6667 & 0.8995 & 0.8911 & 0.8904 & **0.9023** \\  & F1 & 0.6365 & 0.5001 & 0.6583 & 0.4856 & 0.3557 & - & - & - & - & 0.7437 & 0.7525 & 0.7788 & **0.7963** \\ \hline SF-295 & AUC & 0.6505 & 0.6503 & 0.7926 & 0.6714 & 0.7346 & 0.4744 & 0.6400 & 0.7069 & 0.7037 & 0.8707 & 0.8691 & **0.8382** \\  & F1 & 0.4871 & 0.4871 & 0.4871 & 0.4866 & 0.4935 & - & - & - & - & 0.6919 & 0.7120 & 0.7335 & **0.7416** \\ \hline SN12C & AUC & 0.6598 & 0.6014 & 0.7919 & 0.7211 & 0.7341 & 0.5004 & 0.5617 & 0.6880 & 0.6916 & 0.8477 & 0.8851 & **0.8904** & 0.8861
dropout rate as 0.4, the hyperparameters of the loss function \(\beta=0.999\), \(\gamma=1.5\), and we use batch 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.

### Experimental Results

We first evaluate the performance of RQGNN against different SOTA GNN models. Table 2 reports AUC and Macro-F1 scores of each GNN model on 10 datasets. The best result on each dataset is highlighted in boldface. Since OCGIN, OCGTL, GLocalKD, and HimNet adopt one-class classification to identify anomalous graphs, we only report their AUC scores. As we can see, RQGNN outperforms all baselines on all datasets. Next, we 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 average AUC score, and takes the lead by 24.40% and 25.33% on these 10 datasets in terms of average Macro-F1 score, respectively. These empirical evidences demonstrate that even though graph Laplacian matrix is related to graph spectral energy, we still need to 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 2, we can observe that compared to three GNN models, GMT, Gmixup, and TVGNN, RQGNN takes a lead by 8.38%, 20.59%, and 11.69% in terms of average AUC score and 23.70%, 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 in terms of AUC scores. This can be attributed to their inability to effectively capture the important graph anomalous information. In contrast, RQGNN guided by the Rayleigh Quotient successfully captures the spectral differences between anomalous and normal graphs, resulting in significantly superior performance compared to 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% in terms of AUC score, respectively. Among all the baselines, iGAD stands out as the most competitive model, which incorporates anomalous-aware 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-F1 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.

Figure 2: Varying the hidden dimension, width, and depth.
### 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 2.

Firstly, we use RQGNN-1 to indicate the model that replaces the RQ-pooling with average pooling. Recap from Section 4.1 that, it combines the representation of Rayleigh Quotient and CWGNN with average pooling function. As we can observe, RQGNN-1 outperforms all other baselines on all datasets in terms of the Macro-F1 scores. In particular, compared with RQGNN-1, RQGNN 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.

Then, we use RQGNN-2 to indicate the model with only CWGNN-RQ. Specifically, we remove the RQL component that explicitly calculates the Rayleigh Quotient of each graph. Instead, we only compute the Rayleigh Quotient as the node weights for CWGNN. As we can observe, RQGNN-2 outperforms all the other baselines in terms of the Macro-F1 scores, which again shows the effectiveness of the RQ-pooling. Besides, according to Table 2, we can see that RQGNN is 0.09% higher than RQGNN-2 in terms of AUC score and 1.08% higher than RQGNN-2 in terms of Macro-F1 score on average, which further shows the effectiveness of the RQL component. In summary, these results demonstrate the effectiveness of each component in RQGNN.

### Parameter Analysis

Next, we conduct experiments to analyze the effect of representative parameters: the hidden dimension \(d\) of RQGNN, the width \(q\) and depth \(K\) of CWGNN-RQ on MCF-7, SF-295, SN12C, and UACC257 datasets. Figure 2 reports the Macro-F1 score of RQGNN as we vary the hidden dimension \(d\) from \(32\) to \(256\), the width \(q\) from \(3\) to \(6\), and the depth \(K\) from \(5\) to \(8\). As we can observe, when we set the hidden dimension to \(64\), RQGNN 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 set the width to \(4\) 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 to \(6\). As a result, the depth is set to \(6\) in RQGNN.

### 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 a converged model should have a similar Rayleigh Quotient distribution to 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. 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 discover 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 outperforms other SOTA competitors by a significant margin.