PopGLAD: Structural Population Scoring for Graph-Level Anomaly Detection

Graph-level anomaly detection (GLAD) identifies graphs whose structure or attributes deviate from normal patterns. Many existing methods assess each graph through its departure from learned normality. Such scores can obscure a structural change that is weak in individual graphs but consistent across anomalies. To address this challenge, we propose PopGLAD, a population scoring method that leverages an unlabeled graph collection to capture shared evidence. For each graph, PopGLAD estimates a reference direction from the mean departure of the remaining unlabeled graphs and measures directional agreement relative to normal variation. PopGLAD evaluates this agreement in complementary structural and size views that capture local connectivity and graph scale, with normal statistics determining the comparison geometry and calibration. The final scores can be computed efficiently from shared population summaries without explicit pairwise graph comparisons. Our theoretical analysis bounds their pairwise ranking error and characterizes how the strength and stability of the population direction affect the reliability of scoring. Experiments on eight graph benchmarks demonstrate the superiority of PopGLAD over state-of-the-art GLAD baselines.