Rethinking Graph Neural Networks for Anomaly Detection

2 min read

Tang and colleagues look at graph anomalies through the graph spectrum. Their observation, shown on synthetic graphs and four real datasets, is a “right-shift”: the more anomalous nodes a graph has, the more of the signal’s spectral energy moves from low to high frequencies. Ordinary GNNs act like low-pass filters (they smooth a node towards its neighbours), which blurs the high-frequency part where anomalies show. BWGNN builds a bank of band-pass filters from Beta wavelets on the graph Laplacian, each localised to a few hops, so a node that disagrees with its neighbourhood stays visible.

Findings

  • Four datasets: Amazon (11,944 nodes, 6.87% anomalous), YelpChi (45,954 nodes, 14.53%), and two new ones released with the paper, T-Finance (39,357 nodes, 4.58%) and T-Social (5,781,065 nodes, 3.01%).
  • Removing anomalous nodes shifts spectral energy back to low frequencies, while removing random nodes barely changes it, which supports the right-shift claim on real data.
  • YelpChi with 40% training labels: F1-macro 76.96 and AUC 90.54 for BWGNN (hetero), against 63.00 and 79.87 for PC-GNN, an absolute gain of 13.9 and 10.6 points. Amazon 40%: AUC 98.06.
  • Best on all datasets except Amazon with 1% labels, where PC-GNN has a higher AUC, and much faster to train than the specialised fraud detectors.

Limits

  • The authors assume all edges are trusted and study only node anomalies; structural anomalies (fake or missing edges) are left for future work.
  • It is supervised or semi-supervised: it needs labelled anomalies, and the anomalies have to look like the ones in training.
  • Graphs are static fraud and review networks. Nothing here handles a graph whose edges change every second, or an adversary who adapts to the detector.

Relevance

A robot team’s communication or sensing graph is the kind of graph where one misbehaving node disagrees with its neighbours, so spectral detectors are one candidate for flagging a Byzantine robot. It assumes trusted edges, but in a team a liar controls its own edges. Compare the voting-style trimming in resilient consensus, which needs no labels but does need a bound on the number of liars; see robust robotics.