Open-Set Graph Anomaly Detection via Normal Structure Regularisation
Authors: Qizhou Wang
Guansong Pang
Mahsa Salehi
Xiaokun Xia
Christopher Leckie
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Anomaly Detection
Outlier Detection
Social Network Analysis
Graph Mining
Primary area: learning on graphs and other geometries & topologies
TL;DR: In this work, we propose a novel open-set GAD approach, namely Normal Structure Regularisation (NSReg), to achieve generalised detection ability to unseen anomalies, while maintaining its effectiveness on detecting seen anomalies.

Abstract: This paper considers an important Graph Anomaly Detection (GAD) task, namely open-set GAD, which aims to train a detection model using a small number of normal and anomaly nodes (referred to as *seen anomalies*) to detect both seen anomalies and *unseen anomalies* (*i.e*., anomalies that cannot be illustrated the training anomalies). Those labelled training data provide crucial prior knowledge about abnormalities for GAD models, enabling substantially reduced detection errors. However, current supervised GAD methods tend to over-emphasise fitting the seen anomalies, leading to many errors of detecting the unseen anomalies as normal nodes. Further, existing open-set AD models were introduced to handle Euclidean data, failing to effectively capture discriminative features from graph structure and node attributes for GAD. In this work, we propose a novel open-set GAD approach, namely $\underline{n}ormal$ $\underline{s}tructure$ $\underline{reg}ularisation$ (**NSReg**), to achieve generalised detection ability to unseen anomalies, while maintaining its effectiveness on detecting seen anomalies. The key idea in NSReg is to introduce a regularisation term that enforces the learning of compact, semantically-rich representations of normal nodes based on their structural relations to other nodes. When being optimised with supervised anomaly detection losses, the regularisation term helps incorporate strong normality into the modelling, and thus, it effectively avoids over-fitting the seen anomalies and learns a better normality decision boundary, largely reducing the false negatives of detecting unseen anomalies as normal. Extensive empirical results on seven real-world datasets show that NSReg significantly outperforms state-of-the-art competing methods by at least 14% AUC-ROC on the unseen anomaly classes and by 10% AUC-ROC on all anomaly classes. Code and datasets are available at https://github.com/mala-lab/NSReg.

