PaperlayerView exact revision on arXiv

Source-linked AI summary

Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning

Yixin Liu, Zhao Li, Shirui Pan, Chen Gong, Chuan Zhou, George Karypis

arXiv:2103.00113v2cs.LG

TL;DR

Attributed-network anomaly detection is challenged by autoencoder-based methods that underuse network information, lack anomaly-specific objectives, and do not scale well. CoLA uses node–local-subgraph contrastive learning with a GNN and multi-round score estimation, and it outperforms state-of-the-art baselines on all seven benchmark datasets.

  • Problem

    Existing graph-autoencoder approaches do not fully exploit attributed-network information, directly target anomaly detection, or scale to large networks.

  • Method

    CoLA samples node–local-subgraph instance pairs, trains a GNN-based contrastive model on their agreement, and estimates node abnormality from multi-round predicted scores.

  • Results

    6.44% AUC average improvement over the best baseline results across seven datasets, with CoLA achieving the best anomaly-detection performance on all seven.

  • Takeaways & Limitations

    CoLA provides an anomaly-detection framework that uses local node–substructure relationships and supports large-scale networks through lightweight instance pairs.

Abstract

from arXiv · show

Anomaly detection on attributed networks attracts considerable research interests due to wide applications of attributed networks in modeling a wide range of complex systems. Recently, the deep learning-based anomaly detection methods have shown promising results over shallow approaches, especially on networks with high-dimensional attributes and complex structures. However, existing approaches, which employ graph autoencoder as their backbone, do not fully exploit the rich information of the network, resulting in suboptimal performance. Furthermore, these methods do not directly target anomaly detection in their learning objective and fail to scale to large networks due to the full graph training mechanism. To overcome these limitations, in this paper, we present a novel contrastive self-supervised learning framework for anomaly detection on attributed networks. Our framework fully exploits the local information from network data by sampling a novel type of contrastive instance pair, which can capture the relationship between each node and its neighboring substructure in an unsupervised way. Meanwhile, a well-designed graph neural network-based contrastive learning model is proposed to learn informative embedding from high-dimensional attributes and local structure and measure the agreement of each instance pairs with its outputted scores. The multi-round predicted scores by the contrastive learning model are further used to evaluate the abnormality of each node with statistical estimation. In this way, the learning model is trained by a specific anomaly detection-aware target. Furthermore, since the input of the graph neural network module is batches of instance pairs instead of the full network, our framework can adapt to large networks flexibly. Experimental results show that our proposed framework outperforms the state-of-the-art baseline methods on all seven benchmark datasets.

I. INTRODUCTION

Attributed-network anomaly detection must handle diverse mismatches between node attributes and local structure, while existing methods face representation, objective, and scalability limitations. CoLA addresses these issues with node–local-subgraph contrastive learning and lightweight instance-pair processing.

  • Motivation: Attributed networks contain structural anomalies with abnormal links and contextual anomalies with corrupted attributes despite natural neighboring structure.These anomaly types reflect different mismatches between attributes and network structure.
  • Limitations of Existing Methods: Existing deep methods use graph autoencoders that reconstruct data rather than directly optimizing anomaly detection.Their reconstruction mechanism can yield suboptimal anomaly-detection performance and may not fully exploit attributed-graph information.
  • Limitations of Existing Methods: Autoencoder-based graph methods also require full-graph operations, creating a bottleneck for anomaly detection on large networks.The introduction identifies full-graph processing as a scalability challenge.
  • Proposed Direction: Contrastive learning compares node instances with neighbors, enabling it to capture normal matching patterns and anomalous mismatches without manual labels.Its pairwise agreement scores are directly related to node abnormality and can support anomaly-aware training.
  • CoLA: CoLA samples target-node versus local-subgraph pairs and trains a GNN-based contrastive model to learn attributes, local structure, and abnormality scores.The framework splits the network into lightweight instance pairs instead of applying graph convolution to the full network.
  • Evaluation: CoLA is evaluated through experiments on multiple datasets, with the paper describing extensive comparisons against baseline methods.The introduction states that experiments demonstrate the framework’s effectiveness and comparative performance.

