# PREM: A Simple Yet Effective Approach for Node-Level Graph Anomaly Detection

Junjun Pan∗1, Yixin Liu∗2, Yizhen Zheng∗2, and Shirui Pan1,3 1 School of
Information and Communication Technology, Griffith University, Queensland,
Australia
2 Department of Data Science and AI, Monash University, Melbourne, Australia
3 Institute for Integrated and Intelligent Systems (IIIS), Griffith
University, Queensland, Australia
Shirui Pan is the corresponding author. * indicates equal contributions to
this work<EMAIL_ADDRESS>{yixin.liu,
<EMAIL_ADDRESS><EMAIL_ADDRESS>dept. name of organization
(of Aff.)
name of organization (of Aff.)
City, Country
email address or ORCID

###### Abstract

Node-level graph anomaly detection (GAD) plays a critical role in identifying
anomalous nodes from graph-structured data in various domains such as
medicine, social networks, and e-commerce. However, challenges have arisen due
to the diversity of anomalies and the dearth of labeled data. Existing
methodologies - reconstruction-based and contrastive learning - while
effective, often suffer from efficiency issues, stemming from their complex
objectives and elaborate modules. To improve the efficiency of GAD, we
introduce a simple method termed PREprocessing and Matching (PREM for short).
Our approach streamlines GAD, reducing time and memory consumption while
maintaining powerful anomaly detection capabilities. Comprising two modules -
a pre-processing module and an ego-neighbor matching module - PREM eliminates
the necessity for message-passing propagation during training, and employs a
simple contrastive loss, leading to considerable reductions in training time
and memory usage. Moreover, through rigorous evaluations of five real-world
datasets, our method demonstrated robustness and effectiveness. Notably, when
validated on the ACM dataset, PREM achieved a 5% improvement in AUC, a 9-fold
increase in training speed, and sharply reduce memory usage compared to the
most efficient baseline.

###### Index Terms:

anomaly detection, unsupervised learning, graph-structured data, efficiency

1st Given Name Surname

##  I Introduction

Graph anomaly detection (GAD) is a burgeoning field that focuses on
identifying unusual patterns, including anomalous nodes, edges, or graphs that
deviate noticeably from the majority [5, 23, 56]. As an advanced and practical
technique, GAD has been widely used in fields as diverse as medicine [28, 21],
social networks [17], and e-commerce [43]. Among various GAD scenarios, node-
level GAD holds significant importance as it focuses on discerning the
abnormality of individual nodes.  For instance, node-level GAD can identify
fraudsters in e-commerce networks, thereby contributing to improved security
and trust within the online marketplace. In this paper, our research is
specifically dedicated to addressing the challenging yet practical research
problem of node-level GAD***In the paper, the term “GAD” specifically
indicates node-level GAD..

In practice, building a principled GAD model is a challenging task due to two
major obstacles: the diversity of anomalies and the absence of anomaly labels
[5, 23]. Firstly, anomalous nodes in graphs can manifest in various ways,
including distinctive node features from their neighborhoods, atypical
interaction patterns with other nodes, and unusual topological substructures
[5]. Consequently, the challenge lies in developing a single GAD model that
can effectively identify diverse types of anomalous nodes comprehensively. On
the other hand, the expensive nature of annotating anomaly labels makes it
difficult to train a GAD model with reliable supervision signals [12]. As a
result, traditional shallow (graph) anomaly detection methods often struggle
to achieve satisfactory performance in such scenarios [29, 2, 16, 30].

(a) Train

(b) Test

Figure 1: AUC and runtime (in second) of baselines and our method PREM on ACM.
Left: training; Right: testing.

With the rising popularity of graph neural networks (GNNs), which have shown
success in various graph-related tasks, there has been an emergence of deep
learning-based methods proposed to tackle the GAD problem. These methods
leverage unsupervised GNN models to capture intricate graph anomaly patterns
and learn meaningful representations for anomaly detection purposes.
Essentially, deep GAD methods can be categorized into two main categories:
generative and contrastive. The generative GAD methods mainly use auto-
encoder-like GNN models for graph data reconstruction and calculate anomaly
scores based on the reconstruction error of nodes [5, 7, 18, 27, 47]. The
contrastive GAD methods, differently, employ a discriminator to assess the
degree of inconsistency between target nodes and their neighbors for
abnormality evaluation [23, 12, 6].

Though the deep learning-based methods have led to significant improvements
for GAD, these advancements have come at a considerable cost in terms of
efficiency in time and memory consumption. This is because these methods often
rely on well-hand-crafted modules and complicated objectives to achieve great
performance. For example, the multiple rounds estimation used in contrastive
GAD prolongs the model evaluation time. In addition, the integration of
structural-aware modules [47, 27] or edge reconstruction tasks [5, 7, 47]
intensifies memory usage, which escalates with dataset size, impeding memory
efficiency. These limitations hinder the application of these methods in real-
world scenarios characterized by vast amounts of data, underscoring the need
for more efficient GAD solutions.

Figure 2: GPU Memory usage (in MB) of baselines and our method. Notices that
we fix batch size=300 for all contrastive learning-based methods and the mini-
batch version of PREM (termed PREM-b) for comparison purposes.

To enable effective, efficient, and computationally friendly anomaly detection
on real-world graph data, in this paper, we introduce a novel GAD method
termed PREprocessing and Matching, herein referred to as PREM. This framework
offers superior performance over existing methods, coupled with exceptional
efficiency in both time and memory. For instance, when evaluated on the ACM
dataset, as depicted in Fig. 1 and Fig. 2, our method substantially surpasses
all existing GAD baselines. It registers an impressive performance improvement
of 5% in AUC, while significantly reducing the training time (9 $\times$
faster) and consumes much less memory compared with the most efficient
baseline. The crux of PREM lies in its streamlined two-part structure: a pre-
processing module and an ego-neighbor matching module. Specifically, our
approach eliminates message passing propagation during training, as the pre-
processing stage aggregates neighbor features only once, leading to much lower
time and space complexity. In addition, we employ a similarity-based method,
eschewing the need for multi-round procedures that usually hamper efficiency.
Furthermore, with the implementation of mini-batch processing, PREM requires
only a minimal amount of memory. In summary, the contribution of our work is
three-fold:

  * •

We develop a simple yet very efficient framework, PREprocessing and Matching,
PREM, for graph anomaly detection (GAD), adhering to the principle of
simplicity and minimalism.

  * •

Our proposed method, namely PREM is orders of magnitude faster and consumes
much less memory compared with existing GAD baselines.

  * •

The robustness and effectiveness of our method have been thoroughly evaluated
and analyzed across five real-world datasets, where PREM achieved the best
performance compared with existing GAD baselines.

TABLE I: Architecture comparison between state-of-the-art GAD methods and
PREM.

Method |  Feature Reconstruction |  Structure Reconstruction |  Subgraph Sampling |  Node-Subgraph Contrast |  Node-Node Contrast |  Multi-View Contrast |  Multi-round Evaluation
---|---|---|---|---|---|---|---
DOMINANT |  ✔ |  ✔ |  ✗ |  ✗ |  ✗ |  ✗ |  ✗
CoLA |  ✗ |  ✗ |  ✔ |  ✔ |  ✗ |  ✗ |  ✔
ANEMONE |  ✗ |  ✗ |  ✔ |  ✔ |  ✔ |  ✗ |  ✔
GADMSL |  ✗ |  ✗ |  ✔ |  ✔ |  ✔ |  ✔ |  ✔
SL-GAD |  ✔ |  ✗ |  ✔ |  ✔ |  ✗ |  ✔ |  ✔
Sub-CR |  ✔ |  ✗ |  ✔ |  ✔ |  ✗ |  ✔ |  ✔
PREM |  ✗ |  ✗ |  ✗ |  ✔* |  ✔* |  ✗ |  ✗

  * *

Without training-time propagation

##  II Related Work

###  II-A Graph Neural Networks

Graph Neural Networks (GNNs), falling under the broad umbrella of deep neural
network [15], are specifically for handling semi-structured graph data. It is
facilitated by harnessing both the attributive and the topological information
inherently present within the non-Euclidean graph-structured data. The very
inception of GNNs can be traced back to [3], where an innovative spectral-
based method was introduced. This method facilitated the extension of
convolution networks to graph-based structures. Following this inaugural
contribution, the concept was further built upon with the development of a
range of subsequent spectral-based convolution GNNs [4, 10]. These furthered
the field by adopting filters designed in accordance with the principles of
graph signal processing [33, 53]. One important milestone in this domain was
the advent of Graph Convolutional Networks (GCN) [13]. The GCN essentially
served as a bridge, connecting spectral-based methods and spatial-based GNN
approaches by simplifying spectral graph convolutions. Specifically, it
approximates the first-order Chebyshev polynomial filters.

The development of GCN paved the way for the rapid evolution of spatial-based
methods. These methods were not only more efficient but also exhibited wider
applicability across various use cases. For example, Graph Attention Networks
(GAT) [37] was a significant evolution in this regard. GAT integrated the
attention mechanism [36], making it possible to account for varying levels of
significance among node neighbors, rather than just employing a basic average
of neighboring data. Another significant spatial-based approach was the
Simplified Graph Convolutions (SGC) [41]. It further simplifies GCN by
removing non-linearity and collapsing weight matrices between graph
convolution layers, reducing the overall complexity. In addition to these
major contributions, numerous studies have focused on improving GNN from other
unique angles. These include the expansion of scalability [1, 45, 51], the
reduction of prior knowledge requirement [22, 24, 59, 54, 50, 48, 49] and the
enlargement of receptive fields [14, 35, 19, 42, 54]. GNN approaches have
found widespread success across multiple domains. They have been employed
effectively in areas such as business analysis [52], federated learning [34],
latent structure inference [25], and question answering [26].

###  II-B Traditional Graph Anomaly Detection

Graph anomaly detection can be defined as classifying outliers from normal
nodes. With the increasing use of attributed networks in industry, the
importance of graph anomaly detection has become popular in recent years. In
order to effectively detect anomalies in attributed networks, various non deep
learning-based algorithms and methodologies have been developed, each with
their own strengths and weaknesses. A pioneer work, AMEN [30] mines anomaly
information from the internal and external consistency of neighborhoods. Radar
[16] analyses the residual between target node attributes and the majority to
calculate the anomaly score. ANOMALOUS[29] extends the framework of [16] by
incorporating CUR decomposition with residual analysis. DEEPFD [39] first
attempts to learn the embedding via reconstructing target node’s features, and
then detects anomaly substructures via clustering. [57] improves the
scalability by growing and merging communities of nodes that share similar
properties. HCM [11] learns the embedding by predicting the shortest distance
between nodes to obtain both local and global information. However, due to the
limitations of their shallow mechanism, their performance is proven to be
limited when handling high-dimensional features and complex structures.

###  II-C Deep Learning-based Graph Anomaly Detection

Compared to traditional methods, Deep learning-based graph anomaly detection
(GAD) methods are able to better capture the complex relationships and
structures present in attributed networks, resulting in more accurate and
efficient anomaly detection. They mainly fall into two categories: generative
and contrastive learning. DOMINANT [5] pioneers the first generative GAD
method by learning node embeddings via minimizing reconstruction error for
attributes and adjacency matrix, exploiting both attribute and topological
features. SpecAE[18] follows a similar approach but uses deconvolution and
Gaussian Mixture Model for anomaly estimation. AnomalyDAE [7] decouples
attribute and structural encoders to efficiently model interactions. ComGA
[27] incorporates community detection, while AS-GAE [47] adds a location-aware
module. For contrastive learning-based methods, CoLA [23] addresses challenges
with a contrastive learning paradigm, using a discriminator to detect
inconsistencies between target node and neighbor subgraph embeddings. ANEMONE
[12] introduces a patch-level contrastive task for multi-scale anomaly
detection. GRADATE [6] improves the framework through graph augmentation and
multi-views contrast. SL-GAD [55] combines attribute reconstruction and node-
subgraph contrast, while Sub-CR [46] uses masked autoencoder and graph
diffusion to fuse attributes with local and global topological information.
Apart from the two main categories, There are also other methods targeting
GAD, such as subtractive aggregation [56], one-class SVM [40], and
complementary learning [20].

Although existing deep GAD methods have demonstrated promising results, their
limitations in efficiency and scalability hinder their applicability in real-
world scenarios involving large-scale graphs with a vast number of nodes and
edges. As shown in Table I and Fig. 1, 2, integrating more modules improves
performance but at the expense of efficiency. To address these issues, we
propose PREM, a novel approach that significantly streamlines the GAD process
by employing a linear discriminator in an embarrassingly simple manner. Not
only does PREM outperform the baseline methods by a considerable margin, but
it also runs much faster and has lower memory consumption. This enhanced
efficiency and scalability make PREM a more suitable choice for practical
applications in detecting anomalies within extensive graph structures.

##  III Preliminaries

###  III-A Definition

Throughout this paper, we use calligraphic fonts, bold lowercase letters, and
bold uppercase letters to denote sets, vectors, and matrices, respectively. We
denote an attributed graph as $G=(\mathcal{V},\mathcal{E},\mathbf{X})$, where
$\mathcal{V}=\\{v_{1},\cdots,v_{n}\\}$ is the set of vertices (or nodes), the
number of nodes $|\mathcal{V}|$ is $n$, and $\mathcal{E}$ is the set of edges,
where $|\mathcal{E}|=m$, which can also be expressed by a binary adjacent
matrix $\mathbf{A}\in\mathbb{R}^{n\times n}$. The feature matrix of a graph
$\mathbf{X}\in\mathbb{R}^{n\times d}$ can be represented as a list of row
vectors $\mathbf{X}=(\mathbf{x}_{1}^{T},\cdots,\mathbf{x}_{n}^{T})$, where
$\mathbf{x}_{i}$ is the feature vector of node $v_{i}$ and $d$ is the
dimension of features.

###  III-B Problem Formulation

In this paper, we focus on the unsupervised node-level graph anomaly detection
(GAD) problem. The aim is to learn a scoring function $f(\cdot)$ to estimate
the anomaly score $s_{i}$ for each node $v_{i}$. A larger anomaly score
$s_{i}$ indicates that the node $v_{i}$ is more likely to be an anomalous
node. In this paper, we aim to develop a novel GAD model (serving as
$f(\cdot)$) that estimates the anomaly score efficiently under strictly
unsupervised settings without ground-truth labels of the anomaly provided.

##  IV Method

Figure 3: The overall pipeline of PREM that composes of a pre-processing
module and an ego-neighbor matching module. In the first module, we conduct
anonymized message passing, i.e., without the self-loop, on the given graph to
obtain neighbor features. Then, in the ego-neighbor matching module, we input
the ego features, i.e., raw features, and neighbor features into a
discriminator, which includes a linear layer and the cosine similarity
computation component, to obtain anomaly scores. The higher the score is, more
likely the node is an anomaly.

In this section, we introduce the proposed model term PREM in detail. The
overall pipeline of PREM is illustrated in Fig. 3. On the highest level, PREM
is composed of two components: 1) A pre-processing module is designed to
precompute the neighbor features, thereby eliminating the need for costly
message passing during training; and 2) a ego-neighbor matching module that
learns the matching patterns between ego and neighbor information with a
simple linear layer-based network. Once PREM is well-trained, the anomaly
scores can be estimated by the ego-neighbor similarity directly. In the
following subsections, we first introduce the two main components of PREM
respectively. Then, we illustrate a simple contrastive learning objective to
train PREM model. Finally, we expound on the calculation of anomaly scores
during inference and discuss the superb efficiency of PREM.

