acceptodds
Under review as a conference paper at ICLR 2027

NORMAL-REFERENCED DISCRIMINATION FOR OPEN-SET GRAPH ANOMALY DETECTION

Abstract

Open-set graph anomaly detection uses labeled normal nodes and a few labeled anomalies to detect both the labeled anomaly types and unseen types absent from the training labels. These labels help the detector learn normal and anomalous patterns, improving its detection accuracy. However, a detector fitted to the labeled types may mistake unseen anomalies for normal nodes. To address this problem, we propose Normal-Referenced Discrimination (NoRD), which trains a single anomaly score using both labeled and unlabeled nodes. The unlabeled nodes contain normal nodes and anomalies, including unseen types. Specifically, NoRD learns to distinguish these unlabeled nodes from labeled normal nodes alongside supervised anomaly detection, allowing unlabeled anomalies to contribute to training. Since both groups contain normal nodes, directly separating them would also encourage high anomaly scores for unlabeled normal nodes. Accordingly, NoRD first expresses each anomaly score relative to the labeled normal scores, providing a common reference for the comparison. It then applies a mixture link that accounts for normal nodes in both groups and reduces the pressure to increase already-low anomaly scores on unlabeled nodes. Experiments on seven public graphs demonstrate consistent improvements over competing methods in both overall and unseen-anomaly detection. Code is available at https://anonymous.4open.science/r/NoRD/.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Open-set graph anomaly detection, Graph neural networks, Density ratio estimation

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_4TNyOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies open-set graph anomaly detection, where labeled anomalies cover only seen anomaly classes while the test graph also contains unseen anomaly classes. The main idea is that the unlabeled set already contains unseen anomalies, so it can provide useful supervision without explicitly synthesizing unseen anomaly examples. NoRD combines supervised detection on labeled normal/seen-anomaly nodes with a normal-referenced discrimination objective. Normal-reference normalization and a mixture link are introduced to avoid incorrectly pushing unlabeled normal nodes toward high anomaly scores. Experiments on seven public datasets and an additional large internal payment graph show consistent improvements over a broad set of baselines, including recent open-set GAD methods such as NSReg and DEMO.

Critical strengths
  1. The motivation is clear. NoRD makes effective use of unlabeled nodes, which may already contain unseen anomalies, rather than relying on synthetic unseen anomalies.
  2. The normal-reference normalization and mixture link are well aligned with the motivation, helping exploit the unlabeled population while reducing the influence of unlabeled normal nodes.
Critical weaknesses
  1. The method relies on a representative normal reference.
  2. The open-set evaluation on Yelp and T-Finance relies on constructed anomaly subclasses. Yelp and T-Finance provide only binary anomaly labels.
  3. Limited comparisons with recent generalist GAD methods.
  4. Although the paper includes several open-set GAD baselines, it lacks comparisons or sufficient discussion of recent generalist and zero-shot GAD methods, including ARC [1], UNPrompt [2], IA-GGAD [3], DR-GGAD [4], AnomalyGFM [5], and REFI-GAD [6].

[1] Liu, Y., Li, S., Zheng, Y., Chen, Q., Zhang, C., and Pan, S. ARC: A Generalist Graph Anomaly Detector with In-Context Learning. NeurIPS, 2024. [2] Niu, C., Qiao, H., Chen, C., Chen, L., and Pang, G. Zero-shot Generalist Graph Anomaly Detection with Unified Neighborhood Prompts. IJCAI, 2025. [3] Zhang, X., He, Z., Fu, C., and Xie, C. IA-GGAD: Zero-shot Generalist Graph Anomaly Detection via Invariant and Affinity Learning. NeurIPS, 2025. [4] Fu, C., He, Z., Zhang, X., Xie, C., Jin, X., and Yang, Y. DR-GGAD: Dual Residual Centering for Mitigating Anomaly Non-Discriminativity in Generalist Graph Anomaly Detection. ICLR, 2026. [5] Qiao, H., Niu, C., Chen, L., and Pang, G. AnomalyGFM: Graph Foundation Model for Zero/Few-shot Anomaly Detection. KDD, 2025. [6] Liu, Y., Liu, Y., Zheng, Y., Liew, A. W.-C., Cao, X., and Pan, S. Rethinking Feature Alignment in Generalist Graph Anomaly Detection: A Relational Fingerprint-based Approach. ICML, 2026.

Questions for authors

see weaknesses

4 comments
AuthorsOpenReview ↗

