Dear Reviewer H5pG

We deeply appreciate your positive reviews of our research. Your suggestions have greatly inspired our future research direction. Below, we provide detailed responses to your questions.

We provide detailed references in the Global References section of the global rebuttal.

R4.1 - W1 [Title modification]

Thank you for your suggestion regarding our title. We are considering the following modifications:

• On the Limitations of Reconstruction-based Graph-Level Anomaly Detection: Analysis and a Simple Solution.
• Rethinking Reconstruction-based Graph-Level Anomaly Detection: Limitations and a Remedy.

If the reviewer has any additional suggestions or ideas regarding the titles, we would be grateful to hear them.

R4.2 - W2 [Future direction]

Thank you for your suggestion regarding our future direction.

[Challenge: Diversity of potential patterns] Please note that our theoretical analysis focused on specific intuitive cases, which are community structures and cycles, to help readers better understand our analysis concept. However, real-world datasets may exhibit a wider variety of patterns, including those related to node attributes.

• [Example: Homophily] For example, our new analysis of the protein dataset [12] reveals that both normal and anomalous graphs exhibit homophilic patterns (i.e., edges tend to join nodes with the same attribute), with anomalies displaying a stronger pattern than normal graphs. Further details are provided in {R2.2 of our response to Reviewer EQox}.

[Importance of categorization] We agree that categorizing patterns is crucial for systematically understanding our results and generalizing them to a broader range of potential patterns. Unfortunately, however, due to the aforementioned challenges posed by the diversity of potential patterns (including those related to node attributes), categorization is not straightforward. Despite the challenges, we are actively developing a categorization that can include a significant portion of potential patterns.

R4.3 - W3 [Other metrics]

Thank you for your suggestion regarding the diverse evaluation. As verified by our additional experiments, MUSE’s empirical superiority withstands the test of different metrics (AP score and Precision@10).

• [Additional experiments with other metrics] Compared to the two strongest baselines, GLAM [9] and OCGTL [8], MUSE outperforms them in 7/10 and 8/10 datasets in terms of AP score and Precision@10, respectively.
  • AP (Average Precision) score summarizes the precision-recall curve, which considers both precision and recall.
  • Precision@10 measures the number of true anomalies among the top-10 anomaly score data.

[Tables: Results on other metrics]

• [Intuition behind AUROC] We used AUROC for its convenience in evaluation, as it is independent of class thresholding. Due to its convenience, many anomaly detection methods across various domains (e.g., image [1, 2, 3, 4] and graphs [6, 7, 8, 9]) utilize AUROC as their main evaluation metrics.

Dear Reviewer EQox,

We sincerely appreciate the reviewer’s valuable time and efforts. The reviewer’s questions and suggestions have greatly enhanced the alignment between our theoretical analysis and our proposed method. Below, we provide detailed responses to the reviewer’s questions.

We provide detailed references in the G6 section of the global rebuttal.

R2.1 - W1 + Q1 [Gap between analysis and method]

We thank the reviewer for the constructive feedback. Fortunately, we believe the reviewer’s concerns largely stem from our lack of clarity. We claim that our method, MUSE, builds directly upon the analyses in Sec. 3 of our manuscript. Let us clarify.

The central motivation behind MUSE is three-fold:

• [M1] Error distribution serves as a good (i.e., distinguishable) representation for graph-level anomaly detection;
  • The {claims and Theorems in Sec. 3} imply that the two classes (normal and anomaly) have different error distributions. Reconstruction flip in itself indicates that the error distributions differ for the normal and anomalies.
  • {Fig. 5} further buttresses this idea.
• [M2] A naïve use of error distribution, however, can lead to ineffective graph-level anomaly detection;
  • The {claims and Theorems in Sec. 3} imply that considering the graphs with higher mean reconstruction error as anomalies (like many other methods) can be ineffective.
• [M3] Using diverse aspects of error distribution can lead to effective graph-level anomaly detection.
  • {Fig. 5} exemplifies a case where the shape of error distributions helps distinguish two graphs with similar mean reconstruction errors.