###  IV-A Message Passing-based Pre-Processing

In conventional GAD methods, message passing-based GNNs are commonly used to
capture contextual information of each node, aiding in the prediction of node-
level abnormality. However, the forward and backward propagation involved in
message passing can be time-consuming, which significantly affects the
efficiency of model training [8]. Consequently, an important question arises:
Is it possible to expedite the learning process by eliminating message passing
during training? To address this question, we propose a pre-processing scheme
based on message passing that enables PREM to perform message passing only
once throughout the learning procedure.

Since the agreement between each node and its context (i.e., its surrounding
substructure) is highly correlated to the node-level abnormality [23, 12], in
our pre-processing module, we concentrate on extracting two types of
information: ego information, which indicates the attributes specific to a
node, and neighbor information, encompassing the contextual knowledge
surrounding the node. Firstly, to capture ego information, we construct ego
features $\mathbf{X}^{(e)}$ by collecting the raw feature vectors together
directly, i.e., $\mathbf{X}^{(e)}=\mathbf{X}$. This approach enables us to
capture the intrinsic attributes and characteristics of each node without
considering the surrounding context.

Then, to extract neighbor information, we propose to conduct message passing
on the raw features to generate neighbor features $\mathbf{X}^{(n)}$. One
possible approach is to adopt the propagation rule used in mainstream GNNs,
such as GCN [13] and SGC [41], for our message passing-based pre-processing.
However, it is important to note that conventional GNNs typically aggregate
both ego and neighbor information during message passing. This aggregation
strategy may lead to information leakage in the downstream ego-neighbor
matching network, subsequently impacting the performance of anomaly detection.
To alleviate this issue, we design an anonymized message passing scheme that
enables the extraction of neighbor information separately. In concrete, the
neighbor features can be calculated by:

