Spreading Out-of-Distribution Detection on Graphs

Authors: Daeho Um, Jongin Lim, Sunoh Kim, Yuneil Yeo, Yoonho Jung
Primary area: learning on graphs and other geometries & topologies
Keywords: out-of-distribution detection, graph neural networks, benchmark, healthcare

Abstract:
Node-level out-of-distribution (OOD) detection on graphs has received significant attention from the machine learning community. However, previous approaches are evaluated using unrealistic benchmarks that consider only randomly selected OOD nodes, failing to reflect the interactions among nodes. In this paper, we introduce a new challenging task to model the interactions of OOD nodes in a graph, termed spreading OOD detection, where a newly emerged OOD node spreads its property to neighboring nodes. We curate realistic benchmarks by employing the epidemic spreading models that simulate the spreading of OOD nodes on the graph. We also showcase a ``Spreading COVID-19" dataset to demonstrate the applicability of spreading OOD detection in real-world scenarios. Furthermore, to effectively detect spreading OOD samples under the proposed benchmark setup, we present a new approach called energy distribution-based detector (EDBD), which includes a novel energy-aggregation scheme. EDBD is designed to mitigate undesired mixing of OOD scores between in-distribution (ID) and OOD nodes. Our extensive experimental results demonstrate the superiority of our approach over state-of-the-art methods in both spreading OOD detection and conventional node-level OOD detection tasks across seven benchmark datasets. The source code is available at https://github.com/daehoum1/edbd.

Decision: accept (poster)
Reviewer scores: 8, 6, 8, 6, 5

Reviews and discussion:
<thread>
creation date:
1730368304441

thread_type:
official_review

<thread_object>
creator: reviewer_peqa

<content>
summary:
This paper formulates spreading OOD detection, a new benchmark setup for node-level OOD detection method that incorporates interactions among OOD samples and establishes a new dataset called Spreading COVID-19 to benchmark the spreading OOD detection scenario in real-world data.

A node-level OOD detector called EDBD employs an attentive energy aggregation scheme that prevents the mixing of energies between ID nodes and OOD nodes. EDBD is applied to enhance the OOD detection.

strengths:
**S1.**  This paper proposes a new benchmark that models the realistic spread of OOD properties across graph nodes. This setup provides a more applicable framework for real-world scenarios.

**S2.**  This paper leverages EDBD to prevent unwanted mixing of OOD and in-distribution (ID) nodes. By controlling the influence of energy distribution, EDBD achieves better OOD discrimination on proposed datasets and spreading situations.

**S3.**  The paper's aggregation scheme in EDBD is versatile and adaptable to various scenarios on graph-structured data.

weaknesses:
**W1.**  The paper’s reliance on COVID-19 to introduce and validate the spreading OOD detection model may feel outdated. As COVID-19 has become less urgent as a topic, using it as the central example could reduce the model's perceived relevance. A more contemporary application, such as misinformation spread or novel pathogens, might enhance the model's applicability and appeal

**W2.** What’s the relationship of this new problem with other problems, e.g., node classification or outlier detection on graphs? I’m not sure what’s the main difference between this problem and the outlier detection problem. The outliers are not seen in the training set? Can these algorithms be used as the baselines? 

**W3.** The effectiveness of the EDBD approach heavily depends on the graph structure and quality of connectivity information. In cases where graph structures are incomplete or noisy, the method’s performance may degrade, potentially affecting its robustness in real-world scenarios.

**W4.** While the paper employs SI and SIS models for simulating OOD spreading, it leaves the integration of more complex epidemic models for future work. This limits the current approach's applicability to more intricate real-world spreading phenomena that may not be accurately represented by simple models.

**W5.** Although the "Spreading COVID-19" dataset simulates virus spread, the lack of training on actual epidemic or contagion data might reduce the generalizability of the model when faced with real-world data that includes nuanced spreading patterns not captured by synthetic simulations.