Response to Reviewer 4TNy (1/2)

Thank you for your valuable feedback and for your positive assessment of our motivation and design. We have revised the paper based on your comments, with the changes marked in blue. We detail our responses below, and please kindly let us know if they address your concerns.

W1: The method relies on a representative normal reference.

A1: We agree with this point. NoRD uses the labeled normal nodes as its reference for what "normal" looks like: the discrimination objective asks which unlabeled nodes differ from them. If the labeled nodes cover only part of the normal population, the normal nodes outside that part also differ from the reference, and the objective can no longer separate them from anomalies as cleanly. The dependence you point out is therefore inherent to the design, and the relevant question is how quickly performance degrades as the reference becomes less representative. Our original experiments sampled the labeled normal nodes uniformly and could not answer it. We have now added an experiment (Section 4.2 and Appendix C.4) in which, on Photo, Computers, and CS, 50%, 80%, or 100% of the labeled normal nodes are drawn from a single normal class, with NSReg and DEMO run on the same partitions.

Table R1. Unseen AUROC / AUPRC (%) when the labeled normal nodes are biased toward one normal class, averaged over Photo, Computers, and CS.

Share from one normal classNoRDNSRegDEMO
Uniform87.10 / 54.2984.79 / 49.7585.41 / 50.89
50%83.36 / 49.6778.76 / 45.9079.03 / 46.30
80%73.47 / 43.3371.65 / 40.8870.35 / 40.06
100%67.59 / 38.9564.89 / 35.2166.23 / 36.16

What Table R1 shows is that this reliance does not turn into fragility. NoRD stays ahead of NSReg and DEMO at every level of bias, so even a poorly chosen reference never leaves it behind methods that use the labeled normal nodes differently. A reference that is skewed but still contains the other normal classes remains quite useful: at 50%, NoRD's lead in unseen AUROC over the stronger baseline widens from 1.7 to 4.3 points, and its accuracy (83.36) is close to what the two baselines reach with an unbiased reference (84.79 and 85.41). The hard case is 100%, where the other normal classes are missing from the reference altogether. Accuracy drops considerably there, but it does so for all three methods, and NoRD keeps a narrow lead. We therefore see the remaining loss as a difficulty that unrepresentative normal labels pose for open-set GAD in general, rather than one specific to normal-referenced discrimination.


W2: The open-set evaluation on Yelp and T-Finance relies on constructed anomaly subclasses. Yelp and T-Finance provide only binary anomaly labels.

A2: Open-set evaluation needs anomaly subclasses, so that some of them can be held out as unseen, but Yelp and T-Finance come with binary labels only. For these two graphs we follow the protocol of NSReg (ICLR 2025, Appendix B.2), which clusters the anomalous nodes with kk-means on Deep Graph Infomax representations, so that open-set methods can be compared under a common protocol; Section 4.1 now states this construction and its source explicitly.

AuthorsOpenReview ↗

Response to Reviewer 4TNy (2/2)

W3: Limited comparisons with recent generalist GAD methods.

W4: Although the paper includes several open-set GAD baselines, it lacks comparisons or sufficient discussion of recent generalist and zero-shot GAD methods, including ARC [1], UniPrompt [2], IA-GGAD [3], DR-GGAD [4], AnomalyGFM [5], and REFI-GAD [6].

A3–A4: Thank you for pointing us to this line of work; the comparison turned out to be informative beyond the ranking itself. Following your suggestion, we ran all six methods on our seven public graphs, under the same partitions and metrics as the other baselines. The results are given below and have been added to Tables 1–2 and Appendix C.1.

Table R2. AUROC / AUPRC (%) on all anomalies.

MethodPhotoComputersCSYelpT-Financeogbn-arxivogbn-proteinsAvg.
ARC57.38 / 9.8253.28 / 15.9050.73 / 22.2764.84 / 24.7376.80 / 25.7248.43 / 16.5253.11 / 9.2157.80 / 17.74
UNPrompt49.04 / 6.7454.03 / 16.8268.86 / 41.1945.27 / 13.2259.76 / 23.6856.80 / 20.2373.33 / 21.0958.16 / 20.42
AnomalyGFM55.32 / 9.7446.35 / 14.3877.18 / 57.9557.84 / 16.1366.81 / 9.8856.07 / 19.9949.41 / 8.5658.43 / 19.52
IA-GGAD46.96 / 8.6863.20 / 35.9870.53 / 38.7358.61 / 20.0769.83 / 19.0457.71 / 20.7268.98 / 54.7462.26 / 28.28
DR-GGAD61.27 / 11.2544.94 / 13.6657.21 / 25.9730.22 / 10.2660.98 / 26.5451.88 / 17.1436.48 / 6.1149.00 / 15.85
ReFi-GAD74.82 / 45.9054.82 / 17.6168.80 / 36.8672.19 / 36.2188.25 / 54.0152.92 / 17.4679.52 / 60.8570.19 / 38.41
NoRD88.05 / 58.4182.29 / 58.1997.23 / 92.7376.77 / 37.8993.26 / 78.0563.25 / 29.5783.59 / 67.9683.49 / 60.40