$\mathbf{X}^{(n)}=\mathbf{P}\mathbf{X},$ (1)

where $\mathbf{P}$ is the anonymized propagation matrix that can be written
by:

$\mathbf{P}=\mathbf{M}*(\tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-1/2})^{k},$
(2)

where $k$ is the propagation steps in message passing,
$\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}$ is the adjacency matrix with self-
loop, $\tilde{\mathbf{D}}$ is the degree matrix of $\tilde{\mathbf{A}}$, and
$\mathbf{M}$ is a self-anonymization mask where diagonal entries are all zero
while the remaining entries are all one. By utilizing the self-anonymization
mask, the signals associated with ego features can be filtered out during the
message passing process. Consequently, each row vector $\mathbf{x}_{i}^{(n)}$
in the neighbor features matrix $\mathbf{X}^{(n)}$ can concentrate on
summarizing the neighbor information independently, without being influenced
by the ego information.

It is worth noting that $\mathbf{X}^{(e)}$ and $\mathbf{X}^{(n)}$ are computed
only once during the learning procedure, and there are no trainable weights to
be involved in the pre-processing step. Thanks to this merit, our method is
much simpler and faster than existing methods that involve multiple layers of
GNNs in GAD models.

###  IV-B Ego-Neighbor Matching Network

Once we have obtained the ego and neighbor features, we proceed to construct
an ego-neighbor matching network. This network is designed to learn the
matching patterns between the ego information and the corresponding neighbor
information of each node. By capturing these matching patterns, we can
effectively assess the normality of nodes during the testing phase.

In specific, the proposed ego-neighbor matching network is composed of two
linear layers and a cosine similarity unit. Note that the original features of
attributed graphs are frequently high-dimensional, and there are often
correlations among different feature dimensions. In such scenarios, directly
measuring the similarity solely at the feature space can be inefficient and
ineffective. Therefore, instead of calculating the feature-level similarity,
we first introduce two learnable linear layers to map the ego features and
neighbor features into a low-dimensional space, respectively. Formally, given
the ego feature vector $\mathbf{x}^{(e)}_{i}$ and neighbor feature vector
$\mathbf{x}^{(n)}_{i}$ for node $v_{i}$, the linear mapping can be written by:

$\displaystyle\mathbf{h}^{(e)}_{i}$
$\displaystyle=\mathbf{x}^{(e)}_{i}\mathbf{W}_{1}+\mathbf{b}_{1},$ (3)
$\displaystyle\mathbf{h}^{(n)}_{i}$
$\displaystyle=\mathbf{x}^{(n)}_{i}\mathbf{W}_{2}+\mathbf{b}_{2},$

where $\mathbf{h}^{(e)}_{i}$ and $\mathbf{h}^{(n)}_{i}$ are low-dimensional
ego embedding vector and neighbor embedding vector respectively, while
$\mathbf{W}_{1}$, $\mathbf{W}_{2}$, $\mathbf{b}_{1}$, and $\mathbf{b}_{2}$ are
learnable weights/bias parameters of the linear layers.

