# Data Augmentation for Supervised Graph Outlier Detection with Latent
Diffusion Models

Kay Liu1, Hengrui Zhang1, Ziqing Hu2∗, Fangxin Wang1, Philip S. Yu1 ∗Work done
during Ziqing Hu’s PhD at the University of Notre Dame 1University of Illinois
Chicago, Chicago, United States
2Amazon, Chicago, United States
{zliu234, hzhan55, fwang51<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Graph outlier detection is a prominent task of research and application in the
realm of graph neural networks. It identifies the outlier nodes that exhibit
deviation from the majority in the graph. One of the fundamental challenges
confronting supervised graph outlier detection algorithms is the prevalent
issue of class imbalance, where the scarcity of outlier instances compared to
normal instances often results in suboptimal performance. Conventional methods
mitigate the imbalance by reweighting instances in the estimation of the loss
function, assigning higher weights to outliers and lower weights to inliers.
Nonetheless, these strategies are prone to overfitting and underfitting,
respectively. Recently, generative models, especially diffusion models, have
demonstrated their efficacy in synthesizing high-fidelity images. Despite
their extraordinary generation quality, their potential in data augmentation
for supervised graph outlier detection remains largely underexplored.

To bridge this gap, we introduce GODM, a novel data augmentation for
mitigating class imbalance in supervised Graph Outlier detection with latent
Diffusion Models. Specifically, our proposed method consists of three key
components: (1) Variantioanl Encoder maps the heterogeneous information
inherent within the graph data into a unified latent space. (2) Graph
Generator synthesizes graph data that are statistically similar to real
outliers from latent space, and (3) Latent Diffusion Model learns the latent
space distribution of real organic data by iterative denoising. Extensive
experiments conducted on multiple datasets substantiate the effectiveness and
efficiency of GODM. The case study further demonstrated the generation quality
of our synthetic data. To foster accessibility and reproducibility, we
encapsulate GODM into a plug-and-play package and release it at the Python
Package Index (PyPI): https://pypi.org/project/godm/.

###### Index Terms:

Graph Outlier Detection, Data Augmentation, Diffusion Models, Class Imbalance,
Anomaly Detection

##  I Introduction

Graphs are foundational data structures that capture complex relationships
among diverse entities. Recently, graph data mining has showcased
effectiveness and flexibility across various tasks, including community
classification among academic citation networks [1], recommender systems in
social networks [2], knowledge graph completion [3], and so on and forth.
Within this broad spectrum of applications, graph outlier detection has
emerged as a popular and important area of research and practice [4, 5, 6].
Graph outlier detection focuses on detecting outliers within graph-structured
data that significantly deviate from standard patterns, which has proven
valuable in domains such as financial fraud detection in bank systems [7],
fake news detection on social media [8], spam detection on review platform
[9], and anti-money laundering in transaction networks [10].

However, despite the advancements in graph outlier detection techniques,
similar to supervised outlier detection on other data modalities, graph
outlier detection suffers a fundamental challenge known as class imbalance,
where the number of positive instances (outliers) is significantly lower than
the number of negative instances (inliers). For example, the ratio of positive
to negative is only 1:85 in the DGraph dataset [7], reflecting the real-world
extreme ratio in financial fraud detection scenario. This class imbalance
problem poses challenges in the training of outlier detectors and often
results in suboptimal performance. Specifically, as the negative instances
dominate the training data, the loss function can be biased towards the
majority of the negative class and, hence, exhibit poor generalization
capability in identifying true outliers. In the worst case, a detector could
classify every instance as negative, displaying seemingly low loss value and
high accuracy score, yet basically lacking any knowledge.

Figure 1: An toy example of data augmentation for class imbalance in graph
outlier detection. Synthetic outliers help balance the class distribution in
the training data, thereby improving the performance of graph outlier
detection.

Common practices mitigate this imbalance by upsampling or downsampling [11].
Upsampling augments the minority positive class by simply replicating
outliers, whereas downsampling reduces the size of the majority negative class
by randomly dropping normal instances. However, while beneficial in certain
contexts, these methods often introduce their own challenges, such as the risk
of overfitting outliers in the case of upsampling or the loss of valuable
training data through downsampling. Another common approach to alleviate class
imbalance is through instance reweighting in the loss function estimation. It
allocates greater weights to positive instances and assigns lesser weights to
negative instances. This approach is mathematically equivalent to upsampling
and downsampling, thereby having a similar tendency to overfit outliers or
underfitting inliers. These challenges underscore the need for more
sophisticated data augmentation methods that can generate some synthetic data
to handle the class imbalance in graph outlier detection, as Fig. 1 shows.

In recent years, generative models, particularly diffusion models, have
achieved significant advancements in synthesizing high-fidelity image data
[12]. Diffusion models capture intricate data distributions and generate high-
quality samples by gradually denoising the samples from a simple prior
distribution (e.g., Gaussian distribution). On graph data, although some works
have explored the possibility of diffusion on molecular graphs [13, 14], few
studies have been conducted to apply diffusion models to tackle the class
imbalance problem in the task of graph outlier detection. However, existing
diffusion models can hardly be directly adapted to large-scale graph outlier
detection applications due to the following non-trivial challenges: (1)
Heterogeneity: Unlike relatively simple molecular graphs, the information
contained in graphs for outlier detection can be highly heterogeneous,
including high dimensional features and more than one type of edge, even
temporal information. Existing diffusion models are primarily designed for
monotypic information, exemplified by the RGB channels in image data. (2)
Efficiency: In the application of graph outlier detection, e.g., financial
fraud detection, the graphs are typically much larger than molecular graphs,
up to millions, even billions scale. The prohibitive computational cost of
diffusion models hinders their direct application in outlier detection on
large graphs. (3) Condition: Different from the unconditional generation on
molecular graphs, conditional generation is required to mitigate the problem
of class imbalance. We only want to generate outliers rather than normal nodes
in synthetic graphs.

To bridge this gap, we make the first attempt to leverage diffusion models in
graph outlier detection and propose a data augmentation for mitigating class
imbalance in supervised Graph Outlier detection with latent Diffusion Models
(GODM). Our main idea is to generate outliers in graph space while conducting
diffusion in latent space. To address heterogeneity, we propose Variantioanl
Encoder to map the heterogeneous information inherent within the graph data
into a unified latent space. In addition, Graph Generator synthesizes
different types of information back to graph space from the latent embedding.
To alleviate the efficiency problem, instead of direct diffusion in graph
space, we only conduct diffusion in the latent space crafted by the
variational encoder. Furthermore, we use negative sampling and graph
clustering to reduce the computational cost. For diffusion models, we also
adopt EDM [15] instead of commonly used DDPM [16] to facilitate the generation
efficiency of Latent Diffusion Model. For the condition, we not only give a
class label to the variational encoder to form node embedding with class
information but also conduct conditional generation on both Latent Diffusion
Model and Graph Generator. Finally, our heterogeneous, efficient, and
conditional GODM can generate graphs with outliers that are integrated with
the original real graph for the training of the downstream graph outlier
detector. Importantly, GODM is model agnostic, providing researchers and
practitioners with the flexibility to integrate it across various graph
outlier detectors.

Our contributions in this paper are mainly as follows:

  * •

We make the first attempt to leverage diffusion models in graph outlier
detection and propose to adopt diffusion models in the latent space and bridge
the graph space and the latent space with a variational encoder and graph
generator for heterogeneity.

  * •

We further design outlier-only generation conditioned on outlier labels and
improve the efficiency of GODM by negative sampling, graph clustering, and
EDM.

  * •

We conduct extensive experiments to demonstrate the effectiveness and
efficiency of GODM. To foster accessibility, we make our code a plug-and-play
package, which is publicly available at: https://pypi.org/project/godm/.

The remainder of this paper is organized as follows. Section II formally
defines the notation and the problem we studied in this paper. Section III
provides an overview of GODM. Section IV gives detailed experimental results
and analyses. Section V briefly describes related works. We summarize the
paper and discuss future work in Section VI.

##  II Preliminary

Figure 2: The architecture of proposed data augmentation method GODM. For a
given graph $\mathcal{G}$, GODM first partitions the large graph by graph
clustering algorithms and conducts negative sampling on edge, reducing the
computational cost. Then, a GNN-based Variational Encoder maps each node in
subgraphs into the latent space embedding $\mathbf{Z}^{0}$. A forward
diffusion process $\mathbf{Z}^{0}\rightarrow\mathbf{Z}^{S}$ is applied in the
latent space. Reverse denoising process
$\hat{\mathbf{Z}}^{S}\rightarrow\hat{\mathbf{Z}}^{0}$ starts from the prior
distribution $p(\hat{\mathbf{Z}}^{S})$ and generates samples
$\hat{\mathbf{Z}}^{0}$ in latent space with denoising MLP conditioned on
outlier labels $\hat{\mathbf{y}}$. Graph Generator also conditionally generate
node features $\hat{\mathbf{X}}$, graph structures $\hat{\mathcal{E}}$, edge
timestamps $\hat{\mathbf{t}}$, and edge types $\hat{\mathbf{p}}$ from latent
embedding $\hat{\mathbf{Z}}^{0}$. By ensembling all necessary information, we
obtain the synthetic graph $\hat{\mathcal{G}}$. Along with the real graph
${\mathcal{G}}$, $\hat{\mathcal{G}}$ will be used for the training of the
downstream graph outlier detector $D$.

In this section, we establish the notation adopted in the subsequent sections
and rigorously formulate the problem of data augmentation for addressing class
imbalance in supervised graph outlier detection.

###  II-A Notation

Let
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X},\mathbf{y},\mathbf{t},\mathbf{p})$
denotes a graph with $n$ nodes, where $\mathcal{V}=\\{v_{i}\\}_{i=1}^{n}$ is
the set of nodes, and $\mathcal{E}=\\{e_{ij}\\}$ represents the set of edges.
Here, $e_{ij}=(v_{i},v_{j})$ denotes an edge between node $v_{i}$ and node
$v_{j}$. The matrix $\mathbf{X}\in\mathbb{R}^{n\times d}$ contains
$d$-dimensional feature vectors $\mathbf{x}_{i}$ for each node $v_{i}$.
$\mathbf{y}\in\\{0,1\\}^{n}$ represents the vector of the node label $y_{i}$
for each node $v_{i}$, where $0$ denotes an inlier, while $1$ denotes an
outlier. $\mathbf{t}=\\{t_{ij}\\}\in\mathbb{N}$ and
$\mathbf{p}=\\{p_{ij}\\}\in\\{1,\ldots,P\\}$ are the optional non-negative
integer edge timestamp vector and edge type vector, respectively, where $P$ is
the number of edge types.