Table R3. AUROC / AUPRC (%) on unseen anomalies.

MethodPhotoComputersCSYelpT-Financeogbn-arxivogbn-proteinsAvg.
ARC58.10 / 9.4153.38 / 13.6041.59 / 14.7855.62 / 12.9876.39 / 16.2648.41 / 12.9851.38 / 5.0054.98 / 12.14
UNPrompt50.10 / 6.2353.99 / 14.4768.67 / 24.5648.60 / 6.9557.25 / 12.4652.87 / 13.7665.55 / 23.3356.72 / 14.54
AnomalyGFM55.85 / 9.2446.28 / 12.2880.17 / 35.8346.56 / 8.6467.67 / 5.7556.19 / 13.9553.25 / 5.0158.00 / 12.96
IA-GGAD50.70 / 5.3363.21 / 23.6870.38 / 16.7453.20 / 10.4885.60 / 59.2450.68 / 12.8266.97 / 4.3962.96 / 18.95
DR-GGAD62.44 / 7.4344.93 / 11.6850.09 / 17.0541.13 / 5.6359.24 / 18.1151.82 / 13.4933.90 / 3.2849.08 / 10.95
ReFi-GAD54.10 / 6.2951.65 / 13.4867.39 / 32.5767.89 / 18.4184.62 / 68.3251.89 / 13.3471.47 / 8.8964.14 / 23.04
NoRD82.69 / 27.0981.63 / 44.9896.97 / 90.8171.90 / 22.0794.77 / 81.8456.21 / 14.9774.91 / 43.9479.87 / 46.53

NoRD achieves the highest mean on every graph and metric. Beyond the ranking, we would like to discuss what we think the comparison shows.

We believe the gap mainly reflects what each family of methods learns from. Generalist detectors are trained on other graphs and are designed to work on a new graph with few or no labels, so their notion of an anomaly comes mostly from elsewhere. The per-graph results suggest that this notion transfers unevenly: the best generalist method changes from graph to graph, and a method that does well on one graph can fall to or below chance level on another. Open-set GAD instead trains on the target graph itself, and the premise of NoRD is that the unlabeled nodes of this graph already contain the unseen anomalies, so the detector can learn what is anomalous here rather than in general. Adapting with a few target labels narrows the gap only in part: ReFi-GAD, which does so, is the strongest of the six on all anomalies, but its advantage over the zero-shot methods largely disappears on unseen ones.We therefore see the two lines of work as addressing different problems, transferring a detector across graphs versus going beyond the labeled anomaly classes within one graph, rather than as direct competitors, and we have added a discussion along these lines to Related Work.

Thank you again for helping us broaden the comparison. We sincerely hope that our responses have addressed your concerns.

Reviewer_4TNyOpenReview ↗

score

The authors have addressed my concerns. I will raise my score.

Thank you very much for your positive reassessment! We are pleased that our responses have addressed your concerns. We sincerely appreciate your careful review and constructive suggestions.

Reviewer_KsYCOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes NoRD, which combines supervised anomaly detection with discrimination between labeled normal and unlabeled nodes to detect both seen and unseen anomalies in graphs.

Critical strengths
  1. Anomaly detection with limited coverage of anomaly labels has practical value.

  2. The method’s effectiveness is demonstrated on seven datasets.

Critical weaknesses
  1. The method relies heavily on labeled and unlabeled normal nodes following the same distribution. In practice, labeling may involve selection bias, and normal nodes may exhibit diverse patterns that can also evolve over time.

  2. Eq. (9) shows that the mixture link reduces the upward pressure on low-scoring unlabeled nodes, but these nodes may also include unseen anomalies whose scores are underestimated.

  3. In Figure 4, seen and unseen anomalies belong to different categories, but their representations are mixed together and difficult to distinguish under the proposed method. DEMO shows clearer separation between the two groups.

  4. The method section is not clearly presented, and the motivation behind the design is insufficiently explained.