After linear mapping, now we can evaluate the ego-neighbor similarity with the
compact embeddings. To simplify, we employ a cosine similarity unit to measure
the agreement between two embeddings, which can be formulated by:

$c_{i}=\operatorname{cos}(\mathbf{h}^{(e)}_{i},\mathbf{h}^{(n)}_{i}),$ (4)

where $\operatorname{cos}(\cdot,\cdot)$ is the cosine similarity function and
$c_{i}\in[-1,1]$ is the ego-neighbor similarity of node $v_{i}$. Intuitively,
$c_{i}$ can be used to indicate the normality of node $v_{i}$: according to
the homophily assumption, a (normal) node tends to have similar behavior with
its neighborhoods, leading to a larger $c_{i}$ given by our matching network;
in contrast, anomalous nodes usually break the homophily assumption due to
their noisy connections and unexpected features [23], hence have smaller
$c_{i}$. In other words, we can easily estimate the anomaly score according to
the learned similarity.

Figure 4: Illustration of positive and negative pairs in PREM.

###  IV-C Contrastive Learning-based Model Training

In this subsection, we present the training strategy for our PREM model. Given
the challenge of obtaining ground-truth labels for anomalies, our focus in
this paper is on the unsupervised GAD problem [5, 23]. In this context, it
becomes necessary to design a carefully crafted unsupervised learning
objective to train the PREM model, as opposed to relying on labeled data.
Inspired by the success of contrastive learning on GAD tasks [23, 12], we
design a simple yet effective contrastive learning objective for our model
training.

Recalling that we aim to maximize the ego-neighbor similarity of a normal
node. However, we cannot identify the normal nodes exactly without accessing
their labels during the training phase. Fortunately, with the assumption that
the number of anomalies is much smaller than which of normal nodes, we can
directly maximize the ego-neighbor similarity of all nodes. By doing so, PREM
can effectively capture the dominant matching patterns observed in normal
nodes. This approach allows us to prioritize the identification of normal
behavior patterns while accommodating the inherent difficulty of precisely
identifying individual normal nodes without explicit labels. By focusing on
the majority of normal nodes, we can still train the model to capture the
essential matching patterns associated with normalcy. Formatting this idea to
a contrastive framework, we define the ego and neighbor embeddings of the same
node, i.e., $\mathbf{h}^{(e)}_{i}$ and $\mathbf{h}^{(n)}_{i}$, as a positive
pair. Then, their cosine similarity is denoted as a positive term in
contrastive learning:

$c_{i}^{(pos)}=c_{i}=\operatorname{cos}(\mathbf{h}^{(e)}_{i},\mathbf{h}^{(n)}_{i}).$
(5)

If we only maximize the positive term $c_{i}^{(pos)}$, it would lead to the
model collapse problem, i.e., the model assigns high values or probabilities
to all input pairs. The model collapse problem can severely reduce the
discriminative power and hinder the effective detection of anomalies. To avoid
this issue, it is necessary to involve negative pair in our contrastive
training scheme. Regarding the ego embedding $\mathbf{h}^{(e)}_{i}$ of node
$v_{i}$ as an anchor, we can naturally define the neighbor embedding
$\mathbf{h}^{(n)}_{j}$ of another node $v_{j}$ as a negative sample. In this
case, we can obtain a negative pair ($\mathbf{h}^{(e)}_{i}$ and
$\mathbf{h}^{(n)}_{j}$) that forms a neighbor-based negative term in
contrastive learning:

$c_{i}^{(neg_{nbr})}=\operatorname{cos}(\mathbf{h}^{(e)}_{i},\mathbf{h}^{(n)}_{j}).$
(6)

With the neighbor-based negative term, now we can learn to discriminate the
matching patterns between ego and neighbor information with PREM.
Nevertheless, it is important to note that relying solely on neighbor-based
negative samples may introduce a potential issue known as the “easy negative”
problem [58, 32]. The easy negative problem occurs when the negative pairs
provided by the neighbors are too straightforward for the model to
discriminate, resulting in the model not effectively learning meaningful
matching patterns. This can hinder the model’s ability to accurately identify
anomalies. To address the easy negative problem, we propose introducing more
diverse and challenging negative samples. One effective strategy to achieve
this is by leveraging ego features. Discriminating among ego features is
particularly challenging because the raw features of two nodes can be very
similar in a graph. Motivated by this, in addition to the neighbor-based
negative term, we also incorporate an ego-based negative term for contrastive
training. In concrete, given the ego embedding $\mathbf{h}^{(e)}_{i}$ as an
anchor, we randomly sample the ego embedding $\mathbf{h}^{(e)}_{k}$ of another
node $v_{k}$ as its ego-based negative sample. Then, the ego-based negative
term can be written by:

$c_{i}^{(neg_{ego})}=\operatorname{cos}(\mathbf{h}^{(e)}_{i},\mathbf{h}^{(e)}_{k}).$
(7)

Finally, we establish a contrastive loss function to maximize the positive
contrastive terms while minimizing the negative contrastive terms. Unlike the
majority of works [59, 44, 31] that employ the Info-NCE contrastive loss, in
PREM, we use a binary cross-entropy-like contrastive loss for model training,
which can be regarded as an extension of Jensen-Shannon divergence-based
contrastive loss [38, 9]. Specifically, we first use a linear mapping to
project the positive/negative terms $c\in[-1,1]$ into $\hat{c}\in[0,1]$, and
then acquire the loss by:

$L=-\sum_{t=1}^{N}(\log(\hat{c}_{i}^{(pos)})+\alpha\log(1-\hat{c}_{i}^{(neg_{nei})})+\\\
\gamma\log(1-\hat{c}_{i}^{(neg_{ego})})),$ (8)

where $\alpha$ and $\gamma$ are the hyper-parameters for trade-off. Compared
to Info-NCE loss with $\mathcal{O}(n^{2})$ time complexity, our loss is much
more efficient to compute (with $\mathcal{O}(n)$ complexity). Such a nice
property ensures the rapid model training of PREM. Fig. 4 illustrates an
example of the definitions of positive and negative pairs in PREM.

(a) Cora

(b) CiteSeer

(c) PubMed

(d) ACM

(e) Flickr

Figure 5: ROC curves on five datasets.

###  IV-D Anomaly Score Calculation

Once the PREM model is well-trained, we can estimate the anomaly score using
the ego-neighbor matching module. In contrast to existing methods that fuse
anomalous information from both positive and negative contrastive terms [23],
PREM takes a simpler approach. We use the opposite value of the ego-neighbor
similarity $c^{(pos)}_{i}$ as the anomaly score for a node $v_{i}$, denoted as
$s_{i}=-c^{(pos)}_{i}$. As discussed in Sec IV-B, the similarity
$c^{(pos)}_{i}$ effectively reflects the normality of each node. Hence, by
taking the negative value of similarity, we obtain an anomaly score that
captures the abnormality of the node. In the inference phase, we can directly
discard the negative contrastive terms since the similarity measure already
encompasses the information needed to assess the normality of nodes. In
contrast to existing contrastive GAD methods that involve negative score
calculations and multi-round estimations [23, 12], PREM offers improved
efficiency and stability during anomaly score estimation.

