PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Graph-level Anomaly Detection by Glocal Knowledge Distillation

Rongrong Ma, Guansong Pang, Ling Chen, Anton van den Hengel

arXiv:2112.10063v1cs.CVcs.AIcs.LG

TL;DR

Graph-level anomaly detection needs representations that capture both local and global graph irregularities, but existing approaches have limitations in representing these patterns. GLocalKD jointly distills graph and node representations by training a GNN predictor to match a randomly initialized GNN, and the authors report that it outperforms seven state-of-the-art methods across 16 real-world datasets.

  • Problem

    Graph-level anomaly detection needs expressive representations of local and global normal patterns to identify both node-neighborhood and holistic graph anomalies.

    Source: §1 · p. 1

  • Method

    GLocalKD jointly distills graph and node representations by training a predictor GNN to match representations from a fixed, randomly initialized GNN.

    Source: §1 · p. 2

  • Results

    Across 16 real-world datasets, GLocalKD significantly outperforms seven state-of-the-art competing methods.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Reported robustness to anomaly contamination indicates applicability with either anomaly-contaminated unlabeled training data or exclusively normal training data.

    Source: §1 · p. 2

    The formulation covers plain graphs and attributed graphs whose nodes have feature vectors.

    Source: §3.1 · p. 3

Abstract

from arXiv · show

Graph-level anomaly detection (GAD) describes the problem of detecting graphs that are abnormal in their structure and/or the features of their nodes, as compared to other graphs. One of the challenges in GAD is to devise graph representations that enable the detection of both locally- and globally-anomalous graphs, i.e., graphs that are abnormal in their fine-grained (node-level) or holistic (graph-level) properties, respectively. To tackle this challenge we introduce a novel deep anomaly detection approach for GAD that learns rich global and local normal pattern information by joint random distillation of graph and node representations. The random distillation is achieved by training one GNN to predict another GNN with randomly initialized network weights. Extensive experiments on 16 real-world graph datasets from diverse domains show that our model significantly outperforms seven state-of-the-art models. Code and datasets are available at https://git.io/GLocalKD.

1 INTRODUCTION

Graph-level anomaly detection must capture both local node-neighborhood irregularities and holistic graph-level differences, a challenge in a comparatively little-explored setting. GLocalKD jointly distills graph and node representations, and experiments report strong performance across real-world datasets.

1 INTRODUCTION

  • GAD seeks anomalies among collections of graphs, where expressive representations must capture both local node-neighborhood and holistic graph-level normal patterns.The paper notes that GAD has received comparatively little attention; related work on time-evolving graphs addresses anomalous changes in a single graph instead.Source: §1 · p. 1
  • Reconstruction-based detectors face the challenge of faithfully reconstructing or generating graphs, while Deep SVDD focuses on globally anomalous graphs and is restricted by its one-class hypersphere assumption.These limitations motivate an approach that can detect both local and global anomalies without relying on graph reconstruction.Source: §1 · p. 2
  • GLocalKD learns global and local normal patterns by jointly distilling graph and node representations.A predictor GNN learns to match representations from a second GNN with fixed, randomly initialized weights; prediction error serves as an anomaly score for irregular graphs.Source: §1 · p. 2
  • Across 16 real-world datasets, GLocalKD significantly outperforms seven state-of-the-art competing methods.It is also reported as more sample-efficient than other deep detectors, with 95% fewer training samples still yielding accuracy that outperforms competing methods by a large margin.Source: §1 · p. 2
  • The paper reports that GLocalKD remains stable across anomaly-contamination rates and representation dimensionalities, and is applicable to unsupervised and semi-supervised settings.The stated settings use anomaly-contaminated unlabeled training data or exclusively normal training data, respectively.Source: §1 · p. 2

2 RELATED WORK

Prior graph-level anomaly detection work often targets time-evolving graphs, uses representations learned separately from anomaly detectors, or relies on graph reconstruction. The paper positions GLocalKD's random-distillation approach as a way to learn jointly globally- and locally-sensitive graph normality.

2.1 Graph-level Anomaly Detection

  • Time-evolving graph methods identify anomalous changes in sequences of similar graphs, while static graph-level anomaly detection in diverse graph collections has received less attention.The paper distinguishes this setting from methods for anomalous nodes or edges in a single large graph [16] [41].Source: §2.1 · pp. 2–3
  • Static-graph approaches apply anomaly measures to representations from graph kernels or embedding methods, but learn those representations independently of the detector [25] [50].Graph-level pattern extraction is another direction, though its performance is limited when patterns differ across domains or application scenarios [25].Source: §2.1 · p. 3
  • Deep anomaly-detection methods often depend on reconstruction or generation, which is challenging for graphs; Deep SVDD with GNN representations targets high-level anomalies and is restricted by its measure [50].The section also notes limited prior deep-learning work specifically on graph-level anomaly detection.Source: §2.1 · p. 3

