Rethinking Reconstruction-based Graph-Level Anomaly Detection: Limitations and a Simple Remedy
Authors: Sunwoo Kim
Soo Yong Lee
Fanchen Bu
Shinhwan Kang
Kyungho Kim
Jaemin Yoo
Kijung Shin
Venue: NeurIPS 2024 poster (2024)
Keywords: graph-level anomaly detection
graph neural network
graph autoencoder
Primary area: graph_neural_networks
TL;DR: We investigate reconstruction-based graph neural networks in graph-level anomaly detection task.

Abstract: Graph autoencoders (Graph-AEs) learn representations of given graphs by aiming to accurately reconstruct them. A notable application of Graph-AEs is graph-level anomaly detection (GLAD), whose objective is to identify graphs with anomalous topological structures and/or node features compared to the majority of the graph population. Graph-AEs for GLAD regard a graph with a high mean reconstruction error (i.e. mean of errors from all node pairs and/or nodes) as anomalies. Namely, the methods rest on the assumption that they would better reconstruct graphs with similar characteristics to the majority. We, however, report non-trivial counter-examples, a phenomenon we call reconstruction flip, and highlight the limitations of the existing Graph-AE-based GLAD methods. Specifically, we empirically and theoretically investigate when this assumption holds and when it fails. Through our analyses, we further argue that, while the reconstruction errors for a given graph are effective features for GLAD, leveraging the multifaceted summaries of the reconstruction errors, beyond just mean, can further strengthen the features. Thus, we propose a novel and simple GLAD method, named MUSE. The key innovation of MUSE involves taking multifaceted summaries of reconstruction errors as graph features for GLAD. This surprisingly simple method obtains SOTA performance in GLAD, performing best overall among 14 methods across 10 datasets.

Rethinking Reconstruction-based Graph-Level Anomaly Detection: Limitations and a Simple Remedy
Sunwoo Kim', Soo Yong Lee', Fanchen Bu?, Shinhwan Kang', Kyungho Kim Jaemin Yoo?, Kijung Shin
Kim Jaechul Graduate School of AI, Schooo of Electrical Engineering Korea Advanced Institute of Science and Technology (KAIST) (kswoo97, syleetolow, boqvezen97, shinhwan. kang, kkyungho, jaemin, kijungs)@kaist.acc
Abstract
Graph autoencoders (Graph-AEs) learn representations of given graphs by aiming to accurately reconstruct them. A notable application of Graph-AFs is graph-level anomaly detection (GLAD), whose objective identify graphs with anomalous topological structures and/or node features compared to the majority of the graph population. Graph-AEs AEs for GLAD regard graph with a high mean reconstruction etror (i.e. mean of errors from all node pairs and/or nodes) anomalies. Namely, the methods rest on the assumption that they would better reconstruct graphs with similar characteristics to the majority. We, however, report non-trivial counter- examples, phenomenon we call reconstruction flip, and highlight the limitations of the existing Graph-AE- -aabaedd based GLAD methods. Specifically, theoretically investigate when this assumption holds and when it fails. Through our analyses, further argue that, while the reconstruction errors for given graph are effective features for GLAD, leveraging the multifaceted summaries reconstruction errors, beyond just mean, can further strengthen the features. Thus, we propose a novel and simple GLAD method, named MUSE. The key innovation of MUSE involves taking multifaceted summaries of reconstruction errors graph features for GLAD, This surprisingly simple method obtains SOTA performance in GLAD, performing best overall among 14 methods across 10 datasets.
empirically and
the
Introduction
Graph autoencoders (Graph-AEs) representations of given graphs by aiming to accurately reconstruct them. Representative examples of Graph-AEs include GAE [22] and GraphMAE [15), which respectively aim accurately reconstruct graph structure and node features. Graph-AEs have a broad spectrum of applications, such as anomaly detection [38, 33, 6] and link prediction [13, 22, 24].
family of graph neural networks (GNNs) that learn latent
Graph-ABs are trained to capture the structural information graphs used for training (i.e., training graphs). Thus, intuitively, Graph-AEs expected to better reconstruct graphs that are similar to the training graphs. However, to our surprise, this expectation is not always true. Given Graph-AEs trained reconstruct the graphs in Figure ((a), which share common structural characteristics, one would expect that the Graph-AEs would reconstruct the training graphs with smaller reconstruction errors than dissimilar counterpart (e.g., in Figure 1 (b)). We, however, report the opposite. The reconstruction error is lower for the graph in Figure ((b) than the training graphs. While similar observations were reported in computer vision application [31], which elaborate in Section 2.1, the existing literature does not clearly explain the aforementioned phenomenon.
This counterintuitive phenomenon guides our analysis, implication, and the proposed method. First, we aim to understand this counterintuitive phenomenon, which we refer to as the reconstruction flip
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Error: 0.706
Error: 0.709
Error: 0.710
Error: 0.676
(a) Training graphs
(b) Unseen graph
Figure I:
The training graphs in (a) and the unseen graph (b) exhibit different structural character- istics, but Graph-AE model reconstructs the graph in (b) more accurately than those in (a).
We argue that the phenomenon can occur when (1) the training graphs and unseen graphs share primary structural pattern and (2) the pattern is more pronounced in unseen graphs than in training graphs. We corroborate our claim with our theoretical and empirical analysis.
Second, finding has strong implications for graph-level anomaly detection (GLAD). GLAD aims to identify graphs of different characteristics (e.g., structures and/or features) from the majority [38, 33, 39, 32]. Many existing GLAD methods leverage Graph-AEs [33, 38]. They regard a graph with high mean reconstruction error (i.e, mean of errors from all node pairs and/or nodes) as anomalies, assuming trained Graph-AEs would struggle to reconstruct the graphs with structural patterns (and/or node attributes) that deviate from most training graphs. However, our finding suggests that this assumption does not always hold. Specifically, anomalous graphs with structural characteristics distinct from the training graphs may exhibit similar or even lower mean reconstruction errors. In such cases, the existing methods would struggle to detect anomalous graphs. We argue that this issue arises from how the existing methods leverage reconstruction errors, yet these errors remain valuable graph features for GL.AD. We propose using multifaceted summaries of the reconstruction errors, rather than relying solely on their mean, to further enhance the features.
Third, based on the analysis and implication, we propose simple and novel GLAD method, MUSE (Multifacted Summarization of Reconstruction Errors). MUSE, like other Graph- Araph-AE-based GLAD methods, reconstructs given graphs. However, MUSE employs new way of using reconstruction errors: representing a graph with multifaceted summaries (e.g., mean, standard deviation, etc.) of the graph's 's reconstruction errors for GLAD. This simple innovation allows MUSE obtain SOTA performance in the GLAD tasks. Through our extensive experiments including 13 baseline methods and 10 benchmark datasets, MUSE performs overall best, achieving up to 28. performance gain (in terms of AUROC) compared to the best competitor. We summarize our contribution as follows:
Analysis (Section 3) with implications (Section 4): We investigate the reconstruction flip phe- nomenon both theoretically and empirically, yiclding practical implications for GLAD.
Effective method (Section 5): Motivated by our analysis, we propose MUSE, simple yet effective GLAD method that represents graph multifaceted summaries of its reconstruction errors.
Extensive experiments (Section 6): Our experiments 10 datasets demonstrate the superiority of MUSE over prior GLAD methods. Our code and datasets are available at https: github. com/kswoosh /CLAD_MUSE.
2 Related Work and Preliminaries
In this section, we provide brief literature review graph-level anomaly detection (GLAD) and peculiar observations in GLAD. We then present the preliminaries of our work.
2.1 Related work
Graph-level anomaly detection. Graph-level anomaly detection (GLAD) aims to identify graphs
whose characteristics deviate from those of the majority of the graph population [38, 33, 39, 32].
GLAD has various applications, including brain diagnosis [25] and drug discovery [46]. While several GLAD methods require anomaly label supervision to train a detector 35), we focus on the methods that do not require anomaly labels [38. 33, 39, 32], since anomaly labels are often not available in real-world scenarios. A GLAD method typically trains model to perform certain pretext tasks on given graphs, and the graphs are regarded as anomalies if the trained model shows poor pretext task

---

performance on them. Notable pretext tasks include graph reconstruction [38, 33], graph embedding hypersphere minimization [39, 57], and cross-view mutual information maximization [34, 32].
Peculiar observations in graph-level anomaly detection. The most relevant literature with our work is a study of Zhao and Akoglu [56]. In graph classification datasets, they regarded graphs belonging to particular class as normal graphs and otherwise as anomalies to benchmark several GLAD methods. In this setting, they observed that several GLAD methods, especially kernel-based ones, occasionally perform worse than random guessing. However, their analysis focused on graph kernels [37, 41], without covering graph autoencoders, which are our focus. computer vision, Liu et al. [31] suggested that certain anomalous images can be easier to reconstruct than normal ones, presenting a method that can overcome these undesirable circumstances. However, neither their analysis nor the method can be trivially extended to the graph domain, as elaborated in Appendix F.I.
2.2 Preliminary
Graphs. A graph G (V, is defined by node set = {ui...., fldin and an edge set & fei,..., ,ig)), where each edge e, E & is defined by node pair. We assume that each node i; E V equipped with a feature vector X; E Rdd which forms a node feature matrix X E TR [ where each i-th row X;: = x,. Moreover, can be represented by an adjacency matrix A E {0. 13 V|x|1| where A. = 1 if and only if 25) E & Therefore, the graph can also be defined as G = (X, A).
Graph neural networks. Graph neural networks (GNNs) a category of neural networks designed for processing graph data. GNNs primarily leverage message passing schemes [49, 14, 45, 11, 28, 30]. In this work, we consider GNNs as parameterized functions So that generate node embeddings Z = fx A) V/) for each graph G AX Graph autoencoders. Graph autoencoders (Graph-AEs) are a family of GNNs that learn graph latent representations by graph reconstruction. Specifically, Graph-AEs reconstruct given graph's structure [22, 43] and/or node features [15, 16]. For example, GAE [22] reconstructs the adjacency matrix of given graph. Specifically, GAE first uses encoder GNN fa to generate node embeddings Z = fo(X, A) of a given graph 9 = (X, A). Then, GAE obtains a reconstructed adjacency matrix through the cnner-produs of node embeddings and entry-wise sigmoid activation a (i.e.,
Á E [V] x|V|
Á a (ZZZ)), Lastly, it minimizes the difference between A and A, for which one can use the binary
cross-entropy (BCE) loss LACE(G | Sa) == -- - (As log Aij + (1 Ai.j) log (1 Ai.))
|4]
2 or the squared Frobenius-norm loss LSEN (9 So) = |A - A = Σm AA. - Ans) Given set of training graphs G (91, 92.-.. .9 96 GAE is trained (i.e., the encoder parameter is updated) minimize Egec L( fo) (or equivalently, Bg fo)), where L is LACF LSEN.
In our analysis below, we focus on methods that reconstruct graph structures, while we describe and investigate aadeffeature-rrcconstuciioo methods in Appendix E.I.
3 Analysis of Graph Autoencoders
In this section, we explore reconstruction flip phenomena (c.g., the phenomenon described in Figure 1). where graph autoencoders (Graph-AEs) reconstruct some unseen graphs that are dissimilar to training graphs better than training graphs.
Our analysis focuses on evidencing the claims below. We assume GAE [22] trained on graphs sharing a primary pattern P of strength S.
Claims
Reconstruction flip tends to occur when unseen (test) graphs have the same primary pattern P but with greater strength S' > S.
Reconstruction flip tends not to occur when unseen (test) graphs have a different primary pattern p' P PP
'Some GNNs designed to produce edge embeddings [58, 58] and/or graph embeddings [52, 10].
3

---

Com-Com dataset
Cycle-Cycle dataset
BCE loss
0.775
0,750
Frobenius loss
26
BCE loss
0.690
Frobenius lose
25,020
Unseen graphs (same pattern but stronger strength)
0.725
25
0.696
25.019
25.003
Training graphs (same pattern weaker strength)
0.675
0.694
25.000
100 Epochs
200
1,00 200
100
200
100
200
Epochs
Epochs
Epochs
Figure 2: Reconstruction flip occurs. When Graph-AEs are trained on graphs sharing primary
pattern of weak strength, the trained Graph-AEs exhibit lower reconstruction errors for graphs with the same pattern but with higher strength (red lines) than those with weaker strength (blue lines).
Com-Cycle dataset
Cycle-Com dataset
Frobenius loss
30
0.6938
Frobenius loss
BCE loss
BCE loss
Unseen graphs (dissiinct pattern)
0.6936
0.8
26
Training graphs (same pattern)
0.7
100
200
100
0.6932
100 Epochs
25
100
Epochs
Epochs
Epochs
Figure 3:
Reconstruction flip does NOT occur. When Graph-AEs are trained on graphs sharing
primary pattern, the trained Graph-AEs exhibit higher reconstruction errors for graphs with a different pattern (red lines) than those with the same pattern (blue lines).
That is, when Graph-AEs Graph-AEs tend to exhibit lower errors in reconstructing graphs with P of greater strength S' > S. However, the trained Graph-AEs tend exhibit higher errors in reconstructing graphs with a different pattern P' * P. For demonstration, we elaborate on P and S via synthetic datasets (Section 3.1) and present both empirical (Section 3.2) and theoretical (Section 3.3) investigations.
trained graphs with a primary pattern P of strength S, the trained
3.1 Synthetic graphs
To elaborate on the concepts of a primary pattern P and pattern strength S, we employ two types of synthetic graphs: (1) graphs with community structures and (2) graphs with cycles.
Community type. Syn-Com graphs have community structures, a pervasive pattern in real-world graphs [12], the primary pattern P. Graphs in Figure 1 are instances of such graphs. We control the strength of community structures through parameter 7 [0, 1]. The 10 nodes in each graph evenly divided into communities. Each intra- and inter-community edge is formed with probability (1 + r)/2 and (1 - r)2 respectively. In our empirical analysis, we consider two graph classes with different 7 Graphs in one class G,mm
generated with 0.4 (weaker community structure; the graphs in Figure I(a)) and those in the other class Coom are generated with 7 0.8 (stronger community structure; the graph in Figure 1(b)).
Cycle type. Syn-Cycle graphs contain a cycle of nodes (i.e., closed chain of nodes), which is commonly observed in real- world graphs [8]. In Syn-Cycle, the primary pattern P corre- sponds to the node cycle. Graphs in Figure 4 are instances of Syn-Cycle. In Syn-Cycle graphs, the pattern strength S is stronger in the clean-cycle graph consisting only of cycle with n nodes (the left graph in Figure 4), and is weaker in noisy-cycle graphs, where node within the cycle of (n 1)
cycle
Noisy cycle
Figure 4: A clean-cycle graph and noisy-cycle graph.
nodes is linked to an extra node (the right graph in Figure 4). The number of nodes n is fixed to 10.
We provide detailed descriptions of both graph types in Appendix C.
3.2 Empirical analysis
Setting. We consider two scenarios. Scenario I, we aim to validate our first claim. To this end, we leverage (1) the Com-Com dataset, where the training graphs are sampled from Gçem and the unseen graphs are sampled from G.20 and (2) the Cycle-Cycle dataset, where the training graphs sampled from the noisy-cycle graphs and the unseen graph is the clean-cycle graph.

---