TABLE II: Statistic information of datasets. Dataset | Nodes | Edges | Attributes | Anomalies
---|---|---|---|---
Cora | 2,708 | 5,429 | 1,433 | 150
CiteSeer | 3,327 | 4,732 | 3,703 | 150
PubMed | 19,717 | 88,648 | 500 | 600
ACM | 16,484 | 71,980 | 8,337 | 650
Flickr | 7,575 | 239,738 | 12,407 | 450

###  IV-E Efficiency Discussion

####  IV-E1 Mini-batch-based Model Training

Thanks to the pre-processing of ego and neighbor features, PREM is capable of
supporting mini-batch-based optimization, making model training
computationally efficient. This allows us to train PREM using batches of
ego/neighbor features instead of the entire graph, resulting in reduced memory
consumption. Additionally, this feature enables training on edge devices and
suggests the potential scalability of PREM.

####  IV-E2 Complexity Analysis

We discuss the time complexity of each component in PREM respectively. For the
pre-processing module, the complexity of message passing is
$\mathcal{O}(kmd)$. Note that this computation can be computed only once in
the whole learning procedure. For the ego-neighbor matching module, the
complexity of linear mapping is $O(ndd_{h})$, where $d_{h}$ is the hidden
dimension of embeddings. The cost of the cosine similarity unit is
$O(nd_{h})$. To compute the contrastive loss, the time complexity is $O(n)$.
The complexity of anomaly scoring is the same as which of the ego-neighbor
matching module. To sum up, the pre-processing, training, and testing
complexity of PREM are $\mathcal{O}(kmd)$, $O(ndd_{h}T)$, and $O(ndd_{h})$,
respectively, where $T$ is the training epoch.

##  V Experiments

In this section, we propose our experiment settings and results. We first
introduce the datasets, followed by the parameters of training. The experiment
results are then presented, including an ablation study and sensitivity
analysis. Our method is implemented in PyTorch and is evaluated on a Desktop
PC with a Ryzen 5800x CPU, an RTX2070 GPU, and 32GB RAM. The code is available
at https://github.com/CampanulaBells/PREM-GAD.

TABLE III: Hyper-parameters of our method.

Hyper-parameter | Cora | CiteSeer | PubMed | ACM | Flickr
---|---|---|---|---|---
Embedding dim. $d_{h}$ | 128 | 128 | 128 | 128 | 128
Prop. step $k$ | 2 | 2 | 2 | 2 | 2
Learning rate | 0.0003 | 0.0003 | 0.0005 | 0.0001 | 0.0005
Epoch $T$ | 100 | 100 | 400 | 200 | 1500
Trade-off param. $\alpha$ | 0.9 | 0.9 | 0.6 | 0.7 | 0.3
Trade-off param. $\gamma$ | 0.1 | 0.1 | 0.4 | 0.2 | 0.4

###  V-A Experimental Settings

####  V-A1 Datasets

The proposed method is evaluated on five datasets including four citation
network datasets (i.e. Cora, CiteSeer, PubMed, and ACM) and a social network
dataset (Flickr). The specific statistical details are outlined in Table II.
We follow the settings described in prior studies [5, 23] to inject anomalous
nodes. Concretely, there are two types of anomaly injection: structural
anomalies and attribute anomalies injection. In terms of injecting structural
anomalies, we build $\mathit{q}$ cliques of size $\mathit{p}$ by building
edges amongst randomly chosen nodes. This results in the formation of
$\mathit{pq}$ structural anomalies. For attribute anomalies injection,
substitute the feature of the target node with the feature vector of the one
exhibiting the highest Euclidean distance in an arbitrarily selected candidate
node set.  A total of $\mathit{pq}$ attribute anomalies have been injected for
balancing.

TABLE IV: AUC of PREM and baselines. Method | Cora | CiteSeer | PubMed | ACM | Flickr
---|---|---|---|---|---
DOMINANT | 0.8128 | 0.8197 | 0.7896 | 0.7561 | 0.7436
CoLA | 0.9046 | 0.8894 | 0.9468 | 0.8375 | 0.7616
ANEMONE | 0.9207 | 0.9282 | 0.9534 | 0.8492 | 0.7679
GRADATE | 0.9032 | 0.8904 | 0.9450 | 0.8580 | 0.7522
SL-GAD | 0.9178 | 0.9221 | 0.9627 | 0.8143 | 0.7965
Sub-CR | 0.9023 | 0.9272 | 0.9687 | 0.8060 | 0.7921
PREM | 0.9510 | 0.9779 | 0.9719 | 0.9056 | 0.8613
PREM-b | 0.9508 | 0.9741 | 0.9714 | 0.9088 | 0.8561

(a) Cora

(b) CiteSeer

(c) PubMed

(d) ACM

(e) Flickr

(f) Features

(g) Embeddings (w Anony.)

(h) Embeddings (w/o Anony.)

Figure 6: (a)-(e): Sensitivity analysis for balancing factors $\alpha$ and $\gamma$; (f)-(h) t-SNE visualizations of input features and learned embeddings by PREM (with and without Anonymization) on PubMed dataset. In (f)-(h), Ego (Normal/Anomaly) represents ego features for normal and anomaly nodes respectively, while Nei(Nomral/Anomaly) is neighbor feature for normal and anomaly nodes respectively. TABLE V: Training and testing time of GAD methods in seconds. Method | Cora | CiteSeer | PubMed | ACM | Flickr
---|---|---|---|---|---
train | test | train | test | train | test | train | test | train | test
DOMINANT | 3.9946 | 0.0050 | 8.3463 | 0.0050 | 104 | 0.0100 | 124 | 0.0090 | 266 | 0.0100
CoLA | 95 | 235 | 180 | 456 | 711 | 1770 | 1639 | 1056 | 712 | 454
ANEMONE | 101 | 247 | 191 | 465 | 732 | 1797 | 1643 | 1047 | 761 | 453
GRADATE | 541 | 319 | 917 | 557 | 3991 | 2392 | 2580 | 1491 | 1234 | 703
SL-GAD | 221 | 546 | 399 | 1007 | 1637 | 4171 | 4585 | 2697 | 2099 | 1262
Sub-CR | 145 | 422 | 243 | 708 | 1104 | 3385 | 720 | 2241 | 1355 | 958
PREM | 0.5386 | 0.0007 | 1.1002 | 0.0011 | 4.8098 | 0.0014 | 14 | 0.0112 | 68 | 0.0071
PREM-b | 5.6882 | 0.0080 | 11 | 0.0190 | 95 | 0.0310 | 214 | 0.1682 | 1028 | 0.1031

