PaperlayerView exact revision on arXiv

Source-linked AI summary

Zero-shot Generalist Graph Anomaly Detection with Unified Neighborhood Prompts

Chaoxi Niu, Hezhe Qiao, Changlu Chen, Ling Chen, Guansong Pang

arXiv:2410.14886v2cs.LG

TL;DR

Dataset-specific graph anomaly detection requires separate models, but graph attributes vary across datasets and graph data lacks the foundation models used in image anomaly detection. UNPrompt normalizes attributes and learns neighborhood prompts for zero-shot detection across graphs. It outperforms competing methods in generalist and unsupervised GAD settings.

  • Problem

    Existing GAD methods train a separate model for each graph dataset, while heterogeneous attributes and the lack of graph foundation models complicate generalization across graphs.

    Source: §1 · pp. 1–2

  • Method

    UNPrompt uses coordinate-wise normalization to align graph attributes and neighborhood prompts trained through latent node attribute prediction to learn generalized patterns.

    Source: §1 · p. 2, §3.4 · pp. 4–5

  • Results

    UNPrompt significantly outperforms competing methods in zero-shot generalist GAD and outperforms all baselines in unsupervised GAD.

    Source: §1 · p. 2, §5.2 · p. 7

  • Takeaways & Limitations

    A detector trained on one graph can detect anomalies in unseen target graphs without retraining or target labels during inference.

    Source: §6 · p. 7

Abstract

from arXiv · show

Graph anomaly detection (GAD), which aims to identify nodes in a graph that significantly deviate from normal patterns, plays a crucial role in broad application domains. However, existing GAD methods are one-model-for-one-dataset approaches, i.e., training a separate model for each graph dataset. This largely limits their applicability in real-world scenarios. To overcome this limitation, we propose a novel zero-shot generalist GAD approach UNPrompt that trains a one-for-all detection model, requiring the training of one GAD model on a single graph dataset and then effectively generalizing to detect anomalies in other graph datasets without any retraining or fine-tuning. The key insight in UNPrompt is that i) the predictability of latent node attributes can serve as a generalized anomaly measure and ii) generalized normal and abnormal graph patterns can be learned via latent node attribute prediction in a properly normalized node attribute space. UNPrompt achieves a generalist mode for GAD through two main modules: one module aligns the dimensionality and semantics of node attributes across different graphs via coordinate-wise normalization, while another module learns generalized neighborhood prompts that support the use of latent node attribute predictability as an anomaly score across different datasets. Extensive experiments on real-world GAD datasets show that UNPrompt significantly outperforms diverse competing methods under the generalist GAD setting, and it also has strong superiority under the one-model-for-one-dataset setting. Code is available at https://github.com/mala-lab/UNPrompt.

1 Introduction

Existing graph anomaly detectors are generally trained separately for each dataset, while graph attributes vary in dimensionality and semantics and graph data lacks the foundation models used in image anomaly detection. UNPrompt addresses these challenges with attribute normalization and neighborhood prompts for zero-shot detection across graphs.

1 Introduction

  • Dataset-specific GAD training limits real-world applicability through repeated computation and labeled-data demands, and target-graph training may be barred by privacy rules.The paper frames generalist anomaly detection as training on auxiliary data and detecting anomalies in diverse targets without retraining or fine-tuning.Source: §1 · p. 1
  • Graph attributes differ in dimensionality and semantics across domains, while graph data lacks the foundation models that support generalist image anomaly detection.The paper asks whether generalist GAD can work across heterogeneous graph attributes and structures without foundation models.Source: §1 · pp. 1–2
  • UNPrompt unifies cross-graph attributes with coordinate-wise normalization and learns generalized neighborhood prompts through latent node attribute prediction.The normalization aligns attribute dimensionality and semantics; neighborhood prompts model graph-agnostic normal and abnormal patterns.Source: §1 · p. 2
  • UNPrompt trains on one auxiliary graph and detects anomalies in unseen graphs without retraining, outperforming competing methods in zero-shot and conventional one-model-per-dataset settings.Figure 1 illustrates attribute unification and compares anomaly scores for methods trained on Facebook and tested on Amazon.Source: §1 · p. 2, Figure 1 · p. 2

2 Related Work

Prior GAD work includes supervised and unsupervised approaches, but direct transfer struggles to capture patterns shared across graphs. Graph prompt learning and generalist anomaly detection provide related directions, though existing prompt methods and ARC do not match UNPrompt’s zero-shot setting.

