Redundancy-Aware Test-Time Graph Out-of-Distribution Detection

We sincerely appreciate your valuable comments and will reply to all these concerns individually.

W1.1: Figure 2 contains "?", which makes it difficult to understand

We would like to clarify that Figure 2 in our paper does not contain "?" symbols. The issue you mentioned may result from incomplete image rendering in the browser. We recommend downloading the paper and viewing it locally using Adobe Reader to ensure correct visualization.

---

W1.2 & W2.1: Section 3 introduces ReGIB and the objective for coding tree construction, but lacks a straightforward explanation on the choice of using the construction loss as the OOD detection score

Thank you for the question. The construction of coding tree does not introduce any new loss function. Instead, we use structural entropy as the optimization metric for coding tree construction (see Eq. (12) and (14)). Moreover, we would like to clarify that we do not use structural entropy as the OOD score, and the OOD score is actually computed based on Eq. (18).

---

W2.2: If the OOD samples are detected when the loss exceeds a certain threshold, the good performance of the proposed method may stem from a well-tuned threshold on the benchmark datasets

Thank you for the comment. The strong performance of our method does not stem from a well-tuned threshold. We follow the same evaluation protocol as GOOD-D and GOODAT, where the AUC metric is computed using auc = sklearn.metrics.roc_auc_score(y, ood_score). Specifically, y denotes the binary ground-truth labels, and ood_score represents the confidence score for predicting a sample as OOD. This score is a continuous value that can be ranked across samples. AUC is computed by ranking all samples according to their ood_score, and then calculating the corresponding true positive rate (TPR) and false positive rate (FPR) over the full range of score distributions to construct the ROC curve (with FPR on the x-axis and TPR on the y-axis). The AUC is the area under this ROC curve, with a larger value indicating stronger discrimination ability. The effectiveness of these methods, including ours, is thus evaluated independently of any manually selected threshold.

---

W3 & Q2.2: The paper could benefit from more empirical details on the coding tree construction and a time consumption comparison between the proposed method and other baseline methods

Thank you for pointing this out. We provide detailed illustrations and explanations of the coding tree construction process in Appendix D and Figures 10 to 12 of the paper. Moreover, coding tree construction, as well as the proposed RedOUT method, is not time-consuming. In Appendix E7, Table 10 compares the time consumption of pretraining, coding tree construction, and test-time OOD detection.

We additionally provide a comparison of time consumption with other baselines in the table below. For deep learning methods under other settings, we select the best-performing methods, GOODD and GraphCL-MD, for reference.

Note that the official implementation of AAGOD could not run successfully in our experimental environment. Several issues have also been reported by other users on its GitHub repository and remains unresolved.

---

Q1: Since the proposed method uses the optimized loss as an OOD detection score, how does the method identify a sample as an OOD sample? Is there a manually set threshold that separates IID and OOD samples?

Thank you for the insightful question. A global evaluation metric AUC is used to assess a model’s ability to distinguish between ID and OOD samples overall. In practical applications, we can estimate a decision threshold based on the ID distribution observed in the pretraining dataset. For example, a score threshold that corresponds to a 5% false positive rate (FPR) on ID samples can be chosen. This threshold can then be used at test time to decide whether a new input is OOD. Notably, the selection of threshold does not affect the evaluation of the model’s OOD detection performance, that is, the threshold selection does not affect the computation of AUC metric.

---

Q2.1: While the paper provides time complexity analysis, could the comparison between the proposed method and other baseline methods be provided?

Thank you for the valuable question. A detailed analysis and comparison of computational complexity between our proposed RedOUT and GOODAT is provided on page 31 in Appendix E7. In addition, we provide a comparative analysis of time complexity for our proposed method and several other representative baselines as follows:

• RedOUT only optimizes a tree encoder with $L$ layers, each being a two-layer MLP with hidden dimension $h$. The total time complexity is $O(L(mh + nh^2))$ per graph.
• GOOD-D updates two GIN encoders with $L$ layers and hidden size $h$. The forward pass complexity is $O(L(mh + nh^2))$ per graph. An additional $O(nh)$ cost arises from the group-space clustering, resulting in $O(L(mh + nh^2)+nh)$ overall.
• GTrans performs optimization over node features and edge structure based on a fixed backbone. The per-graph time complexity is $O(L(mh + nh^2)+md + nd^2 + B'\log B')$, where $B'$ is the number of candidate edge flips.
• AAGOD introduces an auxiliary augmentation scorer alongside the main GNN model with $L$ layers and hidden dimension $h$ that scoring $K$ augmentations per graph. The total time complexity is $O(L(mh + nh^2)+K(nd+m))$.
• GOODAT introduces two masking modules (feature and edge maskers). The time complexity per graph is $O(L(mh + nh^2)+nd + m)$, as it applies learnable masks over node features and edge connections.

Overall, the time complexity of our proposed RedOUT is comparable to that of other baselines.

---

Limitation: The authors have discussed the limitation that the proposed method mainly focuses on graph-level detection. However, I encourage the authors to further discuss the limitations of the proposed method.

Thank you for the suggestion. The current coding tree optimization algorithm relies on the fixed height applied to the whole dataset, without considering the diversity among samples. One potential direction for improving our method is to incorporate an adaptive coding tree height to better extract essential structures in graphs, which we leave as our future work. We will expand the discussion of limitations in the revised version.

We once again thank you for your constructive feedback and valuable suggestions. We will carefully address all the raised points in the revised version.

We sincerely appreciate your thoughtful comments and address your comments and suggestions point by point below.

Q1: Further analysis of baselines and the contribution of this work

Thank you for the suggestion. In Appendix E2, we provide a detailed categorization and discussion of the 18 baseline methods considered in our comparison. These baselines are grouped into 4 categories: Non-deep Two-step Methods, Deep Two-step Methods, End-to-end Training Methods, and Test-time and Data-centric Methods. Additional discussion and comparison with related works are provided in Appendix B. We summarize the key differences and contributions below.

Non-deep two-step methods, deep two-step methods, and end-to-end training methods all rely on training data to modify the parameters of GNN models. Data-centric methods such as AAGOD do not alter pre-trained GNN parameters but still require access to ID training data for post-hoc data augmentation. In contrast, our method is designed for the test-time setting, aiming to improve OOD detection performance without modifying pre-trained models or requiring any access to training data. Although Gtrans and GOODAT are also test-time methods, they requires additional training of graph transformation functions or graph maskers. In our case, the extraction of essential structure is achieved via structure entropy minimization, which is a training-free optimization procedure. We would like to further emphasize that the core contribution of this work lies in the first to extend GIB framework to redundancy-aware disentanglement. Specifically, we propose ReGIB, which effectively removes redundant information and extracts essential structure by jointly optimizing theoretical upper and lower bounds.

Thanks again and we will include further analysis in the revised version.

---

Q2: How to select optimal values for different datasets

Thank you for the insightful question. For the hyperparameter $k$, while the performance may exhibit slight variations, we observe that RedOUT consistently achieves strong results, as illustrated in Figure 4. Specifically, on 5 out of 6 datasets, RedOUT outperforms all baselines regardless of the choice of $k$. Furthermore, compared with GOODAT (which also operates in test-time setting), our method achieves superior performance on all 6 datasets. These results demonstrate that ReGIB can effectively extract essential structural information and eliminate irrelevant redundancy, regardless of the depth of coding tree. For the hyperparameter $\lambda$, we empirically find that values in the range from 1e-4 to 1e-2 lead to consistently effective performance. This robustness reduces the need for extensive hyperparameter tuning, making our method well-suited for practical deployment in real-world scenarios.

---

Q3: Analysis of the computational overhead of coding tree construction on large-scale graphs

Thank you for the suggestion. We provide a detailed analysis of the scaling efficiency of our method in Appendix E7. As shown in Figure 13, the results indicate that from small-scale graphs to larger ones such as the OGB datasets (e.g., ogbg-code2), the runtime and memory consumption of coding tree construction increase nearly linearly with the number of nodes.

We once again thank you for your constructive feedback and valuable suggestions. We will carefully address all the raised points in the revised version.

We sincerely appreciate your valuable comments and are happy to address your concerns as follows:

W1 & Q2: An explanation for the relatively limited performance improvement on the IMDB dataset. Could incorporating node/edge attributes (besides structure) help?