Published as a conference paper at ICLR 2025
OPEN-SET GRAPH ANOMALY DETECTION VIA NORMAL STRUCTURE REGULARISATION
Qizhou Wang'; Guansong Pang"!
Mahsa Mahsa Salehi', Xiaokun Xia², Christopher Leckie!
'The University of Melbourne
2 Singapore Management University
3 Monash University
*The University of Tokyo
{mi ke. wwng, ca lecki leckie)uue (enunnmmllll meebbedd..au, gspang@smu. edu.
mahsa. sale ehi emonahhshhhhheeomooooooooocahhhe edu, xia. xiackuneippu ip
ABSTRACT
This paper considers important Graph Anomaly Detection (GAD) task, namely open-set GAD, which aims to train detection model using a small number of normal and anomaly nodes (referred to seen anomalies) to detect both seen anomalies and umseen anomalies (i.e., anomalies that cannot be illustrated the training anomalies). Those labelled training data provide crucial prior knowledge about abnormalities for GAD models, enabling substantially reduced detection er- rors. However, current supervised GAD methods tend ever-emphasise fitting the seen anomalies, leading to many errors of detecting the unseen anomalies as normal nodes. Further, existing open-set AD models were introduced to handle Euclidean data, failing to effectively capture discriminative features from graph structure and node attributes for GAD. In this work, we propose a novel open-set GAD approach, namely normal structure regularisation (NSReg). to achieve gen- eralised detection ability to unseen anomalies, while maintaining its effectiveness detecting anomalies. The key idea in NSReg is introduce regularisa- tion term that enforces the learning of compact, semantically representations of normal nodes based on their structural relations to other nodes. When being op- timised with supervised anomaly detection losses, the regularisation term helps in- corporate strong normality into the modelling. and thus, it effectively avoids over- fitting the seen anomalies and learns a better normality decision boundary, largely reducing the false negatives of detecting unseen anomalies as normal. Extensive empirical results on seven real-world datasets show that NSReg significantly out- performs state-of-the-arr competing methods by at least 14% AUC-ROC on the unseen anomaly classes and by 10% AUC-ROC on all anomaly classes. Code and datasets are available at https://github.ccm coommmlaa hat.a/ocoommmmaaaaaa/seee
INTRODUCTION
Detection of anomalous nodes in graph is crucial task in the context of Graph Anomaly Detection (GAD) (Akoglu al., 2015; Ma et al., 2021; Qiao et al., 2024a). Its popularity has been growing in recent years due to its wide range of real-world applications, such as detection of malicious users in social networks, illegal transactions have been numerous GAD methods introduced (Ding et al., 2019; Liu et al., 2021; Ma et al., 2021; Qiao et al., 2024a), with the majority them designed as unsupervised approaches. However, they are often associated with high detection errors due to the lack of knowledge about anomalies.
financial networks, and faults sensor networks. There
There has been growing interest in supervised Anomaly Detection (AD) methods (Jiang et al., 2023; Pang et al., 2023; Tang al., 2022; Pang et al., 2019; 2021b) because they are able to utilise labelled anomaly data to substantially reduce the high detection errors of unsupervised approaches. Such methods assume the availability of a limited number of labelled anomalies, which is usually feasible
Work initiated while at Monash University 1 "orresponning author: Guansong Pang (gspangesmm eaapang@smu..mm edu. sg)

---

Published as a conference paper at ICLR 2025
to obtain in real-world applications and can be utilised to enable Despite their generally superior performance, these methods prove less effective in open-set AD where training models with labelled anomalies (referred to as seen anomalies) fails to adequately represent anomalies at inference time, particularly in the context of newly emerging types/classes of anomalies that substantially different from those seen in training (i.e., unseen anomalies). This is because such methods often concentrate soiely on modelling abnormal patterns derived from labelled anomalies, thus exhibiting poor generalisation to the unseen anomalies, i.e., many unseen anomalies are detected as normal, as shown in Figure (a-b). Further, they are mostly designed for handling Euclidean data like image and tabular data (Pang et al., 2019; 2023), thereby overlooking valuable discriminative information on the structure and node attributes in graph data for GAD.
supervision.
To address these issues, this paper focuses on the practical yet under-explored problem of open-set GAD, aiming to enhance the generalisation for both seen and unseen anomaly nodes by leverag- ing small set of labelled seen anomaly nodes. To this end, we propose a novel open-set GAD approach, namely normal structure regularisation (NSReg). leverage the rich normal graph in- formation embedded in the labelled nodes. The key idea in NSReg is introduce a regulari- sation term that enforces the learning of com- pact, semantically-rich representations of normal nodes based on their structural relations to other nodes. When being optimised with supervised AD losses, the regularisation term incorporates strong normality into the modelling, and thus, effectively avoids overfitting the seen anomalies, while learning better normality decision bound- ary. This helps substantially reduce the errors of detecting unseen anomalies as normal.
Ansanalis
Ciocs Asuzalia
BCB
BWGNN
(6) NSRog (ouns)
ABR--ROCA -9333
AUC-ROCa - B75
ALT--RDGa GW ALI--dd:
ALrG-OCaaae 0770
All anso
aghe Pneegooeenn
ALC-ROCA 6033
ADC-ROCe - 6:35
ALT RDC 4 WT
ALTOROC leaee 0617
AUC mID -0,51
ADC-80Cem 0.096
Figure 1: Visualisation of node representa- tions with anomaly score contour lines of three supervised GAD models: baseline classifier Binary Cross-Entropy (BCE), recent state-of- the-art BWGNN (Tang et al., 2022), and our proposed NSReg, on two real-world datasets: Photo and ogbn-proteins. trained using a limited number of seen anoma- lies and normal nodes. BCE and BWGNN overly focus on the decision boundary between the seen anomalies and normal nodes, whereas NSReg mitigates overlitting to the seen anoma- lies, resulting in more generalised detection of seen and unseen anomalies.
In particular, to capture those semantically-rie normal structure relations, NSReg differentiates the labelled normal nodes that are connected in their local neighbourhood from those that are not. This is done by predicting three types of commal-node-oremtee
The models are
relation prediction, includ- ing: connected normal nodes, unconnected nor- mal nodes, and unconnected normal nodes to un- labelled nodes. We show theoretically that our regularisation module prioritises establishing dis- tinct node representations based on their structural relationships with the normal class, rather than grounded information. As a result, it effectively reinforces the structural normality of the graph in the representation space and enforces more stringent decision boundary for the normal class, enabling better separability of the unseen anomaly nodes from the normal nodes, as shown in Figure I(c). Moreover, NSReg a plug-and-play module, which can be integrated various supervised GAD learning approaches to enhance their generalisability to unseen anomalies. It worth noting that NSReg is designed to enhance the generalisation of supervised GAD to un- seen anomalies by leveraging discriminative structural information derived from small number of labelled nodes. It is not intended for unsupervised GAD, where label information is unavailable, and models designed for the unsupervised setting are prone to different issues, e.g., the failure to capture anomaly patterns of interest or high false positives. In summary, our main contributions are as follows:
attempting to predict these anomalies without
plugin module into
We study an under-explored problem of GAD, namely open-set GAD, and validate the feasibility of leveraging graph structural normality to regularise representation learning in supervised GAD, resulting in effective mitigation of the overfitting on the seen anomalies.
2

---

Published as a conference paper at ICLR 2025
We propose NSReg that regularises supervised GAD models by differentiating normal- node-oriented relations. It tackles the problem by enforcing better separation between un- seen anomalies and normal nodes while retaining seen anomaly detection performance.
NSReg is a plug-and-play regularisation term that can be applied to enhance the generali- sation of different supervised GAD methods.
We show through extensive empirical studies that NSReg significantly outperforms all com- peting methods by at least 14% AUC-ROC on the unseen anomaly classes and by 10% AUC-ROC on all anomaly classes.
RELATED WORK
Graph Anomaly Detection. GAD methods are usually designed unsupervised learning to bypass the reliance of labelled data (Ma et al., 2021; 1; Jiang et al., 2023). Earlier shallow methods (Peng et al., 2018; Perozzi & Akoglu, 2016; Gao et al., 2010; Li al., 2017; Yu al., 2018) leverage various heuristics to detect anomalies. Recent GAD methods predominantly utilise graph neural networks (GNNs) (Wu al., 2020) and have demonstrated superior performance due to their strong repre- sentation learning capacity. There are numerous unsupervised GNN-based GAD methods proposed (Ding et al., 2019; Li et al., 2019; Zhao et al., 2020; Ding et al., 202 Wang et al., 2021b; Liu et al., 2021: Xu al., 2022: Qiao & Pang, 2024; Hc et al., 2024). However, these methods are not trained using real anomalies and have proven to be ineffective when their heuristic optimisation objective mismatches the actual anomaly patterns. To leverage noomaly-specifff prior knowledge, supervised learning that utilises labelled anomalies ( (Wang et al., 2021a; Tang et al., 2022; Chai et al., 2022; Dou et al., 2020; Huang al., 2022; Wang al., 2021c; Gao et al., 2023; Wang et al., 2023b; Chen et al., 2024; Zhuo et al., 2024) and learning schemes such as meta learning and transfer learning have also been explored for GAD (Ding et al., 2021b; 2022a; Zhou al., 2023; Wang et al., 2023a; Niu et al., 2024). Nevertheless, these methods are prone to overfitting the small number of labelled anomaly nodes and do not implement effective regularisation to ensure the generalisation on the unseen anomalies. Note that open-set GAD differs fundamentally from graph OOD) detection (Wu et al., 2023; Gong Sun, 2024; Lin et al., 2024), where the focus is on identifying novel classes that deviate from in-distribution data but are not necessarily anomalous. In contrast, open-set GAD aims to distinguish normal from anomalous data, treating both seen and unseen anomaly classes as single anomaly class during evaluation.
Towards Supervised Anomaly Detection. Although numerous AD methods have been proposed (Chandola et al., 2009; Pang et al., 2021a), most of them (Zenati et al., 2018; Park et al., 2020; Roth et al., 2022) adopt optimisation objectives that focus on representation learning and are indi- rect for anomaly scoring. More recent works (Sohn al., 2021; Ruff et al., 2020; Pang al., 2019; 2023; 2021b; Zhao & Hryniewicki, 2018) leverage a small number of labelled anomalies to per- form optimisation and anomaly scoring in an end-to-end pipeline, significantly improving detection performance. However, such methods are originally designed for non-structured data and cannot explore structural information when directly applied for GAD.
Imbalanced Node Classification. Another closely related line of research is imbalanced classifi- cation (Chawla et al., 2002; Zhou & Liu, 2006; Johnson & Khoshgoftaar, 2019), which is a long- standing challenge in mitigating the class imbalance in the training data. A variety of approaches (Ding et al., 2022b; Wang al., 2021d; Qu et al., 2021; Zhao et al., 2021; Park et al., 2022) have been proposed to mitigate class imbalance in the training graph data to avoid overfitting the majority classes. However, these methods only assume a fixed number of known classes and do not consider the potential unseen classes at inference time. As result, they fail to generalise unseen anomaly classes in open-set GAD.
3 OUR PROPOSED APPROACH
3.1 PROBLEM STATEMENT
We consider open-set GAD attributed graphs. Let G EV,E, be attributed graph with a node set V, an edge set & and a feature matrix X, which contains significantly fewer anomalous nodes Vú, than normal nodes V,, In open-set GAD, during training, the labelled training nodes ytrsin
3

---

Published as a conference paper at ICLR 2025
Ancenaly Soire
Ingot grapha Ø
CaD y
Overall Loss
Relatien Labelling
CAD
R
Effeet of Extaa
ALNER
Effect Cao
Jateamn
Vint
Shared the hSR modkine
Jaeen
Axsp (Q
Narmaalechatan-orrinne Modelling
orinnte Relation Generation
NSR Module
An overview of our proposed approach, NSReg, illustrating the integration of the NSR module into graph anomaly detector as a plug-and-play module for regularising supervised GAD training. where red arrows indicate the "plugging points". The box with dashed border line filled in teal illustrates the decomposition of NSReg's s overall learning objective in the shared representation space Z. Here, LNSR focuses on enforcing more stringent decision boundary for the normal class, enabling better separability of the unseen anomaly nodes from the normal nodes, which is not considered by LAD.
Figure 2:
often unable illustrate all possible anomaly classes inference. For clarity, we use Vieen to denote anomaly nodes that can be illustrated by the labelled anomaly nodes (seen anomalies) and Vunseen denote the unseen anomalies, such that Va = Vaeen U UV Yunseen and Vtrain C V.seen
Our objective is to learn a scoring function ó : (g. V) - R. such that @(g u,) > OGG un), for all and Un Vn, In this paper, we consider GNN-based anomaly scoring function 6. which consists of a pipeline with two components: a graph representation learner vi V; +x): (G.V) - Z and an anomaly scoring function (2 0,)) Z + R. where O. and O,, are learnable parameters. We aim to obtain the following anomaly scoring mapping:
(G V; 0p) (G Ow),),
with the support of the labelled nodes and the graph structure. The main challenges are the unfore- seeable nature of anomalies and the risk of overfitting labelled anomaly nodes.
3.2 OVERVIEW OF NSREG
In this paper, we propose a novel open-set GAD framework, namely normal structure regularisation (NSReg), as a solution to tackle the aforementioned challenges. The key insight behind NSReg is to explicitly guide the representation learner in capturing discriminative normal structural informa- tion from the graph characterised by the labelled normal nodes, supplementing the incomplete and often biased label information provided by the labelled anomalies that represent the seen anomalies. The modelling of this structural normality effectively calibrates the normality decision boundary, enabling better generalisation the unseen anomalies, i.e., better separation between the unseen anomalies and normal nodes.
As illustrated in Figure 2, NSReg leverages novel Normal Structure Regularisation (NSR) module to enforce compact and uncluttered normal subspace in the representation space. During training, the NSR module is integrated regularising component with a supervised graph anomaly detector, both sharing the same representation learner for joint optimisation, to enable the joint learning of the structural normality and seen anomaly patterns for GAD, The general objective of NSReg can be defined as the following:
Σ LAD(SOs Wo) + + LNsu((r, Cr), @g. ON.R DEV
arg min
PER
where O2 and ONSR are the respective learnable parameters of the anomaly detection 6 and the NSR module, and CAD is the loss function of a supervised GAD model, with s, being the predicted anomaly score and y, being the ground truth. Additionally, LNSR signifies the loss function of the NSR module adjusted by the regularisation coefficient X, with qr denoting the predicted normality of relation sample r. and its normality c,- is defined by labelling function C. During inference, the representation learner th is combined with the trained anomaly scoring network 7p to form an end-to-end pipeline for detection, and the NSR module is disconnected from the representation
4

---

Published as a conference paper at ICLR 2025
learner since the normal structural information has already been learned. This simplifies the infer- ence process without introducing any additional NSR module-related runtime or resource overhead.
3.3 NORMAL STRUCTURE REGULARISATION (NSR)
The design of the NSR module, which is the core of NSReg, is motivated by the limitations of most supervised GAD methods, which are only designed to maximise separability between normal nodes and seen anomalies, but fail to provide sufficient supervision for the representation learner to effectively differentiate unseen anomaly representations from the normal class. In an open-set en- vironment, we are unable to obtain the prior knowledge of the unseen anomalies, and thus, difficult to learn the unseen anomaly patterns. Thus, NSReg takes step back and focuses on learning better normality, which would help distinguish the unseen anomalies from the normal nodes better. NSReg achieves this by modelling the normal-node wwall-ooooooiee oriented relations (i.e., fr = (v. u) v E Vn, u E V)), which is aimed enforcing a stricter definition of the normal region and recalibrating misplaced un- seen anomaly representations within the representation space. By modelling three types of normal- oriente relations discriminative task, NSReg enhances representation learning with sig- nificantly enriched normality semantics, effectively disentangling unseen anomaly nodes from nor- mal nodes in the representation space. We first provide theoretical analysis of enforcing structural normality and then detail the two core components of NSR: normal-node-orieen relation genera- tion and modelling.
Preserving Structural Normality Improves Representation Learning for GAD. We analyse the effects of enforeing structural normality the representation space and its advantages for enhanc- ing generalisation unseen anomalies. We consider mapping g (R2 Rd) - R1o.1] in the node representation space 2, which takes the representations of nodes in each relation as inputs to model their normality. The normality of the relations is defined by labelling function C, where O and indicate the lowest and the highest levels of normality, respectively. C' should satisfy that <= max(Ca) < min(C.) <= 1, where C, and C, indicate the respective set of the labels for the relations between only the normal nodes and the relations between normal and anomaly nodes respectively, emphasising a significant differentiation in the scale of normality.
Specifically, g gC JE consists of two sub-mappings: JE, a linear mapping that fuses the node representations to produce relation representations, with the option to incorporate a scaling function on these node representations; and Jc, a linear mapping with monotonic final activation function to assign normality scores based on the representation. Note that both the scaling function and activation function are required to be homeomorphic. If Z is shared with a discriminative graph anomaly detector, the normal nodes and the observed anomalies will be well separated into two isolated dense regions. Based this observation, that differentiating between these two types of relations will force any anomalous nodes, including unseen ones, to be excluded from the normal region.
demonstrate through the following proposition
Proposition 1. Consider well-trained mapping 9 that effectively distinguishes between the two types of normal-nodd--rrenteed relations within relation representation space H. derived from node representation space Z. The first type consists exclusively of relations among normal nodes, while the second type involves one normal and one anomalous node, with normality defined by some labeling function C, regardless their connectiviry. Consider the subspace of all normal nodes in Z as a connected open set 2nd the boundary of which is defined by some closed hypersurfaces M = {M,li E (1..... .....) Furthermore, let 2m denote the union of the interior of each M, C M. Given such 2, and 2m, we can obtain that z E 2, is true for all z E 2m indicating their equivalence.
The proof, along with an intuitive diagram (Figure 5), is provided in Appendix A. There are two key insights we can obtain from this proposition. First, since it is obvious that 2, is a subset of Zm. by proving their equivalence, we observe that inside the boundary of the normal subspace, no anoma- lous subspace exists, and therefore, no anomaly nodes, whether seen or unseen, are present. Second, this implies that for normal-node-orrintte relations involving anomalies to be distinguishable from relations exclusively between normal nodes, the only way to adjust the representation learner is to ensure that anomaly node resides within the normal space Z,, Therefore, enforcing structural normality will result in the displacement of misplaced anomalies from the normal subspace. These insights motivate the design of our NSR module, which is detailed below.
5

---

Published as a conference paper at ICLR 2025
Normaa--ndde-oriente Relation Generation. The relation generation module implements the la- belling function C' and oversees relation sampling, specifically tailored to integrate structural nor- mality knowledge in open-set GAD. It first samples normality, considering three types of relations, including connected normal relations ((),,,)) un- connected normal relations un)) and unconnected normal other nodes, (u,, A labelling function C' (an illustrative diagram is provided in Figure 6), which meets the requirements outlined in Proposition is then used to define their normality scores as follows:
relations and defines their
r E (n,,.,n) {(U, u)
0, u E Vtrain (v, u) E E n
C(r)
if E (m....)) = {uu, u) e, E Vtrain (v, u) E
0 if E (n,,,.)) {(1, u)
V Virain _uE V Verain (v, $ E}.
where 0 < a < is the specification of the normality of (n....)) relative to other types of relations. a = 0.8 is set by default to define a three-level normality hierarchy we want to enforce. This specification effectively embeds the homophilic assumption between the normal nodes while preserving the difference between the most related and related normal relations. We also find it unnecessary include normal seen anomaly pairs because similar information can be learned from supervised GAD objectives. Due to space limit, please refer to Appendix C.5 for details.
Normal-node-oriented Relation Modelling. This module instantiates the discriminative mapping y for normal relation modeling as a neural network, denoted F. It first generates the representations of relations by fusing the representations of their corresponding end nodes using a learnable mapping Fg. which is then fed into normality prediction network Fc to model their normality. Specifically, Fg can be defined as:
h FE ()
w)) = (zz)) WE (zz)),
(4)
where a is the sigmoid function, We E is learnable weight matrix, and is element-wise product. 2, and z, are the representations of the node in relation r. generated by the node representation learner 2/, which comprises GNN-based representation learner followed by projection network. The default GNN is a two-layer GraphS AGE (Hamilton et al., 2017) considering its good learning capacity and scalability. The relation modelling network is then optimised according to the following loss function:
LNRR = -c(c-- log (Fe(h.) + (1- -....)))o -log (o.o)))))
(5)
where c,- is the relation label subject to the labelling function C' and Fc is implemented as a learner layer followed by the Sigmoid function. This design satisfied all the conditions required for Propo- sition 1, ensuring that the normality enforced by the NSR module is accurately reflected in the shared representation space. It produces distinctive node representations in relation to those of the labelled normal nodes, thereby enforcing significantly enriched, fine-grained normality among the node representations. This enhancement directly regularises the representation learning of super- vised anomaly detectors, enabling better separation of the unseen anomaly nodes from the normal nodes.
3.4 OPEN-SET GAD USING NSREG
Training. NSReg is trained through batch gradient descent over a predefined number of iterations. At each iteration, we first sample batch of bAD training nodes V. which contains 6%D labelled normal nodes and all labelled anomaly nodes (note that the number of labelled anomalies is typically very small) for tuning the anomaly scoring network y and the representation learner vo. In addition, the normal-node- orieeter relation generation is performed to generate bySr relation samples R for optimising the NSR module and v. The overall training objective of NSReg can be formulated as:
-1
A LNsu Cr), [
arg min @Nsr
(Yvv log(Sv) + (1 (1-Yy) log (1 -S))) [v]
where the first term is a simple supervised cross-entropy- loss-p---os---seeeee anomaly detector and the second term is our NSR module. As shown in Sec. 4.1, the NSR term be also effectively combined with other supervised GAD models in the first term. During training, the GAD loss is computed initially based the first term of the objective function and is used update the parameters of

---

Published as a conference paper at ICLR 2025
the anomaly scoring network 7). Subsequently, the NSR loss be caleulated using the second term of the objective function to update the relation modelling network. Finally, the combined GAD and NSR losses are aggregated and backpropagated to update the parameters of the representation learner. A Python-style pseudocode for training is provided in the Appendix B.1.
Inference. During inference, given test node v, NSReg first generates its representation 2,, which is then scored using the trained anomaly scoring network 77: 8y G(g, v) = (V)
EXPERIMENTS
Datasets. NSReg is extensively evaluated using seven real-world attributed graph datasets. To the best of our knowledge, publicly available GAD datasets include multiple types of human- annotated natural anomaly classes. Therefore, we adapt imbalanced node classification and binary- labelled GAD datasets to define anomaly subclasses with distribution discrepancies for open-set GAD evaluation. For imbalanced node classification datasets with multiple minor classes, such as Photo, Computers, and CS (Shchur et al., 2018), we treat each minor class (those with less than 5% of total nodes) as seen anomalies, and the rest as unseen anomalies. This is consistent with the general definition of anomalies, characterised by rarity and significant difference from the majority. In the case of Yelp (Rayana & Akoglu, 2015) and T-Finance (Tang et al., 2022), two well-known GAD datasets with binary labels, we cluster the learned representations of the anomaly class to create anomaly subclasses. Three large-scale attributed graph datasets, oghn-arxiv, oghn- proteins (Hu et al., 2020), and T-Finance (Tang et al., 2022) are also adapted to evaluate NSReg at scale. More details about the datasets are presented in Appendix B.2. This approach enables thorough and realistic evaluation of GAD by incorporating real world anomalies while ensuring semantically distinct anomaly classes for creating an open-set set setting. Following previous studies (Tang et al., 2023; Qiao et al., 2024b), injected (synthetic) anomalies datasets are not utilised in our experiments given their well-known injection patterns, which are often incorporated unintentionally into the design of detection models, affecting the fairness of the evaluation.
Evaluation Protocol and Metrics. For each dataset, we treat one of the anomaly classes as the seen anomaly, with the other anomaly classes as unseen anomalies. We alternate this process for all anomaly classes, and report the results averaged over all cases. All experiments are repeated for 5 random runs. For example, the CS dataset includes 8 anomaly classes, each is treated as 'seen' in turn, resulting in 8 sub-experiments per run, with a total of 40 sub-experiments across 5 runs. The Python style code for the evaluation protocol is presented in Appendix B.3. We employ two widely used and complementary performance metrics in GAD: the Area Under Receiver Operating Characteristic Curve (AUC-ROC) and the Area Under Precision- Recall Curve (AUC-PR). In par- ticular, AUC-ROC measures both true positives and false positives, while AUC-PR summarises the precision and recall of the anomaly classes, offers a focused measure exclusively on the anomaly classes.
Competing Methods. NSReg is compared with 20 competing methods from multiple related ar- eas, including four popular unsupervised methods, eight state-of-the-art (SOTA) supervised methods and one baseline method. Specifically, DOMINANT (Ding et al., 2019), GGAN (Chen al., 2020), (Wang et al., 2021b), CoLA (Liu et al., 2021), AEGIS (Ding et al., 2021a) CONDA (Xu et al., 2022), TAM (Qiao & Pang. 2024) and ADA-GAD (He et al., 2024) are implemented as our unsupervised baselines due to their popularity and competitive performance among unsupervised GAD methods. The SOTA methods consist of recently proposed supervised anomaly detectors for Euclidean data: DevNet (Pang et al., 2019), PReNet (Pang et al., 2023), and those for graph data: DCI (Wang et al., 2021c), BWGNN (Tang et al., 2022), AMNet (Chai et al., 2022), GHRN (Gao al., 2023), CON- SISGAD (Chen et al., 2024) and PMP (Zhuo et al., 2024), and two imbalanced node classification methods as well: GraphSMOTE (Zhao et al., 2021) and GraphENS (Park et al., 2022). Addition- ally, generic hybrid bascline XGBGraph introduced by Tang et al. (2023) is also included. The classification method using binary cross-entropy (BCE) is considered as a baseline model.
Implementation Details. NSReg comprises representation learner featuring two-layer Graph- SAGE (Hamilton et al., 2017), followed by a two-layer projection network, each containing 64 hidden units per layer. NSReg is optimised using the Adam (Kingma & Ba, 2014) optimiser for 200 epochs for the Photo, Computers, and CS datasets with a learning rate of 1 x 10-3, and for 400 epochs for Yelp with learning rate of 5 10-3 due to its larger number of nodes. We set the
7

