Truncated Affinity Maximization: One-class Homophily Modeling for Graph Anomaly Detection
Authors: Hezhe Qiao
Guansong Pang
Venue: NeurIPS 2023 poster (2023)
Keywords: Anomaly Detection
Graph Neural Network
Graph Anomaly Detection
One-Class Homophily
Local Node Affinity
TL;DR: We empirically reveal a one-class homophily phenomenon in graph anomaly detection (GAD) datasets and utilize it to introduce a novel unsupervised anomaly measure and model for accurate GAD

Abstract: We reveal a one-class homophily phenomenon, which is one prevalent property we find empirically in real-world graph anomaly detection (GAD) datasets, i.e., normal nodes tend to have strong connection/affinity with each other, while the homophily in abnormal nodes is significantly weaker than normal nodes. However, this anomaly-discriminative property is ignored by existing GAD methods that are typically built using a conventional anomaly detection objective, such as data reconstruction.
In this work, we explore this property to introduce a novel unsupervised anomaly scoring measure for GAD -- local node affinity-- that assigns a larger anomaly score to nodes that are less affiliated with their neighbors, with the affinity defined as similarity on node attributes/representations.  We further propose Truncated Affinity Maximization (TAM) that learns tailored node representations for our anomaly measure by maximizing the local affinity of nodes to their neighbors. Optimizing on the original graph structure can be biased by non-homophily edges(i.e., edges connecting normal and abnormal nodes). Thus, TAM is instead optimized on truncated graphs where non-homophily edges are removed iteratively to mitigate this bias. The learned representations result in significantly stronger local affinity for normal nodes than abnormal nodes. Extensive empirical results on 10 real-world GAD datasets show that TAM substantially outperforms seven competing models, achieving over 10% increase in AUROC/AUPRC compared to the best contenders on challenging datasets. Our code is available at https://github.com/mala-lab/TAM-master/.

Truncated Affinity Maximization: One-class Homophily Modeling for Graph Anomaly Detection
Hezhe Qiao, Guansong Pang"
School of Computing and Information Systems, Singapore Management University smu. edu. gspangesmu. edu. sg
hezheqiao.. sccheqiao.2222phhdes. 2022@phdcs
Abstract
We reveal one-class homophily phenomenon, which is one prevalent property we find empirically in real-world graph anomaly detection (GAD) datasets, i.e, normal nodes tend have strong connection/affnity with each other, while the homophily in abnormal nodes is significantly weaker than normal nodes. However, this mnomaly-dissriiinen
property is ignored by existing GAD methods that are typically built using a conventional anomaly detection objective, such as data reconstruction. In this work, we explore this property introduce novel unsu- pervised anomaly scoring measure for GAD local node affinity that assigns larger anomaly score to nodes that are less affiliated with their neighbors, with the affinity defined similarity on node attributes/reppesenaatiins We further propose Truncated Affinity Maximization (TAM) that learns tailored node repre- sentations for our anomaly measure by maximizing the local affinity of nodes to their neighbors. Optimizing on the original graph structure can be biased by non- homophily edges (i.e., edges connecting normal and abnormal nodes). Thus, TAM is instead optimized on truncated graphs where noo-holophily edges are removed iteratively to mitigate this bias. The learned representations result in significantly stronger local affinity for normal nodes than abnormal nodes. Extensive empirical results 10 real-world GAD datasets show that TAM substantially outperforms seven competing models, achieving over 10% increase in AUROC/AUPRC com- pared to the best contenders challenging datasets. Our code is available at https:// https://giin thub. hommmala--1e
Introduction
Graph anomaly detection (GAD) aims to identify abnormal nodes that are different from the majority of the nodes in graph. It has attracted great research interest in recent years due its broad real- world applications, e.g., detection of abusive reviews or malicious/fraudnlen users [9, 62,32,3,5 57]. Since graph data is non-Fuclideea with diverse graph structure and node attributes, it challenging to effectively model the underlying normal patterns and detect abnormal nodes in different graphs. To address this challenge, graph neural networks (GNNs) have been widely used for GAD. The GNN-based methods are often built using a data reconstruction [8, 11 31, 65] or self-supervised learning [15, 17, 28, 54, 63] objective. The data reconstruction approaches focus on learning node representations for GAD by minimizing the errors of reconstructing both node attributes and graph structure, while the self- self-supervised approaches focus on designing proxy task that is related to anomaly detection, such as prediction of neighbor hops [17] and prediction of the relationship between node and a subgraph [28], learn the node representations for anomaly detection.
These approaches, however, ignore one prevalent anomaly discrimiatieeeeeeee property we find empirically in real-world GAD datasets, namely one-class homophily, i.e., normal nodes tend to have strong connection/affinity with each other, while the homophily in abnormal nodes significantly weaker
"Corresponding author: G. Pang
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

than normal nodes. This phenomenon can be observed in datasets with synthetic/real anomalies, as shown in Fig. I(a) (see App. A for results on more datasets). The abnormal nodes do not exhibit homophily relations to each other mainly because abnormal behaviors are unbounded and can be drawn from different distributions.
Motivated by the one-class homophily property, we in- troduce a novel unsupervised anomaly scoring measure for GAD local node affin- ity that assigns a larger anomaly score to nodes that are less affiliated with their neighbors. Since we do not have access to class la- bels, we define the affinity in terms of similarity on node attributes/representttioos to capture the homophily rela- tions within the normal class. Nodes having strong local affinity are the nodes that are connected to many nodes of similar attributes, and those nodes are considered more likely to be normal nodes. One challenge of using this anomaly measure is that some abnormal nodes can also be connected to nodes of similar abnormal behaviors. A straightforward solution this problem is to apply our anomaly measure in a node representation space learned by off-the-shed popular representation learning objectives like DGI [51]. but the representations of normal and abnormal nodes can become similar due to the presence of tto-homophill edges (i.e., edges connecting normal and abnormal nodes) that homogenize the normal and abnormal node representations GNN message passing. To address this issue, we further propose Truncated Affinity Maximization (TAM) that learns tailored node representations for our anomaly scoring measure by maximizing the local node affinity to their neighbors, with the non-homophily edges being truncated to avoid the over-smooth representation issue. The learned representations result in significantly stronger local affinity for normal nodes than abnormal nodes. As shown in Fig. 1(b), it is difficult for using the local node affinity to distinguish normal and abnormal nodes on raw node attributes and DGI-based node representations, whereas the TAM-based node representation space offers well-separable local affinity results between normal and abnormal nodes. In summary, this work makes the following main contributions:
BlgCobllg
ElngCabiin
pkycoo 2g
Bloy.ablllg
Humal
Honamall
2.5
2.0
22
Ex Us 24
Arazss
Arsizn
harna
12
Harell
Nomal
Annernal
2.0
15
23 2. 1.0
04
R6-based WT1T0
officty
Figure 1: (a) Homophily and (b) local affinity distributions of normal and abnormal nodes on two popular benchmarks, BlogCatalog [49] and Amazon [10]. The homophily of a given node is calculated using the number of nodes that have the same class label as the given node [13]. The local affinity is calculated on raw attributes (RA) and node representations learned by DGI [51] and TAM, respectively.
We, for the first time, empirically reveal the one-class homophily phenomenon that provides an anomaly -iiiiiii-ddieiimnnatieeee property for GAD. Motivated by this property, we introduce novel unsupervised anomaly scoring measure, local node affinity (Sec. 3.2).
We then introduce Truncated Affinity Maximization (TAM) that learns tailored node rep- resentations for the proposed anomaly measure. TAM makes full use of the one-class homophily to learn expressive normal representations by maximizing local node affinity on truncated graphs, offering discriminative local affinity scores for accurate GAD.
We further introduce two novel components (Sec. 3.3), namely Local Affinity Maximization- based graph neural networks (LAMNet for short) and Normal Structure- pereturr-peeeeeedd Graph Truncation (NSGT), to implement TAM. Empirical results six real-world GAD datasets show that our TAM model substantially outperforms seven competing models.
2 Related Work
Numerous anomaly detection methods have been introduced, including both shallow and deep approaches [5,37], but most of them are focused on non-graph data. There have been many studies on GAD exclusively. Most of previous work use shallow methods [2], such as Radar [22], AMEN [43],

---

and ANOMALOUS [41]. Matrix decomposition and residual analysis are commonly used in these methods, whose performance often bottlenecked due to the lack of representation power to capture the rich semantics of the graph data and to handle high-dimensional node attributes and/or sparse graph structures.
GNN-based GAD methods have shown substantially better detection performance in recent years [32]. Although some methods are focused on a supervised setting, such as CARE-GNN [10], PCGNN [27], Fraudre [58]. BWGNN [47], and GHRN [12], most of them are unsupervised methods. These unsupervised methods can be generally categorized into two groups: data reconstruction based and self-supervised-bire baaere approach. Below we discuss these most related methods in detail.
Data Reconstruction-basee Approach. As one of the most popular methods, graph auto-encoder (GAE) is employed by many researchers to learn the distribution of normal samples for GAD. Ding et al. [8] propose DOMINANT, which reconstructs the graph structure and node attributes by GAE. The anomaly score is defined as the reconstruction error from both node attributes and its structure. It is often difficult for GAE learn discriminative representations because it can overfit the given graph data. Several mechanisms, including attention, sampling, edge removing, and meta-edge choosing 27,27,30 45], are designed to alleviate this issue during neighborhood aggregation. Some recent variants like ComGA [31] and AnomalyDADi [1I] incorporate an attention mechanism to improve the reconstruction. Other methods like SpaceAE [24] and ResGCN [39] aim to differentiate normal and abnormal nodes that do not have significant deviation, e.g., by exploring residual information between nodes. In general, reconstructing the structure of a node based on the similarities to its neighbors is related to but different from local node affinity in TAM (see Sec. 3.2), and GAE and TAM are also learned by very different objective (see Sec. 3.3). Being GNN-based approaches, both the reconstruction-basse neighborhood information to obtain the anomaly scores, but we explicitly define an anomaly measure from new perspective, i.e., local node affinity. This offers a fundamentally different approach for GAD.
approaches and our approach TAM rely on the node's
Self-supervised Approach. Although data reconstruction methods can also be considered as self-supervised approach, here we focus on non-rcconstruction pre-text tasks for GAD. One such popular method is proxy classification or contrastive learning task [18, 53, 65]. Liu et al. [28] propose CoI.A, which combines contrastive learning and sub-graph extraction to perform self- supervised GAD. Based on CoLA, SL-GAD is proposed to develop generative attribute regression and viewi-view contrastive learning [63]. There are some methods that leverage some auxiliary information such degree, symmetric and hop to design the self-supervised task [6, 7,,23,2,,56 56, 61]. For example, Huang et al. propose the method HCM-A [17] to utilize hop count prediction for GAD. Although some self-supervised methods construct the classification model on the relationship between the node and the contextual subgraph, this group of methods is not related to local node affinity directly, and its performance heavily depends on how the pre-text task is related to anomaly detection. Similar to the self-supervised approaches, the optimization of TAM also relies on an unsupervised objective. However, the self-supervised approaches require the use of some pre-text tasks like surrogate contrastive learning or classification tasks to learn the feature representations for anomaly detection. By contrast, the optimization of TAM is directly driven by new, plausible anomaly measure, which enables end-to-end optimization of an explicitly defined anomaly measure.
3 Method
3.1 The Proposed TAM Approach
Problem Statement. We tackle unsupervised anomaly detection on an attributed graph. Specifically, let G (V, E, X) be an attributed graph, where {u,,- uN} } denotes its node set, & S V x V with e E E is the edge set, Gij- = represents there is connection between node and uj. X E I N denotes the matrix of node attributes and E RM is the attribute vector of Uú and A E (0, NNNN the adjacency matrix of G with A,, = 1 iff (o;, Uy) E E, then GAD aims to learn an anomaly scoring function f : V + R, such that f()) < f()),, Ve E Vn, v' E V., where V, and V,, denotes the set of normal and abnormal nodes, respectively. Per the nature of anomaly, is typically assumed that [v.,| > [Va|. But in unsupervised GAD we do not have access to the class labels of the nodes during training. this work, our problem is to learn an unsupervised local node fffinity-based anomaly scoring function f.
3

---

Graph
XSGT
Drepen Grekk
Aecopll
9
Nodo: Repersentations
@hara Alenmal
Smolemplh
LAMNet
Trancited Edge
Albay Xasitaaio
Prebabilstie Truncation
(b)
Figure 2: Overview of TAM. (a) TAM leverages the observation that normal nodes have stronger affinity relations to their neighbors than anomalies to learn an unsupervised GAD model. It learns set of affinity maximization GNNs (i.e. LAMNet) on a set of sequentially truncated graphs yielded by our probabilistic graph truncation method NSGT. We build an ensemble of TAM models to make use of the randomness in NSGT for more effective GAD. (b) NSGT iteratively removes edges with a probability proportional to the distance between the connected nodes.
Our Proposed F Framework. Motivated by the one-class homophily phenomenon, we introduce local node affinity-basse based anomaly score measure. Since difficult capture and quantify the one-class homophily in the raw attribute space and the generic node representation space, we introduce a truncated affinity maximization (TAM) approach to learn a tailored representation space where the local node affinity can well distinguish normal and abnormal nodes based the one-class homophily property. As shown in Fig. 2, TAM consists of two novel components, namely local affinity maximization-basse graph neural networks (LAMNet) and normal dtructure-rrssevve graph truncation (NSGT). LAMNet trains a graph neural network using a local affinity maximization objective iteratively truncated graph structure yielded by NSGT.
NSGT is designed in way through which we preserve the homophily edges while eliminating non non-homophily edges iteratively. The message passing in LAMNet is then performed using the truncated adjacency matrix rather than the original one. In doing so, we reinforce the strong affinity among nodes with homophily relations to their neighbors (e.g., normal nodes), avoiding the potential bias caused by non-homophily edges (e.g., connections to abnormal nodes). The output node affinity in LAMNet is used to define anomaly score, i.e., the weaker the local affinity is, the more likely the node an abnormal node. There exists some randomness in our NSGT-based graph truncation. We utilize those randomness for more effective GAD by building a bagging ensemble of TAM.
3.2 Local Node Affinity as Anomaly Measure
As shown in Fig. 1, normal nodes have significantly stronger homophily relations with each other than the abnormal nodes. However, we do not have class label information to calculate the homophily of each node in unsupervised GAD. We instead utilize the local affinity of each node to neighbors to exploit this one-class homophily property for unsupervised GAD. The local affinity can be defined as an averaged similarity to the neighboring nodes, and the anomaly score f is opposite to the affinity:
Σ sim (x,,x)) f(u)) -h(ss). h(v.) (eo) ByEN(e.)
(1)
where N (wx) is the neighbor set node v, and sim(x;, |xx ||| measures the similarity of node pair (U:, U)), The local node affinity h(v;)) is normal score: the larger the affinity is, the stronger homophily the node has w.r.t. its neighboring nodes based on node attributes, and thus, the more likely the node is normal node.
The measure in Eq. (1) provides a new perspective to quantify the normality/abnormalty of nodes, enabling a much simpler anomaly scoring than existing popular measures such as the reconstruction error f(;;) = (1 - a)la 2 aillz + ox|ix; - & where a, denotes the neighborhood strueture of U4 a; and x; are the reconstructed structure and attributes for node U, and is hyperparameter.

