Beyond Homophily: Robust Graph Anomaly Detection via Neural Sparsification

1 Introduction

Graph-based Anomaly Detection (GAD) refers to identifying anomalies that deviate significantly from the majority of objects in relational and structured data. With graph data becoming ubiquitous and ever-growing, graph-based anomaly detection has received increasing attention on account of its vast applications, such as spammer recognition [Ye and Akoglu, 2015], financial fraudster identification [Weber et al., 2019] and sensor fault detection [Gaddam et al., 2020]. Due to the complex interactions between nodes in real-world systems (e.g., partnership in a social network or transactions on a financial platform), detecting anomalies within graph data becomes more challenging than anomaly detection in noninteraction feature space (e.g., image).

Most recently, Graph Neural Networks (GNNs) serve as popular approaches for graph-structure data and are naturally applied in GAD [Dou et al., 2020; Liu et al., 2021]. Driven by the message passing scheme, standard GNN methods usually recursively aggregate and transform the representations of neighbors for each ego node and categorize the abnormal cases. However, many investigations [Dou et al., 2020; Liu et al., 2020] discover that anomalies tend to camouflage themselves and mitigate suspiciousness by connecting with substantial benign entities. Considering a social network as an instance, where nodes represent users and edges indicate relationships, fraudsters establish insincere links to real users, and they can effortlessly inject wrong structure information into the entire network, which leads to poor performance of estimating user credibility via the plain GNNs.

∗Work done during an internship at Huawei.

†Corresponding Author.

To remedy this issue, the existing GAD methods can be generally divided into three categories. That is, (1) applying resampling strategy to selectively aggregate neighborhood information by measuring the label similarity of node pairs [Dou et al., 2020; Liu et al., 2021], (2) designing spectral-based architectures based on adaptive low and high-passing filters [Chai et al., 2022; Tang et al., 2022], (3) adding auxiliary loss to strengthen the expressive power of network [Ding et al., 2019; Zhao et al., 2020].

Although some encouraging progress has been achieved, the capability of anomaly detectors against noisy graph structures remains to be further investigated and enhanced, since the unknowable and ever-changing behaviors of anomalies hinder anomaly detection and lead to poor robustness [Chang and Chang, 2014]. A natural and fundamental question arises here: how to resist structure noises of GAD for detecting anomalies robustly? As GNNs are fragile when graphs have disturbing edges, our work is motivated by the intuition that sparsifying graph structures by selecting task-relevant edges not only enhances the detection robustness but also facilitates discovering essential neighbors, for example, an accomplice of fraudsters. Furthermore, there are indeed two disparate and essential connection properties, i.e., homophily and heterophily in GAD. Specifically, the connected nodes have similar attributes or the same category labels, called homophily, while the connections between dissimilar nodes in terms of attributes or labels are referred to as heterophily. In real-life graphs for anomaly detection, such as Amazon [McAuley and Leskovec, 2013] and Reddit [Kumar et al., 2019], the connections involving anomalies or benign entities are diverse in homophily and heterophily. How to sparsify graph structures and aggregate neighborhood information under such complex interactions remains to be further explored.

With these in mind, we propose a neural sparsification framework for GAD (short for SparseGAD). As illustrated in Figure 1, under the framework, we can effectively optimize the sparsification of graphs and collaboratively learn node representations in consideration of homophily and heterophily, which, to the best of our knowledge, has not been studied before. In practice, our SparseGAD has a three-stage process for this task. First, we exploit a GNN to infer a novel adjacency matrix where the value of each entry can represent the informativeness and properties of neighbors to ego nodes. Second, we sparsify the graph structure by removing taskirrelevant edges and discovering the closely related nodes as neighbors. Third, we share the parameters of GNN in the first stage, conduct the heterophily-aware aggregation scheme to represent each node, and categorize suspicious cases. Our extensive experiments on real-world datasets of GAD demonstrate the superiority and robustness of SparseGAD.