Thank you for the insightful suggestion. In Section 4.5, through a case study, we investigate that the suboptimal performance mainly stems from the highly similar structural semantic information and the shared data source, which makes it challenging even for existing methods to effectively distinguish OOD samples.

For graphs in social networks, which typically exhibit high connectivity and edge density, incorporating node and edge attributes implies huge potential to enhance the model’s representational capacity, beyond the essential structural information we currently extract. However, the current IMDB-B/M datasets do not incorporate node or edge attributes. This is a promising direction that inspires us to take a deep exploration in our future work. We will include further analysis in the revision.

---

W2 & Q1.1: The impact of incorrect pseudo-labels at test time on RedOUT, especially for highly uncertain OOD samples

Thank you for the valuable question. While the pseudo-labels predicted by pre-trained model may contain errors when encountering highly uncertain OOD samples, such errors do not compromise the effectiveness of our redundancy removal mechanism. Specifically, we leverage ReGIB to disentangle the conditional redundant information associated with pseudo-labels in Eq. (6), and optimize the upper bound in Eq. (8) to minimize $I(f(G ^ *); f(G) \mid \tilde{Y})$.

In the general case, we decompose the learned representation as $f(G) \rightarrow{R_1 + Y_G}$ and $f(G ^ *) \rightarrow{R_2 + Y_G}$, where $R_{1/2}$ denotes label-irrelevant redundant information, and $Y_G$ denotes label-related information. Minimizing $I(f(G ^ *); f(G) \mid \tilde{Y})$ is equivalent to minimizing $I((R_1+Y_G);(R_2+Y_G) \mid \tilde{Y}) \rightarrow \min I(R_1; R_2)$.

If the pseudo-label $\tilde{Y}$ predicted by the pre-trained model is incorrect, then $f(G) \mid \tilde{Y} \rightarrow \bar{R}_1 + \bar{Y}_G$ and $f(G ^ *) \mid \tilde{Y} \rightarrow \bar{R}\_2 + \bar{Y}\_G$, where $\bar{R}\_{1/2}$ denotes the residual irrelevant information after removing the wrongly associated label part, and $\bar{Y}\_G$ similarly denotes the remaining label-related information. In this case, minimizing $I(f(G ^ *); f(G) \mid \tilde{Y})$ becomes $\min I(\bar{R}_1 + \bar{Y}_G ; \bar{R}_2 + \bar{Y}_G) \rightarrow \min I(\bar{R}_1 ; \bar{R}_2)$.

Hence, the optimization still targets the irrelevant redundancy and the direction of our objective remains unchanged. Therefore, the effectiveness of our method in removing irrelevant redundancy is not compromised.

---

W3: Scalability of coding tree construction on large graphs

Thanks for your suggestions. We provide a scalability efficiency analysis of our method in Appendix E7. As shown in Figure 13, the results illustrate that from smaller scales to the OGB datasets (e.g., ogbg-code2), the runtime and memory usage scale up nearly linearly with the number of nodes. Furthermore, as shown in Table 10, the time overhead introduced by coding tree construction is negligible compared to the cost of model pretraining and test-time detection.

---

Q1.2: Could the reliance on pseudo-labels amplify noise or bias in the essential view extraction?

Thanks for the question. The extraction of essential information does not depend on pseudo-labels and thus is not subject to such bias. It is derived independently by minimizing the structure entropy in Eq. (12). We will include the additional explanation in the revision.

---

Q3: How sensitive is the framework to the choice of coding tree height $k$ in unseen datasets or new application scenarios? Could an adaptive or data-driven selection of k improve stability?

Thanks for the question. The impact of the coding tree height $k$ on performance is analyzed in Figure 4. We observe that across 5 out of 6 datasets, our method outperforms the baselines regardless of the specific choice of $k$. Notably, compared with GOODAT, which also operates in a test-time setting, our method achieves superior performance across all 6 datasets. This further confirms the effectiveness of our proposed ReGIB in extracting essential structures and removing redundancy, irrespective of the coding tree depth.

Additionally, in light of the variability of test-time samples, an adaptive or data-driven selection of $k$ shows great potential for improving stability. We leave this exploration for future work.

We once again thank you for your constructive feedback and valuable suggestions. We will carefully address all the raised points in the revised version.