questions:
**Q1.** How might the proposed spreading OOD detection model adapt to more complex epidemic models, such as SEIR (Susceptible-Exposed-Infectious-Recovered) or multi-host transmission models? Are there specific limitations or computational challenges that prevent their integration?

**Q2.** What steps could be taken to ensure the model’s robustness on graphs with missing or noisy edges and nodes? Would incorporating graph-denoising techniques or imputing missing links improve EDBD’s performance?

**Q3.** Have alternative case studies, such as the spread of misinformation or emergent diseases, been considered to showcase the model’s versatility? How might these cases impact the model's applicability and reception in current contexts?

**Q4.** What’s the relationship of this new problem with other problems, e.g., node classification or outlier detection on graphs?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730549054438

thread_type:
official_review

<thread_object>
creator: reviewer_t4yw

<content>
summary:
This paper introduces a novel task called spreading out-of-distribution (OOD) detection, which focuses on identifying OOD nodes within graph structures, particularly emphasizing the interactions and influence these nodes have on their neighbors. The authors leverage epidemic spreading models to create realistic benchmarks that reflect the dynamics of OOD node propagation in real-world scenarios. The authors propose an innovative approach known as the Energy Distribution-Based Detector (EDBD), which utilizes energy scores to enhance the aggregation process of node information. This method aims to mitigate the mixing of OOD scores between in-distribution (ID) and OOD nodes, thereby improving the accuracy of OOD detection.

strengths:
1.The creation of the Spreading COVID-19 dataset provides a realistic and relevant context for evaluating OOD detection methods. This dataset simulates real-world scenarios, making the findings more applicable to practical situations.
2. The authors conducted comprehensive experiments, comparing EDBD against several state-of-the-art methods across multiple datasets.
3. The paper is well-structured and clearly presents the methodology, experimental setup, and results, making it accessible for readers and researchers interested in the topic.

weaknesses:
1. While the results demonstrate superior performance, the paper may lack comprehensive statistical analysis (e.g., significance testing) to support the claims of superiority over existing methods.
2.The energy-based aggregation approach may introduce additional complexity compared to simpler methods. This complexity could make the method less accessible for practitioners who may prefer more straightforward solutions.

questions:
1. What is the sensitivity of EDBD to different hyperparameter settings? How do variations in these parameters affect the model's performance?
2. How does EDBD perform on larger graphs or more complex networks? Are there any scalability issues that arise when applying the method to real-world scenarios with extensive node interactions?
3. How interpretable are the results produced by EDBD? Can the authors provide insights into why certain nodes are classified as OOD based on the energy aggregation process?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730581903727

thread_type:
official_review

<thread_object>
creator: reviewer_8nsj

<content>
summary:
This paper introduces "spreading OOD detection," for node-level out-of-distribution (OOD) detection on graphs. It addresses limitations in existing methods by modeling the spread of OOD samples through graph structures. The authors propose a new dataset, "Spreading COVID-19," and present a novel approach called Energy Distribution-Based Detector (EDBD) that outperforms existing methods in both spreading and conventional OOD detection tasks.

strengths:
1. The concept of spreading OOD detection is novel and addresses a gap in existing methods.
2. A new dataset is introduced which will help future research
3. The figures used in the paper manage to illustrate the problem and approach well.

weaknesses:
1. It would be interesting to see comparison of EDBD with SOTA in terms of computational complexity and scalability.
2. Some discussion on how the proposed dataset compares to real-world datasets and its characteristics would benefit the paper

questions:
1. Are there any specific graph structures or spreading patterns where EDBD might underperform compared to other methods?
2. How sensitive is the performance of EDBD to the choice of hyperparameters in the energy-aggregation scheme?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730676904054

thread_type:
official_review

<thread_object>
creator: reviewer_xogv