2 RelatedWork

Graph Neural Networks (GNNs). GNNs [Kipf and Welling, 2017; Veliˇckovi´c et al., 2018; Hamilton et al., 2017] have demonstrated their capacity in various machine learning tasks built upon graph structure data [Wang et al., 2018; Wang et al., 2019], such as molecular property prediction [Zhang et al., 2021], talent acquisition [Sun et al., 2021] and point of interests retrieval [Huang et al., 2021]. Some extensively-used GNNs, such as Graph Convolution Network (GCN) [Kipf and Welling, 2017] implicitly leverage the homophily assumption, resulting in the oversmooth problem with the increasing depth of GNN layers. The common philosophy behind non-homophilic (a.k.a heterophilic) approaches is to weaken the smooth effect. For instance, APPNP [Gasteiger et al., 2019] and GCNII [Chen et al., 2020a] average the GNN-smoothed node representations with the original linear-transformed node embeddings. FAGCN [Bo et al., 2021] and GPR-GNN [Chien et al., 2021] assign learnable weights that can be positive or negative in the aggregation of neighbors' representations and layers' representations respectively.

Graph Structure Learning (GSL). GSL methods aim at rebuilding or refining graph structure to boost GNN performance by following a general pipeline: the adjacency matrix of the graph is characterized with learnable parameters and then jointly optimized with GNN under the supervision of downstream tasks (e.g., node classification [Luo et al., 2021]) or self-supervised signal (e.g., reconstruction error [Fatemi et al., 2021] and contrastive loss [Liu et al., 2022b]). Due to the discrete inherence of the graph structure, the key of GSL is how to parameterize the adjacency matrix. One type of methods [Fatemi et al., 2021; Jin et al., 2020] directly treats each element in the adjacency matrix as a learnable parameter under the assumption of edge independence, while another type of method selects the top-K similar nodes as the ego node's new neighbors by computing node-pair similarity [Liu et al., 2022b; Yu et al., 2020]. Besides, some methods [Jin et al., 2021; Liu et al., 2023] rebuild the topology of graphs thoroughly considering the homophily. However, most recent GSL methods are evaluated in homophilic scenarios, leaving works on heterophilic applications with abundant structure noise (esp. anomaly detection) unexplored.

GNN-based Anomaly Detection. Considering the trend that anomalies, such as financial fraudsters, connect to abundant normal users, which limits the power of conventional GNN (e.g., GCN) based on the homophilic assumption, various techniques are leveraged to alleviate the negative impact. From the spectral domain, AMNet [Chai et al., 2022] and BWGNN [Tang et al., 2022] both design multi-pass spectral filters to discover high-frequency anomalies. To select important neighbors, CARE-GNN [Dou et al., 2020] and AOGNN [Huang et al., 2022] both use a Reinforcement Learning module by taking the neighbors' similarity measurements with ego nodes and AUC performance as rewards, respectively. While PC-GNN [Liu et al., 2021] directly measures the anomaly probability gap by training an additional MLP with only the node attributes as input. Nevertheless, few works investigate the sparsification of the noisy graph structures in GAD to enhance the robustness of anomaly detection.

3 Preliminary and Problem Statement

In this section, we first introduce the conceptions of homophily and heterophily. Then we describe the specific definition of our paper objective, i.e., graph-based anomaly detection. After that, we introduce the GNN backbone of our SparseGAD framework, which can also be replaced by other advanced GNN architectures.

Homophily versus Heterophily. In homophilic graphs, connected node pairs tend to have same category labels or similar attributes. In contrast, the edges link two dissimilar nodes in the heterophilic graphs. Remarkably, the graphs in GAD embody homophilic and heterophilic edges together.