####  V-A2 Baselines

In this paper, we compare PREM with six state-of-the-art (SOTA) baselines,
including a generative method (DOMINANT [5]), three contrastive methods (CoLA
[23], ANEMONE [12], and GADMSL [6]), and two hybrid methods that combines
generative and contrastive learning (SL-GAD [55] and Sub-CR [46]).

####  V-A3 Evaluation metric

We utilize ROC-AUC as our evaluation metric to compare the results. The ROC
curve is the plot of the true positive rate and false positive rate under
different thresholds. AUC is the area under the ROC curve which is capped by
1. The larger the AUC, the better the classifier. We also record the time
taken to train and evaluate methods in seconds to compare the efficiency of
methods.

####  V-A4 Implementation Details

We present the parameter setting of PREM for the five datasets on Table III.
We set the number of propagation steps $k$ to 2 and set the embedding
dimension $d_{h}$ to 128 for all datasets. The learning rate of PREM for Cora,
CiteSeer, PubMed, ACM, and Flickr are 3e-4, 3e-4, 5e-4, 1e-4, 5e-4, and the
epochs are 100, 100, 400, 200, 1500, respectively, to get better performance
on datasets with various size. For balance factors $\alpha$ and $\gamma$, we
use grid search with search space $[0.1,0.2,\dots,1.0]$ for $\alpha$ and
$[0.1,0.2,\dots,0.5]$ for $\gamma$. We also consider PREM with a mini-batch
size of 300 (denoted as “PREM-b”) for comparison. Our method has been
evaluated for 10 times with different random seeds to report the average
results. For baselines, we follow the settings in their paper to obtain the
reported results.

TABLE VI: Maximum GPU memory usage of GAD methods in MB. Method | Cora | CiteSeer | PubMed | ACM | Flickr
---|---|---|---|---|---
train | test | train | test | train | test | train | test | train | test
DOMINANT | 282 | 282 | 572 | 572 | 5943 | 5943 | 6051 | 6051 | 4399 | 4401
CoLA | 60 | 60 | 137 | 135 | 1561 | 1528 | 2088 | 1665 | 918 | 717
ANEMONE | 62 | 62 | 139 | 139 | 1533 | 1529 | 1673 | 1673 | 729 | 729
GRADATE | 95 | 90 | 185 | 182 | 3022 | 3015 | 2713 | 2713 | 951 | 949
SL-GAD | 164 | 129 | 415 | 330 | 1600 | 1591 | 2691 | 2588 | 1784 | 1541
Sub-CR | 128 | 118 | 276 | 263 | 3083 | 3056 | 3652 | 3309 | 1491 | 1405
PREM | 110 | 54 | 347 | 161 | 294 | 146 | 3711 | 1629 | 2495 | 1103
PREM-b | 16 | 9 | 44 | 24 | 6 | 3 | 97 | 52 | 138 | 75
TABLE VII: Results of ablation analysis.

Variant | Cora | CiteSeer | PubMed | ACM | Flickr | Average
---|---|---|---|---|---|---
w/o nei. neg. | 0.7369 | 0.7304 | 0.8848 | 0.6131 | 0.7565 | 0.7393
w/o ego neg. | 0.9310 | 0.9782 | 0.9210 | 0.8730 | 0.7048 | 0.8761
w/o Anony. | 0.9541 | 0.9592 | 0.8811 | 0.9109 | 0.8536 | 0.9109
PREM | 0.9510 | 0.9779 | 0.9719 | 0.9056 | 0.8613 | 0.9328

###  V-B Comparative Results

In this subsection, we evaluate our proposed PREM by comparing its
performances and training and evaluation time to other baseline methods. The
AUC of PREM and baselines are summarized in Table IV, and the training and
testing time are listed in Table V. Fig. 5 shows ROC curves.

####  V-B1 Anomaly Detection Performance

From the data presented in Table IV, it is evident that PREM achieves the best
performance across all datasets, markedly outperforming baselines. This
accomplishment is a testament to its robustness and the efficacy of its
design. For example, PREM achieves the highest performance in the CiteSeer
dataset, where it achieves an AUC of 0.9779. This result is not only the best
in the group but it’s also noticeably higher than the other methods, i.e.,
leading by around 5%, illustrating the effectiveness of PREM. The PubMed and
ACM datasets further underscore PREM’s dominance. It not only processes these
large datasets efficiently but also manages to deliver superior results with
an AUC of 0.9719 and 0.9056 respectively. We can also witness that the mini-
batch-based training would not lead to performance degradation for PREM.

####  V-B2 Anomaly Detection Efficiency

Table V provides a detailed comparison of the training and testing times of
PREM and various baseline methods across five datasets. Impressively, PREM far
surpasses all other methods in terms of efficiency. On average, it often
operates at a pace 10 times swifter than its closest competitor , DOMINANT in
training, and 100 times faster than other contrastive learning based methods.
Significantly, in testing, this efficiency gap between our method and other
contrastive learning-based methods widens, e.g., PREM is 100,000 times faster
than ANEMONE, as computing negative ego-neighbor similarity is much more
efficient than subgraph sampling and multiple round evaluation, which are
widely used in other contrastive learning based methods [23, 12, 6]. This
speed advantage is attained without compromising memory efficiency or
performance. While the fastest baseline DOMINANT demonstrates the ability to
manage larger datasets, it does so at the expense of substantial memory
consumption. For instance, with the PubMed dataset, DOMINANT consumes roughly
5943 MB of memory in training, which is about 20 times more than PREM’s mere
294. Moreover, the mini-batch version PREM-b has extremely small memory
requirements across all datasets, enlightening the potential of running PREM
on edge devices with limited memory. The efficiency and effectiveness of PREM
stem from its simplicity as we only use a discriminator for anomaly score
calculation and most of the heavy computation can be done and reused in the
pre-processing module. It avoids complex objectives and modules that other
baselines do, focusing instead on efficiency and precision. This strategy
minimizes computational costs and reduces processing time while achieving SOTA
performance.

###  V-C Ablation Study

In this subsection, we study the effect of negative contrast pairs and
anonymization. The results are listed in Table VII. Overall, we can observe
that PREM achieves the best results when all components are included in terms
of the average result. Disabling the neighbor negative term results in the AUC
drop to the bottom, which illustrates that this term plays a primary role in
the model training. While removing the ego negative term slightly increases
the AUC on CiteSeer, it has a significant impact on large datasets such as
PubMed and Flickr. We can also find that using the two modules can improve
anomaly detection performance. When examining the impact of anonymization, a
comparison between Fig. 6 (g) and (h) reveals a significant reduction in the
distance between ego features and node features of anomalous nodes when
anonymization is not applied. As a result, anomaly nodes become more difficult
to be distinguished from their neighborhood and, thus lead to the degradation
of model performance.

