Revisiting Score Propagation in Graph Out-of-Distribution Detection

W3&Q2. Justification regarding using Bernoulli distribution to model edge weights.

Fair Concern! As we are dealing with discrete graphs, where edges either exist or do not, the adjacency matrix values are binary, taking on either 0 or 1. This naturally aligns with the Bernoulli distribution, which is frequently employed in graph structure learning, as exemplified in several pertinent references in [A,B,C].

[A] Learning Discrete Structures for Graph Neural Networks. ICML'19.

[B] Variational Inference for Graph Convolutional Networks in the Absence of Graph Data and Adversarial Settings. NeurIPS'20.

[C] Data Augmentation for Graph Neural Networks. AAAI'21.

W3-2. Examples that demonstrate the importance of the number of intra-edges and inter-edges.

We present detailed evidence in Table 14, which outlines the relationship between the ratio of intra-edges and OOD detection performance across 10 real datasets. The data illustrate that a higher number of intra-edges is crucial for effective OOD detection.

Q1. Request for an intuitive example showing the importance of intra-edges and inter-edges in OOD detection.

Figure 2 provides a clear, intuitive example demonstrating how variations in the number of intra-edges versus inter-edges impact OOD detection. The two graphs in Figure 2 have the same nodes, but due to the differing numbers of intra-edges and inter-edges, they yield completely opposite results after score propagation. Specifically, score propagation enhances OOD detection performance only when intra-edges dominate; otherwise, it may in turn hurt the performance. This conclusion is supported by the emperical results of our used real datasets, as shown in Table 2, Table 3, and Table 14.

Q3. Concern about lower FPR on the dataset Reddit2 compared to other models.