2 Related Work

  • Unsupervised GAD methods use reconstruction, self-supervision, or learnable anomaly measures, while supervised methods use labeled anomalies and often address over-smoothing.Both approaches struggle to capture generalized normal and abnormal patterns across graph datasets when applied zero-shot.Source: §2 · pp. 2–3
  • Cross-domain GAD transfers knowledge from a labeled source graph to a target graph, requiring training on both, unlike generalist GAD.Existing supervised and unsupervised models can be applied directly to target datasets but struggle to capture generalized patterns.Source: §2 · p. 3
  • Graph prompt methods target task unification or cross-domain transfer, while ARC uses labeled target nodes; UNPrompt instead addresses zero-shot GAD.Graph prompt approaches optimize prompts with labeled downstream data, and ARC is described as a few-shot method.Source: §2 · p. 3

3 Methodology

UNPrompt learns a generalist graph anomaly detector by unifying node attributes and using neighborhood-based latent attribute predictability to distinguish normal from abnormal nodes. It applies the learned prompts to unseen graphs without target labels or retraining.

3.1 Preliminaries

  • Generalist GAD trains on one graph and applies the model to unseen graphs without fine-tuning; the zero-shot setting uses no labeled target nodes.The target graphs may have attributes or structures heterogeneous from the training graph.Source: §3.1 · p. 3

3.2 Overview of UNPrompt

  • The overview combines attribute unification with prompt-based latent attribute prediction, using each node’s predictability as its normal score.At inference, the unified target graph is processed with learned prompts without retraining or labeled target nodes.Source: §3.2 · p. 3

3.3 Node Attribute Unification

  • Coordinate-wise normalization aligns graph attributes by dimensionality and semantics, shifting and scaling each dimension to zero mean and unit variance.Feature projection first maps graph attributes to a common dimensionality.Source: §3.3 · p. 4

3.4 Neighborhood Prompt Learning

  • Neighborhood prompts learn graph-agnostic patterns by maximizing latent-attribute predictability for normal nodes and minimizing it for abnormal nodes.The method treats predictability as a normality measure, motivated by normal nodes tending to connect to similar normal nodes.Source: §3.4 · pp. 4–5
  • A neighborhood aggregation network predicts latent attributes from neighbors; adjacency is excluded from the prediction target to avoid neighborhood-information leakage.The network is pre-trained with graph contrastive learning, then kept frozen while prompts and a transformation layer are optimized.Source: §3.4 · pp. 4–5

3.5 Training and Inference of UNPrompt

  • Training pre-trains the aggregation network, then optimizes prompts and a transformation layer; inference unifies target attributes and uses similarity as the normal score.Inference requires neither retraining nor labeled nodes from the target graph.Source: §3.5 · p. 5

4 Time Complexity Analysis

The section expresses UNPrompt’s overall time complexity in terms of graph size, model dimensions, prompt size, and training epochs.

4 Time Complexity Analysis

  • UNPrompt’s overall time complexity is expressed as a sum of pretraining and prompt-learning costs.The expression includes separate epoch terms for pretraining and prompt learning.Source: §4 · p. 5
  • The complexity expression depends on edge count, node count, hidden-unit and attribute dimensions, prompt size, and the two training-epoch counts.The passage identifies E1 as pretraining epochs, E2 as prompt-learning epochs, and K as prompt size.Source: §4 · p. 5
  • Theoretical and empirical computational-cost results are presented in the appendix.Source: §4 · p. 5

5 Experiments

Experiments test UNPrompt in Facebook-trained zero-shot transfer and conventional unsupervised GAD. Results favor UNPrompt, while ablations and prompt/objective analyses probe its components and design choices.

5.1 Performance on Zero-shot Generalist GAD

  • UNPrompt and competing methods are trained on Facebook and directly tested on other GAD datasets, with AUROC and AUPRC averaged over five random-seed runs.Facebook is selected because its anomaly patterns are described as more generic.Source: §5.1 · p. 6
  • UNPrompt achieves the best AUROC on 5 of 7 datasets and exceeds the best-competing method by over 9% on average.The models are trained on Facebook and evaluated on seven real-world datasets.Source: §5.1 · pp. 6–7, Table 1 · p. 6
  • Ablations on four datasets show all four components contribute: normalization aligns attributes, pre-training supports transfer, prompts capture generalized patterns, and transformation improves anomaly discrimination.The variants remove coordinate-wise normalization, graph contrastive learning-based pre-training, neighborhood prompts, or the transformation layer.Source: §5.1 · p. 7, Table 2 · p. 7
  • As prompt size K varies from 1 to 9, Reddit, Weibo, and YelpChi-all remain stable while other datasets fluctuate slightly.The authors conclude that neighborhood prompts capture generalized patterns even at small sizes.Source: §5.1 · p. 7, Figure 3 · p. 7
  • Latent attribute predictability consistently and significantly outperforms the local affinity-based measure across graphs.This comparison replaces the latent attribute prediction objective with local affinity maximization while keeping UNPrompt's other modules fixed.Source: §5.1 · p. 7, Figure 3 · p. 7