---

Published as a conference paper at ICLR 2025
Table I: AUC-ROC and AUC-PR (mean=std) for detecting all anomalies and exclusively unseen anomalies. The boldfaced are the best results. "_" denotes unavailable result due to out- -em-ofy-mmmry..
ABC ROC
AUC
Test
Method
Photo
Computes
CS
Yelp
Averge
Phomo
Computers
CS
Yelp
Avernee
DOMINANT
04234000001
057640.000 LMTT
0.00
1.503at D05
0/072600000
0.182a0 uos
0.157
0.221 (833
0. 0.106a00000
0.81-10055
0:206600018
TAM
0.56600004
0.43580.022
0.26530.066
0.408:0.005
6.02266.022
0.131:0:01
0.31820.006
135:000087
PRoNet
0667740022 0.06-00011
0156760066
0.62200004
0455440.10
0.77680003
0.363-9.011
033660100
0.3K340.015
DorNet
0.59520.079
0.60680.064
0. 0.769u0.029
0.57580.000
0.65200.466
0,22388.155
0.2848 093
0.68450.018
0.31520.027
0,373:0.073
DC1
0.77740001
0187140081
D 8355-40812
0.8840.0090
0:20600775
0455740.095
B-37-00999
063540.005
0486600011
Asuma
All
BWGNN
AMNs
0.7740:001
0.72840.006
0:01
0177160017
0.72259005
0.789
037540.005
6757
0.72760.012
0:71563021
0.59110.011
075540005
0.2372001P
0.313800066
0.30880054
6.48740000
0.611200122
0.95-00005
0.61=000066
0.67720.445
0.76410.004
01
0.36040.055
0.349=00
0.577500355
0.5m 40:000
0412=0011
DONSISGAD
0550700000
8.5560035
PMP
0:72622.013
0.718
0.71240.06
0:712400006
0447700007
0.7M9500000
0.34540023
0.455=0.000
G. ENS
0.71220005
067229.009
0.8458..277
0.572x0.011
0.20000013
6246100005
0:3195n015
0.515
0 199220000
0.320=0.012
G. SMUTH
061669041
8 0731
0:72740.014
0.139400011
0.309551143
0 0300000199
BCE
0.50720.014
0.72480.077
0.85c50.339
0.71280.017
0.77448
0.51520.011
0.75640.006
0.57640.01
0.53250.015
NSReş (Our))
0.77799015
0M57
0.75460011
0440699636
0.55941011
0
0.95500014
0432+90031
DOMINANT
0.77480005 0442
0400
0.60383.044
0.500e0000
00000
1355500002 0.109800000
0.125000000
COLA
06200004
D 011
0.391 10.015
0:557400022
6 6.166100000
0:00100:5
0.20100:111
0005510003
0.161 10.014
TAM
0621+0004
B 86 0435
0,201
067368:001
0 0.29452.006
00002000000
0.133590.000
FRRNei
0-4M200002
0.5770003
041510.00
0.52220
00041100004
0.205.p.122
0.252.0.010
0 125
0.133.0013
DerNet
0.864500000
0557790005
062140.006
0,05500005
0.00200001
014
0244400077
DCT
O.142 0.003
062928.001
0.4770.015
0.67760.009
000340:688
0:28aa
0.558a0.085
0157::000
0:27:00015
AMNa:
0,503x2.004
0.605500005
0350
0,50483.014
0.658an.006
00068800022
0.27700000
0.759g0.006
0.14220.05
0.207s0.007
GHERN
0611-0.014
D 0223900006
0.8940.001
0615-0011
0166460003
0.111-0000
0,55340.000
(1 0134-0000
0.35240024
CONSIS
0,4742000000
0,51669.049
0645
0,575a00002
1L575e0
0008820005
0.27200.99
0.16120025
0.19550.000
IMP
0.508100000
0166010007
8 8876600.05
0.70810.007
B66k-0011
0061100007
0:206-0::12
0.71410.006
013--0005
0.306-00200
G. ENS
0.518520005
066C=90099
0659
0.55642.117
000340000022
022220012
0.447-0.017
0.20750010
G. SMOOT
04641100046
0.35an.045 0161100066
0.71::6:20
066510041
00041100044
023220004 045
0.678.0.0066
0.16720015
0:200:0033
BCE
0:00
0662660015
0.00860.021
06700000077
0.29580011
0.733=00000
0177000015
0.314=0012
NSRre (Qred)
0.8%60..8
0.78218.119
0.50010.05
(L8IKHUZZ1
0,22146.867
I.41TA1U124
0,36618.821
0L196:00020
0.43488M
number of labelled anomalies to 50 and the percentage of labelled normal nodes to 5% by default. Each batch of training nodes includes all labelled anomalies and randomly sampled number of la- belled normal nodes capped at 512. Similarly, each batch of relations is capped at 512, with an equal number of samples for each relation type. The default value of is set to 0.8 and À is set to 1 for all datasets. The analysis of their sensitivity can be found in Appendix C.6, where NSReg maintains stable performance, showing its robustness to the choice of hyperparameters. Further details are provided in Appendix B.4. In our default setting, 50 anomalies are used for training along with 5% of randomly selected normal nodes, while the remaining data is reserved for evaluation.
4.1
MAIN RESULTS
GAD Performance on Both Seen and Unseen Anomalies. We first evaluate the performance of NSReg detecting all test anomalies (i.e., V \ Vtrsin, including samples of both seen and un- seen anomaly classes). The results of 3 best unsuperivsed baselines and all supervised baselines are reported in Table (the upper part). Please refer to C.I in the Appendix for complete results of all baselines. We can see that NSReg achieves consistently and significantly better performance than all competing methods across all datasets in terms of both AUC-ROC and AUC-PR. On aver- age, NSReg demonstrates a significant performance advantage over all competing methods, among which the supervised baselines prove to be considerably more effective than the unsupervised ones. Specifically, for AUC-ROC, NSReg achieves an improvement of 9.7% and 11 11.6% compared to the best and second-best competing methods, BCE and PMP, respectively. Additionally, NSReg shows 16.9% and 28.2% improvement compared to these two methods in terms of AUC-PR. The signifi- cant overall performance gain is mainly attributed to NSReg's 's strong capability of detecting unseen anomalies, while at the same time achieving effective fitting of the seen anomalies.
GAD Generalisation to Unseen Anomalies. The capability of detecting unseen anomalies in the test data (i.e., Viest U yunseen) is more indicative for evaluating a model's open-set GAD ability. As shown in Table (lower part), NSReg again achieves significantly better performance, compared to the competing methods. Notably, on average, NSReg exhibits a greater margin of improvement on the unseen anomaly classes, with 14% and 17.4% improvement over the top-2 performing com- peting methods in terms of AUC-ROC. Similarly, a 35% and 39.4% performance gain over the top-2 performing competing methods is observed for AUC-PR. The substantially enhanced performance underscores NSReg's 's strong ability in reducing the errors of detecting unseen anomalies as normal.
Data Efficiency. We investigate NSReg's 's data efficiency by varying the number of seen anoma- lies around the default setting, including 5, 15, 25, 50, and 100, in order to understand the model's capacity to handle variations in data availability. The results illustrated in Figure 3. Due to space constraints, we report results on the AUC-PR results on all test anomalies and provide the AUC-ROC results in Appendix C.7. The results show that NSReg consistently
8

---

Published as a conference paper at ICLR 2025
Table 2: Our NSR as a plugin module in supervised AD models DevNet, DCI and BWGNN.
Table 3: Large-scale GAD results. "_" denotes
unavailable result due to out-of-
Metric
Fiizacee
PReNet
0,58120.00
0611290015
0.89280.017
0.50tan.019
Merrc
ALC-ROC
AUC-PK
DaeNet
0.01--001
062230885
045440.210
Daraset
OHi
+NSK
Dift
On
+NSK
Dit:
DXT
0.566-00141
0.815:0077
0.763x 0.113
0:715500055
DeNNS
Compurers
Photo
CS
0.769
0.606
0,599
0.684
0.645
0,949
+0.180"
+0.040"
+0.055
0.84
0.223
0.284
0.340
01872
0.424
+0.183
+00056
+0.2011
ABC- ROC
(AT)
BWGNN
AMN
0,58740005
0.585:0.00
0.500000049
0667490.19
6711:0077
0777411907
0.88990.004
0.22860011
0.0230.0000
0.739:0.050
0.729
Ydl
0.675
0.684
+0.009"
0.315
+0.008
G.OOTTE
0.575a0.016
Aug.
+0,079
BCE
0,592
0,50590020
0.92260.011
0,094820012
Photo
0,772
0.865
+0:83
04422
0,577
+0.1257
NoRRe
0689HU11
0.92948.077
0.8104RU06
Compunors
CS
0.681
0.856
0.657
0.73K
+0.0011
+0.855
0.655
0447
0.635
0.501
+0.0747
-0.012
Piteeee
DecNei
0.28940000
0:304:0009
6436-0017
0.5110 140
0.32340.27
0:35480
Yelp
0.689
0,740
+0.0117
0.351
0.357
+0.036
IXI
0:266803300
0.3788L1122
BWONN
Computers
Avg. DUT.
Ploto
0.728
0.502
0.725
40.074:
10.050
+0.091"
0.133
0.348
+00156
+0.1101
40.277
AEIC-
(AII)
PR
AMNcI
GLESS
CHIRN
0,272:0.055
0,271400007
0.57680055
0,56400005
0.64480.06
0.35240005
0:72240011
0.47780051
0,52142014
0.579
10.04"
0687
0.78
+00311
G.SMOTE
0,577600077
Ydlp
BCE
0,310E0000
0.524
0.72640.034
0.500a0.115
16ff
+0.85
+0.097
Villeg
0.38641U006
0.723480020
0.75748.020
0,615401125
achieves significantly improved AUC-PR performance on the overall anomaly detection across the complete spectrum of the Photo, Computers, and CS datasets. On Yelp. NSReg either out- performs, or on par with the competing methods across the entire range for overall perfor- mance. Similar findings can be observed on detecting unseen anomalies (see Figures 9 and 10).
Photo
Compaters
NSReg as Plug-and-Play Module. This section ex- amines the effect of using the NSR module of NSReg as a plugin module to enhance three other supervised methods, referred to as NSR-enabled models. Table 2 shows the GAD performance on detecting all test anomalies, with the original BWGNN, DCI and De- vNet as the baselines. Due to the page limit, the re- sults for unseen anomalies are reported in Table 8 in Appendix C.2. We can observe that the NSR-enabled BWGNN, DCI and DevNet yield significant perfor- mance improvements across all datasets in both eval- uation metrics. In particular, DevNet by over 10% for AUC-ROC and 30% for AUC- PR. for all anomalies and unseen anomalies. Similarly, for BWGNN, its NSR-variant outperforms the original model by over 7% in terms of AUC-ROC on both test sets and more than 14% for AUC-PR. For DCI, NSR also yields similar level of performance improvement. The consistent improvement demon- strates not only the high generalisability of our proposed NSR but also the importance of enforcing structural normality in supervised GAD.
0.5
0.5
NSRag
0.2
0.2
BCE
G.SOOT
15
25 50100
15 25 50100
G.ENS
Yelp
BWGNN
DecNit
0.8
0.4
PiieNat
*-
AMNee
0.5
GHRN
-7- DXI
0.2
0.2
15 25 50100 Mytrain
15
25 50100
1
average, it improves
AUC-PR on all anomalies w.r.t. number of labelled anomalies.
Figure 3:
Large-scale GAD Performance.
We compare NSReg's 's GAD performance with supervised base- lines on all test nodes and unseen anomalies of three large-scale GAD datasets, as presented in Table 3 and Table 12 in Appendix C.4. Notably, NSReg consistently demonstrates advantageous perfor- mance, as observed in other datasets in Table 1. Moreover, NSReg exhibits superior efficiency in terms of data utilisation for large-scale GAD tasks-in it achieves effective structural regularisation and significantly improves generalisation with only 100 seen anomalies, accounting for only less than 1% of total anomalies.
4.2 ABLATION STUDY
This section empiricall explores the effectiveness and significance of enforcing our structural nor- mality within node representations by answering the following questions, with AUC-PR results reported in Table 4 and visualisations included in Figure 4. We include the results in AUC-ROC in Table 10 in Appendix C.3 due to space limits.
How important is graph structural information when enforcing normality? We answer this question by replacing the NSR module with the one-class hypersphere objective in Deep SAD (SAD) (Ruff al., 2020), which minimises the volume of normal node representations learn

---

Published as a conference paper at ICLR 2025
Figure 4: Node representations learned via various regularisation schemes on Photo.
Table 4: Our proposed NSR other regularisers in AUC-PR.
Rog.
SAD
(a...)
All unomalles
Datnet
SAD
(l.(4)
(1.(08))
NSR (dusl)
NSR (Dur)
Phono
0:20940:215
0
0,58560012
0,623400229
6600108066
Computers
0.381a0 190
049240014
0,599600244
0,51940023
0.559.0.018
CS
0.700000016
0.790400000
0,543300000
0.8594110422
08892110016
Yelp
0.17550/046
0,39220.013
07330g00075
0.399410021
0.590201004
average
0.38
0.548a9.014
0,57400034
0.605a11022
0.622411.211
NSR (sum)
Unseen anomalies
Dutaset
SAD
CL
(L
NSR (dual)
NSR (Ouns)
Mhoto
0.06
0006600000
0,13540019
0.20240049
0.22140.57
Compatrs
0.28500114
0.31840018
0,39900030
08040022
0.47748224
Sue
CS
0631
0.745000000
0,70240025
0.84+00046
0.866:9.221
Yelp
0.090000177
0.17850.011
0.152500045
0. 0.00000022
0.196:
Average
0.20040:44
0,32780.011
0,365g00000
0.409400057
0.429211:311
the normality without considering the graph structure information. Table 4 shows that NSR can significantly outperform the one-class learning SAD, highlighting the advantage of enforcing graph crtucture-iformer normality. This is because, by simply tightening the normal representations with- out considering their structural relationships, SAD may not necessarily learn discriminative unseen anomaly representations,
illustrated in Figure 4(SAD). We also found the one-class learning- based SAD is unstable due to its notorious risk model collapse, while our NSR does not have this issue due the fine-grained structural relation prediction.
Why is our proposed NSR more effective at structural regularisation? To answer this question, replace our NSR module with supervised and unsupervised contrastive learning (CL (s.) and CL (u.S.) in Table 4), which enforce similarities between nodes based on their connections. NSReg consistently outperforms both baselines on all tests for both metrics. This is because the NSR module is tailored to ensure that its enforced normality, which is better aligned with the objective of enhanced normal class modelling, is reflected in the shared representation space, therefore resulting in more stringent normal class subspace and significantly mitigating overfitting on the seen anomalies, as shown in Figure (NSR).
and thus
Can we just augment the seen anomalies to improve the generalisation on the unseen ones? This can be answered by comparing the results of NSReg with graph augmentation-basee based methods G.SMOTE and G.ENS in Table 1. NSReg significantly outperforms the two methods, suggesting that merely augmenting seen anomalies is inadequate for generalising to unseen ones. This is due to the fact that the augmented anomaly samples mainly resemble only the seen abnormalities, which may even further increase the risk of overfitting on the seen anomalies.
Can we perform the relation prediction in NSR with less types of relations? We compare NSR with its variant that is trained without the second relation Rm,,,.)) (NSR (dual) in short). Table shows that the default NSR outperforms NSR (dual) by a non-trivial margin on almost all cases. This is because R.n.u.u) is essential for defining our normality hierarchy, enabling finer granularity in relation modeling, preserving the structural differences between more closely related normal nodes and other nodes, on top of enforcing the distinction between normal and anomaly nodes.
5 CONCLUSION AND FUTURE WORK
This paper introduces a novel open-set GAD approach, Normal Structure Regularisation (NSReg), which employs a plug-and-play regularisation term enhance anomaly-discriminatie normality from graph structures, thereby reinforcing strong normality in node representations during super- vised GAD model training. By aligning node representations with their structural relationships relative to the normal nodes, NSReg establishes a stringent decision boundary for the normal class and enhances its generalisation to unseen anomalies by reducing the errors of detecting them as normal. Comprehensive empirical results show the superiority of NSReg in detecting both seen and unseen anomalies compared to 20 competing methods on several real-world graph datasets.
In terms of limitations, despite its impressive effectiveness in improving generalisation in open-set GAD, NSReg models normality only within the immediate neighbourhood of the labelled normal nodes. While this is not an issue present, real-world interactions grow more complex and larger in scale, exploring normal relations beyond immediate neighbours to gain additional information for open-set GAD may become necessary, which we leave for future work.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported in part by the ARC Centre of Excellence on Automated Decision Making and Society CE200100005.
Guansong Pang is in part supported by the Lee Kong Chian Fellowship and the Tier Academic Research Fund of the Ministry of Education, Singapore (No.
REFERENCES
Leman Akoglu, Hanghang Tong, and Danai Koutra. Graph based anomaly detection and description: survey. Data Mining and Knowledge Discovery, 29(3):626-688 6888, 2015. 1
Ziwei Chai, Siqi You, Yang Yang. Shiliang Pu, Jiarong Xu, Haoyang Cai, and Weihao Jiang. Can Abnormality be Detected by Graph Neural Networks? In Proc. IJCAI, 2022. 3,7
Varun Chandola, Arindam Banerjee, and Vipin Kumar. Anomaly detection: A survey. ACM com-
puling surveys (CSUR), 41(3):1-58, 2009, 3
Nitesh V Chawla, Kevin W Bowyer, Lawrence O Hall, and W Philip Kegelmeyer. Smote: synthetic minority over-sampling technique. Journal of Artificial Intelligence Research, 16:321-357 2002.
Nan Chen, Zemin Liu, Bryan Hooi, Bingsheng He, Rizal Fathony, Jun Hu, and Jia Chen. Consis- tency training with learnable data augmentation for graph anomaly detection with limited super- vision. In Proc. ICLR, 2024. 3,7
Zhenxing Chen, Bo Liu, Meiqing Wang, Peng Dai, Jun Lv, and Liefeng Bo. Generative adversarial attributed network anomaly detection. In Proc. CIKM, pp. 1989-1992, 2020. 7
Kaize Ding, Jundong Li, Rohit Bhanushali, and Huan Liu. Deep anomaly detection attributed networks. In Proc. SDM, pp. 594-602. SIAM, 2019.
Kaize Ding, Jundong Li, Nitin Agarwal, and Huan Liu. Inductive anomaly detection on attributed networks. In Proc. IJCAI, 2021a. 3,7
Kaize Ding, Qinghai Zhou, Hanghang Tong, and Huan Liu. Few-shot network anomaly detection via cross-network meta-learning. In Proc. WWW, pp. 2448-2456, 2021b. 3
Kaize Ding, Kai Shu, Xuan Shan, Jundong Li, and Huan Liu. Cross-domain graph anomaly detec- tion. IEEE Transactions on Neural Networks and Learning Systems, 33(6):2406225 2415, 2022a. 3
Kaize Ding, Zhe Xu, Hanghang Tong. and Huan Liu. Data augmentation for deep graph learning: A survey. SIGKDD Explor. Newsl., pp. 61-77, dec 2022b.
Yingtong Dou, Zhiwei Liu, Li Sun, Yutong Deng, Hao Peng, and Philip S Yu. Enhancing graph neural betwork-based fraud detectors against camouflaged fraudsters. In Proc. CIKM, 2020. 3
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019. 17
Jing Gao, Feng Liang, Wei Fan, Chi Wang, Yizhou Sun, and Jiawei Han. On community outliers and their efficient detection in information networks. In Proc. SIGKDD, pp. $13-822, 2010. 3
Yuan Gao, Xiang Wang, Xiangnan He, Zhenguang Liu, Huamin Feng, and Yongdong Zhang. Ad- dressing heterophily graph anomaly detection: A perspective of graph spectrum. In Proc WWW, pp. 1528-15388 2023. 3,7
Zheng Gong and Ying Sun. An energy-centric framework for category-free out-of -iitr---iittibttionn node detection graphs. Proc. SIGKDD, pp. 908-919, 2024.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Adv. NIPS, 30, 2017. 6,
11

---

Published as a conference paper at ICLR 2025
Junwei He, Qianqian Xu, Yangbangyan Jiang, Zitai Wang, and Qingming Huang. Ada-gad: Anomaly-dene denossed autoencoders for graph anomaly detection. In Proceedings of the AAAI Con- ference Artificial Intelligence, pp. 8481-8489, 2024. 3,7
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Adv. NeurlPS, 33:22118 22132, 2020. 7
Mengda Huang, Yang Liu, Xiang Ao, Kuan Li, Jianfeng Chi, Jinghua Feng, Hao Yang, and Qing He. Auc-oriented graph neural network for fraud detection. In Proc. www. pp. 1311-1321, 2022.
Minqi Jiang, Chaochuan Hou, Ao Zheng. Xiyang Hu, Songgiao Han, Hailiang Huang. Xiangnan He, Philip Yu, and Yue Zhao. Weakly supervised anomaly detection: survey. arXiv preprint Ntl.:3302.04499 2023. 1,3
Justin M Johnson and Taghi M Khoshgoftaar. Survey on deep learning with class imbalance. Journal of Big Data, 6(1):1-54, 2019. 3
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. Proc. ICLR, 2014.
Jundong Li, Harsh Dani, Xia Hu, and Huan Liu. Radar: Residual analysis for anomaly detection in attributed networks. In Proc. IJCAI, pp. 2152-2158, 2017. 3
Yuening Li, Xiao Huang, Jundong Li, Mengnan Du, and Na Zou. Specae: Spectral autoencoder for anomaly detection in attributed networks. In Proc. CIKM, pp. 2233-22366 2019. 3
Xixun Lin, Wenxiao Zhang, Fengzhao Shi, Chuan Zhou, Lixin Zou, Xiangyu Zhao, Dawei Yin, Shirui Pan, and Yanan Cao. Graph neural stochastic diffusion for estimating uncertainty in node classification. In Proc. ICML, 2024. 3
Yixin Liu, Zhao Li, Shirui Pan, Chen Gong, Chuan Zhou, and George Karypis. Anomaly detection on attributed networks via contrastive self-super learning. IEEE Transactions on Neural Networks and Learning Systems, 33(6):2378-22
2021. 3.
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 Trans- actions on Knowledge and Data Engineering, 2021. 1,3
Leland McInnes, John Healy, Nathaniel Saul, and Lukas Grossberger. Umap: Uniform manifold approximation and projection. The Journal of Open Source Software, 3(2)):611, 2018. 18
Chaoxi Niu, Hezhe Qiao, Changlu Chen, Ling Chen, and Guansong Pang. Zero-shot generalist graph anomaly detection with unified neighborhood prompts. arXiv preprint arXiv:2410.1488 14886, 2024.3 3
Guansong Pang, Chunhua Shen, and Anton van den Hengel. Deep anomaly detection with deviation networks. In Proc. SIGKDD, pp. 353-362, 2019. 3,
Guansong Pang, Chunhua Shen, Longbing Cao, and Anton Van Den Hengel. Deep learning for anomaly detection: A review. ACM computing surveys 545) 54(2):1-38, 2021a. 3
Guansong Pang, Anton van den Hengel, Chunhua Shen, and Longbing Cao. Toward deep super- vised anomaly detection: Reinforcement learning from partially labeled anomaly data. In Proc. SIGKDD, pp. 1298-1308, 2021b. 1,3
Guansong Pang, Chunhua Shen, Huidong Jin, and Anton van den Hengel. Deep weakly-supervin anomaly detection. In Proc, SIGKDD, pp. 1795-1807, 2023. 2,
Hyunjong Park, Jongyoun Noh, and Bumsub Ham. Learning memory- normality for anomaly detection. In Proc. CVPR, pp. 14372-14381, 2020.
Joonhyung Park, Jacyun Song, and Eunho Yang. Graphens: Neighbor-aware ego network synthesis for Maas-imbalancee node classification. In Proc. ICLR, 2022. 3,
12