• [Proposed method: MUSE] Motivated by [M1,2,3], MUSE represents each graph by using the multifaceted summaries of its reconstruction errors.
  • MUSE pools a graph’s reconstruction errors (M1) using multiple aggregation functions (M3) and uses a vector of these aggregated errors as the graph’s representation (M2).

[M1,2,3] directly supports the design principles of our method, MUSE. We, thus, argue that our analytic insights and method design principles are coherently and tightly connected. We will revise our manuscript to improve clarity.

R2.2 - W2 + Q2 [Real-world dataset analysis]

Thank you for your suggestion. We will include the below analysis in our revised manuscript.

• [Summary] We conducted additional analysis to address the reviewer’s concern. Cases discussed in our analysis (Sec. 3) are also observed in real-world datasets [12, 13]. Moreover, our theoretical findings are in line with our real-world experimental results.
• [Case 1] Anomalous graphs have distinct primary patterns $P$ from normal graphs.
  • [Dataset analysis] The mutagenicity dataset [13] belongs to this case.
    • [Pattern 1] Anomalies tend to contain NH2 and/or NO2 compounds.
    • [Pattern 2] Normal graphs tend to lack such compounds.
  • [Empirical results] In line with our analysis, the reconstruction flip does not occur, as shown in Table 3.
    • Both the existing reconstruction-based anomaly detectors [5, 6, 7] and our method MUSE perform significantly better than the random guess. Specifically, [5, 6, 7] show 0.56, 0.59, and 0.55 test AUROC respectively, and MUSE shows 0.68 test AUROC.
• [Case 2] Anomalous graphs have similar primary patterns $P$ to normal graphs but with different strengths.
  • [Dataset analysis] The protein dataset [12] belongs to this case.
    • [Shared pattern] In all the proteins, the same type of amino acids (nodes) tend to be joined by edges.
    • [Different strength] Such edge homophily patterns tend to be stronger in anomalies than normal graphs. Specifically, the average likelihood of edge homophily in normal graphs is 0.63, while that of anomalous graphs is 0.70.
  • [Empirical results] In line with our analysis, the reconstruction flip occurs, as shown in Table 4 of our manuscript.
    • Existing reconstruction-based anomaly detectors [5, 6, 7] perform worse than random guessing. Specifically, [5, 6, 7] show 0.41, 0.48, and 0.46 test AUROC, respectively.
    • In contrast, our method MUSE performs significantly better than random guessing, outperforming all the baseline methods. Specifically, MUSE shows a 0.78 test AUROC.

Dear Reviewer SHGf,

We deeply appreciate the time the reviewer dedicated to reviewing our paper. Your questions have improved the presentation of the connection between our analysis and method. Below, we provide detailed responses to the reviewer’s questions.

We provide detailed experimental results in the PDF attached in Sec. G7 of global rebuttal, and references in Sec. G6 of global rebuttal.

R3.1 - W1 [Novelty]

We argue that our contribution is novel and valid for 3 reasons:

[Novel method] Among graph-level anomaly detectors [5, 6, 7], MUSE has novel and effective representation learning components.

• [Feature reconstruction loss] We are the first to use cosine loss to stabilize learning in graph-level anomaly detectors.
  • [5] doesn’t reconstruct features, and [6, 7] use the Frobenious norm.
• [Data augmentation] We use graph augmentation to mitigate overfitting.
  • [5, 6, 7] don’t augment graphs.
• [Ablation study] Performance drops in 8/10 datasets when we skip augmentation or change cosine loss to Frobenious norm, proving their necessity.
  • [Result details] Please see Table 1 of the attached PDF.

[Novel findings] We are the first to report and analyze the reconstruction flip issue in graphs, which can hinder anomaly detection, and to propose a solution: represent a graph with multifaceted summaries of its reconstruction errors.

• [Related work] Recent anomaly works [1, 2, 3, 4] share the conventional two-stage framework. However, their key innovations, like ours, were in proposing a good representation, instead of an unconventional framework.