2.2 Knowledge Distillation

  • Conventional knowledge distillation trains a student to imitate a pretrained teacher, but the paper notes that general-purpose pretrained teachers are unavailable for graph-level data and graph databases vary across domains [12].GLocalKD instead draws on random knowledge distillation and applies it to jointly learn globally- and locally-sensitive graph normality.Source: §2.2 · p. 3

3 FRAMEWORK

The framework targets both locally anomalous graphs, which contain nodes that deviate from similar nodes across the graph set, and globally anomalous graphs whose holistic properties differ. It trains a predictor to match graph- and node-level representations from a fixed random target network, then scores deviations at both levels.

3.1 Problem Statement

  • The problem is to rank graphs by abnormality across a set of normal graphs, covering both anomalous nodes and graphs with nonconforming holistic properties.Local graph anomalies are distinct from anomalous-node detection within one large graph: they are detected across a set of separate graphs.Source: §3.1 · p. 3

3.2 The Proposed Framework

  • The end-to-end framework combines two GNNs with joint random distillation of graph- and node-level representations to detect both types of anomalous graphs.The target network is randomly initialized and fixed; the predictor has the same architecture and learns to match its outputs.Source: §3.2 · p. 3, §3.2.1 · p. 4

3.2.1 Overview of the Framework.

  • Training fixes the randomly initialized target network and minimizes a loss over predictor outputs at both graph and node levels.The overall loss balances graph-level and node-level distillation losses; at evaluation, the predictor’s learned parameters are used to score a graph.Source: §3.2.1 · p. 4

3.2.2 Key Intuition.

  • Frequent patterns in random graph and node representation spaces are learned with smaller prediction errors, so test graphs that depart from either level’s learned regularity receive larger anomaly scores.Graphs conforming to training regularities receive smaller scores.Source: §3.2.2 · p. 4

4 JOINT RANDOM DISTILLATION OF GRAPH AND NODE REPRESENTATIONS

GLocalKD distills graph- and node-level representations from a fixed random target into a predictor, using their prediction errors to score graphs. The paper’s theoretical analysis relates larger errors to graphs drawn from distributions different from the training graphs.

4.1 Graph Neural Network Architecture

  • The method uses GCNs for node and graph representations, with a fixed randomly initialized target and a predictor with the same architecture whose weights are learned.The target yields random-space representations; the predictor is trained to match them. The paper selects GCN for expressive graph features and computational efficiency.Source: §4 · p. 4, §4.1.1 · p. 4, §4.1.2 · p. 5

4.1.1 Random Target Network.

  • The target GCN maps node features and graph structure to node representations, then max-pooling aggregates node representations into a graph-level representation.For plain graphs, node degree supplies the input node features.Source: §4.1.1 · pp. 4–5

4.2 Glocal Regularity Distillation

  • Glocal regularity distillation minimizes graph-level and node-level representation distances jointly, treating the two anomaly scales as equally important.The total loss is the sum of graph-level and node-level losses.Source: §4.2 · p. 5

4.3 Anomaly Detection of Using GLocalKD

  • A test graph’s anomaly score uses prediction errors from both its graph-level and node-level representations.The paper states that the two anomaly scales are treated equally in scoring.Source: §4.3 · p. 5

4.4 Theoretical Analysis of GLocalKD

  • Under the paper’s Bayesian analysis, distilling a randomly drawn function from the prior makes prediction error an estimate of ensemble predictive variance when the ensemble is unbiased.The analysis connects this perspective to smaller errors for patterns represented by many training samples and larger errors for graphs from different distributions.Source: §4.4 · pp. 5–6
  • Graphs dissimilar to most training data are described as having larger predictive variance and prediction errors, allowing joint distillation errors to distinguish locally and globally anomalous graphs from normal ones.For graphs with patterns similar to many training graphs, the errors are small because sufficient examples train the predictor.Source: §4.4 · pp. 5–6

5 EXPERIMENTS AND RESULTS

Across 16 real-world datasets, GLocalKD is compared with seven competing methods and tested for sample efficiency, contamination robustness, sensitivity, and the roles of graph- and node-level distillation.

5.1 Datasets

  • The experiments use 16 public datasets, seven competing methods, a shared three-layer GCN architecture for GLocalKD and OCGCN, and AUC evaluation across five runs or folds.The datasets include attributed and plain graphs; four contain real anomalies and 12 use minority classes as anomalies.Source: §5.1 · p. 6, §5.2 · p. 6, §5.3 · pp. 6–7

5.4 Comparison to State-of-the-art Methods

  • GLocalKD is best on 7 datasets, with reported gains of 1%–12% on many datasets, and significantly outperforms iForest-based methods and OCGCN across the 16-dataset test.The reported significance against LESINN-based methods ranges from 85% to 95%.Source: §5.4 · p. 7
  • GLocalKD and OCGCN have similar time complexity; both run faster online than iForest/LESINN methods but are generally more costly than WL- and PK-based methods.GLocalKD and OCGCN typically require multiple iterations to perform well.Source: §5.4 · p. 7

5.5.2 Findings.

  • With 95% less training data, GLocalKD retains similarly good performance across nearly all six attributed datasets and can outperform OCGCN by large margins on ENZYMES and AIDS.Figure 4 compares AUC performance for GLocalKD and OCGCN across training-data amounts.Source: Figure 4 · p. 7, §5.5.2 · p. 7

5.6.2 Findings.

  • On the six attributed datasets, GLocalKD is barely affected by training contamination up to 16%, while OCGCN’s performance drops substantially on ENZYMES and AIDS as contamination increases.The authors attribute the difference to random distillation learning patterns in the training data versus SVDD’s sensitivity to contamination.Source: §5.6.1 · p. 7, §5.6.2 · p. 7, Figure 5 · p. 8

5.7 Sensitivity Test

  • GLocalKD performs stably across representation dimensions on most datasets; three GCN layers are recommended because performance flattens from three to five layers while computational cost increases.The generally recommended output dimension is 256.Source: §5.7.1 · p. 8, §5.7.2 · p. 8

5.8 Ablation Study

  • The ablation variants retain either graph-level or node-level random distillation, while the full model uses both components.GLocalKD w/o L_node uses graph representations only; GLocalKD w/o L_graph uses node representations only.Source: §5.8.1 · p. 8

5.8.2 Findings.

  • Joint graph- and node-level distillation trades off well across datasets; node-level effects dominate on AIDS, DHFR, DD, MMP, p53, PPAR-gamma, and hERG, while graph-level effects dominate on ENZYMES, IMDB, and HSE.The results indicate that both locally- and globally-anomalous graphs can occur in the datasets.Source: Table 2 · p. 8, §5.8.2 · p. 8

6 CONCLUSION

The paper presents GLocalKD for detecting both locally and globally anomalous graphs. Experiments report strong AUC, sample efficiency, and performance under anomaly-contaminated training data.

6 CONCLUSION

  • GLocalKD is designed to detect both locally- and globally-anomalous graphs in graph datasets.The conclusion describes it as the first model designed for both anomaly types.Source: §6 · p. 8
  • Experiments show significantly better AUC and greater sample efficiency than the paper’s advanced counterparts.The conclusion does not specify numerical results in this passage.Source: §6 · p. 8
  • GLocalKD achieves promising AUC with large anomaly contamination in training data, supporting its use in semi-supervised and unsupervised settings.The semi-supervised setting uses exclusively normal training data; the unsupervised setting uses anomaly-contaminated unlabeled training data.Source: §6 · p. 8

APPENDIX

The appendix outlines implementation and empirical supplements, then describes GLocalKD training as predictor optimization against a fixed random target network.

APPENDIX

  • The appendix collects implementation details and additional empirical results, including runtime, sensitivity tests, and LESINN subsample-size results.Appendix A gives the algorithm and Appendix B the architecture, hyperparameters, and optimization details.Source: APPENDIX · p. 10

A THE ALGORITHM OF GLOCALKD

  • Training initializes target and predictor weights, then uses stochastic gradient descent to optimize the predictor while the target parameters remain fixed.Each step obtains node and graph representations from both networks and updates the predictor using the model loss.Source: A THE ALGORITHM OF GLOCALKD · p. 10
  • The procedure takes a normal training graph set as input and returns the fixed random target network and learned predictor network.The algorithm computes node and graph representations for each sampled mini-batch.Source: A THE ALGORITHM OF GLOCALKD · p. 10

B IMPLEMENTATION DETAILS

GLocalKD uses a three-layer GCN with max-pooled graph representations. The implementation details specify its training configuration and the comparison methods’ settings.

B IMPLEMENTATION DETAILS

  • Experiments ran on an NVIDIA Quadro RTX 6000 GPU and Intel Xeon E-2288G CPU; OCGCN shares GLocalKD’s GCN architecture.The passage also specifies Python 3.62 and PyTorch 1.93; Table 3 reports training and test times.Source: B IMPLEMENTATION DETAILS · p. 10, Table 3 · p. 10
  • Both GLocalKD networks use three GCN layers, a 512-unit hidden layer, and a 256-unit output layer, with max pooling for graph representations.Source: B IMPLEMENTATION DETAILS · p. 10
  • The learning rate is generally 10^-4, with specified datasets using 10^-5 and PROTEINS_full using 10^-2.Performance on the specified datasets varies little between learning rates 10^-4 and 10^-5.Source: B IMPLEMENTATION DETAILS · p. 10
  • Training runs for 150 epochs, with batch size 300 except on HSE, MMP, p53, and PPAR-gamma, where it is 2000.Source: B IMPLEMENTATION DETAILS · p. 10

C TRAINING AND TEST TIME

Table 3 reports training and test times for methods on REDDIT, p53, and COLLAB. For two-stage methods, training time counts only representation or embedding learning.

C TRAINING AND TEST TIME

D SENSITIVITY TEST

The sensitivity test examines GLocalKD performance in relation to GCN output dimensionality and depth.

D SENSITIVITY TEST

E DETAILED RESULTS OF LESINN

The LESINN results examine performance across subsampling sizes while holding ensemble size fixed.

E DETAILED RESULTS OF LESINN

Loading 2112.10063v1…