In Scenario 2, we aim to validate our second claim. To this end, we leverage (3) the Com-Cycle dataset, where the training graphs are sampled from G7=0.4 and the unseen graphs are sampled from the noisy-cycle graphs, and (4) the Cycle-Com dataset, where the training graphs are sampled from the noisy-cycle graphs and the unseen graphs are sampled from G
For each dataset, we train GAB [22] equipped with GIN [49] as the graph encoder. We use either the (I) binary cross-entropy (BCE) loss or the (2) squared Frobenius-norm (Frobenius) loss, which are formalized in Section 2.2, for the reconstruction loss. We compare the reconstruction losses for the training graphs and unseen graphs. Further details are provided in Appendix D.2.
Note. While we focus on adjacency reconstruction in this section, we provide an analysis of feature- reconstruction methods in Appendix E.I, where the results are consistent with those below.
Empirical results. Scenario 1, for both Com-Com and Cycle-Cycle datasets, reconstruction losses are lower for the graphs with stronger pattern strengths, which are unseen graphs (see Figure 2). That is, all graphs share primary pattern (either node community or cycle) with two different strengths S < S", and GAE trained graphs of pattern strength S reconstructs those of pattern strength S with lower losses, demonstrating our first claim. In Scenario 2, for both Com-Cycle and Cycle-Com datasets, reconstruction losses become lower for the training graphs after some training epochs (see Figure 3). That is, given training graphs with a primary pattern P (either node communities or a eycle), the trained GAE reconstructs graphs with the same pattern P with lower losses than those with a different pattern P', demonstrating our second claim.
3.3 Theoretical analysis
In this subsection, we theoretically analyze the empirical observations in Section 3.2, focusing on the occurrence of reconstruction flip. Informally speaking, we shall show that when GAB trained on graphs with a primary pattern iP of strength S, the following holds:
(A1) Reconstruction losses decrease for graphs with the same P of various strengths.
(A2) Reconstruction losses decrease more rapidly for graphs with the same P of greater strengths.
Setting. For theoretical analysis, we use single-layer linear GAE. Formally, for a given graph G X. the linear GAE reconstructs the given graph's 's adjacency matrix as follows: A = AXW(AXW)2 where W E RR is a learnable weight matrix and n is the number of nodes. We use the squared Frobenius norm as the reconstruction loss C(g. W) A - A We consider Syn-Com graphs Grom (Section 3.1). To formalize the training of linear GAE, we define the expected gradient descent update of W as follows:
W(r, W. 7) W -EG
TaCG W) ow
|
where y>> >> 0 is learning rate and Eg [+]]] takes the expectation over all the graphs G E Goom, We assume graphs of strength 7 are used as the training graphs and graphs of strength 72 are used as the unseen (test) graphs.
Theoretical results. We now present our theoretical results, with proof of each theorem in Ap- pendix A. We first demonstrate that (A1) holds by expectation.
Theorem 1 (Generalization across 7). For any 2 12 and 0 < < 1, there exists >> 0 such that for any < 7 S e and any 0 < T2 S (recall that and 1 are the lower and upper bounds of T, respectively) with the initial weight matrix ( I,..
EglC(G, W(T. w( (1))T
Eglc(G, W ((0)
<
the loss on grophi strength T2 after update
the loss graphs of srenngh before update
Roughly, Theorem 1 states that regardless of the values of ti and 72, updating W with graphs of strength Ti reduces the reconstruction losses for graphs of strength 72- Intuitively, this suggests that GAE learns the primary pattern P, regardless of the strength S (here, 7)) of the training graphs.
Now, we demonstrate that (A2) holds by expectation.
5

---

Density 2
0.0
0.5
1.0 1.5
Reconstruction error (BCE)
(a) Graph G1
(b) Graph G2
(c) Gaussian KDE visualization of error distributions of Gi (bluc) and G2 (red).
Figure 5: A case of Graph-AEs (specifically, GAE (22]) having similar mean reconstruction errors for two dissimilar graphs (specifically, 91 has 0.6622 and G2 has 0.6627), while their error distributions differ significantly.
Theorem 2 (Correlation with r). For any n 2 34 and 0 < S 0.98, there exists e > 0 such that for any < 7 S c and any T1 0.02 S 72 with the initial weight (()) = I,,.
Eg C(G, w( C(G, W(1, w (0) 7)) T
Eg [CG w()) L(g, W(T w() 7))
<
the decrease loss graphs strength T1 (training graphis)
the decrense loss grophs strength 72 graphs)
Roughly, Theorem states that updating W using graphs of pattern strength Ti results in a greater reduction of reconstruction losses for graphs of higher strength 72 > Ti than for the graphs used in W update (i.e., graphs of strength TI). Intuitively, this result suggests that even if GAE is trained on graphs with a primary pattern P of strength S (here, Ti), the trained GAE tends to reconstruct graphs of greater strength S' (here, 72) with smaller losses.
4 Implications in Graph-Level Anomaly Detection
In this section, we investigate the practical implications of our analysis in Section for graph-level anomaly detection (GLAD).. Specifically, we discuss the limitations of existing graph-autoencoder- based GLAD methods and propose an improved approach to using graph reconstruction errors.
4.1 Limitations of existing Graph-AEs in GLAD
Anomalous graphs may have low mean reconstruction errors. As outlined in Section 2.1, many methods for graph-level anomaly detection (GLAD) use graph autoencoders (Graph-AEs), aiming to identify graphs whose characteristics deviate from the majority. Typically, such GLAD methods [33, 38] consider graphs with higher reconstruction losses (i.c. mean (or sum) of reconstruction errors from node pairs and/or nodes) as anomalies. This is based on the intuition that Graph- AEs would struggle reconstruct anomalous graphs that are dissimilar to the majority of training graphs. However, our empirical (Section 3.2) and theoretical (Section 3.3) analyses reveal that Graph-AEs exhibit lower mean reconstruction errors for graphs that are less similar to training graphs. In the context of GLAD, when anomalous graphs have the same primary pattern as training graphs but have stronger strengths, Graph-AFs tend exhibit lower training graphs. Thus, such anomalies tend not to be detected by existing Graph-AE-based GLAD methods, revealing their severe limitations.
reconstruction errors, compared to the
Mean is not all you need. In addition practice, we find that in some cases, dissimilar graphs can have similar mean reconstruction errors. As shown in Figure 5, although the graph G in (a) and the graph G2 in (b) have significantly different numbers of edges, their mean reconstruction errors are similar, making it difficult to distinguish between the two graphs (refer to the caption of Figure 5). On the other hand, Figure 5(c) shows that the reconstruction eтror distributions over individual node pairs 2 of G, (blue distribution) and G2 (red distribution) differ significantly in shape. Other descriptive statistics, such as standard deviation, can effectively distinguish the two graphs in such cases. Thus, incorporating additional statistical measures beyond the mean is beneficial for Graph-AEs in GLAD.
An example distribution the distribution of Ai, log A (1 As,) log (1 Asz), Vi,j [n].

---

4.2 Enhancing the use of reconstruction errors
Based on the implications discussed in Section 4. 1, we argue that a graph 's reconstruction errors aggregated in various way' can provide features that effectively distinguish anomalous graphs from normal graphs. We provide detailed descriptions of this claim below.
Reconstruction errors serve as good features for GLAD. Consider the following scenarios where Graph-AEs are trained graphs sharing pattern P of strength S. First, for an unseen graph of pattern P with higher strength S' > S, Graph-AEs tend to return lower mean reconstruction errors compared to those of the training graphs (Figure 2). Second, for an unseen graph of different pattern p' + P. Graph-AEs tend to give higher mean reconstruction error than those of the training graphs (Figure 3). In both cases, the error distributions of anomalous graphs differ from those of normal graphs, serving as effective features for distinguishing them.
Using multifaceted summaries of errors is important for GLAD. In practice, need fixed-size representation of the error distribution to be used with anomaly classifiers, which generally require fixed-size input vector. To achieve this, propose using various summary statisties (e.g., mean and standard deviation) to represent the given error distribution. Specifically, rather than relying on a single statistic, we use multifaceted summaries that capture various aspects of the error distributions. This is because distinct етгог distributions may share certain similar summary statistics, as shown in Figure 5. Therefore, multifaceted summaries of the error distribution can an effective feature vector for distinguishing anomalous graphs from normal graphs
5 Proposed Method: MUSE
Based on the discussions provided Section 4.2, we present MUSE (Multifacted Summarization of Reconstruction Errors), simple yet effective graph-level anomaly detection (GLAD) method. MUSE aggregates graph's 's reconstruction emrors into multiple summary statistics and uses a vector of these aggregated errors the graph's 's representation for GLAD. We describe how train the reconstruction model in Section 5.1 and how we obtain the error representation (i.e., a multifaceted summary of reconstruction errors) in Section 5.2.
5.1 Step 1: Training reconstruction model
We first train MUSE to reconstruct graphs in training data. Step is composed of three parts: (1) augmentation, (2) encoding/decoding, and (3) reconstruction loss minimization. For input graph g = (X, A), MUSE first augments the input graph by randomly dropping some edges, mitigating potential overfitting problems. Specifically, MUSE randomly samples [p|ε]] edges from & for some 0 S < 1. Let ε denote the set of sampled edges. We mask the corresponding entries in A by setting them to zero to generate the augmented adjacency matrix A' E {0, 10 (0,1]MMxx)) xP (i.e., A = {U,, 0y} E 8", otherwise A!. = A Vi.j j E [[V]].
MUSE then encodes the augmented graph G' = (X,A') ) to obtain node embeddings Z E R Vi by using a graph neural network (GNN) encoder fe (i.c., Z = fe [X, A')). Subsequently, MUSE decodes the node embeddings Z to obtain reconstructed node features X E R [V]xd and reconstructed adjacency matrix A E (0, 1)l For node feature reconstruction, MUSE uses node feature decoder gv d + IRd (i.e., X go (Z)). Similarly, for adjacency matrix reconstruction, MUSE uses an adjacency matrix decoder h&s RRdd' + Rdd and the inner product of its output (i.e., A of (Z'Z"T") where a is a sigmoid function and Z' = (Z)).
Lastly, for training, we leverage reconstruction losses regarding the node features and the adjacency matrix. For node feature reconstruction, we use the sosine-similarity loss as in GraphMAE [15]. Formally, the loss is defined as follows:
M Σ
(9
where ||:112 is the fo-no
V
|X lla |X,,,
For adjacency-matrix reconstruction, we use the binary cross-entropy (BCE) loss as in GAE [22]. Since real-world graphs are often sparse (i.c., the adjacency matrix contains significantly more zero
7

---

entries than ones), we weight the loss terms associated with non-zero entries to stabilize model training the presence of this imbalance. Formally, the loss is defined follows:
II
(A(9) = |
WAi, log Ai, + -i,,) log (1 A..)),
(3)
I=1
2 E د A.
where w
1)t and scale hyperparameter. Then, the total reconstruction
loss L(g) is defined as the mean of (x(g) (Eq. (2)) and LA (9) (Eq. (3)) (ie., L(G) (9x (9)))) For set of training graphs G (91.... 9K), we update the parameters (i.e., 8 4,
and Φ) by using gradient descent aiming minimize K LiE(K] ((G.).
5.2 Step 2: Generating error representation
After training the reconstruction model, we represent each graph using its reconstruction errors, specifically those from all node pairs and/or nodes. Consider obtaining the reconstruction errors for graph G = (X, A) with the trained reconstruction model (i.e., fo. 9e, and ha)) To this end, we first obtain reconstructed features X and reconstructed adjacency matrix Á by using the encoding and decoding scheme described in Section 5.1. Note that we do not perform augmentation for Step (i.e., the original graph (X, A) the input of the encoder fe).
After that, we obtain nederfeature reconstruction errors Lx(g fa, Iv. ha) on each node and adjacency-matrix reconstruction errors LA (9 Se, Io. h&) on each node pair. Formally,
X
Lx (9) = Lx for Ieb ho) =
R and
(4)
|X,,ll2 (XI:Il2J
LA(9)= = (9 for Fe. h4) = [As., log As, (1 A.,) log (1 A.J)) E RI (5)
I Lastly, based the motivation described in Section 4, aggregate reconstruction errors (i.e., "summarize" vectors into scalars) using T different aggregation functions Agg, 's as follows:
Err(g) = [Agg: (Lx Age, (9),
Agg (LA ... Age ( E ER"..
(6)
different aggregations (0)
different aggregations of (G)
Any aggregation functions that provides a representative summary of Lx and LA (9) are applica- ble, such as mean and standard deviation. As result, represent graph G as a 27 271-dimensional vector Er)(g) (Eq. (6)), which we refer to as the final error representation of g. We present a time complexity analysis of MUSE in Appendix F.3.
After obtaining error representations of graphs, we leverage one-class classifiers on these representa- tions to finally perform anomaly detection. Note that Steps and 2 are decoupled from the application of one-class classifiers (i.e., one-class classifier is trained after completing Steps and 2).
Experiments
In this section, we evaluate the effectiveness of MUSE in graph-level anomaly detection (GLAD) by addressing four key research questions.
RQ1. How accurately does MUSE detect anomalous graphs?
RQ2. How robust is MUSE against contamination of the training set?
RQ3, Can the error representations of MUSE distinguish anomalies from normal graphs in the representation space?
RQ4. Are the key components of MUSE essential for its performance?
6.1 Experimental settings
Datasets. Given the absence of benchmark datasets with ground-truth graph-level anomalies, follow- ing existing GLAD studies [39, 32, 33, 55, 34, 38), we use graph classification benchmark datasets

---

Table 1: GLAD performance: Mean and standard deviation of test AUROC values (x 100) in the GLAD task are reported. The best and second-best performances are highlighted in green and yellow. A.R. denotes average ranking. MUSE obtains the best average ranking among 18 methods.
Method
DD
Protein
NCII
AIDS
Reddit
IMDB
MUTAG
DHFR
BZR
ER
AR
methods
DOMINANT-G [6]
64.3 (4.4 55.9 (9.7) 65.5 (6.1) 80.6 (4.0) (5.3 60.8 (6.7) (42) (9.2 (7.2 58.7 (5.5)
10.7
OCGTTL GLocal [34]
(5.5
(8.) 61.2
95.3 (.7) (4.0 (5.8 64.9 (49) 66.5 (9.) 11.3
63.0 (36)
6.9
(6.
(.57 (56 51.2 (1.2) 49.8
58.5
55.1 (44) 54.1 (8.1) 55.8
(167)
54.4
17.0
GLADC [33]
(2.1 50.7 (5.6) (3.) 51. (1.00 52.2
57.7 (5:) (453
(4.1
09.0
52.8 (4.2)
16.8
GLAM [57]
616(52) (5.6 58.1 (19) 93.6 (2.0 (4.)
(3. (3. 57.2
72.6
55.2
9.8
HIMNET [38]
6689 (4.6 64.3 (.2) 6247
6188 (4.) 27,5 (376
(9.0
55.7 (28)
12.3
SIGNET [32)
(93)
56.4 (6.4) 63.1 (4.0) 97.2 (1.8) (4.40
48.2 (4.8) (1.5 40.2
66.6 (9:5)
56.2 (4.3)
10.4
GrapliCLL-1 [53]
(399 60.7 (4.2) 55.8 (3.1) 71.2 (6.61 57.7 (5.5 54.2 (6.)) (23) 57.8 (67) 60.5 (9:3)
55.5 (4.1)
14.2
GAF-1 [22]
(5.7 61.3 (7.0) 62.5 86.2 (1:4) (3.)
63.8
63.2
56.5 (966
68.5 (1377)
60.0
10.3
GraphMAE-1 [15)
(7.3 60.5 (4.9) 53.4 (3:2) 91.8 (5.3) 72.7 67.0 (5.00
62.3 (2.6)
62.2 (9.0)
70.1 (7.6)
52.2 (3.6)
10.6
SSL
GraphCL-2 (53)
(3.0)
59.1 (5.2) 60.3 (4.4) 91.8 (3.5) 77.3 66.3 (5.0)
67.4 (3.3) 59.1 (4.0)
71.9 10.4
67.3 (3.4)
7.2
GAE-2 [23]
(3.2
62.3 (5.0) 62.4 (3.9) 85.8 (1.6)
(5.7)
66.6
67.3 (3:3)
60.8 (5.6)
72.0 (8.8
65.7 (2.0)
7.0
GraphMAAE [155
68.0 61.2
68.3 (3.6) 90.8 (3.6) 75.8
66.7 (5.8)
68.1 (2:4) 61.4
72.8
66.2
5.1
Variants
MCSE w/o Lx
(3.4
75.6 (8.7) 69.2 (3:7) 99.6 (0.5) 72.2
65.8 (5.7)
65.8 (3.1) 60.4 (6.6) 65.6 (19.4) (3.6)
5.8
MUSE w/o LA
61.8 (7.6) 64.7 (20) 63.1 (3:3)
89.3 (2.8)
72.0 (433)
(..
57.0 (3.5) 58.1 (3.1) 68.7 (14.2
60.7 (4.0)
11.0
MCSE w/o AVG
(4.6
68.1 (5.5) 68.0 (2.0)
95.0 (2.)
73.2 (66)
66.2 (6.5)
60.9 (3.) 60.1 (2:4)
66.3 (13.0) 62.0 (3.5)
7.7
MUSE w/o STD
(5.3)
(5.2) 65.2 (3.6) 98.7 (0.5)
70.5 (4.3)
77..7 (3:7)
62.0 (2.4) 62.9 (6.4) 71.3
66.7 (2.4)
5.6
MM
80.5 78.4 (2.2) 71.1 (2.0) 99.7 (0.5)
78.4
69. (3.5) 67.5 (3.4) 63.8 69.5 (12.6)
67.9 (3.6) 2.2
for evaluation. Specifically, we use 10 datasets from diverse domains, such as chemical molecules, bioinformatics, and social networks. Detailed descriptions of the datasets are in Appendix B.
Training and evaluation. Following Qiu et al. [39], for dataset with C' graph classes, we use C' experimental configurations. In each configuration, graphs with one class are treated as normal, while graphs with the other classes considered anomalies. For each configuration, the normal graphs are split into training, validation, and test sets in an 80%//0%//00% ratio. Additionally, 5% of anomalies are sampled for the validation set (only for hyperparameter tuning) and 5% for the test set. We conduct five trials for each configuration, with each trial using different data splits and model initializations. Each model's performance on each dataset is evaluated by averaging the test mean AUROC across all configurations.
Baseline methods and MUSE. We compare MUSE against 13 baseline methods, including 7 GLAD methods [39, 32, 33, 55, 34, 38, 6] and 6 graph self-supervised learning (SSL) methods [15, 22, 53]. Among SSL methods, those with '-1' in their names are one-stage SSL methods that use SSL losses as anomaly scores. Those with '22' are two-stage SSL methods that (1) obtain graph embeddings the models learn via SSL and (2) employ one-class classifier. For aggregation functions of MUSE (Eq. (6)). we use two aggregation functions: mean and standard deviation. Therefore, we represent each graph with 4-dimensional vector, which is formalized in Appendix D.4. All methods use GIN [49] as a graph encoder. All two-stage approaches use an MLP autoencoder as a one-class classifier. Details of two-stage methods and the MLP autoencoder are in Appendix D.3. In addition, we provide further experimental details, including hyperparameter configurations, in Appendix D.
6.2 RQ1. Performance in graph-level anomaly detection
As shown in Table 1, MUSE outperforms all baseline methods in terms of average ranking. Two points stand out. First, in 8 out of 10 datasets, MUSE outperforms all other GLAD methods. Compared to the second-best GLAD method (OCGTL), MUSE achieves up to 16.2% performance gain (in the NCII dataset). Second, in 8 out of 10 datasets, MUSE outperforms all the SSL-based two-stage baselines (GraphCI-22, GAE-2, and GraphMAB-2). Given that they use the same one-class classifier with MUSE this result demonstrates the effectiveness of the proposed error representation (Eq. (6))
6.3 RQ2. Robustness against the training set contamination
In real-world scenarios, training data may also contain anomalous graphs, making the robustness of GLAD methods against training set contamination crucial for their practical effectiveness. To assess this robustness, we inject anomalous graphs into the training set at rates of 10%. 20%, and 30%. 3 As shown in Figure 6, MUSE exhibits the least performance drop, among the three strongest GLAD methods, demonstrating its robustness.
SSpecifically, for training set containing n graphs, sample x (k/100) anomalous graphs and inject.

---

AIDS
IMDB
ER
100.0
MuSE (ours)
70
Test Test AUROC
97.5
655
93.0
00
60
OCGTL (baseline)
60
90.0
GLAM (basellnee
0%
10%
2055
30%
0%
10%
20%
30%
0%
30%
2005
30%
0%
10%
20%
30%
Anomaly injection ratio
Anomaly injection ratio
Anomaly injection ratio
Anomaly injection ratio
Figure Comparison of the three strongest GLAD methods'
robustness against training set
contamination. MUSE undergoes the least performance drop among the three methods.
6.4 RQ3. Error representation visualization
AIDS
00
Reddlt
Protein
We evaluate whether the error repre- sentation offered by MUSE can ef- fectively distinguish graphs of differ- ent classes. We sample half of the graphs belonging to the same class to train MUSE. Then, we visualize the error representations generated by the trained MUSE for the rest half and graphs sampled from another class. As shown in Figure 7, the eтrоr repre- sentations produced by MUSE are dis- tinguishable across different classes.
Trained on clae 0
Trained on dase
Cless 0 grapha
graphi
Figure 7: PCA visualization of MUSE's error representations of graphs. Graphs belonging to different classes are well- separated in the representation space.
6.5
RQ4. Ablation study
Lastly, provide ablation study of MUSE. We aim to justify the two key components of MUSE: (1) the reconstruction errors Lx and LA. and (2) multiple aggregation functions (specifically, mean and standard deviation). To this end, we leverage the following four variants of MUSE:
(V1) MUSE w/o Lx: A variant that only leverages adjacency matrix reconstruction,
(V2) MUSE w/o LA: A variant that only leverages node feature reconstruction,
(V3) MUSE w/o STD: variant that only leverages mean aggregation,
(V4) MUSE w/o AVG: variant that only leverages standard-deviation aggregation.
As shown in Table 1, MUSE with all components outperforms all of its variants in 8 out of 10 datasets, justifying the design choice of MUSE.
7 Discussions
In this work, we report and analyze an intriguing phenomenon, reconstruction flip of graph autoen- coders (Graph-AEs). We investigate the phenomenon theoretically and empirically (Section 3) and further claim their implication in graph-level anomaly detection (GLAD; Section 4). Based on our analysis, we propose novel GLAD method, MUSE (Section 5), and report its superior performance in GLAD via extensive experiments (Section 6). Below, we conclude the paper by discussing some potential limitations of our research, which could be addressed in future work.
More diverse and general primary patterns. our analysis, we focus on the two patterns: community structures and node cycle (Section 3). Although our claims hold for these patterns, wide range of graph patterns remains unexplored in this work. Furthermore, a unified framework that incorporate various graph patterns into a single pattern may exist. Further investigation into these patterns may improve our analysis, leading to new potential applications.
Scalability improvement. Since MUSE reconstructs the entire adjacency matrix of graph (Eq. (3)). its time complexity for reconstruction O(n²). where n the number of nodes in the graph. While this complexity is manageable for many real-world graph-level datasets (refer to Table 2), leveraging MUSE for large-scale graphs can challenging. A simple technique that reconstructs only sampled subset of an adjacency matrix results in a performance drop (refer to Appendix E.5). Therefore, improving the scalability of MUSE while preserving its detection performance a non-trivial task, making it promising direction for future research.
10

---

Acknowledgements. This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. RS-2024-004069855 (90%). This work was supported by Institute of Information & Communications Technology Planning & Evaluation (ITP)) grant funded by the Korea government (MSIT) (No. RS-2019--1190075, Artificial Intelligence Graduate School Program (KAIST)) (10%).
References
[1] K. M. Borgwardt, C. S. Ong. S. Schönauer, S. Vishwanathan, A. J. Smola, and H.-P. Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(1):44--156, 2005,
[2] Z. Chen, Fu, Y.-.. Wang, Ma, W. Liu, and M. Hebert. Image deformation meta-networks for one-shot learning. In CVPR, 2019.
[3] W.-L. Chiang, X. Liu, S. Si, Y. Li, S. Bengio, and C.-J. Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In KDD, 2019.
[4] M. Choe, S. Kim, J. Yoo, and K. Shin. Classification of edge-dependent labels of nodes in hypergraphs. In KDD, 2023.
[5] J. Dai, H. Qi, Y. Xiong, Y. Li, G. Zhang, H. Hu, and Y. Wei. Deformable convolutional networks. In ICCV, 2017.
[6] K. Ding, J. Li, R. Bhanushali, and H. Liu. Deep anomaly detection attributed networks. In SDM, 2019.
[7] D. Dobson and A. Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4);771-788) 2003.
[8] I. J. Farkas, I. Derényi, A.-L. Barabási, and T. Viesek. Spectra of "real-world" graphs: Beyond the semicircle law. Physical Review E, 64(2):026704, 2001.
[9] S. Freitas, Y. Dong, J. Neil, and D. H. Chau, A large-scale database for graph representation learning. In NeurIPS, 2021.
[10] H. Gao and S. Ji. Graph u-nets. In ICML, 2019.
[11] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In ICML, 2017.
[12] M. Girvan and M. E. Newman. Community structure in social and biological networks. Proceedings of the national academy of sciences, 99(12):8221-7826 2002.
[13] Z. Guo, F. Wang. K. Yao, J. Liang, and Z. Wang. Multi-scale variational graph autoencoder for link prediction. In WSDM, 2022.
[14] W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017.
[15] Z. Hou, X. Liu, Y. Cen, Y. Dong, H. Yang, C. Wang, and Tang. Graphmae: Self-supervised masked graph autoencoders. In KDD, 2022.
[16] Z. Hou, Y. He. Y. Cen, X. Liu, Y. Dong, E. Kharlamov, and J. Tang. Graphmae2: A decoding- enhanced masked self-supervised graph learner. www, 2023.
[17] Kazius, R. McGuire, and R. Bursi. Derivation and validation of toxicophores for mutagenicity prediction. Journal of medicinal chemistry, 48(1):312- 2005.
[18] S. Kim, D. Lee, Y. Kim, J. Park, T. Hwang, and K. Shin. Datasets, tasks, and training methods for large-scale hypergraph learning. Data Mining and Knowledge Diseovery, 77(6):221-22544 2023.
[19] S. Kim, S. Kang, F. Bu, S. Y. Lee, J. Yoo, and K. Shin. Hypeboy: Generative self-supervised representation learning hypergraphs. In ICLR, 2024.
[20] S. Kim, S. Y. Lee, Y. Gao, A. Antelmi, M. Polato, and K. Shin. A survey hypergraph neural networks: an in-depth and step-by-step guide. In KDD, 2024.
[21] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
[22] N. Kipf and M. Welling. Variational graph auto-encoders. NeurlPS Worksop of Bayesian Deep Learning, 2016.
11

---

[23] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks In ICLR, 2017.
[24] G. Kollias, V. Kalantzis, T. Idé, A. Lozano, and N. Abe. Directed graph auto-encoders. In AAAI, 2022.
[25] T. Lanciano. F. Bonchi, and A. Gionis. Explainable classification of brain networks via contrast subgraphs. In KDD, 2020.
[26] S. Laue, M. Mitterreiter, and J. Giesen. Computing higher order derivatives of matrix and tensor expressions. In NeurlPS, 2018.
[27] J. Lee, S. Kim, and K. Shin. Slade: Detecting dynamic anomalies in edge streams without labels via self-supervised learning. In KDD, 2024.
[28] S. Y. Lee, F. Bu, J. Yoo, and K. Shin. Towards deep attention in graph neural networks: Problems and remedies. In ICML, 2023.
[29] S. Y. Lee, S. Kim, F. Bu, J. Yoo, J. Tang, and K. Shin. Feature distribution on graph topology mediates the effect of graph convolution: Homophily perspective. In ICML, 2024.
[30] L. Liang, S. Kim, K. Shin, Z. Xu, S. Pan, and Y. Qi. Sign is not a remedy: Multiset-to-muttise message passing for learning on heterophilic graphs. In ICML, 2024.
[31] W. Liu, Chang, B. Ma, S. Shan, and X. Chen. Diversity-measurable anomaly detection. In CVPR, 2023.
[32] Y. Liu, K. Ding, Q. Lu, F. L., Y. Zhang, and S. Pan. Towards self-interpretaable graph-level anomaly detection. In NeurIPS, 2023.
[33] X. Luo, J. Wu, J. Yang, S. Xue, H. Peng, C. Zhou, H. Chen, Z. Li, and Q Z. Sheng. Deep graph level anomaly detection with contrastive learning, Scientific Reports, 12(1):19867, 2022.
[34] R. Ma, G. Pang, L. Chen, and A. den Hengel. Deep graph-level anomaly detection by glocal knowledge distillation. In WSDM, 2022.
[35] X. Ma, J. Wu, J. Yang, and Q. Z. Sheng. Towards graph-level anomaly detection via deep evolutionary mapping. In KDD, 2023.
[36] C. Morris, N. M. Kriege, Bause, K. Kersting, P. Mutzel, and M. Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In Workshop on Graph Representation Learning and Beyond (GRL+), 2020.
[37] M. Neumann, R. Garnett, C. Bauckhage, and K. Kersting, Propagation kernels: efficient graph
kernels from propagated information. Machine learning. 102:209-244 245, 2016.
[38] C. Niu, G. Pang, and L. Chen. Graph-level anomaly detection via hierarchical memory networks In ECML-PKDD, 2023.
[39] C. Qiu, M. Kloft, Mandt, and M. Rudolph. Raising the bar graph-level anomaly detection.
In IJCAI, 2022.
[40] K. Riesen and H. Bunke. lam graph database repository for graph based pattern recognition and machine learning. In Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshop, pages 287-297. Springer, 2008
[41] N. Shervashidze, P. Schweitzer, E. J. Van Leeuwen, K. Mehlhorn, and K. M. Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
[42] J. J. Sutherland, L. A. O' O'brien, and D. F. Weaver. Spline-fitting with a genetic algorithm: method for developing classification structure- activity relationships. Journal of chemical information and computer sciences, 43(6)):906-1915. 2003.
[43] Q. Tan, N. Liu, X. Huang, S.-H. Choi, L. Li, R. Chen, and X. Hu. S2gae: self suff-super graph autoencoders are generalizable learners with graph masking. In WSDM, 2023.
[44] W. Tu. Q. Liao. Zhou, X. Peng. C. Ma, Z. Liu, X. Liu, Z. Cai, and K. He. Rare: Robust masked graph autoencoder. IEEE Transactions on Knowledge and Data Engineering, 36(10): -340-,353, 2024.
[45] Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention networks. In ICLR, 2017.
12

---

[46] H. G. Vogel. Drug discovery and evaluation: pharmacological assays. Springer Science & Business Media, 2002.
[47] N. Wale, I. A. Watson, and G. Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14:347-375, 2008.
[48] Xia, Wu, J. Chen, B. Hu, and S. Z. Li. Simgrace: A simple framework for graph contrastive learning without data augmentation. In WWW, 2022.
[49] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In ICLR, 2019.
[50] X. Yan, H. Cheng, Han, and P. S. Yu. Mining significant graph patterns by leap search. In SIGMOD, 2008.
[51] Yanardag and S. Vishwanathan. Deep graph kemelss In KDD, 2015.
[52] Z. Ying, J. You, Morris, X. Ren, W. Hamilton, and J. Leskovec. Hierarchical graph representation learning with differentiable pooling. In NeurlPS, 2018.
[53] Y. You, T. Chen, Y. Sui, T. Chen, Z. Wang, and Y. Shen. Graph contrastive learning with augmentations. In NeurIPS, 2020.
[54] G. Zhang, Z. Yang, J. Wu, J. Yang. S. Xue, H. Peng, J. Su, C. Zhou, Q. Z. Sheng, L. Akoglu, et al. duul-discriminative graph neural network for imbalanced graph-level anomaly detection. In NeurlPS. 2022.
[55] Z. Zhang and L. Zhao. Unsupervised deep subgraph anomaly detection. In ICDM, 2022.
[56] L. Zhao and L. Akoglu. On using classification datasets to evaluate graph outlier detection: Peculiar observations and new insights. Big Data, 11(3):151-180, 2023.
[57] L. Zhao, S. Sawlani, A. Srinivasan, and L. Akoglu. Graph anomaly detection with unsupervised gnns. In ICDM, 2022.
[58] Y. Zhou, H. Huo, Z. Hou, L. Bu, Mao, Wang. X. Lv, and Bu. Co-embedding of edges and nodes with deep graph convolutional neural networks. Scientific Reports, 13(1):16966, 2023.
13

---

A Proof
In this section, we provide proof of each theorem presented in the paper.
A.1 Proof of Theorem
Theorem 1 (Suspicious generalization across T). For any 12 and 0 < TI S. 1, there exists >> 0 such that for any 0 < I and any 0 < S 1 with the initial weight matrix W Ip.
Eg LC(G, (T1 O m2)
Bylcig, [T2
the graphs strength 72 ofter updute
grophs strength T2 before updote
Proof. Note that the reconstruction loss defined as follows:
A - AXW(AXW)"12-
(7)
AWWA |3. The derivative of Eq. (7) and Here, since X is identity, Eq. (7) is equal L |A its expectation are as follows [26]:
0C
= 2(A -A3),
aW
W=l.
EA
2(E[A - LE[A3) 3))
ow
W=I.
Given n (the total number nodes) and т (the community strength), let N = (the number of nodes in each community) and
1+r (the inner-community edge probability), we have 2
(1) lffi j:
E = (N- -2)0² + +NN - 1)p(1 - + N(N - 1)p(1 - p)?
(N (N-1)(C 1)(N - -2)0² +3N(N pp?
and
B[A
(N 1)(N 2)(N -3 +N 1)(N +)²²+ (N -N- 1)(N-2222
22)p² +NN++NN- -N-11 1)p
+ 2(N 1)(N 2) 2N(N - 1)p(1 pp)
+ + - 1)(N 2)) (NN-0--- pp)
+2N² - 11)p (1) NNN-NN + NNN 1)(1 (p)(1-pp2200)))))00 2 N(N - 1)(1 -P(1- -
+N(N 1)(N 1
(-6+ 11N 6 +
-000---(11---00-- N +3N (1-))
+p(-1 +2 (1)(1((1p))) + - p) - 2(1 -))
(2) If and are in the same group:
E A 1j = (N- (N - 3)p² + + 2N(N 2)p(( -- +2 - p) + N(N 1)p(1 - -p)
= -NN -3)" + N(3N - -)p(1-p)++p+ - 2Np(1 -),
14

---

and
B[A 4
= (N - 2)(N - 3)(N - 4)p + 2) - 3)0² +2(N - 2)(N 3)/² 2(N - -2)p²
+ (N - 2)pp + 2(N - - + +2 - -2)p²
+ + 2)(N - -3)/2 (1)) - 2) p)2 + 2N 1)2 + +(N 2)Nx²(1 - pp²
+ + 2)(N 33) - p)² +2( 2) - p)²
1)(N -2)p p)2
+2N - 11
N(N - 1)( 2)(1 -p)² N(N 2) p)2 +2N(N - 11(11
-2N(L-p)'+NNV) 1)( p1
1)p(1-10
+ 1= - pp)
3(-2+ +
p)9)
+ N + -V(1-p)
(1- 33 p))
(3) if and] are in different groups
B = 2(N - 1)(N 2) - + 2 1)p(1 - p) 101--p) p)s + +(1 (1-p),
+ (N -
-NN- ((1(N-5)p((1-p))) -N- ( -p) +2( 1)p(1111111111111 -pp1pp + (1 p),
and
E[A
(N 1-t-:-1--110000101---------1111-
2)p² -p)
+ (N - 1)(N - 1-11-100 p) (N (W (N
+ (N - I) - 2)p²(1 p) (N 1)) (P(N-2)p(1 -))² DNN 3)
+ (N 1)(N 2)p(1 pp(1-p)²++
2 (N 1)p(1 (o(1-p)²+t +(N +N +NN-11('(p - p)² (N 1)p(1 p)
(N 1) ()p²(11p) + (N 1)²p"(1-p) (N (00-11)2 ()p[11 pp)
(N 1)²p(1
1)(N 2)p(1-p)3 * 11)-p(1p1111 1 p)3 (N 1)p(1 -p)²
(N 1)p(1 - p)² (N 11)(1 2)p(1-p)) +(N 1) -2)p(1 pp)
+ (N 1)²p(1 - +)*+ + (N 1)²p(1 - + (N-1)p(1 -p)² +NN -1)p(1 - -p)
+ (N - 1)² - 2)p(1 pp)² + +NN 1)²p(1 - p) *NN -1)'p(1 1 p)3 + (N - 1)(N - -2)p(1 - p))
+ (N - 1)p(1 - (N - p)²+ 11)(N-))
- 2) -3)p'(1-) (11-p)
+ (N 1)(N - 2)p² (1 (N - 1)((1 - (1p22 (1-p - 1)p(1 - p)
=(- (-1 + N)p(1 4)
where
A (14-
-1))
Hence, the entries in
OC
EA[A* A = 2 EA
OW
w=
have three different values: (1) i and j are equal, (2) a and vú and vy belong to the same group,
and (3) * j and v; and vj belong to the different groups. Thus, we can express [A - as al bP CU, where a, b, R and P and U are defined as:
9) and U = 0 1 0
P 1
(8)
where 1 E NxN and 0 NxN.
15

---

Specifically.
a = 3(N - 2)(N - -3)p² + + - 6)p(1 p)² + +N(N - 11)11 1)(1-p)
== (N - (N - -3)p"((N 1 -)pp - 1) + NN3N 55p((1 - ()) - 2)p 1)
+N(N - 11)( -))=)))(-)))'
= =Nº(1 4p 12p² - 16p" + 8p²) + + 9p 34pp + 52p2 34p²)
+ +N2 - +p 22p² 38p² 18p") 6p 4p)
c= (N - - (1-p)(((NN - -2)²p -N +5) +N 1)(1 1)( - 2)3p - +1)
For any training graphs with 1 - ie. 0.5 <p v 1, we have
For any N 2 4, a > 0,
For any N 2 6, b > 0,
For any N 2 4, c 2.c000 0.
Thus, a, b, c > 0 for any N 2 6 (i.e., n 2 12) hold.
Let W ((,, w be the updated W after step of gradient descent with learning trained on graphs with (and n.). Now, we derive the reconstruction loss on test graphs computed with W Formally, reconstruction loss by using W" is defined as follows:
C = A AW" (AW'AW")T = | - A(W)
(9)
We further simplify (2 as follows:
(W')2 = + 2(, + P2P + Ez + (61 + te,
(10)
where 61 = 7a, 62 = - 74, and 63 = -
To simplify Eq. (10), we use the property that pa NP, U2 = NU, and PU UP = NU. Using these facts, rewrite Eq. (10) as below:
I +L 22, + U U (1I)
where
26 + e
02 26p + Ne² + 2
03 2G + No. 261 2Nc203
Now, by using the derived results, we rewrite the reconstruction loss term Eq. (9) as below:
C =
--
|A-AAL+at+ooPtooPPAA = - -
(12)
where
(APA) = Σ
Aik
k. in the same group
(AUA)
Σ
Ax
k. different groups
(A kg Σ Au
We can decompose the loss by
L = Σ -
-
(1+
- a2 -a3(AA)))))
1.
16

---

Given and j. let x Aij, (A?) (APA);). and w (AUA).). we have
Lij = (x (1 ai -22 -a3w)
= = a1)ry - 20zzzz 20 + (1 +1++0 ,1)
+ + +a1 + 2( a1)aa + 022²² + 202203zw + azw?
Let Lij- = (Aig - (A²) = (x - -.)² By using this notation, we derive the following result:
Lgg - Lis = -2ayry 20gz 20zzw + a1 + +2yy²
+ +111 + 22222 + 2(1 + 01 a033w + a²²² + 2020321 + az3²
We shall show that
E
(Cu L.y]] < 0.
As - 0+, ignoring higher-order terms and keeping the term linear w.r.t, it suffices to show that
Σ
a ZZyl
Ely Ely²)) + [[E[z]]
E(yz]) + c(E[ww) Elgwo)
Note: In the following derivation, iss from test graphs (i.e., p = _22l1) ),
(1) if j
E [ry] =
E [ar]] 0
[rw] =
E [y = (N - 1)p (N- 2
NN(1 - + N(N - 1)(1 - pp) + 2N 1)p(1- -p)
= N2 - + pp)
E[ye] = (N - 1)(N - -2)(N -3)p² + +3(N - 1) 2)p²² +(N- - 1)p
+ N(N 1)2p(1 + - 1)p(1 p)
+ +N(N 1)(N -2)p2
N(N 1)p(1 -p)
+N(N 1)(N 21) 3N(N 1)(1 p)2 +N11 p)
NN 2p + 2p²)+ + (3 4p² 2p²)
+ (N - 4p² + +8p))+(122)) (-p 6p² - 6p²)
E[yw] = 2N - -1) - 22)p22111111
2N(N - 1)p(1 - p)
+ 2NNN - 1))p((1pp)= +NNN - 11)p(1 -p)
- 2pp)) + - -p3) + NN4p2 - -2p opp)
2p²)
Hence,
du = E[zy] Ely²) -N= +N20)) (p 2p²)
d12 = E[rz] - Elyz] = vV(-1+2p--2) 2p²) N (-3 + 2p3)
+ - ( 6p + 6p²)
d1s := E[rw] - =
2p²) + N(-4p² + 2p + 2p²)
(2) Else if' and j are in the same group
17

---

[yy pLly Np 2p -p²) 22p
B [ = pit = 22p(1 2p + 2p") 2N + +p²
Lww] = [ = 2N² (p² -p--pp) +4))4(( -p²
E [yy"] = (N - 2)p² + (N - 2N - -3)p + N(1 D)2 + N(N - 1)(1 p)* + 2N (1))2((11-7 -p)
2Vº(1 - 2p + 2p²)2 + (
- 4p 6p² 5p + 6p' - 22p
Ely=| = (N - 2)(N - 3)(N - 4)p² + + - 2) - -3)p + +(N -2)p"
+ (N - 2)(N 3)p² - - 33)² + (N- 2)p2
+NNN 1) - 2)p2(1 p)² N(N - 2)p²
+N(N 2)(N 3)p² + +N(N 2)p(1-p)
+N(N 1)(N - (1) +NNN (1(1-))4 +2N 1)(1 (1) +N111 p)²
= -Nº - 2p + 2p²)² - 21 5p + 3p²)
+ N22 - 11:3--1pp-1 + 24p² 14pp~16pp) + Np( -
+ 20p²))
E(yw] = 2N - -2) 33pp + 2N(N - (1 + 2N - 22pp² -p)
+ 2NN(N- - -1((N 22)p(1 - + 2N(N -2)p(1-p)* + +NN( - -2)p(1 pp)
(2p 6pp +8 - -4p") -pp))+++000 (- 2p +
1 -2pp 12p") + 4N 8p 8p")
Hence,
d21 == E[ry] - Ely²] = - - 2p -0 10p² + 10p²)) + 2pp - p- 3p²)
d22 == [|æ2] - Ely=l = NN - 2p + 9p
+ +Np(2 12p + 25p² + N p - 2 13p 22p² + 16p")
d2s :- [[ww] Elyw] = 2N(-1
+ - - -
2p
(3) Else if i and j are in different groups
E [xyy (1 -p) = 2(N - 1)p(1 p)²
[[zz] (1 p)][[] 2(N 1))p(1 p)
[[rw] (1 p)E[w] (N -1)3p²(1 p) + N2 p)3
Bly²] 2(N 1)p(1 - p) 2 - -1)(N 2)p2(1 p)2 + +(N (1 p)²
= 2(N 1)p(1 p) + - 1))(2N - -3)p(11- - 2p)²
Elya] = 2(N 1)(N - 2N - 33) (11pp)²=- +2( 1)(N - (1
+ 2(N I)(N 22pp21 21)"(1-p)++2/M - 1)(N - 2)p(1 p)²
+ 1)(N 2)) - 11)(1 -p)
+2(N 1)²(N 2),²(1-p)*+2// +2 - -1)2p(2 p))
_4p2 8p² + +4p")+ +p")) 16p² + 28p² - 14p*)
+ +N(-4p 20p² 32p' + 16p²) 16p²) + 2p 2p 8p² 12p 6p
[yw]
2(N - 1N 2)p' p) 2(N 1)3p² - p))
+ 2(N 1)2(N- 2)p(1 -p)² + 2(N 1 1)3p(1 - p)
+ (N - 1)(N - 2)p(1 - p)3 + (N 11)p(1 - pp)
+ +N - 1)²p(1 p)² + (N - 1)p(1 10--p) p)
= =N 6p² + 8p2 - 4p") + (-4p 15p² 24p² + 13p")
+ N3p - 13p" 23p² 13p²) + (-p 4p² 7p3 + 440
18

