Decoupled Graph Energy-based Model for Node Out-of-Distribution Detection on Heterophilic Graphs

Thank you for your time and effort in reviewing our paper. We very much appreciate your insightful comments and your recognition of our work. We hereby address the concerns below.

In Abstract, the authors argue that GNNSafe has significant performance degradation on heterophilic graphs. However, there is a recent work [1] that has similar consideration.

[1] Ren, Lingfei, Ruimin Hu, Zheng Wang, Yilin Xiao, Dengshi Li, Junhang Wu, Jinzhang Hu, Yilong Zang, and Zijun Huang. "Heterophilic Graph Invariant Learning for Out-of-Distribution of Fraud Detection." In ACM Multimedia 2024. 2024.

We agree with [1] that also considered heterophilic graphs. However, their work differs significantly from ours - they focused on OOD generalization in the context of fraud detection, while we focus on node-level OOD detection.

In Introduction, the authors only analyze the limitation of one recent graph OOD method named GNNSafe. However, as discussed in Section 5, there are many existing graph OOD methods. What are the fundamental research challenges that cannot be addressed by these existing methods?

The fundamentally unaddressed issue for existing graph-based node ood detection methods is that - they rely on homophily assumption. This makes existing works show serious performance degradation in heterophilic graphs. In contrast, our work develops DeGEM showing state-of-the-art performance on both homophilic and heterophilic graphs. In particular, we discuss graph OOD detection along two distinct lines in Related Work (Section 5): 1) graph-level OOD detection ; 2) node-level OOD detection. Among these, the former has received more research attention. Moreover, graph-level OOD detection differs significantly from node-level OOD detection -- in graph-level detection, different graphs can be viewed as following i.i.d. distribution, whereas in node-level settings, nodes are interdependent. This interdependency presents a fundamental and unique challenge for node-level OOD detection, hindering straightforward adaptation of existing methods in other domains. A few works have been proposed to tackle the node interdependencies in node OOD detection. However, all of the existing graph-based methods rely on homophily assumption which cannot deal with heterophily issues for node-level OOD detection.

There are some minors. For example, the text font in tables is too small. It would be better to provide all the source scripts as well as the used datasets and give the anonymous repo link in the text.

Thanks for your suggestion. We will improve the readability of the table in the revision. We follow your advice of providing our code using an anonymous Github link: https://anonymous.4open.science/r/DeGEM\_ICLR2025\_rebuttal-B801/README.md, and we have attached the anonymous link in our abstract.

Thank you for your time and effort in reviewing our paper. We very much appreciate your insightful comments and your recognition of our work. We hereby address the concerns below.

More detailed explanations are needed regarding the state-of-the-art performance on homophilic graph datasets. The paper introduces specific components designed to address the heterophily phenomenon in graph datasets, which lead to their effectiveness on heterophilic datasets. However, it remains unclear why these components are also beneficial for homophilic data. Providing a rationale or theoretical basis for this performance would strengthen the paper's quality.

We clarify that the components we have proposed are applicable to general graphs, including both heterophilic and homophilic graphs. Our focus is on heterophilic graphs, where previous work has performed poorly, leaving substantial room for improvement. Specifically, we suggest training Energy-based Models (EBMs) by Maximum Likelihood Estimation (MLE), this can enhance the modeling ability of any data distribution for constructing better OOD detection. Moreover, the proposed MH Graph Encoder can adaptively extract both local and global information. In homophilic graphs, the learned model will focus more on local neighbor nodes. However, in heterophilic graphs, the learned model extracts more useful information from distant but similar nodes. Thus it improves the learned representation in both homophilic and heterophilic graphs.

Given the paper’s focus on heterophilic graphs, it would be helpful to include experiments that analyze how varying levels of heterophily affect model performance. This could be similar to Figure 2 in [1], which explores performance across different heterophily levels, offering valuable insights into the model's adaptability.