---

Published as a conference paper at ICLR 2025
Adam Paszke, Sam Gross, Francisco Massa, Adam Lever, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf. Ed- ward Yang. Zach De Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: an imperative style, high-performance deep learning library. In Adv. NewrIPS, 2019. 17
Zhen Peng, Minnan Luo, Jundong Li, Huan Liu, and Qinghua Zheng. Anomalous: A joint modeling approach for anomaly detection attributed networks. In Proc. IJCAI, pp. 3513-3519, 2018. 3
Bryan Perozzi and Leman Akoglu. Scalable anomaly ranking of attributed neighborhoods. In Proc. ICDM, pp. 207-215, 2016.
Hezhe Qiao and Guansong Pang. Truncated affinity maximization: One-class homophily modeling for graph anomaly detection. Adv. NeurlPS, 36, 2024. 3,7
Hezhe Qiao, Hanghang Tong, Bo An, Irwin King, Charu Aggarwal, and Guansong Pang. Deep graph anomaly detection: A survey and new perspectives. arXiv preprint (tt.::2400009957,, 2024a. 1
Hezhe Qiao, Qingsong Wen, Xiaoli Li, Ee-Peng Lim, and Guansong Pang. Generative semi-
supervised graph anomaly detection. arXiv preprint 1887 2024b. 7
Liang Qu, Huaisheng Zhu, Ruiqi Zheng, Yuhui Shi, and Hongzhi Yin. Imgagn: Imbalanced network embedding via generative adversarial graph networks. In Proc. SIGKDD, pp. 1390-1398, 2021.
Shebuti Rayana and Leman Akoglu. Collective opinion spam detection: Bridging review networks and metadata. In Proc. SIGKDD, pp. 985-994, 2015.
Karsten Roth, Latha Pemula, Joaquin Zepeda, Bernhard Schölkopf, Thomas Brox, and Peter Gehler. Towards total recall in industrial anomaly detection. In Proc. CVPR, pp. 14318-14328, 2022. 3
Lukas Ruff, Robert A. Vandermeulen, Nico Gömnitz, Alexander Binder, Emmanuel Müller, Klaus- Robert Müller, and Marius Kloft. Deep semi-supervised anomaly detection. In Proc. ICLR, 2020. 3.9
Oleksandr Shchur, Maximilian Mumme, Alcksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurlPS 2018, 2018. 7
Kihyuk Sohn, Chun-Liang Li, Jinsung Yoon, Minho Jin, and Tomas Pfister. Learning and evaluating representations for deep one-class classification. Proc. ICLR, 2021. 3
Jianheng Tang. Jiajin Li, Ziqi Gao, and Jia Li. Rethinking graph neural networks for anomaly detection. In Proc. ICML, pp. 21076-21089, PMLR, 2022. 1.
Jianheng Tang, Fengrui Hua, Ziqi Gao, Peilin Zhao, and Jia Li. Gadbench: Revisiting and bench- marking supervised graph anomaly detection. Advances in Neural Information Processing Sys- fems, 02222228-26655 2023. 7,
Andrew Z. Wang, Rex Ying, Pan Li, Nikhil Rao, Karthik Subbian, and Jure Leskovec. Bipartite dynamic representations for abuse detection. In Proc. SIGKDD, pp. 3638-3644 2021a. 3
Qizhou Wang, Guansong Pang, Mahsa Salehi, Wray Buntine, and Christopher Leckie. Cross- domain graph anomaly detection via anomaly-awan contrastive alignment. In Proc. AAAI, pp- 6676-46844 2023a.
Xuhong Wang, Baihong Jin, Ying Du Ping Cui, Yingshui Tan, and Yupu Yang. One-class graph neural networks for anomaly detection in attributed networks. Neural Computing and Applica- tions, (((1)):1003312085 September 2021b. 3.7
Yanling Wang, Jing Zhang, Shasha Guo, Hongzhi Yin, Cuiping Li, and Hong Chen. Decoupling representation learning and classification for gan-based anomaly detection. In Proc. SIGIR, pp- 1239-1248, 2021c. 2021c 3,
13

---

Published as a conference paper at ICLR 2025
Yuchen Wang. Jinghui Zhang, Zhengjie Huang, Weibin Li, Shikun Feng, Ziheng Ma, Yu Sun, Di- anhai Yu, Fang Dong, Jiahui Jin, et al. Label information enhanced fraud detection against low homophily in graphs. In Proceedings of the ACM Web Conference 2023, pp. 406-416 2023b. 3
Zheng Wang, Xiaojun Ye, Chaokun Wang. Jian Cui, and Philip Yu. Network embedding with completlyy-imbllancee labels. IEEE Transactions Knowledge and Data Engineering, 33(11); 3634-3647, 2021d. doi: 10. 10.1109/KDDE.2200.919999999
Qitian Wu, Yiting Chen, Chenxiao Yang, and Junchi Yan. Energy-basee out-of--istribur detection for graph neural networks. In Proc. ICLR, 2023. 3
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions Neural Networks and Learning Systems, 32(1):4-24, 2020. 3
Zhiming Xu, Xiao Huang, Yue Zhao, Yushun Dong, and Jundong Li. Contrastive attributed network anomaly detection with data augmentation. In Pacific-Asian Conference on Knowledge Discovery and Data Mining (PAKDD), 2022. 3,7
Wenchao Yu, Wei Cheng, Charu Aggarwal, Kai Zhang, Haifeng Chen, and Wei Wang. Netwalk: A flexible deep embedding approach for anomaly detection in dynamic networks. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp- 2681,, 2018. 3
Houssam Zenati, Manon Romain, Chuan-Sheng Foo, Bruno Lecouat, and Vijay Chandrasekhar. Adversarially learned anomaly detection. In Proc. ICDM, pp. 727-736. IEEE, 2018. 3
Tianxiang Zhao, Xiang Zhang, and Suhang Wang. Graphsmote: Imbalanced node classification graphs with graph neural networks. In Proc. WSDM, pp. 833-841, 2021. 3,7
Tong Zhao, Chuchen Deng, Kaifeng Yu, Tianwen Jiang, Daheng Wang, and Meng Jiang. Error- bounded graph anomaly loss for gnns. In Proc. CIKM, pp. 1873-1882, 2020. 3
Yue Zhao and Maciej K Hryniewicki. Xgbod: improving supervised outlier detection with unsu- pervised representation learning. In 2018 International Joint Conference on Neural Networks
(IJCNN) pp. 1-8. IEER, 2018. 3
Shuang Zhou, Xiao Huang, Ninghao Liu, Huachi Zhou, Fu-Lai Chung, and Long-Kai Huang. Im- proving generalizability of graph anomaly detection models via data augmentation. IEEE Trans- actions on Knowledge and Data Engineering, 2023.
Zhi-Hua Zhou and Xu- Ying Liu. Training cost-sensitive neural networks with methods addressing the class imbalance problem. IEEE Transactions on Knowledge and Data Engineering, pp. 63- 77, 2006.
Wei Zhuo, Zemin Liu, Bryan Hooi, Bingsheng He, Guang Tan, Rizal Fathony, and Jia Chen, Parti- tioning message passing for graph fraud detection. In Proc. ICLR, 2024. 3,7
A
APPENDIX
Appendix
The appendix section structured as follows. In Appendix A, we details the proof of the proposition 1. In Appendix B, provide extended details of the experimental setup, including dataset informa- tion, experimental protocol, and implementation specifics. In Appendix C, we provide additional results that included in the main section due to space limitations.
14

---

Published as a conference paper at ICLR 2025
Z
((3)
Zal
a (Zai)
x(2a2)
Path I
Z22
Zm
O
(Z
Zn
Figure 5: Proposition proof intuition: Z and (2) represent the shared node representation spaces before and after applying the scaling function a, respectively. In this plot, the grey region represents the normal subspace Zu, and the union of the grey and red regions represents Zm- The boundary of the normal subspace, M, is depicted by the black lines. The goal to prove that the red regions, which denote the neighbourhood of anomalies, do exist within the normal subspace for well- trained relation discriminator.
A PROOF OF PROPOSITION
For convenience, we define a labelling function with a range of [0, 1]. This function assigns a normality score of O to relations between normal nodes and anomaly nodes. In contrast, relations exclusively between normal nodes receive scores ranging from significantly greater value than O, denoted a, to a maximum of 1. For simplicity, use the mapping of our default choice of relation modelling function F. It is worth noting that any function that satisfies the condition specified in Sec. 3.3 can be proved using the same approach. We show via proof by contradiction that, if F is well-trained to distinguish the normal nodes exclusive relations and those that involves anomalies in node representation space shared with supervised anomaly detector, anomaly node lies in the normal region within the shared representation space of and F, where normal nodes form a dense subspace.
We assume the normal region in the shared representation space is a connected open set, due to the high similarity and dense distribution of normal representations forced by supervised discriminative loss CAD. For well-trained F and any given normal node from the region n, suppose there are two anomaly nodes, al and a2, where al lies outside the normal region and a2 overlaps with the normal region. Note that such al can be easily found, as CAD will ensure sufficient number of seen anomalies residing outside of the normal subspace Zn Consider a path connecting these two anomaly nodes:
4 = to (Zm1) + (1 - (2w2) te E (0, 1).
The homeomorphic of the Sigmoid function will ensure that we are able to find the scaled represen- tation of normal node (22) along the path at / = 4m- Then we have:
(zm) ) = fm (Za1) ) + (1 fm (m) (222)-
(8)
Applying F to the relation between n and m, we have:
F(hmm) Wa ham b
Wo(diag(o(zn)) Wz)o(zm)) +
Wo(diag(a(zn)) WF)((mo(Za)) (1 lm (Z(2)) +
tm WW diag (o(z,) W (E)o((aa) + +b) (1 - tm/) (wo diag (o(z.) W WB)o(za2) +b)
im Wchnal + b) + tmm) Wchhna + b) Lm F(haa) + (m)) F (hhaz))
15

---

Published as a conference paper at ICLR 2025
Since F is well trained, have F(hma1) < ? 8 and F(haa2) < 6, where o(7) E R(o,)) Therefore, we have:
and
< <9- 8 F F(hmm) = tm Fm (hpal) ) + (1 - fm)) Fm)na))
fum o (bm))) < ( - 6) < a
which contradicts with the fact that Jum
B MORE EXPERIMENTAL DETAILS
B. PSEUDOCODE FOR TRAINING NSREG
The training procedure of NSReg is described in the following pseudocode:
Algorithm Training NSReg
Require: G and ytrain s.t. ytrain < [V]
Ensure: Φ: (9, v) > an anomaly scoring mapping
1: Initialize variables
2: for = in [I,..., Meepocha do
3: <- Sample bAD nodes from Vtrain
4: R Sample bysR relations as described in Sec. 3.4.
5: CAD + Compute the supervised GAD loss.
6: Perform gradient descent for 7).
7: LNSr + Compute the NSReg loss.
8: Perform gradient descent for F, E.
9: L + Compute the total loss as in Eq. 6
Perform gradient descent for v.
11: end for
return
B.2 DATASETS
B.2.1
DATASET STATISTICS
Table 5 shows the statistics seven datasets used. Note that the Yelp dataset is a heterogencous graph containing three different views. We choose the edge subset of the "Review-User-Revien (RUR)" view our experiments.
Table 5: A summary of dataset statistics
Dim.
Nodes
Edge
Ano. Classes
Ano.
PAno.
Photo
745
7.487
119,043
2
369
4.92
Computers
767
13,381
245,778
5
2,064
15.42
CS
6,805
18,333
81,894
8
4,159
22.69
Yelp
32
45,954
98,630
2
6,677
14.53
ogbn-arxiv
128
169,343
1,166,243
27,830
16.43
ogbn-proteins
8
132,534
39,561,252
2
10,693
8.07
T-Finance
10
39,357
21,222,543
2
1,803
4.58
B.2.2 DATASET PREPROCESSING
For the imbalance attributed node classification datasets Photo, Computers, CS and ogbn- treat each class that has less than 5% of the total number of nodes of the graph and the remaining classes as normal. In the ogbn-arxiv dataset. with the original graph containing 40 subclasses, for experimental efficiency, any class representing 3% to 5% of the total nodes is
anomaly class
16