Questions for authors
  1. How can the proposed method remain effective when the training set is not representative of normal patterns?

  2. When anomalies mimic normal nodes, could Eq. (9) cause their anomaly scores to be underestimated?

3 comments
AuthorsOpenReview ↗

Response to Reviewer KsYC (1/2)

Thank you for your thoughtful comments and questions. We have revised the paper based on your feedback, with the changes marked in blue. We respond to each point below and would appreciate it if you could let us know whether our responses address your concerns.

W1 & Q1: The method relies heavily on labeled and unlabeled normal nodes following the same distribution. In practice, labeling may involve selection bias, and normal nodes may exhibit diverse patterns that can also evolve over time. How can the proposed method remain effective when the training set is not representative of normal patterns?

A1: NoRD does treat the labeled normal nodes as representative of the normal population. It finds unseen anomalies by asking which unlabeled nodes differ from the labeled normal ones, so if some normal patterns are missing from the labels, the normal nodes that follow those patterns also look different and become harder to tell apart from anomalies. You point to three ways in which this can happen in practice, and we take them in turn.

Selection bias. We added an experiment that biases the labeling on purpose (Section 4.2 and Appendix C.4): on Photo, Computers, and CS, 50%, 80%, or 100% of the labeled normal nodes are drawn from a single normal class, with NSReg and DEMO run on the same partitions.

Table R1. Unseen AUROC / AUPRC (%) when the labeled normal nodes are biased toward one normal class, averaged over Photo, Computers, and CS.

Share from one normal classNoRDNSRegDEMO
Uniform87.10 / 54.2984.79 / 49.7585.41 / 50.89
50%83.36 / 49.6778.76 / 45.9079.03 / 46.30
80%73.47 / 43.3371.65 / 40.8870.35 / 40.06
100%67.59 / 38.9564.89 / 35.2166.23 / 36.16

NoRD remains effective in the sense that, however biased the labels are, it is still the most accurate of the three methods. When the labels are skewed but the other normal classes are still present, it holds up well: at 50%, its lead in unseen AUROC over the stronger baseline widens from 1.7 to 4.3 points, and it performs close to what NSReg and DEMO achieve with unbiased labels (83.36 versus 84.79 and 85.41). When the other classes are missing from the labels altogether, accuracy drops considerably, but this happens to all three methods alike, and NoRD still ranks first. An unrepresentative training set is thus a real difficulty, but one that comes with the open-set setting rather than with NoRD in particular.

Diverse normal patterns. The normal nodes in these graphs already span several semantic classes, so our main results, obtained with uniformly sampled labels, are results on a diverse normal population.

Patterns that evolve over time. Our graphs are static, so we cannot evaluate temporal drift directly, and we now list it as a direction for future work in the Conclusion. The closest case we can offer is the 100% setting above, where normal patterns present in the unlabeled nodes are completely absent from the labeled ones, as would happen when new normal behavior emerges after labeling. All methods lose substantial accuracy there, and NoRD still ranks first. We therefore expect temporal drift to be a real challenge for this family of methods, and updating the labeled normal nodes over time is the natural remedy to study.


W2 & Q2: Eq. (9) shows that the mixture link reduces the upward pressure on low-scoring unlabeled nodes, but these nodes may also include unseen anomalies whose scores are underestimated. When anomalies mimic normal nodes, could Eq. (9) cause their anomaly scores to be underestimated?

A2: Thank you for this insightful question. The attenuation in Eq. (9) does also apply to low-scoring unseen anomalies. However, it applies equally to the far more numerous low-scoring normal nodes, and removing it raises both groups together, which reduces their separation rather than helping the anomalies.

To check whether this holds for the anomalies you have in mind, we looked at the unseen anomalies that most resemble normal nodes: the 20% with the highest attribute similarity to the labeled normal nodes (Appendix C.5, Table 9).

Table R2. Unseen AUROC (%) on the 20% of unseen anomalies most similar to labeled normal nodes.

VariantPhotoComputersCS
NoRD79.9479.2696.41
w/o mixture link61.6263.4182.82
w/o discrimination objective65.7468.5394.34

As shown in Table R2, the mixture link helps these normal-like anomalies instead of suppressing them: it improves AUROC on this subset by 13.6–18.3 points, about as much as on all unseen anomalies (13.3–20.1 points). Without the link, performance on this subset even falls below that of supervision alone, which is consistent with the explanation above: without the attenuation, discrimination raises the many low-scoring normal nodes together with these anomalies.

