Self-Discriminative Modeling for Anomalous Graph Detection

To W1: Thank you for the insightful question. The adversarial training of SDM-ATI and SDM-ATII utilizes a generator to produce pseudo-anomalous graphs, with a discriminator balancing this via an adversarial loss (Eq. 9). Therefore, the numbers of training epochs for the generator and discriminator inherently control the gap between normal and pseudo-anomalous graphs. In practice, we employed a balanced setting of training epochs for both the generator and discriminator, and achieved superior performance. As visual evidence illustrated by the t-SNE plots (Figure 7), although generated anomalies stay close to normal data, they remain sufficiently distinct. SDM-NAT controls the gap through $\lambda$, a larger $\lambda$ implies a larger similarity between the generated pseudo anomalous graphs and the normal graphs, but we can observe that the performance is robust across a wide range of $\lambda$ (see Figure 9).

We want to clarify that this setting would not introduce difficulties in training the classifier, as the adversarial dynamic and the joint learning in our methods can adaptively balance the discrimination capability of the classifier and the generation quality of the generator. The performance comparison (Tables 1, 3, and 6) across multiple datasets is good evidence to support this claim, and the embedding separation (e.g., Figure 7) also confirms the discrimination capability of the classifier. Besides, we further provided statistical analysis to demonstrate that pseudo-anomalous graphs are sufficiently different from normal graphs, so that they can truly benefit decision boundary learning (see response to Reviewer 1ZeV's W1).

To W2: Thank you for your valuable concern. We tested the performance by removing the overlapping generated pseudo graph anomalies but gained only a slight improvement (usually $\leq 1\\%$, sometimes even drops) in performance. Actually, our method doesn't require explicitly distinguishing between normal and pseudo anomaly graphs. Our results (e.g., Figure 6) show that despite overlaps observed between normal and pseudo anomalies during training, SDM variants still maintain superior generalization performance in the test phase and achieve robust separation of normal and anomalous graphs.

To W3: We appreciate the suggestion. Actually, we have included relevant visualization results in Appendix E.2. For example, in Figure 7, we not only visualize the normal and real anomalous graphs for our methods (as in other baselines), but also visualize the generated pseudo anomalous graphs for comparison. The data points marked in yellow denote the generated pseudo-anomalous graphs in our methods. We observe that SDM effectively separates normal and anomalous graphs, with pseudo-anomalous graphs interpolated between normal and real anomalous graphs (refer to Figure 7 (h), (i), and (j)). This serves as good evidence to support the strengths of those pseudo-anomalous graphs in learning a more robust decision boundary compared to other baseline methods.

Again, we thank the reviewer for recognizing our work, and we hope that our responses can solve your concerns.

We thank the reviewer for recognizing our work. Below are our responses to your concerns:

To W1: We would like to address your concern from the following two aspects:

1. From the embedding visualization (e.g., Figure 7), the embedding distributions of the pseudo-anomalous graphs are mostly separated into different regions from the normal data. As an illustrative example, Figure 7(j) shows that the pseudo-anomalous graphs successfully interpolate between the real anomalous and normal samples, which is good evidence to demonstrate the effect of the generated pseudo graph anomalies as the auxiliary signals to benefit decision boundary learning.
2. To more explicitly address your concerns, we evaluated SDM-NAT on AIDS (class 1) by employing the normalized $k$-nearest-neighbor distance to quantify the discrepancy. Specifically, we computed the average pair-wise one-nearest-neighbor distance between:

• Normal graphs vs. Normal graphs, which is $0.0127$.
• Real anomalous graphs vs. Normal graphs, which is $0.1056$.
• Pseudo-anomalous graphs vs. Normal graphs, which is $0.0542$.

The results confirm that the pseudo-anomalous graphs are sufficiently different from normal graphs, supporting their role in enhancing decision boundary learning.

To W2: We would like to clarify how our approach ensures the generation of diverse pseudo-anomalous graphs:

1. Our method does not generate pseudo-anomalous graphs as a one-time, static process. Instead, the generation is dynamic and evolves continuously throughout training. Early in the process, the pseudo-anomalous graphs exhibit significant deviations from normal graphs, posing a relatively straightforward GLAD task. As training progresses, the generator will produce pseudo-anomalous graphs that increasingly resemble normal graphs, thereby escalating the difficulty of the task. This progressive shift aligns with the principles of curriculum learning [1], where the model begins with simpler examples and gradually tackles more challenging ones. As a result, the model can be exposed to a broad and diverse spectrum of pseudo-anomalous samples, rather than just a narrow subset.
2. In SDM-ATI and SDM-ATII, the adversarial interplay between generator and discriminator also drives diversity. The generator needs to vary its perturbation strategies to challenge the discriminator, preventing repetitive patterns. This results in the diversity of generated pseudo-anomalous graphs. In SDM-NAT, pseudo-anomalous graphs are generated by sampling from the latent distribution of normal data. Therefore, the generated pseudo-anomalies are expected to enclose the normal samples in the latent space, which naturally enhances the diversity. This also aligns well with our motivation illustrated in Figure 1.

[1] Yoshua Bengio, et al. Curriculum Learning, ICML, 2009.

To W3: The overlap observed in Figure 6 (top row) during training is a natural outcome of the adversarial design of SDM-ATII, where the generator produces pseudo-anomalous graphs resembling normal graphs to challenge the discriminator. Actually, while the overlap is observed, the majority of normal graphs and anomalous graphs are still separable, and it helps the model to learn an effective decision boundary. The results observed in the bottom row of Figure 6 fully validate this claim, where SDM-ATII indicates strong generalization by successfully distinguishing real anomalous graphs in the test phase. We will supplement this discussion in the paper.

To W4: We agree with the reviewer that the robustness evaluation under data contamination is important. In response, we conducted an experiment on MUTAG (class 0) by injecting anomalous data into the training set at varying contamination levels defined as certain percentages of the normal data. The experimental results shown below indicate that the three SDM variants maintain stable performance under different contamination levels, which still outperform SOTA baseline DOH2SC (94.72% AUC w/o contamination) under 10% contamination level. This demonstrates the robustness and real-world applicability of our approach.

$\begin{matrix} \\hline \text{Contamination Level}& &0\\%&10\\% &20\\% &30\\% \\\\\hline \text{SDM-ATI} & \text{AUC} &\bf95.83 (0.00) &94.77 (0.79) &93.85 (0.04) &94.23 (1.23) \\\\ & \text{F1-Score} &\bf83.33 (0.00) &82.61 (0.46) &80.24 (0.00) & 81.27 (1.96)\\\\\hline \text{SDM-ATII} & \text{AUC} & \bf99.31 (1.42) & 97.58 (0.48)&97.25 (0.02) &97.04 (0.15) \\\\ & \text{F1-Score} &\bf99.13 (1.74) & 94.12 (0.00)&88.24 (0.00) &89.22 (0.98) \\\\\hline \text{SDM-NAT} & \text{AUC} & \bf100.00 (0.00)&97.67 (0.73) & 96.44 (0.21) &95.71 (2.17) \\\\ & \text{F1-Score} &\bf100.00 (0.00) &92.16 (1.96) &88.24 (0.00) & 87.70 (3.39) \\\\\hline \end{matrix}$

To Other Comments: We will (1) double-check and harmonize the format of "$*i.e.,*$" and "$*e.g.*,$", and (2) supplement the ratio of samples in each category for all datasets.

We thank the reviewer for the positive comments. Below are our responses to your concerns:

To Q1: The statement "no overlap between $\mathscr{D}$ and $\tilde{\mathscr{D}}$" is intended to facilitate a more precise problem definition for our paper, as we would not be able to identify normal or abnormal for a data point in the overlapping region between $\mathscr{D}$ and $\tilde{\mathscr{D}}$. This is also a common assumption defined in anomaly detection literature [1], where normal and anomalous instances are modeled as originating from distinct distributions to establish a clear separation. However, we recognize the reviewer’s valid concern. In a continuous graph space, distributions may exhibit overlapping supports. We would like to answer this question by the following two aspects:

1. The "no overlap" assumption refers to the idealized setup where $\mathscr{D}$ and $\tilde{\mathscr{D}}$ are generated from non-overlapping processes. This abstraction facilitates the design of our anomaly detection method by providing a clean delineation between normal and anomalous behaviors.
2. In practice, real-world graph distributions may not be perfectly separable, which can be caused by outliers or the nature of the data. Our framework, however, is designed to handle such scenarios effectively. For instance, we generate pseudo-anomalous graphs to simulate $\tilde{\mathscr{D}}$, which may lie close to normal graphs in the feature space. This is evident in our t-SNE visualizations (e.g., Figures 7 and 8), where the proximity of these distributions tests the model’s ability to detect subtle anomalies. Our simulation experiment (in Sec 3.2) and empirical result (in Sec 3.3-3.5) on benchmark datasets demonstrate that the method performs robustly even when the theoretical assumption of non-overlapping supports is relaxed.

[1] Lukas Ruff, et al. Deep One-Class Classification, ICML, 2018.

To Q2: In our paper, we describe our approach as an unsupervised learning problem where "the training data do not contain any anomalous graphs." This means that during the training phase, the model is exposed exclusively to normal graphs from the distribution $\mathscr{D}$, with no anomalous graphs from $\tilde{\mathscr{D}}$ present. This setup aligns with the standard "one-class" anomaly detection paradigm [2], a well-established approach under unsupervised settings. Specifically:

1. Training Phase: The training dataset consists solely of normal graphs (from $\mathscr{D}$), and no labels are provided, consistent with unsupervised learning.
2. Testing Phase: The model is evaluated on a separate test set that includes both normal graphs (from $\mathscr{D}$) and anomalous graphs (from $\tilde{\mathscr{D}}$). The task is distinguishing anomalies from normal instances, despite not encountering anomalies during training.

The reviewer is correct that, in a broader unsupervised learning context, training data could contain a mix of normal and anomalous instances without labels, requiring the model to discover anomalies implicitly. Therefore, we also conducted an experiment to evaluate our performance in the data contamination case (refer to the response to Reviewer 1ZeV's W4), where part of the anomalies are included in the training dataset. We can observe that our method also works when the training data have some unlabeled anomalies.

[2] Bernhard Schölkopf, et al. Estimating the support of a high-dimensional distribution, Neural Computation, 2001.