---

Our anomaly measure also provides a new perspective to learn tailored node representations for unsupervised GAD. Instead of minimizing the commonly used data reconstruction errors, based on the one-class homophily, we can learn anomaly-diseriminati node representations by maximizing the local node affinity. Our TAM approach is designed to achieve this goal.
3.3
TAM: Truncated Affinity Maximization
The local node affinity may not work well in the raw node attribute space since (i) there can be many irrelevant attributes in the original data space and (ii) some abnormal nodes can also be connected to nodes of similar attributes. To tackle this issue, TAM is proposed to learn optimal node representations that maximize the local affinity of nodes that have strong homophily relations with their neighbors in terms of node attributes. Due to the overwhelming presence of normal nodes in a graph, the TAM-based learned node representation space is optimized for normal nodes, enabling stronger local affinity for the normal nodes than the abnormal ones. The TAM- anomaly scoring using local node affinity can be defined as:
STAM (195 O,A.X)
1 (w:)
Σ
sim (h,, by),
e, (N()))
where h; = ((e;; O, A, X) is GNN-based node representation of us learned by mapping function & parameterized by in TAM. Below we introduce how we learn the v/b function via the two components of TAM, LAMNet and NSGT.
Local Affinity Maximization Networks (LAMNet). LAMNet aims to learn a GNN-based mapping function & that maximizes the affinity of nodes with homophily relations to their neighbors, while keeping the affinity of nodes with conhooophhly edges are weak. Specifically, the projection from the graph nodes onto new representations using & GNN layers can be generally written as
( = GNN AA ((-1), W(
where ( E Nx and H (B-1) E NNA are the h(() 2.9-dimensional and dimeeniiial representations of node v, in the (f)-th layer and (e 1)-th layer, respectively. In the first GNN layer, i.., when the input (0) is set to the raw attribute matrix X. W()) are the weight parameters of (f)-th layer. For GNN(.), multiple types of GNNs can be used [50, 55). In this work, we employ GCN (graph convolutional network) [20] due to its high efficiency. Then (#) can be obtained via
H
-
where D = diag (D,) = Aij
Aij is the degree matrix for the graph G, and d(-) is an activation
function. Let H = (h, he...., b be the node representations of the last GCN layer, then the mapping function & sequential mapping of graph convolutions as in Eq. (4), with O {Wi, W ........ W()) be the parameter set in our LAMNet. The following objective then be
used to optimize v::
(FrAM(ee min Σ (TA O, A, + MANN( NEV
Σ sim (h,, ha)
where the first term is equivalent to maximizing the local affinity of each node based on the learned node representations, while the second term regularization term, and À is regularization hyperparameter. The regularization term adds constraint that the representation of each node should be dissimilar from that of non-adjacent nodes to enforce that the representations of non-local nodes are distinguishable, while maximizing the similarity of the representations of local nodes.
The optimization using Eq. (5) can be largely biased by non-homophily edges. Below introduce the NSGT component that helps overcome this issue.
Normal Structure-preserved preserved Graph Truncation (NSGT). LAMNet is driven by the one-class homophily property, but its objective and graph convolution operations can biased by the presence non-homophily edges, ie., edges that connect normal and abnormal nodes. The NSGT component
5

---

is designed to remove these non non- homoohill edges, yielding a truncated adjaceney matrix A with homophily edge-based normal graph structure. LAMNet is then performed using the truncated adjacency matrix A rather than the original adjacency matrix A.
Since homophily edges (i.e., edges connecting normal nodes) connect nodes of similar attributes, the distance between the nodes of homophily edges is often substantially smaller than that of non- homophily edges. But there can also exist homophily edges that connect dissimilar normal nodes. These can be observed in GAD datasets, as shown in Fig. 3(a-b) for datasets with synthetic/real anomalies. Motivated by this. NSGT takes probabilistic approach and performs the graph truncation as follows: for given edge eij 1, it is considered as non-homophily edge and removed (i. e. eij = 0) if and only if the distance between node is and node y is sufficiently large w.r.t. the neighbor sets of both U; and ,,. N(u,) and N(w)). Formally, NSGT truncates the graph by
Eij c 0 iff dij > r; dij Tj Verj 1,
(6)
where dı is a Euclidean distance between o and fy based on node attributes, is a randomly selected value from the range [dmean, di, where dmean J Σ (mg.ny)er dij is the mean distance of graph, where is the number of non-zero elements in the adjacent matrix, and dg. is the maximum distances in {dit. U2 E N.m))]. Similarly, ry is randomly sampled from the range [dmean d ds,max).
Theoretically, the probability of ra < diÿ can be defined
max(di dmean; 0)
(ra < dij))
di,max dmnea
Note that this probability is premised on d, max dmeean and we set (r, < dry) = if di, S
dmean Then the probability of eiş being removed during the truncation process is as follows
p(8 \ eig) p (r: < dry) p (ra < diy),
(8)
As shown in Fig. 2(b), if exj is a homophily edge, we would have small dej. which results in small p (r:- < d:j) and (ry < diz). and thus, p(E \ eij) is also small. By contrast, non-homophily edge would result in a large diy. and ultimately large p(E \ cty). Therefore, NSGT can help eliminate non-homophily edges with a high probability, while preserving the genuine homophily graph structure.
BlogCatalog
Amazon
Considering the large difference in the range [dmean; mar) for each node and the randomness in truncation, NSGT performs sequentially it- erative truncation rather than a single-pass trun- cation. In each iteration it randomly removes some non-homophily edges with probability pro- portional to the distance between their associated nodes, and then it updates the range [dmean, d4 da,mazl for nodes that have edges being removed. Thus, for K iterations on a graph G. would produce set of K sequentially truncated graphs with the corresponding truncated adjacency matrices A A2, . Åx). Note that since the graph is sequentially truncated, we have Ei+1 C &, where E, is the edge set left after the i-th iteration. As shown in Fig. 3(c-d), such sequentially iterative truncation helps largely increase the homophily of the normal nodes, while at the same time effectively removing non- non-homophily edges gradually.
60
Distance
Distance
Nor, hww.hhholllllyyy.oooooooooc adgess
0.554
5.
BiooCabllo Amazar
2,1552
8,500
0.500
Arrazon
Homosphll
Non-Homophlly
Figure 3: (a) and (b) are respectively the Eu- clidean distance statistics of the homophily (N- N) edges that connect normal nodes and the hom-holpp (N-A) edges that connect nor- mal and abnormal nodes on BlogCatalog and Amazon. (c) Homophily of normal nodes vs. (d) the number of non-homophily edges with increasing truncation iterations/depths.
Training. To detect anomalies in different graph truncation scales, we train a LAMNet on each of the K sequentially truncated adjacency matrices in A, resulting in LAMNets parameterized by {0), O ( for various truncation depths. Particularly, for each LAMNet, instead of using A, its graph convolutions across all GCN layers performed on the truncated adjacency matrix AŞ as follows to mitigate the biases caused by the

---

non-homophily edges in message passing:
H 1 ò (D-+A, H ( w((-))
In doing so, we complete the training of TAM-based base model, consisting of K LAMNets.
Further, being a probabilistic approach, NSGT has some randomnesses in the graph truncation, and so does the LAMNets. To make use of those randomness, we build an ensemble of TAM models with size of I', shown in Fig. 2(a). That is, for graph G, we perform NSGT T times independently, resulting in T' sets the truncated adjacency matrix set (21, Ar}, with each A (A1, A..... A K) }. We then train a LAMNet on each of these x adjacency matrices, obtaining an ensemble of T TAM models (i.e., T K LAMNets).
Note that in training the LAMNets, the local affinity the first term in Eq. (5) is computed using the original adjacency matrix A. This is because we aim to utilize the primary graph structure for local affinity-based GAD; the graph truncation is designed to mitigate the graph convolution biases only.
Inference. During inference, we can obtain one local node affinity- basee anomaly score per node from each LAMNet, and aggregate the local affinity scores from all T x K LAMNets compute an overall anomaly score as
T
score (us)
STAM (ve o7 A, X),
(10)
T
where 07,, is the learned weight parameters for the LAMNet using the k-th truncated adjacency matrix in the 1-th TAM model. The weaker the local node affinity in the learned representation spaces under various graph truncation scales, the larger the anomaly score the node v, has.
4 Experiments
Datasets. We conduct the experiments on six commonly-used publicly-available real-world GAD datasets from diverse online shopping services and social networks, and citation networks, including BlogCatalog [49], ACM [48], Amazon [10], Facebook [56], Reddit, and YelpChi [21]. The first two datasets contain two types of injected anomalies contextual and structural anomalies [8, 34] that are nodes with significantly deviated graph structure and node attributes respectively. The other four datasets contain real anomalies. Detailed information about the datasets can be found in App. B.
Competing Methods and Performance Metrics. TAM is compared with two state-of-the (SOTA) shallow methods- iForest [25] and ANOMALOUS [41] and five SOTA GNN-based deep methods, including three self-supervised learning based methods - CoLA [28]. SL-GAD [63], and HCM-A [17] and two reconstruction-bart based methods DOMINANT [8] and ComGA [31]. iForest works on the raw node attributes, while ANOMALOUS works on the raw node attributes and graph structure. The other methods learn representation space for GAD.
Following [4,38, 32,,, 64], two popular and complementary evaluation metrics for anomaly detection, Area Under the Receiver Operating Characteristic Curve (AUROC) and Area Under the precision- recall curve (AUPRC), are used. Higher AUROC/AUPRC indicates better performance. The reported AUROC and AUPRC results are averaged over 5 runs with different random seeds.
Implementation Details. TAM implemented in Pytorch 1.6.0 with python 3.7 and all the experi- ments are run on an NVIDIA GeForce RTX 3090 24GB GPU. In TAM, each LAMNet is implemented by two-layer GCN, and its weight parameters are optimized using Adam [19] optimizer with 500 epochs and a learning rate of le - 5 by default. T = 3 and K = 4 are used for all datasets. Datasets with injected anomalies, such as BlogCatalog and ACM. require strong regularization, so used by default; whereas X = 0 is used for the four real-world datasets. Hyperparameter analysis w.r.t. K presented in Sec. 4.2. TAM can perform stably within a range of T and X (see App. C. for detail). All the competing methods are based on their publicly-availe official source code, and they are trained using their recommended optimization and hyperparameter settings in the original papers.
is
7

---

Table I: AUROC and AUPRC results on six weal-world GAD datasets with injected/real anomalies. The best performance per is boldfaced, with the second-best underlined.
Dataset
Metric
Method
BlogCatalog
ACM
Amazon
Facebook
Reddit
YelpChi
iurest
0.376520.019
0
1.5622=0.000
0..382
0,4363=a.020
0.4120=o.040
ANOMALOUS
0.5652+0.026
0.6856-0.068
0,4457
0.9021+0.005
0..082
0,4956+0.008
DOMINANT
0.7590+0.010
0.8569=0.020
0.5996-0.004
0.5677+00002
0.5555
0.41333:0.000
AUROC
CoLA
0.7746 0.8233 20.001
0.5898
-0.00s
0.8434
0.6028
0.4636,0.000
SL-GAD
0.8123+0.002
0.8479=0.00s
0.5937=0..01
0.7936
1.5677==0.00s
0.3312+00006
HCM-A
0. 0.00
0.8060=20.00
0.3956_0.034
0.7387
+0.02
0.4599
+0.011
0.4593=0.005
ComGA
0. 0.76832..000
0.8221 20.025
0.5895
=0.000
0.6055
0,5453
0.439) #0.000
TAM (Ours)
0.8248
0.8878
0.7064
-0.030
0.9144
+9.440
0.6023
+..024
0.5643+0.0077
iForest
0.0423 20.002
0.0372
0.1371
=0.002
0.03
0
60.000
0.0169=20.00
0.0409
ANOMALOUS
0.0652
0.0035
0.0558
=0.001
0.
+0.04
0.0375
0.0S19+0.002
DOMINANT
0.3102::0.01
0.4402-=0.036
0.1424
0.0814:20001
0.0356:00.002
0.039550.020
AUPRC
CoLA
0.3270.1.000 0.3235
Lo.017
0.0677
_0.001
0.210610.011
0.0449 10.000
0.044810.000
SL-GAD
0.3882+00007
0.3784_.0.011
0.0634
0.1316
0.0406-0.004
0.0350000.00
IICM-A
0.3139 20.001
0.3413
0.0527
0.0713
20.004
0,0287
2:0000
0.0287
20.012
ComGA
0.3293 10.028
0.2873
0.1153_0.000
0.0354
10.001
0.0374
0.0423 1000000
TAM (Ours)
0.4182.0.000 10.000
0.5124 L00018
0.2634 0..00
0.2233 10.016
0.0446.0.000
0.0778
-0.00 -0.009
4.1 Main Results
Effectiveness on Diverse Real-worid Datasets. The AUROC and AUPRC results on six real-world GAD datasets are reported in Tab. 1. TAM substantially outperforms all seven competing methods on all datasets except Reddit in both metries, having maximally 9% AUROC and 12% AUPRC improve- ment over the cespeconne methods on the challenge dataset Amazon; on Reddit, it ranks second and performs similarly well to the best contender CoLA. Further, existing methods perform very unstably across different datasets. For example, DOMINANT performs well on ACM but badly on the other datasets; CoIAA works well on Reddit but it fails in the other datasets. Similar observations found in a recent comprehensive comparative study [26]. By contrast, TAM can perform consistently well on these diverse datasets. This is mainly because i) the proposed one-class homophily is more per- vasive than the GAD intuitions used by existing methods in different datasets, and ii) TAM offers an effective anomaly scoring function to utilize this anomaly disciiiiiiiiiiiittiiee property for accurate GAD. On Detecting Structural and Contextual Anoma- lies. We further examine the effectiveness of TAM on detecting two commonly-studied anomaly types, structural and contextual anomalies, with the re- sults on BlogCatalog and ACM reported in Tab. 2, where the three best competing methods on the two datasets in Tab. 1 are used baselines. Compared to contextual anomalies, it is significantl, more challenging to detect structural anomalies, for which TAM outperforms all three methods in both AU- ROC and AUPRC. As for contextual anomalies, al- though TAM underperforms SL-GAD and ranks in second in AUROC, it obtains substantially better AUPRC than SL-GAD. Note that compared to AUROC that can be biased by low false positives and indicates overoptimistic performance, AUPRC is a more indicative measure focusing on the performance on the anomaly class exclusively [3,38]. So, achieving the best AUPRC all four cases of the two datasets demonstrates the superiority of TAM in precision and recall rates for both types of anomaly. These results also indicate that structural anomalies may have stronger local affinity than contextual anomalies, but both of which often have weaker local affinity than normal nodes.
Table 2: AUROC and AUPRC results of de- tecting structural and contextual anomalies.
Dataset
Metric
Method
BlogCataoog
Simetural
Comictual
(Snnctural
Contestaal
IOMINANI
03766
03991
UA333
AUROC
SL-GAD
CoLA
0.6244
0.855
0,9754
0.8677
0.7354
0.7468
0.9878
0.9200
TAM
0.6199
0.9627
0.7902
0.9534
DOMINANT
00561
0.438
00052
0.3039
AUPRC:
SI-GAD
CoLA
00370
0.359
0.6298
0.4776
02081
0.0114
0.3085
0.6166
TAM
0.0570
0.6308
0,0568
0.7126
TAM vs. Raw/Generic Node Representation Space. As discussed in Sec. 1, local node affinity requires new node representation space that is learned for the affinity without being biased by non-homophily edges. We provide quantitative supporting results in Tab. 3, where TAM is com- pared with Raw Attribute (RA), and the spaces learned by DGI [51] and GMI [40]. It is clear that the representations leamed by TAM significantly outperforms all three competing representation spaces on all six datasets.
Table 3: Using local node affinity raw at- tributes (RA) and learned representation spaces. OOM denotes out of memory
24GB GPU.
Metric
Method
BlogCanalog
ACM
Amazon
Dataset
Facchook Reddit YelpChi
RA
0.3334
0.7530
0.6722
0.4176
0,5754
0.333T
AUROC
GMI
DGI
0.5647
0,5880
0.7823
0.4438
0.4979
018647
0.8594
0.548)
0.4501
0.5254
00M
FAM (Ous))
0,8238
0.7064
0.9865
0,5923
0,5541
RA
0.1599
0.1257
0.019
0.0536
0.0545
AUPRC
GMI
DGI
0.0662
0.0748
0.1991
0.0578
0,0719
0.1108
0.1260
0.0598
0.0551
COM
(Ous)
0.4178
0.5124
0.2541
0,2362
0,0446
0,0778
8

---

Computational Efficiency. The runtime (including both training and inference time) results are shown in Tab. 4. DOMINANT and ComGA are the simplest GNN-based methods, achieving the most efficient meth- ods. Our method needs to perform multiple graph trun- cation and train multiple LAMNets, so it takes more time than these two reconstruction-base methods, but it runs much faster than the three recent SOTA models,
Table 4: Runtime (in seconds) results.
Method
BlogCoalog
ACM Amazon Facebook Reddi YelpChi
Datasel
DOMINANT
30
48
0
7
10
26
ComGA
330
543
115
67
159
425
HCM-A
2,664
36,254
12.7
1,228
71.891
CoLA
715
2.082
84
18,104
SL-GAD
3055
5.728
3,071
314
4.156
19.588
TAM (Ouss)
214
827
362
41
391
837
HCM-A, CoLA, and SL-GAD, on most of the datasets. A detailed analysis is provided in App. C.2.
4.2 Ablation Study
Graph Truncation NSGT. Three alternative approaches to our graph truncation NSGT include:
i) Raw Graph (RG) that directly performs afrin-
ity maximization on the original graph struc- ture without any graph truncation, and ii) Edge Drop (ED) that randomly drops some edges (5% edges by default) [7]. iii) Similarity Cut (SC) (removing 5% least similar edges). We compare NSGT to these three approaches in the TAM framework in Tab. 5. is clear that NSGT consistently and significantly outperforms both alternative approaches. RawGraph does not work well due to the optimization biases caused non- homophily edges. EdgeDrop is ineffective, which is even less effective than RawGraph, as it often removes homophily edges rather than the opposite due to the overwhelming presence of such edges in a graph. SimilarityCus also significantly underperforms our NSGT on nearly all cases. This is mainly because this variant would fail to take account of local affinity distribution of each node as being captured in NSGT. As a result, it could remove not only non-homophily edges but also homophily edges associated with normal nodes whose local affinity is not strong as the other normal nodes, which would be the opposite to the objective of the optimization in TAM, leading to less effective detection performance.
Table 5: NSGT vs. RG and ED.
Metric
Method
BlogCataoog
ACM
Amswon
Facebook Redli
YelyChi
RG
0.6728
0.7311
0.4763
03185
0.3573
0,3923
AUROC
ED
0.5678
0.7162
0.1574
0.564]
0.5611
0,5014
sc
0.6500
0.5668
0.5855
0.6951
0,6077
0.4910
NSGT
0J235
0.8830
0.7120
0.905
0,5938
0.5449
RG
0.849
0.1145
0.619
0.000
0.033
0.030
AUPRC
ED
0.1229
0.1876
0.0669
0.1244
0.4417
0.0519
SC
0.1621
0:5109
0.0924
0,0410
0.8467
0.0598
NSGT
0.4150
0.5152
0.2555
0.2200
0.0449
0,0775
Affinity Maximization Network LAMNet. The importance of LAMNet is examined by comparing it to its two variants, including Raw Truncated A Affinity (RTA) that directly calcu- lates the local affinity- anomaly scores af- ter NSGT (i.e., without involving LAMNet at all), and DOM that performs LAMNet but with our affinity maximization objective replaced by the popular graph reconstruction loss used in DOMINANT [8]. As shown by the com- parison results reported in Tab. 6. LAMNet consistently and significantly outperforms both RTA and DOM, showing that LAMNet can make much better use of the truncated graphs. In addition, by working on our truncated graphs, DOM can substantially outperform its orig- inal version DOMINANT in Tab. I on most of the datasets. This indicates that the pro- posed one-class homophily property may be also exploited to improve existing GAD methods.
Table 6: LAMNet vs. RTA and DOM.
Metric
Method
BlopCatalog
ACM
Amzzon
Datasel
Fazebook Reddit YelpChi
RIA
0.7497
0,8013
0.6256
0.3161
0,3783
0.3118
AUROC:
DOM
0.7642
(18679
0.5169
0.7793
0
0.5154
LAMNet
0,848
0,8878
0,7064
0.9144
0,592
0.5643
RTA
0.3320
0.208
0.103
01212
0.0457
00613
AUPRO
DOM
0.3115
0.4535
0.1517
0.156
0.0466
0.0338
LAMNeI
0.4182
0,5124
0,2630
0,2233
0.0450
0.0766
Anomaly Scoring. We compare the TAM anomaly scoring to its two variants: i) TAM-T that calculates the node affinity in Eq. (5) on the the truncated graph structure rather than the primary graph structure as in TAM, and ii) Degree that directly uses the node degree after our graph truncation as anomaly score. As illustrated by the AUPRC results in Fig. 4(a), TAM consis- tently and significantly outperforms both variants. Degree obtains fairly good perfor- mance, which shows that our graph trun- cation results in structural changes that are
BlogCatdoo ACM Amazon
Fasebook Reddit YelpCii
0.5
0.
AhPnC
0.4
auanc
Ra
82
6.1
0.1
0,
AGU
lnveso
Fanetoo
Readi
3
8
K
(a)
(b)
Figure 4: (a) TAM vs. Degree and TAM-T. (b) TAM results w.r.t graph truncation depth K.

---

beneficial to GAD. TAM-T underperforms TAM since the local affinity based on the truncated graph structure is affected by randomness and uncertainty in the truncation, leading to unstable and suboptimal optimization. We also show in Fig. 4 (b) that aggregating the anomaly scores obtained from different truncation scales/depths helps largely improve the detection performance. Similar observations are found in the corresponding AUROC results (see App. C.3).
4.3 Performance on Large-scale Graphs
In order to demonstrate the effectiveness of TAM on the large-scale datasets, we conduct the ex-
Table 7: Results on large- scale graphs
periments on the four large-scale datasets with large set of nodes and edges, Amazon-all and YelpChi-all by treating the different relations as single relation following [6], T-Finance [47] and OGB-Proteins [14]. The experimental results are shown in Tab. 7. Due to the increased num- ber of nodes and edges, we set = for these datasets. TAM can perform consistently well on these large-scale datasets and outperforms four comparing methods, which provides further evidence about the effectiveness of our proposed one-class homophily and anomaly mcasure.
Dataset
Amazon-all
VolpChi-all T-Finince OCRB-Protciss
IOKINANT
0.6953
0.3300
0.3330
0.7267
ComGA
0.7154
0.5352
0.5542
0.7134
AUROC
Cis.A
0.2614
0.4801
0-429
0.7142
GAD
0.2728
0.5851
0.4648
0.7371
TAM
0.8476
0,5818
0.6175
0.7449
DOMINANN
0.1015
0.633
0.0474
0.2177
ComLA
0.1854
0.1658
0.0481
0.1554
AUPRC
CoLA
0,0516
0.1361
0.0410
0.1349
SL-GAD
0.0444
0.1711
0.0386
0.1886
0.0547
0.2173
4.4 Handling Camouflage Attributes
Fraudsters may adjust their behaviors to camouflage their malicious activities, which could hamper the per-
Table 8: Results under different levels of
formance of GNN-based methods. We evaluate the
camouflage attributes
performance of TAM when there camouflages in the raw attributes. Particularly, we replace 10%, 20%, 30% randomly sampled original attributes with camou- flaged attributes, in which the feature/attribute value of the abnormal nodes is replaced (camouflaged) with the mean feature value of the normal nodes. The results are shown in the Tab. 8, which demonstrates that TAM is robust to a high level of camouflaged features and main- tains its superiority over the SOTA models that work on the original features. The reason is that NSGT can still successfully remove some non-homophily
Metric
Method
0%:
10%
Datasel
20%
30%
BlugCaulog
0,8218
0.3045
0,8022
0,7831
ACM
0.8878
0.8727
0
0.8652
AUROC
Faczhook
0.7064
0.8870
0.7036
0.6554
0.8804
0.6838
0.8650
0.5876
YelpChi
0.5640
0.5447
0.5211
0.5301
BlugCatalog
0.4182
0.4014
0.4034
0.4095
ACM
0.5124
0.48%
0.4614
AUPRC
Amazon
0.2324
Fazebook
0.2126
0,2015
Rodkii
0.0446
0.441
0.0114
0.0400
YelpChi
0.0778
0.0726
0.0701
0.0678
edges the local domain, allowing LAMNet to make full use of the one-class homophily and achieve good performance under the camouflage.
5 Conclusion and Future Work
This paper reveals an important nromaly-discriminttin property, the one-class homophily, in GAD datasets with either injected or real anomalies. We utilize this property to introduce a novel unsu- pervised GAD measure, local node affinity, and further introduce a truncated affinity maximization (TAM) approach that end-to-end optimizes the proposed anomaly measure on truncated adjacency matrix. Extensive experiments on real-world GAD datasets show the superiority of TAM over seven SOTA detectors. We also show that the one-class homophily can be exploited to enhance the existing GAD methods.
Limitation and Future Work. TAM cannot directly handle primarily isolated nodes in a graph, though those isolated nodes are clearly abnormal. Additionally, like many GNN-based approaches, including GAD methods, TAM also requires a large memory to perform on graphs with a very large node/edge set. The one-class homophily may not hold for some datasets, such as datasets with strong heterophily relations/subgraphs of normal nodes 11299,35 36,46444 46, 62, 66). Our method would require some adaptations work well on the dataset with strong heterophily or very large graphs, which are also left for future work.
10