The notable decrease in False Positive Rate (FPR) observed with GRASP on the Reddit2 dataset can be attributed to an increased proportion of intra-edges, as detailed in Table 14. After propagating score along $A\_+$, the high scores of ID nodes are transferred more to $\mathcal{V}\_{uid}$ than to $\mathcal{V}\_{uood}$, resulting in higher scores for $\mathcal{V}\_{uid}$ than for $\mathcal{V}\_{uood}$, thus widening the gap between $\mathcal{V}\_{uid}$ and $\mathcal{V}\_{uood}$ and reducing the misidentification of OOD. Figure 1 in the attached pdf (Please refer to the Common Responses section titled "Author Rebuttal by Authors" https://openreview.net/forum?id=jb5qN3212b&noteId=HVpGXjNQ0B) shows the score distribution of $\mathcal{V}\_{uid}$ and $\mathcal{V}_{uood}$ on Reddit2 before and after using GRASP respectively. The shaded area with diagonal lines represents FPR, visually illustrating the aforementioned reasons.

Q4. Patterns in the ratio of intra-edges to inter-edges for better OOD detection performance.

The following table systematically presents the impact of the intra- to inter-edge ratio ($\eta\_{intra}$/$\eta\_{inter}$) on OOD detection performance across various datasets. The results indicate that the number of intra-edges plays a crucial role in OOD detection performance. When the ratio of intra-edges is increased to dominate, score propagation can achieve excellent OOD detection performance across different datasets.

    Thanks very much for your detailed responses. I will keep my positive score on this paper.

We appreciate the reviewer's constructive feedback and insightful questions. Below, we address each point in detail:

W1&Q5. Suggestion on providing more discussion w.r.t the exisiting graph OOD works and comments on the paper's contribution position.

We appreciate your comments and the opportunity to clarify and further discuss the positioning!

Firstly, we acknowledge the contributions of previous works in this field and have made it clear from the introduction (line 29) that our approach is inspired by prior research [72]. If any part of the text inadvertently suggested that we were the first to address graph OOD detection, we are welcome with advices to eliminate possible confusion and better position our contributions.

Regarding the discussion with references and existing works on graph OOD:

1. OOD Generalization vs. OOD Detection. The uncited paper [A] suggested by the reviewer addresses a different problem -- OOD generalization rather than OOD detection. This distinction is crucial as OOD generalization focuses on correctly classifying domain-shifted data, which involves a different kind of "OOD" than the semantic shift concerns of OOD detection. Our work specifically targets scenarios where data does not conform to any in-domain class.
2. Graph-level vs. node-level. We also note a significant body of research [B-G] that focuses on graph-level OOD detection. Our work, however, contributes to the less-explored area of node-level OOD detection, where current literature remains sparse [H-L]. Our findings help fill this gap by providing new insights and methodologies.
3. Training-required vs. post hoc method. Methodologically, our approach differs significantly from those in existing literature, which often require extensive re-training [I-L]. Our post hoc solution (demonstrated in Tables 2, 3, 15, and 16) enables effective and efficient OOD detection, facilitating easier deployment and practical application in real-world scenarios.
4. New theoretical contribution. Our paper introduces fundamental theoretical analysis, a first in the realm of node-level graph OOD detection. We elucidate key factors such as the importance of intra-edge dominance, providing a new theoretical framework that aids in understanding and addressing the unique challenges of OOD detection on graphs.

We hope these clarifications and expansions will address the concerns raised and better articulate the value and positioning of our work in the literature.

[A] Generalizing graph neural networks on out-of-distribution graphs. TPAMI'23

[B] GraphDE: A Generative Framework for Debiased Learning and Out-of-Distribution Detection on Graphs. NeurIPS'22

[C] Towards OOD Detection in Graph Classification from Uncertainty Estimation Perspective.ICML'22

[D] On Estimating the Epistemic Uncertainty of Graph Neural Networks using Stochastic Centering. ICML'23

[E] GOOD-D: On Unsupervised Graph Out-Of-Distribution Detection. WSDM'23

[F] A Data-centric Framework to Endow Graph Neural Networks with Out-Of-Distribution Detection Ability. KDD'23

[G] HGOE: Hybrid External and Internal Graph Outlier Exposure for Graph Out-of-Distribution Detection. MM'23

[H] Energy-based out-of-distribution detection for graph neural networks. ICLR'23

[I] Uncertainty aware semi-supervised learning on graph data. NeurIPS'20

[J] Graph posterior network: Bayesian predictive uncertainty for node classification. NeurIPS'21

[K] Learning on graphs with out-of-distribution nodes. KDD'22

[L] Bounded and Uniform Energy-based Out-of-distribution Detection for Graphs. ICML'24

W2. The baselines selected in the experiments may not be sufficiently novel. This makes the experimental results are not convincing enough.

To address this concern, we have incorporated two latest baselines, NODESafe [A] and fDBD [B], into our experiments on both common datasets (5 datasets) and large-scale datasets (3 datasets). NODESafe aims to reduce the generation of extreme scores when traing ID models on graphs, and fDBD detects OOD samples based on their feature distances to decision boundaries. Our results reveal that the performance of these methods lags significantly behind ours due to their inability to increase the proportion of intra-edges.

[A] Bounded and Uniform Energy-based Out-of-distribution Detection for Graphs. ICML'24

[B] Fast Decision Boundary based Out-of-Distribution Detector. ICML'24

Limitation. GRASP may not be as effective in scenarios with random connectivity patterns

We agree with the reviewer's point that when a graph has random connectivity, all methods will perform poorly because such a graph lacks any meaningful edge information, making it indeed impossible to work effectively. To validate this, we conduct a simple experiment in Cora. Specifically, we randomly shuffle the original edges of the graph while retaining the original features and labels for training the ID model. We then evaluate the performance of each baseline on the trained model. The results, presented in the table below, confirm that all methods achieve AUROC scores around 50%, comparable to random guessing. However, in real-world graphs, random connectivity is unlikely, ex. social network. In reality, there are connections between IDs, and they naturally tend to be linked together. Therefore, it is less practical to consider the network with random connectivity.

Q1. How does the performance of GRASP vary with different OOD distributions (e.g., uniform, normal, outliers)?

We thank reviewer for the suggestion! We manually generate 2D sample points as graph nodes, with ID samples drawn from a standard Gaussian distribution and OOD samples drawn from three different distributions: a 2D uniform distribution, a different normal distribution from ID, and an outlier distribution. The outlier samples are randomly selected points outside the region of the ID sample points. We calculate the RBF kernel similarity between pairs of sample points and constructe edges between nodes with high similarity to simulate the similarity between nodes' embeddings after training GNN.

The experimental results are shown in the table below. The results indicate that GRASP performs best when the OOD is normal, worst when the OOD is uniform, and intermediate when the OOD is outlier.

We are happy to provide more experiment results for reviewer's interest!

Q2. Can the authors provide further insights into how GRASP works and how it interprets the graph structure?

Thank you for your inquiry about the rationale behind GRASP! Here's a succinct overview to aid your understanding:

• Core Principle: The effectiveness of GRASP in enhancing graph OOD detection hinges on increasing the proportion of intra-edges before performing score propagation.
• Implementation: Based on this principle, GRASP identifies a subset $G$ within the graph, characterized by having more connections to ID data than to OOD data. Additional edges within $G$ are then added to enhance the score propagration for OOD detection.

Regarding your question on how GRASP interprets the graph structure:

• GRASP is designed to amplify the score difference between $\mathcal{V}\_{uid}$ (nodes to be identified as ID) and $\mathcal{V}\_{uood}$ (nodes to be identified as OOD). By reinforcing connections within the subset $G$ that has stronger ties to ID data, and then conducting score propagation, it exert a greater influence on $\mathcal{V}\_{uid}$ compared to $\mathcal{V}\_{uood}$. This structured modification and targeted propagation are pivotal for enhancing the discriminative capability of the network against OOD nodes.

If there is any aspect of the question that we have misunderstood, or if further clarification is required, please do not hesitate to let us know!

Q3. How does the performance of GRASP scale with the size of the graph and the number of nodes? Is there any systemic analysis?

The 10 datasets used in our experiments cover various scales from small scale to large scale. As shown in Tables 1-3, GRASP's performance is not significantly affected by the scale or size of the datasets. Instead, its performance is more influenced by the proportion of inter-edges in the original datasets.

We appreciate the reviewer's constructive feedback and insightful questions. Below, we address each point in detail:

W1. it is strongly suggested to release the source code of experiments.

Sure! We have made the source code available at the following link: https://anonymous.4open.science/r/GRASP-EEA3/README.md.

W2. Considering the imporvement is margin in Table 2 and 3, it is also suggested that the authors should provide a standard error with statistical significance analysis in the results.

We appreciate your observations regarding the improvements in Table 2 and 3! We'd like to emphasize that the overall improvement of our method is substantial. Nevertheless, your suggestion about including the standard error (STD) to provide statistical significance analysis is well taken. We have updated the manuscript to include standard errors for all datasets. It is important to note that the FPR95 metric displays a relatively high standard error across methods on the Cora, Amazon, and Chameleon datasets due to their small sizes, which makes the outcomes sensitive to variations in data splits. Nonetheless, our method consistently remains competitive across all five runs, as detailed in the updated Table.

We appreciate the reviewer's constructive feedback and insightful questions. Below, we address each point in detail:

W1&Q1. Concern about using MSP score to select S_id and S_ood.

Thank you for this insightful question! We acknowledge the concern that the model can sometimes exhibit overconfidence for certain OOD nodes. However, this does not undermine the applicability of GRASP when ID nodes' MSP scores are generally higher than those of OOD nodes. As demonstrated in Figure 4, we selectively utilize the highest MSP scores for ID and the lowest for OOD. This selection strategy results in more accurate estimations of $S\_{id}$ and $S\_{ood}$.

We empirically support this approach with results presented in Tables 2, 3, and 5, across five datasets (Squirrel, Reddit2, arXiv-Year, snap-patents, and Wiki). These results show significant performance improvements with GRASP, particularly where original MSP scores were ineffective, ensuring more accurate distinctions between $S_{id}$ and $S_{ood}$ in each iteration.

Additionally, our method offers high flexibility—it can integrate any existing OOD scoring function. While we use MSP in our primary demonstrations to explain GRASP's principles, substituting MSP with other well-known OOD scoring methods in our framework also yields competitive results, as shown in Table 7. This highlights GRASP’s adaptability and robustness.

W2. Suggestion of including error bars.

This is an excellent suggestion! We have now included the main results with standard errors for all datasets in the revised manuscript and the table below. It is important to note that the FPR95 metric displays a relatively high standard error across methods on the Cora, Amazon, and Chameleon datasets due to their small sizes, which makes the outcomes sensitive to variations in data splits. Nonetheless, our method consistently remains competitive across all five runs, as detailed in the updated table in the second part of the response.

We appreciate the reviewer's constructive feedback and insightful questions. Below, we address each point in detail:

W1. Relationship between GRASP and the in-distribution classification accuracy.

Fair concern! GRASP is a post hoc OOD detection method that does not interfere with the classification process. Therefore, the classification accuracy of in-distribution (ID) data remains unchanged.

W2. Extension to subgraph-level tasks or graph-level tasks.

We appreciate the reviewer's suggestion to extend our work to different tasks! While our primary focus is on the node-level setting, we are open to discussing how GRASP can be adapted for subgraph-level or graph-level tasks. One potential approach is to treat a subgraph or graph as a single node, with the similarity between subgraphs or graphs represented by the weights of edges. This adaptation would enable the application of our method to these broader contexts.

Q1. Is the classification accuracy in Appendix D.1 assessed before or after employing GRASP? Is there a comparison between the two?

(Related to W1) The classification accuracy presented in Appendix D.1 is from the pretrained ID model before employing GRASP. Since our method is post hoc, the classification accuracy remains the same across all post hoc methods.

Q2. Do similar cases discussed in Figure 2 exist within real-world datasets?

Yes, they do. Figure 2 is designed to intuitively illustrate our theoretical findings, which are authentically reflective of real-world scenarios. Our theory suggests that score propagation enhances OOD detection performance when intra-edges are predominant. This behavior is captured in real-world datasets, as supported by the empirical evidence presented in Table 14.

Q3. What is the accuracy of the edge-adding method presented in the text, specifically how many to intra-edges, and how many to inter-edges? What impact would incorrectly added edges have on the results?

The accuracy of the added edges on the common datasets is shown in the table below:

We investigate the impact on GRASP's performance by adding varying proportions of incorrect edges. The results are presented in the table below, with the "ratio" column indicating the proportion of incorrect edges added. The results show that GRASP's performance deteriorates significantly when the proportion of incorrect edges exceeds 0.3.

Dear Reviewer hQev,

Thank you for raising the concerns regarding our claim that "GRASP still works when raw MSP fails." We appreciate the opportunity to further clarify this aspect of our study.

To delve deep into this, we conducted a visualization analysis of the MSP score distribution similar as Figure 4 across each dataset. Due to the limitations of the OpenReview platform, we are unable to upload these new figures to share the insight. (We will include in the revision) In these figures, we observe multiple distinct "heaps" in the score distribution. It is important to note that since MSP measures across the entire test set, it does not effectively capture all the local characteristics. Notably, our results indicate that selections made using Sid, which prioritizes the highest MSP scores, more composed of ID nodes rather than OOD nodes. This tendency is further reinforced with additional propagation iterations.

We also wish to highlight additional evidence supporting the effectiveness of GRASP:

1. GRASP is also compatible with other scoring function beyond MSP. Substituting MSP with other well-known OOD scoring methods in our framework also yields competitive results, as shown in the table (AUROC) below.

2. Enhancement of Intra-edge Ratios During Propagation. By utilizing Sid and Sood estimates, GRASP significantly increases the proportion of intra-edges, thereby improving the overall accuracy of edge addition. The ablation study results displayed below illustrate the increased accuracy of added edges when GRASP is employed, compared to scenarios where it is not used:

Regarding the impact of other based models, we have shown in Table 13 that GRASP achieves optimal performance on various base models in the literature. For the reviewer’s convenience, we have included the relevant results below and in the third part of the response, which clearly attests to the versatility and practicality of GRASP: