UniGAD: Unifying Multi-level Graph Anomaly Detection
Authors: Yiqing Lin
Jianheng Tang
Chenyi Zi
H. Vicky Zhao
Yuan Yao
Jia Li
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Anomaly Detection
Graph Neural Networks
Primary area: graph_neural_networks
TL;DR: We propose the first unified framework for detecting anomalies at node, edge, and graph levels.

Abstract: Graph Anomaly Detection (GAD) aims to identify uncommon, deviated, or suspicious objects within graph-structured data. Existing methods generally focus on a single graph object type (node, edge, graph, etc.) and often overlook the inherent connections among different object types of graph anomalies. For instance, a money laundering transaction might involve an abnormal account and the broader community it interacts with. To address this, we present UniGAD, the first unified framework for detecting anomalies at node, edge, and graph levels jointly. Specifically, we develop the Maximum Rayleigh Quotient Subgraph Sampler (MRQSampler) that unifies multi-level formats by transferring objects at each level into graph-level tasks on subgraphs. We theoretically prove that MRQSampler maximizes the accumulated spectral energy of subgraphs (i.e., the Rayleigh quotient) to preserve the most significant anomaly information. To further unify multi-level training, we introduce a novel GraphStitch Network to integrate information across different levels, adjust the amount of sharing required at each level, and harmonize conflicting training goals. Comprehensive experiments show that UniGAD outperforms both existing GAD methods specialized for a single task and graph prompt-based approaches for multiple tasks, while also providing robust zero-shot task transferability.

