Source-linked AI summary
Graph Anomaly Detection via Multi-Scale Contrastive Learning Networks with Augmented View
Jingcan Duan, Siwei Wang, Pei Zhang, En Zhu, Jingtao Hu, Hu Jin, Yue Liu, Zhibin Dong
TL;DR
Graph anomaly detection needs to exploit subgraph comparisons in addition to node-subgraph and node-node contrasts. GRADATE adds subgraph-subgraph contrast between an original and edge-modified graph view within a multi-scale framework. Across six benchmark datasets, the authors report that GRADATE outperforms competing methods and that the edge-modification strategy is effective.
Problem
Existing GAD contrastive methods use node-subgraph and node-node contrasts but neglect subgraph-subgraph comparison information, despite subgraph embeddings supporting reliable node-neighborhood relationships.
Method
GRADATE uses original and edge-modified graph views, random-walk subgraphs, and joint node-subgraph, node-node, and subgraph-subgraph contrasts to compute node anomaly scores.
Results
GRADATE outperforms competitors across six benchmark datasets, with reported AUC gains of 2.54%, 0.62%, 3.64%, 0.45%, 5.31%, and 0.43% on EAT, WebKB, UAT, Cora, UAI2010 and Citation, respectively.
Takeaways & Limitations
The results support subgraph-subgraph contrast with augmented views as an effective strategy for graph anomaly detection.
Abstract
from arXiv · showhide
Graph anomaly detection (GAD) is a vital task in graph-based machine learning and has been widely applied in many real-world applications. The primary goal of GAD is to capture anomalous nodes from graph datasets, which evidently deviate from the majority of nodes. Recent methods have paid attention to various scales of contrastive strategies for GAD, i.e., node-subgraph and node-node contrasts. However, they neglect the subgraph-subgraph comparison information which the normal and abnormal subgraph pairs behave differently in terms of embeddings and structures in GAD, resulting in sub-optimal task performance. In this paper, we fulfill the above idea in the proposed multi-view multi-scale contrastive learning framework with subgraph-subgraph contrast for the first practice. To be specific, we regard the original input graph as the first view and generate the second view by graph augmentation with edge modifications. With the guidance of maximizing the similarity of the subgraph pairs, the proposed subgraph-subgraph contrast contributes to more robust subgraph embeddings despite of the structure variation. Moreover, the introduced subgraph-subgraph contrast cooperates well with the widely-adopted node-subgraph and node-node contrastive counterparts for mutual GAD performance promotions. Besides, we also conduct sufficient experiments to investigate the impact of different graph augmentation approaches on detection performance. The comprehensive experimental results well demonstrate the superiority of our method compared with the state-of-the-art approaches and the effectiveness of the multi-view subgraph pair contrastive strategy for the GAD task.
Introduction
Graph anomaly detection targets feature and structure anomalies in graph data, but prior contrastive methods underuse subgraph information. GRADATE addresses this gap with augmented views and multi-scale contrasts, and experiments report superior performance.
- Motivation: Graph anomaly detection identifies nodes that deviate from the majority through feature anomalies or structure anomalies.Feature anomalies differ from neighboring nodes in features, whereas structure anomalies involve dissimilar nodes that are closely connected.
- Research gap: Existing methods neglect subgraph information and do not directly optimize subgraph embeddings for graph anomaly detection.More representative subgraph embeddings can improve relationships computed between nodes and their neighborhoods.
- Proposed framework: GRADATE uses the original graph and an edge-modified graph as two views, sampling subgraphs by random walk and combining node-subgraph, node-node, and subgraph-subgraph contrasts.The framework combines anomalous information across multiple scales and views before calculating each node's anomaly score.
- Contribution: Subgraph-subgraph contrast is introduced to GAD to learn more representative subgraph embeddings and enhance node-subgraph contrast.The method defines this contrast between two views and jointly optimizes subgraph representations with node-subgraph contrast.
- Evaluation: Extensive experiments on six benchmark datasets support the effectiveness of edge modification-based subgraph-subgraph contrast and GRADATE's superiority over state-of-the-art methods.The reported evaluation compares GRADATE with competing approaches across six datasets.
Related Work
Related work spans shallow anomaly detection, graph neural networks, graph contrastive learning, and graph augmentation. These lines of work provide the foundations for GRADATE's multi-scale contrastive design.
- Graph anomaly detection: Early graph anomaly detection methods use node features or network structure but cannot continuously improve by mining deeper information.The paper contrasts these non-deep approaches with later neural-network methods that mine deep nonlinear information.
- Graph contrastive learning: Graph contrastive learning extracts supervisory information without expensive labels for downstream graph tasks.Existing approaches include node-graph mutual-information maximization and node-subgraph contrasts.
- Notation: Table 1 summarizes the notation used throughout the paper.The table is presented as the notation summary for the subsequent formulation and model description.
- Graph augmentation: Graph augmentation creates plausible graph variations to expand datasets and improve model generalization without expensive labels.Prior operations commonly modify graph nodes, edges, or node features, while some methods use random walks with restart.
Problem Definition
The paper formulates GAD on an undirected graph with node features and an adjacency matrix, learning a node-level anomaly scoring function. Higher scores indicate greater anomaly likelihood.
- Problem formulation: The input is an undirected graph G = (V, E) with N nodes, M edges, node features X ∈Rn×d, and adjacency matrix A ∈Rn×n.Aij = 1 denotes an edge between vi and vj, while Aij = 0 denotes no edge.
- Problem formulation: The model learns an anomaly scoring function f that estimates an anomaly score Si for each node.A larger Si means that node i is more likely to be anomalous.
Method
GRADATE has graph augmentation and graph contrastive network modules. It creates a second edge-modified view, samples subgraphs by random walk, and compares nodes with subgraphs across the views.
- Graph augmentation: The graph augmentation module treats the original graph as the first view and produces a second view through edge modification.This creates the paired graph views used by the contrastive network.
- Graph contrastive network: The graph contrastive network samples subgraphs by random walk and forms node-subgraph pairs in each view.These comparisons provide anomalous information from node and subgraph feature relationships.
Graph Augmentation
GRADATE creates a second graph view by modifying edges, then samples subgraphs with random walks for contrastive learning. The edge modification deletes and adds equal numbers of edges to encourage robust subgraph representations without destroying graph properties.
- Graph views: GRADATE treats the original graph as one view and creates a second view through edge modification.Subgraphs are then sampled by random walk in the resulting views.
- Subgraph sampling: Random-walk subgraphs provide the node and subgraph inputs to the graph contrastive network.The method uses neighborhood subgraphs to compare target nodes with local graph context.
- Edge Modification: Edge Modification randomly drops PM/2 edges from the adjacency matrix.The drop proportion P is fixed, and the deleted edges are selected uniformly at random.
- Edge Modification: The same number of edges, PM/2, is uniformly and randomly added to the adjacency matrix.Deletion and addition are performed together to perturb the graph while preserving its intended properties.
Graph Contrastive Network
The graph contrastive network combines node-subgraph, node-node, and subgraph-subgraph contrasts across two graph views. These contrasts produce anomaly scores by comparing positive and negative relationships and aggregating information across views and detection rounds.
- Contrastive design: The network uses node-subgraph, node-node, and subgraph-subgraph contrasts, with the first two defined within each view and strengthened through two-view information fusion.Subgraph-subgraph contrast directly optimizes subgraph embeddings and supports node-subgraph discrimination.
- Node-subgraph contrast: A target node is paired positively with its located subgraph and negatively with a random subgraph associated with another node.The target node is masked in the subgraph, whose features are mapped through GCN and averaged into a subgraph representation.
- Node-node contrast: Node-node contrast pairs a target node positively with the same node after MLP and negatively with another node.The target node features are masked, and a separate GCN obtains the subgraph representation used in this contrast.
- Subgraph-subgraph contrast: Subgraph-subgraph contrast pairs subgraphs containing the same target node across views positively and subgraphs containing another node negatively.This contrast is directly optimized jointly with node-subgraph contrast to learn representative subgraph embeddings for GAD.
- Joint optimization: The joint loss combines node-subgraph, node-node, and subgraph-subgraph losses as L = βL_NS + (1 − β)L_NN + γL_SS.β balances subgraph-level and node-level information, while γ controls the subgraph-subgraph contrast.
- Anomaly scoring: Normal nodes match positive pairs and differ from negative pairs, whereas anomalous nodes are dissimilar in both pair types.The method fuses anomaly information from two views and three contrasts, then averages multi-round results with their standard deviation.
Experiments
The experiments evaluate GRADATE on six benchmark datasets using injected feature and structure anomalies, with ROC and AUC-based comparisons against baseline methods.
- Study Scope: The study also examines the effectiveness of subgraph-subgraph contrast and edge modification for graph anomaly detection.These components are evaluated through experiments and ablation studies.
- Datasets and Evaluation: GRADATE is evaluated on six benchmark datasets with injected feature and structure anomalies.The datasets are Citation, Cora, WebKB, UAI2010, UAT, and EAT.
- Evaluation Metrics: Performance is assessed using ROC curves and AUC comparisons against eight baseline methods.Larger ROC under-curve areas indicate better anomaly detection performance.
Result and Analysis
GRADATE outperforms competing methods across all six datasets, with contrastive learning methods generally stronger than shallow baselines.
- Overall Results: GRADATE outperforms competitors on all six datasets, achieving AUC gains of 2.54%, 0.62%, 3.64%, 0.45%, 5.31%, and 0.43%.The gains correspond to EAT, WebKB, UAT, Cora, UAI2010, and Citation, respectively.
- Baseline Comparison: Most neural network-based methods outperform the shallow methods LOF and ANOMALOUS.The paper attributes this comparison to shallow methods' limitations with high-dimensional graph features.
- Contrastive Methods: Among deep methods, contrastive learning approaches perform better, with GRADATE achieving the best performance.The reported contrastive methods are CoLA, ANEMONE, SL-GAD, Sub-CR, and GRADATE.
Ablation Study
Ablation studies show that subgraph-subgraph contrast improves detection alongside node-subgraph contrast, while edge modification is the strongest tested augmentation.
- Various Scale Contrastive Strategy: Adding subgraph-subgraph contrast enhances detection performance by boosting node-subgraph contrast.The ablation compares NS, NS+SS, NS+NN, and NS+NN+SS configurations.
- Various Scale Contrastive Strategy: Using node-subgraph, node-node, and subgraph-subgraph contrasts together produces the best performance.The full NS+NN+SS configuration corresponds to GRADATE.
- Graph Augmentation Strategy: Edge Modification achieves the best performance among the four tested graph augmentations on all datasets.The compared approaches are Gaussian Noised Feature, Feature Mask, Graph Diffusion, and Edge Modification.
- Graph Augmentation Strategy: Feature perturbations may disrupt normal-node features, while Graph Diffusion is less compatible with subgraph-subgraph contrast because it targets global information.The paper links these properties to poorer comparison between nodes and their neighborhoods.
Sensitivity Analysis
Sensitivity analyses examine the balance parameters, trade-off parameter, and edge-modification proportion, identifying settings that maintain strong performance across benchmarks.
- Balance Parameters α and β: The balance parameters α and β improve detection performance on EAT and UAI2010, with similar behavior reported on other datasets.The selected α and β values vary across the six datasets.
- Trade-off Parameter γ: GRADATE tends to perform well when γ is set to 0.1 across all benchmarks.The analysis varies γ from 0.1 to 0.9.
- Perturbation Proportion P: Detection performance changes relatively little with perturbation proportion P on UAT, UAI2010, and Citation.The implementation fixes P = 0.2 on all datasets.
Conclusion
The paper proposes GRADATE, a multi-scale contrastive graph anomaly detection framework with an augmented view, and evaluates it across six benchmark datasets. Its subgraph-subgraph contrast and augmentation analysis support improved graph anomaly detection performance.
- GRADATE introduces a graph anomaly detection framework using multi-scale contrastive learning with an augmented view.
- The framework adds subgraph-subgraph contrast to GAD and investigates different graph augmentation technologies.
- Extensive experiments on six benchmark datasets show that GRADATE outperforms competing methods.