5.2 Performance in Unsupervised GAD

  • In conventional unsupervised GAD, UNPrompt outperforms every baseline on all datasets and surpasses the best competitor by over 2% on average.The authors report this as evidence that latent node attribute predictability also holds as a generalized GAD measure in unsupervised settings.Source: §5.2 · p. 7, Table 3 · p. 7

6 Conclusion

UNPrompt targets zero-shot generalist GAD with one detector trained on a single graph, using coordinate-wise normalization and neighborhood prompts. The graph-similarity analysis finds low similarity across different domains before normalization and aligned attribute distributions afterward.

6 Conclusion

  • UNPrompt trains one detector on a single dataset to generalize to unseen target graphs without retraining or target-node labels.Coordinate-wise normalization aligns attribute dimensionality and semantics; neighborhood prompts learn generalized patterns through latent node attribute prediction.Source: §6 · p. 7

A Graph Similarity

  • Cross-domain graph distributional similarities are typically small, while Amazon and Amazon-all, and YelpChi and YelpChi-all, each have similarity one.The paired datasets come from the same distributions despite differing in node counts and structures.Source: A Graph Similarity · p. 10
  • Coordinate-wise normalization makes node attributes share the same distribution across graphs, supporting the goal of reducing their semantic gap.Distributional similarity is measured by cosine similarity between vectors concatenating coordinate-wise means and variances.Source: A Graph Similarity · p. 10

B Details on Pre-training of Neighborhood Aggregation Networks

UNPrompt pre-trains a neighborhood aggregation network using graph contrastive learning, then learns prompts and a transformation for detection. Its unsupervised variant uses latent attribute predictability as a normal score to guide prompt learning.

B Details on Pre-training of Neighborhood Aggregation Networks

  • Contrastive pre-training uses edge removal and attribute masking, then pulls same-node embeddings across views together and pushes other nodes apart.The resulting objective trains transferable discriminative node representations.Source: B Details on Pre-training of… · pp. 10–11
  • Figure 4 contrasts distributional similarity between graphs without and with coordinate-wise normalization.The caption identifies the two conditions but does not specify a particular outcome.Source: Figure 4 · p. 11

C Algorithms

  • The training algorithm unifies features, pre-trains and freezes the aggregation network, then optimizes prompts and a transformation; inference applies these components to test graphs.The training and inference processes are summarized in Algorithms 1 and 2.Source: D Unsupervised GAD with UNPrompt · p. 11, C Algorithms · p. 11

D Unsupervised GAD with UNPrompt

  • For unsupervised GAD, UNPrompt uses neighborhood-based latent attribute predictability as a normal score and weights prompt learning toward higher-scoring nodes.The score comes from a pre-trained model and may be unreliable for low-score nodes, so the objective does not minimize their predictability.Source: D Unsupervised GAD with UNPrompt · pp. 11–12

D.1 Experimental Setup.

The unsupervised evaluation compares UNPrompt with eight baselines across six datasets spanning different graph distributions and domains.

D.1 Experimental Setup

  • The evaluation uses Amazon, Facebook, Reddit, YelpChi, Amazon-all, and YelpChi-all, covering six distributions and domains.The experiments follow the implementation details used in the generalist GAD setting.Source: §D.1 · p. 12
  • Eight unsupervised baselines are compared, including iForest, ANOMALOUS, CoLA, SL-GAD, HCM-A, DOMINANT, ComGA, and TAM.The baseline selection follows Qiao and Pang (2023).Source: §D.1 · p. 12
  • Each method’s average performance and standard deviations are reported over five independent runs with different random seeds.More experimental details are provided in Section G.2.Source: §D.1 · p. 12

D.2 Main Results.

UNPrompt outperforms competing methods in the unsupervised setting and shows stronger generalist performance as common dimensionality increases. Adding coordinate-wise normalization to existing baselines does not consistently help and downgrades most of them.

D.2 Main Results

  • UNPrompt substantially outperforms all competing methods on every dataset in AUROC and AUPRC, exceeding TAM’s average performance by over 2% in both metrics.It also beats the best competitor by 2%-6% in AUROC on most datasets.Source: §D.2 · p. 12

E.1 Generalist Performance with different common dimensionalities

  • Increasing common dimensionality generally improves UNPrompt’s generalist detection performance, whereas the baselines show inconsistent gains or losses across datasets.Small dimensionality discards attribute information; the analysis uses Amazon, Reddit, Weibo, and YelpChi.Source: §E.1 · p. 12

