acceptodds
Under review as a conference paper at ICLR 2027

PopGLAD: Structural Population Scoring for Graph-Level Anomaly Detection

Abstract

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.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Graph Anomaly detection, Unsupervised Learning

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_Z7wvOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies graph-level anomaly detection (GLAD) from the perspective of shared departures across an unlabeled population and introduces a new GLAD method called PopGLAD. PopGLAD represents graphs through normalized attributed WL counts and complementary size statistics, with normal data determining the feature weighting, precision estimates, and directional calibration. Each query is evaluated against the mean departure of the remaining graphs, allowing recurrent changes to contribute evidence even when individual distances are uninformative. Experiments on eight benchmarks demonstrate the effectiveness of PopGLAD.

Critical strengths
  1. Methodological novelty. PopGLAD introduces a population-based scoring approach that captures structural deviations shared across graphs. The idea is novel and offers a valuable way to identify anomaly evidence that individual-distance scoring methods may overlook.

  2. Theoretical contribution. This paper provides a bound on ranking error that accounts for uncertainty in the population reference and dependence between scores. The analysis clarifies when directional scoring offers an advantage over individual-distance scoring and links ranking reliability to the strength and stability of the estimated population direction.

  3. Strong empirical results. PopGLAD achieves strong performance on seven of eight benchmarks. Ablation studies further support the benefits of population scoring, covariance estimation, and view fusion.

Critical weaknesses
  1. Roles of weighting and calibration. As I understand it, the structural view employs a diagonal precision matrix to weight features and utilizes covariance information to normalize scores. However, the authors need to clarify the interaction between these two components and explain how correlations among WL features are handled.

  2. Rationale for the fitting/calibration split. The authors should provide a more thorough justification for how normal data is partitioned, specifically, how they balance the estimation of normal statistics with the calibration of scores. This is crucial for bridging the practical implementation with the discussion of normal-center accuracy.

  3. Connection between theory and empirical analysis. In Figure 5 and Theorem 1, the authors examine reference-direction stability using different transformations. However, the connection between the plotted cosine similarity and the theoretical analysis should be further clarified.

  4. Specification of the denominator floor. The numerical value of τ\tau is not explicitly given. The authors should clarify the practical effect on scoring.

Questions for authors
  1. How do precision weighting and directional calibration work together when WL features are correlated? Moreover, what is the rationale behind using the same regularization parameter (ηs\eta_s) for both stages?

  2. Given that at most 128 calibration graphs are used, what is the basis for the split between the fitting set and the calibration set? I suggest that the authors provide a brief explanation of the balance between normal-statistic estimation and score calibration.

  3. Could the authors explain how the observed cosine similarities support the theoretical claims regarding reference stability?

Reviewer_m6ojOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

In this paper, the authors propose PopGLAD, a graph-level anomaly detection method that leverages population-level structural information to identify anomalies. Unlike conventional approaches that evaluate individual deviations from normality, PopGLAD measures the agreement between each graph's deviation and a reference direction estimated from the remaining unlabeled graphs. The proposed PopGLAD method integrates Weisfeiler-Lehman structural representations with graph-size information, using normal statistics for precision weighting and score calibration. The authors also provide a theoretical analysis of ranking stability under finite reference populations and develop an efficient scoring procedure.

Critical strengths
  • The idea of exploiting shared structural deviations across graph populations is interesting and well-motivated. It provides a useful perspective on detecting anomalies that may not exhibit sufficiently large individual deviations from normality.
  • The experimental results are impressive. On the four larger datasets, PopGLAD achieves significantly higher AUROC and AUPRC than the state-of-the-arts baselines, while the runtime comparison also shows a substantial computational advantage.
Critical weaknesses
  • PopGLAD uses separate normal centers for estimating the population reference direction and centering query responses. Although their respective roles are described in Section 4.3, the motivation for using two different centers should be elaborated.
  • Although the paper compares against numerous deep learning baselines, it lacks comparisons with classical graph kernel methods, such as the Weisfeiler-Lehman (WL) kernel. Since PopGLAD also relies on WL-based structural representations, the authors need to include graph kernels as baselines to provide a more comprehensive evaluation of its advantages.
  • The authors have not released the implementation code of PopGLAD. Although implementation details are included in the appendix, the reproducibility is still limited.
Questions for authors
  • What are the advantages of using separate fitting and calibration centers instead of a shared normal center?
  • Can the authors include a comparison with classical graph kernel methods (e.g., WL) combined with OCSVM or iForest?
  • Can the authors release the source code of PopGLAD to improve the reproducibility?
Reviewer_kg9POpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes PopGLAD, a training-free method for graph-level anomaly detection that scores each graph in an unlabeled collection by how well its departure from normality aligns with the mean departure of the remaining graphs. It combines frequency-weighted Weisfeiler–Lehman features with a small size view, and uses normal graphs to estimate normal feature statistics, calibrate scores, and fuse the two views. This paper also provides a theoretical analysis regarding when directional agreement outperforms individual distances and bounds the ranking error under finite references. PopGLAD achieves competitive performance on eight graph datasets, with large gains on the large-scale datasets and lower runtime than the latest baselines.

Critical strengths

S1. Scoring each graph by its agreement with the population-level departure of the unlabeled collection is a simple and intuitive idea that offers an effective alternative to per-graph deviation scoring.

S2. The empirical improvements are substantial, particularly the large margins on the large-scale datasets, and lower runtime compared to other baselines.

S3. The discussion about the failure modes is insightful as it shows how distinct anomaly groups can cancel in the population mean. This specifically clarifies the scenarios when population agreement loses useful detection information.

S4. The theoretical analysis gives useful intuition for when directional agreement succeeds where individual distances fail.

Critical weaknesses

W1. PopGLAD relies on transductive access to the unlabeled collection, while most baselines are inductive. This setting, including its relation to semi-supervised novelty detection and PU learning, needs a more explicit discussion to help readers interpret the comparison.

W2. Tying the fusion weight to the structural shrinkage coefficient seems heuristic. Its relation to the actual complementarity of the two views is not well explained, even though performance appears sensitive to how the views are weighted.

W3. The method essentially relies on a single aggregate reference direction, which limits its applicability to heterogeneous anomalies without a shared shift. The authors acknowledge this, but a deeper discussion of the assumption is expected.

W4. The theoretical bounds rely on worst-case constants and mainly provide qualitative insight. Therefore, the authors should provide a brief discussion of their tightness.

Questions for authors

Q1. Could the authors discuss how PopGLAD relates to semi-supervised novelty detection and PU learning, which also contrast a normal sample with an unlabeled mixture?

Q2. Could the authors explain the rationale for tying the fusion weight to the structural shrinkage coefficient, and provide a brief sensitivity analysis over the size-view weight?

Q3. Could the authors clarify how PopGLAD behaves when anomalies consist of several subtypes with different structural shifts? Showing which substructures, or at least which WL depths, contribute most to the reference direction can help characterize the shared shift the method relies on.

Q4. Could the authors briefly discuss the tightness of the constants in the ranking bounds?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.