<content>
summary:
This paper introduces a more realistic benchmark for node-level out-of-distribution (OOD) detection on graphs, called “spreading OOD detection”, where  OOD characteristics spread across connected nodes, similar to real-world diffusion processes like disease spreading. The paper dedicates one part to defining this benchmark in detail, using the “Spreading COVID-19” dataset to show its practical value. This benchmark is different from traditional approaches that treat OOD nodes as isolated and do not consider interactions. Another part of the paper is focused on a new method, the Energy Distribution-Based Detector (EDBD), designed to address this benchmark. EDBD uses an energy-aggregation scheme to keep OOD and in-distribution (ID) scores from mixing, helping to identify OOD nodes more accurately.

strengths:
Although the benchmark is presented as realistic, it relies on assumptions in simulations that may be hard to verify, particularly given the use of the LastFM dataset, which may not accurately represent human contact patterns essential for modeling disease spread. The suitability of LastFM’s social connections as a proxy for physical contact is uncertain, as are other factors like spatial constraints and the presence of high-degree nodes that could act as unrealistic “super-spreaders.” To address this concern and enhance the benchmark’s realism, the authors could validate these assumptions against datasets explicitly designed for human contact networks (such as those used in epidemiology studies) or test the model on multiple datasets with diverse structural properties to better reflect real-world contact interactions.

The EDBD method’s performance appears closely tied to assumptions within the benchmark setup, making it difficult to assess its independent technical relevance. The method seems to build on GNNSAFE with the addition of energy similarity and consistency matrices, yet these connections and differences are not fully discussed. To clarify the contribution, the authors could provide a more detailed comparison between EDBD and GNNSAFE, explaining how the added matrices influence performance and to what extent the results depend on benchmark-specific assumptions.

weaknesses:
Although the benchmark is presented as realistic, it relies on assumptions in simulations that may be hard to verify, particularly given the use of the LastFM dataset, which may not accurately represent human contact patterns essential for modeling disease spread. The literature in this area includes foundational works from over a decade ago, which should be discussed, e.g. [1,2,3].
The suitability of LastFM’s social connections as a proxy for physical contact is uncertain, as are other factors like spatial constraints and the presence of high-degree nodes that could act as unrealistic “super-spreaders.” To address this concern and enhance the benchmark’s realism, the authors could validate these assumptions against datasets explicitly designed for human contact networks (such as those used in epidemiology studies) or test the model on multiple datasets with diverse structural properties to better reflect real-world interactions.

The EDBD method’s performance appears closely tied to assumptions within the benchmark setup, making it difficult to assess its technical relevance. The method seems to build on GNNSAFE with the addition of energy similarity and consistency matrices, yet these connections and differences are not fully discussed. To clarify the contribution, the authors could provide a more detailed comparison between EDBD and GNNSAFE, explaining how the added matrices influence performance and to what extent the results depend on benchmark-specific assumptions.

[1] Mossong, J., Hens, N., Jit, M., Beutels, P., Auranen, K., Mikolajczyk, R., ... & Edmunds, W. J. (2008). Social contacts and mixing patterns relevant to the spread of infectious diseases. PLoS medicine, 5(3), e74.   
[2] Balcan, D., Colizza, V., Gonçalves, B., Hu, H., Ramasco, J. J., & Vespignani, A. (2009). Multiscale mobility networks and the spatial spreading of infectious diseases. Proceedings of the national academy of sciences, 106(51), 21484-21489.   
[3] Pastor-Satorras, R., Castellano, C., Van Mieghem, P., & Vespignani, A. (2015). Epidemic processes in complex networks. Reviews of modern physics, 87(3), 925-979.

questions:
Q1: Since the dataset is central to the benchmark, it is crucial to understand how well it reflects realistic contact-driven networks for virus spreading. Information on whether the dataset’s assumptions have been validated against more realistic epidemic scenarios would also help clarify its suitability for simulating disease dynamics. Could the authors provide detailed information on the construction and structure of the LastFM dataset, including the main mechanisms of edge formation, the presence of high-degree nodes that could act as super-spreaders, and the dataset’s time span in relation to episode durations required to reach 75% node infection? 