B. Anomaly Detection on Attributed Networks

Attributed-network anomaly detection combines node attributes and graph structure, but existing shallow and autoencoder-based methods have limitations in modeling, objective alignment, and scalability. CoLA frames anomaly detection as ranking nodes by scores in an unsupervised setting and uses contrastive learning to address these gaps.

  • CoLA distinguishes anomaly detection from representation learning by using the full contrastive model to compute anomaly scores and node-local subgraph pairs to capture local abnormality.
  • The task is unsupervised node ranking: an anomaly score represents each node’s abnormality, and nodes are detected according to their ranked positions.

IV. METHODOLOGY

CoLA samples target-node/local-subgraph pairs, trains a GNN-based contrastive model on them, and estimates node abnormality from predicted pair scores. Its sampling emphasizes local consistency and hides initial nodes to prevent trivial identification.

  • CoLA has three components: instance pair sampling, a GNN-based contrastive learning model, and anomaly score computation.
  • Contrastive instance pair sampling: The proposed contrastive instance pair consists of a target node and a local subgraph sampled from an initial node.
  • Contrastive instance pair sampling: Positive pairs sample neighboring nodes around the target, while negative pairs use an initial node randomly selected from other network nodes.
  • Contrastive instance pair sampling: The design focuses on node-neighbor inconsistency because anomalies are described as mismatches with nearby nodes rather than primarily with global information.
  • Sampling process: Local subgraphs are sampled with random walk with restart for usability and efficiency, while other graph sampling algorithms remain compatible with the framework.
  • Sampling process: Anonymization sets initial-node attribute vectors to zero, hiding target-node information before the target and subgraph are combined into positive or negative sample pools.
  • GNN-based contrastive learning model: The contrastive model contains GNN, readout, and discriminator modules, and its outputs support statistical estimation of a target node’s anomaly score.

1) GNN module:

The GNN module aggregates local-subgraph information and maps high-dimensional attributes into low-dimensional node embeddings. The target node uses a structure-free transformation sharing GCN weights with the subgraph encoder.

  • The GNN aggregates information among local-subgraph nodes and transfers high-dimensional attributes into a low-dimensional embedding space.
  • With L GNN layers, the input representation is the attribute matrix X_i and the output representation is the node-embedding matrix E_i.
  • CoLA can use mainstream GNNs including GCN, GAT, and GIN, while the implementation adopts GCN for efficiency.
  • The GCN layer uses a self-looped adjacency matrix, degree normalization, learnable weight matrices, and an activation function such as ReLU.
  • Because a single target node has no structure information, it is mapped into the shared embedding space using the GCN weight matrices and activation function as a DNN.

2) Readout module:

The readout and discriminator modules convert local-subgraph and target-node embeddings into a contrastive agreement score. CoLA trains these scores against pair labels with binary cross-entropy.

  • Readout module: The readout module converts local-subgraph node embeddings E_i into a local-subgraph embedding vector e_lg_i.
  • Readout module: CoLA uses average pooling over the local-subgraph node embeddings as its readout function.
  • Discriminator module: The discriminator contrasts local-subgraph and target-node embeddings and outputs a predicted agreement score using a bilinear scoring function.
  • Discriminator module: The discriminator score uses W^(d) and the logistic sigmoid function σ(·).
  • Objective function: The integrated model acts as a binary classifier for contrastive instance-pair labels.
  • Objective function: CoLA minimizes binary cross-entropy so predicted scores s_i approach ground-truth pair labels y_i.
  • Objective function: Vanilla BCE is paired with balanced positive and negative sampling, while alternative objectives remain possible for more complex sampling strategies.

C. Anomaly Score Computation