---

and Published as a conference paper at ICLR 2025
considered an anomaly class. Note that the normal class is defined the combination of all the majority classes, from which labelled normal nodes are randomly and uniformly drawn, and remain consistent through the entire experiment.
For the Yelp and T-Finance datasets, which only contain binary anomaly labels, we first apply an unsupervised representation learning method Deep Graph Infomax (DGI) for representation learn- ing and then apply k-means clustering to partition the anomaly class into two anomaly subclasses using their node representations. Specifically, our DGI model employs two-layer GraphSAGE as the representation learner with 128 hidden units per layer. The model is optimised for 1,000 epochs using the Adam optimiser with the learning rate and the batch size to 1 10-3 and 512. respec- tively. To further magnify the distribution shift, instead of employing random sampling, we conduct weighted random sampling generate training anomaly nodes, where the probability associated with each anomaly node is proportional to its distance from its corresponding cluster centroid.
B.3 EXPERIMENTAL PROTOCOL
Algorithm Open-set GAD) Experimental Protocol
Require: 9, and anomaly class index idxanom-
Ensure: The overall and unseen AUC-ROC and AUC-PR values.
Vn < {u Ve idxxnoom
2: n f- Sample the training normal nodes.
3: for e idxanom do
4: Vseen x fo == c}
5: Vuinsee 5- {2 V/ not in idxanom]
6: V train <- sample from Veeen and Virain
7: @ &- Train an anomaly detection network using NSReg as described in Algorithm
8: AUC-ROCslL AUC-PR &- evaluate & using V V train-
9: AUC-ROCuseen AUC-PR unseen +- evaluate & using Vn U Junseen Vtrain
10: Record class AUC-ROC and AUC-PR.
end for
12: Calculate the average performance AUC-ROC"!! AUC-PRal)
AUC-ROC
unseen
AUC-PR unseen
13: return AUC-ROCall, AUC-PRal), AUC-ROC unseen AUC-PR unseen
In this section, we outline the process conducting open-set GAD experiments and encapsulate in Algorithm 2. For each dataset, we alternate treating each anomaly class as the seen anomaly, with the remaining anomaly classes as unseen, for all anomaly classes. For example, the CS dataset, 8 out of 15 classes marked anomalies. The results for this dataset underwent 5 independent runs of cub-experiments, with each anomaly class treated as 'seen' rotation, totaling 40 sub- experiments for CS. Note that the normal class remains consistent across each run, and the labelled normal nodes are uniformly drawn.
B.4 IMPLEMENTATION DETAILS
B.4.1 DEPENDENCIES
NSReg is implemented in Python and makes extensive use of Pytorch (Paszke et al., 2019) and Pytorch Geometric (Fey & Lenssen, 2019). We summarise the main scientific computing libraries and their versions used for our implementation as follows:
python=3.88.13
pytorch==1.10.1 (py3.8 1.3 I.3.cldnn.c..d.8.0..
pytorch_geometric==220000 (py38_tom)))) torch_1 1.100._eu 10000_cul111 cul13)
numpy=1.23.5
scipy==1.10.0
1.1k
17