###  V-D Sensitivity Analysis

To investigate the effect of the trade-off parameters $\alpha$ and $\gamma$,
we perform a grid search with stride=0.1 for all parameters. As shown in Fig.
6 (a)-(e), a similar trend is observed among citation networks. PREM achieves
the highest AUC scores when $\alpha$ and $\gamma$ are in equilibrium, while
its performance decreases when either $\alpha$ or $\gamma$ is approaches
extreme values. When both $\alpha$ and $\gamma$ are 0.1, the AUC drops
significantly, indicating the collapse problem. The AUC on the social network
Flickr is more sensitive to changes in hyper-parameters, peaking at
$\alpha=0.3$ and $\gamma=0.4$. To conclude, the trade-off between neighbor
negative and ego negative depends on the properties of datasets, which is
consistent with previous findings [6, 55, 20]. While hyper-parameter turning
becomes expensive for large datasets, it is possible to quickly find the most
appropriate trade-off parameters of PREM for large datasets with limited
computational resources due to the highly efficient and scalable framework and
training procedure.

##  VI Conclusion

This paper introduces PREM, a simple yet powerful graph anomaly detection
method. By leveraging a pre-processing module to pre-compute neighbor
features, PREM eliminates the need for train-time message passing, resulting
in high training efficiency. The prediction of anomaly scores is achieved
through an ego-neighbor matching module that utilizes cosine similarity
between ego and neighbor embeddings, leading to fast and accurate abnormality
estimation. Extensive experiments demonstrate that PREM significantly
outperforms state-of-the-art methods by a large margin, while also exhibiting
high running efficiency and low memory consumption. In future work, we plan to
explore the extension of PREM to address the anomaly detection problem in
complex graph types, such as dynamic graphs, heterogeneous graphs, and
heterophilic graphs.