###  II-B Problem Formulation

In this paper, we focus on the task of graph outlier detection, which is
formally defined as:

######  Definition 1 (Graph Outlier Detection)

Given a graph $\mathcal{G}$, graph outlier detection can be regarded as a
binary classification task that learns a detector
$D:v_{i}\rightarrow\\{0,1\\}$ that classifies every node in $\mathcal{G}$ to
an inlier (0) or an outlier (1).

In the task of graph outlier detection, we aim to mitigate class imbalance by
data augmentation:

######  Definition 2 (Data Augmentation for Class Imbalance)

In outlier detection, the number of inliers is far more than the number of
outliers, i.e., $|\\{v_{i}\mid y_{i}=0\\}|\gg|\\{v_{i}\mid y_{i}=1\\}|$.
Therefore, we aim to learn a parameterized data augmentation model, which can
generate realistic and diverse synthetic graph
$\hat{\mathcal{G}}=(\hat{\mathcal{V}},\hat{\mathcal{E}},\hat{\mathbf{X}},\hat{\mathbf{y}},\hat{\mathbf{t}},\hat{\mathbf{p}})$,
where $\hat{y_{i}}=1,\forall v_{i}\in\hat{\mathcal{V}}$. To alleviate the
class imbalance in the training of the graph outlier detector $D$, we
integrate the original graph $\mathcal{G}$ and the synthetic graph
$\hat{\mathcal{G}}$ for the training of detector $D$.

##  III Methodology

In this section, we elaborate on the proposed data augmentation method GODM in
detail. Fig. 2 shows the architecture of GODM. It starts by partitioning the
input graph $\mathcal{G}$ with graph clustering algorithms for reducing memory
consumption. Subsequently, each partitioned subgraph is encoded into a latent
space representation denoted by $\mathbf{Z}^{0}$ through Variational Encoder
based on graph neural networks (GNNs), followed by a forward diffusion
$\mathbf{Z}^{0}\rightarrow\mathbf{Z}^{S}$ in the latent space, where $S$ is
the maximum step in the diffusion model. The reverse denoising process
$\hat{\mathbf{Z}}^{S}\rightarrow\hat{\mathbf{Z}}^{0}$ iteratively estimates
the noise and generates the latent embedding $\hat{\mathbf{Z}}^{0}$ from a
predefined prior distribution $p(\hat{\mathbf{Z}}^{S})$ using a denoising
function, which is a multi-layer perceptron (MLP), conditioned on class labels
$\hat{\mathbf{y}}$. Graph Generator employs the latent representations
$\hat{\mathbf{Z}}^{0}$ to conditionally reconstruct the node features and
graph structures alongside other information available in the original real
graph. By ensembling generated information, we are able to obtain
$\hat{\mathcal{G}}$ that contains the nodes that are statistically similar to
the real outliers. This synthetic graph $\hat{\mathcal{G}}$, in concert with
the original graph $\mathcal{G}$, is leveraged to enhance the training
efficacy of the downstream graph outlier detection task.

In Section III-A and Section III-B, we introduce the design details of the
Variational Encoder and Graph Generator, respectively. Then, we describe
Latent Diffusion Model in Section III-C. We summarize the training and
inference process in Section III-D and Section III-E, respectively. Finally,
we analyze the algorithmic complexity in Section III-F.

###  III-A Variational Encoder

Graph data is inherently complex and heterogeneous, containing both node
feature $\mathbf{X}$ and graph structure $\mathcal{E}$, sometimes also partial
node class labels $\mathbf{y}$, temporal information $\mathbf{t}$, and
different types of edges $\mathbf{p}$. However, current diffusion models are
mainly designed for monotypic information (e.g., the magnitude of RGB channels
in images). To bridge this gap, we adopt a GNN-based Variational Encoder
$E:\mathcal{G}\rightarrow\mathbf{Z}$ to map different types of information to
a unified latent space.

Node Feature. To encode the node feature into the latent space, we take the
feature of each node as the initial embedding for the encoder, i.e.,
$\mathbf{h}_{i}^{0}=\mathbf{x}_{i}$.

Class Label. As we only generate outliers by conditional generation, it will
be helpful to encode node labels $\mathbf{y}=\\{y_{i}\\}$. We add the class
information to the initial node embedding:

$\mathbf{h}_{i}^{0}=\mathbf{x}_{i}+\mathbf{w}^{C}_{E}\cdot y_{i},$ (1)

where $\mathbf{w}^{C}_{E}\in\mathbb{R}^{d}$ is a linear transformation for
class label.

Graph Structure. Graph neural networks have emerged as a profound architecture
for learning graph data, efficaciously learning the node representations by
encoding the graph topology and node feature simultaneously with message
passing. In this paper, we take GraphSAGE [17] as an example. For each layer
of GraphSAGE, each node updates its embedding by aggregating the message
within the neighborhood:

$\mathbf{h}_{i}^{l}=\text{ACT}(\mathbf{W}^{l}\cdot\text{CAT}(\mathbf{h}_{i}^{l-1},\text{AGG}(\\{\mathbf{m}_{ij}^{l},\forall
e_{ij}\in\mathcal{E}\\}),$ (2)

where $\mathbf{h}_{i}^{l}$ is the node embedding for node $v_{i}$ in the
$l-$th layer, $\mathbf{m}_{ij}^{l}$ is the edge-wise message of edge $e_{ij}$,
and ACT is a non-linear activation function.
$\mathbf{W}^{l}\in\mathbb{R}^{d^{l}\times 2d^{l-1}}$ is the linear
transformation matrix, where $d^{l}$ and $d^{l-1}$ are the hidden dimension of
$l$-th layer and $(l-1)$-th layer, respectively. While CAT represents
concatenation, AGG denotes the aggregation function (e.g., mean). In the
vanilla GraphSAGE, an edge-wise message is typically the embedding of source
node $v_{j}$ from the last layer:

$\mathbf{m}_{ij}^{l}=\mathbf{h}_{j}^{l-1}.$ (3)

Edge Type. However, sometimes, we have different types of edges in graphs,
known as heterogeneous graphs or heterogeneous information networks [18, 19].
As different edge types can encapsulate various semantics, encoding edge types
can be important for the downstream task. Therefore, we add the type
information to the edge-wise message:

$\mathbf{m}_{ij}^{l}=\mathbf{h}_{j}^{l-1}+\mathbf{W}^{P}\cdot\phi(p_{ij}),$
(4)

where $\mathbf{W}^{P}\in\mathbb{R}^{d^{l-1}\times P}$ is a linear
transformation for edge type, and $\phi$ is the one-hot encoding function.

Edge Time. In addition, temporal information is critical in time series
applications [20]. When edge time is available, we are also able to encode the
timestamp to the edge-wise message with trigonometric temporal embedding [21]:

$\mathbf{m}_{ij}^{l}=\mathbf{h}_{j}^{l-1}+\mathbf{W}^{T}\cdot
TE_{(t_{ij},\cdot)},$ (5)

where $\mathbf{W}^{T}\in\mathbb{R}^{d^{l-1}\times d^{l-1}}$ is the linear
transformation for edge time, and $TE$ is defined as:

$\displaystyle TE_{(t_{ij},2k)}=sin(t_{ij}/10000^{2k/d^{l-1}}),$ (6)
$\displaystyle TE_{(t_{ij},2k+1)}=cos(t_{ij}/10000^{2k/d^{l-1}}),$

where $k$ is each dimension of the temporal embedding.

By stacking multiple layers, GNNs are capable of encoding both node features
and neighborhood graph structures into independent and identically distributed
(i.i.d.) node embedding $\mathbf{Z}$, which can be further leveraged by Latent
Diffusion Model. To ease the generation for Latent Diffusion Model, we use
Variational Encoder, which outputs two matrixes:

$\displaystyle\bm{\mu}=\text{GNN}_{\bm{\mu}}(\text{GNN}_{\text{shared}}(\mathcal{G})),$
(7)
$\displaystyle\text{log}\bm{\sigma}=\text{GNN}_{\bm{\sigma}}(\text{GNN}_{\text{shared}}(\mathcal{G})),$

where $\bm{\mu}$ is the matrix of mean and log $\bm{\sigma}$ is the matrix of
log standard deviation. While GNN${}_{\text{shared}}$ is the shared GNN head,
GNNμ and GNNσ are specifically for $\bm{\mu}$ and $\bm{\sigma}$, respectively.
Then, the latent space embedding $\mathbf{Z}$ can be obtained via the
parameterization trick:

$\mathbf{Z}=\bm{\mu}+\bm{\sigma}\cdot\bm{\varepsilon},\bm{\varepsilon}\sim\mathcal{N}(\bm{0},\bm{I}),$
(8)

where $\mathcal{N}(\bm{0},\bm{I})$ refers to a multivariate normal (or
Gaussian) distribution with a mean of $\bm{0}$ and a covariance of $\bm{I}$,
where $\bm{0}$ denotes a zero vector, and $\bm{I}$ represents a identity
matrix.

###  III-B Graph Generator

Graph Generator $G:\hat{\mathbf{Z}}\rightarrow\hat{\mathcal{G}}$ take the
opposite process of Variational Encoder, generating
$\hat{\mathcal{G}}=(\hat{\mathcal{V}},\hat{\mathcal{E}},\hat{\mathbf{X}},\hat{\mathbf{y}},\hat{\mathbf{t}},\hat{\mathbf{p}})$
given the latent space embedding $\hat{\mathbf{Z}}$. Each row
$\hat{\mathbf{z}}_{i}$ in the embedding $\hat{\mathbf{Z}}$ is corresponding to
a generated node $\hat{v}_{i}$ in $\hat{\mathcal{V}}$.

Class Label. Recall that our objective is exclusively generating outliers with
positive labels. Consequently, rather than generating class labels, we take
the desired labels as an input for conditional generation.

$\hat{\mathbf{z}}_{i}^{C}=\hat{\mathbf{z}}_{i}+\mathbf{w}^{C}_{G}\cdot\hat{y}_{i},$
(9)

where $\hat{\mathbf{z}}_{i}$ is the $i$-th row of $\hat{\mathbf{Z}}$ and
$\hat{\mathbf{z}}_{i}^{C}$ is embedding with class condition.
$\mathbf{w}^{C}_{G}\in\mathbb{R}^{d^{L}}$ is the linear transformation for the
class label, and $d^{L}$ is the output dimension of the $L$-th layer of the
encoder, i.e., the latent embedding dimension of $\hat{\mathbf{z}}_{i}$.

Node Feature. To generate the node feature $\hat{\mathbf{X}}$ from the latent
space embedding, for the $i$-th row of $\hat{\mathbf{X}}$, we take the
embedding with class condition $\hat{\mathbf{z}}_{i}^{C}$ as input:

$\hat{\mathbf{x}}_{i}=\mathbf{W}^{F}_{G}\cdot\hat{\mathbf{z}}_{i}^{C},$ (10)

where $\mathbf{W}^{F}_{G}\in\mathbb{R}^{d\times d^{L}}$ is the linear
transformation for node feature generaion.

Graph Structure. The generation of graph structures denoted by the set of
inferred edges $\hat{\mathcal{E}}$ requires link prediction between all
pairwise combinations of nodes within the graph. The predicted edge score
$\hat{e}_{ij}$ can be formulated as:

$\hat{e}_{ij}=\text{sigmoid}(\mathbf{w}^{E}_{G}\cdot\text{CAT}(\hat{\mathbf{z}}_{i}^{C},\hat{\mathbf{z}}_{j}^{C})),\forall(\hat{v}_{i},\hat{v}_{j})\in\mathcal{\hat{V}}\times\mathcal{\hat{V}},$
(11)

where $\mathbf{w}^{E}_{G}\in\mathbb{R}^{2d^{L}}$ is the linearn transformation
for the edge generation. The generated edges are determined as follows:

$\hat{\mathcal{E}}=\\{(\hat{v}_{i},\hat{v}_{j})\mid\hat{e}_{ij}\geq 0.5\\}$
(12)

Edge Type. With the generated edges in hand, we can predict the type of every
generated edge:

$\hat{p}_{ij}=\text{softmax}(\mathbf{W}^{P}_{G}\cdot\text{CAT}(\hat{\mathbf{z}}_{i}^{C},\hat{\mathbf{z}}_{j}^{C})),\forall(\hat{v}_{i},\hat{v}_{j})\in\mathcal{\hat{E}},$
(13)

where $\mathbf{W}^{P}_{G}\in\mathbb{R}^{P\times 2d^{L}}$ is the linearn
transformation for the edge type prediction.

Edge Time. Similarly, the timestamp of generated edges can be predicted as:

$\hat{t}_{ij}=\mathbf{w}^{T}_{G}\cdot\text{CAT}(\hat{\mathbf{z}}_{i}^{C},\hat{\mathbf{z}}_{j}^{C}),\forall(\hat{v}_{i},\hat{v}_{j})\in\mathcal{\hat{E}},$
(14)

where $\mathbf{w}^{T}_{G}\in\mathbb{R}^{2d^{L}}$ is the linear transformation
for the edge timestamp regression.

###  III-C Latent Diffusion Model

Utilizing Variational Encoder and Graph Generator, synthetic graph generation
is already feasible. Nonetheless, the inherent complexity and heterogeneity of
graph data pose a significant challenge when attempting a one-step estimation
from a simple prior distribution, such as a Gaussian distribution, to the
intricate target distribution. This challenge often leads to compromised
generation quality and results in a marginal effect on the downstream graph
outlier detection. Therefore, we integrate Latent Diffusion Model [12] to
break down the estimation into a sequence of incremental steps. In each step,
Latent Diffusion Model incrementally refines the distribution estimated,
bridging the divergence between the simple prior and the intricate target
distribution.

Latent Diffusion Model consists of a pair of processes. A fixed forward
diffusion process perturbs the original data by the incremental adding
Gaussian noise across a range of variances, and a reverse denoising process
employs a learned denoising function to iteratively denoise the samples from a
simple prior distribution, which is pure noise. In order to speed up the
generation process, we adopt EDM [15] as our diffusion model. For the detailed
design, we follow [22].

Forward Diffusion Process. We construct a forward diffusion process
$\\{\mathbf{Z}(s)\\}_{s=0}^{S}$, where $s\in[0,S]$ is a continuous diffusion
step. In the diffusion process, $\mathbf{Z}(0)=\mathbf{Z}$ is the embedding
from Variational Encoder, while $\mathbf{Z}(S)\sim\mathcal{N}(\bm{0},\bm{I})$
is sampled from the prior distribution. According to [23], the forward
diffusion process can be written in stochastic differential equation (SDE) as:

${\rm d}\mathbf{Z}=\bm{f}(\mathbf{Z},s){\rm d}s+g(s){\rm d}\bm{\omega}_{t},$
(15)

where $\bm{\omega}_{t}$ is the standard Wiener process (i.e., Brownian
motion). $\bm{f}(\cdot,s)$ and $g(\cdot)$ are the drift coefficient and the
diffusion coefficient, respectively. The selection of $\bm{f}(\cdot,s)$ and
$g(\cdot)$ vary between different diffusion models. $f(\cdot)$ is usually of
the form $\bm{f}(\mathbf{Z},s)=f(s)\mathbf{Z}$. Thus, Eq. 15 can be written
as:

${\rm d}\mathbf{Z}=f(s)\mathbf{Z}{\rm d}s+g(s){\rm d}\bm{\omega}_{t}.$ (16)

Let $\mathbf{Z}$ be a function of diffusion step $s$, i.e.,
$\mathbf{Z}^{s}=\mathbf{Z}(s)$. The diffusion kernel of Eq. 16 can be
represented in the conditional distribution of $\mathbf{Z}^{s}$ given
$\mathbf{Z}^{0}$:

$p(\mathbf{Z}^{s}|\mathbf{Z}^{0})=\mathcal{N}(a(s)\mathbf{Z}^{0},a^{2}(s)\sigma^{2}(s)\bm{I}),$
(17)

where $a(s)$ and $\sigma(s)$ can be derived as:

$a(s)=\exp{\int_{0}^{s}f(\xi)\rm d\xi},$ (18)
$\sigma(s)=\sqrt{\int_{0}^{s}g^{2}(\xi)/a^{2}(\xi)\rm d\xi}.$ (19)

Consequently, the formulation of the forward diffusion process is equivalent
to the definition of diffusion kernels characterized by $a(s)$ and
$\sigma(s)$.

Conventional denoising diffusion probabilistic models (DDPM) [16] can be seen
as discretizations of the variance preserving SDE with
$a(s)=\sqrt{1-\beta(s)}$ and $\sigma(s)=\sqrt{\beta(s)/{(1-\beta(s))}}$, as
$a^{2}(s)+a^{2}(s)\sigma^{2}(s)=1$. However, in order to achieve more
efficient generation in GODM, we adopt EDM [15], which belongs to variance
exploding SDE. Variance exploding SDE set $a(s)=1$, which implies that noise
is directly added to the data instead of being blended through weighting. In
this case, the variance of the noise (the noise level) is exclusively
determined by $\sigma(s)$. In EDM, a linear noise level $\sigma(s)=s$ is
applied. Therefore, the diffusion kernel can be written as:

$p(\mathbf{Z}^{s}|\mathbf{Z}^{0})=\mathcal{N}(\bm{0},\sigma^{2}(s)\bm{I}),$
(20)

and the forward diffusion process can be formulated as:

$\mathbf{Z}^{s}=\mathbf{Z}^{0}+\sigma(s)\bm{\varepsilon},\bm{\varepsilon}\sim\mathcal{N}(\bm{0},\bm{I}).$
(21)

Reverse Denoising Process. As derived in [23], the reverse denoising process
is formulated as the reverse SDE of Eq. 15:

${\rm d}\mathbf{Z}=[\bm{f}(\mathbf{Z},s)-g^{2}(s)\nabla_{\mathbf{Z}}\log
p_{s}(\mathbf{Z})]{\rm d}s+g(s){\rm d}\bm{\omega}_{s},$ (22)

where $\nabla_{\mathbf{Z}}\log p_{s}(\mathbf{Z})$ is the score function of
$\mathbf{Z}$. In EDM, given $a(s)=1$ and Eq. 18, it follows that,

$\bm{f}(\mathbf{Z},s)=f(s)\mathbf{Z}=\bm{0}.$ (23)

For the $g(s)$, derived from Eq. 19, we obtain

$g(s)=\sqrt{2\sigma(s)\dot{\sigma}(s)},$ (24)

where $\dot{\sigma}$ denotes the first order derivative of $\sigma$. With
$\bm{f}(\mathbf{Z},s)$ and $g(s)$, we are able to obtain:

${\rm d}\mathbf{Z}=-2\dot{\sigma}(s)\sigma(s)\nabla_{\mathbf{Z}}\log
p_{s}(\mathbf{Z}){\rm d}s+\sqrt{2\dot{\sigma}(s)\sigma(s)}{\rm
d}\bm{\omega}_{s},$ (25)

where the noise level $\sigma(s)=s$.

###  III-D Training

Conventional graph generative models are highly constrained in scalability.
Typical graph generative models are working molecular graphs that are at
hundreds node scale [24]. However, outlier detection graphs are usually much
larger, scaling to millions, even billions. Efficient training of generative
models on large graphs requires special designs. We propose to apply negative
sampling and graph clustering to improve the scalability of GODM.

Negative Sampling. In the graph structure generation, if the training of the
generator includes every pair of nodes, this leads to a computational
complexity of $O(n^{2})$. This parabolic complexity is catastrophic for large
graphs (e.g., millions scale). Furthermore, it will result in a high imbalance
in the training of the edge predictor itself. Negative sampling emerges as a
crucial technique to reduce computational cost and alleviate the imbalance. To
form a concise training set $\bar{\mathcal{E}}$ for edge generator, apart from
adding the positive edge, i.e., $\\{\bar{e}_{ij}=1\mid
e_{ij}\in\mathcal{E}\\}$, we randomly select a negative edge (a pair of nodes
that is not connected) corresponding to every positive edge,
$\\{\bar{e}_{\tilde{i}\tilde{j}}=0\mid
e_{\tilde{i}\tilde{j}}\notin\mathcal{E}\\}$. By this means, we reduce the
complexity from $O(n^{2})$ to $O(|\mathcal{E}|)$.

Graph Clustering. When the graph scales to millions of nodes, full-batch
training becomes impractical, even with negative sampling. In addition,
traditional neighbor sampling methods are well-suited in our case, as we need
to reconstruct both the node feature and graph structure (i.e., edges).
Specifically, node sampling cannot gather complete information for edge
prediction, while edge sampling favors the nodes with a high degree. To
address these challenges, we resort to graph clustering inspired by [25]. We
first apply graph clustering algorithms (e.g., Metis [26]) to divide the large
graph into small partitions. Then, we treat each partition as a minibatch and
train GODM on each partition instead of the full graph.

Leveraging these two techniques, we are able to efficiently train GODM in two
steps. We first train Variational Encoder and Graph Generator to bridge the
graph space and latent space. Then, we train the diffusion model in the latent
space.

Variational Encoder and Graph Generator. By integrating Variational Encoder
and Graph Generator, we are able to train both of them in a variational
autoencoder (VAE) fashion. We reconstruct the node feature with mean squared
error:

$\ell_{\mathbf{X}}=\frac{1}{|\mathcal{V}|}\sum_{v_{i}\in\mathcal{V}}\|\mathbf{x}_{i}-\hat{\mathbf{x}}_{i}\|_{2}^{2},$
(26)

where $\|\cdot\|_{2}$ denotes the L2 norm. Then, we predict the edges in the
training edge set $\bar{\mathcal{E}}$ with binary cross entropy loss:

$\ell_{\mathcal{E}}=-\frac{1}{|\bar{\mathcal{E}}|}\sum_{\bar{e}_{ij}\in\bar{\mathcal{E}}}(\bar{e}_{ij}\log(\hat{e}_{ij})+(1-\bar{e}_{ij}\log(1-\hat{e}_{ij}))).$
(27)

Similarly, we reconstruct the timestamp with mean squared error and edge type
with cross-entropy loss:

$\ell_{\mathbf{t}}=\frac{1}{|\mathcal{E}|}\sum_{e_{ij}\in\mathcal{E}}(t_{ij}-\hat{t}_{ij})^{2},$
(28)
$\ell_{\mathbf{p}}=-\frac{1}{|\mathcal{E}|}\sum_{e_{ij}\in\mathcal{E}}\log(\hat{p}_{ij,p_{ij}}),$
(29)

We can obtain the total reconstruction loss by the weighted sum of all
reconstruction loss:

$\ell_{\rm
recon}=\omega_{\mathbf{X}}\ell_{\mathbf{X}}+\omega_{\mathcal{E}}\ell_{\mathcal{E}}+\omega_{\mathbf{t}}\ell_{\mathbf{t}}+\omega_{\mathbf{p}}\ell_{\mathbf{p}},$
(30)

where $\omega_{\mathbf{X}}$, $\omega_{\mathcal{E}}$, $\omega_{\mathbf{t}}$,
and $\omega_{\mathbf{p}}$ are the hyperparameter weights balancing the
importance between each term of reconstruction loss. Finally, we use the ELBO
loss to train Variational Encoder and Graph Generator:

$\mathcal{L}_{\text{VAE}}=\ell_{\rm recon}+\beta\ell_{\rm kl}.$ (31)

where the $\ell_{\rm kl}$ is the Kullback-Leibler (KL) divergence loss between
the latent space embedding and prior distribution (e.g., Gaussian
distribution). However, as we have an additional Latent Diffusion Model, we
loosen this regularization on the latent embedding. Consequently, we use a
small hyperparameter weight $\beta<1$ to encourage the model to minimize
reconstruction error while ensuring that the resultant embedding shape remains
within the desired shape. The training of the VAE, consisting of Variational
Encoder and Graph Generator, is presented in Algorithm 1.

Algorithm 1 GODM: Training of VAE

0: Input graph
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X},\mathbf{y},\mathbf{t},\mathbf{p})$

0: Node representation $\mathbf{Z}$, well-trained Variational Encoder $E$ and
Graph Generator $G$

1: Partition graph $\mathcal{G}$ into a set of subgraphs
$\\{\mathcal{G}_{\text{sub}}\\}$

2: for each $\mathcal{G}_{\text{sub}}$ do

3: Get $\bm{\mu}$ and log$\bm{\sigma}$ via Eq. 7

4: Reparameterization of $\mathbf{Z}$ via Eq. 8

5: Generate $\hat{\mathbf{X}}$, $\hat{\mathcal{E}}$, $\hat{\mathbf{t}}$,
$\hat{\mathbf{p}}$ via Eq. 10, 12, 14, 13

6: Calculate loss via Eq. 31

7: Update Variational Encoder and Graph Generator parameters via the Adam
optimizer

8: end for

Latent Diffusion Model. After the training of Variational Encoder and Graph
Generator, we train Latent Diffusion Model via denoising score matching.

To solve the SDE in Eq. 25, we need to obtain the score function
$\nabla_{\mathbf{Z}}\log p_{s}(\mathbf{Z})$, which is as intractable as
$p_{s}(\mathbf{Z})=p(\mathbf{Z}^{s})$. However, the conditional distribution
$p(\mathbf{Z}^{s}|\mathbf{Z}^{0})$ is tractable. From Eq. 17, we obtain its
analytical solution:

$\nabla_{\mathbf{Z}}\log
p(\mathbf{Z}^{s}|\mathbf{Z}^{0})=-\frac{\bm{\varepsilon}}{a(s)\sigma(s)}.$
(32)

Thus, we train a multi-layer perceptron (MLP) as the denoising function
denoted by $\bm{\epsilon}_{\theta}$ for denoising score matching:

$\min\mathbb{E}_{\mathbf{Z}^{0}\sim
p(\mathbf{Z}^{0})}\mathbb{E}_{\mathbf{Z}^{s}\sim
p(\mathbf{Z}^{s}|\mathbf{Z}^{0})}\|\bm{\epsilon}_{\theta}({\mathbf{Z}}^{s}_{C},s)-{\bm{\varepsilon}}\|_{2}^{2},$
(33)

where
${\mathbf{Z}}^{s}_{C}=\mathbf{Z}^{s}+\mathbf{y}\mathbf{W}^{C},\mathbf{W}^{C}\in\mathbb{R}^{1\times
d^{L}}$, encoding class label for conditional generation. The entire training
process of Latent Diffusion Model is summarized in Algorithm 2.

Algorithm 2 GODM: Training of Latent Diffusion Model

0: Node representation $\mathbf{Z}$

0: Well-trained denoising function $\bm{\epsilon}_{\theta}$

1: Sample the embedding $\mathbf{Z}^{0}$ from $p(\mathbf{Z})=p(\bm{\mu})$

2: Sample diffusion steps $s$ from $p(s)$ then get $\sigma(s)$

3: Sample noise vectors
${\bm{\varepsilon}}\sim\mathcal{N}(\bm{0},\sigma^{2}(s)\bm{I})$

4: Get perturbed data ${\mathbf{Z}}^{s}=\mathbf{Z}^{0}+{\bm{\varepsilon}}$

5: Calculate loss
$\ell(\theta)=\|\bm{\epsilon}_{\theta}({\mathbf{Z}}^{s}_{C},s)-\bm{\varepsilon}\|_{2}^{2}$

6: Update the network parameter $\theta$ via Adam optimizer

###  III-E Inference

The well-trained GODM is utilized in the inference process, augmenting real
organic data by generated data. We first sampling $\hat{\mathbf{Z}}^{{S}}$
from Gaussian distribution. Then, we iteratively denoise
$\hat{\mathbf{Z}}^{{s_{i}}}$ to obtain $\hat{\mathbf{Z}}^{{s_{i-1}}}$
conditioned on $\hat{\mathbf{y}}=\bm{1}$ via denoising function
$\bm{\epsilon}_{\theta}$. The estimated $\hat{\mathbf{Z}}^{{0}}$ is fed into
Graph Generator along with $\hat{\mathbf{y}}$ to generate synthetic graph
$\hat{\mathcal{G}}$. Finally, the augmented graph $\mathcal{G}_{\text{sub}}$,
which integrates the synthetic graph $\hat{\mathcal{G}}$ and the real organic
graph $\mathcal{G}$, is used for training the downstream outlier detector $D$.
Algorithm 3 presents the whole procedure of inference.

Algorithm 3 GODM: Inference

0: Graph generator $G$ and denoising function $\bm{\epsilon}_{\theta}$

0: Augmented graph $\mathcal{G}_{\text{aug}}$

1: Sample
$\hat{\mathbf{Z}}^{{S}}\sim\mathcal{N}(\bm{0},\sigma^{2}({S})\bm{I})$

2: for $i=\max,\cdots,1$ do

3: $\nabla_{\hat{\mathbf{Z}}^{s_{i}}}\log
p(\hat{\mathbf{Z}}^{s_{i}})=-\bm{\epsilon}_{\theta}(\hat{\mathbf{Z}}^{s_{i}}_{C},{s_{i}})/\sigma({s_{i}})$

4: get $\hat{\mathbf{Z}}^{s_{i-1}}$ via solving the SDE in Eq. 25

5: end for

6: Generate $\hat{\mathcal{G}}=G(\hat{\mathbf{Z}}^{0},\hat{\mathbf{y}})$

7: $\mathcal{G}_{\text{aug}}=\text{batch}(\mathcal{G},\hat{\mathcal{G}})$

###  III-F Complexity Analysis

In this section, we meticulously analyze and elucidate the time efficiency and
memory scalability of GODM in training and inference for both VAE (Variational
Encoder and Graph Generator) and Latent Diffusion Model, providing insights
for handling large graphs which are common in real-world applications of graph
outlier detection.

####  III-F1 Time Efficiency

In the training of VAE, the major bottleneck comes from the graph structure
generation in Graph Generator. This generation originally requires link
prediction for every pair of nodes in the graphs, which is $O(n^{2})$. By
graph clustering, we divide the large graph into relatively small partitions
for minibatch training. We denote the average partition size (i.e., batch
size) by $b$, so the number of partitions is $\frac{n}{b}$. Then, the
complexity is reduced to $O(\frac{n}{b}b^{2})=O(nb)$, as only node pairs
within each partition are predicted. We apply the negative sampling to further
reduce the complexity to $O(|\mathcal{E}|)$, as we only sample a negative edge
for each positive edge. For Latent Diffusion Model, we only sample a fixed
number of diffusion steps to train the denoising function. As a result,
assuming the number of latent dimensions is a constant, the complexity is
$O(n)$. Thus, the total training complexity is $O(n+|\mathcal{E}|)$. For the
inference, we first take $S$ steps sampling in Latent Diffusion Model, which
is $O(nS)$, and predict edges between node pairs in each partition, which is
$O(nb)$. Therefore, the total inference complexity is $O(nS+nb)$.

####  III-F2 Memory Scalability

The vanilla VAE requires memory consumption of $O(n^{2})$, which is infeasible
for large graphs. To reduce memory consumption, we adopt minibatch training on
graph partitions and negative sampling for link prediction. The complexity of
VAE training can be obtained by the number of edges divided by the number of
partitions $O(|\mathcal{E}|/\frac{n}{b})=O(\frac{|\mathcal{E}|b}{n})$. Latent
Diffusion Model only requires a memory of $O(b)$. In the inference process,
the VAE performs link prediction for all node pairs in a batch, leading to a
memory complexity of $O(b^{2})$, and Latent Diffusion Model only demands
$O(b)$ for each batch. Therefore, the total inference process needs $O(b^{2})$
of memory.

##  IV Experiments