AuthorsOpenReview ↗

Response to Reviewer KsYC (2/2)

W3: In Figure 4, seen and unseen anomalies belong to different categories, but their representations are mixed together and difficult to distinguish under the proposed method. DEMO shows clearer separation between the two groups.

A3: We can see why the figure gives this impression. Separating seen from unseen anomalies, however, is not what an open-set detector is asked to do: the two groups share the same anomalous label, and the detector needs to separate both of them from normal nodes, not from each other. Overlap between the two anomaly groups is therefore compatible with effective detection, and what matters in the figure is how each group sits relative to the normal nodes.

Read this way, the high-score regions of NSReg and DEMO concentrate near the seen anomalies, whereas those of NoRD also cover groups of unseen anomalies, with some overlap with normal nodes remaining. This matches the detection results: on Photo, unseen AUPRC is 27.09 for NoRD, 23.52 for NSReg, and 20.98 for DEMO. We have revised the Visualization paragraph in Section 4.2 to state how the figure should be read.


W4: The method section is not clearly presented, and the motivation behind the design is insufficiently explained.

A4: Thank you for this comment. Each component of NoRD is there to solve a specific problem that the previous step leaves open, and the revised method section now follows this chain, introducing each component together with the problem it addresses:

  • Discrimination between UU and RR. The labels cover only one anomaly class, so supervision gives no signal for unseen classes. The unlabeled set UU contains every anomaly class, whereas the labeled normal set RR contains only normal nodes, so whatever separates UU from RR comes from anomalies, seen or unseen. Proposition 1 makes this precise in an idealized setting: the optimal discriminator ranks nodes by their anomaly-to-normal density ratio.
  • Normalization against the normal reference. Most nodes in UU are normal. Applied to the raw score, discrimination would keep normal nodes at a nonzero anomaly probability while supervision pushes them toward zero. Because the ideal discriminator depends on a node only relative to the normal population, NoRD measures each score against the labeled normal nodes, which removes this disagreement without changing the node ordering.
  • Mixture link. Even after normalization, a plain (identity) link would ask every unlabeled node, including normal ones, to score above the reference, and would push hardest on the lowest-scoring nodes. The mixture link keeps an explicit constant term for the normal nodes shared by UU and RR, so low-scoring unlabeled nodes receive little upward pressure.

A new overview in Section 3.2 lays out this chain before any equations; Figure 1 now marks which quantities are raw scores, normalized scores, and probabilities; and Section 3.4 adds a small numerical example. The detailed derivations are in Sections 3.3–3.5.

Thank you again for your advice. We sincerely hope that these responses have answered your questions.

Dear Reviewer KsYC,

Thank you again for your thoughtful comments. They have helped us improve the paper. Following your suggestions, we added an experiment with biased labeling of normal nodes and discussed patterns that change over time. We also explained more clearly how the mixture link handles low-scoring unlabeled nodes, revised how Figure 4 should be read, and reorganized the method section so the motivation for each component comes before its equations.

With less than two days left in the discussion period, we would like to know whether these responses have addressed your concerns. If anything is still unclear, please let us know and we will do our best to respond before the discussion closes. We are grateful for the time and care you have given our work.

Best regards, The Authors

Reviewer_ki8HOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2(+1)
Presentation
1
Soundness
2(+1)
Read review
Paper summary

The paper proposes Normal-Referenced Discrimination (NoRD) for transductive open-set graph anomaly detection. A shared GraphSAGE scorer combines supervised detection with discrimination between labeled normal and unlabeled nodes. Normal-reference normalization and a learned mixture link reduce upward score pressure on unlabeled normal nodes.

Critical strengths

1.NoRD addresses a clear conflict in unlabeled-versus-normal discrimination, adding only one scalar link parameter. Gradient analyses provide an interpretable explanation of its mechanism. 2.Experiments cover seven public graphs, twelve baselines, five runs, and rotating seen anomaly classes, with additional evaluation on an internal payment graph. NoRD achieves the highest mean AUROC and AUPRC under both All and Unseen evaluation.