E.2 Incorporating coordinate-wise normalization into baselines

  • Coordinate-wise normalization does not improve the baselines consistently and downgrades most of them.The authors attribute this to compressed normal-abnormal distinctions and baselines not designed to capture generalized patterns across graphs.Source: §E.2 · p. 12

E.3 Generalist performance with different training graphs

UNPrompt retains strong average generalist performance when trained on Amazon, while unsupervised performance depends on the threshold used to select normal nodes.

E.3 Generalist performance with different training graphs

  • With Amazon as the training graph, UNPrompt achieves the best average AUROC and AUPRC across seven datasets and performs more stably across datasets than BWGNN, GHRN, and XGBGraph.Amazon and Amazon-all share a distribution but differ in node counts and graph structures; only a few methods, including UNPrompt, perform well on Amazon-all.Source: §E.3 · pp. 12–13
  • Figure 5 presents AUROC results for UNPrompt and other baselines under different common dimensionalities; Table 4 reports AUROC and AUPRC results of unsupervised GAD methods on six real-world GAD datasets.“Avg” denotes the average performance of each method.Source: Figure 5 · p. 13, Table 4 · p. 13

E.4 Sensitivity of Unsuperivised GAD w.r.t the threshold

  • Thresholds of at least 30% yield stable unsupervised performance, whereas thresholds of 5%–15% can cause significant drops.At small thresholds, abnormal nodes are more likely to be mislabeled as normal, misleading optimization; larger thresholds focus optimization on high-confidence normal nodes.Source: §E.4 · p. 13

F Time Complexity Analysis of UNPrompt

UNPrompt pre-trains an aggregation network, then freezes it while learning neighborhood prompts and a transformation layer. Its reported runtime is lower than that of the compared baselines.

F Time Complexity Analysis of UNPrompt

  • Graph contrastive pre-training costs O(4E1(|A|dh + Ndhd′ + 6Nd_h^2)); subsequent prompt and transformation-layer optimization costs O((4KNd′ + 2Nd_h^2)E2).The aggregation network is frozen during prompt optimization, but forward and backward propagation through it remains necessary.Source: F Time Complexity Analysis of UNPrompt · pp. 13–14
  • Overall training complexity is linear in the training graph’s nodes, edges, and node attributes, and the trained model detects anomalies on target graphs without further training.The analysis uses a one-layer aggregation network and a single-layer MLP classification head.Source: F Time Complexity Analysis of UNPrompt · p. 14
  • UNPrompt’s training and inference times are much lower than those of the compared baselines, including AnomalyDAE, TAM, GAT, and BWGNN.TAM has the highest time consumption, attributed to multiple graph truncations and local-affinity maximization networks.Source: F Time Complexity Analysis of UNPrompt · p. 14

G.1 Details on Datasets

  • Experiments use eight real-world datasets spanning online shopping, social networks, and co-purchase networks, including large-scale Amazon-all and YelpChi-all.The dataset statistics include nodes, edges, feature dimensions, and anomaly rates.Source: §G.1 · p. 14

G.2 More Implementation Details

The supplementary material specifies shared implementation settings, distinguishes UNPrompt’s cross-domain zero-shot setting from inductive learning and ARC, and identifies limits and future directions.

G.2 More Implementation Details

  • Generalist training uses 200 epochs for graph contrastive pre-training and 900 for neighborhood prompt learning, with the same hyperparameters across target graphs and no target-specific search.Both stages use Adam with learning rate 0.001; pre-training uses edge-removal and attribute-masking probabilities of 0.2 and 0.3, respectively, and temperature τ = 0.5.Source: §G.2 · p. 14
  • For unsupervised GAD, the threshold is set to the 40th percentile of pre-trained normal scores, while prompt size and trade-off parameters are selected by random search.The hidden units are 128 and the scaling parameter α is 10 for all graphs.Source: §G.2 · p. 15

H.1 Difference between Inductive learning and Generalist GAD

  • Inductive graph learning evaluates unseen data from the same source with matching attribute dimensionality and semantics, unlike UNPrompt’s cross-domain, cross-dataset zero-shot setting.Inductive methods train on partial datasets or previously observed dynamic-graph data.Source: §H.1 · pp. 15–16

H.2 Difference between ARC and UNPrompt

  • ARC is few-shot, uses reconstruction error and labeled in-context nodes, and trains on large graphs from multiple domains; UNPrompt is zero-shot and uses latent attribute predictability from one dataset.UNPrompt tests on unseen datasets and domains.Source: §H.2 · p. 16

H.3 Future works

  • UNPrompt cannot currently process graphs with millions of nodes because inference requires loading the full graph; subgraph-based inference is proposed for future work.The paper also suggests exploring multi-hop neighborhoods and extending the method to dynamic graph anomaly detection.Source: §H.3 · p. 16

Related papers

Loading 2410.14886v2…