Optimizing OOD Detection in Molecular Graphs: A Novel Approach with Diffusion Models
Xu Shen Yili Wang Kaixiong Zhou Shirui Pan Xin Wang












Both authors contributed equally to this research.


  Jilin University
 
  Changchun
  China
  xushen23@mails.jlu.edu.cn


[1]

  Jilin University
  
  Changchun
  China
wangyl21@mails.jlu.edu.cn





  Massachusetts Institute of Technology
  
  Cambridge
  USA
kz34@mit.edu




  Griffith University
  
  Goldcoast
  Australia
s.pan@griffith.edu.au


Corresponding author.


  Jilin University
  
  Changchun
  China
xinwang@jlu.edu.cn





























Despite the recent progress of molecular representation learning, its effectiveness is assumed on the close-world assumptions that training and testing graphs are from identical distribution. The open-world test dataset is often mixed with out-of-distribution (OOD) samples, where the deployed models will struggle to make accurate predictions. The misleading estimations of molecules' properties in drug screening or design can result in the tremendous waste of wet-lab resources and delay the discovery of novel therapies. Traditional detection methods need to trade off OOD detection and in-distribution (ID) classification performance since they share the same representation learning model. In this work, we propose to detect OOD molecules by adopting an auxiliary diffusion model-based framework, which compares similarities between input molecules and reconstructed graphs. Due to the generative bias towards reconstructing ID training samples, the similarity scores of OOD molecules will be much lower to facilitate detection. Although it is conceptually simple, extending this vanilla framework to practical detection applications is still limited by two significant challenges. First, the popular similarity metrics based on Euclidian distance fail to consider the complex graph structure. Second, the generative model involving iterative denoising steps is notoriously time-consuming especially when it runs on the enormous pool of drugs. To address these challenges, our research pioneers an approach of Prototypical Graph Reconstruction for Molecular OOd Detection, dubbed as PGR-MOOD. Specifically, PGR-MOOD hinges on three innovations: i) An effective metric to comprehensively quantify the matching degree of input and reconstructed molecules according to their discrete edges and continuous node features; ii) A creative graph generator to construct a list of prototypical graphs that are in line with ID distribution but away from OOD one; iii) An efficient and scalable OOD detector to compare the similarity between test samples and pre-constructed prototypical graphs and omit the generative process on every new molecule. Extensive experiments on ten benchmark datasets and six baselines are conducted to demonstrate our superiority: PGR-MOOD achieves more than 8% of average improvement in terms of detection AUC and AUPR accompanied by the reduced cost of testing time and memory consumption. The
anonymous code is in: https://anonymous.4open.science/r/PGR-MOOD-53B3https://anonymous.4open.science/r/PGR-MOOD-53B3.










<ccs2012>
 <concept>
  <concept_id>00000000.0000000.0000000</concept_id>
  <concept_desc>Do Not Use This Code, Generate the Correct Terms for Your Paper</concept_desc>
  <concept_significance>500</concept_significance>
 </concept>

</ccs2012>


[500]Do Not Use This Code Generate the Correct Terms for Your Paper
[300]Do Not Use This Code Generate the Correct Terms for Your Paper
Do Not Use This Code Generate the Correct Terms for Your Paper
[100]Do Not Use This Code Generate the Correct Terms for Your Paper














Optimizing OOD Detection in Molecular Graphs: A Novel Approach with Diffusion Models
    Xin Wang
    
====================================================================================






§ INTRODUCTION

Molecular representation learning, which transforms molecules into low-dimensional vectors, has emerged as a critical and essential part of many biochemical problems, such as drug property prediction <cit.> and drug design <cit.>. For handling the non-Euclidean molecules, graph neural networks (GNNs) have been widely applied to encode both node features and structural information based on message-passing strategy <cit.>. The embedding vectors of atoms and/or edges are then summarized to represent the underlying molecules and adopted to various downstream tasks <cit.>.








The recent successes of molecular representation learning are often built on the assumption that training and testing graphs are from identical distribution. However, out-of-distribution (OOD) molecular graphs with different scaffolds or sizes, as shown in Fig. <ref>, is unavoidable when the model is deployed in real-world scenarios <cit.>. Taking antibiotics screening as example, the training data consists of drugs inhibiting the growth of Gram-negative pathogens, while the testing data is mixed with antibiotics against Gram-positive ones <cit.>. Because of the different pharmacological mechanisms in treating bacteria, a reliable drug screening model should not only accurately identify more the in-distribution (ID) samples (e.g., Gram-negative), but also detect “unknown” OOD inputs (e.g., Gram-positive) to avoid misleading predictions during inference. As illustrated in Fig. <ref>, a notable decline in GNNs' prediction accuracy is observed with OOD samples. This highlights the significance of OOD detection, which discerns between ID and OOD inputs, allowing the model to adopt appropriate precautions <cit.>.