---

Acknowledgments.
We thank the anonymous reviewers for their valuable comments. The work supported part by the Singapore Ministry of Education Academic Research Fund Tier 1 grant (21SISSMU031).
References
[1] Leman Akoglu, Mary McGlohon, and Christos Faloutsos. Oddball: Spotting anomalies in weighted graphs. In Advances in Knowledge Discovery and Data Mining: 14th Pacific-Asia Conference, PAKDD 2010, Hyderabad, India, June 21-24, 2010. Proceedings. Part II 14, pages 10004221.Sprineee 2010. 10
[2] Leman Akoglu, Hanghang Tong, and Danai Koutra. Graph based anomaly detection and description: a survey. Data mining and knowledge discovery, 29:626 99,626-688, 2015.
[3] Kendrick Boyd, Kevin H Eng, and C David Page. Area under the precision-recall curve: point estimates and confidence intervals. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Pari III 13, pages 451-466. Springer, 2013. 8
[4] 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 International Joint Conference on Artificial Intelligence (IJCAI), Vienna, Austria, pages 23-29,
2022. 7
[5] Varun Chandola, Arindam Banerjee, and Vipin Kumar. Anomaly detection: A survey. ACM computing surveys (CSUR), 41(3):1-58, 2009. 2
[6] 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 Transactions on Knowledge and Data Engineering, 2022. 3. 10, 15
[7] Jinyin Chen, Yangyang Wu, Xuanheng Xu, Yixian Chen, Haibin Zheng, and Qi Xuan. Fast gradient attack on network embedding. arXiv preprint arXiv: 1rXiiv1809.000
1809880922222 02799,2277777 2018.
[8] Kaize Ding, Jundong Li, Rohit Bhanushali, and Huan Liu. Deep anomaly detection on attributed networks. In Proceedings of the 2019 SIAM International Conference on Data Mining, pages 594-602. STAM, 2019. 1, 3, 7, 9, 20
[9] Linfeng Dong, Yang Liu, Xiang Ao, Jianfeng Chi, Jinghua Feng, Hao Yang, and Qing He. Bi-level selection via meta gradient for graph-based fraud detection. In Database Systems for Advanced Applications: 27th International Conference, DASFAA 2022, Virtual Event, April 11-14, 2022, Proceedings, Part I, pages 387-394 Springer, 2022. 1,
[10] Yingtong Dou, Zhiwei Liu, Li Sun, Yutong Deng, Hao Peng, and Philip S Yu. Enhancing graph neural network-based fraud detectors against camouflaged fraudsters. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 315-324, 2020. 2, 3, 7, 15
[11] Haoyi Fan, Fengbin Zhang, and Zuoyong Li. Anomalydae: Dual autoencoder for anomaly detection on attributed networks. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages
IEEE, 2020. 1,
[12] Yuan Gao, Xiang Wang, Xiangnan He, Zhenguang Liu, Huamin Feng, and Yongdong Zhang. Addressing heterophily in graph anomaly detection: A perspective of graph spectrum. In Proceedings of the ACM Web Conference 2023, pages 1528-1538, 1538, 2023. 3
[13] Yuan Gao, Xiang Wang, Xiangnan He, Zhenguang Liu, Huamin Feng, and Yongdong Zhang Alleviating structural distribution shift in graph anomaly detection. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pages 357-365,
2023. 2. 15
[14] 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.
Advances in neural information processing systems, 33:22118 12-2233,, 2020. 10, 15
[15] Ling Huang, Ye Zhu, Yuefang Gao, Tuo Liu, Chao Chang, Caixing Liu, Yong Tang, and Chang- Dong Wang. Hybrid-order anomaly detection on attributed networks. IEEE Transactions on Knowledge and Data Engineering, 2021.
11

---

[16] 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 Proceedings of the ACM Web Conference 2022, pages 1311-1321, 2022.
[17] Tianjin Huang, Yulong Pei, Vlado Menkovski, and Mykola Pechenizkiy. Hop-count based self-supervised anomaly detection on attributed networks. arXiv preprint arXiv:2104.07917
2021. 1, 3, 7, 18, 20
[18) Ming Jin, Yixin Liu, Yu Zheng, Lianhua Chi, Yuan-Fang Li, and Shirui Pan. Anemone: graph anomaly detection with multi-scale contrastive learning. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 3122-3126, 2021.
3
[19] D. Kingma and J. Ba. Adam: A method for stochastic optimization. Computer Science, 2014. 7
[20] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02900 2016.
[21] Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. In Proceedings of the 25th ACM SIGKDD international
conference on knowledge discovery & data mining, pages 1269-1278, 2019. 7, 15
[22] Jundong Li, Harsh Dani, Xia Hu, and Huan Liu. Radar: Residual analysis for anomaly detection in attributed networks. In ICCAI, pages 2152-21555 2017. 2
[23] Qiutong Li, Yanshen He, Cong Xu, Feng Wu, Jianliang Gao, and Zhao Li. Dual-augment graph neural network for fraud detection. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pages 4188-4192, 2022. 3
[24] 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, pages 2233-2236, 2019. 3
[25] Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. Isolation based anomaly detection. ACM Transactions on Knowledge Discovery from Data (TKDD), 6(1):1-39, 2012. 7,20
[26] Kay Liu, Yingtong Dou, Yue Zhao, Xueying Ding, Xiyang Hu, Ruitong Zhang, Kaize Ding, Canyu Chen, Hao Peng. Kai Shu, et al. Bond: Benchmarking unsupervised outlier node detection on static attributed graphs. In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022. 8, 20
[27] Yang Liu, Xiang Ao. Zidi Qin, Jianfeng Chi, Jinghua Feng, Hao Yang, and Qing He. Pick and choose: a gan-based imbalanced learning approach for fraud detection. In Proceedings of the Web Conference 2021, pages 3168-3177 2021.
[28] Yixin Liu, Zhao Li, Shirui Pan, Chen Gong, Chuan Zhou, and George Karypis. Anomaly detection on attributed networks via contrastive sule-super learning. IEEE transactions on neural networks and learning systems, 33(6):2378 22922, 2021. 3, 7, 15, 20
[29] Yixin Liu, Yizhen Zheng, Daokun Zhang, Vincent CS Lee, and Shirui Pan. Beyond smoothing: Unsupervised graph representation learning with edge heterophily discriminating, In Proceed- ings of the AAAI conference on artificial intelligence, volume 37, pages 4516-4524, 2023. 10
[30] Zhiwei Liu, Yingtong Dou, Philip S Yu, Yutong Deng, and Hao Peng. Alleviating the inconsis- tency problem of applying graph neural network to fraud detection. In Proceedings of the 43rd international ACM SIGIR conference on research and development in information retrieval, pages 1569-1572, 2020. 3
[31] Xuexiong Luo, Jia Wu, Amin Beheshti, Jian Yang, Xiankun Zhang, Yuan Wang, and Shan Xue. Comga: Community-ave aware attributed graph anomaly detection. In Proceedings of the Fifteenth ACM International Conference Web Search and Data Mining, pages 657-665, 2022. 1, 20
[32] Xiaoxiao Ma, Jia Wu, Shan Xue, Jian Yang, Chuan Zhou, Quan Z Sheng, Hui Xiong, and Leman Akoglu. A comprchensive survey on graph anomaly detection with deep learning. IEEE Transactions on Knowledge and Data Engineering, 2021. 1,3
[33] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. homophily a necessity for graph neural networks? arXiv preprint 211.:2006.06744 2021. 15
12

---

[34] Julian John McAuley and Jure Leskovec. From amateurs to connoisseurs: modeling the evolution of user expertise through online reviews. In Proceedings of the 22nd international conference on World Wide Web, pages 897-908, 2013. 7
[35] Arjun Mukherjee, Vivek Venkataraman, Bing Liu, and Natalie Glance. What yelp fake review filter might be doing? In Proceedings of the international AAAI conference web and social media, volume 7. pages 409-418, 2013. 15
[36] Caleb C Noble and Diane Cook. Graph-based anomaly detection. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 631-636, 2003. 10
[37] Guansong Pang, Chunhua Shen, Longbing Cao, and Anton Van Den Hengel. Deep learning for anomaly detection: A review. ACM computing surveys (CSUR), 54(2):1-38, 2021. 1,2
[38] Guansong Pang, Anton van den Hengel, Chunhua Shen, and Longbing Cao. Toward deep supervised anomaly detection: Reinforcement learning from partially labeled anomaly data. In Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, pages 1298-1308, 2021. 7,8 8
[39] Yulong Pei, Tianjin Huang, Werner van Ipenburg, and Mykola Pechenizkiy. Resgen: attention- based deep residual modeling for anomaly detection on attributed networks. Machine Learning,
111(2)5119-441, 2022.
[40] Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang. Graph representation learning via graphical mutual information maximization. In Proceedings of The Web Conference 2020, pages 259-270, 2020. 8
[41] Zhen Peng, Minnan Luo, Jundong Li, Huan Liu, and Qinghua Zheng. Anomalous: A joint modeling approach for anomaly detection attributed networks. In ISCAI, pages 3513-3519, 2018. 3, 7, 20
[42] Zhen Peng, Minnan Luo, Jundong Li, Luguo Xue, and Qinghua Zheng. A deep multi-view framework for anomaly detection on attributed networks. IEEE Transactions on Knowledge and Data Engineering. 34(6):25392255 22532, 2020. 3
[43] Bryan Perozzi and Leman Akoglu. Scalable anomaly ranking of attributed neighborhoods. In Proceedings of the 2016 SIAM International Conference on Data Mining, pages 207-215.
SIAM, 2016. 2
[44] Shebuti Rayana and Leman Akoglu. Collective opinion spam detection: Bridging review networks and metadata. In Proceedings of the 21th acm sigkdd international conference on knowledge discovery and data mining, pages 985-994,220 2015. 15
[45] Fengzhao Shi, Yanan Cao, Yanmin Shang, Yuchen Zhou, Chuan Zhou, and Jia Wu. H2-fdetector: a gnn-based fraud detector with homophilic and heterophilic connections. In Proceedings of the ACM Web Conference 2022, pages 1486-1494, 2022. 3
[46] Jimeng Sun, Huiming Qu Deepayan Chakrabarti, and Christos Faloutsos. Neighborhood formation and anomaly detection in bipartite graphs. In Fifth IEEE International Conference on
Data Mining (ICDM' (CCDM'0), pages 8-pp. IEEE, 2005. 10
[47] Jianheng Tang, Jiajin Li, Ziqi Gao, and Jia Li. Rethinking graph neural networks for anomaly detection. arXiv preprint arXiv:2205. / 15508, 2022. 3, 10, 15
[48] Jie Tang. Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Areeminer: extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 990-998, 2008. 7, 15
[49] 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, pages 817-826, 2009. 2, 7, 15
[50] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint 1:XXi:1710.11000 2017. 5
[51] Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICLR (Poster), 2(3):4, 2019. 8
[52] Qizhou Wang, Guansong Pang. Mahsa Salehi, Wray Buntine, and Christopher Leckie. Cross- domain graph anomaly detection via anomaly-aware contrastive alignment. arXiv preprint 12X.02212.001066 2022. 7
13

---

[53] Xuhong Wang, Baihong Jin, Ying Du, Ping Cui, Yingshui Tan, and Yupu Yang. One-class graph neural networks for anomaly detection in attributed networks. Neural computing and applications, 33(18): 2021. 3
[54] Yanling Wang, Jing Zhang, Shasha Guo, Hongzhi Yin, Cuiping Li, and Hong Chen. Decoupling representation learning and classification for gnn-based anomaly detection. In Proceedings of the 44th international ACM SIGIR conference on research and development in information retrieval, pages 1239-1248, 2021.
[55] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: / /810,0082, 2018.
[56) Zhiming Xu, Xiao Huang, Yue Zhao, Yushun Dong, and Jundong Li. Contrastive attributed network anomaly detection with data augmentation. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 444-457. Springer, 2022. 3,7, 15
[57] 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
on Knowledge and Data Engineering. 33(1):169- 179, 2019. 1
[58] Ge Zhang, Jia Wu, Jian Yang, Amin Beheshti, Shan Xue, Chuan Zhou, and Quan Z Sheng. Fraudre: Fraud detection dual-resistant to graph inconsistency and imbalance. In 202/ IEEE International Conference on Data Mining (ICDM), pages 867-876. IEEE, 2021. 3
[59] Jiaqiang Zhang, Senzhang Wang, and Songcan Chen. Reconstruction enhanced multi-view con- trastive learning for anomaly detection on attributed networks. arXiv preprint arXiv:2205.04811 2022.
[60] Shijie Zhang, Hongzhi Yin, Tong Chen, Quoc Viet Nguyen Hung. Zi Huang, and Lizhen Cui. Gen-based user representation learning for unifying robust recommendation and fraudster detection. In Proceedings of the 43rd international ACM SIGIR conference on research and development in information retrieval, pages 689-698, 2020. 15
[61] Tong Zhao, Chuchen Deng, Kaifeng Yu, Tianwen Jiang, Daheng Wang, and Meng Jiang. Error-bounded graph anomaly loss for gnns. In Proceedings of the 29th ACM International Conference on information & Knowledge Management, pages 1873-1882, 2020.
[62] Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. Graph neural networks for graphs with heterophily: A survey. arXiv preprint arXiv:2202.070822 2022. 10
[63] 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. JEEE Transactions
on Knowledge and Data Engineering. 2021. 1, 3, 7, 18, 20
[64] Shuang Zhou, Xiao Huang, Ninghao Liu, Qiaoyu Tan, and Fu-Lai Chung. Unseen anomaly detection on networks via multi- hyperspherrr learning. In Proceedings of the 2022 SIAM International Conference on Data Mining (SDM), pages 262-270. SIAM, 2022. 7
[65] Shuang Zhou, Qiaoyu Tan, Zhiming Xu, Xiao Huang, and Fu-lai Chung. Subtractive aggregation for attributed network anomaly detection. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 3672-3676, 2021. 1,3
[66] Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K. Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11168-11 1166-111666 11176, 2021. 10
14

---