In this section, we systematically delineate the experiments to evaluate GODM.
We first introduce experimental setups in Section IV-A. Then, we aim to
answer: RQ1 (Section IV-B): How effective is GODM on improving graph outlier
detection performance? RQ2 (Section IV-C): How is the quality of the synthetic
data generated by GODM? RQ3 (Section IV-D): How efficient is GODM in terms of
time and memory? The code implementation of our experiments is publicly
available at https://github.com/kayzliu/godm.

###  IV-A Experimental Setups

To benchmark GODM and contemporary graph outlier detection algorithms from
various aspects, we conduct experiments in a unified and comprehensive
environment, which is in part adapted from GADBench [6].

####  IV-A1 Datasets

TABLE I: Statistics of datasets
(*: with multiple edge types and temporal infomation).

Dataset | #Nodes | #Edges | #Feat. | Outlier
---|---|---|---|---
Weibo | 8,405 | 407,963 | 400 | 10.3%
Tolokers | 11,758 | 519,000 | 10 | 21.8%
Questions | 48,921 | 153,540 | 301 | 3.0%
Elliptic | 203,769 | 234,355 | 166 | 9.8%
DGraph∗ | 3,700,550 | 4,300,999 | 17 | 1.3%

We use five diverse datasets from GADBench. Weibo, Elliptic, Tolokers, and
Questions are homogeneous static graphs with only one type of edge. DGraph is
a heterogeneous temporal graph with different types of edges. The graphs vary
in scale, ranging from thousands of nodes to millions of nodes. Table I
provides the statistics of the datasets. In the table, #Nodes stands for the
number of nodes, and #Edges stands for the number of edges. #Feat. denotes the
raw feature dimension, i.e., the number of node attributes. The Outlier column
represents the outlier ratio in the label, indicating the extent of class
imbalance. The detailed descriptions for each dataset are as follows:

Weibo [27]: This dataset involves a graph delineating the associations between
users and their corresponding hashtags from the Tecent-Weibo platform,
consisting of 8,405 users and a collection of 61,964 hashtags. Activities
within this dataset are regarded as suspicious (i.e., outliers) if they
consist of a pair of posts occurring within narrowly defined temporal
intervals (e.g., 60 seconds). Users engaging in at least five incidents of
such behavior are classified under the suspicious category, in contrast to the
remainder designated as benign. Following this classification criterion, the
dataset contains 868 users identified as suspicious and 7,537 as benign. The
primary feature vector includes geolocation data for each micro-blog entry and
a representation utilizing the bag-of-words model.

Tolokers [28]: The dataset is obtained from the Toloka crowdsourcing platform.
It is composed of nodes corresponding to individual workers who have engaged
in at least one out of thirteen specified projects. Edges are established
between pairs of workers who have concurrently contributed to an identical
task. The primary objective is to predict the likelihood of a worker having
received a ban in any one of the projects. The features attributed to each
node are constructed utilizing the worker’s personal profile information in
conjunction with their task-related performance metrics.

Questions [28]: The dataset is derived from Yandex Q, a question-answering
platform. The nodes represent individual users. An edge is established between
two nodes to denote the scenario wherein one user has responded to another’s
inquiry within the temporal bounds of one year, stretching from September 2021
to August 2022. This dataset is specifically curated to encapsulate the
engagement of users who exhibit interest in the medical topic. The target for
this dataset is to predict the likelihood of users’ continued activity on the
platform by the conclusion of the observed period. The average FastText
embeddings of the lexical content present in the users’ descriptions are used
for node features.

Elliptic [10]: The dataset comprises a graph of 203,769 nodes representing
Bitcoin transactions, connected through 234,355 edges representing payment
flows, along with 166 distinctive node attributes. It correlates Bitcoin
transactional data with corresponding real-world entities that are categorized
as lawful, including exchanges, wallet services, mining operations, and
legitimate services, as well as unlawful categories, including scams,
malicious software, terrorist-related organizations, ransomware operations,
and fraudulent investment activities known as Ponzi schemes.

DGraph [7]: The DGraph dataset is a large-scale graph with different edge
types and temporal information supplied by Finvolution Group. It includes 3
million nodes, 4 million dynamic edges, and 1 million labeled nodes. The nodes
represent user accounts within a financial organization offering personal loan
services, while an edge between two nodes indicates that one account has
designated the other as an emergency contact. Nodes classified as fraud
correspond to users displaying delinquent financial conduct. For those
accounts with borrowing records, outliers are identified as accounts with a
history of overdue payments, while inliers are those without such a history.
Additionally, the dataset includes 17 node features derived from user profile
information.

####  IV-A2 Baselines

In our experiments, we evaluate GODM against different types of baseline
methods. We have three types of baseline methods, including general graph
neural networks, graph outlier detectors, and data augmentation for graph
outlier detection. For general graph neural networks, we follow GADBench and
select six GNNs:

GCN (Graph Convolutional Networks) [1]: GCN is the seminal work that applies
convolution operation on graph data. It propagates the information of a node
to its neighbors, thus enabling the network to develop a representation for
each node that reflects its local neighborhood context.

SGC (Simplified Graph Convolution) [29]: This variant of GCN leverages
Chebyshev polynomials to approximate the spectral graph convolution operator.
This strategy allows the model to encompass both local and global graph
structures, enhancing its scalability for handling larger graphs.

GIN (Graph Isomorphism Network) [30]: GIN is a form of GNN that effectively
captures graph structures while maintaining graph isomorphism. It achieves
this by generating consistent embeddings for structurally identical graphs,
which is permutation invariant.

GraphSAGE (Graph Sample and Aggregate) [17]: GraphSAGE presents a general
inductive learning approach where node embeddings are generated through the
sampling and aggregation of features from a node’s immediate neighborhood.

GAT (Graph Attention Networks) [31]: GAT incorporates the attention mechanism
within the GNN framework. It dynamically assigns varying importance to
different nodes during the information aggregation process, focusing the
model’s learning on the most relevant parts of the neighborhood.

GT (Graph Transformer) [32]: Drawing inspiration from the Transformer model in
neural networks, GT adapts these principles for graph-structured data. It
utilizes masks in the self-attention mechanism to capitalize on the inherent
structure of graphs, thus boosting the model’s efficiency.

In addition to general GNNs, we also include eight GNNs specifically designed
for graph outlier detection:

GAS (GCN-based Anti-Spam) [33]: GAS is an attention-based spam review
detector, extending the capabilities of GCN to process heterogeneous and
heterophilic graphs. It employs the KNN algorithm to align with the structure
of each graph.

DCI (Deep Cluster Infomax) [34]: DCI is a self-supervised learning strategy
that separates the learning of node representations from outlier detection. It
addresses discrepancies between node behavioral patterns and their label
semantics by clustering the entire graph, thus capturing intrinsic graph
properties in focused feature spaces.

PCGNN (Pick and Choose Graph Neural Network) [35]: Tailored for imbalanced GNN
learning in fraud detection scenarios, PCGNN uses a label-balanced sampler for
node and edge selection during training. This results in a more balanced label
distribution within the induced subgraph.

BernNet [36]: BernNet is a GNN variant offering a robust approach to designing
and learning arbitrary graph spectral filters. It utilizes an order-K
Bernstein polynomial approximation for estimating filters over the normalized
Laplacian spectrum, catering to a variety of graph structures.

GATSep [37]: Designed to optimize learning on heterophily graphs, GAT-sep
merges key design elements like ego- and neighbor-embedding separation,
higher-order neighborhood processing, and combinations of intermediate
representations.

AMNet (Adaptive Multi-frequency GNN) [38]: AMNet is structured to capture
signals across both low and high frequencies by stacking multiple BernNets and
adaptively integrating signals from different frequency bands.

BWGNN (Beta Wavelet Graph Neural Network) [39]: BWGNN addresses the ”right-
shift” phenomenon on outliers. It uses the Beta kernel to address higher
frequency anomalies through spatially/spectrally localized band-pass filters.

GHRN (Graph Heterophily Reduction Network) [40]: GHRN tackles the issue of
heterophily in the spectral domain for graph outlier detection. This approach
focuses on pruning inter-class edges to enhance the representation of high-
frequency components in the graph spectrum.

For heterogeneous graphs, despite the rich literature, limited heterogeneous
GNNs can cope with temporal information. As one of the representatives, we
chose HGT for our baseline:

HGT (Heterogeneous Graph Transformer) [21]: HGT is engineered to address the
challenges of modeling heterogeneous graphs. It introduces node- and edge-type
dependent parameters that are crucial for defining heterogeneous attention
mechanisms for each edge.

Because the data augmentation for graph outlier detection is a relatively new
research topic, there are limited baselines. We include one baseline for
homogeneous graphs and introduce a variant of GODM that can work on both
homogeneous and heterogeneous datasets, GOVAE:

DAGAD (Data Augmentation for Graph Anomaly Detection) [41]: DAGAD incorporates
three modules to augment the graph data, including an information fusion
module for representation learning, a data augmentation module to enrich the
training set with synthetic samples, and an imbalance-tailored learning module
to distinguish between minority anomalous class and majority normal class.

GOVAE: In this variant, we drop Latent Diffusion Model and form a variational
autoencoder with Variational Encoder and Graph Generator. The inference is a
direct one-step estimation from prior Gaussian distribution.

Along with GODM, we compare these three data augmentation methods for graph
outlier detection in Table II, where the flexibility represents whether the
data augmentation is model agnostic. Heterogeneous and time indicate whether
the method supports these two types of information. The diffusion column
indicates whether the method adopts diffusion models.

TABLE II: Comparison of data augmentation for graph outlier detection.

| Flexibility | Heterogeneous | Time | Diffusion
---|---|---|---|---
DAGAD |  ✗ |  ✗ |  ✗ |  ✗
GOVAE | ✓ | ✓ | ✓ |  ✗
GODM | ✓ | ✓ | ✓ | ✓

####  IV-A3 Metrics

We follow the extensive literature in graph outlier detection [5, 6] to
comprehensively evaluate the performance of graph outlier detectors with three
metrics that are robust to class imbalance: Receiver Operating Characteristic-
Area Under Curve (AUC), Average Precision (AP), and Recall@k (Rec), where the
value of k is set to the number of actual outliers present in the dataset.

####  IV-A4 Implementation Details

We modified GADBench to benchmark outlier detection performance.

Environment. The key libraries and their versions used in our experiments are
as follows: Python 3.9, CUDA 11.8, PyTorch 2.0.1 [42], PyTorch Geometric 2.4.0
[43], DGL 1.1.2 [44], and PyGOD 1.0.0 [4].

TABLE III: Performance comparison in AUC, AP, and Rec (%) on four datasets.