---

Hence,
d31 = E[zy] E[y²] = -2 - (-1+ p\p?
da2 == [[ B[y=] =
p)p?
d33 = E/zw]
= - (1=++))( 2N 2p 2p²)
+ + Sp - + 2p -p" + 13p²))
Conclusion.
Recall that c >> 0 for any n 2 12 and 0 < 71 S and we aim to show that
Σ a(Blzy E + [[[[a)] - Blyzl) + c[E[zw] - Elyw]) <
suffices to show that, for any 0.5 < p - 1,
(EEl Eg 1) Σ
(Bazz] Ely=)) S
Σ 1,j
[E] [ow] Elyw]]
S
1.f
with at least one inequality being strict. Since there are
2N pairs of (i such that =j. j.
2N(N - 1) pairs of (i,j) such that * j and and j are in the same group, and
2N2 pairs of (i.j) such that i # and i and j are in different groups,
it is equivalent to showing that
du + (N 1)d2, + Ndy S 0, Vi {1,2,3).
and at least for one value, the inequality is strict.
Indeed,
du + (N - 1)d21 + Ndai = --
12p² - -10p²)
+
+ - 26p") N
6p 17p² -22p" + 16p²)
(p 4p² 2 -p" <0
for any N 2 4;
d12 + (N - 1)d22 + Nd = N2 4p 12p + 16p² - 8pt) + N 56p² + 34p²)
+ N2 - (p-3333 + 77p² 522²) + Np(-1 22p 52p² + 32p")
+ - 8p² + 15p² - 6p <0
for any N 2 3;
d1a + (N - 1)d23 + Ndg3 (N-1 () 12p AN 2p 2p 2p²)
+ Npp11 - 12p 33p²) 22 + - 19p + +29p²) < 0.
for any N 2.
In conclusion, when trained with any 0.5 < Pirain < (i.e., < T. S 1) and Ntrain 2 6 (i.e.,
12), as y approaches 0+ for any 0.5 Ptest I 1 (i.e., 0 < $ 1),
di du + (N 1)d21 + Nd <0
d2 = d12 + (N 1)d22 + Nd < 0
d3 = d1s + (N 1)d2s + Nd $ 0,
completing the proof.
19