## References

  * [1] Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günnemann.  Scaling graph neural networks with approximate pagerank.  In SIGKDD, 2020.
  * [2] Markus M Breunig, Hans-Peter Kriegel, Raymond T Ng, and Jörg Sander.  Lof: identifying density-based local outliers.  In SIGMOD, pages 93–104, 2000.
  * [3] Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun.  Spectral networks and locally connected networks on graphs.  ICLR, 2014.
  * [4] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst.  Convolutional neural networks on graphs with fast localized spectral filtering.  In NeurIPS, 2016.
  * [5] Kaize Ding, Jundong Li, Rohit Bhanushali, and Huan Liu.  Deep anomaly detection on attributed networks.  In SDM, 2019.
  * [6] Jingcan Duan, Siwei Wang, Pei Zhang, En Zhu, Jingtao Hu, Hu Jin, Yue Liu, and Zhibin Dong.  Graph anomaly detection via multi-scale contrastive learning networks with augmented view.  In AAAI, 2023.
  * [7] Haoyi Fan, Fengbin Zhang, and Zuoyong Li.  Anomalydae: Dual autoencoder for anomaly detection on attributed networks.  In ICASSP, pages 5685–5689. IEEE, 2020.
  * [8] Xiaotian Han, Tong Zhao, Yozen Liu, Xia Hu, and Neil Shah.  Mlpinit: Embarrassingly simple gnn training acceleration with mlp initialization.  In ICLR, 2023.
  * [9] Kaveh Hassani and Amir Hosein Khasahmadi.  Contrastive multi-view representation learning on graphs.  In ICML, pages 4116–4126, 2020.
  * [10] Mikael Henaff, Joan Bruna, and Yann LeCun.  Deep convolutional networks on graph-structured data.  arXiv preprint arXiv:1506.05163, 2015.
  * [11] Tianjin Huang, Yulong Pei, Vlado Menkovski, and Mykola Pechenizkiy.  Hop-count based self-supervised anomaly detection on attributed networks.  In ECML-PKDD, pages 225–241. Springer, 2022.
  * [12] Ming Jin, Yixin Liu, Yu Zheng, Lianhua Chi, Yuan-Fang Li, and Shirui Pan.  Anemone: Graph anomaly detection with multi-scale contrastive learning.  In CIKM, pages 3122–3126, 2021.
  * [13] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In ICLR, 2017.
  * [14] Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann.  Diffusion improves graph learning.  In NeurIPS, 2019.
  * [15] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  nature, 2015.
  * [16] Jundong Li, Harsh Dani, Xia Hu, and Huan Liu.  Radar: Residual analysis for anomaly detection in attributed networks.  In IJCAI, volume 17, pages 2152–2158, 2017.
  * [17] Yangyang Li, Yipeng Ji, Shaoning Li, Shulong He, Yinhao Cao, Yifeng Liu, Hong Liu, Xiong Li, Jun Shi, and Yangchao Yang.  Relevance-aware anomalous users detection in social network via graph neural network.  In IJCNN, pages 1–8. IEEE, 2021.
  * [18] Yuening Li, Xiao Huang, Jundong Li, Mengnan Du, and Na Zou.  Specae: Spectral autoencoder for anomaly detection in attributed networks.  In CIKM, pages 2233–2236, 2019.
  * [19] Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S Zemel.  Lanczosnet: Multi-scale deep graph convolutional networks.  In ICLR, 2019.
  * [20] Fanzhen Liu, Xiaoxiao Ma, Jia Wu, Jian Yang, Shan Xue, Amin Beheshti, Chuan Zhou, Hao Peng, Quan Z Sheng, and Charu C Aggarwal.  Dagad: Data augmentation for graph anomaly detection.  In ICDM. IEEE, 2022.
  * [21] Yixin Liu, Kaize Ding, Huan Liu, and Shirui Pan.  Good-d: On unsupervised graph out-of-distribution detection.  In WSDM, pages 339–347, 2023.
  * [22] Yixin Liu, Kaize Ding, Jianling Wang, Vincent Lee, Huan Liu, and Shirui Pan.  Learning strong graph neural networks with weak information.  In SIGKDD, pages 1559–1571, 2023.
  * [23] Yixin Liu, Zhao Li, Shirui Pan, Chen Gong, Chuan Zhou, and George Karypis.  Anomaly detection on attributed networks via contrastive self-supervised learning.  IEEE TNNLS, 2021.
  * [24] Yixin Liu, Yizhen Zheng, Daokun Zhang, Vincent CS Lee, and Shirui Pan.  Beyond smoothing: Unsupervised graph representation learning with edge heterophily discriminating.  In AAAI, volume 37, pages 4516–4524, 2023.
  * [25] Yixin Liu, Yu Zheng, Daokun Zhang, Hongxu Chen, Hao Peng, and Shirui Pan.  Towards unsupervised deep graph structure learning.  In WWW, pages 1392–1403, 2022.
  * [26] Linhao Luo, Yuan-Fang Li, Gholamreza Haffari, and Shirui Pan.  Reasoning on graphs: Faithful and interpretable large language model reasoning.  arXiv preprint arxiv:2310.01061, 2023.
  * [27] Xuexiong Luo, Jia Wu, Amin Beheshti, Jian Yang, Xiankun Zhang, Yuan Wang, and Shan Xue.  Comga: Community-aware attributed graph anomaly detection.  In WSDM, pages 657–665, 2022.
  * [28] Chengsheng Mao, Liang Yao, and Yuan Luo.  Medgcn: Graph convolutional networks for multiple medical tasks.  arXiv preprint arXiv:1904.00326, 2019.
  * [29] Zhen Peng, Minnan Luo, Jundong Li, Huan Liu, Qinghua Zheng, et al.  Anomalous: A joint modeling approach for anomaly detection on attributed networks.  In IJCAI, pages 3513–3519, 2018.
  * [30] Bryan Perozzi and Leman Akoglu.  Scalable anomaly ranking of attributed neighborhoods.  In SDM, pages 207–215. SIAM, 2016.
  * [31] Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang.  Gcc: Graph contrastive coding for graph neural network pre-training.  In SIGKDD, 2020.
  * [32] Joshua Robinson, Ching-Yao Chuang, Suvrit Sra, and Stefanie Jegelka.  Contrastive learning with hard negative samples.  In ICLR, 2021.
  * [33] David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst.  The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains.  IEEE signal processing magazine, 30(3):83–98, 2013.
  * [34] Yue Tan, Yixin Liu, Guodong Long, Jing Jiang, Qinghua Lu, and Chengqi Zhang.  Federated learning on non-iid graphs via structural knowledge sharing.  In AAAI, volume 37, pages 9953–9961, 2023.
  * [35] Chang Tang, Xinwang Liu, Xinzhong Zhu, En Zhu, Zhigang Luo, Lizhe Wang, and Wen Gao.  Cgd: Multi-view clustering via cross-view graph diffusion.  In AAAI, 2020.
  * [36] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In NeurIPS, 2017.
  * [37] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  In ICLR, 2018.
  * [38] Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm.  Deep graph infomax.  In ICLR, 2019.
  * [39] Haibo Wang, Chuan Zhou, Jia Wu, Weizhen Dang, Xingquan Zhu, and Jilong Wang.  Deep structure learning for fraud detection.  In ICDM, pages 567–576. IEEE, 2018.
  * [40] Xuhong Wang, Baihong Jin, Ying Du, Ping Cui, Yingshui Tan, and Yupu Yang.  One-class graph neural networks for anomaly detection in attributed networks.  Neural computing and applications, 33:12073–12085, 2021.
  * [41] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger.  Simplifying graph convolutional networks.  In ICML. PMLR, 2019.
  * [42] Man Wu, Shirui Pan, Lan Du, and Xingquan Zhu.  Learning graph neural networks with positive and unlabeled nodes.  ACM TKDD, 2021.
  * [43] Fengli Xu, Jianxun Lian, Zhenyu Han, Yong Li, Yujian Xu, and Xing Xie.  Relation-aware graph convolutional networks for agent-initiated social e-commerce recommendation.  In CIKM, pages 529–538, 2019.
  * [44] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen.  Graph contrastive learning with augmentations.  In NeurIPS, volume 33, pages 5812–5823, 2020.
  * [45] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna.  Graphsaint: Graph sampling based inductive learning method.  In ICLR, 2020.
  * [46] Jiaqiang Zhang, Senzhang Wang, and Songcan Chen.  Reconstruction enhanced multi-view contrastive learning for anomaly detection on attributed networks.  In IJCAI, 2022.
  * [47] Zheng Zhang and Liang Zhao.  Unsupervised deep subgraph anomaly detection.  In ICDM, pages 753–762. IEEE, 2022.
  * [48] Xin Zheng, Yixin Liu, Zhifeng Bao, Meng Fang, Xia Hu, Alan Wee-Chung Liew, and Shirui Pan.  Towards data-centric graph machine learning: Review and outlook.  arXiv preprint arXiv:2309.10979, 2023.
  * [49] Xin Zheng, Miao Zhang, Chunyang Chen, Quoc Viet Hung Nguyen, Xingquan Zhu, and Shirui Pan.  Structure-free graph condensation: From large-scale graphs to condensed graph-free data.  In NeurIPS, 2023.
  * [50] Yizhen Zheng, Ming Jin, Shirui Pan, Yuan-Fang Li, Hao Peng, Ming Li, and Zhao Li.  Toward graph self-supervised learning with contrastive adjusted zooming.  IEEE TNNLS, 2022.
  * [51] Yizhen Zheng, Shirui Pan, Vincent Lee, Yu Zheng, and Philip S Yu.  Rethinking and scaling up graph contrastive learning: An extremely efficient approach with group discrimination.  In NeurIPS, volume 35, pages 10809–10820, 2022.
  * [52] Yizhen Zheng, CS Lee Vincent, Zonghan Wu, and Shirui Pan.  Heterogeneous graph attention network for small and medium-sized enterprises bankruptcy prediction.  In PAKDD, 2021.
  * [53] Yizhen Zheng, He Zhang, Vincent Lee, Yu Zheng, Xiao Wang, and Shirui Pan.  Finding the missing-half: Graph complementary learning for homophily-prone and heterophily-prone graphs.  arXiv preprint arXiv:2306.07608, 2023.
  * [54] Yizhen Zheng, Yu Zheng, Xiaofei Zhou, Chen Gong, Vincent CS Lee, and Shirui Pan.  Unifying graph contrastive learning with flexible contextual scopes.  In ICDM, pages 793–802. IEEE, 2022.
  * [55] Yu Zheng, Ming Jin, Yixin Liu, Lianhua Chi, Khoa T Phan, and Yi-Ping Phoebe Chen.  Generative and contrastive self-supervised learning for graph anomaly detection.  IEEE TKDE, 2021.
  * [56] Shuang Zhou, Qiaoyu Tan, Zhiming Xu, Xiao Huang, and Fu-lai Chung.  Subtractive aggregation for attributed network anomaly detection.  In CIKM, pages 3672–3676, 2021.
  * [57] Mengxiao Zhu and Haogang Zhu.  Mixedad: A scalable algorithm for detecting mixed anomalies in attributed graphs.  In AAAI, volume 34, pages 1274–1281, 2020.
  * [58] Xiaoke Zhu, Xiao-Yuan Jing, Fan Zhang, Xinyu Zhang, Xinge You, and Xiang Cui.  Distance learning by mining hard and easy negative samples for person re-identification.  Pattern Recognition, 95:211–222, 2019.
  * [59] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang.  Graph contrastive learning with adaptive augmentation.  In WWW, pages 2069–2080, 2021.