[1] Zhu, Jiong, et al. "Graph neural networks with heterophily." Proceedings of the AAAI conference on artificial intelligence. Vol. 35. No. 12. 2021.

Following your advice, we conduct additional experiments on varying the homophilic ratio. The synthetic graphs are constructed following [1]. We report the AUROC results on synthetic-Cora below, and we use the Feature OOD setting.

As the homophilic ratio decreases from 1.0 to 0.0, the performance of GNNSafe drops significantly from 79.12 to 69.02. In contrast, DeGEM consistently maintains a high performance across homophilic ratios, achieving around 99 in most cases. This indicates that GNNSafe struggles to handle heterophily, whereas our proposed method demonstrates strong performance on both homophilic and heterophilic graphs.

It appears that the uncertainty estimation methods proposed in previous GNN literature [1, 2] could also be applied for OOD node detection. Would it be possible for the authors to consider including these methods as baselines?

[1] Huang, Kexin, et al. "Uncertainty quantification over graph with conformalized graph neural networks." Advances in Neural Information Processing Systems 36.

[2] Hart, Russell, et al. "Improvements on Uncertainty Quantification for Node Classification via Distance Based Regularization." Advances in Neural Information Processing Systems 36.

Yes, uncertainty methods can also be used for node OOD detection. In our paper, we have included two uncertainty-based baselines: GKDE and GPN. We are glad to provide additional uncertainty baselines. Due to time limitations, we conduct experiments using [2] as an additional baseline, which is a stronger variant based on GPN. And the results for homophilic/heterophilic graphs are shown below respectively.

 |   82.21   | 81.00  |  88.06  | 78.80  | 91.73  | 91.77  |    97.00     | 79.38  |  86.65  | 63.84  | 94.99  | 91.00  | 84.29  | 76.79  | 78.20  | 60.29  |   OOM  |   OOM  |   OOM  |   OOM  |   OOM  |   OOM  |

| GNNSafe | 87.98 | 75.30 | 92.18 | 75.40 | 92.36 | 88.92 | 98.69 | 93.74 | 98.47 | 92.96 | 97.34 | 95.72 | 51.00 | 79.08 | 82.93 | 66.18 | 67.27 | 69.20 | 79.02 | 54.26 | 88.73 | 80.31 | | DeGEM | 99.93 | 84.20 | 99.84 | 84.30 | 97.58 | 93.04 | 100.00 | 94.49 | 99.91 | 93.97 | 99.28 | 95.80 | 94.83 | 97.36 | 94.76 | 64.51 | 81.30 | 86.00 | 86.01 | 58.20 | 97.08 | 83.56 |

It can be seen that compared to [2], our method achieves consistently better performance across homophilic and heterophilic graphs.

Thank you for your time and effort in reviewing our paper. We very much appreciate your insightful comments and your recognition of our work. We hereby address the concerns below.

While the paper includes some ablation studies, it does not discuss independent contributions from specific components such as the Multi-Hop encoder, Energy Readout, and Conditional Energy modules. Further independent testing of these components is recommended for future research.

Thanks for your suggestion. We have evaluated +MH (Row 6 in Table 4), +MH+CE (Row 7), and +MH+ERo (Row 8) in the original paper. We mainly evaluate the effectiveness of each component by adding it one by one. We believe this already could indicate the effectiveness of each component. There are many existing works that also evaluate their components by adding them one by one in the ablation study ([a,b,c,d]).

However, we are also glad to provide additional ablation study of +CE, +ERo, and recurrent update (+CE+ERo). We would like to indicate that the CE and ERo should be used together to construct the recurrent update for enhancing performance. We refer to the model that incorporates DGI and MLE (Maximum Likelihood Estimation) for learning energy based on GCN as the base model. The detailed ablation results are shown below.

The results clearly show the effectiveness of the MH graph encoder and Recurrent Update.

[a] LSGNN: Towards General Graph Neural Network in Node Classification by Local Similarity, IJCAL 2023.