Q2: Could the authors discuss the sensitivity of the proposed method to variations in the SIS model parameters and its adaptability to different diffusion patterns? Understanding this sensitivity is important for evaluating the method’s robustness in various scenarios. Additionally, could the authors clarify why OOD detection is not approached as a binary classification between ID and OOD, or as a one-class classification in cases where only ID labels are available? Addressing these points would provide valuable insights into the generalizability of the benchmark and the chosen approach for OOD detection.

Q3: Given the high error bars in Tables 2 and 3, how conclusive are the results? Could the authors explain if the similar performance of EDBD and the Energy method suggests that data features, rather than graph structure, drive the performance? Also, since Eq. 4 of the paper is quite similar to Eq. 7 of GNNSAFE, could the authors clarify the exact differences between EDBD and GNNSAFE beyond adding the energy similarity and consistency matrices? For example, does the first row in Table 4 represent GNNSAFE?

Q4: Since hyperparameter tuning can greatly impact performance, could the authors explain how it was done for both EDBD and baseline methods? Was the search for competitors restricted compared to EDBD? For GNNSAFE, was only the supervised loss used, or did the authors include GNNSAFE++ with energy regularization? If only the supervised loss was used, what motivated this choice?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730727973837

thread_type:
official_review

<thread_object>
creator: reviewer_cft1

<content>
summary:
This research addresses a significant gap in node-level out-of-distribution (OOD) detection by introducing a novel task that considers the interactions among nodes in a graph. Previous methods have relied on unrealistic benchmarks that randomly select OOD nodes, which do not reflect real-world scenarios where OOD properties can spread among neighboring nodes. The key contributions of this paper include:
1. Introduction of Spreading OOD Detection: This new task models how newly emerged OOD nodes can influence their neighbors, simulating more realistic scenarios of OOD detection.
2. Realistic Benchmark Creation: The authors develop benchmarks using epidemic spreading models to simulate the dynamics of OOD node interactions within graphs. 
3. “Spreading COVID-19” Dataset: A specific dataset is introduced to illustrate the practical applications of spreading OOD detection, showcasing its relevance to real-world situations.
4. Energy Distribution-Based Detector (EDBD): The paper presents a new detection approach that employs an energy-aggregation scheme aimed at reducing the overlap in OOD scores between in-distribution (ID) and OOD nodes, enhancing detection accuracy.
5.Extensive Experimental Validation: Results from comprehensive experiments demonstrate that the proposed EDBD approach outperforms existing state-of-the-art methods in both spreading OOD detection and traditional node-level OOD detection tasks across seven benchmark datasets.
Overall, this work advances the field of OOD detection by incorporating the complexities of node interactions in graph structures, providing both theoretical and practical contributions.

strengths:
This research addresses a significant gap in node-level out-of-distribution (OOD) detection by introducing a novel task that considers the interactions among nodes in a graph. Previous methods have relied on unrealistic benchmarks that randomly select OOD nodes, which do not reflect real-world scenarios where OOD properties can spread among neighboring nodes. The key contributions of this paper include:
1. Introduction of Spreading OOD Detection: This new task models how newly emerged OOD nodes can influence their neighbors, simulating more realistic scenarios of OOD detection.
2. Realistic Benchmark Creation: The authors develop benchmarks using epidemic spreading models to simulate the dynamics of OOD node interactions within graphs. 
3. “Spreading COVID-19” Dataset: A specific dataset is introduced to illustrate the practical applications of spreading OOD detection, showcasing its relevance to real-world situations.
4. Energy Distribution-Based Detector (EDBD): The paper presents a new detection approach that employs an energy-aggregation scheme aimed at reducing the overlap in OOD scores between in-distribution (ID) and OOD nodes, enhancing detection accuracy.
5.Extensive Experimental Validation: Results from comprehensive experiments demonstrate that the proposed EDBD approach outperforms existing state-of-the-art methods in both spreading OOD detection and traditional node-level OOD detection tasks across seven benchmark datasets.
Overall, this work advances the field of OOD detection by incorporating the complexities of node interactions in graph structures, providing both theoretical and practical contributions.