Dataset | Weibo |  | Tolokers |  | Questions |  | Elliptic
---|---|---|---|---|---|---|---
Metric | AUC | AP | Rec |  | AUC | AP | Rec |  | AUC | AP | Rec |  | AUC | AP | Rec
GCN | 98.11 | 93.48 | 89.34 |  | 74.69 | 42.88 | 42.06 |  | 69.81 | 12.54 | 16.99 |  | 82.68 | 22.23 | 27.61
SGC | 98.66 | 92.46 | 87.90 |  | 70.67 | 38.03 | 35.98 |  | 69.88 | 10.13 | 15.62 |  | 73.02 | 11.44 | 9.14
GIN | 97.47 | 92.67 | 87.90 |  | 74.05 | 36.57 | 36.76 |  | 67.76 | 12.30 | 18.36 |  | 84.38 | 29.66 | 35.64
GraphSAGE | 96.54 | 89.25 | 86.17 |  | 79.42 | 48.65 | 46.42 |  | 71.69 | 17.63 | 21.10 |  | 85.31 | 37.52 | 36.20
GAT | 94.08 | 90.25 | 86.74 |  | 77.26 | 43.14 | 43.30 |  | 70.33 | 14.51 | 17.26 |  | 84.42 | 23.43 | 27.42
GT | 97.06 | 91.44 | 87.03 |  | 79.24 | 46.22 | 46.57 |  | 70.83 | 16.14 | 20.27 |  | 87.14 | 29.91 | 38.97
GAS | 94.88 | 90.70 | 86.74 |  | 76.91 | 47.35 | 45.02 |  | 64.50 | 13.61 | 17.53 |  |  87.81 | 40.03 |  44.78
DCI | 93.90 | 87.78 | 83.86 |  | 75.98 | 39.85 | 40.19 |  | 67.95 | 14.58 | 19.18 |  | 81.93 | 27.63 | 33.15
PCGNN | 90.89 | 84.57 | 79.83 |  | 72.18 | 37.52 | 36.76 |  | 68.38 | 14.79 | 16.99 |  | 86.50 |  42.66 | 43.77
GATSep | 96.72 | 91.55 | 89.05 |  | 79.63 | 46.08 | 46.73 |  | 69.96 | 15.98 | 19.18 |  | 83.89 | 21.46 | 21.15
BernNet | 93.85 | 88.00 | 85.30 |  | 76.20 | 42.20 | 42.21 |  | 70.80 | 16.04 | 17.53 |  | 82.01 | 20.52 | 23.55
AMNet | 95.88 | 89.74 | 85.59 |  | 75.83 | 42.66 | 41.90 |  | 69.71 | 17.02 | 19.18 |  | 80.06 | 16.73 | 17.17
BWGNN | 98.29 | 92.72 | 84.73 |  | 80.15 | 49.65 | 47.35 |  | 69.47 | 16.24 | 18.63 |  | 84.32 | 22.56 | 26.50
GHRN | 97.21 | 92.67 | 88.18 |  | 79.80 | 49.50 | 48.29 |  | 68.24 | 16.24 | 18.63 |  | 85.36 | 24.01 | 30.29
DAGAD | 98.54 | 83.36 | 90.78 |  | 77.69 | 33.94 | 44.39 |  | 71.21 | 6.88 | 20.55 |  | 85.62 | 26.18 | 40.54
GOVAE |  99.46 |  96.84 | 93.08 |  |  83.42 | 53.85 |  52.49 |  |  75.73 |  19.13 |  23.84 |  | 83.93 | 36.66 | 42.66
GODM | 99.57 | 97.54 | 93.08 |  | 83.46 |  52.95 | 52.96 |  | 76.84 | 20.48 | 24.66 |  | 89.77 | 43.92 | 53.92

Hardware. All of our experiments were performed on a Linux server with an AMD
EPYC 7763 64-core CPU, 192GB RAM, and an NVIDIA RTX A40 GPU with 48GB memory.

Hyperparameters. GODM is implemented with default hyperparameters. For
Variational Encoder, we use one layer GraphSAGE for
$\text{GNN}_{\text{shared}}$, $\text{GNN}_{\bm{\mu}}$, and
$\text{GNN}_{\bm{\sigma}}$, respectively. We set the hidden dimension to the
largest power of 2, which is no greater than the feature dimension of the
dataset divided by 2. The weights of reconstruction loss
$\omega_{\mathbf{X}}$, $\omega_{\mathcal{E}}$, $\omega_{\mathbf{t}}$, and
$\omega_{\mathbf{p}}$ are 1, 0.5, 1, and 0.3, respectively. The weight for KL-
divergence $\beta$ is 0.001. For the diffusion model, we use the dimension
twice as the hidden dimension in VAE. We use five layers of MLP as the
denoising function following the detailed design in [22]. For training, we
adopt the Adam optimizer with a learning rate of 0.001 without weight decay to
train the VAE and the diffusion model for 100 epochs, respectively, and apply
early stopping with a patience of 50. The negative sampling ratio is 1, and
the approximate graph partition size is 2048. For inference, we use 50 steps
of diffusion and generate the same amount of synthetic outliers as the number
of real organic outliers in the training set. For all the hyperparameters in
graph outlier detection, we apply the default setting in GADBench. We report
the graph outlier detection performance of GODM with the optimal downstream
graph outlier detector.

Open-Source Package. To enhance accessibility, we encapsulate our data
augmentation into user-friendly API and make our code a plug-and-play package.
This package is built upon PyTorch and PyTorch Geometric (PyG) frameworks. It
accepts a PyG data object as input and returns the augmented graph as output.
By inheriting the transforms.BaseTransform in PyG, we enable users to apply
GODM just like any other transformations supported in PyG, e.g., ToUndirected.
We are also able to customize hyperparameters during initialization. Code Demo
1 gives a brief example of API usage.

⬇

1from pygod.utils import load_data

2data = load_data(’weibo’) # load data

3

4from godm import GODM # import GODM

5godm = GODM(lr=0.004) # init. GODM

6aug_data = godm(data) # augment data

7

8detector(aug_data) # train on data

Code Demo 1: Using GODM on Weibo dataset [27].

For distribution, we release our package on the Python Package Index (PyPI).
Users can easily install GODM by executing pip install godm in a command line.

###  IV-B Performamce on Graph Outlier Detection

TABLE IV: GODM’s performance improvements on graph outlier detection
algorithms in AUC, AP, and Recall (%) on Tolokers.

| AUC | AP | Rec
---|---|---|---
GCN | 75.45 (+0.76) | 44.17 (+1.29) | 44.24 (+2.18)
SGC | 72.73 (+2.06) | 39.75 (+1.72) | 38.01 (+2.02)
GIN | 74.83 (+0.78) | 38.54 (+1.96) | 38.32 (+1.56)
GraphSAGE | 81.65 (+2.23) | 52.53 (+3.87) | 50.93 (+4.52)
GAT | 82.18 (+4.91) | 51.13 (+7.99) | 50.78 (+7.48)
GT | 82.73 (+3.49) | 51.73 (+5.51) | 50.93 (+4.36)
GAS | 76.96 (+0.05) | 45.48 (-1.87) | 43.15 (-1.87)
DCI | 73.75 (-2.23) | 37.52 (-2.33) | 37.54 (-2.65)
PCGNN | 73.65 (+1.47) | 38.42 (+0.90) | 38.01 (+1.25)
GATSep | 83.46 (+3.83) | 52.95 (+6.87) | 52.80 (+6.07)
BernNet | 76.53 (+0.33) | 44.04 (+1.83) | 42.21 (+0.00)
AMNet | 76.67 (+0.84) | 44.31 (+1.65) | 43.30 (+1.40)
BWGNN | 82.10 (+1.95) | 51.94 (+2.29) | 51.25 (+3.89)
GHRN | 82.05 (+2.25) | 51.84 (+2.34) | 51.56 (+3.27)

We start by examining how effective GODM is in the task of graph outlier
detection on homogeneous graphs. We report graph outlier detection performance
on four homogeneous datasets in terms of AUC, AP, and Rec of different
algorithms in Table III. In the table, the highest score in each metric is
marked in bold, while the second highest score is underlined. For DAGAD, we
report the optimal performance of its two implementations with GCN and GAT.
Although DAGAD shows superior performance compared to the standalone GCN and
GAT, it fails to surpass more sophisticated detectors. On the other hand, GODM
and GOVAE together demonstrate significant enhancements in graph outlier
detection performance across all datasets and metrics. Notably, on the Weibo
dataset, where the performance metric is already relatively high (AUC of 98.66
for SGC), GODM further elevates the performance, achieving an AUC of 99.57. A
particularly noteworthy improvement is observed on Elliptic, where GODM
enhances the Rec by over 20% (an increase of 9.14) compared to GAS, which is
the second-best performing algorithm. Although GOVAE exhibits competitive
performance, its limited generation ability results in generally weaker
performance compared to GODM, especially on Elliptic.

Further investigations were carried out to understand the extent of
improvement GODM could bring to various graph outlier detection algorithms,
specifically on Tolokers. We integrate GODM on the top of all graph outlier
detection algorithms and report the performance changes in terms of AUC, AP,
and Rec in Table IV. The absolute performance is reported out of brackets, and
the relative change is reported in the brackets. We can observe that GODM
enhances graph outlier detection performance for most of the algorithms. GODM
increases the AP of GAT by 7.99. For DCI and GAS, the only two algorithms that
minorly decrease the performance, this could be attributed to suboptimal
hyperparameter settings for these specific algorithms or the dataset. We
believe the performance can be improved by careful hyperparameter tuning.

TABLE V: Performance comparison in AUC, AP, and Rec (%) on DGraph.

| AUC | AP | Rec
---|---|---|---
HGT | 72.89 | 3.13 | 5.20
w/o Feature | 75.10 | 3.64 | 5.59
w/o Edge | 74.36 | 3.52 | 5.76
w/o Time | 74.23 | 3.29 | 4.73
w/o Type | 75.09 | 3.62 | 5.98
GOVAE | 75.36 | 3.58 | 5.54
GODM | 75.80 | 3.66 | 6.19

Moreover, in Table V, we benchmark the graph outlier detector performance on
DGraph, a large-scale dataset with different types of edges and temporal
information. We include HGT along with variants of GODM. For the w/o Feature,
we randomly sample the node feature from the Gaussian distribution to replace
the generated node feature in the synthetic graph. For the w/o Edge, all
generated edges are substituted with random edges. For w/o Time, we give
uniformly sampled timestamps to replace the generated timestamps. For the w/o
Type, we use a random type sampled from a uniform distribution for all
generated edges. According to Table V, GODM demonstrates enhanced performance
across all metrics when compared to HGT. Furthermore, masking any generated
information leads to a notable decline in performance, which underscores the
significance of each aspect of the generated data. While GOVAE achieves
commendable results, its performance still falls short of GODM’s, highlighting
the superior efficacy of Latent Diffusion Model.