Prior arts of graph OOD detection can be roughly grouped into two categories. One line of the existing work aims to leverage the original classifier and fine-tune it to improve its detection ability <cit.>. The another line is to redesign the scoring function to indicate ID and OOD cases <cit.>. 

Nevertheless, these methods inevitably require modifications to the original molecular representation learning model, leading to a trade-off between OOD detection and ID prediction <cit.>. 
Recent advancements in computer vision 
have proposed the use of a diffusion model-based reconstruction approach for the unsupervised OOD detection, which typically involves an auxiliary generative model that approximates the ID distribution to reconstruct the input samples during testing phase <cit.>. 

Since the distribution of reconstructed samples is more biased towards ID than OOD, the disparity between original inputs and reconstructed outputs can be used as a judge metric for OOD detection. However, this kind of approach has never been practiced in the field of molecular graphs.




We first design a naive model called GR-MOOD as shown in Fig. <ref>, to verify the feasibility of the reconstruction method for molecular  OOD detection and draw a positive conclusion through experiments. 
However, the inherent complexity of molecular graphs, which are characterized by non-Euclidean structures, poses two significant challenges. 

First, this nature of molecular graphs renders conventional similarity metrics (e.g., Euclidean distance) less effective to quantify the closeness between original and reconstructed graphs.  Meanwhile, the different molecules often undergo distribution shifts that include both structural and feature changes, further complicating the assessment of similarity. This leads to Challenge 1: Identifying an effective metric to evaluate the similarity between the original input and the reconstruction.
More importantly, the diffusion models require hundreds or thousands of sampling steps to denoise from a normal standard distribution towards generating new graphs, which introduces additional complexity. 

Such extensive requirement becomes impractical, especially when performing reconstructing for a large volume of test samples. This leads to Challenge 2: Addressing the additional complexity of diffusion model required for reconstruction. 
Thus we propose a critical research question: 
0.98How can we adopt reconstruction method to effectively and efficiently handle the unique properties of molecular graphs for OOD detection?


In this paper, we introduce a groundbreaking OOD detection model, Prototypical Graph Reconstruction for Molecular OOd Detection (PGR-MOOD for short). 
For Challenge 1, concerning the identification of an effective metric for assessing the similarity between the original input and its reconstruction, 
PGR-MOOD adopts Fused Gromov-Wasserstein (FGW) distance <cit.>, which utilizes both the structural and feature information of molecular graphs to enhance the measurement of their matching degree. 





To efficiently address Challenge 2, PGR-MOOD proposes  to create a series of prototypical graphs that are closer to ID samples and away from OOD ones. We reduce the need of reconstructing every test graph and just compare its similarities with the prepared prototypical graphs. With this procedure, we can extend to the large-scale OOD detection. Our contributions are summarized as follows:

    
  * GR-MOOD Framework: We propose to detect OOD graphs from a novel perspective, i.e., via comparing the original molecules with their reconstructed outputs based on the diffusion model. The technical feasibility and challenges are analyzed empirically for this new framework. 
    

    
  * PGR-MOOD Framework: To overcome the  challenges of reconstruction measurement and generation efficiency, we propose a molecular detection method that contains a prototypical graphs generator and a similarity function based on FGW distance. In the testing phase, one only needs to measure the similarity between the prototypical graphs and the current inputs to identify OOD with lower values.

     
    
    
    
    
    
  * SOTA Experimental Results: We conduct extensive analysis on ten benchmark molecule datasets and compare with six baselines. PGR-MOOD obtains the consistent superiority over other state-of-the-art models, delivering the average improvements of AUC and AUPR by 8.54% and 8.15%, 13.7% reduction on FPR95, and substantial savings in time and memory consumption. 




































	


§ RELATED WORK



 §.§ Graph Neural Networks

Since graph neural networks can use the topological structure and node properties of graphs for representation learning, they have become the most powerful method for processing graph data <cit.>, especially molecular graphs <cit.>. 
GCN <cit.>, the simplest but most efficient method, has been proved to be equivalent to the first-order approximation filter on graphs <cit.> and thus performs well in node classification <cit.> and link prediction <cit.>.
On graph instance-related tasks, GIN <cit.> proves that GNN is as powerful as the 1-WL test and leverages an injective summation operation to increase performance. 



More and more researchers have proposed more representational methods, but they all ignore the performance and trustworthiness issues brought by OOD distribution <cit.>.



 §.§ Graph Generative Models