Critical weaknesses
  1. The methodological presentation is difficult to follow, as numerous quantities are introduced in rapid succession without sufficient explanation of their roles or relationships. In particular, the distinction between the true anomaly proportion α\alpha and the learned mixture-link parameter ρ\rho, as well as the transformation from raw scores fif_i to normalized scores uiu_i, should be explained more clearly.

  2. Figure 1 includes several types of bars, but their meanings and scales are unclear. Readers may struggle to distinguish anomaly scores, exponentiated scores, and membership probabilities, or to connect these quantities to the corresponding equations. The phrase “same shift” also requires clarification: it appears to refer to subtracting the common reference offset bRb_R from every score. Explicit labels and a concrete numerical example would make the figure substantially easier to understand.

  3. The density-ratio interpretation assumes that the labeled normal reference follows the same distribution as the normal component of the unlabeled population, i.e., pR=pNp_R = p_N. This assumption may fail when normal labels disproportionately represent particular communities or attribute groups. Although Appendix A discusses reference distribution shift, the experiments use uniformly sampled normal labels and do not evaluate biased reference selection. The method’s practical robustness to violations of this central assumption therefore remains unclear.

  4. Proposition 1 characterizes the optimal membership logit over unrestricted functions in a fixed representation space. In contrast, NoRD jointly learns a graph encoder and a constrained scoring function using both supervised and discrimination losses. The proposition thus motivates the design but does not establish that the jointly learned scores preserve the desired anomaly ranking. Further analysis connecting the proposition to the actual optimization setting would strengthen the theoretical justification.

  5. NoRD combines a supervised anomaly detection loss with a discrimination loss that separates labeled normal nodes from unlabeled nodes, but their interaction through the shared encoder and scoring network remains insufficiently explained. Because the unlabeled population also contains normal nodes, the discrimination loss may encourage higher scores for these nodes, potentially conflicting with the supervised objective. Could the authors clarify how each loss contributes to parameter updates, how normalization and the mixture link mitigate

Questions for authors

Please see Weaknesses

5 comments
AuthorsOpenReview ↗

Response to Reviewer ki8H (1/3)

Thank you for your careful reading and detailed comments. We have revised the paper based on your feedback, with the changes marked in blue. We detail our responses below, and please kindly let us know if they address your concerns.

W1: The methodological presentation is difficult to follow, as numerous quantities are introduced in rapid succession without sufficient explanation of their roles or relationships. In particular, the distinction between the true anomaly proportion α\alpha and the learned mixture-link parameter ρ\rho, as well as the transformation from raw scores fif_i to normalized scores uiu_i, should be explained more clearly.

W2: Figure 1 includes several types of bars, but their meanings and scales are unclear. Readers may struggle to distinguish anomaly scores, exponentiated scores, and membership probabilities, or to connect these quantities to the corresponding equations. The phrase "same shift" also requires clarification: it appears to refer to subtracting the common reference offset bRb_R from every score. Explicit labels and a concrete numerical example would make the figure substantially easier to understand.

A1–A2: We see these two comments as pointing to the same difficulty: the method works with several kinds of quantities (scores, exponentiated scores, and two different probabilities), and a reader needs to see which is which and how one leads to the next. We have rewritten the method section and relabeled Figure 1 around a single chain, which we summarize here.

The chain starts from the raw score fif_i, the anomaly logit fitted by supervised detection; σ(fi)\sigma(f_i) is the anomaly probability used at inference. The discrimination objective does not use fif_i directly. It first measures each score against the labeled normal nodes, ui=fi−bRu_i=f_i-b_R, where bR=log⁡1∣R∣∑j∈Refjb_R=\log\frac{1}{|R|}\sum_{j\in R}e^{f_j}. This is where the exponentiated scores efje^{f_j} come in: they are positive, unbounded quantities used to compute the offset, not probabilities. It is also what the figure called "same shift": the same bRb_R is subtracted from every score, so the ordering of the nodes is unchanged and ui=0u_i=0 simply means "at the reference level". Finally, the mixture link maps uiu_i to the membership probability qiq_i, the probability that a node comes from the unlabeled set rather than from the labeled normal nodes. This is a different quantity from the anomaly probability σ(fi)\sigma(f_i).

The distinction between α\alpha and ρ\rho belongs to this last step. α\alpha is the proportion of anomalies in the unlabeled set, an unknown property of the data. ρ\rho is a trainable weight inside the mixture link. Discrimination alone cannot identify α\alpha, so NoRD learns ρ\rho jointly with the score and does not interpret it as an estimate of α\alpha.