UniGAD: Unifying Multi-level Graph Anomaly Detection
Yiqing Lin' Jianheng Tang Chenyi Zi H.ickky Zhao', Yuan Yao?, Jia Li Tsinghua University
Hong Kong University of Science and Technology
HHong Kong University of Science and Technology (Guangzhou)
linyq200mails. tsinghua. edu. en, jtangbf ust hk, barristanzi1666gmaal. com, vzhaoOtsinghua, edu. en, (yuany, yyuany,jialee, jialee] Oust.
Abstract
Graph Anomaly Detection (GAD) aims to identify uncommon, deviated, or sus- picious objects within graph-structured data. Existing methods generally focus single graph object type (node, edge, graph, etc.) and often overlook the inherent connections among different object types of graph anomalies. For in- stance, money laundering transaction might involve abnormal account and the broader community it interacts with. To address this, we present UniGAD, the first unified framework for detecting anomalies at node, edge, and graph lev- els jointly. Specifically, we develop the Maximum Rayleigh Quotient Subgraph Sampler (MRQSampler) that unifies multi-level formats by transferring objects at each level into graph-level tasks on subgraphs. We theoretically prove that MRQSampler maximizes the accumulated spectral energy of subgraphs (i.e., the Rayleigh quotient) to preserve the most significant anomaly information. To further unify multi-level training, introduce novel GraphStitch Network integrate information across different levels, adjust the amount of sharing required at each level, and harmonize conflicting training goals. Comprehensive experi- ments show that UniGAD outperforms both existing GAD methods specialized for single task and graph prompt-base based approaches for multiple tasks, while also providing robust zero-shot task transferability. All codes can be found at https: /ttpss:/g/n thub. com com/111yyq11///U1i
Introduction
Graph Anomaly Detection (GAD) involves identifying a minority of uncommon graph objects that significantly deviate from the majority within graph-structured data [17, 2]. These anomalies can manifest as abnormal nodes, unusual relationships, irregular substructures within the graph, or entire graphs that deviate significantly from others. GAD has many practical applications in various contexts, including the identification bots and fake news on social media [3, 1, 403, detection of sensor faults and internet invasions in IoT networks [8, 14], and prevention of fraudsters and money laundering activities in transaction networks [19, 55]. The mainstream GAD models originate from the Graph Neural Networks (GNNs), which have recently gained popularity for mining graph data [52, 24, 57, 16]. To address the specific challenges of graph anomalies such as label imbalance [34, 31], relation camouflage [12. 38], and feature heterophily [50, 15], numerous adaptations of standard GNNs have been proposed [9, 67, 13, 40, 39, 10, 53, 41, 62].
However, existing GAD approaches typically focus on single type of graph object, such as node-level or graph-level anomaly detection, often overlooking the inherent correlations between different types
WWrk done visiting student Hong Kong University of Science and Technology. Corresponding Author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Pre-train Shared GNN
Subgraph Sampling
Graph Representation
Multi-level Layer!
Multi-level Layerz
Prediction
Stitch Loyerl
Stitch Leyer2
node
node
Node Anomalies
Node
Imput
MQRSampler
Output
Encoder
GNN
Pool ing
odge
odge
Edge Anomalies
Edge
graph
graph
Anomalies
Graph
Graph
(I) Unify multi-level formats.
(II) Unify multi-level training.
Figure 1: The overall framework of UniGAD.
of objects in graph-structured data. For example, a money laundering transaction might involve both an abnormal account and the broader community interacts with, while the specific cancer of cell is determined by particular proteins or protein complexes within the cell. Although some unsupervised methods fuse information from nodes, edges, and subgraphs through reconstruction [27, 10, 47] or contrastive pre-training [58, 13, 36), they are still limited to single-level label supervision or prediction. There is a need for a unified approach that considers these correlations information across different levels and performs multi-level anomaly detection.
To design unified model for addressing multi-level GAD, we identify two key challenges: 1. How to unify multi-level formats? Addressing node-level, edge-level, and graph-level tasks uniformly is challenging due to their inherent differences. Some recent works provide insights into unifying these tasks through the use of large language models (LLMs) or prompt tuning. While some methods leverage the generalization capability of L.LMs [32, 54, 29] on text-attributed graphs, such semantic information is often unavailable in anomaly detection scenarios due to privacy concerns. On the other hand, graph prompt learning methods [48, 37, 61] design induced k-hopp graphs to transform node or edge levels into graph-level tasks. Nevertheless, their sampling strategies are not specifically tailored to anomaly data, resulting in inappropriate node selections that 'erase' critical anomaly information. This oversight can severely impact the effectiveness of anomaly detection.
How to unify multi-level training? Training single model for multi-level tasks involves various influencing factors, such transferring information between different levels and achieving balanced training of these level tasks. There is limited rescarch on multi-task learning in the graph learning domain. Efforts like ParetoGNN [23] employ multiple sule-supe learning objectives (c.g.. similarity, mutual information) as independent tasks, but these are insufficient for managing multi- level supervision. A comprehensive approach is needed to effectively integrate and balance the training of different level tasks in multi-level GAD.
In this paper, we propose UniGAD, unified GAD model that leverages the transferability of information across node-level, edge-level, and graph-level tasks. To address the first challenge, we develop novel subgraph sampler, MRQSampler, that maximizes accumulated spectral energy (i.e.. the Rayleigh quotient) in the sampled subgraph with theoretical guarantee, ensuring that the sampled subgraphs contain the most critical anomaly information from nodes and edges. For the second challenge, we introduce the GraphStitch Network, which unifies multi-level training by integrating separate but identical networks for nodes, edges, and graphs into unified multi-level model. This is achieved using a novel GraphStitch Unit that facilitates information sharing across different levels while maintaining the effectiveness of individual tasks. We perform comprehensive experiments on 14 GAD datasets and compare 17 state-of of-theeart methods covering both node-level and graph-level GAD techniques, as well prompt-based general multi-task graph learning methods. Results show that UniGAD achieves superior performance and offers robust zero-shot transferability across different tasks.
2 Related Work and Preliminaries
Graph Anomaly Detection. Leveraging deep learning techniques in GAD has led to significant advancements and a wide range of applications [3, 14, 1, 4. 19, 65]. thoroughly reviewed in comprehensive survey [43]. Node-level anomaly detection, the most prevalent scenario GAD, has witnessed numerous adaptations and improvements in graph neural networks (GNNs) aimed at

---

enhancing performance from either spatial [34, 38, 25] or spectral [28, 50, 15] perspective. Despite these advancements, recent benchmarks such as BOND [33] for unsupervised settings and GADBench [49] for supervised settings reveal that no single model excels across all datasets, highlighting the need for model selection tailored to specific datasets and task characteristics. For graph-level anomaly detection, various methodologies have been proposed, including transformation learning [66], knowledge distillation [42], and evolutionary mapping [44]. SIGNET [35] employs information bottleneck to generate informative subgraphs for explaining graph-level anomalies, while Rayleigh Quotient GNN [11] explores the spectral properties of anomalous graphs. Although both node-level and graph-level anomaly detection are rapidly evolving fields, to the best of our knowledge, there is no existing model that supports the joint detection of both node-level and graph-level anomalies.
Multi-fask Learning on Graphs. Multi-task learning involves training model to handle multiple tasks simultaneously, utilizing shared representations and relationships within the graph to enhance performance across all tasks. Recently, techniques such as graph prompt-based approaches and large language model (L..M)-
approaches have shown promise this area. Prompt frameworks [69] like GraphPrompt [37], All-in-One [48], PRODIGY [22], MultiGPrompt [61], and SGL-PT [68] are designed to address a wide array of graph tasks. These approaches transform tasks at other levels into graph-level tasks by leveraging induced graphs. The All-in-One framework enhances connectivity by adding links between the prompt graph and the original graph, whereas GraphPrompl inserts the prompt token into graph nodes through element wiie multiplication. On the other hand, LLM-based frameworks [32, 54, 29, 6, 51] utilize the power of LLMs to learn from different levels, but they require graphs with text attributes or descriptions, which are not applicable in most anomaly detection scenarios. Additionally, some multi-task GNN efforts [23] focus on multiple self-supervised specific objectives (such similarity and mutual information) as independent tasks, which not suitable for unifying GAD with multi-level label supervision and prediction.
Notation. Let G = EV, denote connected undirected graph, where V = {V1, U2, .... UN J is the set of N nodes, E = {eiy} } is the set of edges, and X E RaxF', is node features. Let A be the corresponding adjacency matrix, D be the degree matrix with D E, Aij. Laplacian matrix L is
then defined as D A (regular) or as I - D 3 AD (normalized), where I is an identity matrix. The Laplacian matrix is a symmetric matrix and can be agen-decomposed as L = UAU", where the diagonal matrix A consists of real eigenvalues (graph spectrum). Besides, we define the subgraph as G, centered on node U and our sampled subgraph for node v, as S,.
Problem Formulation. The multi-level graph anomaly detection problem introduces a more universal challenge compared traditional single-level approaches, described as follows:
Definition 2.1 (Multi-level GAD). Given a training set Tr(N E, containing nodes, edges, and graphs with arbitrary labels at any of these levels, the goal is to train a unified model to predict anomalies in a test set T Te(N, & G), which also contains arbitrary labels at any of these levels.
Note that our approach does not require the presence of labels at all three levels simultaneously. It is feasible have labels one or more levels. Our proposed model aims to leverage the transferability of information across different levels to enhance its predictive capability.
3 Methodology
This section details the proposed model UniGAD for multi-level GAD, comprising a GNN encoder, MRQSampler, and GraphStitch Network, as shown in Fig. 1. Firstly, shared pre-trained unsuper- vised GNN encoder is utilized to learn a more generalized node representation. To unify multi-level formats, the MRQSampler employs spectral sampling to extract subgraphs that contain the highest amount of anomalous information from nodes and edges. thus converting tasks at all three levels into geaph-level tasks (Sec. 3.1). To unify multi-level training, the GraphStitch Network integrates information from different levels, adjusts the amount of sharing required at each level, and harmonizes conflicting training goals. (Sec. 3.2).
3.1 Spectral Subgraph Sampler for Unifying Multi-level Formats
In this subsection, we present the Maximum Rayleigh Quotient Subgraph Sampler (MRQSampler), the core module of our unified framework. By sampling subgraphs of nodes or edges, we transform node-level and edge-level tasks into graph-level tasks. Our sampler optimizes these subgraphs to maximize the Rayleigh quotient, ensuring that the sampled subgraphs retain a higher concentration of anomaly information.
3

---

Message
Passing
Sampling
Graph
Rooted
Sampled Subtree
Figure Message passing GNNs and rooted subtree sampling.
3.1.1 Analysis of the Subgraph Sampling
What is suitable subgraph for GAD? Existing methods on selecting subgraphs for target nodes or edges often use straightforward approaches like r-ego or h-hop subgraphs [48]. However, the size of the subgraph is critical for classification outcomes. If the subgraph too large, includes too many irrelevant nodes, while if it is too small, it may not align effectively with graph-level tasks.
To measure anomaly information in subgraph, recent studies [50, 11] have identified 'right- shift' phenomenon in the spectral energy distribution, moving from low to higher frequencies. This accumulated spectral energy can be quantified by the Rayleigh quotient [20]:
x²'La Læ
EisYE Aij(z -xa)²
RQ L)
Tr.
Eiev #t
The following lemma [50] illustrates the relationship between the Rayleigh quotient RQ(æ, L) and anomaly information:
Lemma 1 (Tang, 2022). Rayleigh quotient RQ(x, L), i.e. the accumulated spectral energy of the graph signal, is monotonically increasing with the anomaly degree.
Thus, for any node our sampling objective is to identify the induced subgraph with the highest Rayleigh quotient containing the most anomaly information.
Where to Sample Subgraph From? To preserve the properties of target nodes, it is essential to sample subgraphs centered around these nodes, capturing key surrounding nodes. The most intuitive methods are r-ego graphs or k-hop graphs. However, considering the message-passing mechanisms of most GNNs [24, 56, 16], classical work [57] provides valuable insight:
Lemma 2 (Xu, 2018). GNN recursively updates each node's 's feature vector through its rooted subtree structures capture the network structure and features of surrounding nodes.
As shown in Fig. 2, the message-passing process GNNs suggests that rooted subtree centered on the target node is more consistent with the GNN's architecture. Therefore, sample subgraphs from these rooted subtree structures. The remaining question is: How to implement subgraph sampling based on the above? To address this, we introduce novel MRQSampler in the next subsection.
3.1.2 Maximum Rayleigh Quotient Subgraph Sampler (MRQSampler)
Building on the motivation in Section 3.1.1, our approach involves sampling subgraphs for each node starting from the rooted subtree with the node its root. The target node is always included. We then select the subtree with the maximum Rayleigh quotient from all possible subtrees as the representative subgraph for that node to ensure contain the maximum anomaly information. We formulate this as the following optimization problem:
E(PrEES (xp xxg)
S* = arg max SC9
Epss z?7
s.t.
S,
VEp E S, (v. Up) accessible.
where G represents k-depth rooted subtree from v. and a possible subgraph from G. The first constraint ensures the target node is included, and the second constraint ensures message passability. Generally, similar selecting subgraphs this manner considered an NP-Hard problem [59]. However, leveraging the properties of trees, propose algorithm to solve the optimal solution.

---

Decouple into 4 unconnected subtrees
Decouple into independent nodes
Definition of Sub-problem:
Down into Simpler Sub-problene
Compute the optimal nodeset with
Amaz rooted free.
(Sub) Compute the optimal nodeset with Agerr in each child's rooted tree.
Recursively solve the sub-problem from the bottom up
Rooted Subtree
Each Child's Subtree
Figure 3: MRQSampler: (i) Derive the condition (Theorem 2) satisfied with the optimal subtree. (ii) Decompose the problem into simpler sub-problems by recursing through the tree depth to solve the optimal subtree with the dynamic programming (DP) algorithm.
We first determine the conditions that increase a subgraph's Rayleigh quotient when adding a node, presented in the following theorem:
Theorem For a graph G. let one of its subgraphs be S, and let its Rayleigh quotient be RQ(S). If node fnew G - S is added to S, the Rayleigh quotient (Q(S) will increase if and only if:
A ((new)) Evres(Inev x²) RQ(S).
Fnew
The proof of Theorem 1 can be found in Appendix A.1. We can extend this theorem from a single new node Unew to a new node set Vnew, leading to the following corollary:
Corollary 1. For a graph G, let one of its subgraphs be S, and let its Rayleigh quotient be RQ(S).
If a new nodeset Vnew C G - -S added to S, the Rayleigh quotient RQ(S) will increase if and only if:
A(Ynew) E(ir)e (Inew, - -xr)² 2 E(s))EEvne (Inew: Fnews, )2
RQ(S). (4)
E Bnow VVow
222
The proof details are also Appendix A.2. While the above analysis can indeed increase the Rayleigh quotient of the sampled subgraph, the sampling order may cause the results to fall into local optimum, which may not guarantee a globally optimal solution. To identify the nodes that must be sampled in the optimal subgraph, we present the following theorem:
Theorem 2. For a graph G, one of its subgraph be S, the S be its final optimal subgraph, and S" For new connected nodeset Vnew ns 0, it contained in S" when satisfies:
A Amar Canau((veeee (Vnew) = max A(Vnew); and A Amax ( (new) RQ(S).
(5)
Vnew SG-S
We refer readers Appendix A.3 for the rigorous proof. Through the above analysis, derive the conditions of the nodeset contained in the optimal subtree (Theorem 2). When Vnew satisfies Eq. (5), it always increases the Rayleigh quotient based on the current subgraph, ensuring that Vnear contained in the optimal solution. Thus, we decouple the problem of finding the subgraph with the maximum Rayleigh quotient into a process of finding the maximum Amer (Vnew) each time, until adding any node/node set fails increase the RQ(S). Following this, we design dynamic programming (DP) algorithm to ensure the optimal subset satisfies these conditions.
MRQSampler Algorithm. We introduce the Maximum Rayleigh Quotient Subgraph Sampler (MRQSampler), which uses dynamic programming (DP) to find the optimal solution. We break down the computation for the central node into sub-problems, storing the results of sub-problems to avoid redundant computations in future calculations. For rooted subtree with the target node (edge) as the root, its children are unconnected to each other. In Fig. 3, we consider 2-depth subtree and summarize our algorithm as follows:
We recursively compute and store the maximum A()new) for each subtree, which can be down into simpler sub-problems similar to the previous one and calculates each layer in the tree recursively from the bottom up.
Stage 1:
5

---

Multi-level Layer!
Multi-level
Layer2
node
node
Bag
edge
Meg Reel
odge
[agndggn Rgol
graph
GraphStitch Unit
graph
GraphStitch Unit
Separate but Identical
Separate but Identical
Architecture
Architecture
Figure 4: GraphStitch network structure in UniGAD. Node level is highlighted.
Stage 2: Based Theorem 2, iteratively select the descendant with the maximum A maz (Vnww) (within its rooted subtree) of the target node and the currently selected nodeset, until the conditions of Theorem 2 are no longer satisfied, i.c., when the Rayleigh quotient of the sampled subgraph longer increases.
For efficiency, this approach can obtain the subgraph with the maximum Rayleigh quotient of the target node/edge's rooted subtree while reducing the algorithmic complexity to O(N log N). It can be further accelerated in parallel since the computation for different nodes is independent. Additionally, the sampling process only needs be computed once in training and inference processes, minimally impacting model efficiency. For the detailed pseudocode of the algorithm, please refer to Appendix B. Note that we use mean pooling for entire graphs, but for subgraphs, we use weighted pooling to highlight central nodes/edges, with an exponential decay based on the number of hops to the central nodes/edges. This method transforms node-level and edge-level tasks into graph-level tasks, ensuring that the most anomaly information is retained in the sampled subgraphs.
3.2
GraphStitch Network for Unifying Multi-level Training
After obtaining graph representations, training them together through fully connected layer can negatively impact individual levels due to the inherent differences across different-level anomalies. This result in medioere performance all levels. A key challenge, therefore, is to facilitate information transfer between multi-levels without compromising single-level effectiveness. Inspired by work in the computer vision field [45], introduce the novel GraphStitch Network to jointly consider multi-level representations.
Specifically, we train separate but identical networks for each level and use the GraphStitch unit to combine these networks into a multi-level network, managing the degree of sharing required at different levels. This approach aims maintain single-level effectiveness while enhancing multi-level information transfer. The network structure is illustrated in Fig. 4.
To elaborate, we denote ey: eg, and eg as the embeddings for nodes, edges, and graphs, respec- tively. The node embedding eN (enn ene eng) consists of outputs from three separate but identically structured networks specialized for nodes, edges, and graphs. Similarly, the edge and graph embeddings are represented eg (een, Beer eeg) and eg (Egnr ege: egg)". egg)
We define a GraphStitch operation as follows:
( Onn
O'n
ang
CêN,Cg,Co = diag
Aeen
Olee
Oleg
(CN, Cg,
agn
A'ge
('gg
The sharing of representations is achieved by learning a linear combination of the outputs from the three networks. This linear combination is parameterized using learnable a. In particular, when training data lacks certain level, the influence of that level on other levels is defined zero during training but still retains the influence other levels on this level. In this way, it allows the labels for training and testing to be arbitrary. Besides, if all the cross terms (oner Ongg Otens Oeg- O'nn+ O'ye) are equal to means that training the three networks jointly is equivalent to training them independently. Finally, the embeddings for nodes, edges, and graphs are fed into three independent multi-layer perceptrons (MLPs) to compute the abnormal probabilities p." pf and p.d respectively.

---

In addition to the GraphStitch structure, UniGAD optimizes the loss functions for multi-level tasks. Specifically, the gradients of each level task's loss may conflict in direction or magnitude, potentially causing negative effects and resulting in worse performance compared to learning single-level tasks individually. Therefore, UniGAD uses multi-level weighted cross-entropy loss for training:
== +=EE& 3(N.E.)) (VE.
(19) (.E. log pp: (p......1) +
y/ (... log (1 (1- ps (. (7)
where 7 is the ratio of anomaly labels (y/: 1) to normal labels (y: 0) and 3V are adaptive weights for different tasks. We adopt 'Gradient Surgery' approach [60] to adjust the 3(N1.99) altering the gradients by projecting each onto the normal plane of the others. This prevents the interfering components of the gradients from affecting the network and minimizes interference among different-level GAD tasks. In this way. UniGAD ensures that each level remains relatively independent while facilitating cross-passing of relevant information between multi-level tasks.
4 Experiments
In this section, conduct experiments to evaluate our UniGAD with node-level, edge-level, and graph-level tasks by answering the following questions: Q1: How effective UniGAD unifying in multi-level anomaly detection? Q2: Can UniGAD transfer information across different levels in zero-shot learning? Q3: What are the contributions of the modular design in the UniGAD model? Q4: How do the time and space efficiencies of UniGAD compare to those of other methods?
4.1 Experimental Setup
Datasets. We consider a total of 14 datasets, including both single-graph datasets and multi multi-graph datasets. 7 single-graph datasets are used to evaluate the performance of unifying node-level and edge- level tasks: Reddit, Weibo, Amazon, Yelp, Tolokers, and Questions, T-finance from the work [49], which contain node-level anomaly labels. For edge anomaly labels, generated them according to
a specific anomaly probability following the formula pft.f) arg anom: Pinso)). And 7 multi- gualti datasets used to validate the performance of unifying node-level and graph-level tasks, including
BM-MN, BM-MS, BM-MT, MUTAG, MNISTO, MNISTI, and T-Group. The first six datasets are from [35], containing both node anomaly labels and graph anomaly labels. Moreover, real-world large-scale social group dataset T-Group, combining the data (graph anomaly labels) in [26]. For its node anomaly labels, assume that if node appears in 3 malicious social groups, we consider it a malicious node. Statistical data for these datasets can be found in Table 1, including the percentage of training data, the number of graphs, edges, nodes, feature dimensions, and the proportions of abnormal nodes, edges, and graphs (Nodes.t. Edges and Graphs..).
release
Table I: Detailed statistics of the datasets used in our experiments.
Dataset
Train % Graphs
f Edges
# Nodes
# Dims Nodes.6 Edges,b Graphs,
Reddit
40%
168,016
10,984
64
3.33%
2.72%
Weibo 40%
416,368
8,405
400
10.33%
5.71%
Amazon
70%
8,847,096
11,944
25
6.87%
2.49%
Yelp
70%
7,739.912
45,954
32
14.53%
13.89%
Tolokers
50%
530,758
11,758
10
21.82%
33.44%
Questions
50%
202,461
48,921
301
2.98%
7.50%
F-Finance
40%
21,222,543
39,357
4.58%
2.77%
BM-MN
40%
700
40,032
12,911
48.91%
14.29%
BM-MS
40%
700
30,238
9,829
31.99%
14.29%
BM-MT
40%
700
32,042
10,147
34.49%
14.29%
MUTAG
40%
2,951
179.732
88,926
14
4.81%
34.40%
MNISTO
10%
70,000
41,334,380
4,939,668
35.46%
9.86%
MNIST1
10%
70,000
41.334.380
4,939,668
35.46%
/
11.25%
T-Group
40%
37,402
93,367,082
11,015,616
10
0.64%
/
4.26%
Baselines. To comprehensively compare with traditional single-level tasks, we consider nine repre- sentative node-level methods: GCN [24], GIN [57], GraphS [16], SGC [56), GAT [52], BernNet [18), PNA [7], AMNet [5], and BWGNN [50]. Given the limited work on edge anomalies, we adapt a concatenated strategy [64] from link prediction, resulting in nine corresponding edge-level methods: GCNE, GINE, GSAGEE, SGCE, GATE, BernE, PNAE, AME, and BWE. For graph-level
7

---

Table Comparison of unified performance (AUROC) at both node and edge levels with different
single-level methods, multi-task methods, and our proposed method.
Dataset Tack-level
Reddit
Weiho
Yelp
Tnlokers Node
Questions Filgo
I-Finance
Node
Edge
Node
Fidge
Node
Fdge
Node
Fdge
Edge
Node
Node
Fidge
GCN
02:00
57,
57.
15
90:
GIN
B5.22
96.84
92.17
1
74.45
75.15
88.3 33
86, 56.43
GopiSAGE
02:25
94.45
$4.53
82. 12
73:74
72.4 47
78. 16
SGC
52:12
97:71
S0.24
08.05
60.51
70.20
74.21
Node-Level
GAT
65:87
94.40
96 24
17: 80
78, 1..90
71.35
90. 00
BernNet
08.08
50.93
96.62
81.68
70.08
70.25
92.37
PNA
65.26
07.45
41
71.81
75.82
71.70
68.
AMNet
68.51
04.17
07.31
61.62
76,0
633
90. 90.58
BWGNN
64.63
H9.31
GENE
111
989 00.003
57. (1)
T3.50
00
GINE
70
GSAGEE
73,331
SGGE
18.
70.41
711
74.24
62
Edge-Jevel
GATE
67.01 117
07.
61.64
BernE
57
07.
80
03
73.50
84.76
87 50
PNAE
64.15
99. 30
75.71
67.
75.08
84.05
83.91
AME
66.75
17. 07.00
89.96
73. 63
71.30
84.95
86: 19
DWE
67.30
08. 93
91.61
75.63
75.06
85,00
27
Mutti task
GraphPromge U
All-in-Qie-U
50.00
01.35
54.10
49.78
55.29
48.01
02.65
50.71
56.11
50.00
64.80
50.96
10.55
40.77
49.
09.55 5666
51.224
50:41
49.29
19.86
55.16
11.00 40
64.24
50.01
0OT
ODT
OOT
OUT
UniGAD
UniGAD- GCN
71.05
65.46
09.02
99. 19.18
82.
80.04
113 22
61.77 74
77.
72.89
73 02
74.72
95.08
93.75
(Ours)
UniGAD BWG
64 42
33.60
90.07
09. 10
84
92.
86
79 05
80
80.62
74.85
70.97
73.45
96.
94.32
anomaly detection, we consider six state-of-the-an methods: OCGIN [66], OCGTL [46], GLocalKD [42], iGAD [63]. GmapAD [44], and RQGNN [11]. Additionally, to compare multi-task models, we include two recent multi-task graph prompt methods: GraphPrompt [37] and All-in-One [48]. While these methods were not originally proposed for joint multi-task training, we adapt their ideas and develop multi-task versions for our comparison, GraphPrompp-UU and All-in-One- whose modifications were limited to the data preprocessing component to accommodate the simultaneous handling of multiple object types (node/edge or node/graph) within induced graphs.
Implementations. We evaluate three metrics: AUROC (Sec. 4), Macro Fl-score and AUPRC (Appendix E). For each result, we conduct 5 runs and report the mean results. In UniGAD, we choose two backbone GNN encoders: GCN [24] and BWGNN [50]. We use a shared graph pre-training method, GraphMAE [21], to obtain a more generalized node representation. For multi-dimensional feature vectors, we normalize all feature dimensions and then take the norm (I-norm in our case) to obtain a composite feature for each node, allowing us to identify the most anomalous nodes in MRQSampler based on this comprehensive feature. To avoid data leakage, for single-grapl datasets, edges between the training set and the testing set are not considered; for multi- graph datasets, the training set and the testing set consist of different graphs and their nodes. More details on the implementation can be found in the Appendix C.
4.2 Multi-Level Performance Comparison (RQ1)
To compare the performance of multi-level anomaly detection, conduct experiments under two settings. For the single-graph datasets, we compare the performance of unified training on node-level and edge-level data. For the multi-graph datasets, we compare the performance of unified training on node-level and graph-level data.
Node-level and edge-level jointly. We first evaluate the performance of unified training on node-level and edge-level data. We compare UniGAD against three groups of GNN models mentioned above: node-level models, edge-level models, and multi-task graph learning methods. Table 2 reports the AUROC of each model on six datasets, with the best result on each dataset highlighted in boldface. Overall, we find that UniGAD achieves state-of-the-art performance in nearly all scenarios. UniGAD outperforms single-level specialized models, indicating that unified training with UniGAD leverages information from other levels to enhance the performance of individual tasks. Multi-task approaches (GraphPrompt-U and All-in-One-U) tend to negatively impact multi-task performance, potentially because they are unable to effectively handle different types of anomaly label supervision. Meanwhile, UniGAD is designed for a multi-task setting, the performance on a single level might be slightly compromised to ensure the model performs well across all tasks in some datasets.
Node-level and graph-level jointly. We then evaluate the unified training of node-level and graph- level tasks under similar settings. Table 3 shows the results, and UniGAD achieves state-of-the-a performance in nearly all scenarios. Our observations are as follows. First, there is multi-level synergy in UniGAD, where strong performance in one task benefits the performance of other tasks.
8

---

Table 3: Comparison of unified performance (AUROC) at both node and graph levels with different
single-level methods, multi-task methods, and our proposed method.
Dataset Task-level
BM-MNN
HML-S
BM-MI
MUTAG
MNISTO
MNNISII
T.Group Graph
Node
Graph
Node
Graph
Node
Graph
Node
Gruph
Node
Graph
Node
Graph
Node
GCN
86.31
90.17
52.30
99.35
94.30
93.84
91.81
GIN
56.23
50:41
54.90
09.29
53.55
53.40
61.51
GraphSAGG
5000
50.00
40.05
90.25
999 .9
09 99
61.15
SGC
50.27
50.87
40.04
89.119
86:.7
M6.97
82.65
Node level
GAT
58.47
B2-02
60.72
99:42
99.30
99 99
76.17
RemnNet
03000
B5- 58
50.15
98 97
919 99
90 99
93.85
PNA
72.96
55.19
75.61
98. 76
59..30
90.57
$3.66
BWGNN
03.05
57.22
$8.07
90.50
999 99.90
99 90
94.51
OCGIN
96.
51. .V7
58.05
89.50
07:24
96.
64.53
OCXITL
98.48
53.17
59.00
92.11
59.36
903.45
46.77
Giogh-ioeel
GLo
iGAD
02.36
01.68
08:05
77.25 25
59.14
53.22
90.28
72.77
06.60
96:90
00. 00.50
57 42
61.41
78,53
GmupAD RQGIN
50u00
50.00
500,00
78.
0OM
00M
00M
98.
97.99
99.83
06.41
95.62
95.37
73,90
Multi-ack
GiophPhrmmpt-11
All m One U
51.59
66.88
16.65
3.21
$4.70
50.54
16.07
19:42
60.70
51.42
45.89
10.35
97.05
50.65
68. 23
05.38
81.16
0CT
83.88
O0T
81:37
00T
00T
6:10
07:40
00T
50.81
000
UniCID
USICID--GEN
99.75
94.20
99 60
99 67
99.65 63
909.99 .99
90.50
96.53
97 93
98.50
95.
11
89.58
95-67
88-75
(Ours
UnGGAD BWG
92.00
68.74
50.30
68.35
90.76
36,01
99.54
73
99.99 99.90
89.80
09.39 90
09.99
96.19
88.78
Table 4: shro transferability (AUROC) at node and edge levels.
Methods
N-EE
Reddit
E-N
N-EE
Weibo
E-N
N-E
Amazon
E-N
N--E
Yelp
E-N
N-E
Tolokers
E E-N
N--E
Questions
E
N--E
T--Finacce
E--N
GraphPromppt-U U
54.06
47.43
57.03
42.85
49.76
50.26
49.97
49.94
48.56
51.08
54.26
51.97
OOT
OCT
All-in-One-I/
43.23
40.93
52.22
54.30
52.61
42.35
40.48
44.50
48.34
50.22
40.83
51.97
OOF
OOT
UniGAD -CN
59.67
98.31
98.
76.20
82.38
58.28
60.92
71.45
73.35
00.54
65.37
99.63
90:17
UniGAD- -00--1 BWG
53.32
57.63
91.71
96.87
82.64
96. 41
75.56
84.08
74.04
78. 19
71.02
02.72
93.60
95.68
For example, in MNIST-O and MNIST-1, compared to other graph-level GAD methods, UniGAD significantly boosts graph-level performance by leveraging strong node-level results. Second, Uni- GAD performs better on large graphs, likely because graph structure plays a more significant role in smaller datasets. However, the backbones of UniGAD (GCN, BWGNN) are primarily node-level models, which may not effectively encode graph-level structural information. This limitation's 's impact diminishes large-scale graph datasets. Besides, methods like All-in-One-U often run out of time (OOT) with large datasets because they redundantly learn the same node representations across different subgraphs, making processing impractically slow, especially for large graph-level datasets like T- T-rroup. UniGAD addresses this issue by using shared GNN encoder across tasks, avoiding redundant learning and enhancing efficiency.
4.3 The Transferability in Zero-Shot Learning (RQ2)
To assess the transfer capability of UniGAD, we explore zero-shot learning scenarios where labels for a given level have never been exposed during training. as shown in Tables 4 and 5. In these experiments, UniGAD is trained solely with labels from alternative levels. The notation N + E indicates using node labels to infer edge labels, with analogous notations for other label transfers. Our findings indicate that in zero-shot scenarios, UniGAD outperforms existing multi-task prompt learning methods. Moreover, the classification performance of UniGAD under zero-shot transfer learning even surpasses some of the leading baselines in supervised settings on Yelp and BM-MS. It highlights the superior transfer capability of UniGAD across various GAD tasks.
4.4 Ablation Study (RQ3)
To investigate the contribution of each module in UniGAD we present the ab-
Table Performance of UniGAD and its variants.
lation study results in Table 6. For the sampler module, we compare the re- sults without subgraph sampling (w/o
BM-MS
Reddit
Metrics Tesk-level
AUROC
Macro F1
AUROC
Macro Fl
node
graph
node
graph
node
edge
node
edge
GS.). using simple sampler with all 2- hop neighbors (w 2hop.), and using ran- dom sampling (w RS.). For the Graph- Stitch module, we replace it with a uni- fied MLP (w/o ST.). The results in- dicate that both the subgraph sampler (SG.) and the GraphStitch (ST.) modules enhance the overall performance of UniGAD. Additionally.
wlo GS.
97. 13
98.
80.35
95. 79
68.69
66.06
53.83
52.78
2hop. RS.
97.49
99.94
67.29
84.20
67.53
63.62
51.77
93.85
84.92
85.88
72.21
05.32
61.85
52.32
51.03
w/o ST.
99.94
95.51
99.47
84.91
67.74
65.92
54.35
52.52
UniGAD 99.60
99.67
99.57
95.86
71.65
65.46
56.77
53.80

---

Table 5: Zero-shot transferability (AUROC) at node and graph levels.
BM-MN
BM-MS
BM-MT
MUTAG
MNISTO
T-Group
Methods
N-+G
G-+N
N-+G
G-+N
N-G
G-NN
N-+G
G--N
N-+G
G-+N
N-+G
G--N
GruphPrompt-U
50.60
51.57
51.97
46.95
46.62
48.06
39.62
64.26
83.98
88.06
58.28
58.35
All-in One-U U
94.39
65.69
52.63
34.27
61.63
36.13
00T
00T
0OT
OOT
UniGAD- GCN
72.82
87.63
81.49
90.83
62. 85
79.26
72.79
88.53
85,24
70.57
86.86
75.89
UniGAD BWG
64.61
57.56
65.33
51.34
55.78
53.41
66.92
87.03
74.23
63.70
86.81
64.81
CPU
GPU
Grephiiity
Too modes
30'
Prtrgg baned
Meggoorpper
ky
Hemory (GB)
10'
Tene Coo
107
BWGNNN
QC1
GrapISACE
GIN
Sec
GAT
Bannket
PMd andver
occI
acaTi
RzOH
GkapPPonys UniDDD ocv
1S4D
UnIDAD INNS4N
(a) Comparing the execution time.
(b) Comparing the peak memory usage.
Figure 5: The evaluation of time and space efficiency metrics. We highlight the percentage of total execution time spent by MRQSampler.
inappropriate subgraph sampling may perform worse than subgraph sampling, likely due the loss of anomalous information during the sampling process.
4.5 Efficiency Analysis (RQ4)
we conduct a comprehensive evaluation of both time and space efficiency on the large-scale real-world T-Group dataset. To provide more straightforward comparison between single-task and multi-task baselines, we calculate the average, minimum, and maximum for combinations of single-task node- level and graph-level models, and compare these with multi-task models. The results, as shown in Fig. (a), indicate that in terms of execution time, our method is slower than the combination of the fastest single-level models but faster than the average of the combination. Regarding peak memory usage, Fig. 5 (b) demonstrates that graph-level models consume significantly more memory than node-level models. Our method maintains memory consumption comparable node-level models and substantially lower than both graph-level GAD models and prompt-based methods.
5
Conclusion
This paper presents UniGAD, a unified graph anomaly detection framework that jointly addresses anomalies at the node, edge, and graph levels. The model integrates two novel components: the MRQSampler and the GraphStitch network. MRQSampler maximizes spectral energy ensure subgraphs capture critical anomaly information, addressing the challenge of unifying different graph object formats. The GraphStitch Network unifies multi-level training by using identical networks for nodes, edges, and graphs, facilitated by the GraphStitch Unit for effective information sharing. Our thorough evaluations across 14 GAD datasets, including two real-world large-scale datasets (T-Finance and T-Group), and comparisons with 17 graph learning methods show that UniGAD not only surpasses existing models in various tasks but also exhibits strong zero-shot transferability capabilities. A limitation of our paper is that the GNN encoder primarily focuses on node-level embeddings, which may result in lost information about the graph structure. We leave the exploration of multi-level tasks pre-training in the future works.
10

---

Acknowledgments and Disclosure of Funding
Y. Lin and H. Zhao were supported by the Beijing Natural Science Foundation under Grant IS24036. J. Li was supported by NSFC Grant No. 62206067 and 2023 Yao was in part supported by the HKRGC GZ) Joint Funding Scheme and the NSFC/RGC Joint Research Scheme Grant N HKKSS635/20. In addition, Y. Lin was also awarded a Tsinghua Scholarship for Overseas Graduate Studies at the Hong Kong University of Science and Technology.
References
[1] Esma Aimeur, Sabrine Amri, and Gilles Brassard. Fake news, disinformation and misinforma- tion in social media: review. Social Network Analysis and Mining, 13(1):30, 2023.
[2] Leman Akoglu, Hanghang Tong, and Danai Koutra. Graph based anomaly detection and description: survey, Data mining and knowledge discovery, 29(3))626-668, 2015.
[3] Ketan Anand, Jay Kumar, and Kunal Anand. Anomaly detection in online social network: A survey. In 2017 International Conference on Inventive Communication and Computational Technologies (ICICCT), pages 456-459. IEEE, 2017.
[4] Alessandro Bondielli and Francesco Marcelloni. A survey on fake news and rumour detection techniques. Information Sciences, 497:38-555 55, 2019.
[5] Ziwei Chai, Siqi You, Yang Yang. Shiliang Pu, Jiarong Xu, Haoyang Cai, and Weihao Jiang. Can abnormality be detected by graph neural networks? In IJCAI, 2022.
[6] Nuo Chen, Yuhan Li, Jianheng Tang, and Jia Li. Graphwiz: An instruction-folloiin language model for graph computational problems. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 353-364, 2024.
[7] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:13260-13211 13271, 2020.
[8] Kelton AP Da Costa, João Papa, Celso O Lisboa, Roberto Munoz, and Victor Hugo C de Albuquerque. Internet of things: A survey machine dearning-based intrusion detection approaches. Computer Networks, 151:147-157, 2019.
[9] Ailin Deng and Bryan Hooi. Graph neural network-baae based anomaly detection in multivariate time series. Proceedings of the AAAI conference on artificial intelligence, pages 4027-4035, 2021.
[10] Kaize Ding, Jundong Li, Rohit Bhanushali, and Huan Liu. Deep anomaly detection on attributed networks. In Proceedings of the 2019 SIAM International Conference Data Mining. SIAM, 2019.
[11] Xiangyu Dong, Xingyi Zhang, and Sibo Wang. Rayleigh quotient graph neural networks for graph-level anomaly detection, arXiv preprint arXiv:2310.0288 028611 2023.
[12] Yingtong Dou, Zhiwei Liu, Li Sun, Yutong Deng, Hao Peng, and Philip S Yu. Enhancing graph neural network- based fraud detectors against camouflaged fraudsters. In CIKM, pages 315-324, 2020.
[13] 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. arXiv preprini arXiv:22 2.00555, 2022.
[14] Anuroop Gaddam, Tim Wilkin, Maia Angelova, and Jyotheesh Gaddam. Detecting sensor faults, anomalies and outliers in the internet of things: A survey on the challenges and solutions. Electronics, 93)::11,, 2020.
[15] Yuan Gao, Xiang Wang. Xiangnan He, Zhenguang Liu, Huamin Feng, and Yongdong Zhang Addressing heterophily in graph anomaly detection: A perspective of graph spectrum. In Proceedings of the ACM Web Conference, 2023.
[16) William Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NewrIPS, 2017.

---

[17] Jiawei Han, Micheline Kamber, and Jian Pei. Data Mining: Concepts and Techniques, 3rd edition. Morgan Kaufmann, 2011.
[18] Mingguo He, Zhewei Wei, Hongteng Xu, et al. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. Advances in Neural Information Processing Systems, 34:14239-1444 14251,, 2021.
[19] Waleed Hilal, S Andrew Gadsden, and John Yawney. Financial fraud: review of anomaly detection techniques and recent advances. Expert systems With applications, 193: 16:29,, 2022.
[20] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
[21] Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang. Chunjie Wang, and Jie Tang. Graphmae: Self-supervised masked graph autoencoders. In Proceedings of the 28th ACM
SIGKDD Conference on Knowledge Discovery and Data Mining, pages 594-604, 2022.
[22] Qian Huang, Hongyu Ren, Peng Chen, Gregor Kržmanc, Daniel Zeng, Percy S Liang, and Jure Leskovec. Prodigy: Enabling in-context learning over graphs. Advances in Neural Information Processing Systems, 36, 2024.
[23] Mingxuan Ju, Tong Zhao, Qianlong Wen, Wenhao Yu, Neil Shah, Yanfang Ye. and Chuxu Zhang. Multi-task sule-see graph neural networks enable stronger task generalization. arXiv preprint arXiv: 22.0::222000000.66. 2022.
[24] Thomas N. Kipf' and Max Welling, Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[25] Ao Li, Zhou Qin, Runshi Liu, Yiqun Yang. and Dong Li. Spam review detection with graph con- volutional networks. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pages 2703-2711, 2019.
[26] Jia Li, Yu Rong, Hong Cheng, Helen Meng, Wenbing Huang, and Junzhou Huang. Semi- supervised graph classification: A hierarchical graph perspective. In The World Wide Web Conference, pages 972 982, 2019.
[27] Jundong Li, Harsh Dani, Xia Hu, and Huan Liu. Radar: Residual analysis for anomaly detection in attributed networks. In IJCAI, pages 2152-2158, 2017.
[28] Yuening Li, Xiao Huang, Jundong Li, Mengnan Du, and Na Zou. Specae: Spectral autoencoder 2019.
for anomaly detection in attributed networks. In CIKM, pages
[29] Yuhan Li, Zhixun Li, Peisong Wang, Jia Li, Xiangguo Sun, Hong Cheng, and Jeffrey Xu Yu. survey of graph meets large language model: Progress and future directions. arXiv preprint arXiv:2311. 12399, 2023.
[30] Yiqing Lin and H Vicky Zhao. Maximum entropy attack on decision fusion with herding behaviors. IEEE Signal Processing Letters, 2024.
[31] 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 2022.
detection. arXiv preprint arXiv:2210.0977
[32] Hao Liu, Jiarui Feng. Lecheng Kong, Ningyue Liang, Dacheng Tao, Yixin Chen, and Muhan Zhang. One for all: Towards training one graph model for all classification tasks. arXiv preprins arXiv:2310.00144 2023.
[33] Kay Liu, Yingtong Dou, Yue Zhao, Xueying Ding, Xiyang Hu, Ruitong Zhang, Kaize Ding, Canyu Chen, Hao Peng, Kai Shu, Lichao Sun, Jundong Li, George H Chen, Zhihao Jia, and Philip S Yu. Bond: Benchmarking unsupervised outlier node detection on static attributed graphs. In Advances in Neural Information Processing Systems, volume 35, 2022.
[34] Yang Liu, Xiang Ao, Zidi Qin, Jianfeng Chi, Jinghua Feng, Hao Yang, and Qing He. Pick and choose: A gan-based imbalanced learning approach for fraud detection. In Proceedings of the Web Conference 2021, 2021.
[35] Yixin Liu, Kaize Ding, Qinghua Lu, Fuyi Li, Leo Yu Zhang, and Shirui Pan. Towards self- interpretable graph-level anomaly detection. Advances in Neural Information Processing Systems, 36, 2024.
12

---

[36] Yixin Liu, Zhao Li, Shirui Pan, Chen Gong, Chuan Zhou, and George Karypis. Anomaly detection on attributed networks via contrastive superviie learning. IEEE transactions on neural networks and learning systems, 2021.
[37] Zemin Liu, Xingtong Yu, Yuan Fang, and Xinming Zhang. Graphprompt: Unifying Pre- Training and Downstream Tasks for Graph Neural Networks. In The Web Conference, pages 417-428, 2023.
[38] Zhiwei Liu, Yingtong Dou, Philip S Yu, Yutong Deng, and Hao Peng. Alleviating the inconsis- tency problem of applying graph neural network to fraud detection. In SIGIR, pages 1579-1572, 2020.
[39] Zhiyuan Liu, Chunjie Cao, and Jingzhang Sun, Mul-gad: a supervisd graph anomaly detection framework via aggregating multi-view information. arXiv preprint arXiv:2212.05477 2022.
[40] Zhiyuan Liu, Chunjie Cao. Fangjian Tao, and Jingzhang Sun. Revisiting graph contrastive learning for anomaly detection. arXiv preprint arXiv:2305.022 02499,, 2023.
[41] Ziqi Liu, Chaochao Chen, Longfei Li, Jun Zhou, Xiaolong Li, Le Song, and Yuan Qi. Geniepath: Graph neural networks with adaptive receptive paths. In Proceedings of the AAAI Conference on Artificial Intelligence, pages
2019.
[42] Rongrong Ma, Guansong Pang, Ling Chen, and Anton van den Hengel. Deep graph-level anomaly detection by glocal knowledge distillation. In Proceedings of the fifteenth ACM international conference on web search and data mining, pages 704-714, 2022.
[43] Xiaoxiao Ma, Jia Wu, Shan Xue, Jian Yang. Chuan Zhou, Quan Z Sheng, Hui Xiong, and Leman Akoglu. A comprehensive survey on graph anomaly detection with deep learning. IEEE Transactions on Knowledge and Data Engineering, 2021.
[44] Xiaoxiao Ma, Jia Wu, Jian Yang, and Quan Z Sheng. Towards graph-level anomaly detection via deep evolutionary mapping. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1631-1642, 2023.
[45] Ishan Misra, Abhinav Shrivastava, Abhinav Gupta, and Martial Hebert. Cross-stitch networks for multi-task learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3994 4003, 2016
[46] Chen Qiu, Marius Kloft, Stephan Mandt, and Maja Rudolph. Raising the bar in graph-level anomaly detection. arXiv preprint arXiv:2205.1 13845, 2022.
[47] Amit Roy, Juan Shu, Jia Li, Carl Yang. Olivier Elshocht, Jeroen Smeets, and Pan Li. Gad-nr: Graph anomaly detection via neighborhood reconstruction. In Proceedings of the 17th ACM International Conference Web Search and Data Mining, pages 576 585, 2024.
[48] Xiangguo Sun, Hong Cheng, Jia Li, Bo Liu, and Jihong Guan. All in one: Multi-task prompting for graph neural networks. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2120-2131, 2023.
[49] Jianheng Tang, Fengrui Hua, Ziqi Gao, Peilin Zhao, and Jia Li. Gadbench: Revisiting and benchmarking supervised graph anomaly detection. Advances in Neural Information Processing Systems, 36, 2024.
[50] Jianheng Tang, Jiajin Li, Ziqi Gao, and Jia Li. Rethinking graph neural networks for anomaly detection. In International Conference on Machine Learning, 2022.
[51] Jianheng Tang, Qifan Zhang, Yuhan Li, and Jia Li. Grapharena: Benchmarking large language models on graph computational problems. arXiv preprint 0400::2407000379, 2024.
[52] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2017.
[53] Daixin Wang, Jianbin Lin, Peng Cui, Quanhui Jia, Zhen Wang. Yanming Fang, Quan Yu, Jun Zhou, Shuang Yang, and Yuan Qi. A semi-supervised graph attentive network for financial fraud detection. In ICDM, pages 598-607. IEEE, 2019.
13

---

[54] Jianing Wang, Junda Wu, Yupeng Hou, Yao Liu, Ming Gao, and Julian McAuley, Instructgraph: Boosting large language models via graph-centric instruction tuning and preference alignment. arXiv preprini arXiv:2402.08785, 2024.
[55] Mark Weber, Giacomo Domeniconi, Jie Chen, Daniel Karl Weidele, Claudio Bellei, Tom Robinson, and Charles E Leiserson. Anli-money laundering in bitcoin: Experimenting with graph convolutional networks for financial forensies. arXiv preprint arXiv: 02591, 2019.
[56] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In ICML, pages 6861 6861-6871, 2019.
[57] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ICLR, 2019.
[58] Zhiming Xu, Xiao Huang, Yue Zhao, Yushun Dong, and Jundong Li. Contrastive attributed network anomaly detection with data augmentation. In Proceedings of the PAKDD,, 2022.
[59] KUo Yang, Zhengyang Zhou, Xu Wang, Pengkun Wang, Limin Li, and Yang Wang. Raye-sub: Countering subgraph degradation via perfect reconstruction.
[60] Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gradient surgery for multi-task learning. Advances in Neural Information Processing Systems, 33:5824-5883 2020.
[61] Xingtong Yu, Chang Zhou, Yuan Fang, and Xinming Zhang. Multigprompt for multi-task pre-training and prompting on graphs. arXiv preprint arXiv:23/2.0373/, 2023.
[62] Ge Zhang, Jia Wu, Jian Yang, Amin Beheshti, Shan Xue, Chuan Zhou, and Quan Z Sheng. Fraudre: Fraud detection dual-resistant graph inconsistency and imbalance. In 202/ IEEE International Conference Data Mining (ICDM), pages 867-876. IEEE, 2021.
[63] Ge Zhang, Zhenyu Yang, Jia Wu, Jian Yang. Shan Xue, Hao Peng, Jianlin Su, Chuan Zhou, Quan Z Sheng, Leman Akoglu, et al. dise-iisce graph neural network for imbalanced graph-level anomaly detection. Advances in Neural Information Processing Systems, 35:24144- 24157. 2022.
[64] Muhan Zhang. Graph neural networks: link prediction. Graph Neural Networks: Foundations, Frontiers, and Applications, pages 195-223, 2022.
[65] Haihong Zhao, Bo Yang, Jiaxu Cui, Qianli Xing, Jiaxing Shen, Fujin Zhu, and Jiannong Cao. Effective fault scenario identification for communication networks via knowledge-enhancee graph neural networks. IEEE Transactions on Mobile Computing, 23(4):3243-3258 2023.
[66] Lingxiao Zhao and Leman Akoglu. On using classification datasets to evaluate graph outlier detection: Peculiar observations and new insights. Big Data, 11(3):151-180 2023.
[67] Li Zheng, Zhenpeng Li, Jian Li, Zhao Li, and Jun Gao. Addgraph: Anomaly detection in dynamic graph using attention- based temporal gen. In IJCAI, pages 4419-4425, 2019.
[68] Yun Zhu, Jianhao Guo, and Siliang Tang. Sgl-pt: A strong graph learner with graph prompt tuning. arXiv preprint arXiv:2302.1 /2449, 2023.
[69] Chenyi Zi, Haihong Zhao, Xiangguo Sun, Yiqing Lin, Hong Cheng, and Jia Li. Prog: A graph prompt learning benchmark. arXiv preprint arXiv:2406.05346 2024.
14

---

A Proofs
A.1 The proof of Theorem
Proof. For a new node Unew, let S' be the subgraph after the addition of Unew- Based on the fact
that the definition of Rayleigh quotient RQ((S) Lingees (x, =z,)² it need to satisfy the following
Eves 22
condition in order to increase the Rayleigh quotient RQ(S') RQ(()):
Ein-tee - -2 EZn - xx)² Eingee (xp - xg)
(A.1)
Ex,es x² + x
Ex,es x7
where Ex.es (Fnew x2 represents the sum of the feature difference between the new node Unew and the connecting edge of the node in the subgraph S. It is worth noting that these edges are present in the original graph G. Since both the numerator and denominator are positive numbers, the Eq. (A.1) 1) can be transformed into:
Σ (Tp xzg)²+ + Σ (Inew zp)
Σ MrES
x
Σ (p.9)EE
(op xg)²²
Σ x knew); (A.2) Er
(P.2)EE
PES
which can be obviously simplified to:
Σ
(Inew xx))
Σ
nnww
Σ
(Ip xz)²²
(A.3)
ES
ErES
(PIO)ES
We move the term with the new node to the same side of the equation and rearrange the Eq. (A.3), and we obtain:
Exres(Enon zx)
Einolees (2p (Ap- xz)²
(A.4)
22200
Epes z²
Note that RQ(S) E Diees (00-8a)²
we denote A(vnew) En -0,)²
and then
Epes 22
x2
obtain the Theorem in Section 3.1.2.
A.2 The proof of Corollary
Proof. Similar to the proof of Theorem 1, for a new nodeset Unew, E Vnews let be the subgraph after the addition of Vnew and it also needs to satisfy RQ(S') > RQ(S)) which is expanded as:
Eppare =gg²² + +e EVeem, (v,es(Enew. xz)² EiS)EEE
(Enewr,
Inewn )2
Ev,es x? E Evann, EVeew x2 nnow:
(A.5)
Einnes - x2)²
Σv,Es x?
where Eearo, EVnew, Ev.es ("new )2 represents the of the feature difference between the newly added nodeset Vnew and the connecting edge of the subgraph S. Σ Einew, EVnex &new, represents the internal of the newly added nodeset Vnew- Similar the proof of Theorem 1, this formula can be transformed into:
Σ
(Inew, - x² + Σ
(Enew, Knew, )2
Σ
(xp-2g) 2zg²
Σ
EYnow I
Enemy
Unewi E Vnewg UYES
(i.))EEnm
N,ES
(p.g)EE
(A.6)
Rearranging the Eq. (A.6), we get:
Exnre EVan Vnew Ev.es(Enew 22 + E(Ss)EE
(Inew: Enew; )2
Σ E(pg)ee -rg)²
Exnom E Vnew x2 Frew
Ev.es x2
(A.7)
which is the same as Corollary in Section 3.1.2.
15

---

A.3 The proof of Theorem 2
Proof. We define the nodeset V has the highest Amar (Vne)) and Amer (Vnew) > RQ(S). To prove that the V is contained in the optimal subgraph S", we give the proof by contradiction. Assume that the negation of the statement is true, so there does not exist View in S We will discuss the issues based two scenarios.
In the first scenario, we assume that the current subgraph S is already the optimal solution. Accord- ing to Corollary 1, we find that adding V new can increase (Q(S) since it satisfies the condition Aaa (Vnew) RQ) Therefore,
obvious that the current set S is not the optimal solution.
In the other scenario, we assume that there is another nodeset View (Veem N = (), which together with the current subgraph S + Vnew forms the optimal solution. According the corollary have
Ev. new
Es(Enew xz)² + -EEvr, (Tnew: Inewy) )²
Amax (V* (Vnew)
(A.8)
Σ Vnn. Fnw
and it satisfies:
Zingeelle-aa.) En.es 27
Amaz ( Vnew)
Ev Vhew Eol 2rr)
+xr)
(#now) Bnews )²
(A.9)
Amar (Vhew)
Evyow
Zhow
To continue with the proof, we present a useful inequality first.
Lemma (Dan's Favorite Inequality). Let 01, m..; On and bi, .i.. Un be positive numbers. Then
min a,
E a
a
max
(A.10)
by
Σ, b
bi
Proof. Here we give a classical proof, we have
Σa a = Σ
Σa=Ebb
bi
a₂ b
Σ
b;
max
4j by
max a3 )
ΣEr bi.
(A.11)
b,
So.
Σ ai
aj
S max
(A.12)
Σ 6;
b,¹
One can similarly prove
Σ a
4 D3
min
(A.13)
Σ bb
Combining Lemma 3 and Eq. (A.9), we obtain the following inequality.
Amax (View)
E(pa)ee(Ip - x² + Ev.... Es(Thew xx)² +I (Inow, - x'new )2 Ex,es 27 + Ev.... I'aen""
Vv Vin CS-S-
(A.14)
Analyzing the above equation reveals that the right side of the formula is RQ(") new + S). That is, for any View. adding View still makes RQ(V + S) increasing according to the Corollary 1, which contradicts the assumption that RQ(V
year + S) is the optimal solution.
Aman (Vrew)
max A(Vnew), and Amaz Vnew P9
Cimaz(Vneni (Vnew) RQ(S).
(A.15)
However, identifying the maximum Amer Amen(Vun)) from the Vnew C G - S still a NP-hard problem. We consider relaxing any nodesets V to any connected nodesets Ve new- Any nodesets can be decomposed into several disconnected smaller nodesets, that is, V'e Ve1 new
122 U... Since there are no edges connecting these nodesets, the following decomposition formula can be derived.
16

---

Vvann Es(Fnew xr)²²= Σ Vot
Es(a -zp) +EE+e Es =xp) ....
vez
DEyier (Irew; Fnnewy) )² E8
(I
new;
- -I
)2 Ee
(2
new;
x
news )² + +...
Vham
Evicu Fnew 2 ==
x0 2
Vel
Ve2
(A.16)
Considering the condition that maximizes the Rayleigh quotient of any connected
new!
Eve mew
Es(onew
- xx,) EE
(I
- I newy
)²
new
A Amax (View) Amar (V new!
(A.17)
Σ
new
According to Lemma 3, Eq. (A.14) is still satisfied. Therefore, we derive that V new is contained in the optimal solution.
B The Pseudocode of MRQSampler Algorithm
We give the pseudocode of MRQSampler in Algorithm 1, which illustrates the algorithm for finding the subgraph with the target node that maximizes the Rayleigh Quotient, In section 3.1.2, we give diagram of the sampling range of 2-hop and 1-hop cases. For the completeness of the theory, give the complete algorithm for arbitrary k-hop cases in the pseudocode form.
For node r, we focus on the k-hop spanning tree T with r as the root node. And for any node u in T except for the root r, A maxl [v] is defined as:
(x:
xp)² + Eunnee (x: - xT)²
A Amaz [u] = max SCT.
(A.18)
Eigs x7
where S C To are the connected subgraphs the subtree T, with v as the root node, and is the parent node of the node v. As described in the Section 3.1.2. we break the computation into two steps:
Stage 1: Compute and store the maximum A Amaz [t] for subtrees rooted with each node v except for the r, which is performed by recursively calling the function GetMaxDeltas in Algorithm 1.
Stage Use these memorized results to compute the optimal Rayleigh Quotient RQ and its corresponding subgraph, which is performed by the function MRQSampler.
In Stage 1, the first thing we need to know is how we get Amaz [v]. Similar to the analysis of the Theorem 2, we can also obtain the condition that the nodeset is in the final optimal subgraph with largest [v]]
A Amax [Unewc]
max {Fnow)
A(Dnew)) and Amaz [Unew) A(v).
(A.19)
This process is similar to finding the maximum RQ. In other words, we keep retrieving the un- selected descendants with maximum Amazl [e and then check whether its Amaz [nnww] exceeds the current A[c). If it does, the inclusion of the optimal subgraph with it can increase the current (n). otherwise, can no longer be increased by adding any descendants and the maximum Amaz reached.
17

---

algorithm MRQSampler
Globals: r the original root of the tree; i arbitrary node; x the node i's feature; T. an array that stores the child nodes node i the tree; 8(i] < -- mmmo ds bi N, 7]: an array of structures that stores the maximum moz( achievable by any connected subgraph V containing the node i within the subtree rooted at and a, b, stores the numerator and denominator of Amaz [i]. N is the optimal selected nodes, is the inferior candidates,
1: # The function for computing Amoz [i] in STAGE
2: Input: f- root of the current subtree; p t parent of
3: Output: 8[t] <- structure array with mox [i] and correlated variables
4: function GETMAxDELTAS(U,
5:
N, I, < 0
Optimal selected nodes, Inferior candidates, Un-selected children of D. Candidates queue
6:
Q SortedSet ()
7:
a, (zlu =lpl)2
Initialize the numerator of the maximum A Amaz
8:
b, x
> Initialize the denominator of the maximum Amaz [u] Initialize the maximum Ama [v] for current sub-tree
9:
Amaz [v] a./b,
10:
for in ['u] do
8|c| < GetMaxDeltas(c, v)
Result of the subtree rooted with child
12:
Q. Qinnsert ([c,
U. (.insert(c)
14:
while Q.size 0 do
15:
C, 8|c] (pog_sargest() & Retrieve the candidate e with Amar [c] and structure 8(c)
16:
if max [0] (a, oc) + 8(c].b)) then Optimization criterion of A maz
17:
Break
U. remove if exist(c)
19:
Og t a, + 0
Update the maximum Amaz [u]
by f b, + 8cc.bb
21:
Amar 2|] + ab/by
22:
Qinnerrt I)
Activate the inferior candidates
23:
Ninnset N)
24:
I+
The remaining candidates the inferior
25:
(U)
b Add the un-selected children to the inferior set
8(u) + (Amaz [t], av, by, N,
Memorise the results
27:
return 8(u]
28:
29: # The main function of MRQSampler in STAGE II
30: Input: r- the original root of the tree (target sampling node)
31: Output: AQQmax +- maximum RQ; N <- optimal sampling nodeset
32: function MRQSAMPLER(r)
33:
aRQ +0
> Initialize the numerator of the RQmaz b Initialize the denominator of the RQ RQmaz
34:
bRQ + x/r]2
35:
RQ aan/bbn,
36:
Q --SSoredSSe ()
37:
for in [ do
38:
8|c] - GetMaxDellasscc.n
b. Recursively calculate the Amar in Stage
39:
Q Qinssrtt ((c, [[c])
40:
while Q.size + do
41:
8fc] 1apop_largest()
42:
RQ > (aRQ + o(c).a))/(brr + b(cc.bb) then Optimization criterion of the RQ
43:
Break
44:
aRQ -- anq + 8|c].0c
D Update the result
45:
bRQ bRQ blc].b.
46:
RQ + aRQ/ /bQQ
Qinnsert (Ō .)
Activate the inferior candidates b Update the selected nodeset
48:
Ninnser (8[c].N)
49:
return [RQmaar: N}
18

---

For ease of computation, we store the optimal Amar(e) [e] by its numerator de and denominator by (line 7-9). Next, we recursively calculate the result for each subtree rooted by every child of the current root (line 11). To simplify complexity in the following steps, we store these results in sorted container (e-g. binary search tree) Q (line 12). Next, we keep retrieving the subgraph with the highest Amaz[c] from Q and compute whether the A mazz [c] increases after adding it to the current solution (line 15) According to Eq. (A.19), we obtain the optimal A Amer [t] for the current subtree with root when the candidate cannot make Amaz(? [u] larger. Moreover, sets from subtrees that are not optimal for e may still be selected at higher levels. Therefore, we also need to keep track of those inferior subtrees and re-consider them when other subtrees that connect to them merged into the solution (line 24-25). Note that subtrees in I are only considered as candidates when the optimal subgraph with root is selected at a higher layer (the "activation" in line 22).
In Stage 2, the overall routine for obtaining RQyan is very similar to the one in GetMaxDel 00 except that the initial value is set to RQ ग|ল since the root has no parent node. In other words, the algorithmic logic of the two functions in Stage and Stage is similar. Stage 2 can be regarded special case of Stage 1 without parent node, utilizing the implementation of memoization from Stage 1.
Assuming that the k-hop spanning tree T has K nodes, the time complexity of Algorithm O(KlogK), since we will at worst examine each edge and sort them. Notice that the computation is irrelevant between different nodes, it can be further accelerated by simultaneously processing multiple nodes. In practice, we observe that the optimal choice of k- k-hop is typically <= 2, and thus the recursive computation can be unrolled thus further improving the efficiency.
C Implementation Details
Node-level Baselines. GCN (Graph Convolutional Network [24]) leverages convolution operations to propagate information from nodes to their neighbors, SGC (Simple Graph Convolution [56]) further simplifies GCN by removing non-linearities and collapsing weight matrices between consecutive layers to improve efficiency. GIN (Graph Isomorphism Network [57]) captures graph structures by generating identical embeddings for structurally identical graphs, ensuring invariance to node label permutationns GraphSAGE (Graph Sample and AggregatE [16]) generates node embeddings through sampling and aggregating features from local neighborhoods, supporting inductive learning. GAT (Graph Attention Networks [52]) incorporates an attention mechanism to assign varying importance levels to different nodes during neighborhood aggregation, focusing on the most informative parts. PNA (Principle Neighbor Aggregation [7]) combines multiple aggregators with degree-scalet for effective neighborhood aggregation. AMNet (Adaptive Multi-frequence Graph Neural Network [5]) captures both low and high-frequency signals by stacking multiple BernNets [18], adaptively combining signals of different frequencies. BWGNN (Beta Wavelet Graph Neural Network [50]) employs the Beta kernel to tackle higher frequency anomalies with flexible band-pass filters.
Graph-level Baselines. OCGIN [66] is one-class graph-level anomaly detector based on graph isomorphism network that addresses performance fluctuations in general graph classification methods. OCGTL [46] combines deep one-class classification with graph transformation learning. GlocalKD learns rich global and local normal pattern information by joint distillation of graph and node representations. iGAD [63] employs an attribute-aware GNN and a substructure-aware deep random walk kernel to achieve dual-discriminative capability for anomalous attributes and substructures. GmapAD [44] proposes an explainable graph mapping approach that projects graphs into a latent space for effective anomaly detection. ROGNN [11] identifies differences in the spectral energy distributions between anomalous and normal graphs.
Multi-task Baselines. GraphPrompt [37] learns different task specispe prompt vectors for each task, which are added to the graph-level representations by element-wing multiplication. All-in-One [48] treats an extra subgraph as a prompt and merges it with the original graph by cross links.
Hardware Specifications. Our experiments were mainly carried out on Linux server equipped with dual AMD EPYC 7763 64-core CPU processor, 256GB RAM, and an NVIDIA RTX 4090 GPU with 24GB memory. Some of the extremely large datasets, such as T-Finance, and certain memory-intensive baselines were implemented on the NVIDIA 8* A800 GPUs. We mark the results as OOT (Out of Time) if the model training exceeds days. For some large datasets, methods with GPU memory requirements exceeding 80GB were marked as OOM (Out of Memory), such iGAD
19

---

and GmapAD, and were attempted to be run on the CPU. iGAD was successfully completed, but GmapAD still encountered a timeout issue,
Metrics. We utilize three widely used metrics to evaluate the performance of all methods: F1- macro, AUROC and AUPRC. Fl-macro is the unweighted mean of the Fl-scores for the two classes, disregarding the imbalance ratio between normal and anomaly labels. AUROC represents the area under the Receiver Operating Characteristic Curve. AUPRC represents the area under the Precision-Redd Recall Curve, emphasizing model performance imbalanced datasets by focusing on the trade-off between precision and recall.
Hyperparameter Tuning. As described in Section 3.2, we first unsupervised model based on GraphMAE [21] to learn the general representation of the input features. The hyperparameters for this step are the default values from the official GraphMAE implementation, with 50 training epochs. Table lists all the hyperparameters used in our model along with their corresponding search spaces. During training, we conduct grid search to identify the model that achieves the highest AUROC score on the validation set. Finally, we evaluate the selected model on the test sets and report the performance metrics.
Table 7: Hyperparameters search space for UniGAD.
Hyperparameter
Distribution
learning rate activation
Range 10-2)
[ReLU, LeakyReLU, Tanh] [16,32,64]
hidden dimension
MRQSampler tree depth
[1,2]
GraphStitch Network layer epochs
[1,2,]]x2
[100, 200, 300, 400, 500]
D Limitations and Impacts
Since the GNN encoder we employ mainly focuses on node-level features, the learned representations may not be perfectly suited for edge and graph level tasks. Therefore, we leave the exploration of how integrate multiple tasks in the pre- pre-training phase to future work. As a generalized graph anomaly detection model, our work will be helpful in detecting classical graph anomaly applications, such as financial fraud, cybercrime, etc. On the other hand, an error in the recognition result may put normal groups behaviors into anomalies, causing disturbance for the normal users in the graph network.
E Additional Experimental Results
We also provide the results of all experiments under the F1-macro and AUPRC evaluation metrics. Similar to the arrangement in the main text, for F1-macro, we show the results multi-level performance comparison under F1-macro metric in Table and Table 9. The results of Zero-Shot Comparison under F1-macro metric are Table 10 and Table 11. For AUPRC, we show the results of multi-level performance comparison under AUPRC metric in Table 12 and Table 13. The results of Zero-Shot Comparison under AUPRC metric are in Table 14 and Table 15. It can be observed from these tables that similar conclusions can be drawn as with the AUROC results in Section UniGAD demonstrates superior performance across most datasets, regardless of whether unified or zero-shot performance evaluated.
20

---

Table 8: Comparison unified performance (F1-macro) at both node and edge levels with different single-level methods, multi-task methods, and proposed method.
Datacet
Reddit
Weiho
Amazon
Yelp
Tolokers Node
Questiion Node
T- T-Finance
Task devel
Node
Edge
Node
Edge
Node
Edge
Node
Edge
Edge
Edge
Nude
Edge
GCN
35.5
92.50
62.45
42.54
SS. 64
48,74
T0.61
GiN
27.22
92.01
72.21
18.75
To. 40
$9.30
7G.81
OnpbSAGE
28, 28.50
55.05
64.05
63. 71
51.07
62.
SGC
12.42
90,
57.43
54.48
48.59
58,
Node-level
87.966
56
02.68
47.28
T0
50.50
12.
46.38
32.889
AMNet
50.04
80.07
D9.75
19.90
74.31
BWGNN
42.25
$6.94
00.49
64.89
63.43
$2.00
80.57
OCNE
42.97
92.112
47.99
42.32
05.15
58,
/
79.07
GINE
35.90
91.54
47.82
133.1
G0.04
066.93
73. 40
SAGEE
11.94
60.50
57.79
57.55 8T
66 65.05
7.4.15
67. 12
SOCE
41.08
50.97
45.
56.50
1/2.177
61.51
Edgellevel
GATE
40.65
90.53
64.00
49.90
61.43
62.80
68. 76
BernE
39:85
02.15
69.
59.70
61.53
07:52
63.
PNAE
192.201
64.38
05.74
87.04
06.27
91.72
Multi-mak
GraphProenge.U
All-in-OnisS
49.12
50.64
51.23
48.65
40.90
14.43
42.94
50.17
47.90
33.29
OUT
OCTT
OCT
UniGAD (Ours)
UniGAD
66.70
69.30
58.23
76
64.65
68.00
67.77
84:02
$4.08
UniGAD BWG
54.08
51.41
96.35
94.22
91.33
73.59
70.16
63. 57
68. 15
66.20
59.45
57.54
89.75
84.90
Table Comparison of unified performance (F1-macro) both node and graph levels with different single-level methods, multi-task methods, and our proposed method.
EM-MN
BM-MT
MUTAG
MNISTO
MNISTI Graph
T-Group Graph
Graph
Graph
Nude
Graph
Gruph
Node
Graph
Node
52.56
GraphSAGE
50.77
45.04
50.29
BemnNet
86,
24.25
19.27
$0.88
BWGNN
82:48
75.22
76.19
92.75
51.81
J02
Gngb-level
12.50
12.50
25.30
87.78
95.04
46.01
GrupAD RQUNN
46.
46. 15
46.15
75, AS
0OM
00M
00M
95.
02.02
97.
60.39
03:42
06.00
48.01
Multicack
GrapPPrempt-U
All-in-One-I1
38.95
34.98
12.80
45.35
21.24
57.48
20:38
12. 86
47.02
41.96
12.88
48.01
38.71
83.08
25.71
80.66
O00
52.39
0CT
80.49
OCT
28.25
00T
50.77
OCT
49, 49.78
O0T
UnGAAD GCN
90.20
67
02:17
61.88
77.04
(Oun)
UnGGAD BWG
87.91
55.80
$3.70
61.07
82.53
51.36
93.07
80.19
99 99
85.54
00.00
90
60
78.00
Table 10: Zero-shot transferability (F1-macro) node and edge levels.
Methods
Reddit
Weibo
Amazon
Yelp
Tolokers
Questions >E.
T-Finance
N >R
N
>R
>N
N
>R
E
>N
N >R
>N
E ON
GraphPramgt-U
29.87
41.00
47.06
42.19
33.22
44.77
41.44
47.17
43.72
47.60
30.00
OOT
OOT
All-in-One-U
2.38
19:17
36.82
51.58
12.84
23.6
12.23
46.04
33.39
49.83
33.08
49.54
OOT
OUT
UniGAD GUN
50.61
50 58
94.44
94. 29
56.70
61.88
51.29
53.36
61.14
57.14
52.01
02.26
80.85
GB:21
UaiGAD BWG
50.04
92.11
93.62
66.47
85.07
63.69
71.10
55.61
53.44
63.35
87.61
Table 11: Zero-shot transferability (F1-macro) at node and graph levels.
BM-MN
BM-MS
BM-MT
MUTAG
MNISTO
T-Group
Methods
N-GG
G-N
N-G
G-
N-G
G-N
N
G-
N-G
G-
N-+G
G-N
GruphPrompt-U
12.86
31.88
20.59
42.78
16.01
43.85
42.15
27.13
26.16
26.75
48,47
43.64
All-in-One-U
12.86
34.98
46.01
41.25
12.86
22.74
39.53
48.50
OCT
O0T
OOT
O0T
UniGAD- GCN
53.43
83.88
57.84
74.63
52.75
78
54.87
39.89
77.47
65.78
63.75
66.47
49.22
UniGAD BWG
46.15
59.27
46.15
52.27
46.22
39.54
45.58
66.32
44.56
60.81
63.92
48.24
21

---

Table 12: Comparison of unified performance (AUPRC) at both node and edge levels with different
single-level methods, multi-task methods, and proposed method.
Dafaset Task-level
Reddit
Welbo
Amazon
Yelp
Tolokers Node
Questions Node
T-
F-Finance
Node
Edge
Node
Edge
Node
Edge
Node
Edge
Edge
Edge
Node
Edge
GCN
5.84
91. .55
36,2 21
20,
4.5 65
12:20
70.51
GIN
5,89
511 :2:
76.74
351.
39-71
12.79
61.79
GriphSAGI
5.64
84: .97
55:55 56
46
48.90
16.72
19.62
Node-level
BeraNet
460
43.04
27:34
11:57
23.07
AMNet
7.52
88
87.26
46.
43:22
14.39
74.73
BWGNNN
6.4
92 8l
58.67
50.32
40.44
16.21
84.54
OCNE
4.68
91. 15
16.59
22,
$5.15
27.83
/
62 12
GINE
5.01
91. 244
25..08
126 226
461005
27.34
/
122 02.01
SAGEE
5.31
07
20 20.28
34.
60.44
500 40
18
SGCE
3.00
14.54
17.47
51.41
30.
Edge
33,
291.83
4.51
16.03
28.
37.61
54.
AME
5.00
87 (03
39.07
32. 46
$3.53
$1.88
43, 43.70
BWE
5:26
33.00
38.83
35.33
14-42
42.72
Multi cask
GraphiPronpe- U
All-in-One-U
3.80
4.07
2,33
2.82
17
0.41
7.51
5.18
0.62
1.02
3.13
2.64
46.10
12.41
13.40
13.63
22.19
21.64
32.16
33.52
1.25
2.57
4.09
5.22
OOT
00T
OOT
OCT
UniGAD
UaiGAD GCN
9.73
5.82
96
95.
38.06
15.55
61.
40.90
16.35
$4.05
15.58
15.90
75.30
69 99.90
UnKiAD BWG
3.29
87.28
42.01
24.65
56,80
17.85
85.34
74.37
Table 13: Comparison of unified performance (AUPRC) at both node and graph levels with different
single-level methods, multi-task methods, and our proposed method.
Dataset lask-tevel
BM-MN
HM-MS
BM-MI
MUIAG
MNISTOO Graph
MNNSEI
TE-Group
Node
Graph
Node
Graph
Node
Graph
Node
Gruph
Node
Node
Graph
Node
Graph
OCN
81.82
23
$3.12
17
91.20
8.78
GIN
52.80
32. 23.44
36, 36,08
$1.91
87 27.602
87.01
1.65
GraphS.AGE
49.17
32.01
34.55
80..20
59. 51.
99.94
3.70
SGC
61.73
11.24
36. 82
34. 32
82.00
82.06
3.98
Node-level
GAT
64.33
40.89
42: 44.25
82.44
99. 80
99:90
6.56
BernNet
58.11
58.37 38
72.
90
00 90
13.51
PNA
72:16
56.35 32
58.07
70. 16
98 18
05 50
1.00
BWGNN
01.85
70.10
78.53
84.53
89.50
90 00
16.30
OCGIN
89:40
68. 80
41.14
31 02
12.50
18.09
/
4.46
OCXTT
76.72
16.
41.35
39.5 33-87
9.54
11.27
7
4.30
Gagh-Sevel
GL
7.71
9.05
17.99
25.01
8.56
13:40
/
2.51
iGAD
68:38
74.57
$3.86
91.00
01.70
07.08
7
5.02
GrupAD
14.20
14.20
15.29
60.33 .6
DOM
00M
7
00M
RQGNN
99.32
97.60
99.33
911.27
97.02
98.20
7,98
Multi task
GraphPrompt-U
All Aul-za-One- Un
57.75
63.87
15.15
8.58
35,75
26.10 15
14.78
9.16
27.18
25.15
21.23
14.85
70:41
0.85
333.09
60.20
62,80
00T
36.25
OCT
83:30
000
DOT
5:97
00T
1.06
O00
4.25
UniGAD
URIGAD-GCM GCN
99.63
73:54
90.00 91
96.39
99.73
90.99
86.00
91.00 06
95.94
01.58
06.08
05:30
21.55
44.05
(Ous)
UnGAD BWG
91.19
23.80
$5.81
30.89
$4.93
14.74
87.15
92.00
99.99
97.92
99.99
98.60
31.31
00.64
Table 14: Zero-shot transferability (AUPRC) node and edge levels.
Metbods
Reddit
E-N
N-E
Welho
N-E
Amazon
E-N
N-E
Yelp
N-E
Tolokers
Questions N-E
E-N
N-E
T-Finaace
E-N
GraphPromptLI
2,80
3.00
7.33
16.50
2.37
9.83
19.00
13.26
34.14
21.59
5.49
3.57
O0T
OCT
All-in-One-U
239
4.15
5.37
6.53
10:20
3.13
14.43
13.49
31.77
21.79
4.11
3.04
00T
OOT
UniGAD GCN
388
93.35
40.51
6.76
60.67
69.74
UaiGAD BWG
3.11
100
86.17
93.21
28.07
78.50
35.99
55.04
51.26
46.36
13.89
5.80
70.61
81.02
Table 15: Zero-shot transferability (AUPRC) at node and graph levels.
BM-MN
BM-MS
BM-MT
MUTAG N-+G
MNISTI N-G
T-Group
Methods
N-G
G-N
N-G
G-N
N-G
G-N
G-N
G-
N-+G
G-
GraphPrompt
13.87
48.25
14.51
26.88
13.17
26.90
63.44
46.84
5.95
22.23
5.04
1.15
All-in-One-U
78.62
73.54
9.24
32.03
11.94
24.38
28.38
9.60
OOT
OOT
OOT
OCT
UniGAD- GCN
31.05
86.00
42.41
81.74
24.26
60.50
10.63
52.67
9.22
25.59
35.02
6.97
UniGAD BWG
21.25
54.09
26.62
31.35
16.86
38.62
38.64
27.56
7.84
32.94
27.15
4.30
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We confirm that the main claims made in the abstract and introduction aceu- rately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of work in Appendix D.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
23

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide complete proof of our theoretical results (Theorem 1, Corollary 1, Theorem 2) in Appendix A.I.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide link to the code in the abstract and include detailed implementa- tion information in Appendix C to enhance reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
24

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We make the code of our model and newly released T-Group dataset open- sourced at https: /eses///anoon http////nnoomm/s.//m 4open www.sceeeeeeeceeeeeeo htt/////UnAAAAASSS Other datasets used only publicly available datasets as stated in Section 4.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
mublic/guidee/Codeuuubiss wwt.ssssssnnnniiiiiiioiiooliiiil for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //nips. wttp//ublccggggcddeoe httgg/dddde/ooeeuumiiiiin /Co///obbeeeeeeee SondeSuumisssione cwmminssionPpp ssionpolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: Please refer to Appendix C for the experiment implementation details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
25

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
All of our experimental results come from the mean randomized trials.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please refer Appendix C for the computation resources.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics /t////nurip... httpe//wwwpppppppt//ac/cccccieee
26

---

Answer:
[Yes]
Justification: We confirmed the research conducted in the paper conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: Please refer to Appendix D for the relative discussion.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring
27

---

that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer:
[Yes]
Justification: We properly credit all referenced baseline works and datasets in Section 4 and Appendix C.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. cow com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide the code via the anonymous link in the abstract, which will be open-sourced under the MIT license. Comprehensive documentation is included with the assets to ensure case of use and understanding.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
28

---

14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
29


Reviews:
[{"review_id": "spNPV8JNLZ", "reviewer": "Reviewer_NHz6", "summary": "This paper presents a novel framework for detecting anomalies at node, edge, and graph levels within graph-structured data. The authors introduce the Maximum Rayleigh Quotient Subgraph Sampler (MRQSampler) to transform multi-level tasks into graph-level tasks by sampling subgraphs with high spectral energy, thus preserving significant anomaly information. Additionally, the GraphStitch Network integrates information across different levels and balances multi-level training objectives. Experimental results demonstrate the promising results on different GAD tasks.", "questions": "Please refer to weakness.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper studies an interesting and underexplored problem that unifies multiple-level GAD tasks in a single framework. The proposed unification strategy is interesting. The paper is overall nicely presented and easy to follow. A comprehensive set of baseline methods are considered in the evaluation.", "weaknesses": "1. AUPR is a popular complementary metric to AUROC, commonly used by the majority of recent GAD papers. It is important for readers to understand the performance of the model with a focus on the anomaly class. Considering that the improvement on some datasets is marginal, discussing the model's performance under AUPR would be beneficial.\n\n2. It seems that on the edge prediction task for some datasets, the baselines achieve the top performance. I am wondering how this method would perform on datasets with a very high degree, like the T-Finance dataset. In addition, it would be interesting to see how this method performs on large-scale datasets to understand its robustness better.\n\n3.  Some of the experiments are marked as OOM) and OOT, especially for those prompt-based methods on larger graphs. While I understand these methods can be resource-intensive, a limit of 24GB max GPU RAM or 1 day wall time might be insufficient for adequately evaluating such methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer’s thorough and constructive feedback on our paper.\n\n### **Q1: AUPRC as a complementary metric**\nWe acknowledge the importance of AUPRC as a complementary metric to AUROC and F1-macro, especially for anomaly detection with imbalanced labels. In light of your suggestion, we have now included AUPRC results in our evaluation. We show the all results in the supplementary PDF Table 1-4.\n\nBased on the results, we observe that UniGAD's performance under the AUPRC metric aligns closely with its AUROC and Macro-F1 scores. UniGAD achieves state-of-the-art performance across nearly all scenarios.\n\n### **Q2: Results on T-Finance, large-scale datasets, and edge prediction**\nWe appreciate the reviewer's interest in high-degree and large-scale datasets. We've conducted additional experiments on the high-degree T-Finance dataset and highlighted our results on another large-scale dataset T-Group.\n\n||AUROC||F1-macro||AUPRC||\n|-|-|-|-|-|-|-\n|Model|Node|Edge|Node|Edge|Node|Edge|\n|GCN/GCNE|96.03|87.63|80.57|79.07|84.94|62.12|\n|GIN/GINE|90.70|79.05|70.61|73.40|70.81|52.01|\n|GraphSAGE/SAGEE|86.43|77.14|76.81|67.12|61.79|18.79|\n|SGC/SGCE|78.16|83.01|62.63|68.76|19.62|33.47|\n|GAT/GATE|74.21|83.91|56.69|65.75|30.35|54.13|\n|BernNet/BernE|90.60|87.80|69.11|63.16|54.70|45.01|\n|PNA/PNAE|92.37|86.19|70.52|57.45|67.65|43.70|\n|AMNet/AME|68.17|92.27|27.69|70.88|23.07|68.14|\n|BWGNN/BWE|93.58|69.01|74.31|64.51|74.73|30.22|\n|UniGAD-GCN|93.93|93.75|84.92|84.08|75.30|69.90|\n|UniGAD-BWGNN|**96.49**|**94.32**|**89.75**|**84.90**|**85.34**|**74.37**|\n\nThe above results on T-Finance indicate that UniGAD outperforms all baseline methods in both node-level and edge-level GAD tasks. Regarding two prompt-based multi-task approaches, GraphPrompt and All-in-One, the preprocessing phase proved to be excessively time-consuming and consume substantial memory, failing to complete within a 2-day timeframe. The primary reason for this inefficiency is the need to generate a distinct induced graph for each edge, which dramatically increases computational demands and memory usage on the high-degree T-Finance dataset.\n\n**Large-scale Dataset Performance Analysis:** We highlight our results on the T-Finance (39,357 nodes, 21,222,543 edges) and T-Group dataset (37,402 graphs, 11,015,616 nodes, 93,367,082 edges) as reported in the manuscript. Our method demonstrated superior performance in both node-level, edge-level and graph-level anomaly detection on this large-scale, real-world dataset. It surpasses two recent powerful GAD baselines: the node-level method BWGNN and the graph-level method RQGNN. This highlights the versatility and effectiveness of our method across different levels of objects, particularly in handling large-scale scenarios.\n\n**Edge Prediction Results Analysis:** For edge prediction, UniGAD achieves the best performance on 4 out of 7 datasets for AUROC and 6 out of 7 datasets on F1-macro. While our method is designed for a multi-task setting, the performance on a single level might be slightly compromised to ensure the model performs well across all tasks.\n\n### **Q3: OOT and OOM under limited resources**\nWe acknowledge the reviewer's concern about the OOM and OOT issues for some baselines on large graphs. We agree that the limit of 24GB GPU RAM and 1-day running time might be insufficient for these resource-intensive methods. To address this, we borrowed A800 80G GPUs for additional experiments during the rebuttal period and extended the time limit to 2 days. \n\n For reference, the datasets having OOM and OOT issues are:\n|Dataset|Graph_num|Edge_num|Node_num|\n|-|-|-|-\n|Amazon|1|8,847,096|11,944|\n|Yelp|1|7,739,912|45,954|\n|MNIST0|70,000|41,334,380|4,939,668|\n|MNIST1|70,000|41,334,380|4,939,668|\n|T-Group|37,402|93,367,082|11,015,616| \n\nFor prompt-based multi-task methods previously facing OOT issues, we employed faster GPUs, extended time limits, and optimized the pre-processing code. These improvements enabled GraphPrompt to complete experiments on all datasets except T-finance. However, All-in-One remained slower than GraphPrompt and failed to finish MNIST0/1 and T-Group within 2 days. This is because All-in-One requires learning token structures through pairwise relationships and calculating dot products between prompt tokens and input graph nodes, which is computationally intensive. In contrast, GraphPrompt simply incorporates a learnable vector into graph pooling via element-wise multiplication, enabling faster processing. The updated results are as follows:\n\n||GraphPrompt(AUROC/AUPRC/F1-macro)|All-in-One|UniGAD(Ours)\n|-|-|-|-|\n|Amazon(Node)|50.01/6.62/40.93|56.11/1.02/48.67|**97.84/87.29/91.33**\n|Amazon(Edge)|50.96/2.64/35.95|54.8/3.13/2.45|**92.18/42.01/73.59**\n|Yelp(Node)|49.83/12.41/40.90|49.77/46.10/14.43|**86.23/61.00/74.57**\n|Yelp(Edge)|49.56/13.63/42.94|49.13/13.49/46.29|**79.05/40.90/66.66**\n|MNIST0(Node)|81.16/82.89/80.66|OOT|**99.99/99.99/99.99**\n|MNIST0(Graph)|83.88/36.25/52.39|OOT|**99.61/97.92/95.54**\n|T-Group(Node)|47.40/1.06/50.77|OOT|**96.19/31.31/68.69**\n|T-Group(Graph)|50.81/2.36/49.78|OOT|**88.78/55.64/78.09**\n\nTwo graph-level anomaly detection methods, iGAD and GmapAD, initially encountered OOM issues. Using 80GB of GPU RAM, iGAD successfully ran on the MNIST0 and MNIST1 datasets. However, T-Group exceeded memory limits due to the large number of nodes per graph. We switched the processing to CPU, which was completed in 2 days. Conversely, GmapAD could operate within the 80GB memory limit on the A800 GPU but still timed out even with a 2-day limit. We discovered that the final SVM predictor in GmapAD becomes significantly slower with a large number of training samples.\n||iGAD(AUROC/AUPRC/F1-macro)|UniGAD(Ours)\n|-|-|-|\n|MNIST0|98.93/94.79/87.73|**99.61/97.92/95.54**\n|MNIST1|99.50/97.98/95.04|**99.98/98.60/97.60**\n|T-Group|64.44/5.92/46.51|**88.78/55.64/78.09**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ShgPWlYndF", "reviewer": "Reviewer_ji27", "summary": "This article presents an anomaly detection model, UniGAD, designed to be applicable across different levels including nodes, edges, and whole graphs. Leveraging the relationship between the Rayleigh quotient and anomaly degree, as described in Lemma 1, the authors have developed a novel subgraph sampling algorithm, MRQSampler. This algorithm recursively adds nodes that maximize the Rayleigh quotient, ensuring the subgraph contains the most anomalous information. Consequently, node-level and edge-level tasks are converted into graph-level tasks for unified processing. Additionally, the authors introduce the innovative GraphStitch Network, which jointly considers multi-level representations. Extensive experimental results substantiate the effectiveness of UniGAD.", "questions": "1. How efficient is MRQSampler? (execution time and memory requirements), can it be processed in parallel on Gpus\n2. Can UniGAD be unsupervised? I think this is more realistic (collecting abnormal samples during the training phase is difficult)", "limitations": "No limitations need to discuss", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The task of unifying different levels of anomaly detection on graphs is challenging and very novel.\n2. Complete theoretical proof, explaining the motivation of MRQSampler.\n3. Complete experiment proves the effectiveness of UniGAD", "weaknesses": "1. The graph signal $x$ in all proofs is treated as a vector, which implies that the node feature is a scalar. However, in practice, graph node features are often vectors. This discrepancy is not clearly addressed by the authors.\n\n2. The MRQSampler appears to be a recursive algorithm rather than a dynamic programming (DP) algorithm, as suggested by Algorithm 1 in the appendix. This distinction impacts the efficiency of the proposed method.\n\n3. UniGAD is a supervised algorithm, yet the baseline comparisons in the experiment include unsupervised algorithms (OCGIN,OCGTL). This raises concerns about the fairness and validity of the experimental comparisons.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### **W1: The discrepancy of scalar node feature in proofs and vector node feature in practice.**\nThank you for highlighting this discrepancy. In theoretical derivations, we followed the established foundations of BWGNN and RQGNN, which consider single-dimensional features in their proofs. This simplification enhances mathematical tractability and facilitates clearer theoretical analysis. In fact, the primary focus of spectral graph theory and graph signal processing is on one-dimensional vectors. \n\nHowever, we recognize that real-world scenarios typically involve multi-dimensional feature vectors. To address this, we developed two approaches:\n- Pre-processing:  Normalize all feature dimensions and then take the norm (1-norm in our case) to obtain a composite feature for each node, allowing us to identify the most anomalous nodes based on this comprehensive feature.\n- Post-processing: Identify anomalous nodes in each feature dimension separately, and then take the union or combination of these node sets across all dimensions. \n\nWe implemented both methods in our code, and our early experiments showed similar results between the two approaches. For efficiency, we used the pre-processing approach in UniGAD. This method ensures that the computational complexity does not increase with the number of feature dimensions, making it more scalable for high-dimensional data. We will clarify this point in the manuscript to provide a more comprehensive understanding of the rationale behind our design choices.\n\n### **W2. MRQSampler: DP or Recursive**\nThe MRQSampler algorithm utilizes principles of dynamic programming (DP), which may not be immediately apparent and thus requires clarification. The key distinction between DP and recursive or divide-and-conquer approaches is the use of memoization, i.e., storing the results of subproblems to avoid redundant computations in future calculations.\n\nIn the MRQSampler, as described in Algorithm 1 (lines 18-29), the process incorporates a bottom-up calculation where the maximum $\\Delta$ values of sub-trees are computed starting from the leaves up to the root. It is important to note that sub-trees not selected in initial iterations at lower levels might still be reconsidered in subsequent iterations at higher levels. Therefore, the maximum $\\Delta$ for these sub-trees, referred to as 'inferior candidates' in the algorithm, could be computed and stored during their first evaluation. These stored values are then reused in later computations, which is a hallmark of DP.\n\nTo better illustrate this process, we restructure Algorithm 1 into the following two stages:\n- **Stage 1:** Compute and store the maximum $\\Delta$ for each sub-tree recursively, starting from the leaf nodes and moving upwards to the root. This stage has a computational complexity of $\\mathcal{O}(N \\log N)$.\n- **Stage 2:** Initiate from the root node and iteratively select the sub-tree with the highest $\\Delta$ from the available candidates, incorporating it into the resultant sub-graph until the $\\Delta$ of the selected sub-tree exceeds the current RQ. As new sub-trees are added to the resultant set, their child sub-trees are also added to the pool of candidates. The complexity of this stage is $\\mathcal{O}(N)$. Without memoization, this stage would necessitate recalculations of the maximum $\\Delta$ for these sub-trees. \n\nThe implementation of memoization in the DP paradigm to store and reuse the results of sub-tasks effectively reduces redundant computations and optimizes the overall complexity of the algorithm to $\\mathcal{O}(N \\log N)$. We will make the necessary revisions to the manuscript to better explain this algorithm.\n\n### **Q1. Time and memory efficiency for MRQSampler**\nFollowing your suggestion, we have conducted a comprehensive evaluation of both time and space efficiency on the large-scale, real-world T-Group dataset. In Figure 1(a), we have specifically highlighted the time consumption of the MRQSampler module separately from other parts of UniGAD, about 37% of the total time. The MRQSampler offers a key efficiency advantage: it requires only once computation to generate and record subgraphs, which can be reused across multiple trials without recalculation when tuning parameters. Besides, we find that k-hop subgraph sampling also takes a lot of time in the prompt-based method. \n\nMoreover, the subgraph sampling process for different nodes can be parallelized, as each node's sampling is independent. This parallelization potential further enhances the scalability of our approach, particularly for large-scale graphs. We are actively working on optimizing MRQSampler for GPU acceleration but it presents some challenges. Currently, we offer a CPU-based parallel version of the code. \n\n### **W3/Q2: Can UniGAD be Unsupervised?**\nOCGIN and OCGTL are widely used unsupervised graph-level GAD baselines, but some supervised methods also compared with them (e.g., GmapAD and RQGNN). We agree that such comparison is not rigor and will highlight this in our analysis. \n\nUniGAD is also designed with label scarcity in mind. It focuses on scenarios with missing labels at different levels, exploring how labels from one level can compensate for another. While UniGAD requires labels, it exhibits zero-shot transferability---applying learned knowledge to unseen scenarios without requiring labels in a secific type.\n\nMoreover, the MRQSampler can be considered as an independent module in our framework. It leverages the correlation between spectral domain Rayleigh quotients and anomaly degrees to identify the most anomalous subgraphs. Essentially, it functions as a graph algorithm that can theoretically identify the most anomalous node-centered subgraphs in an unsupervised manner. This characteristic makes the MRQSampler adaptable to other unsupervised methods beyond the scope of UniGAD. We view this as an area of independent interest and anticipate its potential applications in unsupervised GAD methods.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "y9WqQhalGg", "reviewer": "Reviewer_ymWJ", "summary": "The paper introduces UniGAD, a unified framework for multi-level graph anomaly detection, capable of identifying anomalies at the node, edge, and graph levels. Key contributions include the Maximum Rayleigh Quotient Subgraph Sampler (MRQSampler), which optimizes subgraphs to maximize significant anomaly information, and the GraphStitch Network, which facilitates information sharing across different levels while maintaining effectiveness. Experiments on 13 datasets show that UniGAD outperforms existing methods and demonstrates strong zero-shot transferability. Overall, UniGAD leverages spectral properties and multi-task learning to achieve state-of-the-art performance in graph anomaly detection.", "questions": "Is it possible to provide All-in-One and GraphPrompt code for multi-task versions?", "limitations": "None", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1.Innovative Unified Framework: UniGAD is the first framework to jointly detect anomalies at the node, edge, and graph levels, addressing a significant gap in current GAD research. The integration of multiple anomaly detection tasks into a single model enhances its versatility and applicability across various scenarios.\n\n2.Advanced Methodologies: The Maximum Rayleigh Quotient Subgraph Sampler (MRQSampler) and the GraphStitch Network are key innovations. MRQSampler maximizes spectral energy to preserve critical anomaly information, while the GraphStitch Network facilitates information sharing across different levels, harmonizing conflicting training goals and maintaining the effectiveness of individual tasks.\n\n3.Robust Performance and Transferability: UniGAD is comprehensively evaluated on 13 diverse datasets, consistently outperforming existing methods. It demonstrates robust zero-shot transferability, effectively transferring knowledge across different GAD tasks without prior exposure to specific anomalies, showcasing its robustness and generalizability.\n\n4.Strong Theoretical and Practical Foundations: The approach is supported by solid theoretical foundations, with proofs provided for the optimal conditions of MRQSampler. Additionally, the dynamic programming algorithm ensures computational efficiency, making the method scalable to large datasets. The availability of the implementation code promotes transparency and reproducibility of the results, facilitating further research and application.", "weaknesses": "1.The paper modifies existing methods like All-in-One and GraphPrompt into multi-task versions for comparison. However, All-in-One already supports node, edge, and graph tasks, and GraphPrompt supports node and graph tasks. A more straightforward approach would have been to directly apply these methods to the relevant anomaly detection tasks without modifications to see their effectiveness.\n\n2.The paper mentions that All-in-One and GraphPrompt often run out of time (OOT), but it is unclear whether this refers to the prompt tuning stage or the pre-training stage. Since both methods are known for their relatively fast prompt tuning, clarifying this distinction is crucial for understanding their performance limitations.\n\n3.The paper lacks comparisons of temporal and spatial performance metrics. Including an analysis of the time and space efficiency of UniGAD compared to other methods would provide a more comprehensive evaluation of its practicality for large-scale and real-time applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments to our work! Below are our responses.\n\n### **Q1: Modification of All-in-One and GraphPrompt**\n\nWe would like to clarify that we did not alter the core methodologies of GraphPrompt and All-in-One. Our modifications were limited to the data preprocessing component to accommodate the simultaneous handling of multiple object types (node/edge or node/graph) within induced graphs. The original implementations of these methods support processing only one type of graph object at a time, either by handling one object type exclusively or by processing different types sequentially (i.e., one type for pre-training and another type for prompt tuning). They do not inherently support scenarios where multiple object types are input/output simultaneously.\n\n**Code Access**: We have included the modified versions of All-in-One and GraphPrompt in our source code, which is accessible through the link provided in our manuscript for further reference and verification.\n\n### **Q2: OOT issues for All-in-One and GraphPrompt**\n\nThe time limitation mentioned refers specifically to the preprocess stage and prompt tuning stage. During the pre-training stage, both these methods and UniGAD use GraphMAE, and the time consumption is similar and short. The reasons for significant time consumption of All-in-One and GraphPrompt are:\n- Large amount of induced graphs in pre-processing: The number of induced graphs becomes the sum of node and edge numbers rather than just the number of graphs. This results in tens of millions of induced k-hop subgraphs in some datasets, causing substantial pre-processing time.\n- Large amount of training samples in prompt tuning: Although both methods are known for their fast prompt tuning, it only held for few-shot settings (e.g., 5 or 10 samples for tuning). However, we use the fully supervised setting and have much more training samples, which significantly increased the data required for tuning.\n- Redundant computation: Induced graphs between neighboring nodes inevitably contain duplicated nodes. However, the prompt-based approach treats these duplicates as distinct nodes to be computed separately in different graphs, significantly increasing the computational load. In contrast, UniGAD employs a more efficient approach. It first obtains the representation of each node through a pre-trained GNN encoder. Then, using a sampler and pooling architecture, it derives the embeddings for other levels of objects (edges/graphs). The framework optimizes the process by eliminating the need to generate and process numerous induced subgraphs, instead leveraging the original graph structure and minimizing repetitive calculations.\n\nTo address the OOT issue, we employ faster GPUs, extended time limits to 2 days, and optimized the pre-processing code. The updated results are as follows:\n||GraphPrompt(AUROC/AUPRC/F1-macro)|All-in-One|UniGAD(Ours)\n|-|-|-|-|\n|Amazon(Node)|50.01/6.62/40.93|56.11/1.02/48.67|**97.84/87.29/91.33**\n|Amazon(Edge)|50.96/2.64/35.95|54.8/3.13/2.45|**92.18/42.01/73.59**\n|Yelp(Node)|49.83/12.41/40.90|49.77/46.10/14.43|**86.23/61.00/74.57**\n|Yelp(Edge)|49.56/13.63/42.94|49.13/13.49/46.29|**79.05/40.90/66.66**\n|MNIST0(Node)|81.16/82.89/80.66|OOT|**99.99/99.99/99.99**\n|MNIST0(Graph)|83.88/36.25/52.39|OOT|**99.61/97.92/95.54**\n|T-Group(Node)|47.40/1.06/50.77|OOT|**96.19/31.31/68.69**\n|T-Group(Graph)|50.81/2.36/49.78|OOT|**88.78/55.64/78.09**\n\nWe found that GraphPrompt can complete all datasets in our additional experiments, while All-in-One still fails to finish on the MNIST0/1 and T-Group datasets. This difference in performance can be attributed to their underlying mechanisms. Based on the All-in-One source code, the model must learn the token structure represented by pairwise relationships among tokens. It calculates the dot product between prompt tokens and input graph nodes to determine link establishment, which is computationally intensive. In contrast, GraphPrompt employs a simpler and faster approach, incorporating a learnable vector integrated into graph pooling through element-wise multiplication.\n\n### **Q3: Time and space efficiency of UniGAD**\nThank you for your suggestion. We have incorporated both time and space efficiency metrics into our evaluation, using the large-scale, real-world T-Group dataset (37,402 graphs, 93,367,082 edges, and 11,015,616 nodes). We used the same batch size for all models to ensure a fair comparison.\n\nTo provide a more straightforward comparison between single-task and multi-task baselines, we calculated the average, minimum, and maximum for combinations of single-task node-level and graph-level models, and compare these with multi-task models. The results, as shown in Figure 1(a) in the supplementary PDF, indicate that in terms of execution time, our method is slower than the combination of the fastest single-level models but faster than the average of the combination.\n\nRegarding peak memory usage, Figure 1(b) demonstrates that graph-level models consume significantly more memory than node-level models. Our method maintains memory consumption comparable to node-level models and substantially lower than both graph-level GAD models and prompt-based methods.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mBBH9GQJTK", "reviewer": "Reviewer_ky9h", "summary": "Traditional graph anomaly detection focus on single type of graph object (e.g., node, edge, graph). To address this, this paper introduces the first unified framework (UniGAD) for detecting anomalies at the node, edge, and graph levels jointly. The authors propose two core modules, MRQSampler and GraphStitch, to address the challenge of unifying multi-level task formats and unifying multi-level task training, respectively.  Moreover, the authors theoretically prove that MRQSampler maximizes the accumulated spectral energy of subgraphs (i.e., the Rayleigh quotient) to preserve the most significant anomaly information. Extensive experiments demonstrate that UniGAD surpasses existing single-task GAD methods and graph prompt-based approaches for multiple tasks, offering robust zero-shot task transferability.", "questions": "Refer to weaknesses, please explain the difference in more detail and check the typos.", "limitations": "The authors addressed limitations and societal impacts in the conclusion and appendices.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Originality: \n1. This paper focus on the gap of multi-level graph neural network at the node, edge, and graph levels, which is an important problem.  In many scenarios/data, the labels of these different graph objects are often relevant, but this is always overlooked.\n2. The problem formulation in Definition 2.1 is novel in graph learning, which is feasible to have labels at one or more levels, which makes the framework broadly applicable and provides strong zero-shot capabilities.\n3. The authors designed a theoretically guaranteed graph sampling algorithm that uses the Maximum Rayleigh Quotient to sample the most anomalous subgraphs. This approach ensures sampling nodes that contain anomalous information, preventing the anomalous information from being smoothed out. \n4. The authors implement multi-level task information transfer through a module called GraphStitch. Since multi-task in graph learning research remains rare, this network design is very interesting and prospective.\n\nQuality:\nThe paper exhibits a high level of technical quality, with theoretical proofs and rigorous dynamic programming algorithms provided for the effectiveness of the MRQSampler in maximizing the accumulated spectral energy of subgraphs. \nThe paper proposes a robust framework that achieves the unified multi-level tasks through a pre-trained GNN encoder, MRQsampler, and GraphStitch network.\nThe experiments look solid, including 13 datasets with single-graph datasets and multi-graph datasets and 17 SOTA model with node-level models, edge-level models, graph-level models and multi-task models.\n\nClarity:\nThe paper is well-written and clearly presents its contributions. \n\nSignificance:\nThe framework of UniGAD further improves the effect of graph anomaly detection and has strong zero-shot capability. Besides, it also promote the development of multi-task learning in the graph learning domain.", "weaknesses": "A substantive assessment of the weaknesses of the paper. Focus on constructive and actionable insights on how the work could improve towards its stated goals. Be specific, and avoid generic remarks. For example, if you believe the contribution lacks novelty, provide references and an explanation as evidence; if you believe experiments are insufficient, explain why and exactly what is missing, etc. Please keep in mind that the rebuttal period is not necessarily enough to run new experiments. As a result, asking for new results is rather unrealistic.\n\nOverall, this paper is technically solid and novel. In Page 8, the authors mention that the other multi-task method, like GraphPrompt and All-in-One, often run out of time (OOT) and calculate redundantly. What is it that makes UniGAD avoid this? Are each node’s representations calculated only once? Please explain the difference in more detail. \n\nMinors: in Additional Experimental Results, the caption of the table 8 and table 9 should be F1-macro?  Otherwise this will repeat table 1,2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are greatful for your helpful comments! Below are our responses.\n\n### **Q1: How UniGAD avoid Redundant calculation**\nPrompt-based methods for handling multiple objects convert all objects into induced graphs during pre-processing. This approach results in the number of induced graphs to be processed equaling the sum of nodes, edges, and graphs, potentially reaching tens of millions in some datasets. Each induced graph contains numerous nodes, often appearing repeatedly across different induced graphs, leading to significant computational redundancy.\n\nIn contrast, UniGAD employs a more efficient approach. It first obtains the representation of each node through a pre-trained GNN encoder. Then, using a sampler and pooling architecture, it derives the embeddings for other levels of objects (edges/graphs). The framework optimizes the process by eliminating the need to generate and process numerous induced subgraphs, instead leveraging the original graph structure and minimizing repetitive calculations.\n\n### **Q2: Minor Corrections**\nThank you for bringing this to our attention. The caption of Tables 8 and 9 should be F1-macro. We will thoroughly examine the manuscript for any other minor inconsistencies.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear Reviewers,

We are deeply grateful for your constructive and insightful feedback. We sincerely appreciate your recognition of our contributions to the field of graph anomaly detection. The reviewers have highlighted several key strengths of our work, including UniGAD's unique capability to unify node, edge, and graph-level tasks, the advanced methodologies introduced through MRQSampler and GraphStitch Network, robust empirical performance with strong zero-shot transferability, solid theoretical foundations, and clear presentation. These aspects collectively address a significant gap and promote multi-task learning in current GAD research. We have carefully considered each comment and provided detailed, point-by-point responses to address all the feedback received, further strengthening our manuscript.

The additional experiments carried out during the rebuttal period are summarized as follows:
- **AUPRC:** All results related to the additional AUPRC metric are presented in supplementary PDF Tables 1-4 and discussed in Q1 of the NHz6 rebuttal.
- **High-degree dataset T-Finance:** The new results for high-degree T-finance dataset are included in Q2 of the NHz6 rebuttal.
- **Time and space evaluation:** Experiments assessing time and space efficiency on the extensive T-Group dataset are depicted in Figure 1 of the supplementary PDF and are discussed in Q1 of ji27 and Q3 of ymWJ rebuttal.
- **OOM and OOT Issues:** The results under the extended time and space constraints to address out-of-memory and out-of-time issues are detailed in Q3 of NHz6 and Q2 of ymWJ.

**We attached a one-page PDF summarizing the additional experimental results.** For detailed discussion, please refer to our reviewer-specific feedback.

Meta-review: All reviewers are positive about this paper. I agree with them that this paper has proposed an effective graph anomaly detection framework to jointly address anomalies at the node, edge, and graph levels. This research direction is important and still at its early stage. Overall, this paper presents a solid work and is potentially useful to the community. I am confident that this paper should be accepted.
Decision: Accept (poster)