A One-Class Homophily Phenomenon
Fig. 5 shows the one-class homophily phenomenon the rest of four datasets, in which ACM is dataset with injected anomalies while the other three datasets contain real anomalies. The results here are consistent with that in the main text.
Given the graph along with the ground truth labels, following [13,33), the homophily and heterophily are defined as the ratio of the edges connecting the node with the same classes and different classes, respectively:
{
hhtero (v) = [ioo Iu: a E N(e), yu + HoH
(1I)
X hhomo (1) [N(e]
Hu: u E N()), Uh yo
where ye is the label to denote whether the node e is an anomaly or not. Note that one-class homophily may not always hold, or it weak in some datasets. YelpChi which connects the reviews posted by the same user, e.g. YelpCh-RUR is an example of the latter case, As shown in Figure 5, the homophily distribution of normal and abnormal nodes is similar in YelpCh-RUR, whose pattern is different from the large distribution gap in the other three datasets. Since the normal nodes' homophily is generally stronger than the abnormal nodes, we can still successfully remove the nomooilyyyly edges that connect normal and abnormal nodes with higher probability than the homophily edges, resulting in a truncated graph with stronger one-class homophily.
B Description of Datasets
We conduct the experiments on two real-world dataset with injected anomalies and four real-world with genuine anomalies in diverse online shopping services, social networks, and citation networks, including BlogCatalog [49]. ACM [48], Amazon [10]. Facebook [56], Reddit, YelpChi [21], as well as four large-scale graph datasets. The statistical information including the number of nodes, edge, the dimension of the feature, and the anomalies rate of the datasets can be found in Tab. 9.
Particularly, BlogCatalog is social blog directory where users follow each other. Each node represents a user, and each link indicates the following relationships between two users. The attributes of nodes are the tags that describe users and their blogs. ACM is citation graph dataset where the nodes denote the published papers and the edge denotes the citations relationship between the papers. The attributes of each node are the content of the corresponding paper. BlogCatalog and ACM popular GAD datasets where the anomalies are injected ones, including structural anomalies and contextual anomalies, which are created following the prior work [28]. Amazon is graph dataset capturing the relations between users and product reviews. Following [10,60], three different user-user graph datasets are derived from Amazon using different adjacency matrix construction approaches. In this work, we focus on the Amazon- UnU dataset that connects the users who give reviews to at least one same product. The users with less than 20% are treated as anomalies. Facebook [56] is a social network where users build relationships with others and share their same friends. Reddit is a network of forum posts from the social media Reddit, in which the user who has been banned from the platform is annotated as an anomaly. Their post texts were converted to the vector as their attribute. YelpChi includes hotel and restaurant reviews filtered (spam) and recommended (legitimate) by Yelp. Following [35, 44], three different graph datasets derived from Yelp using different connections in user, product review text, and time. In this work, we only use YelpChi-RUs RUR which connects reviews posted by the same user. Note that considering it's difficult to conduct an evaluation on the isolated nodes in the graph, they were removed before modeling.
Amazon-all and YelpChi-all [10] are two datasets by treating the different relations as a single relation following [6]. T-Finance [47] is a transaction network. The nodes represent the unique account and the edges represent there are records between two accounts. The attributes of nodes are the features related to registration days, logging activities, and interaction frequency. The anomalies are fraud, money laundering and online gambling which are annotated manually. OGB- [14] is biological network where node represents proteins and edge indicates the meaningful association between proteins.
15

---

ACM
Facebook
24
40
Normal
Normal
21
35
Abnormal
Abnormal
18
30
15
Aisuad
12
20
15
10
8.0
0.2
0.4
0.8
0.3
0.4
0.5
0.6 0.7 Homophily
0.8
Homophily
(a)
(b)
Reddit
YelpChi
27
Normal
28
Normal
24
Abnormal
Abnormal
24
21
Densty
20
18
15
16
12
12
9-
3
4
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Homophily
Homophily
(c)
(d)
Amazon-all
YelpChi-all
21
Normal
8
Normal
Abnormal
7
Abnormal
18
6
15
5
Qensi
12
4
9
6
2
3
1
0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.4
0.6
0.8
1.0
Homophily
Homophily
(e)
(f)
T-Finance
OGB-Protein
24
Normal
21
Normal
21
Abnormal
18
Abnormal
18
15
Densicy
15
12
12
6
3
44
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Homophily
Homophily (h)
(g)
Figure 5: Homophily distribution of normal nodes and abnormal nodes on the rest of eight datasets
16

---

Table 9: Key statistics of the datasets. The real-world datasets with Injected/Real (
Data set
Type
Nodes
Edges
Attributes
Anomalies(Rate)
BlogCatalog
Social Networks
5,196
171,743
8,189
300(5.77%)
ACM
Citation Networks
16,484
71,980
8,337
597(3.63%)
Amazon
Co-review
10244
175.608
25
693(6.66%)
Facebook
Social Networks
4,039
88,234
576
27(0.67%
Reddit
Social Networks
10,984
175,608
64
366(3.33%)
YelpChi
Co-review
24,741
49,315
32
1,217(4.91%)
Amazon-all
Co-review
11,944
4.398.392
25
821(6.87%)
YelpChi-all
Co-review
45,941
3.846,979
32
6,674(14.52%)
T-Finance
Transaction Record
39.357
21,222.543
10
1,803 (4.58%)
OGB-Proteri
Biology Network
132,534
39,561,252
8
6000(4.5%)
BlogCatalog
ACM
Amazon
Facebook Reddit
ellpChi
0.90
0.85
0.4
AURO
0.80
AUPRC
0.3
C
0.75
0.70
0.2
0.65
0.60
0.1
0.55
2
1
2
4
(a)
(b)
Figure AUROC and AUPRC results w.r.t. ensemble parameter
C Additional Experimental Results
C.1 Hyperparameter Analysis
This section analyzes the sensitivity of TAM w.r.t two key hyperparameters, including the regulariza- tion hyperparameter and the ensemble parameters T. The results on À and T are shown in Fig. 6 and Fig. 7, respectively.
Ensemble Hyperparameter T. As shown in Fig. 6 with increasing T. TAM generally performs better and becomes stable around T 4. This mainly because the use more ensemble models on truncated graphs reduces the impact of the randomness of truncation and increases the probability of weakening the affinity of abnormal nodes to its neighbors, and this effect would diminish when T' is sufficiently large. The average of local affinity from multiple truncated graph sets is more conducive to anomaly detection.
Regularization Hyperparameter X. In order to evaluate the effectiveness of adopt different values to adjust the weight of the regularization. From Fig. 7, we can see that for BlogCatalog and Facebook, adding the regularization improves the effectiveness of the model by large margin. This is mainly because the use of regularization can prevent all nodes from having identical feature representations. For most real-world datasets with genuine anomalies, the regularization does not significantly improve the effectiveness of the model while decreasing the performance as the increasing of The main reason that Amazon, Reddit, and YelpChi are real-world datasets with diverse attributes, and the role of regularization term is not reflected during affinity maximization.
17

---

BlogCatalog
ACM
Aazoo
Facebook Reddit
Y ellpChi
0.9
0.5
0.8
0.4
AUROC
0.7
0.3
0.6
0.2
0.5
0.1
0.0
0.2
0.4
1.0
0.0
0.2
0.4
0.6
0.8
1.0
2 (b)
a
Figure 7: AUROC and AUPRC results w.r.t regularization hyperparameter
C.2 Complexity Analysis
This subsection analyzes the time complexity of TAM. Specifically, the distance calculation takes Ommo)), m number non-zero elements in the adjacent matrix A, and dg is the dimension of attributes for each node. The graph truncation in TAM takes 2N1 where N is the number of nodes and 1 the average degree the graph. LAMNet, we build a GCN for each truncated graph, which takes (mndy h) using pparse-dense matrix multiplications, where h and dj denotes summation of all feature maps across different layer and feature dimensions in graph convolution operation, respectively. The construction of GCN takes ((md,h) LAMNet also needs to compute all connected pairwise similarities, which takes O (N2). Thus, the overall complexity of TAM is Omndg + (N2 + md, h + KT), where K is the truncation depth and T is the ensemble parameter. The complexity is lower than the time complexity in many existing GNN-based graph anomaly detection methods based the subgraph sampling and hop counting [17,63].
C.3 Anomaly Scoring
AUROC Results of TAM and Its Variants. We present the AUPRC results TAM and its two variants, Degree and TAM-T in the main text, where TAM can consistently and significantly outperform both variants. Similar observation can also found from the AUROC results in Fig. 8(a). Fig. 8(b) shows the AUROC results of anomaly scoring by aggregating the anomaly scores under all truncation scales/depths. Similar to the AUPRC results in the main text, the anomaly scores obtained from different truncation scales/depths can largely improve the detection performance and the results become stable with increasing graph truncation depth K.
Anomaly Scoring Using Multi-scale Truncation vs Single-scale Truncation. Fig. 9 shows the results of TAM that performs anomaly scoring based on single-scale graph truncation rather than the default multi-scale graph truncation. As shown in Fig. 9, the increase of K improves the performance on large datasets such as the Amazon datasets, but often downgrades the performance on the datasets such as Reddit and YelpChi. The main reason is that the node attributes in these datasets are more similar than the other datasets, restricting the effect of graph truncation. However, the opposite occur the other datasets. To tackle this issue, we define the overall anomaly score as an average score over the anomaly scores obtained from the LAMNets built using truncated graphs under all truncation depths/scales. This resulting multi-scale anomaly score, shown in Fig. 8(b), performs much more stably than the single-scale anomaly score.
C.4 Shared-weights LAMNet vs. Non-shared-weight LAMNet
In our experiments, the weight parameters in LAMNets are independent from each other by default, i.e., GNNs in LAMNets are independently trained. this section, we compare TAM with its variant TAM-S where all LAMNets use single GNN backbone with shared weight parameter.
18

---

BlogCatalog
ACM
A mazon
Facebook
-Reddit
YelpChi
Degree
0.90
TAM-T
0.8
0.85
AUROC
0.80
AUROC
0.6
0.75
0.70
0.4
0.65
0.2
0.60
0.55
0.0
BlogCatalog
ACM
Amazon
F Facabook
Reddit
YelpChi
1
3
4
K
5
7
8
(b)
Figure 8: AUROC results of (a) TAM vs. Degree and TAM-T, and (b) TAM w.r.t graph truncation
depth K.
BlogCatalog ACM Amazon
Facebook
Reddit
YelpChi
0.5
0.4
AUROC
0.7
AUPRC
0.3
0.6
0.2
0.1
0.5
5
6
K
K
(a)
(b)
Figure 9: AUROC and AUPRC results of TAM using single-truncation scale-based anomaly scores
The results are shown in Tab. 10. It is clear that TAM performs consistently better than, or comparably well to, TAM-S across the six datasets.
C.5 Simple Similarity- based Non-homophily Edge Removal
Our ablation study in the main text has shown the inferior performance SimilarityCut method compared to our proposed NSGT, where we directly remove 5% least similar edges. Tab 11 shows the results of removing 10% and 30% least similar edges. It clear that NSGT outperforms these two other cases of SimilarityCut.
C.6 ROC and Precision-Recall Curves
The ROC curve and Precision-Recaa curve of TAM the six datasets shown in Fig. 10.
19

---

Table 10: AUROC and AUPRC results of TAM using shared-weipe LAMNets (TAM-S) vs. non- shared-weight LAMNets (TAM).
Dataset
Metric
Method
BlogCatalog
ACM
Amazon
Facebook
Reddit
YelpChi
AUROC
TAM-S
0.817020.002 0.8826-0.005
0.7044 10:00000000 00s
0,9165 20.005
0.60U8
20.000
0.3407 10.008
TAM
0.8248 L0.003
0.8878 00.024
0.7064 11.010
0.9144 10.008
0.6023 10.004
0.564311.0m0
AUPRC
TAM-S
0. 10.002
0,4960
0..001
0.2597
10.000
0.208 10.006
0.0459
10.003
0.0691 10.002
TAM
0.4182
0.5124 000018
0.2634 40.44440000
0.2233=aoomt
0.0446 20.001
0.0778 -0.009
Table 11: Performance under different ratio of similarity- edge removal. / represents the edge-cut ratio based on similarity.
Dataset
Metric
Method
#=0.05
0=0.11
0 0.3
TAM
BlogCatalog
0.6650
0.6526
0.6583
0.8210
ACM
0.8668
0.7986
0.6911
0.8878
AUROC
Amazon
0.5856
0.5827
0.6106
0.7064
Facebook
0.6951
0.7293
0.7934
0.9144
Reddit
0.6007
0.5945
0.5758
0.6028
YelpChi
0.4910
0.4872
0.4754
0.5674
BlogCatalog
0.1621
0.1829
0.1729
0.4152
ACM
0.5109
0,5068
0,4996
0,5124
AUPRC
Amazon
0.0924
0.1092
0,2079
0.2634
Facebook
0.0410
0.1154
0.1374
0,2233
Reddit
0.0467
0.0414
0.0420
0,0446
YelpChi
0.0598
0.0509
0.0519
0.0771
D Description of algorithms
D.1
Competing Methods
iForest [25] builds multiple trees to isolate the data based the node's feature. has been widely used outlier detection.
ANOMALOUS [41] proposes a joint network to conduct the selection of attributes in the CUR decomposition and residual analysis. It can avoid the adverse effects brought by noise.
DOMINANT [8] leverages the auto-encoder for graph anomaly detection. It consists of an encoder layer and a decoder layer which construct the feature and structure of the graph. The reconstruction errors from the feature and structural module are combined the anomaly
score.
HCM-A [17] constructs an anomaly indicator by estimating hop count based on both global and local contextual information. It also employs Bayesian learning in predicting the shortest path between node pairs.
CoLA [28] exploits the local information in contrastive self saff-sueeeeieed framework. They define the positive pair and negative pair for a target node. The anomaly score is defined as the difference value between its negative and positive score.
modules including generative attribute regression and multi- view contrastive for anomaly detection based on CoLA. The anomaly score is generated from the degree of mismatch between the constructed and original features and the discrimination scores.
SL-GAD [63] constructs
ComGA [31] designs a tailor GCN to learn distinguishable node representations by explicitly capturing community structure.
Their implementation is taken directly from their official web pages the widely-used PyGOD library [26]. The links to the source code pages are as follows:
iForest: https///giibbbbooooooodeee////e
ANOMALOUS: http://h/ghmaabooom///oyceeaaaye
DOMIANT: http://hhwb..cooooccooooo//ooooa pytroch
20

---

1.0
1.0
HUPCC-3.53)
1.0
0.5
0.6
66
0.6
0.6
0.4
0.4
0.4
0.2
0.2
52
False Postbive Rate
D-4 0.5
0.8
1.0
5.0
0.2
0.4
Recall
6.6
00
1/8
00.0
False Positve Rate [c]
0.2
04
0.8
6.8
1.0
Recal
(a)
(b)
1.0
1.0
CRPe aMgg50g 0011
Uaisiaadd
0.6
0.4
0.4
0.2
0.2
16
JALRSC 0.200
HANOC 811)
0.80
20.0
0.5
0.5
02
0.4
0.
0.8
1.0
False Positive R (e)
Recall
False P os live Rate (g)
Recall
1.0
(AUFRC 1.440)
1.0
PPd aageod 2h11
0.6
uo/sppad
0.0
0.6
Lospprd
0.5
0.4
0.2
0..0
0.2
0.4
6.6
0.8 1.0
0.2
096
0.2
0.8
0.6
False Positive Rate
Recall
False Positivv Rate
Recall
(1)
(]
(I)
Figure 10: The ROC curve and precision-recall curve of our method TAM on all the six datasets used. (a)(b) BlogCatalog; (c)(d) ACM: (e)(f) Amazon; (h)() Facebook; (i)() Reddit; (l)m) YelpChi
HCM-A: http:///ghhhoooooooooottooooo/oa
CoLA: http:///ghhhibbooooo/rraaAaaaaa
SL-GAD: http://giiihbbbcoomyyiiinnniniis
D.2 Pseudo Codes of TAM.
The training algorithms of TAM are summarized in Algorithm and Algorithm Algorithm describes the process of NSGT. Algorithm 2 describes the training process of TAM.
21