Following your suggestion, we added a numerical example that walks through the chain. Suppose three reference nodes have efje^{f_j} equal to 1, 2, and 3. Then bR=log⁡2b_R=\log 2, and all scores move down by log⁡2\log 2. A node with fi=log⁡2f_i=\log 2 therefore has ui=0u_i=0, which the mixture link maps to a membership probability of 0.5, while its anomaly probability at inference is still σ(fi)=2/3\sigma(f_i)=2/3.

Figure 1 keeps its layout but now follows the same chain: the number line marks fif_i, the reference scores, and uiu_i; the normalization bars are labeled as efje^{f_j}; the probability bars carry explicit 0–1 scales and are labeled as either σ(fi)\sigma(f_i) or qiq_i; and "same shift" is replaced by "Subtract bRb_R from all scores". These changes are in Sections 3.2–3.5 and Figure 1 of the revised paper.

AuthorsOpenReview ↗

Response to Reviewer ki8H (2/3)

W3: The density-ratio interpretation assumes that the labeled normal reference follows the same distribution as the normal component of the unlabeled population, i.e., pR=pNp_R=p_N. This assumption may fail when normal labels disproportionately represent particular communities or attribute groups. Although Appendix A discusses reference distribution shift, the experiments use uniformly sampled normal labels and do not evaluate biased reference selection. The method's practical robustness to violations of this central assumption therefore remains unclear.

A3: We have now added an experiment with biased reference selection (Section 4.2 and Appendix C.4). On Photo, Computers, and CS, 50%, 80%, or 100% of the labeled normal nodes are drawn from a single semantic class, so that one group is heavily over-represented and, at 100%, all other groups are absent from the reference. NSReg and DEMO are run on the same partitions.

Table R1. Unseen AUROC / AUPRC (%) under biased reference selection, averaged over Photo, Computers, and CS.

Share from one normal classNoRDNSRegDEMO
Uniform87.10 / 54.2984.79 / 49.7585.41 / 50.89
50%83.36 / 49.6778.76 / 45.9079.03 / 46.30
80%73.47 / 43.3371.65 / 40.8870.35 / 40.06
100%67.59 / 38.9564.89 / 35.2166.23 / 36.16

The results show that relying on pR=pNp_R=p_N does not make NoRD fragile when the assumption fails. At every level of bias, NoRD remains ahead of NSReg and DEMO, two methods that are not built on this assumption, so violating it never leaves NoRD worse off than the alternatives. Under moderate bias the advantage actually grows: with half of the reference drawn from a single class, NoRD's lead in unseen AUROC over the stronger baseline widens from 1.7 to 4.3 points, and NoRD with this biased reference (83.36) is close to what the two baselines achieve with an unbiased one (84.79 and 85.41). In the extreme settings, where one class makes up 80% or all of the reference, accuracy drops considerably, but it does so for all three methods, and NoRD still ranks first. We therefore read the remaining loss as the price of unrepresentative normal labels in the open-set setting, rather than as a weakness introduced by the assumption itself.

This pattern is also what the analysis you refer to predicts. In the ideal discrimination rule, a shifted reference adds −log⁡[pR(z)/pN(z)]-\log[p_R(z)/p_N(z)] to the membership logit, so a normal node from an under-represented group looks more like a node that exists only in the unlabeled set, that is, more like an anomaly. The term stays moderate while the group is still present in the reference and is no longer bounded once the group has no reference support at all, which is where the largest drops occur.

AuthorsOpenReview ↗

Response to Reviewer ki8H (3/3)

W4: Proposition 1 characterizes the optimal membership logit over unrestricted functions in a fixed representation space. In contrast, NoRD jointly learns a graph encoder and a constrained scoring function using both supervised and discrimination losses. The proposition thus motivates the design but does not establish that the jointly learned scores preserve the desired anomaly ranking. Further analysis connecting the proposition to the actual optimization setting would strengthen the theoretical justification.

W5: NoRD combines a supervised anomaly detection loss with a discrimination loss that separates labeled normal nodes from unlabeled nodes, but their interaction through the shared encoder and scoring network remains insufficiently explained. Because the unlabeled population also contains normal nodes, the discrimination loss may encourage higher scores for these nodes, potentially conflicting with the supervised objective. […]

A4–A5: Thank you for these two comments, which go to the core of how NoRD works.

First, on the proposition itself, it concerns a fixed representation and an unrestricted logit, so it guides the design of NoRD and does not certify the ranking learned under joint training; Section 3.3 now states this scope explicitly. What it does provide is the form of the parameterization: setting ρ=α\rho=\alpha and ui=log⁡[pA/pN]u_i=\log[p_A/p_N] in NoRD recovers the ideal logit.

