Boosting Graph Anomaly Detection with Adaptive Message Passing
Authors: Jingyan Chen
Guanghui Zhu
Chunfeng Yuan
Yihua Huang
Venue: ICLR 2024 poster (2024)
Keywords: Graph neural network
unsupervised anomaly detection
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning

Abstract: Unsupervised graph anomaly detection has been widely used in real-world applications. Existing methods primarily focus on local inconsistency mining (LIM), based on the intuition that establishing high similarities between abnormal nodes and their neighbors is difficult. However, the message passing employed by graph neural networks (GNNs) results in local anomaly signal loss, as GNNs tend to make connected nodes similar, which conflicts with the LIM intuition. In this paper, we propose GADAM, a novel framework that not only resolves the conflict between LIM and message passing but also leverages message passing to augment anomaly detection through a transformative approach to anomaly mining beyond LIM. Specifically, we first propose an efficient MLP-based LIM approach to obtain local anomaly scores in a conflict-free way. Next, we introduce a novel approach to capture anomaly signals from a global perspective. This involves a hybrid attention based adaptive message passing, enabling nodes to selectively absorb abnormal or normal signals from their surroundings. Extensive experiments conducted on nine benchmark datasets, including two large-scale OGB datasets, demonstrate that GADAM surpassinges existing state-of-the-art methods in terms of both effectiveness and efficiency.

Published as a conference paper at ICLR 2024
BOOSTING GRAPH ANOMALY DETECTION ADAPTIVE MESSAGE PASSING
WITH
Jingyan Chen, Guanghui Zhu", Chunfeng Yuan, Yihua Huang State Key Laboratory for Novel Software Technology, Nanjing University jyé sma i jun. sru.edd.cc {zgh, efyuan, yhuang) @n ju edw....d........................ cn
ABSTRACT
Unsupervised graph anomaly detection has been widely used in real-world appli- cations. Existing methods primarily focus on local inconsistency mining (LIM), based on the intuition that establishing high similarities between abnormal nodes and their neighbors difficult. However, the message passing employed by graph neural networks (GNNs) results in local anomaly signal loss, as GNNs tend to make connected nodes similar, which conflicts with the LIM intuition. In this pa- per, propose GADAM, novel framework that not only resolves the conflict between LIM and message passing but also leverages message passing to aug- ment anomaly detection through a transformative approach to anomaly mining beyond LIM. Specifically, we first propose an efficient MLP-based LIM approach obtain local anomaly scores in conflict-free way. Next, introduce novel approach to capture anomaly signals from a global perspective. This involves a hybrid attention based adaptive message passing, enabling nodes selectively ab- sorb abnormal or normal signals from their surroundings. Extensive experiments conducted on nine benchmark datasets, including two large-scale OGB datasets. demonstrate that GADAM surpasses existing state-of-the-art methods in terms of both effectiveness and efficiency.
INTRODUCTION
Anomaly detection on a graph refers to identifying abnormal nodes, which has emerged as cru-
cial research field (Ma X 202T, Ren et al. 2023; Wang L. 202T Liu C (02T)) widely applied in various domains such as social networks (Cheng 2021 Yuan H| 2021). financial fraud detec-
tion (Huang X 2022 Dou Y| 2020). and telecommunication fraud detection Yang et al., al,] 2019). The scarcity of labels and diversity of anomalies makes unsupervised graph anomaly detection (UGAD) an important, but non-trivial problem. There are two main types of abnormal nodes
graphs: contextual and structural anomalies (Liu et al. 2022a), illustrated in Fig. [ A surge of recent
works (Ding et al. [2019] Fan et al. 2020 Bandyopadhyay et al. 2020 Liu et al. [2021] Yuan et al. 2021 Xu a 2022 Zhang et al.
2022) have explored various effective methods for UGAD. Due to the lack of labels, most of them are based on local inconsistency mining (LIM), with the intu- ition that establishing significant similarity between abnormal nodes and their neighbors is more difficult than normal nodes, Graph neural networks (GNNs) (Pan S [222]] Thomas N. Kipr) 2017] Veli ckovi"s c & Bengio 2018) are utilized for node representation learning, reconstruction error or similarity discriminator is used to measure the inconsistency between the node and its neighbors, and higher inconsistency refers larger anomaly score.
Despite the success of existing methods, an important but overlooked problem is the conflict be- tween the message passing of GNNs and the LIM intuition. Specifically, the feature aggregation operation of GNNs tends to make connected nodes similar (Chai et al.) 2022 Li et al.) 2019a, Wu ct al. 2019 Balcilar et al. 2021), which implicitly enhances the consistency between the node and its neighbors and makes anomalies indistinguishable. A naive solution is to employ models without message passing, such as using MLP (Ramchoun et al. 2016), to enable conflict-free LIM. However, the graph structure contains valuable anomaly signals. For instance, densely connected subgraphs
"Corresponding Author

---

Published as a conference paper at ICLR 2024
E-EE
Weaken
Maintain
Message
Abnormality
Local Inconsistency Mining
Strengthen
Messaga Passing
Abnorality
0.55
Strengthen
Decroase
contentual anomaly
Structural anomaly
Message Passing
Abnormality
(+) Confiit-free LIM
(b) Node: Specificc Message Passing: (c) Enhanced anomaly detection
Figure 1:
Two types of anomalies and the guide map of designing UGAD methods. Contextual anomalies are nodes with significantly different attributes from their neighbors. Structural anomalies are densely connected nodes with abnormal links in contrast to sparsely connected regular nodes.
may suggest nodes belonging to structural anomalies. Simultancously, the smoothing effect of mes- sage passing reduces the anomaly degree in normal nodes by aligning them with their neighbors. Therefore, completely discarding the message passing would be unwise.
Meanwhile, various approaches (Li et al. 2019b; Fan et al. 2020 Pei et al. 2021 have been devel- oped to minimize the damage of message passing on LIM-based anomaly detection. These methods aim enhance the local salience of anomalies and produce distinguishable representations, often utilizing attention mechanisms to reduce the message passing between anomalous nodes and their neighbors. But on the one hand, such approaches only apply discover contextual anomalies that have inherently inconsistent features compared to neighboring nodes, In contrast, structural anoma- lies tend to form clusters that share similar attributes and abnormal behaviors. Striving to block the message passing and deliberately maintaining clusters of anomalies inconsistent with their surround- ings conflict with the inherent nature of structural anomalies. On the other hand, the fundamental conflict still remains. The core reason why message passing is harmful to anomaly detection is the adoption of local inconsistency as measure of anomaly signal. Existing semi-supervised ap- Gao
proaches (Chen et al. [202; Liu Y [202]; Gao et al. 2023 Dou Y 2020 have achieved performance boost through establishing fine-grained message passing and rational anomaly mining approaches. Nevertheless, there remains significant gap in how to design anomaly mining approach that seamlessly integrates with message passing in unsupervised scenarios.
The above analysis inspires that designing advanced UGAD method is journey of handling message passing. which is guided by map that consists of several key components as illustrated in
(2) Achieving fine-grained control of node-specific message passing with its neighbors in the absence of labels. (3) Designing new learning objective and anomaly mining approach beyond LIM, harnessing the utility of message passing for enhanced anomaly detection.
Fig. [ (1) Ensuring conflict-free LIM through elaborate control of message passing.
To this end, we propose GADAM (Graph Anomaly Detection with Adaptive Message passing), clear and flexible two-stage framework that performs LIM and message passing decoupled. In the first stage, we propose an MLP-based contrastive method without message passing for LIM, which enables LIM to more effectively and efficiently identify anomalous nodes and produce anomaly scores from a local perspective. classification task, utilizing local anomaly scores as pseudo-labels. Concretely, two high-confidenee normal and abnormal node sets are established using the local anomaly scores from the first stage. Subsequently, we define the learning objective to discriminate the alignment between nodes and the global normal context, i.e. average of high-confidence normal nodes, and generate anomaly scores from global view. The second stage will be semi-supervisedly trained, guided by pseudo- labels, and facilitated by an adaptive message passing scheme. To achieve adaptive message passing for nodes with distinct roles, we further propose an innovative hybrid attention mechanism that takes into account both the anomaly score difference and the feature similarity with its neighbors. The shift in the perspective of anomaly mining. combined with the design of the hybrid attention mechanism, enables message passing to enrich anomaly mining, akin to how feature aggregation in GNNs enhances classification tasks (Huang et al. 2020. Wang & Zhang 2022 Zhu 2005). The anomaly scores from the two stages will be combined to provide holistic measure of node anomaly.
the second stage, we convert the learning objective to binary
GAADM is available at http:://ithuh..cm/Pssslaaaaaaaa
2

---

Published as a conference paper at ICLR 2024
The main contributions of our paper are summarized follows:
We analyze the dilemma faced by current UGAD methods when handling message passing. A novel MLP-based contrastive method is introduced to disentangle message passing from LIM, enabling more effective and efficient L.IM.
We introduce a novel anomaly mining approach from a global view, which utilizes local anomaly scores pseudo-labels and models anomaly detection as binary classification task to facilitate message passing, and enhance the effectiveness of anomaly detection.
A well-designed hybrid attention mechanism is proposed, which takes into account both a node's anomaly score difference and the feature similarity with its neighbors, enabling more precise and udaptive message passing.
Extensive experimental results on nine benchmark datasets, including seven datasets with injected synthetic anomalies and two datasets with organic anomalies, demonstrate that our method achieves state-of-the-art performance compared with range of baselines. More- over, GADAM shows superiority in both runtime and GPU overhead.
BACKGROUND
2.1 UNSUPERVISED GRAPH ANOMALY DETECTION
Let = A, X) be the input graph where V = (11, u,,..., F is the node attribute matrix where the i-th row X(i, denotes is the adjacent matrix and X E Nxx
..., UN) is the set of N nodes, A E VxN
the attribute of node v/ UGAD aims to learn an anomaly score vector E R to indicate the anomaly degree for every node, where larger element s; means higher abnormality for node U,.
2.2 CONTRASTIVE LEARNING FOR UGAD
CoLA (Liu et al. 2021) is the first to leverage contrastive learning for LIM, and its process can be di- vided into four parts. (1) Contrastive instance pairs construction: For given node us CoLA sam- ples an subgraph G = ()((), A (i) x()) with size | = M by random walking with the center node uy and construct the positive instance pair (v,, G.) Another subgraph 9 (VV), A (5), X
is sampled with the center node 2y (i / j) to form the negative instance pair (v;, G.) G. and G have the same size. (2) Instance pair representation learning: The central nodes vs, Uj are anonymized
by setting their attributes to 0' in Gj and Gü respectively. Then, an L-layer graph convolutional network (GCN) with parameters W is used to obtain node embeddings, and a readout function is
(B M E = GCN(C)) W, W) E, rep- m=1
M
employed to yield the subgraph representation: e
resents node embeddings in g and is activation function. The negative subgraph representation e, is obtained in the same way on G Next, an L-layer feed forward network (FFN) with parame- ters W and activation function o same as GCN is utilized to map node v, to the same feature space: h; = FFN (V [i, W, σ). (3) Similarity discriminating: A discriminator with parameter ( is used to evaluate the similarity between contrastive pairs: Dis(hi, (pp.)) = oh, (e(p.)) where epp..) denotes e,, or e,, The similarity of positive instance pair (h; ef, will be increased and the opposite for negative instance pair (h,, e CoLA is learned by minimizing the binary cross-entropy (BCE) loss:
N C= Σ Dog(Dis(h,, + log(1 - Dis(h, ei,)
(1)
(4) Multi-round anomaly score computation: At the inference stage, R positive and negative subgraphs will be sampled for node vs, forming instances pool (g) ,..,,... G.. G. "..,. R).,.. The anomaly score is obtained through R-round evaluation to eliminate the randomness caused by subgraph sampling:
8, Σ Dis(h, exr Dis(l,, e,,")
(2)
R
3

---

Published as a conference paper at ICLR 2024
MLL M-esede
Local Anomaly
X
Learding
Anomaly Scone Combination
Fatrot
6.85
High colldeto
Ancemaly
IL Hybrid Attention based Adaptive Message Passing
Global Coneistency Discemment
Adapttive Massage Passing
clonggtton
wry
Local Anceely
Bobeo Alaekinn
Vesione
Figure Overall workflow of GADAM.
THE PROPOSED METHOD
As shown in Fig. 2 the overall workflow of GADAM contains stages: (1) MLP--ased LIM employs MLP as encoder and extract local anomaly signals through contrastive learning, (2) Hybrid Attention based Adaptive Message Passing is designed calculate the global anomaly score by discriminating the alignment between nodes and the global normal context, accompanied by adaptive message passing with neighbors. Next, we introduce each stage in detail.
3.1 MLP-BASED LOCAL INCONSISTENCY MINING
Considering that contrastive learning can directly target the anomaly detection objective and is friendly to minibatch training (Liu et al. 202I). we employ contrastive learning, along with the following proposed enhancements for more precise and efficient LIM:
We utilize an L-layer MLP for all nodes with L2 normalization to obtain node embedding matrix Hoccll in B). Leveraging MLP instead of GNN as encoder main- tains the independence of node representations, thus avoiding conflicts between LIM and message passing.
(1) MLP as encoder:
H Local o (H( ((1-)) + b() Locat [.. Local
H
[1 Locat ( :l12
loeat
H Tocal
X
(2) Sampling-free contrastive pair construction: We set the positive instance 9% as the complete adjacency subgraph of node 22 instead of sampling. The embedding of Gj is computed by averaging the node embeddings in Gj. and the subgraph embedding matrix E is obtained where Eji, ea denotes the embedding of Gj Then, shuffle E by row get Eshaf- For node vg the positive and negative instance pairs can be expressed as:
(N/ocal =li, neg = (oooca Estuf (ú,
pos
where h//call ( (1) [i, The proposed contrastive pair construction method can avoid the time overhead caused by graph sampling.
(3) Parameter-free similarity discrininator: We utilize the inner product a similarity discrimi- nator, which is equivalent to cosine similarity after L2 normalization:
Dis(h !occal e = h! (e,)) Dis(h local .et,) h /ocall (et,)
(5)
(4) Direct anomaly score calculation: Based the LIM intuition, directly use the feature similarity of the positive instance pairs, i.e., the node and adjacent subgraphs, as the anomaly score:
local DDis(h!oces local .ee))))))) local (et))
4

---

Published as a conference paper at ICLR 2024
CoLA computes anomaly scores through multiple rounds of evaluation, because of the randomiza- tion involved in subgraph sampling and the construction of instance pairs. contrast, our approach obviates the necessity for sampling, with anomaly scores relying solely on positive instance pairs. This modification leads to more efficient computation.
We optimize the first stage using the loss function defined in Eq. [ and produce anomaly score vector Siooel with Eq. (6) The aforementioned enhancements not only mitigate conflicts between LIM and message passing, but also result in a reduction in model parameters and the refinement of modules, consequently improving both the model's effectiveness and efficiency.
After the first stage, we sort Slocal and take the nodes with the smallest % of local anomaly scores to form a high-confidence normal set Vn. and representative global normal context can be obtained by averaging nodes in Vn: C V. Eiev, hlocal We also select kano % of nodes with the largest local anomaly scores to form a high-confidence abnormal set Va. Two high-confidence sets and global normal context C are served supervised signals in the second stage.
3.2 HYBRID ATTENTION BASED ADAPTIVE MESSAGE PASSING
In the second stage, we further propose two components aimed at achieving node-specific message passing and an effective anomaly mining approach beyond LIM, respectively: (1) Adaptive mes- sage passing with hybrid attention is used to determine the strength of message passing based on the local anomaly score differences and feature similarities between nodes and their neighbors. (2) Global consistency discernment is employed to capture anomaly signals based on the consistency of nodes with the global normal context.
3.2. ADAPTIVE MESSAGE PASSING WITH HYBRID ATTENTION
(1) Adattive message passing: We first employ another MLP and follow Eq. for all nodes get H globol in the second stage. For each node v, at epoch I, the node embedding is mixture of h global (i.e.. Hglobal :]] and the adjacency subgraph embedding ei. The coefficient of ej. (i.e., a; (²()) that facilitates the message strength is determined adaptively with a hybrid attention mechanism:
h mix
ag (8) e +1 (1- a2)) hglobal
attention global (h (
(2) Hybrid attention mechanism: The attention mechanism is to assign higher message passing weights to nodes with similar roles. We leverage two types of attention, namely pre-attention and post-attention, which focuses on the local anomaly score difference and the feature similarity re- spectively. Two types of attention are weighted summed to form hybrid attention mechanism precisely determine the strength of message passing.
Pre-attention: Pre-attention is based on the local anomaly score differences between a node and its surroundings. For given node Us the differences are calculated by Eq. (8)
6:
1
Local
locll
(8)
WO
JEN())
where (i) denotes the node set of G We take the mean of the nodes in V, as benchmark for 8, and di be the deviation of 8, for node U;:
15, - E.jE,, (6,))
d;
Varjev, (0g)
An activation function is applied to convert d, to value between [0, 1] to obtain pre-attention:
pre; = 1-o(dd (d:)
(10)
Intuitively, normal nodes and structural anomalies tend to exhibit smaller 8, owing to their higher consistency in anomaly scores with their surroundings. Consequently, these nodes will also have smaller d and larger pre-attention scores, while the opposite for contextual anomalies.
Post-attention: We further propose to leverage feature similarity between a node and its neighbors to obtain post-attention:
post;
glohal (et)
(11)
5

---

Published as a conference paper at ICLR 2024
As contextual anomalies inherently possess features distinct from their neighbors, the post- attention effectively assigns them smaller message passing weights, while the opposite for normal nodes and structural anomalies. Thus, pre-attention and post-attention can work harmoniously. Dynamic weighted sum: Two types of attentions are dynamically weighted summed to get the final attention coefficient for each node et at epoch
(t) =3(0) pree: +(1 (1- post;
8 B x
t
(12)
Tgtobal
where T Tolobal is the total training epochs the second stage, and / < determines the ini- tial weight of pre-attention. Intuitively, as the training advances, the influence of pre-attention gradually diminishes, while the opposite for post-attention. This shift serves a dual purpose: (I) prevents inherent errors in local anomaly scores from continuously misdirecting attention for nodes. (2) As training progresses, nodes naturally adapt to better align with their neighboring nodes, thereby requiring a gradual increase the weight post-attention.
The diversity of attention metrics, the collaborative synergy between the two types of attention, and the dynamic weighted strategy collectively empower the hybrid attention mechanism to facil- itate precise node-specific message passing. Additionally, visualization of the hybrid attention is available Appendix for better clarity and understanding.
3.2.2 GLOBAL CONSISTENCY DISCERNMENT
Inspired by Chen et al. 2022), anomalies tend to be more distant from global normal context C' than normal nodes. Therefore, we enhance the similarity of the high-confidence normal set V, with C while decreasing it for the high-confidence abnormal set Va with the following loss function:
9i Dis(h máz
C) = h pai CTT
C = Val [Val
Σ (og(gs) + Σ log(1 -4u)
(13)
JEV.
KEV.
The global anomaly score obtained from the similarity of the nodes and center C: st gglobal gi- and vector Sglobal is obtained. Ultimately, anomaly detection can be performed by combining two anomaly scores: S = (Stocal + Salobat) 3/2.
3.3 EFFICIENCY ANALYSIS
Assume an input graph has N nodes and È edges, and is the average node degree. Let ʃ be the dimension of the MIP GADAM, we analyze the time complexity of GADAM by considering the two main stages respectively. (1) For MLP-based LIM, the main time complexity is node represen- tation learning which takes ((N f). (2) For the second stage, the time complexity is mainly gener- ated by node representation learning through MLP, which is (NN f); and hybrid attention, which is (Nw) for pre-attention and ON + N2) for post-attention. For anomaly score combination, the time complexity
be ignored. In summary, the overall time complexity is O(22 + f+) 28), which is linearly dependent on the number of nodes and edges in the graph. Besides the high com- putation efficiency, the parameters of GADAM are only the MLPs in two stages, which is memory friendly and helpful for handling large-scale data. We also analyze the baselines listed in $4.1 and compare them with GADAM, see Appendix Dooor more details.
4 EXPERIMENTS
4.1 EXPERIMENT SETUP
Datasets. To comprehensively evaluate our model, we use the following nine benchmark datasets: (1) Seven real-world datasets including five widely used benchmark datasets (Sen et al.) 2008 Tang et al. 2008 Tang& Liu| 2009): Cora, Citeseer, Pubmed, ACM, and BlogCatalog. And two large scale OGB Hu et al. 2020) datasets: ogbn-arxiv and grbnuurrodutt. Since there no organic anomalies in these graphs, we follow previous research (Liu et al., (222a) to inject synthetic anoma- datasets that contain organic
lies, which is common and widely used in UGAD. (2) Two

---

Published as a conference paper at ICLR 2024
Table 1: ROC-AUC comparison on nine benchmark datasets. (First Second) IMP: the average im- provement of GADAM over the rest. OOM: out of memory even if the batch size is set to 32.
Method
Cora
Citeseer
Pubmed
ACM
BlogCatalog
ogbn-Arxiv
ogbn-Products
Books
Reddit
DOMINANT
0,8493
0.8391
0.8013
0.7452
0.7531
0OM
COM
0.5012
0,5621
AAo
0.8431
0.8264
0.8973
0.7516
0.7658
0.6214
OOM
0.5567
0.5454
AdONE
0.8561
0.8724
0.7952
0.7219
0.7314
OOM
OOM
0.5366
0.5015
CoLA
0,8801
0.8891
0,9535
0.7783
0.7807
0,8041
OOM
0.3982
0.5791
ANEMONE
0.9054
0.9239
0,9464
0.8802
0,8005
OOM
OOM
0.4341
0.5563
SL-GAD
0.8983
0.9106
0,9476
0,8538
0.8037
OOM
OOM
0.5655
0.5625
CONAD
0.7423
0.7145
1.6993
0.6849
0.6557
0OM
OOM
0.5224
0,5610
Sub-CR
0.9132
0.9310
0.9629
0.7245
0.8071
OOM
OOM
0.5713
0,5563
ResGCN
0.8479
0.7647
1181799
0.7681
0.7852
OOM
OOM
0.5665
0,5012
ComGA
0,8840
0.9167
0,9212
0.8496
0.8030
OOM
0OM
0.5354
0,5682
GADAM
0.9556
0,9415
019581
0.9603
0.8117
0,8122
0.8499
0.5983
0,5809
IMP
11.21%
10.50%
10.98%
24.54%
5,99%
15.85%
16.88%
5.98%
Books (ancheez et al. 2013) and Reddit (Kumar et al. 2019 Wang et al. tailed dataset description and anomaly injection approach can be found in Appendix
anomalies:
2021). De-
Baselines. We compare with three classes of methods regarding UGAD. The first family of baselines
autoencoder based methods: DOMINANT (Ding al. 2019). AnomalyDAE (Fan et al. 2020),
and AdONE [Bandyopadyyay et al.
2020). The second family are CL-based methods: CoLA (Liu
et al.
2021 ANEMONE (Jin et al. 2022), SL-GAD (Zheng al. 2021). CONAD (Xu et al.
2022 and Sub-CR (Zhang et al. 2022). The third are models that are particularly designed for
handling indistinguishable anomalies caused by message passing: ResGCN (Pei et al.
202 and
ComGA Luo et al. 2022). We provide more details for these models in Appendix B.3
Evaluation metrics. We follow the extensive literature (Ding al. 2021 Tong & Lin 2011 et al. (222a)) in UGAD to comprehensively evaluate model performance with three metrics:
ROC-AUC evaluates the comprehensive performance of both normal and abnormal samples. (2)
Average Precision focuses more on abnormal samples. (3) Recall @k evaluate the top-k samples
with high predicted anomaly scores. More details can be found in Appendix [B.5]
Implementation details. For GADAM, we set 3 = 0.9 in Eq. 12
to determine the initial weight
of are-atteniion. We set kano 1, kn 50 for Pubmed, and kano knoo 30 for rest datasets to establish high confidence sets. More hyperparameter settings can be found in Appendix [.6, For the implementation of baselines, we use the PyGod (Liu et al.) 2022b) library if they are available, otherwise use the source code provided in the original paper.
4.2 EFFECTIVENESS COMPARISON
We compare GADAM with representative baselines, and the mean ROC-AUC of five runs are ported in Tab. [ The variance omitted due to its negligible magnitude. Other results for AP and Recall @k metrics are deferred to Appendix [ By comparison, we have the following observations:
GADAM demonstrates remarkable effectiveness, showcasing substantial improvements ranging from 5.98% to 24.54% in ROC-AUC across all datasets. Notably, it achieves ofte-off-hhean performance eight datasets and remains highly competitive the Pubmed dataset.
GADAM exhibits good compatibility, surpassing most methods that struggle deliver satisfac- tory performance on datasets that contain either injected or real anomalies. In contrast, GADAM excels at effectively addressing diverse anomalies, whether they exhibit synthetic or real patterns.
GADAM exhibits impressive scalability, distinguishing itself from most baseline models that en- counter OOM when dealing with large-scale OGB datasets, which further reveals the high com- putation efficiency of our method.
4.3 DETAILED ANALYSIS FOR TWO STAGES
The tow-stage framework of GADAM prompts natural question: to what extent do these two stages enhance the model? First, we investigate the impact of isolating the message passing on the effectiveness of LIM in the fitst stage. We evaluate this by comparing two variants: GADAM
7

---

Published as a conference paper at ICLR 2024
Table ROC-AUC comparison of model variants on five benchmark datasets. (First Second)
Method
Cora
Citeseer
Pubmed
ACM
BlogCatalog
CoLA
0.8801
0.8891
0.9435
0.7783
0.7807
GADAMOON
0.6480
0.7281
0.7841
0.6691
0.4752
losal
GADAMtocot
0.9256
0.9141
0.9510
0.9199
0,7625
GADAM
0.9556
0.9415
0,9581
0,9603
0.8117
and GADAM local GADAM anomaly detection relies solely on Stocal obtained first stage, while GADAM local we utilize GCN for node embedding instead of an MLP. Next, we as- sess the effectiveness of the proposed enhancements in $3.T comparing GADAM and CoLA. Finally, we evaluate the impact of the second stage by comparing GADAM and GADAM
The experimental results presented in Tab. rrevea several key findings: (1) Message passing exerts a considerable negative impact on LIM (GADAMeCC lood v.s GADAM)ocat), thereby validating the effectiveness of our decoupling strategy. (2) Our proposed enhancement strategies within the MLP- based LIM exhibits notable improvement in effectiveness (GADAMiocal V.s CoLA). (3) The design of the second stage significantly enhances the model's performance (GADAMiccal GADAM).
4.4 EFFICIENCY COMPARISON
To further compare the efficiency and scalability, we count the total rumning time and maximum GPU memory consumption during model execution. As shown in Fig. 3 GADAM excels in both runtime and memory overhead, leading to significantly better efficiency and scalability.
3000
214
Aasss
Ansmmbyok
GPU Memonyyaa)
ANEENONE
100
Sui-Ch
10
ConCA
Cora
Citeweer
Pubmed
Cora
Citeseer
Pubmed
Figure 3: The runtime (left) and GPU overhead (right) of different methods. Noting that runtime includes data augmentation, model training, and anomaly score calculation procedures that may be necessary, and the maximum GPU memory requirement throughout the model's 's execution is shown.
4.5
ABLATION STUDIES
4.5.1 SIZE AND QUALITY OF NIGH-CONFIDENCE ANOMALY SET
In GADAM, two high-confidence sets established guide the second stage of learning. An important question is that,what is the false rate of these pseudo labels and their effect on the training? We present the analysis results in Fig. Notably, given that normal nodes constitute the overwhelming majority, the high-confidence normal set exhibits high accuracy. the analysis about the high-confidence normal is not reported.
peoudo stel RcorDrS
BOC-atic GADAM
CIL
6.M1
CAS
2.0
1.0
(e] Cora
(b) Clessee
(c) Puamed
Figure 4: Pseudo label accuracy of high-confidence anomaly set and the model performance of GADAM with different hinno on three benchmark datasets.
8

---

Published as a conference paper at ICLR 2024
Fig. 4 shows that the pseudo label accuracy tends decrease the size of the high-confidence abnormal set grows. However, GADAM maintains consistent performance across various set sizes. Additionally, model maintains its effectiveness, anomaly set falls below 0.5 (e.g., the Pubmed dataset), showcasing remarkable robustness. An intuitive explanation for this phenomenon is that enlarging the set size exposes more anomalous signals to the model, which helps to prevent overfitting and mitigate the class imbalance.
when the label accuracy of high-confidence
4.5.2 ANALYSIS OF HYBRID ATTENTION MECHANISM
We present a set of ablation experiments to provide a more in-depth analysis of the hybrid attention mechanism. The results are shown in Tab. [] revealing that lack of (w/o attn) blind message flow (fixed attn) is ineffective. Moreover, both pre-attention and post-attention contribute to model performance. Overall, the hybrid attention mechanism can achieve the best performance.
4.5.3 INFLUENCE OF EMBEDDING DIMENSION
Fig. exhibits rising trend performance as the embedding dimension increases, followed by stabilization phase. To strike balance between effectiveness and computation efficiency, we set the embedding dimension to 64 for all datasets.
Table 3: Ablation study for hybrid attention. "w/o attn" denotes without message passing, "fixed attn" denotes the coefficient in Eq.
0.11
is set to a constant: a; 2
0.85
Variants
Cora
Citeseer
Pubmed
0.80
GADAM
0.9556
0.9415
0.9581
w/o altn
0,9213
0.9117
0.9341
fixed attn
0.9275
0.9157
0.9441
w/o pre-attn
0.9492
0.9278
0.9504
0.70
1G Emibediing dim
32
120
256
post-alin
0.9501
0.9301
0.9482
Figure 5: Influence of embedding dimension.
5 RELATED WORK
In this section, we present related works from two views: CL based methods and conflict-aware methods. CoLA (Liu al. 202T) is the first leverage CL for LIM. SL-GAD (Zheng et al.) 202T) not only reconstructs the central node feature, but also performs contrastive learning between re- constructed and origin features. CONAD (Xu et al. 2022) designs four types of prior knowledge for abnormal nodes, and enables the model to learn prior knowledge to identify anomalies through CL. For conflict-aware methods, SpecAE. [Li al. 2019h) introduces framework based on spectral convolution and deconvolution, utilizing Laplacian sharpening magnify feature distances between anomalies and others. ResGCN (Pei et al.) 202T) utilizes an MLP to model the attribute matrix, ob- taining residual matrix. Node residuals serve both measure of anomaly degree and the strength of message passing. ComGA (Luo et al.] 2022) learns community-
node representations to avoid excessive similarity of node characteristics across different communities. Also, there exist noteworthy works (Ding et al., [202]] Huang et al. 2023 Yang et al. 20033] Fathony et al. 2023 Wang et al. 2023) beyond the above views, providing broader overview of UGAD.
CONCLUSION
In this paper, we investigated the shorteomings of existing unsupervised graph anomaly detection methods. We introduced novel approach to perform local inconsistency mining and message pass- ing decoupled, and further detect anomalies beyond the local perspective by incorporating adap- tive message passing and global consistency discernment. The proposed GADAM, features clear framework, high efficiency, and the ability to handle large-scale datasets. Extensive experimen- tal results reveal the superiority of GADAM, and ablation studies provide further understanding of GADAM. We hope our work can shed new insights on graph anomaly detection, and provide inspiration for real-world scenarios.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work was supported by the National Natural Science Foundation of China (#62102177), the Natural Science Foundation of Jiangsu Province (BBK2021018) I,, the Key R&D Program of Jiangsu Province (#BE202172), and the Collaborative Innovation Center of Novel Software Technology and Industrialization, Jiangsu, China.
REFERENCES
Muhammet Balcilar, Renton Guillaume, Pierre Héroux, Benoit Gaüzzre, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in spectral perspective. In Proceedings of the International Conference on Learning Representations (ICLR). 2021.
Sambaran Bandyopadhyay, Saley Vishal Vivek, and MN Murty. Outlier resistant unsupervised deep architectures for attributed network embedding. In Proceedings of the 13th international confer- ence on web search and data mining, 2020.
Ziwei Chai, Siqi You, Yang Yang, Shiliang Pu, Jiarong Xu, Haoyang Cai, and Weihao Jiang. Can abnormality be detected by graph neural networks? In Proceedings of the Twenty-Ninth Interna- tional Joint Conference on Artificial Intelligence (ICAAI, 2022.
Bo Chen, Jing Zhang, Xiaokang Zhang, Yuxiao Dong, Jian Song, Peng Zhang, Kaibo Xu, Evgeny Kharlamov, and Jie Tang. Gecad: Graph contrastive learning for anomaly detection. IEEE Trans- actions on Knowledge and Data Engineering, 2022.
Shu K et al Cheng L, Guo R. Causal understanding of fake news dissemination on social media. Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery Data Mining, 2021.
Kaize Ding, Jundong Li, Rohit Bhanushali, and Huan Liu. Deep anomaly detection attributed networks. In Proceedings of the 2019 SIAM International Conference on Data Mining, 2019.
Kaize Ding, Jundong Li, Nitin Agarwal, and Huan Liu. Inductive anomaly detection on attributed networks. In Proceedings of the twenty-ninth international conference international joint conferences on artificial intelligence, pp. 1288-1294, 2021.
Sun al Dou Y, Liu Z. Enhancing graph neural network- fraud detectors against camou- flaged fraudsters. Proceedings of the 29th ACM International Conference on Information Knowl- edge Management, 2020.
Haoyi Fan, Fengbin Zhang, and Zuoyong Li. Anomalydae: Dual autoencoder for anomaly detec- tion on attributed networks. In ICASSP 2020-2020 IEEE International Conference on Acousties, Speech and Signal Processing (ICASSP), 2020.
Rizal Fathony, Jenn Ng, and Jia Chen. Interaction-focuss focused anomaly detection on bipartite node-and- aate-attributed graphs. In 2023 International Joint Conference on Neural Networks (IJCNN), pp- 1-10. IEEE, 2023.
Yuan Gao, Xiang Wang, Xiangnan He. Zhenguang Liu, Huamin Feng, and Yongdong Zhang. Ad- dressing heterophily in graph anomaly detection: A perspective of graph spectrum, 2023.
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. arXiv preprint arXiv:2005.00687, 2020.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin R Benson. Combining label propagation and simple models out-performs graph neural networks. arXiv preprint arXiv:2010. 13993, 2020.
Yihong Huang, Liping Wang, Fan Zhang, and Xuemin Lin. Unsupervised graph outlier detection: Problem revisit, new insight, and superior method. In 2023 IEEE 39th International Conference on Data Engineering (ICDE), pp. 2565-2578. IEEE, 2023.
Wang Y et al Huang X, Yang Y. Dgraph: A large-scale financial dataset for graph anomaly detection. Thirty-sixth Conference Neural Information Processing Systems, 2022.
10

---

Published as a conference paper at ICLR 2024
Ming Jin, Yixin Liu, Yu Zheng, Lianhua Chi, Yuan-Fang Li, and Shirui Pan. Anemone: Graph anomaly detection with multi-scale contrastive learning. Proceedings of the 30th ACM Inter- national Conference Information & Knowledge Management, 2021.
Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in tem- poral interaction networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge diseovery data mining, pp. 1269-1278, 2019.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In Proceedings of the IEEE/CVF international conference on computer vision, 2019a.
Yuening Li, Xiao Huang, Jundong Li, Mengnan Du, and Na Zou. Specae: Spectral autoencoder for anomaly detection in attributed networks. In Proceedings of the 28th ACM international conference on information and knowledge management, pp. 2233 2236, 2019b.
Pi-Erh Lin. A nonparametric estimation of the entropy for absolutely continuous distribu- tions(corresp.). IEEE Transactions on Information Theory, 22(3):372-375, 1976.
Kay Liu, Yingtong Dou, Yue Zhao, Xueying Ding, Xiyang Hu, Ruitong Zhang, Kaize Ding, Canyu Chen. Hao Peng. Kai Shu, et al. Benchmarking node outlier detection on graphs. Thirty-sixth Conference on Neural Information Processing Systems, 2022a.
Kay Liu, Yingtong Dou, Yue Zhao, Xueying Ding, Xiyang Hu, Ruitong Zhang, Kaize Ding, Canyu Chen, Hao Peng, Kai Shu, et al. Pygod: A python library for graph outlier detection. arXiv preprint ar Www.:2224..4195.. 2022b.
Yixin Liu, Zhao Li, Shirui Pan, Chen Gong, Chuan Zhou, and George Karypis. Anomaly detection on attributed networks via contrastive self-supervised learning. IEEE transactions on neural networks and learning systems, 2021.
Ao et al Liu C, Sun L. Intention-aware heterogeneous graph attention networks for fraud trans- actions detection. Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery Data Mining. 2021.
Qin Z et al. Liu Y. Ao X. Pick and choose: a gnn-based imbalanced learning approach for fraud detection. Proceedings of the Web Conference, 2021.
Xuexiong Luo, Jia Wu, Amin Beheshti, Jian Yang, Xiankun Zhang, Yuan Wang, and Shan Xue.
Comga: Community-awar attributed graph anomaly detection. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, pp. 657-665, 2022.
Xue al Ma X. Wu J. A comprehensive survey on graph anomaly detection with deep learning. IEEE Transactions on Knowledge and Data Engineering, 2021.
A. Casanova A. Romero P. Li'o Veli ckovi c. G. Cucurull and Y. Bengio. Graph attention net- works. International Conference on Learning Representations, 2018
Wu Z Pan S, Chen A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 2021.
Yulong Pei, Tianjin Huang, Werner van Ipenburg, and Mykola Pechenizkiy. Resgen: attention- based deep residual modeling for anomaly detection on attributed networks. 2021 IEEE 8th International Conference on Data Science and Advanced Analytics (DSAA), pp. 1-2. IEEE, 2021.
Hassan Ramchoun, Youssef Ghanou, Mohamed Ettaouil, and Mohammed Amine Janati Idrissi. Multilayer perceptron: Architecture optimization and training. 2016.
Jing Ren, Feng Xia, Ivan Lee, Azadeh Noori Hoshyar, and Charu Aggarwal. Graph learning for anomaly analytics: Algorithms, applications, and challenges. ACM Transactions on Intelligent Systems and Technology, 2023.
Patricia Iglesias Sánchez, Emmanuel Müller, Fabian Laforet, Fabian Keller, and Klemens Böhm.
Statistical selection of congruent subspaces for mining attributed graphs. In 2013 IEEE 13th
international conference data mining, pp. 647-656. IEFE, 2013.
11

---

Published as a conference paper at ICLR 2024
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- -aas. Collective classification in network data. Al magazine, 29(3):93 93, 2008.
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Ametminer: extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, 2008.
Lei Tang and Huan Liu. Relational learning via latent social dimensions. In Proceedings of the 15th
ACM SIGKDD international conference on Knowledge discovery and data mining, 2009.
Max Welling Thomas N. Kipf. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017.
Hanghang Tong and Ching-Yune Yung Lin. Non-negative residual matrix factorization with application to graph anomaly detection. In Proceedings of the 2011 SIAM International Conference on Data Mining, Pp. 143-153. SIAM, 2011.
Qizhou Wang, Guansong Pang, Mahsa Salehi, Wray Buntine, and Christopher Leckie. Cross- domain graph anomaly detection via anomaly-aware contrastive alignment. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 1676-46844 2023.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity on the hypersphere. In International Conference on Machine Learning, pp. 9929-9939. PMLR, 2020.
Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In International Conference Machine Learning, 2022.
Yanling Wang, Jing Zhang, Shasha Guo, Hongzhi Yin, Cuiping Li, and Hong Chen. Decoupling representation learning and classification for gnn- gon-based anomaly detection. In Proceedings of the 44th international ACM SIGIR conference on research and development in information retrieval, pp. 1239-1248, 2021.
Xiong K et al Wang I., Li P. Modeling heterogeneous graph network on fraud detection: a community-basee framework with attention mechanism. Proceedings of the 30th ACM Inter- national Conference on Information Knowledge Management., 2021.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simpli- fying graph convolutional networks. In International conference on machine learning, 2019.
Zhiming Xu, Xiao Huang. Yue Zhao, Yushun Dong, and Jundong Li. Contrastive attributed net- work anomaly detection with data augmentation. In Advances in Knowledge Discovery and Data Mining: 26th Pacific-Asia Conference, PAKDD, 2022.
Shujie Yang, Binchi Zhang, Shangbin Feng, Zhanxuan Tan, Qinghua Zheng, Jun Zhou, and Minnan Luo. Ahead: A triple attention based heterogeneous graph anomaly detection approach. In Chinese Intelligent Automation Conference, pp. 542-552. Springer, 2023.
Yang Yang, Yuhong Xu, Yizhou Sun, Yuxiao Dong, Fei Wu, and Yueting Zhuang. Mining fraudsters and fraudulent strategies in large-scale mobile social networks. IEEE Transactions Knowledge and Data Engineering, 2019.
Xu Yuan, Na Zhou, Shuo Yu, Huafei Huang, Zhikui Chen, and Feng Xia. Higher-order structure based anomaly detection on attributed networks. In 2021 IEEE International Conference on Big Data (Big Data), 2021.
Ye Q et al Yuan H, Zheng J. Improving fake news detection with domain-adversarial and graph- attention neural network. Decision Support Systems, 2021.
Jiaqiang Zhang, Senzhang Wang, and Songcan Chen. Reconstruction enhanced multi-view con- trastive learning for anomaly detection on attributed networks. IJCAI, 2022.
Yu Zheng, Ming Jin, Yixin Liu, Lianhua Chi, Khoa T Phan, and Yi-Ping Phoebe Chen. Genera- tive and contrastive self-supervised learning for graph anomaly detection. IEEE Transactions on Knowledge and Data Engineering, 2021.
Xiaojin Jerry Zhu. Semi supervupe learning literature survey. 2005.
12

---

Published as a conference paper at ICLR 2024
A DATASET DETAILS
A.1 ANOMALY INJECTION DETAILS
Anomalous nodes in seven real-world datasets are generated by the standard injection approach, including contextual anomaly and structural anomaly:
Contextual Anomaly. Contextual anomalies are nodes whose features are significantly different from neighboring nodes. nodes chosen randomly to be regarded contextual anomalies, while for each node i, n random nodes are selected as candidates. Among the candidates, node is chosen with the largest Euclidean distance with node i: ||æ; æyll² and replace the feature a; with zz-- Therefore, m nodes are injected as contextual anomalies. We follow previous works to set 50.
Structural Anomaly. Structural anomalies are nodes densely connected rather than sparsely con- nected regular nodes. We randomly select m nodes and make them fully connected form clique, and all m nodes are regarded as structural anomalies. The above process is repeated n times, result- ing the injection of structural anomalies. We follow previous works to set m 15.
A.2 ADDITIONAL DATASET INFORMATION
For datasets with injected anomalies, we keep two types of anomalies occupy the same proportion. For five benchmark datasets Cora, Citeseer, Pubmed, ACM, and BlogCatalog. we inject the same number of anomalies as the previous works. For two large datasets, inject no more than 5% of anomalies. More details are shown in Tab. 4
Table 4: Statistics of the datasets.
Dataset
#Nodes
#Edges
Degree
#Anomalies
Ratio
Cora
2,708
5,429
2.0
150
5.5%
Citeseer
3.327
4,732
1.4
150
4.5%
Pubmed
19,717
44,338
2.3
600
3.1%
ACM
16,484
71,980
4.4
600
3.6%
BlogCatalog
5,196
171,743
33.1
300
5.7%
ogbn-Arxiv
169,343
1,166,243
6.9
6000
3.5%
ogbn-Products
2,449.029
61,859,140
25.3
90000
3.6%
Books 10,984
1.418
3,695
2.6
28
2.0%
Reddit
168,016
15.3
366
3.3%
Cora, Citeseer, Pubmed, and ACM are widely used citation networks. In these networks, nodes denote papers and edges denote citations between them. The feature node sparse bag-of- words vector extracted from paper.
BlogCatalog social network platform that allows users to publicly share their blogs. The net- work structure is defined by the follower-follower relations. The node attributes consist of a list of tags that describe users and their interests.
ogbn-Arxiv is large-scale academic paper citation network, where nodes represent papers and edges represent the citations between them. Each node comes with a 128-dimensional feature vec- tor obtained by averaging the embeddings of words in its title and abstract. The embeddings of individual words are computed by running the skip-gram model over the MAG corpus.
oghn- Products is an Amazon product co-purchasing network, where nodes represent products sold in Amazon, and edges between two products indicate that the products are purchased together. Node features generated by extracting oog--ffwordd features from the product descriptions followed by a Principal Component Analysis (PCA) to reduce the dimension to 100.
Books is co-purchase network from Amazon. The attributes of nodes include prices, ratings, number of reviews, etc. The ground truth labels are derived from amazonfail tag information.
Reddit is usbr-subreddit graph from the social media platform Reddit. The 1,000 most active sub- reddits and the 10,000 most active users are extracted as subreddit nodes and user respecteyp......yy. Each user has binary label indicating whether it has been banned by the platform, and the banned
13

---

Published as a conference paper at ICLR 2024
users treated anomalies. The text of posts is converted into a feature, and the feature of users and subreddits are feature sunmation of posts they have.
B
ADDITIONAL EXPERIMENT SETTINGS AND DETAILS
B.1 ENVIRONMENTS
Libraries that method relies follows: Python=3.7, CUDA=11.6 torch=1.12, dgl=0.9.0, networkx=2.6.3. For unsupervised baselines, we use benchmark implementations with pygod=0.3.0
B.2 HARDWARE
experiments are performed on Tesla V100 GPU with 32GB memory.
B.3 DESCRIPTION OF BASELINES
DOMINANT utilizes GCN encoder extract embeddings. Then the adjacent ma- trix is reconstructed through the inner product of embeddings, and the feature matrix is reconstructed through another GCN.
AnomalyDAE utilizes dual autoencoders with attention mechanisms reconstruct the ad- jacent matrix and feature matrix.
AdONE employs two autoencoders to reconstruct the adjacent matrix and feature matrix respectively. The effect of abnormal nodes on other nodes is minimized in the process of encoding in decoupled way.
CoLA adopts contrastive learning and uses GCN for node embedding, Two subgraphs are sampled via random walking for each node to form contrastive instances. The anomaly score is obtained based on the similarity difference between the central node and the two subgraphs.
ANEMONE proposes a multi-scale contrastive approach based on CoLA,, which further improves the detection performance.
SL-GAD and CoLA share similar contrast structure, but with distinctive feature in SL- GAD. In SL-GAD, two positive instance subgraphs and two negative instance subgraphs sampled for each node, creating contrast instance pairs. This approach results in the formation of a multi-view contrast pattern. Furthermore, SL-GAD employs the posi- tive instance subgraphs for reconstructing the center node, incorporating the reconstruction етrоr into its anomaly score computation.
CONAD proposes four anomaly types as prior human knowledge, and injects them into the graph with data augmentation. Contrastive learning is employed to guide the model to generate different representations for anomalies, and the anomaly score is obtained through reconstruction error.
Sub-CR employs graph diffusion structure enhancement, samples subgraphs from both the original graph and augmented graph and treats them as contrastive instances in local and global perspectives. Then multi-view contrastive learning and reconstruction used to generate the final anomaly score.
ResGCN employs GCN for node representation learning while simultaneously reconstruct- ing attribute and adjacency matrices. In addition to this, it employs MLP to model the attribute matrix, resulting in a residual matrix. This approach is grounded in the intuition that larger residuals indicate higher likelihood of node being anomaly. The residual values are harnessed as attention coefficients, regulating the information flow within and around the node in the GCN, Finally, the cumulative residual value is utilized to compute the anomaly score.
ComGA identifies structural anomalies as nodes located at the edges different communi- ties that are connected to each other, which diverges from the current consensus. It focuses on making nodes within various communities distinguishable from one another, thus avoid- ing "global smoothness'. To accomplish this, ComGA employs autoencoder to model
14

---

Published as a conference paper at ICLR 2024
the modular matrix and integrates it with GCN enable nodes acquire community- aware features. The anomaly scores are derived from the combined reconstruction errors of the adjacency matrix, identity matrix, and modular matrix.
B.4 ADDITIONAL DESCRIPTION OF RELATED WORKS
In this section we provide complementary introduction methods that are not described in detail in related work:
AEGIS (Ding et al. 2021 mainly focuses inductive learning, including anomaly-
aware GNN layer and gives the model the ability to detect new anomalies by generative adversarial learning.
VGOD (Huang et al., 2023) is designed specifically for two types of anomalies. It uses autoencoder to reconstruct the nodes and the reconstruction error used to detect the con- textual anomaly. At the same time, it uses the variance of the node's neighborhood features as a measure the structural anomaly score, and finally the two anomaly scores are jointly used as the criteria for anomaly detection.
AHEAD YYng et al. 2023) is designed for anomaly detection in heterogeneous graphs. Three types of attention are designed for the encoder, and three types of reconstruction are used after the decoder. This design aims to achieve heterogeneity-awarc unsupervised graph anomaly detection.
GraphBEAN (Fathony et al. 2023) is designed for bipartite bode-and-edge-atriinn graphs, and detects anomalous nodes and edges simultaneously. Taking the example of consumer- consumer-purchase-pe purchase-produce graph, GraphBEAN is designed to detect edges representing anomalous transactions, and users with anomalous behavior.
ACT (Wang al. 2023) focuses cross-domain graph anomaly detection (CD-GAD), which describes the problem of detecting anomalous nodes an unlabeled target graph using auxiliary, related source graphs with label nodes.
B.5 EVALUATION METRICS
ROC-AUC. AUC computes the Area Under the Receiver Operating Characteristic Curve from pre- dicted anomaly scores. The ROC curve is created by plotting the true positive rate against the false negative rate at various thresholds. In this paper, closer to 1 means that the model is more capable of recognizing anomalies.
regard anomalies positive samples. AUC
Average Precision. AP provides insights into the precision of anomaly detection various decision thresholds. calculates the area under the Precision-Recal curve, which balances the effects of precision and recall. And higher AP indicates a lower false-positive rate and false-negative rate.
Recall@k. Recall@k assesses the model's ability to identify anomalies among the top k ranked instances. It measures the proportion of true anomalies captured within the selected k instances, where we set k as the number of anomalies in each dataset. A higher Recall @k score signifies the detector's efficacy in giving priority outlier detection over normal samples.
B.6 MORE HYPERPARAMETER SETTINGS
The proposed model consists of two training stages: local inconsistency mining and global consis- tency discernment, The layer of MLP in each module is set to 1. The number of epochs, batch size, and learning rate for these two modules on each dataset are shown in Tab. 5
C ADDITIONAL. EXPERIMENTAL RESULTS
In this section we provide experimental results under the Average Precision and Recall @k metrics shown in Tab. and Tab. respectively
15

---

Published as a conference paper at ICLR 2024
Table 5: More details of hyperparameter settings, denotes full batch. Local denotes local incon- sistency mining and Global denotes global consistency discernment.
Local epoch
Global epoch
Dataset
Batch size
Ir
Cora
100
le-3
50
5e-4
Citeseer
100
le-3
50
5e-4
0
Pubmed
300
le-3
200
5e-4
ACM
100
le-3
30
5e-4
0
BlogCatalog
2000
2e-3
30
4e-4
0
ogbn-Arxiv
2000
2e-3
1000
4e-4
0
oghn-Products
10
le-4
10
3e-4
512
Books
100
lc-3
5
le-5
0
Reddit
100
5e-4
50
5e-4
0
Table 6: Average precision comparison on nine benchmark datasets.(Firg) Second) OOM: out of memory even if the batch size is set 32.
Method
Cora
Citeseer
Pubmed
ACM
BlogCatalog
oghn-Arxiv
ogbn-Products
Books
Reddit
DOMINANT
0,2010
0.2106
0.3176
0.1774
0.1519
OOM
OOM
0.019
0.037
AnomalyDAF
012831
0.2464
0.3037
0.2626
0,1658
0.1920
OOM
0.0194
0.040
AdONE
0,2331
0.3065
0.3733
0.2638
0,1811
OOM
OOM
0.0202
0.0320
0.4700
0.3846
0.3465
0.2056
0,0023
ANEMONE
0.4483
0.4211
0.4644
0.3399
0.1804
OOM
OOM
0,0072
0.0415
SL-GAD
0,5232
0.4883
0.4861
0.3915
0,2683
OOM
OOM
0.0123
0.0330
CONAD
0.2101
0.3065
0.4038
0,3612
0,2132
OOM
OOM
0.0192
0.0326
Sub-CR
0,6240
0.4867
0,5413
0.4310
0.2438
OOM
OOM
0.0213
0.0463
ResGCN
0.4469
0.6446
0.3648
0.3804
0,2205
OOM
OOM
0.0179
0,0396
ComGA
0.5799
0.5823
0.5247
0.4128
0,2579
OOM
OOM
0.0259
0.0461
GADAM
0.7280
0.7512
0.4264
0.4446
0.2960
0.1948
0,2469
0.0279
D DETAILED TIME COMPLEXITY ANALYSIS
this section we analyze detail the time complexity the baselines, and present the results in Tab. [ for easy comparison. The number of layers of the encoder and the dimension of node embeddings are considered constant for simplicity. and N denote the number of edges and the number of nodes in G. is the number of sampling neighbors for each node, R is the number of evaluation rounds, c is the number of nodes within the local subgraph, w the average node degree of G, and n is the number of nodes for data augmentation.
D.1 DOMINANT
The time complexity of DOMINANT is mainly focused (1) employing GCN for representation learning for all nodes, which is ONN) = Ó(E), (2) reconstructing the adjacency matrix takes O(N²), and (3) reconstructing the feature matrix through another GCN, which is also OEE). Over- all, the time complexity of DOMINANT OE + N2).
D.2 ANOMALYDAE
AnomalyDAE has almost the same framework as DOMINANT, but utilizes a graph attention net- work (GAT) for representation learning. So the time complexity of AnomalyDAR is also OEE+N2).
16

---

Published as a conference paper at ICLR 2024
Table 7: Recall @k comparison on nine benchmark datasets. even if the batch size is set to 32.
(First (First Second) OOM: out of memory
Method
Cora
Citeseer
Pubmed
ACM
BlogCatalog
ogbn-Arxiv
ogbn-Products
Books
Reddit
DOMINANT
0.2388
0.2306
0.3476
0.1500
0,1998
(OM
OOM
0.0096
0.0095
AnomalyDAE
0.4451
0.3315
0.3885
0.2634
0,3162
0.1920
OOM
0.0116
0.0402
AdONE
0.3499
0.2969
0.3903
0.2543
0.2039
OOM
OOM
0.0239
0.0282
CoLA
0.4533
0.4067
0.4718
0.3478
0.2883
0.1997
OOM
0,0003
0.0463
ANEMONE
0.4768
0.4132
0.4560
0.3915
0,3029
OOM
OOM
0.0129
0.0534
SL-GAD
0.6155
0,4855
0.4251
0,3810
0,3274
OOM
OOM
0.0125
0.0473
CONAD
0.4253
0.3217
0.3699
0.3109
0.2229
OOM
OOM
0,0054
0.0177
Sub-CR
0.6684
0,5167
0.4713
0.4452
0,3142
OOM
OOM
0.0145
0.0553
ResGCN
0.5401
0.4855
0.3699
0.3810
0,2653
OOM
OOM
0.0072
0.0577
ComGA
0.6365
0.5576
0.3748
0.4334
0.2928
OOM
OOM
0.0094
0.0545
GADAM
0.7299
0.7120
0.4620
0.4590
0.3667
0,3212
0.2553
0.0143
0.0699
Table 8: Comparison of time complexity.
Method
Overall Complexity
Preproessing/Anggmeettiii Contrastive Learning
Reconstruction
DOMINANT
OIE + N²)
OiE + N2)
AnomalyDAE
OIE x2)
O(E+NN)) ((Nx)
AdONE
((NK)
O(N) R(w
CoLA
D(cNR(c+w))
O(
ANEMONE
OieNR(c+u))
O(eNRw)
O((NR)
SL-GAD
O(eNR(c
O(eN (aw) O(nw)
O(PNR)
CONAD
Olnw N
O(g)
OLE N²)
Sub-CR
+ ONN +eN(+++ w))
O(N ((N+)NN)
O(eN)
O(2N) O1E+ N2) O(E+N9)
ResGCN
O(E + N2)
ComGA
OIE + N2)
O(N9)
GADAM (ours)
OiE+ N)
O(E+N)
D.3 ADONE
(1) AdONE first employs random walk with restart to get enhanced graph structure:
T
Å p' = D-
= p
Σ
where P E N is the transition matrix, D is the degree matrix, and A is the adjacent matrix of G. In practice, T is a small constant, and the computation can be performed by a sparse operator in PyTorch D is diagonal matrix. So the time complexity is O(N).
(2) AdONE employs two MLP-based autoencoders to reconstruct the adjacent matrix and feature matrix respectively, the time complexity is O(N).
(3) AdONE also samples & neighbors for each node, and measures the homophily of nodes using the difference between node and neighbor features. The time complexity for node is (x), and the total time complexity becomes O(Nk), Overall, the time complexity of AdONE is (Nn).
D.4 CoLA
The time complexity of CoLA is mainly focused on three components:
(1) Instance pair sampling, the time complexity of each random walk with restart subgraph sampling is O(w)) In the inference phase, rounds sampling for each node are performed, then the total time complexity becomes (cw RN).
(2) GCN-based contrastive learning model, the time complexity mainly generated by the GCN module, which is (c²) for each pair andO( N R)) for total.
(3) For anomaly score computation, the time complexity is far less than the above two phases, so here ignore this term. To sum up, the overall time complexity of CoLA is O(eN R(c w)).
17

---

Published as a conference paper at ICLR 2024
D.5 ANEMONE
ANEMONE has the same framework as CoLA, with an additional contrastive perspective. So the time complexity of ANEMONE is also O(eN
D.6 SL-GAD
SL-GAD and CoLA share the same contrast learning model, but also use adjacency subgraphs to generate a representation of the central node and reconstruct it. So the time complexity SL-GAD also O(eN R(c + w)).
D.7 CONAD
The time complexity of CONAD is mainly focused on three components: (1) Data augmentation module, which selects nodes and performs four types of augmentation approaches as shown in Tab[9 The time complexity of 'Dense' and 'Outlying' is ((w)), and (n) for 'Deviated' and 'Dis- proportionate'. So the time complexity ofthe data augmentation module is (nw)) (2) Contrastive learning based on node representation learning through GAT, which is (EE). (3) Reconstructing the adjacency matrix takes ((N2)), and reconstructing the feature matrix through another GAT, which is OEE). So the time complexity of reconstruction is OEE + 2 To sum the overall time complexity of CONAD O(nw + + N2).
Table 9; Data augmentation approaches of CONAD.
Anomaly types
Prior Knowledge
Augmentation Approach
Dense Outlying Devialed Dispruportionate
Anomalies has unusually high degree
Randomly connect with other nodes Drop most their edges
Anomalies unusually low degree
Anomalies has deviated attribule from neighbors
Replace their features using the approach in A.1 Largely scale scale down their attributes
Anomalies has unusually small or large attribute
D.8 SUB-CR
(I) Sub-CR first employs graph diffusion as structure enhancement:
= a(T (1 D -
where A E NNN is the adjacent matrix of G, is the identity matrix, and D is the degree matrix. In practice, the computation can be performed by a sparse operator PoTcch, as and D are both diagonal matrices. So the time complexity is O(N).
(2) Sub-CR adopts the same strategy as CoLA for instance pair sampling but without R-round sam- pling in the inference stage, the the time complexity is ((New).
(3) Sub-CR employs GCN for contrastive learning, the time complexity is mainly generated by the GCN module, which is O)2
(4) Reconstructing the feature matrix through another GCN, which also Nc² To sum up, the overall time complexity of Sub-CR is O(N + eN New) O(N + cN(c+
D.9 RESGCN
The time complexity of ResGCN can be broken down into two main components: (1) The time complexity associated with residual learning using an MLP for the adjacency matrix A is denoted as OEE). (2) The time complexity related to node representation learning using GCN, involving the reconstruction of adjacency subgraph, feature matrix, and adjacency matrix, represented as OEE + N2). Thus the overall complexity is O(E + N2).
D.10 COMGA
(1) In ComGA, the MLP with L layers serves as an autoencoder for both representation learning and the reconstruction of the modular matrix B NNN N The time complexity for representation learn ing O(N), with the number of MLP layers being disregarded. Mcanwhile, the time complexity for reconstruction is ((N2).
18

---

Published as a conference paper at ICLR 2024
(2) Additionally, ComGA utilizes GCN for node feature learning and reconstructs both the adjacency and feature matrices, incurring time complexity of O(E + N²).
Consequently, the overall complexity of ComGA is OEE + N2)).
D.11 THE PROPOSED GADAM
By ignoring the number of layers of encoder and the dimension of node embedding, the time com- plexity of GADAM simplifies to:
(1) For MI.P-based LIM, the main time complexity node representation learning which O(N).
(2) For local-context aware message flow, the time complexity is mainly generated by node repre- sentation learning through MLP, which is O(N); and hybrid attention, which is O(Nw) for pre- attention and (Nw)) for post-attention. For anomaly score combination, the time complexity is ignored.
To up. the overall time complexity of GADAM is O(N + NN OIE +
E VISUALIZATION OF ATTENTION
In this section, we present visualization of the attention coefficients to provide an intuitive under- standing of how attention evolves for different types of nodes during the training process. Fig. illustrates the dynamics of attention across three benchmark datasets.
amrcctan uromalio
contertull ancmaalis
0.75
booka
sodeo
Attantion
Attonttonn
0.38
0.25
-025
20
50
15
300
500
(a) Citeseer
BlogCatalog
(c) ogbn-Arxiv
Figure 6: Changes in mean attention values for different node types across the training of the second stage. The X-axis represents the training epoch.
Based the results depicted in Fig. 6 the following key observations can be made:
The attention given normal nodes and structural anomalies exhibits an increasing trend during training, whereas contextual anomalies displays decreasing trend. This aligns with the motivations and objectives behind the hybrid attention mechanism.
The attention given normal nodes and structural anomalies far exceeds that allocated to contextual anomalies. This observation highlights the effectiveness of the hybrid attention mechanism in fine-grained control of node-specific message passing.
Another noteworthy point that our attention is not strictly confined to the interval [o, 1], as demon- strated by the fact that the attention of contextual anomalies drops below O. This design is inspired by Li et al. (2019b). Formally, given the feature of node h and the attention coefficient a, let ep be the embedding of its adjacent subgraph. Then, the adaptive message passing is performed as:
h e, + (1-a).+
When the attention coefficient a > 0, it signifies that the node integrates information from its surroundings, akin to smoothing operation. Conversely, when the attention coefficient < 0, it suggests that the node is emphasizing its own features with greater weight, akin to a sharpening operation.
19

---

Published as a conference paper at ICLR 2024
F THEORETICAL GUARANTEE OF GADAM
Inspired by Chen al. (2022),
provide theoretical guarantee for the second stage of GADAM in this section. We begin with the formal problem statement. Given graph g containing N nodes, let h4 be the embedding of node 2; and let q the embedding for global context. Let yi be the label of node us, where y; O corresponds to normal nodes, and y/- = indicates abnormal nodes. Assume there are normal nodes and m abnormal nodes, satisfying n + m = N. We consider a relatively simple case by optimizing the loss function defined by Eq 113 where normal nodes pulled closer to q, and the opposite for m abnormal nodes:
L - -EE (log(q h,) log(1 h2),,, where y: 0, y
For better clarity, we use h+ to represent the embedding of normal node, and h to represent the embedding of an abnormal node. We perform mean pooling on all nodes obtain g. thus N (E ht4 + -))=)) Then we have:
Theorem 1: Let X denote the random variable of normal node and pt denote its marginal dis- tribution, thus X+ ~ p+(++). Likewise, we denote the abnormal node by X and its marginal distribution by p-. Assume pt and p- mutually independent. Then have: minimizing the loss L forms the lower bound of I) the cross-entropy of the two data distributions pt and p plus 2) the entropy of p Formally,
min L max [H(p ,p+) + H(p
(14)
Proof of Theorem 1:
=
Ext loo[g"
h+t))) h Ex- log(1 q h-)
(15)
first
second
The first term in (5) pulls normal nodes and global context closer, and the second them pushes abnormal nodes and global context away. Then for the first term, we have:
h Th+=
hh (hh))a
Note that >> m and the similarity between normal nodes is predominant and usually large, so the term hh htt is naturally large. Asymptotically, suppose we have q" h+ 1, then minimizing L equivalent to maximizing the second term, and we have:
(lgg( g² h] < log F. q" h
log( E.p lg h-])
The first inequality follows the Jensen Inequality based the concavity of the log function, namely log(E(x)] 2 E[log())]. Therefore we consider the upper bound of the second term:
max F bー)) < max ( h/1))
20

---

Published as a conference paper at ICLR 2024
We omit the log and convert the negative sign to get:
max log (-E,- Er 1)"
= min Ex la" h-]
min
Eg
(15
h + Σ (15))K7
j=1
n ( hj
m
min
+ min
Σ
1 hig
N
m
min
log
(4T)) + log
1=1
1 m
min
log
(h + log m
m
min [- H( ,p*) (p ) + log ZeMp]
Inspired by the entropy estimation operation in Wang Isola (2020), the last equality can be viewed as a resubstitution entropy estimator of h+/ (Lin 1976) via von Mises-Fisher (vMF) kernel density estimation (KDE), where log ZeMP is the normalization constant.
G DETECTION PERFORMANCE ON STRUCTURAL AND CONTEXTUAL ANOMALIES
In this section, we study the performance of different algorithms on two types of injected anomalies, along with nodes that exhibit a dual type by manifesting both contextual and structural anomalies (referred to as combined anomalies).
G.1 PERFORMANCE ON STRUCTURAL. AND CONTEXTUAL ANOMALIES
Three benchmark datasets employed in experimentation: Cora serves small, regular dataset with a low average node degree. ACM, on the other hand, represents a larger dataset with substantial number of anomalies. Finally, BlogCatalog is characterized by large average node degree, presenting a greater challenge for the detection of structural anomalies. We also selected four representative methods in the baseline families described in Sec. 4.1 to form comparison experiment: DOMINANT, CoLA, Sub-CR and ComGA. Performance under AUC-ROC metire is repoted in Tab. 10
Table 10: ROC-AUC comparison on two types of anomalies. (First Second)
Cora Contextual
ACM
BlogCatalog Contextual Structural
Method
Structural
Contextual Structural
DOMINANT
0.7173
0.9312
0.7045
0,8182
0.7371
0.7664
CoLA
0.8934
0.8213
0.9103
0,8325
0,8585
0.7325
Sub-CR
0.9057
0.9293
0.7067
0.7913
0.8267
0.7573
ComGA
0.8173
0.9052
0.7525
0.8989
0.8294
0.7679
GADAM 0.9416
0.9929
0.9586
0.9721
0.8499
0.9094
The results show that:
Most of the baselines struggles balance the detection of both types of anomalies, while GADAM achieves the best.
On the two sparser datasets, Cora and ACM, GADAM significantly outperforms base- lines in structural anomaly detection. Even the denser BlogCatalog dataset, GADAM continues to outperform all baselines, providing further validation of the effectiveness for structural anomaly detection.
21

---

Published as a conference paper at ICLR 2024
Table 11: ROC-AUC comparison on combined anomalies. (First Second)
Cora = 15
Citeseer
Pubmed
ACM
BlogCatalog
Method
= 15
60
60
30
DOMINANT
0.8354
0.8498
0.7904
0.7448
0.7723
CoLA
0.8976
0.8928
0.9618
0.7909
0.7965
Sub-CR
0,9236
0.9400
0.9810
0.7518
0.7963
ComGA
0.8828
0.9335
0,9255
0.8433
0.8275
GADAM
0.9970
0.9994
0.9863
0.9884
0.9685
G.2 PERFORMANCE ON COMBINED ANOMALIES
To further explore the performance of the model combined anomalies we generated certain number of mixed anomalies on the three benchmark datasets. Specifically, we randomly select structural anomalies and employed the contextual anomaly injection method outlined in Appendix A.1 to substitute features for these nodes, thereby creating mixed anomalies. The detection per- formance on five benchmark datesets under the AUC-ROÇ metric is presented in Tab. [1
The results show that GADAM has superior detection performance for combined anomalies. This success can be attributed to the first stage of GADAM captures well the contextual abnormal features exhibited by mixed anomalies. Moreover, in the second stage, GADAM facilitates the absorption of anomalous signals from the neighboring structural anomalies through adaptive message passing. further enhancing the detection of mixed anomalies.
22


Reviews:
[{"review_id": "1YPycJpAX9", "reviewer": "Reviewer_WYWU", "summary": "This paper addresses the problem of unsupervised node-level anomaly detection in a graph through an adaptive message passing framework. The paper rightly motivates the fact that message passing in GNNs results in local anomaly signal loss. The authors have proposed an approach to obtain local and global anomaly scores through MLP and hybrid attention based adaptive message passing. The paper has conducted experiments on anomaly detection on real world datasets with both injected and ground truth anomalies, and used a good number of baseline approaches from the literature.", "questions": "Please see the questions above.\n\n***********************************\n\nAfter Rebuttal: The authors have tried to address all the concerns I had. I am changing my score from 3 to 5. I believe the paper needs a major revision to incorporate the recommended changes and the new experiments. I don't mind if this paper gets accepted in ICLR 2024 with those changes.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The idea of using local anomaly score to compute the global anomaly score is interesting.\n2. The paper uses a good number of baseline algorithms from the literature.", "weaknesses": "1. The problem formulation seems to be problematic. Authors have mentioned \"Structural anomalies are densely connected nodes in contrast to sparsely connected regular nodes\". What about the networks that are dense by nature? Moreover, if density is the only criteria for being a structural anomaly, why can't we use degree of a node as the metric to find the structural anomalies? Are we over-complicating the solution of a relatively simple problem?\n\n2. I am not convinced with the proposed solution. s^local (in Eq. 6) can only capture contextual anomalies, but not the structural anomalies because of the L2 normalization in Eq. 3. Where exactly are we capturing the structural anomalies in this framework?\n\n3. What is the difference between H_local and H_global? They seem to be computed in the same way through Eq. 3. Why are we calling the second one as \"global\"?\n\n4. Some of the claims in the paper should have been explained more. Can you please elaborate the reason of \"as the training advances, the influence of pre-attention gradually diminishes, while the opposite for post-attention\".\n\n5. In Table 1, overall anomaly detection performance is reported. I am curious to see the performance on contextual and structural anomalies separately.\n\n6. As mentioned before, degree centrality seems to be a good metric to capture the structural anomalies. Can you please include this heuristic as a baseline to compare with?\n\n7. How do you capture the nodes which are both contextual and structural anomalies? Also, will your approach be able to capture \"Combined Outliers\" (or combined anomalies) as introduced in \"Outlier Aware Network Embedding for Attributed Networks\" (AAAI-2019)?", "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": "faPlI9ge1g", "reviewer": "Reviewer_deYB", "summary": "The authors investigate the two main paradigms, both used in many unsupervised graph anomaly detection models, message passings (MP) and local inconsistency mining (LIM). Traditionally, many graph anomaly detection models utilize the LIM for determining nodes that have inconsistency with their surroundings and mark them as anomalous. However, the use of MP with many GNN layers tends to smooth out everything, which decreases the contrastive difference between a node and its surroundings. The authors aim to address this conflict by proposing GADAM, a method that first performs LIM via a regular MLP network to get local anomaly scores without using message passing. It then combines these local scores with global scores that use an attention-based adaptive message passing that enables nodes to selectively absorb normal/abnormal signals from their surroundings. The authors then demonstrate the benefit of the models compared with baselines on several public datasets.", "questions": "Please answer my questions in the previous section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Strengths:\n- An interesting approach in unsupervised anomaly detection. The over-smoothing problem is a well-known problem in GNN, and it may impact the performance of GNN-based anomaly detection models. Most unsupervised graph anomaly detection models work by finding inconsistent nodes among the neighbors. The use of message passing in GNN may impact the finding as the over-smoothing problem may make the nodes less inconsistent.\nI would argue that the conflict between LIM and overs-smoothing could be resolved within a message-passing framework by designing a better message-passing flow, imposing stricter bottlenecks in the encoder-decoder process, or other means. However, the paper proposed a different way outside the message-passing framework.\n\n- The methods combine both local perspective and global perspective to create combined perspective anomaly scores.\n- The authors demonstrate the benefit of the model against many GNN baselines", "weaknesses": "I have a few concerns and questions regarding the paper:\n1) In the contrastive pair construction (Section 3.1 item (2)), the authors mentioned that the method uses the complete adjacency subgraph. Does it mean that it includes all 1-hop neighbors? If that's the case, then the receptive field of the method is limited to just the immediate neighbors. This may limit the expressiveness of the model. There may be cases where determining normal/abnormal nodes requires more than just looking at the immediate neighbors. \n2) If in (1), it is not just 1-hop neighbors but all k-hop neighbors, then the size of the subgraphs can be potentially very large in densely connected graphs. How does the model address that?\n3) In the shuffling process, there are some chances that neighboring nodes are accidentally picked as negative pairs. How does the model account for those cases?\n4) The representations of a subgraph G in the local context are just an average of the representation of the node embeddings in G. Then, the anomaly scores for each node are measured by the difference between its node representation and the subgraph representation. It is possible that the node embedding of each neighbor is really different than the target node's embedding, but the average of the neighbor embeddings is similar to the target node. Doesn't it also introduce an over-smoothing problem? It could be worse than the standard message passing, where the aggregation is not just standard averaging but parameterized by a weight matrix. Here, the aggregation is just a plain average.\n5) The use of attention mechanisms may be counter-intuitive in unsupervised anomaly detection that is based on finding abnormal signals from the surroundings. The ability of the attention mechanism to ignore certain signals may make the model ignore suspicious signals, which will result in an abnormal case tagged as a normal case. Has the author tried to replace the attention mechanism with another mechanism, like convolution, that forces the model to utilize all signals?\n6) The experiment results of the baselines presented in the paper are rather different from the ones reported in the original paper for the same datasets. For example, in the original AnomalyDAE paper, the AUC are 97.81 (BlogCatalog), 90.05 (ACM); whereas in this paper, they are 76.58 (BlogCatalog), 75/16 (ACM). Could the authors explain more about it?\n7) How to decide topk% included in the second stage. How does the selection of this percentage affect the results?\n8) The paper is missing some unsupervised graph anomaly detection papers:\n     - Ding, Kaize, Jundong Li, Nitin Agarwal, and Huan Liu. \"Inductive anomaly detection on attributed networks.\" In Proceedings of the twenty-ninth international conference on international joint conferences on artificial intelligence, pp. 1288-1294. 2021.\n     - Huang, Yihong, Liping Wang, Fan Zhang, and Xuemin Lin. \"Are we really making much progress in unsupervised graph outlier detection? Revisiting the problem with new insight and superior method.\" arXiv preprint arXiv:2210.12941 (2022).\n     - Yang, Shujie, Binchi Zhang, Shangbin Feng, Zhanxuan Tan, Qinghua Zheng, Jun Zhou, and Minnan Luo. \"Ahead: A triple attention based heterogeneous graph anomaly detection approach.\" In Chinese Intelligent Automation Conference, pp. 542-552. Singapore: Springer Nature Singapore, 2023.\n     - Fathony, Rizal, Jenn Ng, and Jia Chen. \"Interaction-Focused Anomaly Detection on Bipartite Node-and-Edge-Attributed Graphs.\" In 2023 International Joint Conference on Neural Networks (IJCNN), pp. 1-10. IEEE, 2023.\n     - Wang, Qizhou, Guansong Pang, Mahsa Salehi, Wray Buntine, and Christopher Leckie. \"Cross-domain graph anomaly detection via anomaly-aware contrastive alignment.\" In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, no. 4, pp. 4676-4684. 2023.", "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": "j0YQh5ScOa", "reviewer": "Reviewer_6vV6", "summary": "The authors propose a model for unsupervised anomaly detection in graphs. In particular, the model focuses on 2 types of anomalies: 1) contextual (a node having attributes that are very different from its neighbors') and 2) structural (dense subgraphs). The innovation is a two-stage model that first uses an MLP to find possible contextual anomalies and then uses a message-passing graph neural network with an attention mechanism to find dense subgraphs of anomalous nodes.", "questions": "- The AnomalyDAE paper reports an AUC of over 97 for the BlogCatalog dataset. Do you have an explanation for the discrepancy in your paper (AUC of 76.58)? Were the authors of that paper injecting anomalies in a totally different way?\n\n- The AUC for Sub-CR, DOMINANT, and  COLA is higher in the Sub-CR paper. Do you think hyperparameters for the baseline models are sufficiently tuned?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Takes inspiration of previous work on contrastive learning and recent work on attention for message passing \n- Competitive time complexity\n- Experimental evaluation is fairly comprehensive and shows modest improvement over existing methods, of which there are plenty", "weaknesses": "- Performance reported for competing methods is lower than in the papers where these methods were proposed. It raises the question of whether the models are sufficiently tuned\n- No comparison to methods in the vast literature outside deep learning / neural networks. See for example https://arxiv.org/abs/1404.4679", "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": "eVAV86405O", "reviewer": "Reviewer_va1S", "summary": "In this paper, the authors address the challenge of unsupervised graph anomaly detection, a crucial task in various real-world applications. Existing methods often conflict in their focus between local inconsistency mining (LIM) and message passing. LIM emphasizes identifying high similarities between abnormal nodes and their neighbors, while message passing, commonly employed by graph neural networks (GNNs), tends to make connected nodes similar, leading to local anomaly signal loss. To reconcile this conflict, the authors propose GADAM, a novel framework that not only resolves the tension between LIM and message passing but also utilizes message passing to enhance anomaly detection through a unique approach to anomaly mining beyond LIM. The effectiveness and efficiency of GADAM are extensively evaluated on nine benchmark datasets, including two large-scale OGB datasets. The results demonstrate that GADAM outperforms existing state-of-the-art methods, showcasing superior effectiveness and efficiency in unsupervised graph anomaly detection.", "questions": "1. How to calculate H_{global} in details?\n2. If there is no prior information about the ratio of anomalous nodes in a given graph, how should one select k_{ano}? If the selected k leads to more anomalies than actual ones, will the proposed method be impacted negatively?\n3. What are the detailed steps in injecting anomalies? What the performance will change if different numbers of contextual or structural anomalies are injected (especially the proposed method first detects local structural anomalies)?\n\n--------------------------\n\nAfter rebuttal, my concerns have been addressed.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The proposed method is technically sound, i.e., to overcome the issues of LIM in previous anomaly detection methods.\n- The proposed method has been tested on both synthetic and real-world anomalies and the experimental results show the effectiveness of the proposed method.\n- The conducted experiments are comprehensive including performance comparison, efficiency comparison, and ablation studies.", "weaknesses": "- Although the effectiveness and efficiency of the proposed method have been empirically studied from different aspects, this is no theoretical guarantee of the proposed method.\n- The first step of MLP-based LIM aims to identify local anomalies only. However, if the given data contains more contextual anomalies, will the proposed method fail to capture them?\nThe influence of different types of anomalies on the proposed method is not discussed.", "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)