[Other reviewers] We kindly suggest the reviewer to consider other reviewers’ evaluation

• [jxne] “authors proposed MUSE, a novel method”
• [EQox] “authors propose a novel approach”
• [H5pG] “paper proposes a novel graph autoencoder model MUSE”

R3.2 - W2 [Gap between analysis and method]

We argue that our theoretical analysis (Sec. 3) well supports the detection capability of MUSE.

[Motivation] Three motivations, based on our analysis, explain MUSE’s detection capability.

• [M1] Error distribution serves as a good (i.e., distinguishable) representation for anomaly detection;
  • {claims & Theorems in Sec. 3} show that normal and anomalous graphs have distinct error distributions. Reconstruction flip in itself implies that the error distributions differ for normal and anomaly.
• [M2] A naïve use of error distribution can be ineffective;
  • {claims & Theorems in Sec. 3} show that simply using higher mean error as an anomaly indicator (like other methods) is ineffective.
• [M3] Using diverse aspects of error distribution enhances detection;
  • {Fig. 5} shows how the shape of error distributions helps distinguish graphs with similar mean errors.
• [MUSE] It represents each graph with the multifaceted summaries of its reconstruction errors;
  • It pools a graph’s reconstruction errors (M1) using multiple aggregation functions (M3) and uses a vector of these aggregated errors as the graph’s representation (M2).

[Practical relevance] Our additional data analysis supports the practical relevance of our theoretical findings.

• [Reconstruction flips in real-world data] Our new analysis verified that the reconstruction flip, the key concept of our theoretical analysis, indeed occurs in real-world data.
• [Patterns in real-world data] The patterns in the protein dataset [12] affect anomaly detection performance in line with our theoretical analysis. Details are in {R2.2 of our response to Reviewer EQox}.
• [Empirical results] Reconstruction flips occur in the protein dataset (see Table 4 of the paper). Existing reconstruction-based methods [5, 6, 7] perform worse than random guessing due to the flips, while MUSE outperforms all baselines.

R3.3 - W3 [Large graphs]

[New large graphs] We additionally used MalNetTiny [10] and OVCAR-8 [11].

• Graph statistics are in Table 2 of the attached PDF.

[Detection performance] In these new large graphs, MUSE outperforms the two strongest baselines, GLAM [9] and OCGTL [8].

• [Result details] Please see Table 3 of the attached PDF

[Complexity & runtime] Despite having higher complexity than them, MUSE shows practical runtime in large graphs, which we detail in Sec. R3.4 below.

• [Improving complexity] A new variant, MUSE-Sample, having the same complexity as the two baselines, outperforms them in large graphs. MUSE-Sample is detailed in Sec. R3.4 below.

R3.4 - W4 [Complexity]

We argue that MUSE’s greater complexity does not severely harm its practical value, evidenced by its practical runtime.

[Runtime analysis] Despite higher complexity than the two strongest baselines GLAM and OCGTL, MUSE's runtime (from encoding to anomaly score computation) is practical.

• [Result details] Please see Table 4 of the attached PDF
• [Large graphs] MUSE shows practical runtime in large graphs.
  • [MalNetTiny] Handling 200 large graphs (avg. 2215 nodes each) takes 7.2 seconds in total, or 0.036 seconds per graph on average.
  • [OVCAR-8] Handling 40516 graphs (avg. 26 nodes each) takes less than 3 minutes in total, or 0.004 seconds per graph on average.
• [Compared to others] MUSE is faster than OCGTL and, though slower, still comparable in speed to GLAM.
  • [Why MUSE is faster than OCGTL] MUSE uses a single GNN, unlike the ensemble model OCGTL.
  • [Accuracy] Recall that MUSE outperforms them in 8/10 datasets.