Graph generative models aim to learn the distribution of the graph data and sample from it to generate novel graphs <cit.>, especially for molecular graphs since it is related to many science issues <cit.>. 
Some graph generation methods are inspired by auto-regressive models, such as VAE-based <cit.> or normalizing flow-based models <cit.>. 
However, they are limited by the high computational cost and inability to model permutation invariance of graph <cit.>. 
Inspired by the diffusion models in computer vision <cit.>, the same insight on graphs has developed in recent years <cit.>. 



Although diffusion models achieve state-of-the-art performance, they still suffer from inefficiencies caused by slow denoising processes <cit.>.



 §.§ OOD Detection on Graphs

Recently, many studies focus on graph OOD detection due to its importance.
GOOD-D is the pioneering work for unsupervised OOD graph detection, which performs hierarchical contrastive learning to capture latent ID patterns and detects OOD graphs based on their semantic inconsistency <cit.>. 
GraphDE determines ID and OOD by inferring the environment variables of the graph generation process <cit.>.
AAGOD aims to learn a  parameterized amplifier matrix to emphasize the key patterns which helpful for graph OOD detection, thereby enlarging the gap between OOD and ID graphs <cit.>. 
Anomaly graph detection can also be seen as a special case of OOD detection, since anomaly graphs with anomaly structures and features can be caused by distribution shifts and many methods have been proposed to solve it <cit.>. 

All of the above methods require redesigning or training well-performing GNNs on the ID datasets and inevitably lead to a trade-off between OOD detection and ID prediction.



§ PRELIMINARIES 



We define an undirected graph G =  ( A, X  ) with n nodes, where 
A ∈ℝ^n× n is adjacency matrix to represent the graph topology, X ∈ℝ^n× d is feature matrix of all nodes with the dimensionality of d. G can also be re-written by Optimal transmission (OT) format <cit.> to represent as a tuple (A,X,μ), where μ∈ℝ^n is a vector of weights modeling the relative importance of the
nodes and we define it as a uniform weight (1_n/n). In addition, we define D_train 
as the training dataset that usually consists of ID graphs, and define D_test as the test dataset, which can be divided into in-distribution subset D^in_test and out of distribution subset D^out_test. 





 
	


 §.§ Out of Distribution Detection 