Graph-based Anomaly Detection. In this paper, we focus on attribute graphs for anomaly detection. Specifically, given an attribute graph G = (V,A,X) as input, V is the node set with size n = |V|, and E ⊆ V × V represents the edge set. We denote the adjacency matrix of G as A ∈ {0, 1}n×n , where Aij = 1 if node vi connects to node vj, i.e., eij ∈ E and Aij = 0 otherwise, and N(v) is the neighbor set of node v. X ∈ Rn×f is the matrix of node attributes where each row vector Xv ∈ Rf is the corresponding attributes of node v. A part of nodes V ′ ⊆ V has a corresponding binary label yv ∈ {0, 1}, where 0 represents benign entity and 1 represents anomaly, while other nodes remain unknown. Considering notable structure noises arise in the neighbors of anomalies which harms the performance of GNNs [Dou et al., 2020; Yang et al., 2020], the task aims at predicting the suspiciousness of unlabeled nodes by training an anomaly detector on the labeled node information along with the sparsified subgraph g′ of graph G. The optimized graph topology of g′ is expected to capture the underlying dependence of two nodes and thereby facilitate detecting anomalies robustly.

GNN Backbone. Generally speaking, our GNN is a function fGNN : X,A → {zv}, which maps to the representations of each node v with node attribute matrix X and adjacency matrix A as input. Specifically, we first transform the node attributes with a linear layer h0v = W0Xv + b0, where h0v , b0 ∈ Rd , W0 ∈ Rd×f , and d is the hidden dimension of node representations. Then we utilize a GNN with K layers to aggregate neighbors' information and derive each node's representation. In the k-th layer of GNN, the representation hkv of node v is derived through:

where Wk ∈ Rd×d are the learnable parameters, u ∈ N(v) is the neighbor of node v in the adjacency matrix A, and σ is the activation function. Please note that the values of ckuv control the weights of message aggregation from neighbors, and we will illustrate two settings of ckuv , which play different roles, in subsection 4.3 and subsection 4.5.

Since the anomalies connect to substantial benign entities, over-smoothing neighbors' information limits the power of our model to detect abnormal nodes. Hence, we adopt the aggregation mechanism of Personalized PageRank-based GNN [Gasteiger et al., 2019; Chien et al., 2021] and obtain the aggregated representation zv of node v:

where γk ∈ R is a learnable parameter, and we initialize the parameters {γk}Kk=0 as γk = α(1 - α)k for k ∈ [0,K - 1], γK = (1 - α)K with α being a hyperparameter.

4 Method

4.1 Framework Overview

Real-life graphs in anomaly detection usually have complex information in the local neighborhood, where each node builds diverse relationships with dozens of neighbors [McAuley and Leskovec, 2013; Rayana and Akoglu, 2015]. Moreover, anomalies camouflage themselves by establishing false connections with substantial benign entities [Dou et al., 2020; Liu et al., 2020]. Hence, there exist two essential characteristics of GAD. First, neighbors have varying degrees of informativeness to estimate the ego node credibility due to complex relations, such as friendships and partnerships. We can thereby implement sparsified graph by selecting task-relevant edges to enhance the robustness of anomaly detection. Second, the behaviors of anomalies lead to the widespread heterophily in GAD, and thus distinguishing between homophilic and heterophilic neighbors contributes to identifying anomalies based on the message aggregation scheme of GNN.

Accordingly, to characterize the informativeness of neighbors considering homophily and heterophily, we introduce a learnable adjacency matrix H (hereinafter simplified as homey for brevity), which can further facilitate reducing structure noises and aggregating neighborhood information to robustly detect anomalies. Specifically, assuming we have a graph G = (V, A, X), we derive H from G via homey graph generator F parameterized by φ, a deterministic function as H = Fφ(G). We incorporate H and formulate the GAD task from the perspective of statistical learning:

where Y is the prediction target, i.e., anomaly detection, and SG is a set of sparsified graphs of G. However, it is intractable to enumerate all possible g ∈ SG, and thus we approximate the distributions P(Y |g) and P(g|G,H) by tractable functions [Zheng et al., 2020]:

where Qθ and Qψ are approximation functions for P(Y |g) and P(g|G) parameterized by θ and ψ, respectively. Furthermore, to make the above graph sparsification differentiable, we apply reparameterization trick [Kool et al., 2020] to generate the differentiable sample g′ as:

where g′ ∼ Qψ(g|G,H) denotes g′ = (V,A′ ,X) is a sparsified graph sampled from Qψ(g|G, H).

4.2 Framework Architecture

In this paper, we propose SparseGAD to implement Equation (5). As shown in Figure 2, SparseGAD consists of three essential components:

• Homey Graph Generator is a GNN with an MLP transformation that implements H = Fφ(G) to generate the homey adjacency matrix which captures the informativeness and properties of neighbors.
• Graph Sparsification is a sampling module that implements g′ ∼ Qψ(g|G,H) to sample sparsified graph g′ .
• Homey Message Passing is a GNN that categorizes suspicious cases Qθ(Y |g′ ,H) with the sparsified graph g′ and homey adjacency matrix H as input.

To enable end-to-end and stable training, we share the GNN parameters of homey graph generator with homey message passing and assign different values to ckuv in Equation (1) depending on the goals of each module. In the following subsections, we will demonstrate these components extensively.

4.3 Homey Graph Generator

The goal of homey graph generator is to generate homey adjacency matrix H = Fφ(G) to facilitate sparsifying graph G to reduce noises and aggregating messages of neighbors with homophily and heterophily into consideration. Practically, we first obtain node representations {zv} with node attribute matrix X and adjacency matrix A of G as the input of GNN illustrated in Section 3. During this process, we set ckuv = 1/√(du + 1) (dv + 1) following GCN [Kipf and Welling, 2017], where du and dv are the degrees of node u and v in adjacency matrix A, respectively.

To capture the underlying dependence of node pairs and help discover the underlying neighbors of anomalies and benign entities, we bring in the versatile homey adjacency matrix H, which accommodates the following assumptions:

Assumption 1. The absolute edge weight |Huv| shall reflect the informativeness of neighbor u to ego node v. When the neighbor u has no impact on node v, the absolute value |Huv | → 0.

Assumption 2. The value Huv can help distinguish whether the neighbor u is homophilic or heterophilic.

Since the heterophilic links make up a significant portion of connections involving anomalies, appropriately capturing the connection properties contributes to the detection quality.

In practice, we use a two-layer MLP to transform the representation zv of Equation (2) as z′v = MLP(zv) and calculate the cosine similarity of node pairs as the value of each entry of homey adjacency H:

Based on homey adjacency matrix H, we distinguish neighbor u to ego node v as homophilic, worthless or heterophilic:

The value of Huv is optimized by the learning objective in subsection 4.6, not directly supervised by the edge types [Shi et al., 2022]. Unlike the attention mechanism applied in GAT [Veliˇckovi´c et al., 2018] constraining the learned edge weight to be non-negative via a softmax nonlinear function, cosine similarity allows Huv to zero-centered real values ranging in [-1, 1]. Note that cosine similarity can be replaced by other functions. In our experiment results, we find cosine similarity effective in the majority of datasets. Besides, cosine similarity is beneficial from two perspectives. That is, (1) keeping symmetry, i.e., Huv = Hvu without any other adjacency post-processor, like (H + HT )/2 in some GSL works [Fatemi et al., 2021; Liu et al., 2022b], (2) containing no extra learnable parameters and effortlessly adapting to our graph sparsification module.

4.4 Graph Sparsification

Due to the camouflage behaviors of anomalies, structure noises inherently exist in unsparsified graph G. Hence, we sparsify structures of G to achieve the following targets. First, we remove unnecessary neighbors which may inject false information into the aggregation mechanism of GNN and decline the anomaly detection performance. Second, the closely related nodes are identified as potential neighbors to obtain profitable signals from other nodes. Third, we regularize the adjacency matrix to keep sparsity in the end-to-end training.

As the absolute value of each entry |Huv| captures the informativeness of neighbor u to ego node v, we first filter unnecessary neighbors of node v with a threshold δ:

Meanwhile, we discover the potential neighbors of nodes based on the H through k-nearest neighbors (kNN). As an efficient alternative, we suggest sampling k-nearest neighbors via the Gumbel-Top-k trick [Kool et al., 2020; Kazi et al., 2022]. The sampling strategy can be viewed as a stochastic relaxation of kNN. Specifically, the probability of sampling each node u /∈ N(v) is normalized by puv = |Huv|/ ∑w/∈N(v) |Hwv| to follow the categorical distribution [Kool et al., 2020]. Then we select the nodes with top-k αuv values as new neighbors N2(v):

where ϵ is drawn from Uniform(0, 1) independently for each node u, and top-k(α∗v) is the set of top-k values in the column vector α∗v. In this paper, we implement kNN on the whole graph. While for large graphs, one can approximate it using locality-sensitive hashing approaches [Halcrow et al., 2020] and reduce the time complexity of kNN from O (n2 ) to O(sn(B + logn)), where s is the number of hashes per node, and B is the size of buckets. In our work, we resort to brute-force algorithm [Li and Amenta, 2015] to reduce the space complexity of kNN from O (n2 ) to O (nk) and thereby accelerate kNN on GPU devices.

We obtain the neighbors N ′ (v) of node v in the sparsified graph g′ by assembling the filtered neighbors N1(v) and the kNN neighbors N2(v) as N ′ (v) = N1(v) ∪ N2(v). Accordingly, the each entry A′uv of sparsified adjacency matrix A′ ∈ {0, 1}n×n equals to 1 when u ∈ N ′ (v).

Moreover, we regularize the homey adjacency matrix H to sparsify the graph G. A direct way to solve sparsification is minimizing the ℓ1-norm [Chen et al., 2020b] and nuclear-norm [Koltchinskii et al., 2011] of the adjacency matrix. However, some investigations [Jin et al., 2020; Zhu et al., 2021] indicate that non-differentiable ℓ1-norm and nuclear-norm optimize the adjacency matrix even more challenging in the end-to-end training and need unique optimization algorithms, such as Forward-Backward splitting method [Combettes and Pesquet, 2011]. Besides, these methods optimize the adjacency directly, and thereby they are intrinsically transductive and cannot adapt to graphs with unseen nodes [Zhu et al., 2021].

To address these issues, we develop a GAD-oriented regularization for sparsifying graph G. Since excessive sparsification of the adjacency matrix may lead to sub-optimal classification results, inspired by Gumbel-Softmax [Jang et al., 2017], we derive the sparsification normalization Lr to encourage the absolute value |Huv| of each entry where edge (u, v) in the unsparsified G to approximate 1 or 0 via entropy:

where ωuv = max(δ,min(|Huv|, 1 - δ)), and τ ≥ 0 is a hyperparameter to control the expectation sparsity of H. The smaller τ means entry values of H below a higher threshold are desirably optimized to 0. In other words, smaller τ means more sparsed g′ . We truncate the gradient of |Huv| via δ in Equation (8) to reduce the computational cost of the edges with the highest probability to be removed or reserved.

4.5 HomeyMessage Passing

After we obtain the sparsified graph g′ , we categorize the suspicious nodes through a GNN. Note that we share the parameters of GNN with the inference in subsection 4.3. The majority of GSL methods [Liu et al., 2021; Fatemi et al., 2021; Liu et al., 2022b] focus on learning graph structure and classifying nodes via different architectures, which may cause extra overhead on space and lead to an unstable training process due to the different scales of parameters.