---

A.2 Proof of Theorem 2
Theorem (Correlation with 7). For any n 2 34 and 0 < S 0.98. there exists e >> 0 such that In.
for any 0 < 7 S e and any Ti + 0.02 S 72 S with the initial weight W
EG [(S, w()) L(G, W(T,, w 7)) m
Eg (L, w L(G, W(T, W .)) 72
the decrease ervor on graphs of strength Ti (training gruphs)
the decrease in crror on graphs of strength T3
Proof. Following the notations in the proof of Theorem 1 above, regarding the "speed" of gradient,
0d1
41 4 4
(- 66p² + 64p")
0p
+ N 87p+ -000701010ppp) 104p") N 2 72p 80p")
24p
+11 (1- - Sy 27p² -2p2222p7) 24p²)
0d2
1N*(1 2pp) + 2N + 31p 84p² + 68pp)
0p
+ N² 66p + 231p² 208p + N( 44p 156p² + 128p²)
(1 16p + 45p² 24p")
0ds
(-1+2p)) + N3 - 46p - 144p² 116p²)
0p
N (-1 - 135p + 132p²) + (N-1N111 + 2p + 36p² 48p²)
Trained with p'= 1itl and testing with p Zast1 we have
fl.Pp ,)) Mad1 + bd2 + cd2)
Op
1 Eg [())))))) w()) L(9, W(T,. w ,))) 72
(N)
lim
7-0+
7
a positive constant dotermined by N
a(N,p') 0d (N. + b(N Od2(N.p) +c(N, (d...N 0p
Op
Op
= --((-1+ N1 36p² 48p + +
(-1 -1 + + ( 144p² - 116p²) 26p -N(1 14p' -8pp2 + 28 32p -(-1+ 8p +7p" + N(2 11122224-- 72p² 80p')
+NN(-1 - - 135p² + 132p (001-1-~')(1111 - 32, + 4/2 - 2p/ + 2p
+ 16N
64p²) + 4p 6y² + 4p²)
+ +N"(-4+34p =
+ 104
4p'
10p" 12 23 + 4p"1)
- -N(1 -1' + 8p + 16p - (-1 16p - 45p + 24p + 4N (-1 + 2p)²
18p
+ +N(1 (1(1-44p+ 156p² 128p*)
- 2-2 - -1p 84p² + 68p3) + N2 (-1 + 66p - 231 + 208 (- 81 + 4p')
+ +N2 -4p 52p 34p + (1 16p + 8p¹1)
+ N2 - 3p' + 22p 38p 48p
20

---

Given P1 = r and r=t2
2
f(p2,P1, N) - PI,
+ 32p + 4N2 2N2p0 P1 (1- 2p1 + +2p)
-N(1 14p1 - - -2 36p 48p] + 4.4 2p1)
+ - +
135p + 132p
+(-1+ 8p1 -77pp + 24p + N 24p1 + 24p: 72p7
80p)) N6 34p1 + 66p 64p))
+4N*(-1+ 4p1 - 6p} 4p))
+ 34p1 87pp 1 10pp
4pp 4pt)
- -N(1+ 8p1 - 18y] 16p)) 16p: - 45yî + 24p 4N ( + --1+2p1)
+ +N - 44p1 + 156p; -
31p: - 84pî 68p
+ +N2 + 66p) p31p] (
9p1 34pp + 52pp 34pp)
+N - 4p1 + 12p] - 16p + 8p)) - 3p1 + 22p] 38p 48pp))
-(18p} + (N + 4p1 - 10p] + 44p
- -N(1+ 8p1 - 18p 8 16p))) 8p2 27 24p + N22 24p² + 72p3 - 80p2)
24p
+ 34p2 + 66p} - + 4p2 6p2 4p2)
+ + 34p² 87p + 104p2) - (-1 NN P1) + 14p: 26p + +2p2
+4N2pi - 2pp1 + + - 14p- - 28pp
2 +2pp))) 2p2 36p
- -48p + ( (-1+
+ +N3(33 - 46p² + 144p - 116p2) + NN-1 + 26p + (-6p) 4p1)
(-3 9p1 - 34p/ + 52p 34p1)
+N - 4p1 12p] - 16p + 8p1) + +N(2 3p1 + 22p 38p 48p1)) 16pp
-45p + 24p + (- 2p2)
N 44p2 + 156p2 128p3) 3 (-2-
31pp + 68p
(-1 66p2 231p² 208p)))
By analyzing the above equation, we can find that when N 2 17 (i.c., n 2 34), 0.3 < S 0.99 (i.e.. 0 < T1 < 0.98), and P1 + 0.01 < p2 I 1 (i.e. Ti 0.02 S 52 1), the above equation is negative, i.c., f(2. Pl, N)= f(p1, Pl, N) < 0 or equivalently
lim - (1a CCG w()) - L(G, W(T. w T
7-0+ 7
-Kg C(C) w()) L(G, W(7. w .7)))) T3 << 0,
completing the proof.
B
Datasets
In this section, we descrihe the details of the benchmark graph classification datasets utilized in our experiments. For experiments, we use datasets that are preprocessed by Morris et [36]. We provide descriptive statistics of each dataset in Table 2.
The DD dataset [7] is bioinformatics dataset that contains protein graphs. Each graph represents particular protein. Each node represents an individual amino acid. Each edge represents two nodes that satisfy certain spatial proximity. Each node feature represents type of the corresponding node's amino acid type. Each graph binary label represents whether the corresponding compound is an enzyme not.
The Protein dataset [1] a bioinformaties dataset that contains protein graphs. Each graph represents particular protein. Each node represents secondary structure element of protein. Each edge
21