Second, to connect this to the actual optimization, we added to Section 3.5 an analysis of the update of the shared encoder and scorer parameters θ\theta:

∇θL=∑i[(1−λ)γiseen+λγidis]∇θfi,\nabla_\theta\mathcal{L}=\sum_{i}\big[(1-\lambda)\gamma_i^{\mathrm{seen}}+\lambda\gamma_i^{\mathrm{dis}}\big]\nabla_\theta f_i,

where γiseen\gamma_i^{\mathrm{seen}} and γidis\gamma_i^{\mathrm{dis}} are the derivatives of the two losses with respect to the score of node ii. The supervised coefficients are nonzero only on labeled nodes: they push labeled normal scores down and seen-anomaly scores up. The discrimination coefficients act on the unlabeled and reference nodes, and this is where the conflict you describe would arise: applied to raw scores, they would push unlabeled normal nodes upward. The two components of NoRD change these coefficients in different ways.

Normalization makes the discrimination coefficients sum to zero, so the discrimination loss does not respond when all scores shift together. It acts only on relative scores, while supervision anchors the labeled normal and anomaly scores.

The mixture link multiplies the coefficient of each unlabeled node by σ(η+ui)\sigma(\eta+u_i), which shrinks the upward pressure on low-scoring unlabeled nodes, the unlabeled normal nodes among them. Table R2 illustrates this against a plain (identity) link.

Table R2. Numerical example with η=−2\eta=-2 (its initial value): membership probability qq / gradient ∂ℓ/∂u\partial\ell/\partial u for an unlabeled node with normalized score uu. A negative gradient means upward pressure.

uu−4-4−2-20022
Mixture link0.469 / −0.001-0.0010.473 / −0.009-0.0090.500 / −0.060-0.0600.638 / −0.181-0.181
Identity link0.018 / −0.982-0.9820.119 / −0.881-0.8810.500 / −0.500-0.5000.881 / −0.119-0.119

With the identity link, the pressure is strongest on the lowest-scoring nodes; with the mixture link it nearly vanishes there. The same attenuation applies to unseen anomalies that receive low scores. As a check on anomalies that are hard to tell apart from normal nodes, we evaluated the 20% of unseen anomalies most similar to normal nodes in their attributes: on this subset, NoRD is 13.6–18.3 AUROC points above the variant without the mixture link (Appendix C.5).

This analysis is at the level of scores, and through the shared encoder the two objectives still interact, so we also test the design directly under joint training. On Photo, unseen AUROC is 67.62 with supervision alone. Adding discrimination without normalization lowers it to 60.58, and without the mixture link to 62.81, consistent with the conflict you describe. With both components it rises to 82.69, and Computers and CS show the same pattern (Table 3). The two components are thus what turn the second objective from a liability into a gain.

Thank you again for your detailed suggestions. We sincerely hope that our responses have made the method clearer and addressed your concerns.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank all reviewers for their careful and constructive comments. We are encouraged that the reviewers find that (a) the problem is clearly motivated and practically relevant, since anomaly labels in practice cover only some anomaly classes; (b) the design is well aligned with this motivation: normal-reference normalization and the mixture link exploit the unlabeled nodes while limiting the influence of unlabeled normal nodes, and the gradient analysis gives an interpretable account of the mechanism; and (c) the experiments cover seven public graphs, twelve baselines, and an internal payment graph, with NoRD achieving the highest mean AUROC and AUPRC on both all anomalies and unseen anomalies.

We have addressed all the reviewers' questions with additional experiments and clarifications, and all of them are included in the revised manuscript (changes marked in blue). Below, we summarize the main changes:

  • Additional results under biased selection of labeled normal nodes, as suggested by Reviewers 4TNy, ki8H, and KsYC,
  • Additional comparisons with recent generalist and zero-shot GAD methods, as suggested by Reviewer 4TNy,
  • Additional results on unseen anomalies that resemble normal nodes, as suggested by Reviewer KsYC,
  • A clearer method section and Figure 1, as suggested by Reviewers ki8H and KsYC,
  • Clarification of Proposition 1 and discussion of the interaction between the two losses, as suggested by Reviewer ki8H,
  • Clarification of the constructed anomaly subclasses and the visualization, as suggested by Reviewers 4TNy and KsYC.

Detailed point-by-point responses are posted under each review. We look forward to further discussion with the reviewers and the area chair.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.