###  IV-C Generation Quality

To assess the quality of generated data, we conduct a case study on DGraph to
compare real data and synthetic data from both GOVAE and GODM. The results are
shown in Fig. 3. Specifically, Fig. 3 (a) and (b) illustrate the distribution
density of a single dimension in node features. From the figures, we can see
that the distributions of GODM generated node features are close to the
complex distributions of real data, while GOVAE can only generate Gaussian
distributions, showcasing the generation ability of Latent Diffusion Model. In
addition, to evaluate generated edges, Fig. 3 (c) shows the frequency across
eleven different edge types. The edge type generated by GODM has a more
similar distribution to real data compared to GOVAE, particularly on the 10th
edge type. It further underscores the superiority of GODM over GOVAE.

Figure 3: Visualization of single node feature density and edge type frequency
of real data and synthetic data from GOVAE and GODM on DGraph.

###  IV-D Efficiency Study

We further evaluate the efficiency of GODM and its variants in terms of time
and memory on graphs of various sizes, including Weibo, Elliptic, and DGraph.
In order to demonstrate the efficiency of GODM, we remove graph clustering
(w/o GC), negative sampling (w/o NS), and EDM (w/o EDM) for evaluation. To
simulate the real-world application, we measure the running time of unit epoch
training for VAE and Latent Diffusion Model plus the inference process. For
memory, we present the maximum active GPU memory usage within the whole data
augmentation, as the GPU memory constraint is usually the bottleneck for
machine learning systems. The results are shown in Fig. 4.

Figure 4: Running time and GPU memory of GODM and its variants.

From Fig. 4, we can observe that employing a graph clustering algorithm
significantly diminishes GPU memory utilization. Specifically, on DGraph, w/o
GC results in a memory usage that is over 30$\times$ higher than GODM. On the
other hand, graph clustering turns full-batch training into mini-batch
training, leading to an anticipated increase in running time. Additionally,
negative sampling reduces both the running time and the memory usage, as the
number of edges in the training set reduces from $O(n^{2})$ to
$O(|\mathcal{E}|)$. While EDM maintains consistent memory consumption, it
contributes to time savings by minimizing the number of sampling steps.

##  V Related Works

This section briefly summarizes the previous related works in three key areas,
including graph outlier detection, class imbalance, and graph generative
models.

###  V-A Graph Outlier Detection

Graph outlier detection is a vital task in data mining and machine learning,
aiming to identify anomalous structures (e.g., nodes, edges, subgraphs) in
graphs. Due to its structural simplicity and broader applications, most
research focuses on node-level graph outlier detection and can easily convert
to edge level and graph level task [4]. Many studies focus on unsupervised
settings, detecting outliers in the graph only based on the graph data itself
without any ground truth labels [45, 46, 47]. However, such unsupervised
approaches may not align well with scenarios necessitating the detection of
specific outlier types containing domain-specific knowledge. In this case,
(semi-)supervised graph outlier detectors, which can learn ground truth
labels, are better options. [33] apply attention mechanism to detect spam
review. [11, 48] alleviate the camouflage issue in fraud detection by message
passing in selected neighborhoods. [35] further improves the neighbor
selection in fraud detection. [49] builds the outlier detection graph via the
KNN algorithm. [34] decouples the representation learning and anomaly
detection, and [50] focuses on heterophily in graph outlier detection. Some
other works detect outliers from a spectral perspective. [36] learns arbitrary
graph spectral filters via Bernstein approximation, and [38] is capable of
discerning both low-frequency and high-frequency signals, thereby adaptively
integrating signals across a spectrum of frequencies. In [39], the Beta kernel
is employed to detect anomalies at higher frequencies using flexible and
localized band-pass filters. [40] addresses heterophily in graph outlier
detection from a graph spectrum perspective.

###  V-B Class Imbalance

Despite the fruitful literature on graph outlier detection, most of methods
underrate a pivotal challenge: the class imbalance in ground truth labels.
These methods typically mitigate this imbalance by primitive techniques.
GADBench uses reweighting [6], assigning a higher weight to outliers in the
loss function. Some works adopt upsampling to replicate outliers, which is
mathematically equivalent to reweighting. [11] applies downsampling, reducing
the number of normal instances and losing a large amount of valuable
supervision information from normal instances. However, these tricks may not
sufficiently address the underlying complexities associated with imbalanced
datasets. Consequently, there is a compelling need for more sophisticated
techniques that can effectively address this class imbalance to ensure the
quality of graph outlier detection. [35] balances the neighborhood
distribution by reducing edges between different classes and adding edges
between the same classes but does not change the overall number of positive
and negative nodes. [41] adopts random perturbation for data augmentation to
generate more samples. Other general graph machine learning studies apply
interpolation-based data augmentation methods in latent space [51]. However,
these methods are not specifically designed for graph outlier detection, and
interpolation is too naive to generate helpful instances. This paper seeks to
build upon these foundational works, proposing a novel graph data augmentation
algorithm with latent diffusion models that not only mitigate class imbalance
effectively but are also scalable and efficient on large graphs, ensuring
broader applicability in real-world graph outlier detection.

###  V-C Graph Generative Models

Recent advances in graph generative models have catalyzed a significant body
of research, focusing primarily on the synthesis of realistic and structurally
coherent graphs. [52] proposes VGAE, leveraging variational autoencoder
frameworks to learn latent representations of graph structures for generation
purposes. [53] introduces GraphRNN, generating nodes and edges
autoregressively with two recurrent neural networks. [54] applies a generative
adversarial networks framework to generate graphs via random walks. [55]
introduces the normalizing flow method for molecular graph generation. With
the recent proliferation of works in image generation with diffusion models,
some efforts have extended the generation power of diffusion models to graph-
structured data. [13] proposes a score-based generative modeling of graphs via
the system of stochastic differential equations, while [14] uses a discrete
diffusion model to generate graphs. However, the potential of graph generative
models to address the class imbalance in graph outlier detection remains
largely underexplored. We propose to generate some synthetic outliers to
mitigate this class imbalance in graph outlier detection.

##  VI Conclusion

In this paper, we introduce GODM, a novel method for data augmentation in
supervised graph outlier detection. GODM is designed to address the
significant challenge of class imbalance, a pervasive issue in graph outlier
detection, where the scarcity of outlier instances compared to normal
instances often leads to suboptimal model performance. Our method leverages
the power of generative models, particularly latent diffusion models, to
synthesize fidelity graph data that is statistically similar to real outliers.
GODM consists of three key components: Variational Encoder, Latent Diffusion
Model, and Graph Generator. Variational Encoder maps heterogeneous information
in the input graph into a unified latent space. Latent Diffusion Model learns
the latent space distribution of real organic data through iterative
denoising. Graph Generator then synthesizes graph data from this latent space
embedding, ensuring statistical similarity to real data. Our extensive
experiments across multiple datasets demonstrate the effectiveness and
efficiency of GODM. Note that GODM is model agnostic, which means it can be
flexibly integrated with different downstream graph outlier detectors. We
encapsulate GODM into a plug-and-play package, making it accessible for
broader use in the researcher and practitioner communities.

In future research, several directions can be explored to enhance GODM further
and expand its applicability in the domain of graph outlier detection:

  * •

Diffusion in graph sapce. Considering the heterogeneity and scalability of the
graphs for outlier detection applications, GODM currently employs a diffusion
model in latent space. [56] starts to generate large graphs directly in graph
space. Future research could explore the application of diffusion models on
heterogeneous information directly in graph space, potentially enhancing the
model’s ability to capture complex graph structures.

  * •

Collaboration with outlier detection. Currently, GODM is model agnostic,
meaning the training of GODM and downstream outlier detection tasks are
separate. Integrating the supervision signals from both the generation task
and the downstream outlier detection in a unified training framework could be
mutually beneficial. Self-training offers a promising paradigm for this
integration [57].

  * •

Enhancing generative models. Although the current diffusion model in GODM has
shown impressive capabilities, there is potential for further improvement.
This could be achieved by employing more expressive denoising functions, such
as transformers [58], or by exploring alternative generative models like
energy-based models [59] and or normalizing flows [60], which might offer
different advantages over diffusion models.

## Acknowledgment

This work is supported by NSF under grant III-2106758. We sincerely appreciate
reviewers in advance for their significant effort and invaluable feedback
during the review process.