For OOD detection task, we aim to design a detector g to distinguish whether the input graph G is an OOD sample or not:

    .g(G;τ,J)={[   0 (OOD), if J(G)≤τ,;    1 (ID), if J(G)>τ. ]..


where J denotes a judging function to score the input molecules and τ denotes threshold for identifying the OOD samples.
A desired OOD detector should assign judge scores with the maximum gap between ID and OOD samples.

This target can be described as the following optimization:

    max_J𝔼_G∼ D^in_testJ(G)-𝔼_G∼ D^out_testJ(G).

Supposing the judge score distributions of ID and OOD have significant divergence, we can distinguish them with a simple intermediate threshold. For reconstruction-based OOD detection as shown in Fig. <ref>, the similarity between the input and the output molecules of diffusion model F_M is often adopted as the judge function: 

    J(G)    = sim(F_M(G),G),

where F_M(G) is the reconstructed output and sim(·) is the similarity function. OOD inputs correspond to the lower reconstruction quality and therefore the lower similarity, while the similarity measurement is higher for the ID inputs.



 §.§ Graph Neural Networks

The typical GNNs are based on message passing paradigm. Specifically, the final representation of graph G for a L-layer GNNs is:

    m_v ^(L)   = MP (m_v ^(L-1),{ (m_u^ (L-1)) ,u∈ N ( v  )   } ) ,
    	z_G   =  Pooling({m_v^(L)| v∈ G}),

where m^(0)_v=X_v is raw node feature, N(v) represents a set of neighbor nodes with respect to node v, and MP is the message passing process that aggregates neighborhood features (e.g., sum, mean, or max) and combines them with the local node. GNNs iteratively perform MP to learn the effective node representations and utilize function Pooling to map all the node representations into the graph representations, which is a single vector. 



 §.§ Graph Generative Model


The generative method based on the diffusion model consists of a forward diffusion process and a reverse denoising process. At the forward process, the model progressively adds noise to the original data until a standard normal distribution. At the reverse process, the model learns the score function (i.e., a neural network) to remove the perturbed noise with the same amount of steps <cit.>. 

Given a graph G=(A,X), we can use continuous time t∈[0,T] to index the diffusion trajectory {G_t=(A_t,X_t)  }^T_t=1, such that G_0 is the original input graph and G_T approximately follows the normal distribution. The forward process transforms G_0 to G_T through a stochastic differential equation (SDE):

    dG_t=𝐟_t(G_t)dt+g(t)d𝐰,

where 𝐰 is standard Wiener process <cit.>, 𝐟_t(·): 𝒢→𝒢 is linear drift coefficient, g(t): ℝ→ℝ is a scalar function which represents the diffusion coefficient. 𝐟_t(G_t) and g(t) relate to the amount of noise d𝐰 added to the graph at each infinitesimal step dt. In order to generate graphs that follow the distribution of G_0, we start from G_T and utilize a reverse-time SDE 
for denoising from T to 0:

    dG_t=[𝐟_t(G_t)-g(t)^2 S_θ(G_t,t)]dt+g(t)d𝐰̅,

where S_θ(G_t,t) is score function to estimate the scores of perturbed graphs ∇_G_tlog p_t(G_t) and p_t(G_t) is the marginal distribution under the forward process at time t. In practice, two GNNs are utilized as the score function to denoise both node features and graph structures. 𝐰̅ is a reverse time standard Wiener process. 





§ RECONSTRUCTION OF PROTOTYPICAL GRAPH FOR OOD DETECTION

In this section, we first propose a naive graph reconstruction method, termed as GR-MOOD, to analyze its potential and limitations for molecular graph OOD detection.
Then, we propose a novel approach of PGR-MOOD to reconstruct the prototypical graphs of ID samples for effective and efficient OOD detection.




 §.§ GR-MOOD


Inspired by the generative methods <cit.>, we design a vanilla graph reconstruction model (GR-MOOD) for molecular graph OOD detection. GR-MOOD is pre-trained on a large-scale compound dataset (e.g., QM9 or ZINC) and fine-tuned on D_train. 
Considering input graph G ∈ D_test, 

we utilize GR-MOOD to perturb and reconstruct it via:

    G_o = diffuse(G,θ,T),
    Ĝ = denoise(G_o,θ,T),

where θ is the parameters of GR-MOOD, and T is the iteration numbers. Function diffuse(·) 


applies Eq. (<ref>) to introduce perturbations that transform G into a noised state G_o, while function denoise(·) utilizes Eq. (<ref>) to reverse the process, effectively denoising G_o to generate reconstruction graph Ĝ.













Upon acquiring the reconstruction graph Ĝ, we utilize a GNN well-trained on the ID dataset to encode both the feature and structure information of  G and Ĝ, whose representations are denoted as z and ẑ, respectively. 
The cosine similarity between them is treated as OOD judge score and is defined in Eq. (<ref>):


    sim(G, Ĝ) = z ·ẑ/ z ×ẑ.






To validate GR-MOOD effectiveness, we conduct experiments on two DrugOOD datasets <cit.>.

As shown in Fig. <ref>, the performance of GR-MOOD is comparable (e.g., AUROC and AUPR) or even outperforming (e.g., the smaller score of FPR95 is better) than the SOTA method of GOOD-D <cit.>.



The underlying principle is that since GR-MOOD is trained to  reconstruct graphs that align with the ID distribution, OOD samples, due to their inherent dissimilarity from the ID distribution, will typically undergo poorer reconstruction when  being processed. Such discrepancy is quantified as a lower judge score, which signals the presence of an OOD sample.
This mechanism highlights the critical role of diffusion model based reconstruction method in identifying graphs that do not conform to the expected distribution, thereby providing a quantitative basis for distinguishing between ID and OOD samples.








Limitation of GR-MOOD: Despite the intuitive promise of GR-MOOD, our evaluation reveals the non-negligible
limitations in terms of its time efficiency and reconstruction quality measurement. 

First, the primary constraint of GR-MOOD is due to the inherent structural complexity of molecular graphs. As illustrated in Fig. <ref>, this complexity requires the diffusion model to take an extensive amount of denoising steps to fulfill the reconstruction, improving model performance at the expense of efficiency. Even worse, repeating the generation process for each molecules makes it challenging to scale in the testing phase, which has to screen on a large pool of molecule candidates. Second, another issue pertains to the adequacy of the similarity function employed in our model. As depicted in Fig. <ref>, the reconstruction similarity distributions of ID and OOD samples calculated based on Eq. (<ref>) 
are not significantly different [There are similar sub-structures among the molecular graphs (e.g., functional groups like benzene rings), resulting in close representations of the OOD and ID samples.]. Since graphs embody as non-Euclidean data, the standard metrics such as cosine similarity impedes the ability to accurately capture the nuances of molecular structure and node features among the molecules. This limitation can result in the consequential loss of detection accuracy.






























		
	
	
	

	
 


 §.§ PGR-MOOD


To address the limitations of GR-MOOD, we propose a novel approach based upon diffusion model, PGR-MOOD (Prototypical Graph Reconstruction for Molecular OOD Detection). The innovation of PGR-MOOD has three aspects: A strong similarity function, a prototypical graphs generator, and an efficient and scalable OOD detector. The architecture of PGR-MOOD is shown in Fig. <ref>.



A Strong Similarity Function based on FGW. 
The cosine similarity metric is oriented towards quantifying the angular divergence between two vectors, 
while it is not suitable for non-Euclidean data such as graphs.
In fact, measuring the similarity between graphs is equivalent to calculating the their matching degree, the higher the matching degree, the more similar they are. Fused Gromov-Wasserstein (FGW) distance has been proved particularly advantageous for the measurement between graphs. 


It achieves a balance between the optimal transport (OT) distance with a cost on node features and the Gromov-Wasserstein (GW) distance among the toplogical structures. 




Specifically, FGW 

treats the graph associated with topology and node feature as a probability distribution. It allows for the computation of costs between two distributions with optimal coupling, serving as a distance measure between graphs.

For two graphs represented in OT format, G_1 = (A_1,X_1,μ_1) and G_2 = (A_2,X_2,μ_2), their FGW distance is defined as: 

    FGW_α(G_1,G_2)   =min_Π(μ_1,μ_2)∑_ijkl(α(A_1(i,j)-A_2(k,l))^2
       +(1-α)X_1(i)-X_2(k)_2^2)π_ikπ_jl,

where A_1(i,j) represents the element of the i-th row and j-th column in A_1, X_1(i) represents the ith row vector of X,  α∈ [0,1] is a parameter to balance the structure term and the feature term, Π(μ_1,μ_2)={π∈ R_+^m× ns.t., ∑_i=1^mπ_i,j=μ_2(j),∑_j=1^nπ_i,j=μ_1(i)} is the set of all admissible couplings between μ_1 and μ_2.
FGW(·) metric exhibits optimal performance in directly discerning both structural variances and feature disparities between graphs. 









A Prototypical Graphs Generator. 


The naive diffusion model of GR-MOOD reconstructs graph that favors the distribution of the input samples, instead of following the distribution learned during the training phase. It misleads the detector's judgment on the OOD samples.
To address this challenge, we propose a prototypical graphs generator, which generates prototypical graphs satisfying the following two properties:

192 For any input graph G_in∈ D_in, where D_in represents all ID graphs, the prototypical graph ought to closely resemble the graph G_in.
193 For any input G_out∈ D_out, where D_out represents all OOD graphs, the prototypical graph should exhibit significant deviation from the graph G_out. Consequently, the goal is to generate a prototypical graph G which is close to the ID graphs and far away from the OOD graphs.

To satisfy Property 192, Eq. (<ref>) is utilized as the distance metric, and the loss function ℒ_ID is formulated to guide the denosing process at the generator:

    ℒ_ID = 𝔼_G_in∼ D^in_train[FGW(G_in,G)].














Similarly to comply with Property 193, we introduce loss function ℒ_OOD to enhance the distance between G from OOD samples:

 
    ℒ_OOD =    -𝔼_G_out∼ D^out_train[FGW(G_out,G)].


Note that OOD graphs G_out are unreachable during the training phase, precluding the direct formulation of ℒ_OOD. Consequently, it becomes imperative to synthesize graphs as proxies for the absent OOD samples.
Recalling the pre-trained diffusion model F_M in Eq. (<ref>), it adopts socre function S_θ to generate graph. The parameter weights  of S_θ is given by θ_M={θ_M^(l)}_l=1^L, where θ_M^(l) represent the parameters of the l-th score function. 
We propose to directly perturb parameters θ_M for generating OOD graphs G_out:

    θ_M ={θ_M^(l)(I+α P^(l))}^L_l=1,

where α >0 is perturbation strength, I is identity matrix, and P^(l) is perturbation matrix. 
By perturbing the parameters θ_M, a new score function S_θ(·) is derived. 
Experimental observations (w/o ℒ_OOD of Table <ref>) reveal that S_θ(·) can induce a deviation in the denoising trajectory away from the original data distribution, thereby enabling the diffusion model to generate G_out during the training phase. 
In light of these researches, a composite loss function ℒ_guide is formulated by integrating both ℒ_OOD and ℒ_ID: 


 
    ℒ_guide = ℒ_ID+ℒ_OOD.












It is leveraged to guides the training of Prototypical Graphs Generator F_PG, which has the same architecture and initial parameters θ with F_M, to generate prototypical graph G. The generation of G by F_PG unfolds in two phases:
Firstly, in contrast to generating directly from Gaussian noise, a graph G_0 from D_train is randomly chosen as the start point of generation. We then add T-step noise according to Eq. (<ref>) to get the final noise graph G_T (i.e., G_0 → G_T). 
Secondly, ℒ_guide guides the denoising step of diffusion model to generate prototype graph G:



    dG_t=[𝐟_t(G_t)-g(t)^2 (S_θ(G_t,t)- 
    ∇_G_tℒ_guide(G_t))]dt+g(t)d𝐰,

where t is the indicator of the denoise step and varies from T to 0. 
The prototype graph G generated by the above equation can be viewed as the reconstruction of both ID and OOD graphs, but has better discrimination than the reconstruction generated in GR-MOOD. To further reduce the computation, rather than utilizing the entirety of D_train, a fixed batch-size dataset D_batch is employed for the computation of ℒ_ID. Each D_batch can generate one G, and they are combined  to formulate a list PL={G^(i)}^I_i=1, I=⌈|D_train|/|D_batch|⌉. 







An Efficient and Scalable OOD Detector. 
Diffusion models require significant time and memory resources during the testing phases because they need to generate a reconstructed graph  for each input.


To alleviate this computational burden, PGR-MOOD 


eliminates the necessity of graph reconstruction in the testing phase via preparing the prototypical graphs in the training phase. PGR-MOOD leverages the G within list PL to conduct the similarity measurement with every new test sample. The maximum similarity is employed as the definitive judge score for OOD detection:

    J(G) = max_G∼ PL[sim(G,G_test)],  G_test∈ D_test.

where sim (·) is the similarity function based on the inverse of FGW distance.
















 







 



 
 











 












  








			




 










§ EXPERIMENT



In this section, we verify the effectiveness of PGR-MOOD and GR-MOOD by performing experiments on two graph OOD benchmarks. 









 §.§ Experiment Setup







  §.§.§ Datasets
 

With the increasing attention on OOD detection in the molecular graphs, two benchmarks are proposed, GOOD <cit.> and DrugOOD <cit.>, respectively. These two benchmarks provide the detailed rules to distinguish between ID and OOD. GOOD is built based on the scaffold and size of the molecular graph, and DrugOOD adds an assay on the basis of these two distribution shifts. 

We take six datasets from DrugOOD and four datasets from GOOD as our experimental datasets. Please see Appendix <ref> for details.



  §.§.§ Baselines Methods

To verify the performance of our methods, namely GR-MOOD and PGR-MOOD, we use the GNNs’ Max Softmax Score (MSP) <cit.> as a vanilla baseline and then compare with three SOTA graph OOD detection methods (GOOD-D  <cit.>, AAGOD <cit.>, and GraphDE <cit.>). Meanwhile, two graph anomaly detection methods, namely OCGIN <cit.> and GLocalKD <cit.>, are introduced as the baseline. In addition, as the first molecular graph OOD detection method based on the diffusion model, we also compare the PGR-MOOD with the naive solution GR-MOOD to verify whether its limitations have been solved. Please see Appendix <ref> for details.






  §.§.§ Implementation Details

For our methods, we utilize the diffusion model GDSS <cit.> as the backbone
which achieves stat-of-the-art performance on graph generation. GDSS is pre-trained on the QM9 dataset, which comprises a large collection of organic molecules with 113k samples. Following the setting of GraphDE, we perform 10 random trials and report the average accuracy on the test set, along with 95% confidence intervals. During training, we set α to 0.5 to balance the topological structure and node features  when computing the FGW distance. We set D_batch to 128 and the number of perturbation steps T∈ [1,10] to reduce memory allocation and computation complexity. For all baseline methods, we follow settings reported in their papers. All the experiments are implemented by PyTorch, and run on an NVIDIA TITAN-RTX (24G) GPU.




 §.§ Performance Analysis


Q: Whether PGR-MOOD achieves the best performance on the OOD detection in molecular graphs? Yes, we utilize the new loss function ℒ_guide to guide the diffusion model to generate prototypical graphs that are more representative of all ID samples, and more easily detect OOD samples. 



 
As shown in Table <ref> and Table <ref>, compared with GR-MOOD on six datasets of DrugOOD, PGR-MOOD enhances the average AUC and AUPR by 32.76% and 29.54%, and reduces the average FPR95 by 45.65%. These results demonstrate that the prototypical graphs of PGR-MOOD generated with the FGW similarity function are more suitable for distinguishing the original input graphs in the testing phase.










  To verify the superiority of our method, we compare it with the previous SOTA methods.
As shown in the last row of Table <ref> and Table <ref>, 
our method achieves SOTA results on all datasets. The average improvements against the previous SOTA are 8.54% of AUC and 8.15% of AUPR, and the average reduction on FPR95 is 13.7%.


We attribute these results to the fact that the prototypical graphs generated by PGR-MOOD can enlarge the judge score gap between ID and OOD which satisfies the requirement of optimal OOD detector.





 §.§ Visualization of Score Gap
Q: Whether PGR-MOOD can enlarge the judge score gap between ID and OOD graphs? Yes, we calculate the similarity between the prototypical graphs and test graphs, which has a massive difference for ID and OOD. 
A more significant gap between ID and OOD graphs corresponds to a better graph OOD detector. We present the scoring distributions on two datasets in Fig. <ref>. The ID and OOD are perfectly separated into two distinct distributions, so we can use a simple threshold for OOD detection and achieve SOTA performance.




 §.§ Ablation Experiment

Q: Whether each module in PGR-MOOD contribute to effectively discriminating OOD molecular graphs? Yes, we conduct experiments on four datasets to verify the role of ℒ_ID, ℒ_OOD, and FGW modules in PRG-MGOD. The results are shown in Table <ref>.




  We remove ℒ_ID and ℒ_OOD in the ℒ_guide respectively to explore their impacts on the performance of OOD detection. We find that merely enlarging the distance between the prototypical graph from  OOD samples (w/o ℒ_ID) or bringing it closer to ID samples (w/o ℒ_OOD) significantly undermines the performance of PGR-MOOD. 
This fully confirms that the Property192 and Property193 are valid and correct. These results demonstrate that the composition of ℒ_ID and ℒ_OOD can generate prototypical graphs G with different similarity measurement for ID and OOD graphs in the testing phase.










    






  
We replace the sim(·) function based on FGW in Eq. (<ref>) with Eq. (<ref>) of GR-MOOD to explore its importance on the performance of OOD detection. We find that the FGW is even more influential than ℒ_OOD on all datasets with different metrics. These experimental results demonstrate that a proper similarity measurement is necessary and the FGW can thoroughly evaluate the similarity between two graphs by considering both their structure and features.









Q: Whether the prototypical graphs G generated by ℒ_guide-guided PGR-MOOD follow the Properties 192 and 193 ? Yes, the prototypical graphs G effectively reduce the distance with the ID graphs and significantly increase the separation from the OOD graphs. 
To validate the impact of ℒ_guide, its trend is monitored throughout the generation phase, as depicted in Fig. <ref>. Here, ℒ_ID and ℒ_OOD are computed using Eq. (<ref>) and Eq. (<ref>) and they represent the distance between G and all graphs belong to ID and OOD, respectively. As the generation progresses, ℒ_ID steadily decreases towards 0, whereas ℒ_OOD escalates sharply. This observation aligns seamlessly with the foundational principles of PGR-MOOD.













 §.§ Computational Complexity Comparison

Q: Whether the PGR-MOOD reduces the complexity of time and space in the training and testing phases?
Yes, to validate the efficiency and scalability of PGR-MOOD, we conduct comprehensive comparisons against the SOTA method GOOD-D and a baseline GR-MOOD. The comparative results are illustrated in Fig. <ref>. 
Although PGR-MOOD slightly trails GOOD-D in testing time, it markedly surpasses it in all other aspects.


  
During the training phase, PGR-MOOD exhibits a substantially reduced training duration compared to both GOOD-D and GR-MOOD. This efficiency stems from GOOD-D's reliance on a time-consuming contrastive learning approach for model training, whereas GR-MOOD necessitates fine-tuning of the diffusion model on the training set. 
In contrast, PGR-MOOD requires the generation of only a limited set of prototype graphs, thereby enhancing its training efficiency.
During the testing phase, GOOD-D leverages its trained model to directly classify input graphs, while PGR-MOOD's method, which entails calculating the similarity between input graphs and the set of prototypical graphs individually. 
Consequently, PGR-MOOD is marginally slower than GOOD-D. However, it significantly outpaces GR-MOOD, which requires the regeneration of reconstructed graphs for each input. 






  
To assess the memory efficiency of our method, we evaluate memory allocation during the testing phase. PGR-MOOD, which eschews the need for any model for OOD detection, only loads the set of prototypical graphs and demands the least memory allocation.
In contrast, the GOOD-D method requires loading GNNs, and GR-MOOD necessitates loading a diffusion model for reconstruction graphs, thereby increasing their memory requirements. The experimental findings underscore that our approach
can significantly mitigate memory consumption and enhance model scalability.






§ CONCLUSION

This study explores OOD detection for molecular graphs, starting with a basic diffusion model-based approach, GR-MOOD, and identifying key challenges. We introduce PGR-MOOD, an advanced OOD detection method for molecular graphs that addresses GR-MOOD's limitations by using a diffusion model to create prototypical graphs. These graphs closely resemble ID inputs while distinctly diverging from OOD inputs. PGR-MOOD utilizes the Fused Gromov-Wasserstein distance for efficient similarity measurement and OOD scoring, significantly reducing computational load. Our approach demonstrates SOTA results across ten datasets, proving its effectiveness.










ACM-Reference-Format












§ APPENDIX





 §.§ Descriptions of Datasets and Metric




  * DrugOOD <cit.> is a systematic OOD dataset curator and benchmark for drug discovery, providing
large-scale, realistic, and diverse datasets for graph OOD learning problems. To meet this purpose of covering a wide range of shifts that naturally occur in molecular graphs, we cautiously consider three properties as the basis of dividing ID and OOD, including assay, molecular size, and molecular scaffold.
DrugOOD provides an automated method for dividing datasets into ID training sets, ID testing sets, and OOD testing sets. We use the ID training set to generate prototypical graphs during the training phase, and process OOD detection on the ID testing set and OOD testing set since they have different data distributions.

  * 





GOOD <cit.> is a systematic graph OOD benchmark, which provide carefully designed data environments for
distribution shifts. Given a domain, it has two kinds of shift strategies: covariate shift, and concept shift. For a supervised dataset, each inputs X∈𝒳 corresponding to outputs Y∈𝒴 and have the distribution of training set P^train(·) and testing set P^test(·). The the joint distribution P(Y,X) can be written as P(Y,X)=P(Y|X)P(X). In covariate shift, the input distributions have been shifted
between training and test data. Formally P^train(X)≠ P^test(X) and P^train(Y|X)= P^test(Y|X). For concept shift, the conditional distribution P(Y|X) has been shifted as P^train(X)=P^test(X) and P^train(Y|X)≠ P^test(Y|X). In order to maintain the consistency of datasets we adopted covariate shift.

  * AUROC (Area Under the Receiver Operating Characteristic curve), AUPR (Area Under the Precision-Recall curve), and FPR95 (False Positive Rate at 95% True Positive Rate) are metrics commonly used to evaluate the performance of classification models, particularly in the context of binary classification and anomaly or outlier detection tasks such as OOD (Out-Of-Distribution) detection.




 §.§ Descriptions of Baseline Methods

In our experiments, we compare the following six methods as baselines:


  * MSP <cit.>: MSP utilizes the backbones’ max softmax output as the judge score, where ID has the highest score and OOD has the lowest score.
    
  * GOOD-D <cit.>: By performing hierarchical contrastive learning on the augmented graphs, GOOD detects OOD graphs based on the semantic inconsistency in different granularities.
    
  * GraphDE <cit.>: GraphDE modeling the graph generative process to characterize the distribution shifts of graph data together with an additionally introduced latent environment variable as an indicator to detect OODs.
    
  * AAGOD <cit.>: AAGOD proposes a learnable amplifier to increase the focus on the key pattern of the structure to enlarge the difference between IDs and OODs.
    
  * OCGIN <cit.>: OCGIN is a graph anomaly detection with a binary classifier where a GIN encoder by the guide of SVDD <cit.>.
    
  * GLocalKD <cit.>: GLocalKD proposes a deep graph anomaly detector based on knowledge distillation for both local and global graphs.




 §.§ Analysis of Hyper-Parameters

To analyze the hyper-parameter sensitivity of PGR-MOOD, we experiment on two datasets with different α and I.





  §.§.§ Analysis of α

To analyze the impact of hyper-parameters α in Eq. (<ref>), which balance the structure term and feature term. 
We vary α in { 0.3, 0.4, 0.5, 0.6, 0.7}  and
present the experimental results in Fig. <ref>. PGR-MOOD performs best with α equal to 0.5, which means it is the fairest way for structure and feature. This fits our needs because we can't predict which way the OOD shift will be biased, so it makes sense to weight both terms equally.



  §.§.§ Analysis of I

To analyze the impact of hyper-parameters I in Eq. (<ref>), which corresponds to the number of prototypical graph G that we need to generate. 
We vary I in {2,4,8,16}  and
present the experimental results in Fig. <ref>. The performance of PGR-MOOD is stable when I changes. In fact, the size of I does not have a huge impact on the final OOD detection result. The calculation of G∈ PL can eventually traverse the entire D_in, only the memory required for the generation process will be affected.










						





					
					