CoLA estimates each node’s abnormality from repeated positive and negative node–substructure comparisons, reducing sensitivity to one-shot local sampling. It averages score differences across rounds, while acknowledging that richer score statistics may offer future improvements.

  • Sampling limitation: A sampled local subgraph may incompletely represent a node’s neighborhood, causing one-shot anomaly estimates to miss abnormal links among mostly normal neighbors.This limitation particularly affects structural anomalies whose abnormal connections are sparse relative to their normal neighbors.
  • Multi-round estimation: CoLA samples R positive and R negative instance pairs per node, feeds them to the contrastive model, and computes predicted agreement scores for anomaly estimation.The resulting score differences are processed across multiple sampling rounds.
  • Anomaly score: For each node, the anomaly score is defined as the difference between the negative-pair and positive-pair scores.The score mapping function f(·) is the ultimate target of the anomaly detection framework.
  • Statistical aggregation: Averaging multi-round score differences estimates the normality difference between neighboring and remote substructures.A larger R is expected to improve estimation accuracy, and R is treated as a framework hyper-parameter.
  • Future direction: Further mining of score variance, extrema, or distributions is identified as future work because different anomaly types may produce different score-distribution characteristics.The paper reports that averaging is the most effective practical solution among the considered aggregation choices.

D. CoLA: An Anomaly Detection Framework

CoLA separates training from inference: it trains a contrastive model on sampled instance pairs, then computes anomaly scores for nodes. Mini-batch pair processing makes both stages independent of full-network training.

  • Pipeline: The CoLA pipeline has training and inference phases, with unsupervised contrastive training followed by anomaly-score computation for each node.The framework comprises sampled instance pairs, a GNN-based contrastive model, and anomaly-score computation.
  • Training phase: During each training epoch, nodes are split into mini-batches, positive and negative pairs are sampled, predicted scores are calculated, and BCE loss updates the model.Backpropagation optimizes the contrastive learning model after loss computation.
  • Scalability: CoLA processes mini-batches of instance pairs independently, so its space complexity is uncorrelated with the number of nodes and can support large-scale networks.Anomaly-score computation is also independent across nodes.

E. Complexity Analysis

The complexity analysis decomposes CoLA into sampling, inference, and GNN computation, yielding an overall time complexity that scales with network size, sampling rounds, and mean degree.

  • Sampling: Each random-walk-with-restart subgraph sampling operation costs O(cδ), where δ is the network’s mean degree.The sampling cost is analyzed as one of the framework’s three main components.
  • Inference: Inference over all nodes and R sampling rounds costs O(cnδR).This term reflects repeated subgraph sampling for every node.
  • Overall complexity: The overall time complexity of CoLA is O(cnR(c + δ)).The expression combines sampling and GNN-based contrastive-learning costs.

V. EXPERIMENTS

Experiments evaluate CoLA on seven attributed-network benchmarks spanning social and citation domains, using injected structural and contextual anomalies. CoLA is compared with five anomaly-detection or graph-contrastive baselines.

  • Datasets: The evaluation uses seven benchmark datasets: BlogCatalog and Flickr, plus Cora, Citeseer, Pubmed, ACM, and ogbn-arxiv.The first two are social networks, while the remaining five are citation networks.
  • Datasets: Social-network nodes represent users linked by following relationships, with blog or photo text serving as node attributes.The datasets come from BlogCatalog and Flickr.
  • Datasets: Citation-network nodes represent papers connected by citations, using bag-of-word attributes or 128-dimensional ogbn-arxiv vectors.The first four citation datasets use bag-of-word representations; ogbn-arxiv uses averaged title-and-abstract word embeddings.
  • Anomaly construction: Structural anomalies are injected as small cliques among originally unrelated nodes, while contextual anomalies replace a target node’s attributes with those of a distant candidate.Structural anomalies perturb topology; contextual anomalies perturb attributes.
  • Baselines: CoLA is compared with AMEN, Radar, ANOMALOUS, DOMINANT, and DGI using the experimental setup’s selected baselines and evaluation metrics.The baselines span shallow anomaly detection, deep reconstruction, and graph contrastive representation learning.

2) Evaluation metrics:

CoLA achieves the best anomaly-detection performance across seven benchmark datasets, with advantages over shallow, contrastive, and autoencoder-based baselines. It also scales to ogbn-arxiv where most baselines fail because of memory requirements.

  • Performance comparison: 6.44% average AUC improvement over the best baseline is achieved by CoLA across the seven benchmark datasets.The authors attribute this to capturing node–local-substructure relationships and extracting discriminative scores from contextual and structural information.
  • Performance comparison: CoLA achieves the best anomaly-detection performance on all seven benchmark datasets.The comparison uses ROC curves and AUC values, where larger area under the curve indicates better performance.
  • Baseline comparison: AMEN, Radar, and ANOMALOUS perform less satisfactorily than deep learning methods on high-dimensional attributes and sparse, complex network structures.The authors attribute this limitation to the shallow mechanisms used by these methods.
  • Baseline comparison: DGI is not competitive because its full-graph-versus-node pairs do not capture local-substructure abnormality, unlike CoLA’s target-node-versus-local-subgraph pairs.The authors characterize CoLA’s local pairing as sensitive to local abnormal information.
  • Baseline comparison: CoLA outperforms DOMINANT, especially on the five citation networks, by constructing instance pairs and optimizing an anomaly-detection-related objective.This contrasts with simply reconstructing the original data through an autoencoder backbone.
  • Scalability: CoLA runs successfully on ogbn-arxiv, whereas Radar, ANOMALOUS, DOMINANT, and DGI fail to produce results because of large memory requirements.The framework’s space complexity is independent of the number of nodes n.

D. Parameter Study

The parameter study examines sampling rounds, subgraph size, embedding dimension, and readout functions using AUC-based evaluations. Performance generally improves with larger sampling rounds and embeddings, while subgraph size and readout choices involve trade-offs.

  • Sampling rounds: AUC improves substantially as sampling rounds increase from one shot, but gains become small beyond R=256.The authors set R=256 in subsequent experiments to balance performance and efficiency.
  • Subgraph size: AUC is relatively low at subgraph size c=2 because the sampled subgraph contains only the target node and one neighbor.The authors associate the reduced performance with insufficient neighboring structural information.
  • Embedding dimension: AUC steadily increases as embedding dimension grows from 1 to 32 neurons, while further increases provide smaller gains.For most datasets, the authors observe that 64-dimensional latent embeddings provide effective performance.
  • Readout functions: Min Pooling performs worst among the tested readout functions, while Max Pooling is competitive on most datasets.The authors associate Min Pooling’s lower performance with information loss from using minimum values.
  • Readout functions: Weighted Average Pooling requires heavier computation and performs close to Max Pooling, suggesting similarity-based weighting can be suboptimal.These readout comparisons were conducted on six small-scale datasets.

2) Effect of the source of score computation:

CoLA’s anomaly score combines predicted scores from both positive and negative instances, and considering both sources benefits detection performance. The broader framework uses multi-round score estimation, with mean values described as the most robust choice across datasets.

  • 2) Effect of the source of score computation:: CoLA(+) uses only positive-instance scores, CoLA(-) only negative-instance scores, while CoLA(+/-) uses both sources for anomaly scoring.Table VI compares these three score-source variants using AUC values.
  • 2) Effect of the source of score computation:: Considering both positive and negative scores is always beneficial to anomaly detection performance.The relative contribution of positive and negative instances differs across datasets, but the full version performs better overall.
  • 3) Effect of estimation mode of anomaly score:: Maximum/minimum estimation performs worse than mean estimation, and combining extrema with the mean remains worse than using the mean alone.These comparisons concern multi-round predicted scores used as anomaly scores.
  • 3) Effect of estimation mode of anomaly score:: Adding standard deviation can improve performance, but its correlation with abnormality differs between BlogCatalog/Flickr and citation networks.The reported correlation is negative for BlogCatalog and Flickr and positive for citation networks.
  • 3) Effect of estimation mode of anomaly score:: Mean-value estimation is less effective than some alternatives but is the most robust choice across all datasets.The authors report relatively good detection performance with CoLA(mean) for every dataset.
Loading 2103.00113v2…