Moreover, we incorporate the homey adjacency matrix H in the message passing procedure of GNN due to the following reasons. First, a substantial of edges in GAD assist in concealing anomalies, and we shall control the message passing on this part of edges. Since absolute edge weight |Huv| reveals the informativeness of neighbor u to ego node v, we control the message flows from neighbors with |Huv| as a message gate. Second, the neighbors of anomalies mostly are not homophilic in terms of attributes, even some other anomalies, since the behaviors of anomalies are most probably diverse and unpredictable. Hence, we take into account homophily and heterophily in the process of message passing via homey adjacency matrix H.

Specifically, we obtain the final node representations {ˆzv} by applying the GNN described in section 3 with the sparsified g′ as input. We set the value ckuv in Equation (1) as:

where d′u and d′v are the degree of node u and v in adjacency matrix A′ of sparsified graph g′ , respectively. Intuitively, from the perspective of the spectral GNNs, positive values of Huv are equivalent to low-pass filters, whereas the negative values of Huv indeed facilitate the filtering beyond low-frequency [Yang et al., 2021; Chien et al., 2021]. In this vein, we can detect anomalies in both low and high frequency with the aid of flexible Huv.

4.6 Learning Objective

Our training objective includes two parts. First, we classify the final representations {ˆzv} of nodes into two categories, i.e., benign or abnormal, via a linear transformation:

where W ∈ Rd×1 , b ∈ R, and ˆ yv ∈ (0, 1) denotes the probability of node v belonging to anomalies. The node classification loss is derived from cross-entropy loss:

The second objective is the sparsification regularization Lr derived from Equation (10). The final learning objective of our model is L = Lc + λLr, where λ is a hyperparameter controlling the relative importance of the node classification loss Lc and sparsification normalization Lr.

5 Evaluation

5.1 Experimental Setup

Dataset. We conduct extensive experiments to evaluate SparseGAD on three real-world anomaly detection datasets:

• Amazon [McAuley and Leskovec, 2013] collects the product reviews of the Musical Instrument category on Amazon.com, in which nodes are benign/fraud users.
• YelpChi [Rayana and Akoglu, 2015] includes the hotel and restaurant reviews filtered (spam) as anomalies and recommended (legitimate) as normal nodes by Yelp.
• Reddit [Kumar et al., 2019] consists of user posts on one month collection of subreddits. The ground-truth labels of banned users are obtained from Reddit.

We process the connections of node pairs in Amazon and YelpChi following [Dou et al., 2020], and Reddit is loaded from PyGod package [Liu et al., 2022a]. The performance of our method is conducted on homogeneous settings, i.e., without the category information of edges, and we leave the adaption of SparseGAD for multiple node types and edge types of heterogeneous graphs in our future works.

The statistics of these datasets are shown in Table 1. We further show the edge homophily [Zhu et al., 2020] and node homophily [Pei et al., 2020] of normal nodes and anomalies for each dataset. The edge homophily HEdge is the proportion of edges that link two nodes of the same classes:

while the node homophily of class C is calculated as:

where C includes normal nodes and anomalies. We discover that the anomaly homophily HAnomaly of the datasets in Table 1 are all significantly lower than normal nodes HNormal, which indicates that heterophilic links are the major part of connections involving anomalies.

Metrics. Following previous works in GAD [Dou et al., 2020; Chai et al., 2022], we evaluate the detection performance with two widely-used and complementary metrics: (1) AUC-ROC reflects the detectors' effectiveness on both normal and abnormal nodes, while (2) Average Precision (AP) focuses more on the anomalies.

Baselines. To verify the effectiveness of our SparseGAD, we compare it with three types of baselines. (1) General GNNs, which consist of GCN [Kipf and Welling, 2017], GAT [Veliˇckovi´c et al., 2018], GraphSage [Hamilton et al., 2017], GIN [Xu et al., 2019] and GPRGNN [Chien et al., 2021]. (2) Graph Structure Learning methods, such as Neural Sparse [Zheng et al., 2020], IDGL [Chen et al., 2020b] and SLAPS [Fatemi et al., 2021]. (3) GNN-based anomaly detectors, including CARE-GNN [Dou et al., 2020], PCGNN [Liu et al., 2021], AMNET [Chai et al., 2022] and BWGNN [Tang et al., 2022].

In addition to representative baselines, we also include two variants of SparseGAD to validate the effectiveness of modules: (1) SparseGAD (GCN) utilize Graph Convolution Network [Kipf and Welling, 2017] as the backbone. (2) SparseGAD-s, which removes the sparsification module (or keep g′ = G and λ = 0). (3) SparseGAD-h ignores heterophily exists in GAD by setting Huv = sigmoid(z′u · z′v ).

Experiment Settings. For each experiment, we train all models for 2000 epochs by Adam optimizer. We optimize all models on each dataset by selecting learning rate from {0.01, 0.005, 0.001}, hidden states from {16, 32, 64} and dropout rate from {0, 0.1, 0.2} via grid search, and save the model according to the best AUC in validation. As for SparseGAD, α of Equation (2) and λ are both set to 0.1, and δ is set to 0.05 for all datasets. For each dataset, we search k of kNN from {5, 10, 20} and τ from {0.5, 1.0, 2.0}. We select 40% nodes for training models in supervised scenarios and 1% in semisupervised scenarios. The remaining nodes are split by 1:2 for validation and testing. We report the average value and standard deviation of ten independent runs for each dataset. As for the detailed experiment settings, please refer to our code https://github.com/KellyGong/SparseGAD.git.

5.2 Detection Performance

The anomaly detection results of baselines and SparseGAD are reported in Table 2. Overall, SparseGAD achieves the best detection quality in all datasets except Amazon (40%), where BW-GNN obtains the best AUC and AP scores. Under the semi-supervised scenarios (i.e., YelpChi (1%) and Amazon (1%)), SparseGAD outperforms baselines by a large margin. For instance, in YelpChi (1%), which includes only 67 labeled anomalies, SparseGAD has 4.6% and 2.4% absolute improvements in AP and AUC score compared to BW-GNN, which illustrates the superiority of SparseGAD with lowresource anomaly labels. Moreover, the strong heterophily of anomalies (i.e., HAnomaly = 0) in Reddit leads to the worse performance of advanced graph-based anomaly detectors compared to GAT. By contrast, SparseGAD has consistent improvements in this dataset, proving both the scalability and superiority of our framework.

5.3 Robustness Performance

To compare the robustness of SparseGAD against structure noises with other detectors, we evaluate the detection performance under two types of attacks. i). Random Attack [Jin et al., 2020] injects fake edges into the graph, which can be viewed as adding random structure noises to the clean graphs. ii). DICE [Z¨ugner and G¨unnemann, 2019] aims at fooling GNNs by removing edges between nodes from the same class and inserting edges between nodes from the different classes.

We first poison the graph structure with these two attack methods and then train each model on the poisoned graphs and evaluate the anomaly detection results. We reserve 40% nodes for training models and report the mean AUC of ten independent runs on the test set for each model.

Against Random Attack. In this experiment, we evaluate how SparseGAD behaves under different ratios of random structure noises from 0% to 100% and report the results in Figure 3. Figure 3 shows that the performance of GAT and GraphSage drops significantly with increasing ratios of the random attack, and the performance of AMNET and BWGNN decline noticeably when the random attack to some extent. We discover that SparseGAD successfully defends against the random attack and consistently outperforms baselines in most cases.

Against DICE Attack. Since heterophilic links inherently exist in graphs of anomaly detection, we study how SparseGAD performs under different ratios of heterophily links. In practice, we select the anomalies in the test set as target nodes to attack, and the perturbation number of each node is calculated as max(10, degree) × ratio. We vary the ratio of perturbations on every target node with a step size of 20% to remove the existing links and add an equal number of heterophilic links. AUC values of SparseGAD and baselines on target nodes are reported in Figure 4. We discover that when the perturbation ratio increases, GAT and GraphSage perform worse than other models, whereas our SparseGAD is better than baselines on the attacked target nodes for the most part, demonstrating that SparseGAD can resist DICE attack.