[b] Graph Self-supervised Learning with Accurate Discrepancy Learning, NeurIPS 2022.

[c] Analyzing and Improving the Image Quality of StyleGAN, CVPR 2020.

[d] Text Is MASS: Modeling as Stochastic Embedding for Text-Video Retrieval, CVPR 2024.

Although the decoupled design reduces dependency on graph structure and improves computational efficiency, could the introduction of multiple components (such as GCL, conditional energy, and recurrent updates) make the model structure overly complex? Could future versions simplify key components to reduce implementation difficulty?

We will work on simplifying this model in future work. However, we would like to highlight that, these components can be easily implemented in practice. For example, the GCL algorithm we used is plugged into our backbone model without lots of effort. Additionally, the design you mentioned does not occupy much running time. For example, from Table 7 in the Appendix, the running time of GCL only contributes to 6% of total time consumption.

Thank you for the response. Based on the replies, I would raise my score.

Thank you for your time and effort in reviewing our paper. We very much appreciate your acknowledgment of our motivation and the strong experiment results. We hereby address the concerns below.

The argument that existing works on out-of-distribution detection resort to energy function independent for each node is arguably not true. There is a recent paper [1] that considers Dirichlet energy and extends the node-wise energy-based modeling for accommodating the neighborhood information in the graph. [1] Graph Out-of-Distribution Detection Goes Neighborhood Shaping, ICML 2024.

There may be some misunderstanding here. We do not argue there is no work considering node dependence in energy modeling. In contrast, we acknowledge that GNNSafe has considered the node dependence by energy propagation. We have revised the text to clarify this distinction more effectively. Hope this makes things clearer. We attach the abstract involving modifications below, with italics indicating newly added portions:

Despite extensive research efforts focused on Out-of-Distribution (OOD) detection on images, OOD detection on nodes in graph learning remains underexplored. The dependence among graph nodes hinders the trivial adaptation of existing approaches on images that assume inputs to be i.i.d. sampled, since many unique features and challenges specific to graphs are not considered, such as the heterophily issue. Recently, GNNSafe, which considers node dependence, adapted energy-based detection to the graph domain with state-of-the-art performance.

Is there any intuition why the proposed model can address graph heterophily?

This is because we abandoned the inductive bias of homophily assumption. Specifically, we removed the energy propagation used in GNNsafe to avoid the severe decrease in performance on heterophilic graphs. Additionally, we introduced MLE to train the Energy function, improving the model's expressive ability so that our model is more powerful in OOD detection; and the Multi-Hop (MH) Graph Encoder can extract information from neighbor nodes to distant nodes. Since similar nodes often lie in the distance in heterophilic graphs, combining both local and global information can bring benefits in addressing heterophilic issues. We also introduced Conditional energy, which allows us to use global and local information in energy calculation, further alleviating heterophilic information. These performance-enhancing components for OOD detection do not rely on the homophily assumption, thus enabling our method to achieve state-of-the-art performance on heterophilic graphs.

The proposed model is computationally expensive, and more justification on the necessity of the proposed components that complex the model is needed. More justification on the necessity of the proposed components that complex the model is needed.

Overall, our model's AUROC largely outperformed previous graph-based state-of-the-art (GNNSafe) by 26.33% on average among all graphs, while requiring less than 7% additional training time cost on average. In fact, it is common by trading computational cost for performance improvements in the community. For example: 1) There is a well-known technique called Sharpness-Aware Minimization (SAM) [a] that doubles the computational cost at each training iteration while bringing about 1%-2% accuracy improvement in image classification. 2) The famous generative model - Diffusion [b], which has thousands of times higher inference cost in its original formulation compared to the previous SOTA generative model GANs, but achieves superior performance.

[a] Sharpness-Aware Minimization for Efficiently Improving Generalization, ICLR 2021.

[b] Denoising Diffusion Probabilistic Models, NeurIPS 2020.