---

Published as a conference paper at ICLR 2025
11datoolkit==113.111
dgl==1.0.2
B.4.2
HYPERPARAMETER SETTINGS
For NSReg, addition to the hyperparameters reported in Sec. 4, we set the numbers of neighbours used for GraphSAGE aggregation to 25 and 10 for the first layer and the second layer, respectively, for better runtime efficiency. The same sampling strategy as NSReg is employed for the GNN- adapted competing methods that were designed for Euclidean data. Our anomaly scoring network a two-layer neural network with 32 hidden units in the hidden layer. BCE, DevNet and PReNet are trained for the same number of epochs (200) NSReg using the Adam optimiser using the learning rate of 1 x 10-3, GraphSMOTE, for which the pretraining and training epoch numbers both set to 2,500 where the model exhibits convergence.
keep the default hyperparameter settings for the other baselines except for
For the large-scale datasets ogbn-arxiv and ogbn-proteins, set the default number of labelled anomalies to 100, and a reduced percentage of labelled normal nodes to I % to make more chal- enforce
lenging and practical for real-world applications. For ogbn-proteins, where it is stronger structural regularisation due to its large number of nodes and highly dense connections (i.e., over hunderd thousand nodes with over 300 average degree).
B.4.3 VISUALISATION METHOD
We utilise UMAP (McInnes et al., 2018), widely adopted non-linear invertible dimensionality duction algorithm, in conjunction with the Matplotlib library to generate contour plots representing anomaly scores. Specifically, we apply UMAP to transform node representations at the anomaly scoring (final) layer each method into a 2-dimensional representation space. Within the bound- aries of the 2D representation space for each method, determined by the maximum values of each dimension, we create a uniform mesh with a step size of 0. Subsequently, all points within the mesh are coloured based the anomaly scores assigned by the final layer, utilising their represen- tations transformed by the inverse transformation of the same UMAP model.
B.5 HARDWARE CONHGURATION
Our experiments are conducted using single NVIDIA A100 GPU and 28 CPU cores from an AMD EPYC 7663 Processor on a HPC cluster.
B.6 LABELLING FUNCTION ILLUSTRATION
Labelled Normal
Unlabelled Normal
Labelled Amom.
Unlabelled Amom. Connected
Not considered
Figure 6: An illustrative plot of the labelling function C
Figure illustrates the labelling function C' in the NSReg mentioned in Equation 3.
C ADDITIONAL EXPERIMENTAL RESULTS
C.1 COMPLETE ANOMALY DETECTION PERFORMANCE
The table presents the anomaly detection performance of NSReg compared with all baseline meth- ods, evaluated on both all test anomalies and exclusively on unseen anomalies. Consistent conclu- sions with Section 4. I can be drawn: NSReg significantly outperforms the baseline methods across
18

---