5.4 Ablation Study

To validate the effectiveness of SparseGAD framework, we also investigate the anomaly detection performance of SparseGAD with Graph Convolution Network as the backbone, i.e., SparseGAD (GCN) and compare it with other GSL works. As shown in Table 2, we discover that SparseGAD (GCN) outperforms other GSL approaches in most case, which illustrates the superiority and extensibility of our framework in the GAD task. Besides, to better understand how homey adjacency matrix H and sparsification module help SparseGAD detect anomalies, we conduct ablation studies and compare SparseGAD with other two variants, i.e., SparseGAD-h and SparseGAD-s. As for SparseGAD-h, we only consider the informativeness of neighbors to ego nodes without heterophily via sigmoid activation instead of cosine similarity. As shown in Table 2, we find that SparseGAD achieves coherent improvements in all datasets compared to SparseGAD-h, which suggests that heterophily-aware aggregation is vital in GAD. Besides, in SparseGAD-s, we directly use the raw graph structure without sparsification in the homey message passing. In Table 2, we discover that SparseGAD outperforms SparseGAD-s in most cases, which indicates that the structure noises exists in the graphs of anomaly detection, and selecting the task-relevant edges contributes to more reliable results.

5.5 Parameter Analysis

Before this, we illustrated the effectiveness and robustness of SparseGAD. In this subsection, we attempt to understand the sparsified graph and homey adjacency matrix H we learned.

Importance of Graph Sparsification. Based on the fact that anomalies tend to connect with plenty of benign entities, if the framework is able to learn a denoised graph structure, the influence of the attack edges shall be eliminated from the poisoned graph. Hence, we investigate the homey edge weight Huv of attack edges and raw edges in YelpChi under DICE attack with a 20% perturbation ratio. In Figure 5(a), Huv of attack edges are much smaller than raw edges in the graph and are mainly around 0. The sparsification module will remove most attack edges via threshold δ, which proves that SparseGAD is capable to mitigate the effect of attack edges and learn robust parameters of GNN.

Importance of HomeyAdjacencymatrix. As heterophilic and homophilic connections exist in GAD, if the framework can detect anomalies precisely, the relationships between different neighbors and ego nodes shall be recognized distinctly. Accordingly, we study whether Huv can distinguish the connection properties. In Figure 5(b), we visualize Huv distributions of raw edges across pairs of normal entities, pairs of anomalies, and intersections of anomalies and normal entities in YelpChi (40%). We observe that Huv among the intersections of anomalies and normal entities are much smaller and more diverse than the other connections between the same types of nodes, which proves that SparseGAD can distinguish the complex relationships of node pairs and thereby facilitate aggregating message from neighbors.

6 Conclusion and FutureWork

In this paper, we introduced SparseGAD, a neural sparsification framework for Graph-based Anomaly Detection. Under this framework, we can capture the heterophilic and homophilic reliance of nodes to sparsify graph structure and learn distinguishable node representations for anomalies collaboratively. Our experiments show that our framework outperforms the state-of-the-art baselines in most cases, especially when the structure of graphs is heavily perturbed.

Considering some applications [Wang et al., 2021] of anomaly detection in real-world graphs are accompanied by multiple types of nodes and edges, we would like to investigate how to sparsify graph structure to facilitate detecting anomalies on such heterogeneous graphs in our future works. Besides, some graph compression methods, e.g., [Yin et al., 2022] shed light on how to accelerate graph samplings with GPUs and reduce the graph size for the explosive growth of nodes in large-scale graphs of anomaly detection. We could like to further improve the detection speed with the aid of such techniques.