## References

  * [1] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in _International Conference on Learning Representations_ , 2016.
  * [2] L. Yang, Z. Liu, Y. Dou, J. Ma, and P. S. Yu, “Consisrec: Enhancing gnn for social recommendation via consistent neighbor aggregation,” in _Proceedings of the 44th international ACM SIGIR conference on Research and development in information retrieval_ , 2021, pp. 2141–2145.
  * [3] S. Ji, S. Pan, E. Cambria, P. Marttinen, and S. Y. Philip, “A survey on knowledge graphs: Representation, acquisition, and applications,” _IEEE transactions on neural networks and learning systems_ , vol. 33, no. 2, pp. 494–514, 2021.
  * [4] K. Liu, Y. Dou, Y. Zhao, X. Ding, X. Hu, R. Zhang, K. Ding, C. Chen, H. Peng, K. Shu _et al._ , “Pygod: A python library for graph outlier detection,” _arXiv preprint arXiv:2204.12095_ , 2022.
  * [5] K. Liu, Y. Dou, Y. Zhao, X. Ding, X. Hu, R. Zhang, K. Ding, C. Chen, H. Peng _et al._ , “Bond: Benchmarking unsupervised outlier node detection on static attributed graphs,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 27 021–27 035, 2022.
  * [6] J. Tang, F. Hua, Z. Gao, P. Zhao, and J. Li, “Gadbench: Revisiting and benchmarking supervised graph anomaly detection,” _arXiv preprint arXiv:2306.12251_ , 2023.
  * [7] X. Huang, Y. Yang, Y. Wang, C. Wang, Z. Zhang, J. Xu, L. Chen, and M. Vazirgiannis, “Dgraph: A large-scale financial dataset for graph anomaly detection,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 22 765–22 777, 2022.
  * [8] Y. Dou, K. Shu, C. Xia, P. S. Yu, and L. Sun, “User preference-aware fake news detection,” in _Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , 2021, pp. 2051–2055.
  * [9] Y. Dou, G. Ma, P. S. Yu, and S. Xie, “Robust spammer detection by nash reinforcement learning,” in _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2020, pp. 924–933.
  * [10] M. Weber, G. Domeniconi, J. Chen, D. K. I. Weidele, C. Bellei, T. Robinson, and C. Leiserson, “Anti-money laundering in bitcoin: Experimenting with graph convolutional networks for financial forensics,” in _ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , 2019.
  * [11] Y. Dou, Z. Liu, L. Sun, Y. Deng, H. Peng, and P. S. Yu, “Enhancing graph neural network-based fraud detectors against camouflaged fraudsters,” in _Proceedings of the 29th ACM international conference on information & knowledge management_, 2020, pp. 315–324.
  * [12] R. Rombach, A. Blattmann, D. Lorenz, P. Esser, and B. Ommer, “High-resolution image synthesis with latent diffusion models,” in _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2022, pp. 10 684–10 695.
  * [13] J. Jo, S. Lee, and S. J. Hwang, “Score-based generative modeling of graphs via the system of stochastic differential equations,” in _International Conference on Machine Learning_. PMLR, 2022, pp. 10 362–10 383.
  * [14] C. Vignac, I. Krawczuk, A. Siraudin, B. Wang, V. Cevher, and P. Frossard, “Digress: Discrete denoising diffusion for graph generation,” in _The Eleventh International Conference on Learning Representations_ , 2022.
  * [15] T. Karras, M. Aittala, T. Aila, and S. Laine, “Elucidating the design space of diffusion-based generative models,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 26 565–26 577, 2022.
  * [16] J. Ho, A. Jain, and P. Abbeel, “Denoising diffusion probabilistic models,” _Advances in neural information processing systems_ , vol. 33, pp. 6840–6851, 2020.
  * [17] W. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [18] C. Shi, Y. Li, J. Zhang, Y. Sun, and S. Y. Philip, “A survey of heterogeneous information network analysis,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 29, no. 1, pp. 17–37, 2016.
  * [19] J. Zhao, X. Wang, C. Shi, Z. Liu, and Y. Ye, “Network schema preserving heterogeneous information network embedding,” in _International joint conference on artificial intelligence (IJCAI)_ , 2020.
  * [20] L. Deng, D. Lian, Z. Huang, and E. Chen, “Graph convolutional adversarial networks for spatiotemporal anomaly detection,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 33, no. 6, pp. 2416–2428, 2022.
  * [21] Z. Hu, Y. Dong, K. Wang, and Y. Sun, “Heterogeneous graph transformer,” in _Proceedings of the web conference 2020_ , 2020, pp. 2704–2710.
  * [22] H. Zhang, J. Zhang, B. Srinivasan, Z. Shen, X. Qin, C. Faloutsos, H. Rangwala, and G. Karypis, “Mixed-type tabular data synthesis with score-based diffusion in latent space,” _arXiv preprint arXiv:2310.09656_ , 2023.
  * [23] Y. Song, J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole, “Score-based generative modeling through stochastic differential equations,” in _International Conference on Learning Representations_ , 2020.
  * [24] N. De Cao and T. Kipf, “Molgan: An implicit generative model for small molecular graphs,” _arXiv preprint arXiv:1805.11973_ , 2018.
  * [25] W.-L. Chiang, X. Liu, S. Si, Y. Li, S. Bengio, and C.-J. Hsieh, “Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks,” in _Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining_, 2019, pp. 257–266.
  * [26] G. Karypis and V. Kumar, “Metis: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices,” _http://glaros. dtc. umn. edu/gkhome/metis/metis/download_ , 1997.
  * [27] T. Zhao, C. Deng, K. Yu, T. Jiang, D. Wang, and M. Jiang, “Error-bounded graph anomaly loss for gnns,” in _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, 2020, pp. 1873–1882.
  * [28] O. Platonov, D. Kuznedelev, M. Diskin, A. Babenko, and L. Prokhorenkova, “A critical look at the evaluation of gnns under heterophily: Are we really making progress?” in _The Eleventh International Conference on Learning Representations_ , 2022.
  * [29] F. Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger, “Simplifying graph convolutional networks,” in _International conference on machine learning_. PMLR, 2019, pp. 6861–6871.
  * [30] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural networks?” in _International Conference on Learning Representations_ , 2018.
  * [31] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph attention networks,” in _International Conference on Learning Representations_ , 2018.
  * [32] Y. Shi, H. Zhengjie, S. Feng, H. Zhong, W. Wang, and Y. Sun, “Masked label prediction: Unified message passing model for semi-supervised classification,” in _International joint conference on artificial intelligence (IJCAI)_ , 08 2021, pp. 1548–1554.
  * [33] A. Li, Z. Qin, R. Liu, Y. Yang, and D. Li, “Spam review detection with graph convolutional networks,” in _Proceedings of the 28th ACM International Conference on Information and Knowledge Management_ , 2019, pp. 2703–2711.
  * [34] Y. Wang, J. Zhang, S. Guo, H. Yin, C. Li, and H. Chen, “Decoupling representation learning and classification for gnn-based anomaly detection,” in _Proceedings of the 44th international ACM SIGIR conference on research and development in information retrieval_ , 2021, pp. 1239–1248.
  * [35] Y. Liu, X. Ao, Z. Qin, J. Chi, J. Feng, H. Yang, and Q. He, “Pick and choose: a gnn-based imbalanced learning approach for fraud detection,” in _Proceedings of the web conference 2021_ , 2021, pp. 3168–3177.
  * [36] M. He, Z. Wei, H. Xu _et al._ , “Bernnet: Learning arbitrary graph spectral filters via bernstein approximation,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 14 239–14 251, 2021.
  * [37] A. Zimek, R. J. Campello, and J. Sander, “Ensembles for unsupervised outlier detection: challenges and research questions a position paper,” _Acm Sigkdd Explorations Newsletter_ , vol. 15, no. 1, pp. 11–22, 2014.
  * [38] Z. Chai, S. You, Y. Yang, S. Pu, J. Xu, H. Cai, and W. Jiang, “Can abnormality be detected by graph neural networks,” in _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI), Vienna, Austria_ , 2022, pp. 23–29.
  * [39] J. Tang, J. Li, Z. Gao, and J. Li, “Rethinking graph neural networks for anomaly detection,” in _International Conference on Machine Learning_. PMLR, 2022, pp. 21 076–21 089.
  * [40] Y. Gao, X. Wang, X. He, Z. Liu, H. Feng, and Y. Zhang, “Addressing heterophily in graph anomaly detection: A perspective of graph spectrum,” in _Proceedings of the ACM Web Conference 2023_ , 2023, pp. 1528–1538.
  * [41] F. Liu, X. Ma, J. Wu, J. Yang, S. Xue, A. Beheshti, C. Zhou, H. Peng, Q. Z. Sheng, and C. C. Aggarwal, “Dagad: Data augmentation for graph anomaly detection,” in _2022 IEEE International Conference on Data Mining (ICDM)_. IEEE, 2022, pp. 259–268.
  * [42] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga _et al._ , “Pytorch: An imperative style, high-performance deep learning library,” _Advances in neural information processing systems_ , vol. 32, 2019.
  * [43] M. Fey and J. E. Lenssen, “Fast graph representation learning with pytorch geometric,” _arXiv preprint arXiv:1903.02428_ , 2019.
  * [44] M. Y. Wang, “Deep graph library: Towards efficient and scalable deep learning on graphs,” in _ICLR workshop on representation learning on graphs and manifolds_ , 2019.
  * [45] K. Ding, J. Li, R. Bhanushali, and H. Liu, “Deep anomaly detection on attributed networks,” in _Proceedings of the 2019 SIAM International Conference on Data Mining_. SIAM, 2019, pp. 594–602.
  * [46] Z. Xu, X. Huang, Y. Zhao, Y. Dong, and J. Li, “Contrastive attributed network anomaly detection with data augmentation,” in _Pacific-Asia Conference on Knowledge Discovery and Data Mining_. Springer, 2022, pp. 444–457.
  * [47] Y. Liu, Z. Li, S. Pan, C. Gong, C. Zhou, and G. Karypis, “Anomaly detection on attributed networks via contrastive self-supervised learning,” _IEEE transactions on neural networks and learning systems_ , vol. 33, no. 6, pp. 2378–2392, 2021.
  * [48] Z. Liu, Y. Dou, P. S. Yu, Y. Deng, and H. Peng, “Alleviating the inconsistency problem of applying graph neural network to fraud detection,” in _Proceedings of the 43rd international ACM SIGIR conference on research and development in information retrieval_ , 2020, pp. 1569–1572.
  * [49] D. Jin, Z. Yu, C. Huo, R. Wang, X. Wang, D. He, and J. Han, “Universal graph convolutional networks,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 10 654–10 664, 2021.
  * [50] J. Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra, “Beyond homophily in graph neural networks: Current limitations and effective designs,” _Advances in neural information processing systems_ , vol. 33, pp. 7793–7804, 2020.
  * [51] T. Zhao, X. Zhang, and S. Wang, “Graphsmote: Imbalanced node classification on graphs with graph neural networks,” in _Proceedings of the 14th ACM international conference on web search and data mining_ , 2021, pp. 833–841.
  * [52] T. N. Kipf and M. Welling, “Variational graph auto-encoders,” _arXiv preprint arXiv:1611.07308_ , 2016.
  * [53] J. You, R. Ying, X. Ren, W. Hamilton, and J. Leskovec, “Graphrnn: Generating realistic graphs with deep auto-regressive models,” in _International conference on machine learning_. PMLR, 2018, pp. 5708–5717.
  * [54] A. Bojchevski, O. Shchur, D. Zügner, and S. Günnemann, “Netgan: Generating graphs via random walks,” in _International conference on machine learning_. PMLR, 2018, pp. 610–619.
  * [55] Y. Luo, K. Yan, and S. Ji, “Graphdf: A discrete flow model for molecular graph generation,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 7192–7203.
  * [56] M. Li, E. Kreačić, V. K. Potluru, and P. Li, “Graphmaker: Can diffusion models generate large attributed graphs?” _arXiv preprint arXiv:2310.13833_ , 2023.
  * [57] H. Liu, B. Hu, X. Wang, C. Shi, Z. Zhang, and J. Zhou, “Confidence may cheat: Self-training on graph neural networks under distribution shift,” in _Proceedings of the ACM Web Conference 2022_ , 2022, pp. 1248–1258.
  * [58] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [59] J. Zhao, M. Mathieu, and Y. LeCun, “Energy-based generative adversarial network,” _arXiv preprint arXiv:1609.03126_ , 2016.
  * [60] D. Rezende and S. Mohamed, “Variational inference with normalizing flows,” in _International conference on machine learning_. PMLR, 2015, pp. 1530–1538.