Published as a conference paper at ICLR 2025
Table 6: AUC-ROC and AUC-PR (mean=std) for detecting all anomalies and exclusively unseen anomalies. The boldfaced are the best results. "_" denotes unavailable result due to out- -em-ofy
ABC ROC
AUC
Set
Method
Photo
Computer
CS
Yelp
Avarae
Phomo
Computers
CS
Yelp
Avergee
DOMINANT
04234000011
0576400.00 (KT
8400
0600600011
1.503at1.05
0107260000
0.182an uos
0.087
0.221 0013
0.16650000
0.32260007
1300
OCGNN
0.523x0.040
0.50580.01
0.509
0.406a0.034
6005550012
8.156a0.00
0.358
0.02500.005
0.150u00000
0OLA
0.256000011
0400600000
015
0.30260.13
0.500601020
0.298400054
0.23540 024
0,25340.011
0.204200018
ABGES
0.543x0.033
0.42680.06
0.49150.055
0005880015
0.132an.00 010
0.22740.225
CINDA
0.12440-00)
0 0:00040:411 01573400000
111400017
0:41--011
0. 0.108400000
01150000000
0.09540.011
007-00013
0. 0.1
TAM
0.36430004
043549.002
0.29580.006
0L495
0.22200002
0.131200001
0.31842.006
0.135 087
0.177
ADA-GAD
0.191 10.000
0.557:0004
8 6310-00040
6006-00001
8.174-0:00 031
0.161:0:00
FReNer
0
0632290005
0.57700016
0.672+30044
06112110177
045980010
0.574811131
0.362=00011
ABI
DCI
0.6020005 0
0 012
0.69943.009
07750e40025
0452260094
0-22741
0:115:0027
0.351:00044
0,375
0.46200011
BRONN
0.72820:05
0. 0.769u0.029 0.72220.05
0.727a0.012
0.23720.000
0.313800066
0.461:0.012
0.68700.045
0 0.36620.015
0.5720.035
AMNer
0.777+0001
0 1377 0677
0.0M500011
U.75 1.755
04477400003
0.395001016
0.754590004 0M14
0377700013
0,501 200
CERN
0.74120.055
0.60480.023
0.75750836
0.71389.021
0.20420.009
0.36230004
0.304
0.51520.056
0.34920 000
0412590016
CONSUS
0:70--00011
0-5070000
BARS40057
0-754400000
Bost-ums
0468 40.00
0:42440077
TMP
0:72600000
0.71
0280
0:712+3:16
0447890007
010050.00
0.759
0.245
0.5550.0000
0.0000015
SMOTE
0,662200
047
0:31
0.72760.199
0.135
0.30940043
0.732+0.000
0,30000.19
0.356e0.041
XCI0mnp
6.72200000
077000000
0.200.0.000
0.80518.00
0.26420.000
0.52110000
0-42200000
0.553.0.000
0.622000000
0.500.0.000
BCE
0.72459027
0 035
0.71260017
0.77
0.1169.0111
0.33150026
0,75
0.57
0,53249.15
NSReg (Org))
6.7918.015
0.75400003
0.64146836
0.38910.816
005000004
0A1210021
CGAN
0455500006
0.56580009
0335551.05
0.31982.003
0.22
0,065800011
0.150
0.16850.001
0.05500000
0.105.0.000
0CGNN
032140000
0196-0013
0. 1.50-0.015
0.6644.110 10)
0.0600000
0135-0000
0.11740.006
00650005
0. 0.105-0.000
COLA
0.83620.044
0:62999.044
0 0.4225.015
0.291
0.557
0.15688:229
0.201a00015
0.252
0.005200022
0.101:0:144
ARGES
0.55310.078
D 8.85
0005110011
B112:001
0.200 10.004
CONDA
0.125+0000
0400 0522880000
0,20640.017
0:00000000
0.174420010
0.05540 003
0
TAM
0,21 1000
0435100002
0.30110.001
0.497
6007340:001
0:30410:000
0.633:00000
0.100000000
ADA GAD
(00
PRaNa
0.4020.002
0.55760.03
0.49750.016
0.615
0.512a0 025
0.4445.004
0.352x0.010
1202
0.153a0.013
Unsrn-
DeyNer
DCI
0,00
04668-00000
0662999.011
0.247500013
0.657a0.009
0.01 40.000
0,501-00055
0.03380.088
0025400005
0.356cc 050
0.500440 DM0
0 0.558
D. 157200024
1424411222
0272200015
0 0224440007
BRONN
198-00408
B 83779608000
067440.007
0006400000
0 0 0226-00044
017-00015
0.788-0
AMNe:
0:50
0.00040.005
0.50433.014
0:00800002
0.739.0.000 032
0.14320.009
0.297500007
GIERN
DA11 10/044
0.531:00044
0.2290.016
063300011
00:810:00
10:000000000
0:250100054
CONSIS
0516e00049
0645
0.67563001
11575
0.145ell125
0.47
0.5000.006
66681660022
0.305u00000
G. ENS
061CH1109 0.1
0169600011
0.55620017
00035000012
0222220012
0.44750017
(155
0:207=0:000
G. G.SMOTE
0464420.066
0.835an.04 0.64320.055
045
0.71683.00
Re6San.041
0.04480.044
0.23220043
0.678
167220015
0.260:0.033
B 077184112 1700
6.788-880
00075400000
0.447-0.000
0.267-00004
BCE
0.65020.006
0.60280.015
0.856al
0.65880.023
0.70920:017
0,070000007
0.293g0.015
0.723x0.009
0.170e0.055
0.3 0.31450:012
NSReg (Oue)
6775288019
0153011108
0,000600025
0100610111
0:321
0.477411044
0.36649.031
0,45599831
all datasets in terms of both metrics. The primary difference from Table 1 is that this table includes all unsupervised methods, some of which were omitted in the main text due to space constraints. Unsurprisingly, these unsupervised methods are less effective for open-set GAD due to the lack of anomaly prior knowledge.
Although NSReg achieves superior performance overall, one exception is that XGBGraph performs surprisingly well the Yelp dataset. We believe this is incidental, as XGBGraph is generic hybrid method combining parameter-free node feature propagation with XGBoost, without GAD-specific training. This enables it to perform particularly well on the Yelp dataset. A similar observation was noted in the benchmark paper (Tang et al., 2023) where XGBGraph significantly outperformed all state-of-the the-art methods on this dataset by large margin. However, this strong performance is not universal and is not observed on other datasets.
C.2 DETAILED RESULTS FOR NSR AS A PLUG-AND-PLAY MODULE
We present the complete results of plugging our NSR module into three ofate-of- supervised AD model, DevNet, DCI and BWGNN, with the original models as the baselines for both all test anomalies and in Table the unseen anomalies in Table 8 in terms of both AUC-ROC and AUC-PR. Similar substantial performance improvement can be observed as Sec. 4.
19

---

Published as a conference paper at ICLR 2025
Table Results of plugging our NSR module into three SOTA supervised AD models DevNet, DCI and B BWGNN, with the original models as the baselines on all test anomalies.
Metric
AUC-ROC
AUC-PR
Dataset
Ori
+NSR
Diff.
Ori
+NSR
Diff.
Photo
0.599
0.684
+0.0851
0.223
0.424
+0.2011
Computers
0.606
0.646
+0.040
0.284
0.340
+0.0561
DevNet
CS
0.769
0.949
+0.1801
0,684
0.872
+0.1881
Yelp 0.675
0.684
+0.0091
0.315
0.315
+0.0081
Avg. Diff.
+0.0791
+0.1131
Photo
0.772
0.865
+0.0931
0,452
0.577
+0.1251
Computers
0.683
0.738
+0.0551
0,427
0.501
+0.0741
DCI
CS
0.856
0.857
+0.0011
0.635
0.623
-0.012
Yelp
0.689
0.740
+0.0511
0.351
0.387
+0.0361
Avg. Diff.
+0.0501
+0.0561
Photo 0.728
0.802
+0.0741
0.313
0.530
+0.2171
Computers
0.635
0.726
+0.0911
0.348
0.458
+0.1
BWGNN
CS
0.845
0.879
+0.0341
0,687
0.718
+0.0311
Yelp 0.727
0.747
+0.0201
0.366
0.394
+0.0281
Avg. Diff.
+0.0551
+0.0971
Table 8: Results of plugging NSR module into three SOTA supervised AD models DevNet, DCI and B BWGNN, with the original models as the basclines on unseen anomalies.
Metric
AUC-ROC
AUC-PR
Met.
Dataset
Ori
+NSR
Diff.
Ori
+NSR
Diff.
Photo
0.468
0.513
0.045t
0.045
0.092
0.0471
Computers
0.573
0.623
0.0501
0.200
0.266
0.0661
DevNet
CS
0.739
0.944
0.2051
0.606
0.841
0.2351
Yelp
0.621
0.632
0.0111
0.142
0.146
0.0041
Avg. Diff.
0.0781
0.0881
Photo 0.614
0.780
0.166t
0.083
0.201
0,1181
Computers
0.629
0.693
0.0641
0.288
0.380
0.0921
DCI
CS
0.847
0.847
0.000
0.558
0.547
-0.011
Yelp
0.637
0.699
0.0621
0.157
0.190
0.0331
Avg. Diff.
0.0731
0.0581
Photo 0.598
0.628
0.0301
0.068
0.078
0.0101
Computers
0.570
0.662
0.0921
0.209
0.272
0.0631
BWGNN
CS
0.829
0.873
0.0441
0.620
0.678
0.0581
Yelp 0.674
0.703
0.0291
0.167
0.188
0.0211
Avg. Diff.
0.0491
0.0381
C.3 DETAILED ABLATION STUDY RESULTS.
We present the comprehensive results of the ablation study in Table and 10, corresponding Table in the paper. The performance in AUC-ROC shows similar trend as AUC-PR, aligning with our observations and findings in Sec. 4.2.
C.4 DETAILED LARGE-SCALE GAD RESULTS
In this section, present the complete results for large-scale GAD in Tables 11 and 12. We ob- serve NSReg consistently outperforms the baseline methods by large margin on unseen anomalies, similar discussion in Sec. 4.1.
20

---

Published as a conference paper at ICLR 2025
Table 9: Our proposed NSR module vs other regularisation methods for all test anomalies.
Datuset
SAD
CL (unsup)
CL (8)
NSR (dual)
NSR
Photo
0.599
0.807=0.010
0.891#0.010
0.89420.016
0.908=0.016
Computers
0.644#0.1 126
0.743+0.012
0.781+0.022
0.778+0.021
0.797+0.015
AUC-ROC
CS
0.819#0.014
0.894
0.927+0.012
0.927+0.022
0.957=0.047
Yelp
0.522=0.041
0.731=0.014
0.665#0.072
0.732+0.016
0.734#0.012
average
0.64620.079
0.794+0.011
0.81640.029
0.833+0.019
0.84920.013
Photo
0.269=0.215
0,513+0.018
0,583+0.012
0.623+0.022
0.640=0.036
Computers
0.381
0,492+0.014
0.53940.024
0,539 0.3
0.559#0.018
AUC-RR
CS
0.700=0.016
0.795+0.009
0,843+0.020
0.858+0.04 042
0.889=0.016
Yelp 175:0000066
0.392+0.013
0.330+0.078
0.399+0.021
0.398:0.014
Average
0.64640.079
0.794#0.011
0.81640.029
0,83340.019
0,849#0.013
Table 10: Our proposed NSR module other regularisation methods for unseen anomalies.
Dataset
SAD
CL (unsup)
CL (8)
NSR (dual)
NSR
Photo
0.51620.047
0.652+0.018
0.807=0.017
0.810#0.031
0.836+0.031
Computers
0.614#0.100 103
0.685=0.015
0.733+0.027
0.730+0.025
0.752+0,019
AUC-ROC
CS
0.797=0.016
0.88340.006
0.920#0.013
0,924+0.021
0.953+0.008
Yelp
0.511=0.026
0.677=0.023
0.613+0.071
0.679#0.018
0.690=0.025
averuge
0.610=0.048
0.724#0.016
0.768+0.032
0.786+0.024
0.808#0.021
Photo
0.053=0.004
0.068+0.004
033++00.0
0.207=0.049
0.221=0.057
Computers
0,285=0.134
0.318+0.018
0.379+0.032
0.389+0.028
0.417:0.024
AUC-RR
CS
0.631=0.019
0.743+0.010
0.797+0.025
0,834+0.046
0.866:0.021
Yelp
0.090=0.017
0.178=0.011
0.152+0.045
0.1 0.190+0.023
0.196:0,020
Average
0.265=0.044
0.327+0.011
0.365+0.030
0.405+0.037
0,425+0.031
C.5 EFFECT OF INCLUDING NORMAL-ANOMALY RELATIONS
This section investigates the effect of including additional type of normal relation that connects normal and anomaly nodes in the relation modelling of NSReg. We report the GAD performance for all test anomalies and the unseen anomalies in both AUC-ROC and AUC-PR in Table 13. We found that the inclusion of connected normal-anomaly relations is less effective than the default NSReg in terms of average performance, although it can achieve comparable performance on the CS and Yelp datasets. This is because the structural distinction between the normal and the seen anomalies usually sufficiently preserved by the GAD loss. Additionally, it could introduce unnecessary complexity into the hierarchy of the relation modelling, resulting in less effective modelling of the normality that is not addressed by the GAD loss.
C.6 DETAILED HYPERPARAMETER ANALYSIS
We report the GAD performance on all test anomalies in both AUC-ROC and AUC-PR with respect to À and a in Figure 7 and Figure 8, respectively. The results demonstrate stability across a wide spectrum, indicating the robustness of NSReg with respect to their settings.
Photo
Compuler
Yelp
AUC-ROC
0.9
AUC-PP
0.6
0.8
1.0
0.6
0.8
1.0
Figure 7: Overall GAD performance of NSReg w.r.t
21

---

Published as a conference paper at ICLR 2025
Table 11: Results on large-scale graph datasets for all test anomalies, where "_" denotes unavailable results due to out of memory.
Metric
Datasets
ogbn-urxiv
ogbn-proteins
T-Finance
avg.
PReNet
0.581+0.006
0.613#0.035
0.892=0.017
0.695=0.019
DevNet
0.601
0.622=0.057
0.654=0.210
0.626#0.094
DCI
0.56620.041
0.815#0.037
0.763+ 0.111
0.715#0.063
BWGNN
0.587+0.013 0.727+0.067
0.922=0.011
0.745=0.030
AUC-
AMNet
0.600+0.049 0.711=0.077
0.889=0.024
0.733+0.050
ROC
GHRN
0.58820.009
0.674+0.019
0.923=0.010
0.728+0.013
(AlI)
GLENS
0.847=0.087
G.SMOTE
0.875=0.016
BCE
0.59240.004
0.568+0.020
0,922#0.011
0.694+0.012
NSReg
0.659:0.012
0.843*0.029
0.929=0.007
0.810=0.016
PReNet
0.288+0.004
0.432+0.028
0.571
0.430=0.057
DevNet
0.304=0.009
0.436#0.017
0.323=0.327
0.354#0.1 118
DCI
0.275+0.033
0.597+0.062
0.264=0.240
0.379 112
BWGNN
0.263+0.009
0.582+0.026
0.746=0.023
0.530=0.019
AUC-
AMNet
0.272+0.053
0.576#0.053
0.644=0.046
0.497=0.051
PR
GHRN
0.271
0.564=0.005
0.727=0.031
0.521
(AII)
G.ENS
0.332=0.076
G.SMOTE
0.573=0.077
BCE
0.310#0.003
0.524+0.008
0.726+0.034
0.520#0.015
NSReg
0.723=0.020 0.33620.006
0.757=0.020
0.605:0.125
Table 12: Results on large-scale graph datasets for unseen anomalies, where denotes unavailable results due of memory.
Metric
Datasets
ogbn-arxiv
ogba-proteins
T-Finance
avg.
PReNet
0.465+0.008
00.250=0.055
00.881=0.022
0.532=0.032
DevNet
0.494+0.0119
0.264#0.112
0.64246.227
0.467#0.119
DCI
0.465+0.045
0.672=0.095
0.742+0.1 106
0.626#0.082
BWGNN
0.49920.014 0.429 156
0,903=0.023
0.61020.064
AUC-
AMNet
0.519+0.053 0.339=0.263
0.872+0.045
0.577=0. 120
ROC
GHRN
0,493=0.012
0.309=0.043
0,908
0.570=0.022
(Unseen)
G.ENS
0.835+0. 100
G.SMOTE
0.878+0.016
BCE
0.478=0.005
0.12020.033
0.921#0.010
0.50620.016
NSReg
0.57020.016
0.74820.047
0.928:0.006
0.74920.023
PReNet
0.124+0.002
0.029=0.004
0.431 147
0. 195
DevNet
0,142 006
0.032+0.007
0.284++..0 306
0,153+0. 106
DCI
0.125
0.182=0. 172
0.185#0.222
0.16420. 135
BWGNN
0.13540.004 004
0.058=0.018
0.60920.022 029
0.267=0.017
AUC-
AMNet
0.141
0.048+0.030
0.461 067
0.217+0.040
PR
GHRN
0.132+0.003
0.044=0.002
0.583
0.238=0.021
(Unseen)
G.ENS
0,201
G.SMOTE
0.459x0.095
BCE
0.13620.002
0.025=0.001
0.62920.047
0.263+0.017
NSReg
0.165:0.005
0.488=0.042
0.669:0.024
0.441=0.024
C.7 DETAILED DATA EFFICIENCY RESULTS
In this section, our primary focus is on showing the data efficiency performance of NSReg in terms of AUC-ROC, which complements the discussion of AUC-PR in Sec. 1. As illustrated in Figure 9 and Figure 10, NSReg consistently achieves remarkable performance similar to AUC-PR. Specif- ically, across the entire spectrum, NSReg outperforms the baselines on both overall and unseen anomaly detection for the Photo, Computers, and CS datasets. For the Yelp dataset, NSReg either outperforms or achieves comparable performance, particularly when the number of labelled training anomalies exceeds 5. While GraphSMOTE slightly outperforms NSReg in unseen anomaly detec-
22

---

Published as a conference paper at ICLR 2025
Table 13: NSReg vs. NSReg considering connected normal-anomaly relation (NSReg NA).
AUC-ROC
AUC-PR
NSReg + NA
NSReg
NSReg + NA
NSReg
Photo
0.860=0.017
0,908+0.016
0.561=0.019
0.640=0.036
computers
0.761=0.013
0.797=0.015
0,538=0.011
0.559=0.018
0.965+0.00S
0.957=0.007
0.904=0.014
0.889#0.016
Yelp
0.738+0.004
0.734=0.012
0.401=0.009
0.398#0.014
Average
0.831+0.010
0.849+0.013
0.601=0.015
0.622+0.021
Photo
0.747=0.032
0.83620.031
0.107=0.018
0.221
Computers
0.708=0.015
0.752=0.019
0.392=0.025
0.417=0.024
CS
0.962#0.006
0,953#0.008
0.884=0.018
0.866#0.021
unscen
Yelp
0.689*0.009
0.690=0.025
0.193=0.010
19240.0020
Average
0.777=0.016
0.808+0.021
0.394
0.425=0.031
Compatens
Yelp
AUC-ROC
AUC-PR
0.8
Figure 8: Overall GAD performance of NSReg w.r.t X.
tion, its effectiveness in the seen anomalies limited, resulting in less effective overall detection performance.
NSIleg [ours] BCE
G.MOOTE
---
BWGNN
PiteNet AMNet
-
GHRRN
G ENS
-0- DevNet
X-
-
DCI
Test All
Photo
Computers
CS
Yelp
0.8
AUC-ROC
0.8
0.7
0.7
0.6
0.5
0.6
0.5
Test Unseen
0.7
0.7
AUC-ROC
0.8
0.6
0.6
0.6
0.5
0.5
15
25 1
50
100
5
15
25
50
100
15
25
50
100
15
25
50
100
|
Figure 9: Data efficiency of NSReg and the competing methods in utilising labelled data in AUC- ROC for both all test anomalies and the unseen anomalies.
23

---

Published as a conference paper at ICLR 2025
NSBle (ours] BCE
G GSOOO
BWGNN DovNet
PReNet AMNet
GHRN
GEENS
*-
DCT
Test All
Photo
Computers
CS
Yelp
0.6
0.4
0.8
AUC-PR
0.4
0.4
0.3
0.2
0.2
0.2
Test Unseen
0.4
0.8
0.3
AUC-PR
0.3
0.6
0.2
0.2
0.1
0.1
0.1
15
20 p
30
100
5
15
25
50
100
15
25
50
100
15
25
50
100
|
Figure 10: Data efficiency of NSReg and the competing methods in utilising labelled data in AUC- PR for both all test anomalies and the unseen anomalies.
24


Reviews:
[{"review_id": "CPpO6PJiMz", "reviewer": "Reviewer_KzVj", "summary": "This paper tackles the challenge of open-set graph anomaly detection, where the detection model is trained to detect both known and previously unseen anomalies. The authors introduce NSReg, a method that utilizes auxiliary relational information around normal nodes to regularize the model's training. NSReg works by distancing unseen anomalies from normal nodes, aiding in their detection. The paper also includes a theoretical analysis of the proposed method. Comprehensive experiments evaluate the model's effectiveness and the individual contributions of its components.", "questions": "See Weakness.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper tackles an important and impactful problem—open-set graph anomaly detection—with significant potential for real-world applications.\n2. The writing is clear, and the paper is well-organized, making it easy to follow.\n3. A theoretical analysis is provided, adding depth to the proposed approach.\n4. The paper includes thorough experiments that demonstrate the proposed method's effectiveness, along with ablation studies that evaluate the contribution of each component.", "weaknesses": "1. The core idea of using neighborhood information to enhance anomaly detection is not entirely novel, as similar approaches have been explored in prior works [1], [2], [3]. A comparison between NSReg and these previous methods is necessary to better contextualize its contributions.\n\n2. I have some concerns about the effectiveness of the Normal-node-oriented Relation Generation component. Specifically, the unconnected relation $R_{(n,u,u)}$ between normal nodes and other nodes may include a large number of connections to unlabeled normal nodes, given the predominance of normal nodes in the dataset, as the authors also note. If most $R_{(n,u,u)}$ relations are between labeled and unlabeled normal nodes, distancing these pairs may not meaningfully enhance model training. At the same time, if there are very few $R_{(n,u,u)}$ relations involving labeled normal nodes and unlabeled unseen anomalies, the regularization term may have minimal impact on detecting unseen anomalies. I suggest that the authors conduct an empirical analysis on the distribution of different types of relations within the sampled $R_{(n,u,u)}$ set and discuss how this distribution affects the regularization term's effectiveness.\n\n3. In Eq. (3), the meaning of symbols $\\cdot$ and $\\circ$ are unclear. Also, in Eq. (2) and (5), the supervised training loss should sum over all training nodes, not the entire node set $V$.\n\n4. Could the authors provide justifications for updating the three components $\\eta$, $F$ and $E$, and $\\phi$ separately as stated in the pseudo-code?\n\n5. In the Yelp dataset, NSReg displays less sensitivity to the hyper-parameter $\\lambda$ compared to other datasets (such as Photo, Computers, and CS). Could the authors provide an explanation for this? Additionally, G. SMOTE performs better on unseen anomalies for this dataset, as shown in Table 1. An explanation for this would also be necessary.\n\n6. The source code for this work is not provided for review.\n\n[1]: Label information enhanced fraud detection against low homophily in graphs. WWW. 2023.\n\n[2]: Consistency training with learnable data augmentation for graph anomaly detection with limited supervision. ICLR. 2024.\n\n[3]: Partitioning message passing for graph fraud detection. ICLR. 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oW1QxWFdPX", "reviewer": "Reviewer_VYmz", "summary": "The paper studied the unsupervised graph anomaly detection problem under the lack of prior knowledge setting. In particular, it proposes an approach focusing on learning normality using supervised signals to distinguish unseen anomalies from normal nodes. The proposed method, NSReg, models three types of normal-node-oriented relations as a discriminative task, enhancing representation learning with enriched normality semantics. The authors argue that this approach effectively disentangles unseen anomalous nodes from normal nodes in the representation space. The paper also discusses the plug-and-play design of the method, which allows for its application in various scenarios.", "questions": "1. Aegis (Inductive anomaly detection on attributed networks) is an unsupervised graph anomaly detection using GAN to strengthen the generalization ability of the model. The authors should discuss how their method compares with this work.\n2. Line 271, why is the $aplha$ set to 0.8? What is the significance of this value? The author should discuss this in detail and provide some experiment results to support this choice.\n3. Figure 3 is hard to understand.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The problem studied in the paper is interesting. Due to the lack of prior knowledge, unsupervised graph anomaly detection often suffers from high error rates. The authors focus on learning normality to enhance the model's ability to detect unseen anomalies, potentially improving the performance of existing methods in this area.\n2.  The Plug-and-Play design is a notable strength, as it allows the method to be easily integrated into existing frameworks and applied to various scenarios.\n3. The experiments conducted are comprehensive, covering the performance on all anomalies and unseen anomalies, ablation study, and the performance as a plug module, which evaluates the proposed method's effectiveness well.", "weaknesses": "1. There are some unsupervised graph anomaly detection works that achieve considerable inductive performance. The author did not point out why these methods cannot meet the requirements. There should be a more thorough comparison of these existing methods and an analysis of the deeper reasons behind them.\n2. The description of the proposed method did not clarify the innovation of this paper. One innovation of this paper is the focus on learning normality on structure. This differentiates this work from existing one-class classification/anomaly detection methods, but this point is unclear.\n3. The presentation of the paper needs to be improved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3rGCpkbgyO", "reviewer": "Reviewer_JRAN", "summary": "This paper presents a novel open-set Graph Anomaly Detection (GAD) approach called Normal Structure Regularization (NSReg). The method aims to achieve generalized detection capabilities for unseen anomalies while retaining effectiveness in identifying known anomalies. It introduces a regularization term that encourages the learning of compact, semantically rich representations of normal nodes, informed by their structural relationships with other nodes. Extensive empirical evaluations on seven real-world datasets demonstrate that NSReg significantly outperforms state-of-the-art competing methods.", "questions": "1. What does \"connected normal nodes, unconnected normal nodes, and unconnected normal nodes to unlabelled nodes\" mean? It would be best to illustrate these relationships with a diagram.\n2. What does the calculation symbol \"$\\circ$\" represent in the paper?\n3. In line 241, what do \"these two types of relations\" refer to? Are they the two types described in line 232: \"the relations between only the normal nodes and the relations between normal and anomaly nodes\"? Why does the relationship description in line 2—“connected normal nodes, unconnected normal nodes, and unconnected normal nodes to unlabelled nodes”—not use the same phrasing? Are there actually distinctions between them?\n4. In line 238, what is the specific operation when it states, “If Z is shared with a discriminative graph anomaly detector”?\n5. The equations in lines 267-269 are not labelled and should correspond to Equation 3. How is alpha determined, and why is it set to 0.8?\n6. In Figure 2, is the \"shared representation space\" represented by the grey rectangle with dashed lines? The arrows inside have three different styles, but the authors only labelled two of them.\n7. In line 277, why is g considered a mapping and how is it discriminative?\n8. What is the relationship between the equation in line 282 and g? Is this equation equivalent to $g_C$?\n9. How does the paper address the prediction of unseen nodes, and how does it identify unseen nodes?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "1. The experiments are comprehensive and yield strong results.\n2. The paper provides some theoretical proofs.\n3. It introduces a novel open-set approach to Graph Anomaly Detection (GAD).", "weaknesses": "1. The paper's structure is disorganized, and the context of the paragraph is stiff. For instance, the three types of 'Normal-node-oriented Relations' are not clearly explained. Additionally, in lines 225-228, the authors mention analyzing the effects of enforcing structural normality in the representation space and its advantages for enhancing generalization to unseen anomalies. However, it is difficult to connect this to the later explanations, and the concept of structural normality even is not defined.\n2. The wording in the paper is imprecise. For example, in the caption of Figure 2, the term \"The green teal dashed box\" does not clearly indicate which part of the figure it corresponds to. Furthermore, it is unclear whether \"a discriminative graph anomaly detector\" refers to \"a graph anomaly detector with a discriminator,\" as the term \"detector\" itself implies a discriminative function.\n3. The paper does not provide information about the hardware used for running experiments, nor does it include the experimental code and datasets. This raises concerns about the reproducibility of the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7Nrpx5BC5X", "reviewer": "Reviewer_uvQ4", "summary": "The paper proposes an approach for open-set graph anomaly detection. The authors introduce a method called Normal Structure Regularisation (NSReg) to regularize the learning process by focusing on the structural relationships among normal nodes in the graph. Experiments show that the framework outperforms baselines on datasets included in this paper.", "questions": "Q1. Can the authors explain the differences between open-set GAD and out-of-distribution detection? \n\nReference\n1. Qitian Wu, Yiting Chen, Chenxiao Yang, Junchi Yan. Energy-based Out-of-Distribution Detection for Graph Neural Networks. ICLR 2023. \n2. Zheng Gong, Ying Sun. An Energy-centric Framework for Category-free Out-of-distribution Node Detection in Graphs. KDD 2024. \n3. Xixun Lin, Wenxiao Zhang, Fengzhao Shi, Chuan Zhou, Lixin Zou, Xiangyu Zhao, Dawei Yin, Shirui Pan, Yanan Cao. Graph Neural Stochastic Diffusion for Estimating Uncertainty in Node Classification. ICML 2024. \n4. Jianheng Tang, Fengrui Hua, Ziqi Gao, Peilin Zhao, Jia Li. GADBench: Revisiting and Benchmarking Supervised Graph Anomaly Detection. NeurIPS 2023. \n5. Nan Chen, Zemin Liu, Bryan Hooi, Bingsheng He, Rizal Fathony, Jun Hu, Jia Chen. Consistency Training with Learnable Data Augmentation for Graph Anomaly Detection with Limited Supervision. ICLR 2024.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "S1. The authors introduce a method called Normal Structure Regularisation (NSReg) to regularize the learning process by focusing on the structural relationships among normal nodes in the graph.\n\nS2. Experiments show that the framework outperforms baselines on datasets included in this paper.", "weaknesses": "W1. The contribution seems to be overclaimed. As stated in this paper, open-set GAD is an under-explored problem. However, the definition of open-set GAD problem is very similar to that of out-of-distribution detection, and there are several previous works in this area, such as GNNSAFE[1], EnergyDef[2], and GNSD[3]. \n\nW2. Experiments are not comprehensive enough. As for the supervised GAD model, there are several new baselines, such as XGBGraph[4], and CONSISGAD[5]. The authors should include them as baselines as well. Besides, as mentioned above in W1, such a task is almost the same as the out-of-distribution problem, which means the authors need to compare their framework with out-of-distribution models on out-of-distribution datasets, instead of creating synthetic datasets from T-Finance. \n\nW3. Some parts of the paper need to be further explained. For example, in Section 3.3, Normal-node-oriented Relation Generation, the authors set alpha = 0.8 by default but did not provide any intuition or theoretical analysis of such a value.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)