• [Improving complexity] We present MUSE-Sample, a variant with the same complexity as these baselines. It is more accurate than them in large graphs (see Sec. R3.3 above).
  • [Detail] It samples entries from an adjacency matrix by the number of edges and reconstructs these entries.
  • [Why MUSE-Sample is slower than MUSE] The sampling time exceeds the time saved in reconstruction.

Dear Reviewer jxne,

We deeply appreciate the reviewer’s dedication to the review process. Your questions helped us better evaluate MUSE from various perspectives. Below, we provide detailed responses to your questions.

We provide detailed references in the G6 section of the global rebuttal.

R1.1 - W1 + Q1 [Role of each stage]

• The impact of each stage in anomaly detection:
  • [Impact of the 1st stage] MUSE first obtains graph (error) representations to effectively distinguish normal graphs from anomalies. The better their representations are distinguished, the better MUSE can detect anomalies.
  • [Impact of the 2nd stage] MUSE, then, detects a graph anomaly by determining if its representation deviates from the distribution of normal graph representations. The better the classifier learns the (error) distribution of normal graph representations, the better it can detect anomalies.
• The impact of noises/mistakes from the 1st stage on the 2nd stage classification:
  • [Impact of noise] For most two-stage anomaly detection methods (including MUSE), noises/mistakes in the 1st stage may disrupt the classification in the 2nd stage.
    • Noises/mistakes may lead the normal and anomalous (error) representations to be less distinguishable, which may hinder the one-class classifier from learning normal graph error distribution.
    • While this is a general challenge in widely used two-stage anomaly detectors [1, 2, 3, 4], many of them achieve SOTA performance in many domains.
  • [Robustness analysis] We empirically showed that noise in the 1st stage does not significantly harm MUSE performance. Specifically, when the training set is contaminated with anomalies that cause noise, MUSE shows the least performance drop compared to the baselines.
    • As shown in Fig. 6, MUSE's performance drops by less than 3% in AUROC, even when the training set is contaminated with up to 30% anomalies.
    • However, the two strongest graph-level anomaly detector baselines [8, 9], which are end-to-end methods, show up to a 10% performance drop.

R1.2 - W2 + Q2 [Other evaluation metrics]

MUSE’s empirical superiority withstands the test of different metrics (AP score and Precision@10).

• [Additional experiments with other metrics] Compared to the two strongest baselines, GLAM [9] and OCGTL [8], MUSE outperforms them in 7/10 and 8/10 datasets in terms of AP score and Precision@10, respectively.

[Tables: Results on other metrics]

R1.3 - W3 + Q3 [Computational complexity]

We argue that MUSE’s greater complexity does not severely undermine its practical value, evidenced by its acceptable runtime.

• [Runtime analysis] Despite having a relatively higher theoretical complexity than the two strongest baselines (OCGTL and GLAM), MUSE's runtime is acceptable in many practical use cases. Specifically, we measured the time from graph encoding to final anomaly score computation.
  • [Large-scale data] In large-scale real-world graphs, MUSE shows acceptable runtime.
    • [Additional datasets] We additionally used two datasets: MalNetTiny [10] and OVCAR-8 [11]. Graph statistics are provided below.
    • [Results in MalNetTiny] For 200 large-scale graphs, with an average of 2,215 nodes in each, MUSE processes them in 7.2 seconds total, or 0.036 seconds per graph on average.
    • [Results in OVCAR-8] For 40,516 graphs, with an average of 26 nodes in each, MUSE processes them in less than 3 minutes total, or 0.004 seconds per graph on average.
  • [Comparison with strongest competitors] MUSE was faster than OCGTL and, although slower, still comparable in speed to GLAM.
    • [Why MUSE is faster than OCGTL] Unlike the ensemble model OCGTL, which uses multiple GNNs, MUSE uses a single GNN, resulting in faster runtime.
  • [Anomaly detection performance] Recall that MUSE outperforms these baselines in 8/10 datasets, demonstrating the accuracy of MUSE.

[Table: Dataset statistics]

[Table: Runtime results (seconds)]

$n$ and $m$ denote the number of nodes and edges, respectively.