---

Table 2: Descriptive statisties of the utilized graph classification benchmark datasets.
Methods
DD
Protein
NCI1
AIDS
Reddit
IMDB
MUTAG
DHIR
BZR
ER
# of graphs
1,178
1,113
4,110
2,000
2,000
1,000
4,337
756
405
7,697
Avg. [V]
284.32
39.06
29.87
15.69
429.63
19.77
30.32
42.43
35.75
17.58
Avg. [g]
715.66
72.82
32.30
16.20
497.75
96.53
30.77
44.54
38.36
17.94
of features
89
42
14
56
50
# of classes
2
2
2
2
2
2
represents two nodes that are neighbors along the amino acid sequence are top-K neighbors (K=3) at the protein space. Each node feature represents a type of the corresponding node's secondary structure element type. Each graph binary label represents whether the corresponding protein is an enzyme or not.
The NCI1 dataset [47] is a chemical dataset that contains chemical molecular compound graphs. Each graph represents a particular chemical molecular compound. Each node represents an atom. Each edge represents a chemical bond between two atoms. Each node feature represents type of atom (e.g., carbon, and hydrogen). Each graph binary label represents whether the corresponding compound is an anti-cancer chemical or not.
The AIDS dataset [40] is chemical dataset that contains chemical molecular compound graphs. Each graph represents a particular chemical molecular compound. Each node represents an atom. Each edge represents chemical bond between atoms. Each node feature represents type of atom (e.g., carbon, and hydrogen). Each graph binary label represents whether the corresponding compound shows an anti-HIV activity not.
The Reddit dataset [51] is a social-network dataset that contains social network graphs. Among Reddit-Binary Reddit-Multi-5K, and Reddit-Multi- 12K, utilized Reddit-Binane Each graph represents a thread on Reddit. Each node represents a user. Each edge represents a comment between two users. There are available node features, thus, utilize the one-hot encoded degree of the node as its feature, following existing literature in GLAD [39]. Each graph binary label represents whether the corresponding thread is a discussion-based thread
cnrestion-answe--bae
thread.
The IMDB dataset [51] is an actor-ego-network dataset that contains social network graphs. Each graph represents the ego network of particular actor. Each node represents actor. Each edge represents a co-appearance of two actors in (a) movies. There are no available node features, thus, utilize the one-hot encoded degree of the node as its feature, following existing literature in GLAD [39]. Each graph binary label represents whether the corresponding ego-user particularly acts in the romance genre action genre.
The MUTAG (formally, mutagenicity) dataset [17] is a chemical dataset that contains chemical molecular compound graphs. Each graph represents particular chemical molecular compound. Each node represents an atom. Each edge represents chemical bond between two atoms. Each node feature represents type of atom (e.g., carbon, and hydrogen). Each graph binary label represents whether the corresponding compound is mutagenic or not.
The DHFR dataset [42] is chemical dataset that contains chemical molecular compound graphs. Each graph represents a particular chemical molecular compound. Each node represents an atom. Each edge represents a chemical bond between two atoms. Each node feature represents type of atom (c.g., carbon, and hydrogen). Each graph binary label represents whether the corresponding compound works as dihydrofolate reductase inhibitor or not.
The BZR [42] dataset is chemical dataset that contains chemical molecular compound graphs. Each graph represents a particular chemical molecular compound. Each node represents an atom. Each edge represents chemical bond between two atoms. Each node feature represents type of atom (e.g., carbon, and hydrogen). Each graph binary label represents whether the corresponding compound is active against the benzodiazepine receptor.
The ER dataset a chemical dataset that contains chemical molecular compound graphs. Specifically, it contains compounds that are NR-estrogen receptor (ER)-LBD. Each graph represents particular chemical molecular compound. Each node represents an atom. Each edge represents a chemical bond
22

---