weaknesses:
Theoretical Justification for EDBD: While the energy-aggregation scheme is introduced as a key component of the EDBD, the paper would benefit from a more rigorous theoretical foundation explaining why this method effectively mitigates the mixing of OOD scores. Providing mathematical justifications or theoretical comparisons with other aggregation methods could strengthen the credibility of this contribution.

Sensitivity Analysis: Conducting a sensitivity analysis on the parameters of the EDBD model could provide valuable insights into how different configurations affect performance. Understanding how the model behaves under various conditions would help in fine-tuning the method for practical applications and could guide users in optimizing the approach for specific contexts.

questions:
Theoretical Foundations of EDBD:
Question: What theoretical framework supports the effectiveness of the energy-aggregation scheme in EDBD?
Suggestion: A more detailed theoretical justification for why this approach mitigates the mixing of OOD scores would strengthen your argument and improve the method's credibility.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732372838807

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
In this paper, we introduce spreading OOD detection, a novel benchmark setup for node-level OOD detection that incorporates interactions among OOD samples. We also establish a new dataset, Spreading COVID-19, to demonstrate the applicability of spreading OOD detection in real-world scenarios. Additionally, we propose a novel scheme called the Energy Distribution-Based Detector (EDBD), which achieves outstanding performance in both spreading OOD detection and conventional node-level OOD detection tasks.

**We express our profound gratitude to all reviewers for dedicating their time and effort to thoroughly evaluate our manuscript. The constructive feedback provided by the reviewers has greatly enhanced the quality of our paper**. To address the reviewers’ concerns, **we provide point-by-point responses to all the questions and concerns raised by the reviewers**. Below is a summary of the key updates made to our paper:
* Theoretical Analysis (in Appendix. E)
* Hyperparameter Sensitivity (in Appendix. C.7)
* Comparison between LastFM Asia and a Human Contact Network (in Appendix. A)
* Spreading Covid on a Contact Network (in Appendix. C.8)
* SIS Models with Various Parameter Combinations (in Appendix. C.9)
* Spreading OOD Detection for an Urgent Contagion, RSV (in Appendix. C.10)
* Incomplete Graph Structures (Appendix. C.11)
* Spreading OOD Detection using SEIR models (Appendix. C.12)
* Discussion on "Why are human contact studies not considered?” (in Appendix. F)
* Discussion on "Why OOD detection is not approached as a binary classification?” (in Appendix. F)
* Discussion on "OOD Detection vs Outlier Detection” (in Appendix. F)

**For the revised and updated parts in the manuscript, we have marked the changes in blue**. We hope that the responses provided below address all the reviewers’ concerns, and **please let us know if the raised concerns are addressed**. We are happy to answer further questions and would be delighted to provide additional clarifications.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733313567742

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Final Summary

comment:
Dear Senior Area Chairs, Area Chairs, and Reviewers,

We sincerely appreciate the hard work and dedication of the chairs and the reviewers. During the discussion period, the reviewers provided thoughtful and professional feedback. **We have addressed all of the reviewer's concerns**, which allowed us to greatly improve the quality of the paper by incorporating their valuable suggestions. Specifically, in response to the reviewers' suggestion, we have included a theoretical analysis in Appendix E of the revised manuscript. **Except for Reviewer peqA, all reviewers have expressed supportive opinions for acceptance with high scores.** 

**While we have thoroughly addressed Reviewer peqA's concerns, we have not received any response to our request for clarification on Reviewer peqA's decision over the past eight days, despite repeated attempts to seek a response from Reviewer peqA.** To facilitate the discussions among the chairs and reviewers, we would like to summarize (1) the contributions of our work and (2) our rebuttal addressing all of Reviewer peqA's concerns as a final note. We hope these points will be taken into consideration when the final decision is made.

***

## Contributions

1.  We introduce **spreading out-of-distribution (OOD) detection, a realistic benchmark for node-level OOD detection** that accounts for interactions among nodes.

2. We establish **a new dataset, Spreading COVID-19**, to demonstrate the applicability of spreading OOD detection in real-world problems.

3. We propose **a novel scheme**, Energy Distribution-Based Detector (EDBD), which **outperforms state-of-the-art methods in both spreading OOD detection and conventional node-level OOD detection tasks**.

***

## Reviewer peqA's Concerns

**More complex epidemic model** 

* We conducted **additional experiments using the SEIR model suggested by Reviewer peqA** and verified EDBD's superiority in Appendix C.12 of the revised manuscript.

**More contemporary application than COVID-19**

* We conducted **additional experiments on an urgent contagion, Respiratory Syncytial Virus (RSV)**, and validated EDBD's effectiveness in Appendix C.10 of the revised manuscript.

**Validation of EDBD on graphs with incomplete structures**

* We conducted **additional experiments under edge-missing settings** and confirmed that EDBD maintains reasonable performance in Appendix C.11 of the revised manuscript.

**Lack of training on actual epidemic or contagion data in the context of the Spreading COVID-19 dataset**

* We conducted experiments on the **COVID-19 dataset using various epidemic models, which are widely used in epidemic spreading studies**, and confirmed the consistent superiority of EDBD, as demonstrated in Tables 2, 3, 14, 15, and 17 of the revised manuscript.

**Spreading OOD detection vs. outlier detection/node classification**

* We provided **a clear explanation of the fundamental differences** in Appendix F of the revised manuscript.

***

We strongly believe that the ICLR Senior Area Chairs, Area Chairs, and other reviewers will agree with our perspective upon reviewing our rebuttal to Reviewer peqA. **We hope that Reviewer peqA will take the time to review our clarifications and request even after the discussion period has concluded**. While we respect Reviewer peqA's evaluation, we trust that our rebuttal to Reviewer peqA and the lack of response from Reviewer peqA will be carefully considered in the final decision-making process.


Once again, we extend our sincerest thanks to all the chairs and reviewers for their efforts.

Sincerely,\
The Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces "spreading OOD detection," a novel task in graph-based out-of-distribution (OOD) detection that accounts for the influence of OOD nodes on their neighbors. This addresses a significant limitation of existing methods which typically assume OOD nodes are isolated, an unrealistic assumption in many real-world scenarios where OOD properties can propagate through the graph structure. The authors propose a new benchmark generation scheme based on epidemic spreading models and introduce a "Spreading COVID-19" dataset to demonstrate its practical relevance. Furthermore, they propose the Energy Distribution-Based Detector (EDBD), a new method that outperforms existing approaches on both traditional and spreading OOD detection tasks.

Reviewers appreciate the introduction of the spreading OOD detection task and the development of more realistic benchmarks. They acknowledge the practical value of the "Spreading COVID-19" dataset and the potential of this work to inspire further research in this direction. The proposed EDBD method also demonstrates promising performance improvements in the conducted experiments.

However, reviewers also raise a concern:

- Benchmark Dependence: The EDBD method's strong performance appears to be closely tied to the specific characteristics of the proposed benchmark. It is unclear how well the method would generalize to other scenarios or if it offers significant advantages beyond being well-suited to the authors' benchmark.

Recommendation:

Despite this concern, the paper makes a valuable contribution by introducing a new and relevant task in OOD detection on graphs. The creation of realistic benchmarks and the "Spreading COVID-19" dataset are valuable resources for the community. I recommend accepting this paper as a poster.