- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes KU-GAD, a semi-supervised graph anomaly detection framework that learns anomaly rankings directly by discriminating between verified normal nodes and unlabeled nodes. The authors theoretically show that, under representative normal sampling and a fixed representation, the optimal Known–Unlabeled discriminator preserves the target anomaly ranking. Based on this insight, KU-GAD combines normal-calibrated multi-hop graph representations with a Transformer-based encoder and a Known–Unlabeled discrimination objective. Experiments on seven benchmark datasets demonstrate competitive performance, supported by ablation and sensitivity analyses.
Critical strengths
S1:Clear motivation and theoretical interpretation. The paper provides a clear and intuitive perspective on learning anomaly rankings from known normal and unlabeled nodes, supported by theoretical analysis. S2:Comprehensive experimental evaluation. The paper demonstrates strong performance across multiple benchmarks and includes extensive ablation and sensitivity analyses to validate the proposed method.
Critical weaknesses
W1:Insufficient evaluation of the KU objective. Although the paper provides extensive ablation studies, it lacks a direct comparison of different training objectives under the same encoder. Such experiments would help clarify whether the performance improvements mainly come from the proposed Known–Unlabeled discrimination objective or the representation architecture. W2:Fairness of baseline comparisons. Some baseline results are taken directly from previous papers rather than reproduced under the same experimental settings. The authors should further clarify whether the data splits, training protocols, and hyperparameter settings are sufficiently consistent to ensure fair comparisons. W3:Lack of computational efficiency analysis. The proposed method involves multi-hop graph propagation and Transformer-based aggregation, which may introduce additional computational overhead. However, the paper lacks a detailed analysis of training time, inference cost, and memory consumption, making it difficult to assess its scalability and practical efficiency.
Questions for authors
Q1. Effectiveness of the KU Objective. Could the authors provide an objective-level ablation study using the same encoder but different training objectives, such as normal-only or pseudo-anomaly-based objectives? This would help clarify whether the performance improvements primarily come from the proposed KU objective or the representation architecture. Q2. Practical Applicability of the Theoretical Assumption. The theoretical analysis assumes that the known normal nodes are representative of the overall normal population. Although the paper investigates reference bias, could the authors further discuss how this assumption can be satisfied in real-world scenarios and how KU-GAD performs when the assumption is violated? Q3. Fairness of Baseline Comparisons. Some baseline results are taken from previous studies. Could the authors clarify whether these methods follow consistent data splits, normal-reference budgets, evaluation metrics, and model-selection protocols? A more controlled comparison would help establish the reliability of the reported improvements.
4 comments
A2. Representative Normal Sampling
We appreciate the reviewer's thoughtful question regarding the practical applicability of the representative-normal assumption. We agree that understanding reference representativeness is important for applying KU-GAD in real-world scenarios, and we clarify both the practical considerations and empirical evidence below.
The representative-normal assumption concerns the coverage of the underlying normal population, rather than merely the correctness of known-normal labels.
Practical applicability. In real-world applications, representative references can be constructed by sampling candidate nodes broadly from the target population and subsequently verifying their normality. Ensuring coverage across diverse behavioral, feature, and structural subgroups can further reduce selection bias. This provides a practical reference-acquisition strategy consistent with our theoretical assumptions.
Theoretical interpretation. When the reference distribution differs from the target normal distribution, the population-optimal score decomposes as:
The additional term characterizes the effect of reference-selection bias on anomaly ranking.
Empirical evidence. We have directly investigated violations of representativeness in Section 5.4, Figure 2, and Appendix C.3 (Table 7), using controlled reference-bias experiments across six datasets and five paired seeds.
Reference-bias sensitivity (AUROC / AUPRC):
| Reference sampling | Amazon | Photo | Elliptic | T-Finance |
|---|---|---|---|---|
| Unbiased (β=0) | .917/.874 | .933/.910 | .897/.886 | .870/.802 |
| Mild bias (β=0.5) | .862/.810 | .903/.878 | .923/.904 | .882/.820 |
| Strong bias (β=4) | .533/.337 | .544/.337 | .849/.742 | .817/.507 |
The results demonstrate dataset-dependent robustness to reference shift. Under mild bias, Elliptic and T-Finance retain or slightly improve their performance, while stronger bias produces more substantial degradation, particularly on Amazon and Photo. The full six-dataset results in Table 7 confirm that severe bias reduces both metrics across all evaluated graphs.
Our complementary reference-budget analysis (Appendix C.4) further examines supervision levels from 1% to 15%, distinguishing the amount of normal supervision from its representativeness.
Together, the theoretical analysis and controlled experiments establish a practical guideline for representative normal-reference acquisition and an empirical characterization of KU-GAD's robustness under reference shift.
A3. Baseline Fairness
We thank the reviewer for emphasizing the importance of fair and consistent baseline comparisons. In response to this valuable concern, we conducted a new matched evaluation of RHO and GraphNC within our unified experimental framework.
We implemented both methods following their published approaches, adapting their data interfaces and known-normal reference handling to the common graph and supervision protocol. For GraphNC, this additionally involved retraining its GGAD teacher on the matched graph data. We preserve each method's own training and checkpoint-selection procedures while matching the graph data, reference splits, and evaluation protocol.
All three methods were evaluated using identical canonical graphs, ten paired known-normal reference splits, the same evaluation populations, and consistent AUROC/AUPRC calculations.
Matched baseline comparison (AUROC / AUPRC, 10 paired splits; RHO and GraphNC adapted to the common protocol):
| Method | Amazon | Photo | Elliptic | T-Finance | Tolokers | Questions |
|---|---|---|---|---|---|---|
| RHO | .837/.438 | .711/.237 | .718/.196 | .488/.049 | .520/.288 | .496/.033 |
| GraphNC | .666/.268 | .591/.133 | .503/.116 | .724/.245 | .479/.240 | .483/.037 |
| KU-GAD (Ours) | .904/.738 | .945/.803 | .911/.783 | .892/.714 | .730/.432 | .583/.059 |
KU-GAD achieves the highest mean AUROC and AUPRC across all six datasets, demonstrating its effectiveness under matched graph data, known-normal supervision, and evaluation protocols.
These additional controlled results strengthen the empirical evidence for KU-GAD's improvements over representative graph anomaly detection baselines.
A4. Computational Efficiency
We sincerely appreciate the reviewer's suggestion to examine computational efficiency and scalability. To directly address this concern, we provide both a complexity analysis and empirical measurements of training time, inference cost, and memory consumption, including evaluation on the million-node-scale DGraph dataset.
Complexity analysis. KU-GAD avoids quadratic attention over graph nodes. Its multi-hop representations are constructed through sparse graph propagation, which can be precomputed for a fixed configuration. For a graph with nodes, edges, feature dimension , and propagation depth , propagation and normal-reference calibration require operations.
Importantly, the Transformer performs attention across hop representations within each node, rather than across graph nodes. With hop-sequence tokens (including the CLS token) and hidden dimension , its attention complexity is per layer, with additional linear-in- projection and feed-forward costs.
Consequently, for fixed model dimensions and propagation depth, KU-GAD scales as on a sparse graph, rather than . This architectural property makes multi-hop propagation and Transformer-based aggregation practical for large-scale graphs.
We further measured the practical costs on Photo, T-Finance, and DGraph.
Computational efficiency (single RTX 2080 Ti, fixed configuration):
| Dataset | Preparation | Training | Full-U inference | Peak GPU memory |
|---|---|---|---|---|
| Photo | 16.51 s | 23.73 s | 0.566 s | 0.547 GiB |
| T-Finance | 39.90 s | 25.43 s | 0.095 s | 0.854 GiB |
| DGraph | 203.40 s | 238.65 s | 5.095 s | 0.346 GiB |
Inference uses prepared graph representations; GPU memory denotes peak allocated training memory. The DGraph training measurement includes diagnostic operations.
Notably, on DGraph with approximately 3.7 million nodes, graph preparation takes 203 seconds, fixed-configuration training takes 239 seconds, and inference over 3.519 million unlabeled nodes takes only 5.10 seconds. Peak training GPU allocation is 0.346 GiB, with a peak sampled CPU RSS of 6.711 GiB.
These results demonstrate that KU-GAD's multi-hop propagation and Transformer-based cross-hop aggregation remain computationally practical on large sparse graphs, combining favorable scaling with efficient training and batched inference.
A1. Effectiveness of the KU Objective
We sincerely thank the reviewer for highlighting the importance of isolating the contribution of the KU objective. Following this valuable suggestion, we conducted an objective-level ablation with a shared encoder, comparing KU-GAD against Deep SVDD (Ruff et al., ICML 2018) and OC-NN (Chalapathy et al., 2018), two representative normal-only learning methods.
All methods share the same normal-calibrated multi-hop inputs, Transformer encoder architecture, paired initialization, reference splits, and main-objective training budgets, with objective-specific scoring heads.
We further include KU-hinge, which replaces the original KU-logistic loss (Eq. 5) with a unit-margin hinge objective while preserving K/U supervision:
Lhinge=21EK[max(0,1+s)]+21EU[max(0,1−s)]
Objective-level ablation with a shared encoder (mean AUROC / AUPRC, 10 paired seeds):
All methods are evaluated using common fixed training configurations, independently of the label-free selection used in the original benchmark.
KU-logistic consistently surpasses both one-class objectives in mean AUROC and AUPRC across all six datasets. The same advantage holds in an additional experiment where every method receives identical K-only reconstruction pretraining before objective-specific optimization.
By controlling the encoder architecture and initialization, these results provide direct evidence that the proposed KU discrimination objective contributes to the performance improvements beyond the graph representation architecture itself, validating its role as a central component of KU-GAD.