between two atoms. Each node feature represents type of atom (e.g., carbon, and hydrogen). Each graph binary label represents whether the corresponding compound has toxicity or not.
The source of the ER dataset is httpp:///trippp nih. www.gooo/ooo//ioo htt.g///ooo///caaleegg/e/eeeeeee
C Formal Expression of Synthetic Datasets
In this section, we formally describe the leveraged synthetic graphs: Syn-Com and Syn-Cycle. We elaborate on how each graph is generated.
C.1 Syn-Com
We formalize the data generation process of Syn-Com. For given even number of nodes > 2. assume two disjoint node communities Va and VA (WLOG, V. = for 1 s i I n/2] and
Vi {u, n + S j I n)). For given community parameter
[0, 1], graph of Syn-Com
(X. A) satisfies the following: Ar, Aj,s b(1, + 1)/2) for (us, E (²) (2).
A.j A₁ b(1, (1 r)/2) for e; E Va, ty Vo. and A₁ 0, Vi [n], where b(1,)) is
Bernoulli sampling with a parameter We let X Ta, where I is a n-by-n identity matrix.
C.2 Syn-Cycle
We formalize the data generation process of Syn-Cycle. For given number of nodes >> 2, we consider a clean-cycle graph G5ve (V.E*) AX,)*) where E- {ur 1/41 [n|} {v1 2n and A is the adjacency matrix that represents E
We also consider
of noisy-cycle graphs (i.e., pan graphs) G constructed by randomly relocat- ing an edge from gi to form a (n 1)-size cycle, (i.e., (X, (v,, tyd U (ex)), (X, fuz, Wai 3x \ {ex) ) E G Vea = {w; ]j} E E", where Uyje is Uj's neighbor except for oz). We let = In. Note that for n nodes, there exist 2n noisy-cycle graphs in Geve and a single clean-cycle graph.
D Experimental Details
In this section, we provide experimental details the conducted experiments in our work.
D.1 Machines
All experiments of this work are performed on a machine with NVIDIA RTX 8000 D6 GPUs (48GB VRAM) and two Intel Xeon Silver 4214R processors.
D.2 Details of empirical analysis
For the Com-Com dataset, sample 500 graphs from G7om, for training graphs and sample 500 graphs from Gçom for unseen graphs.
For the Cycle-Cycle dataset, we sample half of G for training graphs and employ the clean-cycle graph as the unseen graph.
For the Com-Cycle dataset, we sample 500 graphs from G for training graphs and sample half of Geve for unseen graphs.
For the Cycle-Com dataset, we sample half of Geve for training graphs and sample 500 graphs from G7 for unseen graphs.
Training and evaluation We train GAES for 200 epochs. The results are similar for 500 epochs, but we present the 200-epoch results for better visualization since the error lines flatten after 200 epochs. For every 10 epochs of training, we measure the mean reconstruction errors for each graph and report the mean of these values for graphs within the same class.
23

---

D.3 Details of two-stage GLAD methods
We provide an overview of two-stage anomaly detection methods. First, by performing certain pretext tasks, they learn representations of data. Then, upon the obtained representations, they utilize a one- class classifier to detect anomalies. Below, (1) we describe graph representations of utilized GLAD methods, including MUSE, and (2) describe the utilized one-class classifier, an MLP autoencoder.
Note. MUSE two-stage method.
Graph representation. As described Section 5, MUSE obtains a representation each graph with the proposed error representation Eq (6). On the other hand, utilized bascline two-stage approaches, which are GraphCL [53], GAE [23], and GraphMAE [15], obtain graph representations from the graph node embeddings. Specifically, they first train graph neural network encoders with their pretext tasks. Specifically, GraphCL performs graph contrastive learning, GAE performs adjacency matrix reconstruction, and GraphMAE performs node feature reconstruction. After finalizing self- supervised learning, we utilize the trained encoder to obtain embeddings of graphs or nodes. Details of each method are follows:
GraphCL: It learns graph embeddings perform its contrastive learning task. Thus, we directly utilize the graph embeddings representations of graphs.
GAE: only learns node embeddings. Thus, we pool node embeddings by using the elementwise- mean readout function.
GraphMAE: It only learns node embeddings. Thus, we pool node embeddings by using the clementwise-mean readout function.
One-class classifier. In experiments, every two-stage method leverages MLP autoencoder its one-class classifier. In a nutshell, the MLP autoencoder detects anomalies by using the reconstruction loss of graph. We first elaborate on how we train the MLP autoencoder and then describe how the trained MLP autoencoder is leveraged to detect anomalies.
We start with the training of the MLP autoencoder. Formally, for given data representation vector z E R the MLP autoencoder MLPg R + Fd generates a reconstructed representation E Rd (i.e., å MLP; (z)) Then, compute a L2 12-noomm reconstruction loss C follows: L == ||z 2 2||2- We update the parameters of the MLP autoencoder & by using gradient descent to minimize C.
After training the MLP autoencoder MLPg, we detect anomalies by using reconstruction loss as an anomaly score. However, since the scale of each representation dimension significantly varies, the reconstruction loss is often dominated by dimensions with larger scales, overshadowing those with smaller values. To mitigate this undesirable phenomenon, in the anomaly inference step, we L2 scores. Importantly, apply different weights to different dimensions wi E R, Vi e [d] (note that is the dimension of an input vector). Specifically, we utilize the dimensionwise standard deviation of train data's representations, which is defined follows:
leverage simeesionwise-weighhe
1)
2
Wg
D Dtrain
Σ
Zk.t
Deerai
Σ Zr,t
ve [d].
(13)
GrEDeracn
where Z is I-th element i-th graph's representation vector and Dtrain is a set of training graphs. By using the normalization weight of Eq (13), we compute the anomaly score. Formally, the anomaly detection score of Gt. denoted by sT, is defined as follows:
d = exp (-2
t/e
MLP (Zi)e)
2 ))
E [0,
(14)
we
Note that the higher s, indicates the f-th data point is normal.
D.4 Details of MUSE
In this subsection, we provide details of MUSE.
Reconstruction models. As described in Section 6, we use GIN [49] our backbone encoder, which the same as other leveraged GLAD baseline methods. For the node feature decoder and adjacency matrix decoder, we use 2-layer MLP with ReLU activation function.
24

---

Error representation. For aggregation functions of enror representation, we leverage a mean function and standard deviation function. Formally, for A where C. R, mean aggregation function Aggnean" 2 + R and a standard deviation aggregation function Aggata 2 + 122 are defined as follows:
Age (A)
Σ aEA
Aggara (A)
(a Aggnoan (A))2.
(15)
[AT
TAI
aEA
Thus, we represent each graph 9 by using a R vector as follows:
Err (9) [AgEnaan (9)( Aggzra (Lx())), AgEmoan (L) Aggotd (La ER.
(16)
D.5 Hyperparameters and Details of Baselines
For every method, we tune the hyperparameters and choose the hyperparameter configuration that gives the best validation AUROC. We provide details of the search space of each model category and its hyperparameters.
Fixed settings. For all the methods, we fix the dropout probability and weight decay as 0.3 and le 6, respectively. In addition, all the methods are trained with Adam optimizer [21].
One-stage learning- based GLAD methods. We tune the following hyperparameters for one-stage learning-based GLAD methods, which are DOMINANT, OCGTI, GLADC, GLocalKD, GLAM, HIMNET, and SIGNET:
Training learning rate y E (10-3,1011)
Models hidden dimension d' E (16,32, 64, 128, 256}
Number of GNN layers K E {3. 4,
Number of model training epochs {30, 60, -300]
For other hyperparameters, we follow the default configuration provided in their official Github.
Two-stage learning-basee based GLAD methods. We tune the following hyperparameters for two-stage leamiin-based GLAD methods, which are GraphCL, GAE, GraphMAE, and MUSE.
Note. Our proposed method MUSE is also included in this category and tuned hyperparameters according to the below
Pretext task learning rate 7 E 110-3,10-1
Models hidden dimension d' E {16,322 32, 64, 128, 256}
Number of GNN layers K E (3,4,5)
Number of pretext task training epochs L {20, 40, ... ,0000
In addition to these hyperparameters, we also tune the positive weight coefficient for our adjacency matrix reconstruction, which is denoted in Section 5, within (0.0, 1.0, 2.0).
Here, models indicate both the encoder model and decoder model that are utilized perform pretext tasks. Note that as described in Appendix D.3, all two-stage methods utilize MLP autoencoder for their one-class classifier. We tune the hyperparameter the MLP autoencoder as follows:
MLP hidden dimension d' E {3,,, 64, 128}
MI.P learning rate (10-2.10-3 10-1)
We fix the MLP auteoncoder training epochs and the number of MLP layers as 500 and 3, respectively,
Two-stage baselines details. For GraphCL, obtain graph views by randomly dropping 50% of edges and adding Gaussian noise to node features sampled from (0, 0.1) and use a two-layer MLP projection head. For GraphMAE, empirically demonstrated to be more effective than learnable mask in our preliminary study. For GAE, utilize binary cross-entropy loss and two-layer MLP decoder."
mask 50% of node features with the mask, which is
'While the original GAE [22] does not use projection head, we found that projection head enhances the performance of GAE, through our preliminary study.
25

---

Com-Com dataset
Cycle-Cycle dataset
Casine loss
Frobenius loss
Cosine loss
Frobenius loss
4 4x
Unseen graphs
10-3
30-4
xx xx10->
3x10 7.
Training graphs
10-1
100 Epochs
100
100
100 Epochs
200
E
Epochs
Epochs
Figure 8: Reconstruction flip occurs on feature reconstruction method. When Graph-AEs are trained on graphs sharing primary pattern of weaker strength, the trained Graph-AEs give smaller reconstruction losses for graphs having the same pattern of stronger strength (red lines) than those of weaker strength (blue lines).
Com-Cycle dataset
Cycle-Com dataset
10"2
10
Cosine loss
Frobenlus loss
Unseen graphs
10-5
Frobenius
20
Cosine
20-3
20"9
10
Training graphs
10
10
100
200
100
200
100
Epochs
Epochs
Epochs
Epochs
Figure 9:
Reconstruction flip does NOT occur on feature reconstruction method. When Graph-
ABs are trained on graphs sharing primary pattern, the trained Graph-AEs give larger reconstruction for graphs having a different pattern (red lines) than those of the same pattern (blue lines).
E
Additional Experimental Results
E.1 Node feature reconstruction methods
Note that in Section 3, we investigate Graph-AEs that reconstruct the adjacency matrix of given graph. this subsection, we analyze another large branch of Graph-AEs: node feature reconstruction methods [15, 16, 44].
Feature reconstruction model. We first formalize the node feature reconstruction method. Consider a graph G = (X, A), where X E RdV]xd, First, a GNN encoder fo is utilized to generates node embeddings Z E xd (i.e., (X( A) = Z). Then, by using the feature decoder 9s RR Fd the reconstructed node features X RIV) xd are obtained. Lastly, we compute the feature reconstruction loss, which is either (1) squared Frobenius norm loss [38] (i.e., C == || { X or (2) cosine similarity loss [15] (i.e., L [ El 1I )). Parameters of the GNN encoder fe and the node feature decoder 96 updated by gradient descent to minimize L.
Setting. The dataset setting equal that empirical analysis provided in Section 3.2. Regarding the model setting, we utilize 3-layer GIN as the GNN encoder fo and 2-layer MLP as the feature decoder 9a- We utilize either squared Frobenius norm or cosine similarity loss for the reconstruction loss. We train each reconstruction model for 200 epochs.
Results. In a nutshell, in Figure& 8, one can observe that the reconstruction flip occurs, which also observed in GAE. In Scenario 2, shown in Figure 9, one can observe that the reconstruction flip does not occur. Thus, we verify that our findings in Section 3.2 are not only restricted to the adjacency matrix reconstruction methods but also hold for the node feature reconstruction methods.
observe the same results as those of GAE. In Scenario 1, shown
E.2 Experimental results each setting.
We present experimental results in each setting of our main experiment. Specifically, experimental results the case where class graphs are anomalies and class graphs are normal are provided in Table 3. In addition, experimental results for the case where class graphs are anomalies and class 0 graphs are normal are provided in Table Notably, in both cases, MUSE obtains the best average ranking among 18 methods (refer to Table 3 and Table 4).
26

---

Table 3: Average and standard deviation of the test AUROC when graphs belonging to class 0 are anomalies and graphs belonging to class 1 are normal. A.R. denotes the average ranking. MUSE outperforms other GLAD methods in terms of average ranking.
Methods
DD
Protein
NCII
AIDS
Reddit
IMDB
MUTAG
DHIR
BZR
ER
A.R.
DOMINANT [6]
44.5 (5.0) (116) 66.1 (6.0) 71.1 (5.3) 34.8:55) 59.9 (.7) 59.8 (5.7) 49.6
(1.3)
(10.3) 66.8 (4.4) 12.7
OCGTL [39]
77.9 (26) 67.8 (106) 64.1 (4.0) 99.1 (1.5) 75.3 (35) 69.1 (33) 63.1 (6.6)
(3.)
75.2 (1.3) 65.8 (47)
GLecalKD [34]
69.6 62.5 (3.) 45.9
97.5 (0.5) (2. 68.1 (55) (2.) 61.8 (96) 62.8 (128) (50) 11.2
GLADC [33]
(56) 60.5 (2 (4.) 98.0 (0.4) 83.3 (2) 68.6 55.5
(2.0 63.5 (3.0) 39.8 11.2
GLAM [57]
(5.6 62.6 60.7 (19) 94.2 72.2 (45) 6377 (24) 60.6
48.3 (62) 62.1 (82) 66,6 12.6
HIMNET [38]
(072 66.0 (29) 41.1 (5.1) 97.9 (0.5) 72.6 (1.) 68.8 (38) 58.6 60.6 (49)
(7.5 52.5 (34) 10.8
SIGNET [32]
63.7 (9.1) 58.1 (6.0) 62.8 (5.1) 98.1 (2.1) 84.8 (48) 54.3 (4.0) 67.1 (1.5)
18.1
(6.)
56.5 10.3
GraphCT [53]
51.3 (5.0)
66.4 (1.9 44.8 (2.7)) 58.8 (5.3) 45.8 (6.7) 53.6 (1:5)
(6.3 56.5 (79)
(3.2 15.4
GAE-1 [22]
(7.8
76.7 (4.9)
59.0 (18) 99.9 (0.1) 86.3 (2.1) 60.6 (8.2) 55.1 (3.0)
59.0 (11.6)
(884
(0.) 10.3
GraphMAB-1 [15)
(4.9
62.5 (3.5
51.7 (3.7) 90.2 (9.5) 74.0 (3.0) 71.8 (5.9) 62.6
52.3 (92)
(52) (4.4) 11.3
GrahCL-22 [53]
(33)
51.8 (1.8) 62.3 (4.5) 97.2 (0.9) 77.8 (3:4) 70.0 (4.0) 68.8 (2.7) 57.0
72.6 (39)
GAB-2 [22]
(5.1)
52.9 (3.6)
(3.1) 99.3 (0.4) 85.4 (4.) 73.7 (4:2) 68.2 (3.3)
57.3 (4.1) 75.5 (147)) 61.2
GrahM/AF [15]
61.5
52.4
62.1 (4.3) 98.5 83.0 (34) 69.6 (4.0) 67.2 (2:7)
59.3 (2.1) 77.1 (14.) (1.2) 8.3
MUSE wfo
(2.4
(1.6 70.1 (0.8 100.0 (0.0) 83.6 (2.5) (7.9
(7.1) 66.0 (3.3) 62.4 (8.4) 67.3 (152) 65.1 (3.4)
MUSE w/o LA
56.9
61.3 (5.8 63.2
86.4
73.4 (4.6 47.9
56.3 (4:6) (K55) 65.8 (12.9) (3.)
12.9
MUSE w/o AVG
(2.9
70.4 (4.9)
70.1 (0.7) 92.1
82.5 (42) 67.4 (6.4) 63.2 (3.4)
60.6 (7.6) 59.6
65.3 8.4
MUSE w/o STD
74.8 (4.0) (18) 62.9 (2.9) 100.0 (0.1) 84.0 (40) 72.1 (2.8) 64.5 (1.5)
64.1 (611) 64.3 (10.2) 66,2 (2.6)
4.9
MUSE
8110
78.7 (2.2) 72.5 (0.3) 100.0 (0.0) 84.7 (4,4) 69.6 (2.7) 68.1 (3.0) 64.3 (8.0) 68.2 (11.3) 67.6 (4.0) 2.7
Table 4: Average and standard deviation of the test AUROC when graphs belonging to class I are anomalies and graphs belonging to class 0 are normal. A.R. denotes average ranking. MUSE outperforms other GLAD methods in terms of average ranking.
Methods
DD
Protein
NCI1
AIDS
Reddit
IMDB
MUTAG
DHFR
BZR
ER
A.R.
DOMINANT [6]
(4.0 68.3 n. 64.8 (6.1) 90.1 (2.3 61.6 70.2 (2.) 63.6 (53)
50.5 (6:5) 6.7
OCGTL [39]
71.0 74.2 (69) 58.2 (.0) (5.) 62.6
(2.2 66,6 (3.) (3.2
67.3 (2.9) 60.2
9.5
GLocalKD [34]
(5.9 38.8 (136) 57.2
(16 20.5 (.5)
(1.) 54.3 (6.1) 46.3 48.8 (206) 67.8 (3.) 15.8
GLADC [33]
29.5 (.7)) 40.9 0.5) 59.7 (.m 4.7 (1.) 21.1 (.9) 46.7 (69) 51.0
(33)
54.4
62.7 (2.1 15.8
GLAM[57) [57]
(5.0 64.6 a.9, (2. 78.
(6.5 65.3 (.4) 66.1 93 43.7 (.0 8.1
HIMNET [38]
(46) 47.8 8.6) 66.1 (596 38.8
54.8 (43) 564 (2)) 66.6 (2.4
58.9
11.5
SIGNET [32)
64.7 (9.) 54.6 (6.) 63.4 (28) 91.2 71.2
42.1 (56) 67.8 (1.7) 62.2
58.5 (2.7)
55.8
11.1
GraphCL-1 [53]
79.9 (22) 70.0 (6.0) 45,2 (2.3) (7.6 (5.7)
62.5 (5.7) 53.6 (.1) 64.1 64.4 (10.7) 47.7 (4.)) 10.7
GAE-1 [22]
(4.6
45.8 (1.)) 66.0 (2.2
63.2
66.9
71.3 (35) 54.0 (76) 75.5
59.8 9.8
GraphMAF- [15]
63.0
58.5 (6:3) 55.0
93.3 71.3 (1.3)
62.1 (4.0) 62.5 (2.8
72.1 (9.) 77.0 (100)) 39.0
10.2
GraphCLL [53)
73.2
66.3 (8.5) 58.3
86.3
76.8
62.5 (7.1) 66.0 (3.5) 61.2
66.1 (1255) 68.5 (2.8) 9.3
GAF-2 [22]
(1
71.7 (6:4) 60.8 (4.6) 89.0 65.2 (7.3)
59.5 (11.0)
66.3 (1:2)
64.3
68.5
(7.
8.3
GraphMAB-2 [15)
74.4 (5.3) 70.0 (6.1) 74.4 (2.8) (6.3)
68.5 (6.1)
63.8 (7.6) 69.0 (2.3) 63.5 (9.) 68.5 (6.4) 68.1 (3.0)
6.7
MUSE w/o Ex
78.4(5.0) 73.5 (5.7) 68.3 (3.8) 99.3 (0.9) 60.8 (5.4) 65.6
65.5 (2.5) 58.3 (4.8) 63.9 (23.6) 67.4 7.5
MUSE w/o LA
66.6 (8.3) 68.1 (1.3)
63.0 (5.3) 92.1 (2.5) 69.9 (4.9) 65.9 (12.8)
57.7 (2.3) 63.1 (8.5) 71.5 (15.4) 57.7 (4.5)
9.7
MUSE w/o AVG
79.3 (5.1) 65.7 (6.00
65.8 (3.3) 97.8 (2.3) 63.9 (8.9)
64.9 (6.6) 58.6 (4.4) (9.6 (12.5) 73.0 (14.4) 58.6 8.8
MUSE w/o STD
73.7 (6.8) 71.0 (8.)) 67.4 (4.2) 97.3 (0.9) 57.0 (4.5) 69.3 (3:5) 59.5 (3.0) 61.7 (67) 78.2 (227) 67.1 (2:) 7.3
MUSE
(9.9 78.0 (2.1) 69.6 (3.7) 99.3 (1.0) 72.1 (6.9) 68.7 (3.3) 66.9 (3.)) 63.2 (92) 70.8 (13.9) 68.2 (3:2)
3.6
E.3 Experimental results on additional evaluation metries
In this section, we compare the GLAD performance of MUSE against those of two strongest competitors, OCGTL and GLAM. To this end, we leverage two metries: average precision score (AP score) and precision @ K. As shown in Table 5 and Table 6, MUSE outperforms the competitors in 7/10 and 8/10 in terms of AP score and precision @ K. respectively. These results demonstrate the effectiveness of MUSE is not limited to a particular evaluation metric.
E.4 Experimental results on additional ablation study
In this section, we demonstrate the effectiveness of the following two components of MUSE: graph augmentation and cosine-similarity feature reconstruction loss. To this end, we use two variants of MUSE. MUSE w/o Aug. is variant where the input graph augmentation is removed. MUSE w/o Cos. is a variant that uses the Frobenious norm loss for the feature reconstruction loss, instead of the
27

---

Table GLAD performance: Average and standard deviation of test AP score values (x 100) in the GLAD task are reported. The best performances are highlighted in green.
Method
DD
Protein
NCI1
AIDS
Reddit
IMDB
MUTAG
DHFR
BZR
ER
OCGTL [39] 84.9 (3.1) 78.1 (1.8) (3.6 95.3 (3.0) (L.8) 81.0 (2.2) 72.7 (1.9) (4. 88.6 (09) 60.3 (1.1)
GLAM (57]
74.7 (1.3) 71.1 (2.0) 73.6 (9.0) 95.4 (2.4) 83.2 (L.6) 78.7 (3.0) 75.9 (1.5) (3.4 76.9 (1.2 65.0 (0.6)
MUSE
88.1 (1.3) 86.5 (1.3) 81.8 (1.2) 99.7 (0.6) 81.7 (2.0) 88.7 (2.7) 79.6 (1.4) 78.9 (2.8) 79.1 (2.1) 70.1 (0.4)
Table GLAD performance: Average and standard deviation of test Precision @ 10 score values (x 10) in the GLAD task are reported. The best performances are highlighted in green.
Method
DD
Protein NCI1
AIDS
Reddit IMDB MUTAG DHFR BZR
ER
OCGTL [39] 5.2 (0.7) 3.5 (0.7) 4.4 (0.8) 9.8 (0.2) 3.5 (0.6) 3.9 (0.6)
5.1 (1.) 3.4 (0.9) 4.0 (0.6) 5.1 (0.4)
GLAM [57] 5.1 (0.9) 6.0 (0.7) (1.0) (0.4) (0.7) 5.9 (0.8)
4.9 (0.8) 4.1 (0.) 5.5 (0.6) 4.7 (0.5)
MUSE
777 (1.3) (1.)) (1.3) 7.8 (1.3) 10.0 (0.0) 5.9 (1.7) 6.6 (1.6) 8.5 (I.I) 5.2 (1.) 4.8 (1.3) 5.3 (0.9)
cosine similarity loss. Note that MUSE uses both input graph augmentation and cosine similarity loss. As shown in Table 7, MUSE outperforms its variants in 8 out of 10 datasets, demonstrating the effectiveness of our graph augmentation and cosine-similarity loss.
E.5 Experimental results from the scalability analysis
In this section, we study the scalability and effectiveness of GLAD methods in large-scale graphs.
Datasets. We use two large-scale real-world graphs, which are MalNetTiny [9] and OVCAR-8 [50]. Specifically, the MalNetTiny dataset consists of graphs, each containing a large number of nodes and edges. In contrast, the OVCAR-8 dataset consists of a large number of graphs.
Scalable MUSE. Note that MUSE may not be scalable for graphs with large number of nodes, since MUSE reconstructs all the entries of an adjacency matrix, which results in the complexity of O(V))). Thus, present scalable version of MUSE, which we call MUSE- MUSE-Sample samples K number of entries from the adjacency matrix, and reconstructs only the sampled entries. Therefore, the time complexity of computing reconstruction loss becomes
Specifically,
O(VIK)= O(VI), :. K is constant, which is the same across all graphs.
(17)
Experimental results. We compare the (1) GLAD performance and (2) inference runtime of our proposed methods (i.e., MUSE and MUSE-Sample against the two strongest baseline methods: OCGTL and GLAM. Regarding the performance comparison, as shown in Table 8, MUSE and MuSE-Sample outperform the baseline methods in both datasets. Regarding the runtime analysis, as shown in Table 9, MUSE is the second-fastest method among the four methods.
F Further Analysis and Discussion
In this section, we provide our further analyses and discussions.
F1 Reconstruction flip in computer vision
Analogous to our observations of the reconstruction flips in graphs, certain images are more casily reconstructed. For instance, Liu et al. [31] noted that "anomalies with colors close to the background may yield unreliable reconstruction errors". Moreover, in the MNIST dataset, a reconstruction model trained on class-7 images sometimes reconstructs class-4 images better than class-7 images [31].
To mitigate this undesirable phenomenon, Liu al. [31] proposed a deformation- based anomaly detection method. In this method, an input image is first deformed in a way that makes a reconstruction model easy to reconstruct. Here, deformation method that maintains the semantics of the input image is employed [5]. To identify whether an image is an anomaly, they first deform the image and then let a reconstruction model reconstruct it. Their underlying intuition that the deformation model would drastically change the image dissimilar to the majority of the training images, and this would
28

---

Table 7: Additional ablation study: Average and standard deviation of test AUROC values (x 10) in the GLAD task are reported. The best performances are highlighted in green.
Method
DD
Protein
NCII
AIDS
Reddit
IMDB
MUTAG
DHFR
BZR
ER
MUSE w/o Aug.
78.9 (3.0) 77.1 (3.2) 68.8 (2.3) 99.6 (0.1) 74,2 (3.3)
69.1 (3.6) 66.0 (2.3)
64.4 (5.4)
66.4 (12.)
69.9 (3.0)
MUSE w/o Cos.
79.5 (2.4) 72.8 (3.4) 68.4 (3.7) 96.5 (2.8) 72.7 (6.7) 63.3 (2.) 65.1 (3.1)
60.1 (1.1) 59.9 (9.7)
68.3 (2.5)
MUSE
88.5 (2.3) 78.4 (2:2) 71.1 (2.0) 99.7 (0.5) 78.4 (5.7) 69.2 (3.5) 67.5 (3:4) 63.8 (8.6) 67.5 (12.6) 67.9 (3.6)
Table 8: Large-scale graphs GLAD performance:
The average and standard deviation of test AUROC values (x 10) in the GLAD task large-scale graphs are reported. The best performances are highlighted in green.
Method
OCGTL [39]
GLAM [57]
MUSE-Sample
MUSE
MalNetTiny
60.5 (4.3)
56.8 (4.3)
66.0 (2.5)
68.1 (2.7)
OVCAR-8
69.8 (7.7)
66.0 (3.5)
72.2 (8.6)
72.8 (8.2)
make the deformed anomalous image different from its original image. Finally, when the deformed image is reconstructed by the reconstruction model, the reconstructed anomalous image would be significantly different from the original anomalous image, resulting in a large reconstruction error.
While the method is intuitive in computer vision, the extension of the suggested method to the graph domain is non-trivial. First, the graph deformation that maintains semantics is non-trivial. It is hard to know the semanties of graph without sufficient domain knowledge, especially without any external graph labels. Furthermore, naive graph augmentations, such as node dropping and edge perturbation, may harm the semantics of graph [48]. Second, while the deformation techniques widely studied in computer vision [5, 2]. those of a graph is an underexplored region. Therefore, employing an adequate technique for graph deformation is also practically infeasible.
Considering these challenges, we consider that the method proposed in Liu et al. [31] hard to be trivially extended to the graph domain.
F.2
Reconstruction flip in real-world graph datasets
We provide our in de-thh analysis result of reconstruction flip in Section 3 by using the synthetic datasets. In this section, we analyze whether the reconstruction flip phenomena occur in real-world graph datasets.
Setting. We focus the anomaly detection task performance of GAE [22], which reconstructs the adjacency matrix of a given graph. GAE uses reconstruction loss as an anomaly score, where an anomalous graph is likely to have high reconstruction errors. We measure the AUROC score on test graphs, based on the setting described in Section 6.1. Here, the AUROC score lower than 0.5 indicates the corresponding model performs worse than random guessing, implying the reconstruction flip has occurred.
Results. As shown in Table 3, in the protein dataset, GAE [22] tends to perform worse than random guessing (spec., average AUROC is 0.458), which indicates that the reconstruction flip occurs. Thus, demonstrate that the reconstruction flip is not limited to synthetic scenarios but also occurs in real-world graph datasets.
F33 Complexity analysis of MUSE
In this section, we provide time complexity analysis for the forward pass of MUSE, concerning the size of graph (i.e., number of nodes [V] and edges [E]).
Encoding, We first encode a graph G = (X E xl
xd A E {0, M with a GNN encoder. The
time complexity of encoding g with L Layer GCN [23] is dl L|E d) [3]. Given that d and L are constants, the complexity is equivalent to ((V|+18))
"Note that the forward pass time complexity of GIN [49] is equivalent to that of GCN concerning graph size. This is because the difference between GCN and GIN lies in the feature transformation, which is independent of the graph size.
29

---

Table Runtime analysis: Average runtime (secs) per each graph of each method on each dataset. Overall, MUSE is the second- festnd-fasted method among the four methods.
Method
DD
Protein
NCI1
AIDS
Roddit
IMDB
MUTAG
DHFR
BZR
ER
MalNecTiny
OVCAR-8
GLAM
0.003
0.002
0.001
0.002
0.005
0.002
0,002
0.003
0.002
0.002
0.01
0.003
[39])][39]
0.007
0.004
MUSE-SSaple
0.006
0.004
0.004
0.904
0.012
0.004
0.004
0.004
0.004
0.004
0.05
0.004
MUSE
Decoding. We decode node embeddings by using node decoder and edge decoder, which MLPs. Since the hidden dimensions and the number layers of ML.s are all constants, the complexity of decoding is equivalent O())).
Reconstruction loss. We compute adjacency matrix reconstruction loss and node feature reconstruc- tion loss. Each loss computation has the time complexity of ((1))²) and respectivel Thus, the overall time complexity of the reconstruction loss computation becomes ((2))²)
Error representation. We utilize average pooling and standard deviation pooling, which both have linear time complexity. Thus, the time complexity is equivalent to (([V12).
Overall. Thus, the time complexity of the forward pass of MUSE is as follows:
(18) While MUSE has quadratic complexity the number of nodes, our task is graph-level task where real-world graphs typically have an affordable number of nodes (as shown in Table 2, the dataset that has the largest average number of nodes has smaller than 430 average number of nodes).
O( + (E1) + O(ID)) + O(IV)) + 0(1) = 0(1V1)).
F44 Broader impacts of work
In this section, we discuss the broader impacts of our research. While our focus lies the graph-level task, similar observations can be found in node-level tasks within various types of graphs, such as dynamic graphs [27], heterophilic graphs [29, 30), and hypergraphs [19, 20, 4, 18]. We anticipate that findings and the proposed MUSE will be widely utilized in applications requiring graph- level anomaly detection, such as drug discovery and brain diagnosis. In addition, as described in Section 2.1, the phenomenon of the reconstruction flip is not limited the graph domain, and is also observed in other domains such as computer vision. To our knowledge, we are the first to utilize summarized reconstruction errors as a representation feature of data. This approach can be directly applied to other fields, such as computer vision.
F.5 Generalized categorization of primary patterns
Expectation. In this work, a primary pattern, we community structure and node cycles. As future direction, more general and formal categorization of graph patterns can be considered. This categorization would enable our analysis (Section to be more systematic and generalized.
Challenge. However, real-world datasets may exhibit a wider variety of patterns, including those related node attributes. For example, in the protein dataset, both normal and anomalous graphs exhibit homophilic patterns (i.e., edges tend to join nodes with the same attribute), with anomalies displaying stronger pattern than normal graphs. This diversity makes the categorization not straightforward. Thus, adequately considering real-world graph patterns would play a crucial role in this categorization.
30

---

G
Checklist
NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We clarify our goal, analyzing reconstruction flip, and provide analysis results
in Section 3. We present a method (Section 5) and demonstrate its superiority (Section 6).
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We provide limitations of the proposed method MUSE in Section 7.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide the full statements for all theorems in Section 3.3 and provide full proofs in Appendix A.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide architectures of MUSE in Section 5, details regarding hyperparam- eters in Appendix D, and model code in atttp://githhi
httpp////ggtauub..c/////ssssrs wwt.w//ww0o/ MUSEE MUSE.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide all the utilized datasets, full code for models, and instructions to run the code in https://gt /ttp/gttthhhthge///g com/kswwo97//LLA _USE.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide the key setting in Section 6, and further details in Appendix D.
7. Experiment Statistical Significance
report Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We describe the number of experimental runs and standard deviation of the performance in Section 6.
8. Experiments Compute Resources
31

---

For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We describe machines utilized for the experiments in Appendix D.I.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http:p::///uuriss... cc wttpcccccccccccccccccccccccccclt cecciiieeeeledleeeess
Answer: [Yes]
Justification: We strictly follow the NeurIPS Code of Ethics, particularly in terms of anonymity that we do not reveal our nationality and institutes, etc.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:
[Yes]
Justification:
We discuss the broader impact of our work in Appendix F.4
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We believe we do not have risks of misusing.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We properly add citations for all the mentioned existing literature or methods.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We do not release any new assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: We do utilize any crowdsourcing human-related tasks.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA].
Justification: We do not utilize any crowdsourcing or human-related tasks.
32


Reviews:
[{"review_id": "Gj2v6Jivmz", "reviewer": "Reviewer_jxne", "summary": "Graph autoencoders aim to learn graph representations by reconstructing them, with a key application in graph-level anomaly detection. GLAD identifies graphs with unusual structures or node features by considering those with high reconstruction errors as anomalies. However, the paper reports counter-examples where this assumption fails, a phenomenon named reconstruction flip. The authors investigate when this assumption holds and its limitations. Based on the conversations, the authors proposed MUSE, a novel method that uses these multifaceted summaries for better anomaly detection. MUSE outperforms 14 methods across 10 datasets, achieving state-of-the-art performance in GLAD.", "questions": "1. Question about the two-stage model architecture (see details above).\n\n2. Performance w.r.t other evaluation metrics.\n\n3. Running time comparison.", "limitations": "The authors have adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ This paper proposes a new method for graph anomaly detection which is from empirical studies and with theoretical analysis.\n\n+ The paper reports an interesting reconstruction flip phenomenon that conflicts with previous assumptions on graph reconstructions in the graph anomaly detection problem. \n\n+ The proposed method is simple and effective in detecting anomalies compared to previous methods using extensive experiments.", "weaknesses": "- The proposed method is two-stage instead of end-to-end, so a straightforward question is how to guarantee that the noises/mistakes from the first stage, i.e., representation learning, will not impact the second classification stage. A follow-up question is what is the impact of each stage in detecting anomalies? \n\n- Only AUROC is used as the evaluation metric. Previous methods, e.g., [37], also used other metrics to verify anomaly detection performance, including Precision, Recall, or F1.\n\n- Although the computational complexity has been analyzed, since the complexity is quadratic to the number of nodes, it will be helpful to understand the efficiency by comparing the running time of the proposed MUSE method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer jxne,\n\nWe 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.\n\n**We provide detailed references in the G6 section of the global rebuttal.**\n\n---\n\n# R1.1 - W1 + Q1 [Role of each stage]\n\n- The impact of each stage in anomaly detection:\n    - **[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.\n    - **[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.\n- The impact of noises/mistakes from the 1st stage on the 2nd stage classification:\n    - **[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.\n        - 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.\n        - 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.\n    - **[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.\n        - 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.\n        - However, the two strongest graph-level anomaly detector baselines [8, 9], which are end-to-end methods, show up to a 10% performance drop.\n\n---\n\n# R1.2 - W2 + Q2 [Other evaluation metrics]\n\nMUSE’s empirical superiority withstands the test of different metrics (AP score and Precision@10).\n\n- **[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.\n\n**[Tables: Results on other metrics]**\n| AP score | DD | Protein | NCI1 | AIDS | Reedit | IMDB | Mutag | DHFR | BZR | ER |\n| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |\n|GLAM|74.7 (1.7)| 71.1 (2.0) | 73.6 (9.0) | 95.4 (2.4) | 83.2 (1.6) | 78.7 (3.0) | 75.9 (1.5) | 75.4 (3.2)|76.9 (1.2)|65.0 (0.6)|\n|OCGTL| 84.9 (3.1) | 78.1 (1.8) | 73.6 (1.6) | 95.3 (3.0) |**88.0 (1.8)**| 81.0 (2.2) | 72.7 (1.9) |**87.6 (4.1)**|**88.6 (0.9)**|60.3 (1.1)|\n|MUSE|**88.1 (1.3)**|**86.5 (1.3)**|**81.8 (1.2)**|**99.7 (0.6)**| 81.7 (2.0) |**81.7 (2.7)**|**79.6 (1.4)**|78.9 (2.8)|79.1 (2.1) |**70.1 (0.4)**|\n\n| Precision@10 |DD|Protein|NCI1|AIDS|Reedit|IMDB|Mutag|DHFR|BZR|ER|\n| --- | --- | --- | --- | ---|---|---|---|--- | --- | --- |\n| GLAM|5.1 (0.9)|6.0 (0.7)|5.1 (1.0)|9.9 (0.4) |**8.4 (0.7)**| 5.9 (0.8) | 4.9 (0.8)|4.1 (0.6) |**5.5 (0.6)**|4.7 (0.5)|\n| OCGTL|5.2 (0.7)|3.5 (0.7)|4.4 (0.8)|9.8 (0.2) |3.5 (0.6)| 3.9 (0.6) | 5.1 (1.2)|3.4 (0.9) |4.0 (0.6)|5.1 (0.4)|\n| MUSE |**7.7 (1.3)**|**7.9 (1.3)**|**7.8 (1.3)**|**10.0 (0.0)**|5.9 (1.7)|**6.6 (1.6)**|**8.5 (1.1)**|**5.2 (1.1)**| 4.8 (1.3) |**5.3 (0.9)**|\n\n---\n\n# R1.3 - W3 + Q3 [Computational complexity]\n\nWe argue that MUSE’s greater complexity does not severely undermine its practical value, evidenced by its acceptable runtime.\n\n- **[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.\n    - **[Large-scale data]** In large-scale real-world graphs, MUSE shows acceptable runtime.\n        - **[Additional datasets]** We additionally used two datasets: MalNetTiny [10] and OVCAR-8 [11]. Graph statistics are provided below.\n        - **[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.\n        - **[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.\n    - **[Comparison with strongest competitors]** MUSE was faster than OCGTL and, although slower, still comparable in speed to GLAM.\n        - **[Why MUSE is faster than OCGTL]** Unlike the ensemble model OCGTL, which uses multiple GNNs, MUSE uses a single GNN, resulting in faster runtime.\n    - **[Anomaly detection performance]** Recall that MUSE outperforms these baselines in 8/10 datasets, demonstrating the accuracy of MUSE.\n\n**[Table: Dataset statistics]**\n\n|| Avg. # of nodes | Avg. # of edges | # of graphs |\n| --- | --- | --- | --- |\n| Largest values among the utilized datasets | 429 | 497 | 7,697 |\n| MalNetTiny | 2,215 | 4,537 | 200 |\n| OVCAR-8 | 26 | 28 | 40,516 |\n\n**[Table: Runtime results (seconds)]**\n\n||DD|Protein|NCI1|AIDS|Reddit|IMDB|Mutag|DHFR|BZR|ER|MalNetTiny | OVCAR-8 | Forward pass complexity |\n| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |\n| GLAM | 0.003 | 0.002 | 0.002 | 0.002 | 0.005 | 0.002 | 0.002 | 0.003 | 0.002 | 0.002 | 0.012 | 0.003 | $O(n+m)$ |\n| OCGTL | 0.005 | 0.004 | 0.004 | 0.004 | 0.007 | 0.004 | 0.004 | 0.004 | 0.004 | 0.004 | 0.015 | 0.006 | $O(n+m)$ |\n| Ours(MUSE) | 0.005 | 0.003 | 0.003 | 0.003 | 0.007 | 0.003 | 0.003 | 0.004 | 0.003 | 0.003 | 0.036 | 0.004 | $O(n^{2})$ |\n\n*$n$ and $m$ denote the number of nodes and edges, respectively.*", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DedmH3zT2t", "reviewer": "Reviewer_EQox", "summary": "The authors propose a novel approach to enhance feature representation by leveraging multifaceted summaries beyond the mere average of reconstruction errors, addressing a limitation prevalent in current reconstruction-based methods. This motivation is timely and relevant, aiming to enrich the feature space for improved anomaly detection capabilities. The experimental setup is comprehensive, and the theoretical framework is solid; however, these two parts are somewhat disjointed.", "questions": "1. What's the connection between the analysis and the method? Is the purpose of the analysis just to prove that the average reconstruction error is not enough to detect anomalies? Does the analysis provide some insights on how to solve this issue?\n\n2. What are the primary patterns for anomaly and normal graphs in ten datasets?", "limitations": "The authors have included the limitation and broader impact section.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Reconstruction Flip Phenomenon**: The illustration of the reconstruction flip in Figure 3 is particularly interesting, offering new insights into the behavior of reconstruction-based models under varying conditions.\n\n**Enlightening Visualization in Figure 5**: This figure effectively demonstrates the inadequacy of relying solely on the average reconstruction error, highlighting cases where two distributions may have identical averages yet exhibit completely different characteristics. Such visualizations are crucial for understanding the nuances of reconstruction-based methods and their limitations.\n\n**Robust Experiments and Theoretical Foundation**: The experimental setup is comprehensive, and the theoretical framework is solid.", "weaknesses": "**Disjointed Analysis and Methodology Presentation**: There is a noticeable disconnect between the insightful analysis presented in Section 3 and the methodology described in Section 5. While the former provides a deep dive into the limitations of current approaches, the latter fails to directly reflect or build upon these findings. It is recommended that the authors integrate the analytical insights more coherently into the development of their method, ensuring a seamless flow of ideas from problem identification to solution proposal.\n\n**Characterization of Primary Patterns in Datasets**: The paper utilizes ten datasets, but lacks a detailed exploration of the **primary patterns** that characterize these datasets. Specifically, is it possible that so-called primary patterns are indeed distinct across anomaly and normal graphs? Including an analysis of these patterns would enhance the necessity and the effectiveness of the proposed approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer EQox,\n\nWe 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.\n\n**We provide detailed references in the G6 section of the global rebuttal.**\n\n---\n\n# R2.1 - W1 + Q1 [Gap between analysis and method]\n\nWe 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.\n\nThe central motivation behind MUSE is three-fold:\n\n- **[M1]** Error distribution serves as a good (i.e., distinguishable) representation for graph-level anomaly detection;\n    - 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.\n    - **{*Fig. 5*}** further buttresses this idea.\n- **[M2]** A naïve use of error distribution, however, can lead to ineffective graph-level anomaly detection;\n    - 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.\n- **[M3]** Using diverse aspects of error distribution can lead to effective graph-level anomaly detection.\n    - **{*Fig. 5*}** exemplifies a case where the shape of error distributions helps distinguish two graphs with similar mean reconstruction errors.\n- **[Proposed method: MUSE]** Motivated by [M1,2,3], MUSE represents each graph by using the ***multifaceted summaries of its reconstruction errors***.\n    - 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**).\n\n**[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.\n\n---\n\n# R2.2 - W2 + Q2 [Real-world dataset analysis]\n\nThank you for your suggestion. We will include the below analysis in our revised manuscript. \n\n- **[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.\n- **[Case 1]** Anomalous graphs have distinct primary patterns $P$ from normal graphs.\n    - **[Dataset analysis]** The mutagenicity dataset [13] belongs to this case.\n        - **[Pattern 1]** Anomalies tend to contain NH2 and/or NO2 compounds.\n        - **[Pattern 2]** Normal graphs tend to lack such compounds.\n    - **[Empirical results]** In line with our analysis, the reconstruction flip does not occur, as shown in Table 3.\n        - 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.\n- **[Case 2]** Anomalous graphs have similar primary patterns $P$ to normal graphs but with different strengths.\n    - **[Dataset analysis]** The protein dataset [12] belongs to this case.\n        - **[Shared pattern]** In all the proteins, the same type of amino acids (nodes) tend to be joined by edges.\n        - **[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.\n    - **[Empirical results]** In line with our analysis, the reconstruction flip occurs, as shown in Table 4 of our manuscript.\n        - 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.\n        - In contrast, our method MUSE performs significantly better than random guessing, outperforming all the baseline methods. Specifically, MUSE shows a 0.78 test AUROC.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m5ger2maZW", "reviewer": "Reviewer_SHGf", "summary": "This paper introduces a new GLAD method. The authors identify and analyze a phenomenon termed \"reconstruction flip\", where Graph-AEs sometimes reconstruct unseen graphs (with certain patterns more accurately than training graphs) better than the training graphs themselves. Based on this analysis, the authors propose MUSE (Multifacted Summarization of Reconstruction Errors), which leverages multifaceted summaries of reconstruction errors to enhance anomaly detection performance. MUSE has been shown to outperform existing methods in various datasets.", "questions": "Please refer to the weaknesses.", "limitations": "This paper does not have any potential negative societal impact.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. This paper is well-organized, and identifying the reconstruction flip phenomenon is novel and provides new insights into the existing GLAD methods.\n\n2. This paper provides relevant theoretical analysis to elaborate on the reconstruction flip phenomenon.\n\n3. Authors conducted extensive experiments in comparison with several SOTA baselines, and demonstrated the effectiveness of the proposed MUSE. Besides, the code is released for reproducibility.", "weaknesses": "1. The primary contribution of this paper is the introduction of multifaceted summaries of reconstruction errors for anomaly detection. However, the methods employed for error representation and summarization are conventional and do not demonstrate significant innovation. Furthermore, the authors utilize this feature to train a one-class classifier, which is also a traditional two-stage method. Consequently, the originality and novelty of this contribution appear to be rather limited.\n\n2. Another important concern of the reviewer is the theoretical analysis provided in the paper, which primarily demonstrates the existence of the reconstruction flip phenomenon. However, it does not significantly contribute to understanding or improving the anomaly detection capabilities of the proposed method.  The practical relevance of the theoretical findings to the performance improvements in anomaly detection is not convincingly demonstrated.\n\n3. This paper does not evaluate MUSE on large-scale graph benchmarks to demonstrate the feasibility of large-scale applications.\n\n4. There is a lack of analysis of the computational complexity of MUSE compared to other methods. Such an analysis would help establish the practical advantages of the proposed method in real-world scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer SHGf,\n\nWe 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.\n\n**We provide detailed experimental results in the PDF attached in Sec. G7 of global rebuttal, and references in Sec. G6 of global rebuttal**.\n\n---\n# R3.1 - W1 [Novelty]\n\nWe argue that our contribution is novel and valid for 3 reasons:\n\n**[Novel method]** Among graph-level anomaly detectors [5, 6, 7], MUSE has novel and effective representation learning components.\n- **[Feature reconstruction loss]** We are the first to use cosine loss to stabilize learning in graph-level anomaly detectors.\n  - [5] doesn’t reconstruct features, and [6, 7] use the Frobenious norm.\n- **[Data augmentation]** We use graph augmentation to mitigate overfitting.\n  - [5, 6, 7] don’t augment graphs.\n- **[Ablation study]** Performance drops in 8/10 datasets when we skip augmentation or change cosine loss to Frobenious norm, proving their necessity.\n  - **[Result details] Please see Table 1 of the attached PDF**.\n\n**[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.\n- **[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.\n\n**[Other reviewers]** We kindly suggest the reviewer to consider other reviewers’ evaluation\n- **[jxne]** “authors proposed MUSE, a **novel** method”\n- **[EQox]** “authors propose a **novel** approach”\n- **[H5pG]** “paper proposes a **novel** graph autoencoder model MUSE”\n---\n# R3.2 - W2 [Gap between analysis and method]\n\nWe argue that our theoretical analysis (Sec. 3) well supports the detection capability of MUSE.\n\n**[Motivation]** Three motivations, based on our analysis, explain MUSE’s detection capability.\n- **[M1]** Error distribution serves as a good (i.e., distinguishable) representation for anomaly detection;\n  - *{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.\n- **[M2]** A naïve use of error distribution can be ineffective;\n  - *{claims & Theorems in Sec. 3}* show that simply using higher mean error as an anomaly indicator (like other methods) is ineffective.\n- **[M3]** Using diverse aspects of error distribution enhances detection;\n  - *{Fig. 5}* shows how the shape of error distributions helps distinguish graphs with similar mean errors.\n- **[MUSE]** It represents each graph with the *multifaceted summaries of its reconstruction errors*;\n  - 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**).\n\n**[Practical relevance]** Our additional data analysis supports the practical relevance of our theoretical findings.\n- **[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.\n- **[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}**.\n- **[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.\n---\n# R3.3 - W3 [Large graphs]\n\n**[New large graphs]** We additionally used MalNetTiny [10] and OVCAR-8 [11].\n- Graph statistics are in **Table 2 of the attached PDF.**\n\n**[Detection performance]** In these new large graphs, MUSE outperforms the two strongest baselines, GLAM [9] and OCGTL [8].\n- **[Result details] Please see Table 3 of the attached PDF**\n\n**[Complexity & runtime]** Despite having higher complexity than them, MUSE shows practical runtime in large graphs, which we detail in **Sec. R3.4 below**.\n- **[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**.\n\n---\n# R3.4 - W4 [Complexity]\n\nWe argue that MUSE’s greater complexity does not severely harm its practical value, evidenced by its practical runtime.\n\n**[Runtime analysis]** Despite higher complexity than the two strongest baselines GLAM and OCGTL, MUSE's runtime (from encoding to anomaly score computation) is practical.\n- **[Result details] Please see Table 4 of the attached PDF**\n- **[Large graphs]** MUSE shows practical runtime in large graphs.\n  - **[MalNetTiny]** Handling 200 large graphs (avg. 2215 nodes each) takes 7.2 seconds in total, or 0.036 seconds per graph on average.\n  - **[OVCAR-8]** Handling 40516 graphs (avg. 26 nodes each) takes less than 3 minutes in total, or 0.004 seconds per graph on average.\n- **[Compared to others]** MUSE is faster than OCGTL and, though slower, still comparable in speed to GLAM.\n  - **[Why MUSE is faster than OCGTL]** MUSE uses a single GNN, unlike the ensemble model OCGTL.\n  - **[Accuracy]** Recall that MUSE outperforms them in 8/10 datasets.\n- **[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**).\n  - **[Detail]** It samples entries from an adjacency matrix by the number of edges and reconstructs these entries.\n  - **[Why MUSE-Sample is slower than MUSE]** The sampling time exceeds the time saved in reconstruction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Z86alct2NK", "reviewer": "Reviewer_H5pG", "summary": "This paper investigates the reconstruction flip phenomena in graph autoencoder which may be beneficial for graph-level anomaly detection.\nThen the paper proposes a novel graph autoencoder model MUSE, which simply represents a graph as multifaceted summaries of its reconstruction errors and achieves appreciable improvement.", "questions": "Please see the Weaknesses. Thanks!", "limitations": "The authors mention the greater complexity of MUSE and the challenges of its operation on large-scale graphs.\n\nIn addition, MUSE is limited by the error distribution. However, this limitation may not occur in practice since current real-world datasets generally do not have error distributions similar to those of the majority.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This article takes an in-depth look at the problem of reconstruction loss in graph autoencoder and presents an impressive theoretical analysis.\n\nThe logic of this paper is quite clear. The theoretical analysis is also very rigorous and inspiring. The similarity of the graph structure in the test set to the training set leads to lower reconstruction errors in the test set, which is consistent with common sense.", "weaknesses": "I think the title is a bit long and redundant with information. Please change the title if you can.\n\nThe primary patterns mentioned in line 122 currently contain community structures and circles. Could there be a more systematic definition or categorization based on graph theory? I believe this may be a future direction for the research. As it stands, the community structure can probably be summarized as the case where the degree distribution is uneven, and the circle is the case where the degree is uniformly 2.\n\nUsing AUROC as a metric alone may be biased. This is because, for anomaly detection tasks, there tend to be fewer anomaly labels, which will lead to large differences in precision and recall rates, which in turn will lead to an inflated AUROC. At the very least, the reasons for using AUROC can be explained.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer H5pG\n\nWe 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.\n\n**We provide detailed references in the Global References section of the global rebuttal.**\n\n---\n\n# R4.1 - W1 [Title modification]\n\nThank you for your suggestion regarding our title. We are considering the following modifications:\n\n- ***On the Limitations of Reconstruction-based Graph-Level Anomaly Detection: Analysis and a Simple Solution.***\n- ***Rethinking Reconstruction-based Graph-Level Anomaly Detection: Limitations and a Remedy.***\n\nIf the reviewer has any additional suggestions or ideas regarding the titles, we would be grateful to hear them.\n\n---\n\n# R4.2 - W2 [Future direction]\n\nThank you for your suggestion regarding our future direction.\n\n**[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.\n\n- **[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}**.\n\n**[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.\n\n---\n\n# R4.3 -  W3 [Other metrics]\n\nThank 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).\n\n- **[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.\n    - **AP (Average Precision) score** summarizes the precision-recall curve, which considers both precision and recall.\n    - **Precision@10** measures the number of true anomalies among the top-10 anomaly score data.\n\n**[Tables: Results on other metrics]**\n\n| AP score | DD | Protein | NCI1 | AIDS | Reedit | IMDB | Mutag | DHFR | BZR | ER |\n| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |\n| GLAM | 74.7 (1.7) | 71.1 (2.0) | 73.6 (9.0) | 95.4 (2.4) | 83.2 (1.6) | 78.7 (3.0) | 75.9 (1.5) | 75.4 (3.2) | 76.9 (1.2) | 65.0 (0.6) |\n| OCGTL | 84.9 (3.1) | 78.1 (1.8) | 73.6 (1.6) | 95.3 (3.0) | **88.0 (1.8)** | 81.0 (2.2) | 72.7 (1.9) | **87.6 (4.1)** | **88.6 (0.9)** | 60.3 (1.1) |\n| MUSE | **88.1 (1.3)** | **86.5 (1.3)** | **81.8 (1.2)** | **99.7 (0.6)** | 81.7 (2.0) | **81.7 (2.7)** | **79.6 (1.4)** | 78.9 (2.8) | 79.1 (2.1) | **70.1 (0.4)** |\n\n| Precision@10 | DD | Protein | NCI1 | AIDS | Reedit | IMDB | Mutag | DHFR | BZR | ER |\n| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |\n| GLAM | 5.1(0.9) | 6.0 (0.7) | 5.1 (1.0) | 9.9 (0.4) | **8.4 (0.7)** | 5.9 (0.8) | 4.9 (0.8) | 4.1 (0.6) | **5.5 (0.6)** | 4.7 (0.5) |\n| OCGTL | 5.2 (0.7) | 3.5 (0.7) | 4.4 (0.8) | 9.8 (0.2) | 3.5 (0.6) | 3.9 (0.6) | 5.1 (1.2) | 3.4 (0.9) | 4.0 (0.6) | 5.1 (0.4) |\n| MUSE | **7.7 (1.3)** | **7.9 (1.3)** | **7.8 (1.3)** | **10.0 (0.0)** | 5.9 (1.7) | **6.6 (1.6)** | **8.5 (1.1)** | **5.2 (1.1)** | 4.8 (1.3) | **5.3 (0.9)** |\n\n- **[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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
# General responses

We thank the reviewers for the invaluable time and effort they spent reviewing our paper. Your questions and comments helped us clarify and improve our work, and we will incorporate your comments in our revised manuscript.

In this general response, we provide (1) a summary of the shared concerns among reviewers and (2) our brief responses.

---

# G1. The connection between theoretical analysis and the proposed method MUSE

- **[Implications of our analysis]** As discussed in Sec. 4 of the manuscript, our theoretical analysis regarding the reconstruction flip demonstrates the limitations of the existing reconstruction-based anomaly detectors [5, 6, 7].
- **[Our method]** As discussed in Sec. 4 of the manuscript, our theoretical analysis coherently motivates the proposed method MUSE. Moreover, MUSE overcomes the limitations.
    - **[Key innovation]** MUSE employs multifaceted summaries of graph reconstruction errors to address the theoretically analyzed limitations of the existing reconstruction-based anomaly detectors [5, 6 ,7].
    - **[Experimental results]** Table 4 of the manuscript shows that MUSE outperforms all baselines on the protein dataset [10] while the existing reconstruction-based anomaly detectors [5, 6, 7] perform worse than random guessing due to the reconstruction flip.
- **[Details]** Their details are in **{R2.1 of our response to Reviewer EQox} and {R3.2 of our response to Reviewer SHGf}**.

---

# G2. How realistic is our theoretical analysis

- **[Reconstruction flips in real-world datasets]** Through our additional real-world data analysis, we demonstrated that the reconstruction flip, which is the key concept of our theoretical analysis, indeed occurs in real-world datasets.
- **[Patterns in real-world datasets]** Moreover, the patterns in the datasets affect anomaly-detection performance in a manner consistent with our theoretical analysis.
- **[Details]** Analysis details are in **{R2.2 of our response to Reviewer EQox}**.

---

# G3. The novelty of MUSE

- **[Error representation]** The key novelty of the proposed method MUSE lies in ***error representation***, representing each graph with the multifaceted summaries of the corresponding graph’s reconstruction error.
    - **[Details on novelty]** To our knowledge, we are the first to represent data with multifaceted summaries of its reconstruction errors.
- **[Technical novelty in representation learning]** Moreover, compared to existing reconstruction-based anomaly detection methods [5, 6, 7], we have two novel representation learning techniques (i.e., feature reconstruction loss and graph augmentation). These components are crucial for performance improvement, as demonstrated by our additional experiments.
- **[Details]** Their details are in **{R3.1 of our response to Reviewer SHGf}**.

---

# G4. Evaluation with additional metrics

- **[Experiments]** MUSE outperforms the two strongest graph-level anomaly detector baselines (GLAM [9] and OCGTL [8]) in 7/10 and 8/10 datasets in terms of AP score metric and Precision@K metric, respectively.
- **[Details]** Their details are in **{R1.2 of our response to Reviewer jxne and R4.3 of our response to Reviewer H5pg}**.

---

# G5. Runtime of MUSE

- **[Runtime analysis]** Despite MUSE's relatively higher theoretical complexity compared to the two strongest baselines (GLAM and OCGTL), we claim that MUSE's runtime is acceptable in practical use cases.
    - **[Large scale dataset 1: MalNetTiny [10]]** For 200 large-scale real-world graphs with an average of 2,215 nodes in each, MUSE forward passes them only in 7.2 seconds total, or 0.036 seconds per graph on average.
    - **[Large-scale dataset 2: OCVAR-8 [11]]** Additionally, for 40,516 graphs with an average of 26 nodes in each, MUSE forward passes them in less than 3 minutes total, or 0.004 seconds per graph on average.
    - **[Comparison with others]** Compared to the baselines (OCGTL and GLAM), MUSE was faster than OCGTL and, although slower, still comparable in speed to GLAM.
    - **[Further scalability]** In the rebuttal, we further introduce a variant of MUSE that has the same complexity as the baselines (OCGTL and GLAM), while achieving greater accuracy than them in large-scale graphs.
    - **[Anomaly detection performance]** Recall that MUSE outperforms these baselines in 8/10 datasets, by 0.0631 AUROC on average, demonstrating MUSE is a more accurate detector.
- **[Details]** Their details are in **{R1.3 of our response to Reviewer jxne} and {R3.3 and R3.4 of our response to Reviewer SHGf}**.

---

We believe our additional experiments and clarifications have addressed many of the reviewers’ major concerns. Please let us know if you have any further questions. We deeply appreciate the reviewers’ dedication to the review process.

Sincerely,

Authors of submission 14690.

---

# G6. Global references

[1] Sohn et al, ICLR 2021

[2] Li et al., CVPR 2021

[3] Mirzae et al., ICLR 2022

[4] Reiss and Hosen., AAAI 2023

[5] Kipf et al., NeurIPS 2016

[6] Luo et al., Scientific Reports 2022.

[7] Niu et al., ECML-PKDD 2023.

[8] Qiu et al., IJCAI 2022

[9] Zhao et al., ICDM 2022

[10] Freitas et al., NeurIPS 2021

[11] Yan et al., SIGMOD 2008

[12] Borgwardt et al., Bioinformatics 2005.

[13] Kazius et al., Journal of Medical Chemistry 2005.

# ↓↓↓↓↓ G7. PDF containing experimental results for the reviewer SHGf

Meta-review: This paper investigates reconstruction flip of graph autoencoder and further claims their implication in graph-level anomaly detection. Based on these analysis, the paper proposes MUSE that involves taking multifaceted summaries of reconstruction errors as graph features for GLAD. While reviewers generally appreciate the paper's theoretical analysis and experimental validations, concerns were raised about the method's novelty and disjointed analysis and methodology presentation which the authors addressed in their rebuttals. In addition, the authors should also pay attention to the following two issues.

1. The title of the paper is quite hard to read and very long, it would be helpful to future readers of this paper if the authors can generate a shorter and more precise title that is easier to parse.  
2. The main paper has no discussion of limitations of the work, the authors need to add the discussion of limitations in the final version and also take into account the potential limitations raised by reviewers when discuss limitations.

I highly encourage the authors to pay attention to the comments in the final revision.
Decision: Accept (poster)