---

Algorithm 1 NSGT
Input: Attributed Graph, G= (V, &). Distance Matrix, M
Output: truncated graph structure E.
1: 1* Regard the graph as a direct graph */
2: Initialize the directed graph truncation indicator ((uiv))) iff (vs, U2)
3: Find the mean dmean from M using dmean m > (0,,,))er di
4: for each e in do
5: Find the maximum d, maxx from (d(u,v'). (v, E)
6: if dy. > dmean then
7: Randomly sample from [dmeans max for node
8: for each of {v', (", E } do
9:
if ((, v²) then
Plan to cut the edge v to v', i.e. E(e,r) t- 10: end if
11:
12: end for
end if
14:
end for
1* The edge will be removed only when it is non-homophily edge from both directions of the
connected nodes */ for each in V do
16:
for each o' in (v,'', E E) do
Cut the edge between and v', & El (( (o',e)) iff ((v,e)) = =(e(()) 0 18: end for
end for
20:
return The truncated graph structure غ
22

---

Algorithm 2 TAM
Input: Graph, G- (V, &, X), N: Number of nodes, Number of layers, E: Training epochs, T: Ensemble parameter, K: Truncation depth.
Output: Anomaly scores of all nodes 8.
1: Compute the Euclidean distance M = {dig) for each connected node pair (u; Uy) & (0)
2: Randomly initialize GNN (h h (0)) X, g(1,0) g(T.0)
3: for k =
K do
4: for = 1, ................................ , do
5: 1* Graph truncation and update the graph structure */
6:
g(t.k) NSGT(V, g(t.k-1), 1,, M)
LAMNet
7:
for epoch = 1, , do
8:
for each v in V
9:
for / 1.... L do
h ohh,1111 O1.x)
11:
h,. = ReLU (AGG((ha (0,2)) e g((8)))
12:
end for Calculate fTAM (1:: Ot,k, A, by Eq. (2).
13:
14:
end for
15:
1* Affinity maximization #/
Minimize
Σ
[rrA (0; Or,k, A, + pmpittal Σ sim (h,, hx) (vvV)(()))
v.EV
17:
Update θ₁, by using stochastic gradient descent end for
19:
end for
20: end for
18 Aggregated anomaly score over T sets of multi-scale graph truncation depths */
21: return Anomaly Score by s (v) TxK
JTAM (v; 07,,- A, X))
23


Reviews:
[{"review_id": "f2Cv61t29i", "reviewer": "Reviewer_NSnj", "summary": "Graph anomaly detection aims to identify abnormal nodes in a given graph. The manuscript argues that the existing graph anomaly detection datasets have one-class homophily where the homophily of normal nodes is much stronger than abnormal nodes. To utilize the one-class homophily phenomenon in graph anomaly detection, a new similarity-based anomaly scoring measure, named local node affinity, is proposed. The proposed method, TAM, learns the parameters of multiple graph neural networks called LAMNets by maximizing the sum of local node affinity on the original graph. The iterative graph truncation technique (NSGT) removes the links between normal and abnormal nodes in each step, and the resulting graphs are fed into LAMNets. During the message passing, LAMNet uses the truncated adjacency matrix. The local node affinity-based anomaly score is measured on the original graph using node representations generated by LAMNets. Experimental results show that TAM achieves high AUROC and AUPRC values compared to seven graph anomaly detection methods on six benchmark datasets.", "questions": "1. Why does NSGT utilize raw attributes instead of node representations learned from LAMNet? \n2. Is there any experimental result on large-scale graph anomaly detection datasets?\n3. Isolated nodes can appear after performing NSGT. How does TAM-T compute the anomaly scores of such isolated nodes?", "limitations": "1. As the TAM model works solely on the assumption of one-class homophily, it might not perform effectively on the graphs where abnormal nodes are homophilic, e.g., YelpChi-RUR.\n2. Since NSGT directly utilizes the raw node features to truncate the graph, the quality of the graph truncation might be affected by the quality of the raw features. However, there can be many irrelevant or redundant attributes in the original features.\n3. Due to the definition of local node affinity measure, TAM cannot handle isolated nodes in the graph even though the node features are available.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. NSGT introduces randomness by removing the non-homophily edges in a probabilistic approach. To utilize such randomness, TAM uses an ensemble strategy by performing NSGT multiple times and feeding the resulting graphs to multiple LAMNets. Table 2 in Appendix C shows that the ensemble strategy improves the performance of TAM.\n\n2. The manuscript provides empirical justifications for the major claims. For instance, the homophily distribution in Figure 1(a) supports the one-class homophily phenomenon. Figure 3(a) and Figure 3(b) show that the Euclidean distance between the nodes connected by a non-homophily edge tends to be greater than that between the nodes connected by a homophily edge.\n\n3. Ablation studies with various variants of TAM and hyperparameter sensitivity analyses show that each component of TAM is effective.", "weaknesses": "1. It is not guaranteed that the one-class homophily property holds for all graph anomaly detection datasets. For instance, both normal and abnormal nodes in the YelpChi-RUR dataset are homophilic, as shown in Figure 1 (d) in Appendix A.\n\n2. The performance of NSGT might depend on the quality of the node attributes. NSGT performs the graph truncation by considering the node attributes of the original graph. As mentioned in lines 170-171, if the original node features contain many irrelevant attributes, NSGT might not work well. Furthermore, features of abnormal nodes can be intentionally camouflaged [1, 2].\n\n   [1] Liu et al., Alleviating the Inconsistency Problem of Applying Graph Neural Network to Fraud Detection, SIGIR 2020.\n\n   [2] Dou et al., Enhancing Graph Neural Network-based Fraud Detectors against Camouflaged Fraudsters, CIKM 2020.\n\n- One suggestion is to utilize the node representation vectors calculated by LAMNets. In addition, an attribute selection strategy can be introduced to remove irrelevant or redundant node attributes.\n\n3. While this manuscript assumes an unsupervised learning setting, one of my concerns is that most state-of-the-art methods assume a semi-supervised learning setting. Indeed, in many real practices, some supervision can be provided for graph anomaly detection, e.g., labeling undesirable nodes or patterns. Given this, the benefit of the proposed method can be limited.\n\n4. Existing studies [3] convert YelpChi by merging different relations into a single relation. Why YelpChi-RUR and Amazon-UPU are used instead of the full datasets? Instead of selecting one particular relation, the authors can utilize all relations and treat them as a single relation.\n\n   [3] Chen et al., GCCAD: Graph Contrastive Learning for Anomaly Detection, TKDE 2022.\n\n5. The statistics of Amazon and YelpChi differ from the actual ones. For Amazon, the number of nodes is 10,224, and the number of anomalies is 693 (6.78%). For YelpChi, the number of nodes is 23,831, and the number of anomalies is 1,217 (5.11%).\n\n6. Minor Comments:\n- Lines 206-207 are confusing. According to lines 206-207, the truncated adjacency matrix instead of the original adjacency matrix is used to optimize LAMNets. However, the local affinity is calculated based on the original adjacency matrix during optimization, as stated in lines 261-262.\n- In lines 215-221, it is not specified how to handle the case where $d_{i, max}$ is less than $d_{mean}$.\n- In lines 116-117, \"such degree\" should be modified to \"such as degree\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the constructive comments and questions. We are grateful for the positive comments on our design, empirical justification and ablation study. Please see our detailed one-by-one responses below.\n\n> **Weaknesses/Limitations #1**: Does one-class homophily always hold?\n\nPlease refer to our reply to **Global Response to Shared Concern #1** in the overall Author Rebuttal section above for this concern.\n\n> **Weaknesses/Limitations #2, Questions #1**: The dependence of the performance of NSGT/TAM on the quality of raw node attributes. \n\nIn TAM, NSGT performs truncation on the graph sequentially based on node attribute similarities to reduce the negative impact of non-homophily edges on message passing. So, it's true that the performance of NSGT (and subsequently TAM) relies on the quality of node attributes, but we show below that performing NSGT directly on the original attributes is a simple, easy-to-use, yet effective way. The two alternative ways you suggested for NSGT do not show clear advantages. We discuss this argument in detail below.\n\n**Using Attribute Selection Before NSGT**. The table below shows the AUC-ROC results of TAM on datasets resulting from the popular unsupervised Laplacian score-based attribute selection (X% means X% top-ranked attributes are selected).\n\n|**Data**|**100%**|**80%**|**60%**|**40%**|**20%**|\n|:----|:----:|:----:|:----:|:----:|:----:|\n|Amazon|0.7064|0.7329|0.7136|0.6924|0.6893|\n|Facebook |0.9144|0.9151|0.8739|0.8802|0.8177|\n|Reddit   |0.6023|0.5845|0.5789|0.5778|0.5664|\n|YelpChi|0.5643|0.5695|0.5749|0.5793|0.5354|\n\nThe results show that a careful unsupervised attribute selection can improve the performance of TAM, such as retaining 80% top-ranked attributes in Amazon, Facebook, and YelpChi, but the improvement is often relatively very marginal. Further, if there is any issue in the attribute selection process (e.g., an undesired selection threshold is used), the relevant attributes may also be removed together with the irrelevant ones, leading to degraded performance of TAM, e.g., the case in Reddit. Note that the node attributes in BlogCatalog and ACM are node embedding features, which are mostly all relevant in these two cases. So, we did not include these two datasets in the attribute selection above.\n\n**Using Learned Node Representations from LAMNet**. As suggested by you, we can perform NSGT on the node representations learned by LAMNet, meaning we first run the full TAM on the original graph and then obtain the newly learned node representations from LAMNet as input to re-run TAM. The AUC-ROC results in the table below that this strategy is not as effective as our original TAM that performs NSGT based on raw attributes.\n\n|**Data**|**RAW Attributes**|**LAMNet-based Representations**|\n|:----|:----:|:----:|\n|BlogCatalog|**0.8248**|0.7024|\n|ACM|**0.8878**|0.8670|\n|Amazon|**0.7064**|0.6766|\n|Facebook |0.9144|**0.9164**|\n|Reddit   |**0.6023**|0.5921|\n|YelpChi|**0.5643**|0.5428|\n\n**Handling Camouflage Features**. We evaluate the performance of TAM when there are camouflaged features in the raw attributes. Particularly, we replace 10%/20%/30% randomly sampled original features with camouflages features, in which the feature value of the abnormal nodes is replaced (camouflaged) with the mean feature value of the normal nodes. The AUC-ROC results are shown in the table below, which demonstrate that TAM is robust to a high level of camouflaged features and maintains good superiority over the SOTA models that work on the original features.\n\n|**Data**|**0%**|**10%**|**20%**|**30%**|\n|:----|:----:|:----:|:----:|:----:|\n|BlogCatalog|0.8218|0.8045|0.8022|0.7831|\n|ACM|0.8878|0.8727|0.8688|0.8652|\n|Amazon|0.7064|0.7036|0.6954|0.6838|\n|Facebook |0.9144|0.8870|0.8804|0.8650|\n|Reddit   |0.6023|0.5998|0.5915|0.5876|\n|YelpChi|0.5649|0.5447|0.5271|0.5301|\n\nWe will add the above results and discussions into our final paper to provide these important insights for readers.\n\n>**Weaknesses #3**: Unsupervised vs. supervised anomaly detectors?\n\nThere are methods from two different paradigms having a different set of pros and cons.\n\n>**Weaknesses #4/Questions #2**: A larger scale of Amazon and YelpChi, and other large datasets?\n\nPlease refer to **Global Response to Shared Concern #2** in the overall Author Rebuttal section above.\n\n>**Weaknesses #5, Questions/Limitations #3**: (1) Difference of statistics in YelpChi-RUR and Amazon-UPU? (2) Handling isolated nodes?\n\n(1) We use exactly the same data sources, but we remove primarily isolated nodes in both datasets in data preprocessing, which is the cause of the difference.\n\n(2) There can be two types of isolated nodes. One is the primarily isolated nodes in a graph. Since this kind of nodes does not have any structure information, it has no impact on the graph structure learning, so one commonly used practice is to not consider these nodes in training and evaluation. We also follow this practice. Using only the node attributes to perform anomaly detection will go down to general tabular anomaly detection. \n\nThe other one is the isolated nodes that appear after truncating the graph. For this type of isolated nodes, TAM can well handle them. This is because the LAMNet is performed on the truncated graph structure, while the local affinity-based anomaly scoring is done using the original graph structure. Thus, TAM can effectively calculate the anomaly scores for this type of isolated nodes. Normally these nodes would have a small local affinity and a large anomaly score, since all their edges are cut off during our graph truncation. TAM-T has different anomaly scoring from TAM, which is based on the truncated graph to calculate the affinity, so TAM-T takes a simplified approach to deal with isolated nodes: it directly takes the isolated nodes emerging during truncation as anomalies.\n\n**Note that due to space limitation, above we present the AUC-ROC results only. Similar findings can be observed in AUC-PR.**"}, {"review_id": "PVCSPJc58H", "reviewer": "Reviewer_uzaW", "summary": "In this paper, the authors introduced a novel unsupervised anomaly scoring measure (local node affinity) for GAD, and further proposed a Truncated Affinity Maximization (TAM) for GAD. TAM learns tailored node representations for our anomaly measure by maximizing the local affinity of nodes to their neighbors, and is optimized on truncated graphs where non-homophily edges are removed iteratively to mitigate this bias. The authors also conduct a series of experiments to evaluate the anomaly detection performance of TAM.", "questions": "See weakness.", "limitations": "See weakness.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well-motivated and easy to follow.\n2. The idea of exploring the one-class homophily characteristic for designing a GAD method is interesting.\n3. The experimental section provides comprehensive evaluations of the proposed method from different perspectives, and demonstrates the effectiveness of the proposed method.", "weaknesses": "1. In the related work section, the authors should discuss the connections and differences between the proposed methods and other existing works, as well as the necessity for this work.\n2. As the authors claimed, one-class homogeneity does not hold in all cases. Therefore algorithms designed on this basis would be relatively limited.\n3. The authors propose to optimize TAM on truncated graphs to avoid the negative impact of non-homophily edges. How the author guarantees to obtain ideal truncated graphs with the removal of non-homophily edges iteratively. Besides, does it have some criteria to judge whether the truncation map obtained is ideal or not?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the overall positive rating and constructive comments. We are grateful for the positive comments on our research motivation, readability, our technical design and empirical justification. Please see our response to your comments one-by-one below.\n\n> **Weaknesses #1**: In the related work section, the authors should discuss the connections and differences between the proposed methods and other existing works, as well as the necessity for this work.\n\nThank you very much for the comment and suggestion. We will add discussions on the connections and differences w.r.t. existing studies in the Related Work section in the final version of the paper. \n\nSpecifically, current unsupervised graph anomaly detection methods can be generally grouped into reconstruction-based and self-supervised-based approaches.\n\nBeing GNN-based approaches, both the reconstruction-based approaches and our approach TAM rely on node's neighborhood information to calculate the anomaly scores, but we explicitly define an anomaly measure from a new perspective, i.e., local node affinity. This results in fundamentally different anomaly detection optimization objectives. Some of these points have been elaborated in detail in Section 3.2. We will include this discussion into Related Work to brief the connections and the differences.\n\nSimilar to the self-supervised approaches, the optimization of TAM also relies on an unsupervised objective. However, the self-supervised approaches require the use of some pre-text tasks like surrogate contrastive learning or classification tasks to learn the feature representations for anomaly detection. By contrast, the optimization of TAM is directly driven by a new, plausible anomaly measure, which enables end-to-end optimization of an explicitly defined anomaly scoring measure.\n\nOverall, TAM offers a very different perspective on devising graph anomaly detection methods, which is tasked to learn tailed node representations for an explicitly defined graph anomaly measure; whereas both reconstruction-based and self-supervised-based approaches are focused more on learning latent node feature representations for a proxy task. Thus, being driven by a prevalent one-class homophily property, TAM and its future variants are expected to align better with the graph anomaly detection problem.\n\n> **Weaknesses #2**: As the authors claimed, one-class homogeneity does not hold in all cases. Therefore algorithms designed on this basis would be relatively limited.\n\nThank you very much for the comment. Please refer to our reply to **Global Response to Shared Concern #1** in the overall Author Rebuttal section above for a detailed discussion on this point.\n\n> **Weaknesses #3**: The authors propose to optimize TAM on truncated graphs to avoid the negative impact of non-homophily edges. How the author guarantees to obtain ideal truncated graphs with the removal of non-homophily edges iteratively. Besides, does it have some criteria to judge whether the truncation map obtained is ideal or not?\n\nThank you very much for the comment and the question. Since it is unsupervised anomaly detection, no ground truth is given to evaluate/prove whether a resulting truncated graph is better than another one. Instead we introduce a plausible probabilistic method that helps iteratively eliminate non-homophily edges with a high probability, while preserving the genuine homophily, as elaborated in the NSGT subsection in the paper. In addition, we utilize an ensemble-based anomaly scoring method that aggregates the anomaly scores obtained from a set of multiple graph truncation scales, which enables TAM to 1) better utilize the dominant homophily edges for anomaly detection and 2) reduce the risk of being affected by non-homophily edges. As shown by extensive empirical results and the new results presented in the other replies to reviewers, TAM and its components show promising detection performance on a wide range of datasets, justifying their effectiveness in real-world graph anomaly detection applications."}, {"review_id": "20Wmzngxq9", "reviewer": "Reviewer_zqNH", "summary": "This paper studies the problem of graph anomaly detection and the authors proposed a novel method based on an identified property named one-class homophily. It is observed that normal nodes have strong connections with each other while abnormal nodes have weaker connections. Existing GAD methods overlook this property. The authors propose a novel unsupervised anomaly scoring measure, i.e., local node affinity, that considers the similarity of nodes to their neighbors. They introduce Truncated Affinity Maximization (TAM) to learn tailored node representations for this measure. TAM optimizes on truncated graphs to mitigate bias from non-homophily edges. Experimental results on several real-world graphs with both manually injected and real anomalies show that TAM outperforms several competing models, achieving over 10% improvement in AUROC/AUPRC on challenging datasets.", "questions": "- Theoretical analysis. Although the proposed method has shown its effectiveness using comprehensive experiments, i.e., comparing seven SOTA on real-world graphs with both manually injected and real anomalies, there is no theoretical analysis to justify the rationale of the proposed method.\n\n- Efficiency test. The largest graph used in the experiments contains ~4k nodes and ~175k edges, which are relatively not very large. To better demonstrate the efficiency of the method, larger graph benchmarks may be needed, e.g., OGB.\n\n- Component design and impact. Some components may need more investigation empirically, especially the graph truncation strategy as well as the impact of different K. In detail, (1) in section 4.2, the raw graph and (random) edge drop have been compared. A straightforward question is what is the performance of simple similarity-based methods, e.g., removing some less similar edges? (2) Since there are K truncated graphs and each one relies on the previous one, the number of edges will be less and less. Is it possible that for larger K, the graph will contain quite some isolated small subgraphs? If so, is there any negative impact on the performance?\n\nSome minor comments:\n- Figure 4(b) exhibits a variation in performance trends across different graphs. Particularly, on the Reddit and YelpChi datasets, the AUPRC decreases as the value of K increases. Is there an explanation for this contrasting behavior?", "limitations": "No potential negative societal impact or the authors adequately addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ This paper focuses on an interesting and important problem. Graph anomaly detection is of value in both research and practice, especially since it is beneficial for various applications.\n\n+ The proposed method is technically sound. The performance in several data with both manually injected and real-world anomalies is promising.\n\n+ The experimental results show that the proposed method achieves consistent performance improvements over the baselines, which demonstrates its superiority. Also, a comprehensive ablation study to show the effectiveness of different components.", "weaknesses": "- There is no theoretical analysis to justify the rationale of the proposed method.\n\n- The proposed method has not been tested on large-scale graphs to show its efficiency.\n\n- The design of some components may need more investigation empirically (see details below).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the overall positive rating and constructive comments. We are grateful for the positive comments on our studied problem, technical contribution and empirical justification. Please see our detailed response below.\n\n> **Weaknesses/Questions #1**: Lack of theoretical analysis to justify our method. \n\nThank you very much for the comments. We, for the first time, reveal the one-class homophily property in graph anomaly detection datasets by a number of empirical justifications. We further introduce a novel graph anomaly detection approach that provides a principled framework to leverage this property for the task. Unlike the overwhelming reconstruction-based and self-supervised learning frameworks, our approach offers a fundamentally different perspective on designing effective graph anomaly detection. Thus, although there is a lack of theoretical analysis, our work presents some solid findings and interesting insights into the graph anomaly detection problem. Therefore, while we're still working on an in-depth theoretical analysis of the proposed property and TAM, it would be beneficial to the anomaly detection community by publishing these interesting findings and novel insights.\n\n\n> **Weaknesses/Questions #2**: Results on large-scale graph datasets.\n\nPlease refer to our reply to **Global Response to Shared Concern #2** in the overall Author Rebuttal section above for detailed discussions on this point.\n\n> **Weaknesses/Questions #3**: The design of some components may need more investigation empirically (see details below), e.g., (1) simple similarity-based graph truncation methods, and (2) the impact of larger $K$ and possibly isolated small subgraphs. \n\n**Re: (1) Simple similarity-based non-homophily edge removal**. We agree that we may perform a deterministic similarity-based removal of less similar edges to obtain the truncated graph, and then optimize LAMNet using such a truncated graph. We present the experimental results of this TAM variant in Tables A1 and A2 below using varying similarity threshold $\\theta$. It is clear that this TAM variant significantly underperforms our default TAM on most of the datasets, i.e., BlogCatalog, Amazon, Facebook, and YelpChi. This is mainly because this variant would fail to take account of local affinity distribution of each node as being captured in NSGT. As a result, it could remove not only non-homophily edges but also homophily edges associated with normal nodes whose local affinity is not as strong as the other normal nodes, which would be the opposite to the objective of the optimization in our approach TAM, leading to less effective detection performance. \nThus, the simple similarity-based method cannot serve as an effective alternative to NSGT.\n\n```\nTable A1. AUC-ROC Results of Using Similarity-based Edge Removal.\n```\n|**Data**|**BlogCatalog**|**ACM**|**Amazon**|**Facebook**|**Reddit**|**YelpChi**|\n|:----|:----:|:----:|:----:|:----:|:----:|:----:|\n|$\\theta$=0.05|0.6650|0.8668|0.5856|0.6951|0.6007|0.4910|\n|$\\theta$=0.1|0.6526|0.7986|0.5827|0.7293|0.5945|0.4872|\n|$\\theta$=0.3|0.6583|0.6911|0.6106|0.7934|0.5758|0.4754|\n|TAM|**0.8210**|**0.8878**|**0.7064**|**0.9144**|**0.6028**|**0.5674**|\n\n```\nTable A2. AUC-PR Results of Using Similarity-based Edge Removal.\n```\n|**Data**|**BlogCatalog**|**ACM**|**Amazon**|**Facebook**|**Reddit**|**YelpChi**|\n|:----|:----:|:----:|:----:|:----:|:----:|:----:|\n|$\\theta$=0.05|0.1621|0.5109|0.0924|0.0410|**0.0467**|0.0598|\n|$\\theta$=0.1|0.1829|0.5068|0.1092|0.1154|0.0414|0.0509|\n|$\\theta$=0.3|0.1729|0.4996|0.2079|0.1374|0.0420|0.0519|\n|TAM|**0.4152**|**0.5124**|**0.2634**|**0.2233**|0.0446|**0.0771**|\n\n**Re: (2) the impact with increasing truncation steps K?** A short answer is: No. Specifically, in the process of early graph truncation, the edge will gradually decrease. However, since our truncation is based on the average similarity of the entire graph, all edges would stabilize near the average similarity after some truncation iterations. The changes in the graph also gradually stabilize. Since we do not have access to class labels, it is difficult to evaluate whether the truncation is too aggressive. Given the fact that the number of abnormal nodes per graph is assumed to be small, and so does the number of non-homophily edges, and thus, a small $K$, $K=5$, is used by default in our experiments.\n\n**Re: (2) any isolated small subgraphs produced by NSGT and their potential impact?** Yes, it is possible. If we perform multiple graph truncations, there would be some isolated small subgraphs, but this does not affect our subsequent affinity maximization. This is because NSGT is proposed to mitigate the bias toward non-homophily edges in the GNN neighborhood aggregation. This would only affect the neighborhood aggregation in GNNs; the calculation of the local node affinity-based anomaly score is still based on the original graph structure. Further, the small subgraphs resulting from NSGT indicate many nodes of the subgraphs have small affinity to the remaining nodes, indicating some sort of weak affinity of the nodes in the subgraphs. As a result, the local node affinity-based anomaly score for these subgraph nodes would be large, and furthermore, given the weak affinity of these subgraph nodes, their anomaly scores would also be large even if the subgraphs are not isolated after NSGT.  \n \n> **Minor Comments**: a variation in the performance on Reddit and YelpChi in Figure 4(b).\n\nThank you very much for the question. Being a probabilistic method,  the graph truncation has the risk of removing some homophily edges with relatively large distances. This risk can increase with increasing K values, as shown in Figure 5, Appendix C.3. We have considered this situation and addressed this potential issue by (1) adopting an ensemble-based scoring method that aggregates the anomaly scores across different K values to obtain stabilize the detection performance and (2) using a relatively small K value.  "}, {"review_id": "8ErCZRgfno", "reviewer": "Reviewer_oFzr", "summary": "This paper proposed an unsupervised algorithm for detecting abnormal nodes in a graph. Based on the one-class homophily assumption and the overwhelming presence of normal nodes in a graph, this paper uses the truncated affinity maximization to enable stronger local affinity for normal nodes than abnormal ones.  To eliminate the training bias brought by the non-homophily edges, Normal Structure-preserved Graph Truncation is proposed to remove non-homophily edges iteratively. The proposed method achieves competitive performance on datasets with synthetic and real anomalies.", "questions": "Please refer to Weaknesses.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-structured and easy to follow.\n2. The proposed method TAM has strong motivation. The unsupervised setting is close to realistic scenario that normal nodes and anomalies exist in a graph and their labels are unknown.\n3. Extensive experiments prove that TAM is a strong baseline for unsupervised anomaly node detection\n", "weaknesses": "1. I suggest adding some supervised graph anomaly detection method on section 2, such as CARE-GNN [1], PC-GNN [2] and Fraudre [3]. Although the supervised setting is far from reality, these algorithms also proposed some ideas for eliminating the negative impact of heterophily edges on anomaly detection.\n2. Is TAM wide-applicable on different GNNs? How does TAM perform on other GNN backbones other than GCN?\n3. In table 1, why baselines and TAM perform so poor regarding AUPRC. It would be better to draw the roc curve and precision-recall curve.\n4. It is difficult to understand Figure 2 (b), what are $c_1$, $c_2$, $c_k$? I suggest reorganizing this illustration.\n5. I suggest placing the limitation in a separate paragraph or subsection. Besides the limitations discussed in Conclusion, are there any other shortcoming of TAM?\n\n[1] Enhancing graph neural network-based fraud detectors against camouflaged fraudsters\n\n[2] Pick and choose: a GNN-based imbalanced learning approach for fraud detection\n\n[3] Fraudre: Fraud detection dual-resistant to graph inconsistency and imbalance\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the overall positive rating and constructive comments. We are grateful for the positive comments on our paper clarity, research motivation, and empirical justification. Please see our response to your comments one-by-one below.\n\n> **Weaknesses #1**: To add some supervised graph anomaly detection methods in Sec. 2\n\nThank you very much for the suggestion.  Supervised graph anomaly detection has drawn increasing attention in recent years, such as the emerging of multiple supervised methods like CARE-GNN,  PCGNN, Fraudre , BWGNN , and GHRN. These methods propose various supervised effective methods to deal with heterophily edges in GNN aggregation, so as to better improve the performance of anomaly detection. We agree that despite being supervised methods, they may inspire designs on exploring the one-class homophily property and alike for better unsupervised graph anomaly detection. We will discuss the corresponding references to discuss those supervised methods and possible opportunities along this research line in Sec. 2.\n\n> **Weaknesses #2**: How does TAM perform on other GNN backbones other than GCN?\n\nAs shown by the results in Tables A1 and A2 below, TAM can also work effectively when using GNN backbones other than GCN.  Particularly, TAM using GAT can have some large improvement on multiple datasets like Amazon and Facebook than GCN, while having similar performance on the other datasets. GraphSage and GIN perform inferior to GCN on most of the datasets, since using backbones like GraphSage would lead to the loss of important local information of some nodes due to its small node sampling size during neighborhood aggregation. The inferior effect of GIN might be because our task is different from supervised node classification, where we emphasize more on how to learn the representation of nodes while our method emphasizes more on learning the local node affinity. In general, TAM can achieve good performance using other GNN backbones, but it can have large performance drop on some datasets when comparing to the performance using GCN/GAT, so TAM works best using GCN or GAT. \n\n```\nTable A1. AUC-ROC for Different GNN Backbones.\n```\n|**Data**|**GCN**|**GAT**|**GraphSage**|**GIN**|\n|:----|:----:|:----:|:----:|:----:|\n|BlogCatalog|**0.8248**|0.8145| 0.7767|0.7682|\n|ACM|0.8878|**0.8891**|0.7313|0.7833|\n|Amazon|0.7064|0.7245|**0.7532**|0.7034|\n|Facebook |0.9144|**0.9394**|0.7372|0.8216|\n|Reddit   |**0.6023**|0.5999|0.5629|0.5348|\n|YelpChi|0.5643|**0.5787**|0.5243|0.5614|\n\n```\nTable A2. AUC-PR for Different GNN Backbones.\n```\n|**Data**|**GCN**|**GAT**|**GraphSage**|**GIN**|\n|:----|:----:|:----:|:----:|:----:|\n|BlogCatalog|**0.4182**|0.3952|0.3844|0.3615|\n|ACM|0.5124|**0.6701**|0.4940|0.4087|\n|Amazon|0.2634|0.3127|**0.4407**|0.2666|\n|Facebook |0.2233|**0.3010**|0.1384|0.1578|\n|Reddit   |**0.0446**|0.0407|0.0409|0.0377|\n|YelpChi|0.0778|**0.0778**|0.0665|0.0727|\n\n\n> **Weaknesses #3**: In table 1, why baselines and TAM perform so poor regarding AUPRC. To draw the roc curve and precision-recall curve.\n\nThank you very much for the question and suggestion. Since 1) anomaly detection datasets are often an extremely imbalanced one and 2) no labeled data is available for training, it is very difficult for unsupervised detectors to achieve both high precision and recall rates on detecting the rare anomalies, leading to small values of AUC-PR (or AUPRC). As for AUC-ROC, its performance is often overoptimistic because 1) it is affected by performance on both normal and anomaly classes and 2) the normal class is the dominant class whose performance would bias the overall performance. \n\nAs a result, it is common to achieve pretty good AUC-ROC but poor AUC-PR performance in unsupervised anomaly detection task (see the results of unsupervised detectors on the far left in Figures D4 & D5 in *Han, S., Hu, X., Huang, H., Jiang, M., & Zhao, Y. (2022). ADBench: Anomaly Detection Benchmark* for some evidence), except that the test data contains many anomalies . \nAUC-PR and AUC-ROC are commonly used as complementary evaluation metrics in graph anomaly detection in the community, because AUC-PR reflects more realistic performance on the anomaly class while AUC-ROC has a good probabilistic interpretation.\n\nWe have inserted the ROC curve and Precision-Recall curve of TAM on the six datasets used in Figure 2 in the pdf file in the Author Rebuttal section above. We will add them in the final paper.\n\n> **Weaknesses #4**: Difficult to understand $c_1$,  $c_2$,  and $c_k$ in Figure 2 (b).\n\nThank you very much for the question and suggestion. We originally intended to use $c_1$,  $c_2$,  and $c_k$ to represent the progressive iteration of our graph truncation. We will reorganize this illustration to provide a more straightforward view of the iterative graph truncation.\n\n> **Weaknesses #5**: Are there any other shortcoming of TAM?\n\nThank you very much for the suggestion and question. We will place the discussion of TAM's limitations in a separate paragraph.\nIn addition to the possible presence of non-homophily cases in some real-world datasets, as also pointed out by Reviewer **NSnj**, another potential limitation is that TAM cannot directly handle primarily isolated nodes in a graph, though those isolated nodes are clearly abnormal if they are rare and the other nodes are connected to at least some nodes. Additionally, like many GNN-based approaches, including graph anomaly detection methods, TAM also requires a large memory to perform on graphs with a very large node/edge set. \n\nNote that these limitations do not affect the detection effectiveness of TAM on a variety of popular real-world graph anomaly detection datasets. Most importantly, it is a seminal work on the idea of one-class homophily and local node affinity maximization specifically for graph anomaly detection, which opens up some great opportunities for exploring substantially more effective anomaly detectors from a new perspective."}]

Author rebuttal:
Dear All Reviewers,

Thank you very much for the time and effort on reviewing our paper, and for the constructive and positive comments. Our rebuttal consists of two part: **Global Response** where we address shared concerns from two or more reviewers and **Individual Response** where we provide a detailed one-to-one response to address your questions/concerns individually.

> **Global Response to Shared Concern #1**: The one-class homophily property may not hold for all graph anomaly detection datasets, such as YelpChi-RUR.

As we show in the paper that the one-class homophily generally holds in popular real-world graph anomaly detection datasets, including datasets with either injected or genuine anomalous nodes. Further, this homophily property also holds for the four large-scale datasets we newly add, T-Finance , Amazon-all, YelpChi-all  and OGB-Protein (see Figure 1(a-d) in the uploaded pdf file for the visualization). 

We agree that the one-class homophily may not alway hold, or it is weak in some datasets. YelpChi-RUR is an example of the latter case. As shown in Figure 1 (d) in Appendix A, the homophily distribution of normal and abnormal nodes is similar in YelpChi-RUR, whose pattern is different from the large distribution gap in the other three datasets. Nevertheless, despite having a similar distribution, it is clear that the homophily distribution of normal nodes is still much stronger than that of abnormal nodes on YelpChi-RUR, as shown in the figure. As a result, when applying NSGT for graph truncation, we can still successfully remove the non-homophily edges that connect normal and abnormal nodes with a higher probability than the homophily edges, resulting in a truncated graph with stronger one-class homophily (see Figure 1(e)(f) in the uploaded pdf file for a comparison of homophily before and after the truncation). This enables better detection performance of our method (an AUC of 0.5643) on YelpChi-RUR compared to SOTA models (e.g., an AUC of 0.4956 for the best competing method).

It should be noted that the widely-used general homophily property can also do not hold in some real-world datasets, such as those for node classification [Ref1-Ref3], where many connected nodes are from different classes. This situation can also apply to our proposed one-class homophily property. However, as the first work on the one-class homophily, we focus on the justification of this property and a novel approach to effectively utilize it for popular graph anomaly detection datasets, including those that has a weaker one-class homophily property and datasets of diverse characteristics. This offers a new perspective to design graph anomaly detection methods, promoting the development of more effective graph anomaly detection algorithms that do not use the overwhelming reconstruction/self-supervised frameworks. Exploring the possible presence of heterophily phenomenon in graph anomaly detection datasets and how to effectively avoid such issues in the detection algorithms (including our method TAM) would be some important, interesting follow-up problems to be addressed.

**References**
- [Ref1] Graph neural networks with heterophily.  AAAI.
- [Ref2] Finding global homophily in graph neural networks when meeting heterophily.  PMLR.
- [Ref3] Graph neural networks for graphs with heterophily: A survey. arXiv preprint arXiv:2202.07082.

> **Global Response to Shared Concern #2**:  Any empirical support from results on large-scale datasets?

Inspired by your comments, we add more experiments on two dataset with a large set of edges, Amazon-all and YelpChi-all by treating the different relations as a single relation. In addition, we add another two large datasets T-Finance and OGB-Proteins with a large set of edges and/or nodes. Their key statistics are given in Table A1 below.

```
Table A1. Key Statistic of New Datasets.
```
|**Data**|**Nodes**|**Edges**|**Features**|**Anomaly**|
|:----|:----:|:----:|:----:|:----:|
|Amazon-all| 11,944|4,398,392 |25|9.5%|
|YelpChi-all| 45,954|3,846,979|32|14.5%|
|T-Finance | 39,357|21,222,543|10|4.6%|
|OGB-Protein |132,534 |39,561,252 |8|4.5%|

The results in the two tables below show that TAM also obtains large detection improvement over four best-performing competing methods across four datasets (comparably well to DOMINANT in AUC-PR on OGB-Protein).

```
Table A2. AUC-ROC Results.
```
|**Data**|**Amazon-all**|**YelpChi-all**|**T-Finance**|**OGB-Proteins**|
|:----|:----:|:----:|:----:|:----:|
|DOMINANT|0.6937|0.5390|0.5380|0.7267|
|ComGA|0.7154|0.5352|0.5542|0.7134|
|CoLA|0.2614|0.4801|0.4829|0.7142|
|SL-GAD|0.2728|0.5551|0.4648|0.7371|
|TAM|**0.8476**|**0.5818**|**0.6175**|**0.7449**|
```
Table A3. AUC-PR Results.
```
|**Data**|**Amazon-all**|**YelpChi-all**|**T-Finance**|**OGB-Proteins**|
|:----|:----:|:----:|:----:|:----:|
|DOMINANT|0.1015| 0.1638|0.0474|**0.2217**|
|ComGA|0.1854|0.1658|0.0481|0.1554|
|CoLA| 0.0516|0.1361|0.0410| 0.1349|
|SL-GAD|0.0444|0.1711|0.0386|0.1771|
|TAM|**0.4346**|**0.1886**|**0.0547**|0.2173|

Performing experiments of using TAM and its competing methods on datasets with a even larger number of nodes, such as DGraph that has millions of nodes, requires a GPU server with an extremely large memory. We're currently lack of those computing resource to do that. Note that many existing graph anomaly detection methods, and GNN-based methods for other tasks as well, have similar issues w.r.t. scaleup to such large datasets. We will try to add results on DGraph in the final paper by tapping Amazon cloud computing service for the experiments.

As for **Individual Response**, we have provided a detailed one-by-one response to answer/address your questions/concerns after your individual review.

We very much hope our response has clarified the confusions, and addressed the concerns. We're more than happy to take any further questions if otherwise. Please kindly advise, and have a great week ahead!

Best regards, 

Authors of Paper 9585

Meta-review: I agree with most of the reviewers to recommend the acceptance of this paper after the detailed rebuttal and extra experimental results from the authors to address many questions and issues raised by reviewers. But in the meanwhile, I would encourage the authors to take the reviewers' feedbacks in the preparation of the camera ready. For example, in additional to empirical justification, it will be good to provide a little bit more insight and analysis to explain about why it might be more robust to handle camouflaged features.
Decision: Accept (poster)