ResGCN: Attention-based Deep Residual Modeling for Anomaly Detection on Attributed Networks

1 Introduction

• Anomalies in attributed networks can differ from the majority in both structure and attributes, such as a node connected to all others with distinctly different attributes..Source: §1 · p. 2
• Existing approaches struggle to capture sparsity and nonlinearity, learn residuals from reconstruction errors, and risk over-smoothing anomalous nodes until they resemble the majority.The cited discussion links shallow non-negative matrix factorization to limited nonlinearity modeling and smoothing to reduced anomaly distinguishability.Source: §1 · p. 3
• ResGCN uses GCN to capture network sparsity and nonlinearity, learns residuals directly from the input, and uses residual-based attention to reduce anomalous-node information propagation.The paper also proposes ranking anomalies by residual information.Source: §1 · p. 3
• Experiments on real-world attributed networks demonstrate ResGCN's effectiveness across different evaluation metrics.Source: §1 · p. 3

2 Problem Definition

• An attributed network consists of nodes, edges, and a node-attribute matrix whose rows give the attributes of individual nodes.Source: §2 · p. 4
• The network's topology is represented by an adjacency matrix and its attributes by an attribute matrix; this study focuses on undirected networks.Source: §2 · p. 4
• Anomaly detection seeks nodes that are rare and differ singularly from the majority reference nodes in the input network.Source: §2 · pp. 4–5

3.1 Graph Convolutional Networks

• GCN learns node representations by passing and aggregating messages between neighboring nodes, using the input attributes at the first layer.The formulation adds self-connections to the input adjacency matrix.Source: §3.1 · pp. 5–6

3.2 ResGCN

• The method uses GCN layers to learn node representations and includes residual modeling, representation learning, network reconstruction, and anomaly ranking.Its GCN input includes self-connections, and the original GCN’s supervised cross-entropy loss is unsuitable for this unsupervised anomaly-detection setting.Source: §3.2 · p. 6, §3.1 · p. 6

3.2.1 Residual Modeling

• A deep neural network learns residual information directly from the input, addressing limits of linear residual models that derive residuals from reconstruction errors.The authors motivate direct learning because residual patterns vary across datasets.Source: §3.2.1 · pp. 6–7

3.2.2 Representation Learning

• Residual-based attention assigns weights to neighbors during GCN aggregation to limit information propagation from anomalous nodes.The attention weights are learned from the residual matrix and applied to the aggregated neighbor representation.Source: §3.2.2 · p. 7, §3.2.1 · p. 7

3.2.3 Network Reconstruction

• Attribute reconstruction uses a multilayer perceptron decoder rather than a graph-convolution decoder, and incorporates the learned residual into its reconstruction error.The authors choose the perceptron because graph convolution mixes node features with those of nearby neighbors.Source: §3.2.3 · p. 9
• ResGCN jointly reconstructs network structure and attributes, then ranks nodes by residual magnitude rather than reconstruction error.The objective combines structure and attribute reconstruction errors; the anomaly score is the L2 norm of a node’s residual row.Source: §3.2.3 · p. 9

3.3 Complexity Analysis

• The overall computational complexity is O(edF + n^2), including GCN computation and pairwise network reconstruction.Here, e is the number of nonzero adjacency entries and F is the sum of feature maps across layers.Source: §3.3 · p. 10

4.1 Datasets

• Amazon and Enron use provided anomaly labels, while BlogCatalog, Flickr, and ACM use injected structural and attribute anomalies.Structural anomalies are generated as small cliques; attribute anomalies are created by replacing selected nodes' attributes.Source: §4.1 · pp. 10–11

4.2 Evaluation Metrics

• Evaluation uses ROC-AUC for threshold-based detection and Precision@K and Recall@K to assess anomalies found in ranked lists.ROC-AUC measures the true-positive/false-positive trade-off; the ranking metrics measure the fraction of true anomalies found in the top K and overall ground-truth set, respectively.Source: §4.2 · p. 12

4.3 Baselines

• Baselines include attribute-based LOF, attribute-and-structure AMEN, residual methods Radar and ANOMALOUS, and GCN-based DOMINANT.The experiments compare ResGCN with several anomaly-detection approaches.Source: §4.3 · pp. 12–13

4.4 Experimental Results

• ResGCN outperforms baselines on Amazon and on the three unlabeled networks except for Precision@50 on Flickr, and achieves comparable results on Enron.Deep and residual-analysis methods also outperform traditional approaches in the reported comparisons.Source: §4.4 · pp. 13–14

4.5 Ranking Strategy Analysis

• Ranking residual information outperforms the alternative ranking strategies on the tested data and metrics except on Enron; combining structure and attribute reconstruction errors also improves detection.Attribute reconstruction-error ranking performs better than structure reconstruction-error ranking.Source: §4.5 · p. 16

4.6 Parameter Analysis

• The best reported trade-off is α = 0.8 on Amazon and BlogCatalog, while the best residual settings are λ = 0.1 on Amazon and λ = 0.2 on BlogCatalog.The influence of α differs by network; performance improves for Amazon when α ≥ 0.1, and larger α performs better on BlogCatalog.Source: §4.6 · p. 17

• Attributed-network anomaly detection includes community analysis, subspace selection, residual analysis, and deep-learning approaches.Examples include CODA (Gao et al., 2010), Radar (Li et al., 2017), ANOMALOUS (Peng et al., 2018), and DOMINANT (Ding et al., 2019a).Source: §5 · p. 18
• Anomaly-aware embedding work includes semi-supervised SEANO (Liang et al., 2018), self-paced SPARC (Zhou et al., 2018), and joint structure-attribute embedding methods ONE (Bandyopadhyay et al., 2019), DONE, and AdONE (Bandyopadhyay et al., 2020).Other approaches map nodes to Gaussian distributions, using representation variance to capture uncertainty (Zhu et al., 2018; Pei et al., 2020).Source: §5 · pp. 18–19
• GCNs learn node representations by passing and aggregating messages between neighboring nodes (Kipf and Welling, 2016a), with variants adding attention (Velickovic et al., 2017), residual and jumping connections (Xu et al., 2018), or disentanglement (Ma et al., 2019).Source: §5 · p. 19

6 Conclusions

• ResGCN demonstrates effectiveness in detecting anomalies compared with state-of-the-art methods.Source: §6 · p. 19
• Its GCN layers capture network sparsity and nonlinearity, while residual-based attention prevents anomalous information from propagating during message passing.Source: §6 · p. 19
• ResGCN detects anomalies by ranking residual information.Source: §6 · p. 19
• The authors identify extending ResGCN to dynamic and streaming networks as future work.Source: §6 · p. 19