Example-based explanations for streaming fraud detection on graphs

•Selection of explanations with our approach is 4× faster than the baselines.•The runtime for graph similarity scoring improves by up to four orders of magnitude.•Our approach accumulates up to 26× higher utility of explanations.•Evaluations include 3 datasets, 5 synthetic models, 9 baselines, and 4 metrics.•Our optimisations are robust to different input rates and concept drifts.