Score Propagation as a Catalyst for Graph Out-of-distribution Detection: A Theoretical and Empirical Study

(Connecting to the Q2 above ^ )

• Empirical results. Then we conduct comprehensive experiments comparing the time and space costs of our algorithm with various baselines (both post-hoc and training-based approaches). From the experimental results, it is evident that our algorithm is highly efficient across all datasets.

  • We first present the time(s)/memory(M) of all post-hoc baseline methods consumed over all datasets considered.

    	cora		amazon		coauthor-cs		chameleon
    	time	memory	time	memory	time	memory	time	memory
    MSP	0.03	622.79	0.04	635.41	0.13	1092.05	0.05	634.05
    Energy	0.05	624.10	0.10	636.52	0.11	1094.72	0.11	634.75
    KNN	0.24	630.92	0.13	658.21	0.30	1101.30	0.17	636.44
    ODIN	0.02	621.82	0.05	636.40	0.07	1093.64	0.16	635.41
    Mahalanobis	0.15	627.39	0.22	641.21	0.29	1099.38	0.21	637.18
    GNNSafe	0.06	626.23	0.15	652.80	0.35	1106.19	0.12	637.95
    GRASP	0.05	628.79	0.15	677.26	0.25	1118.02	0.15	644.09

    	squirrel		arxiv-year		snap-patents		wiki
    	time	memory	time	memory	time	memory	time	memory
    MSP	0.05	658.00	0.36	726.59	3.41	4014.22	3.01	9765.80
    Energy	0.12	660.50	0.52	726.17	3.24	4039.91	3.13	9788.45
    KNN	0.14	660.18	3.77	732.90	6241.01	3933.32	273.96	9812.89
    ODIN	0.06	659.58	0.61	727.68	3.61	4005.23	3.00	9760.24
    Mahalanobis	0.19	661.44	1.28	730.41	5.93	4056.08	6.17	9829.16
    GNNSafe	0.10	662.48	0.97	790.20	13.48	4187.67	62.09	9655.11
    GRASP	0.13	668.07	0.68	768.21	13.63	4279.92	218.67	9824.79

  • Additionally, we provide comparison with training-based methods in the literature. It is worth noting that the training-based methods incur substantial time and space costs due to training from scratch, exhibit a significant performance gap compared to our algorithm and therefore are practically infeasible for practical deployment.

    	cora		amazon		coauthor-cs		chameleon
    	time	memory	time	memory	time	memory	time	memory
    GKDE [1]	26.72	3366.01	160.00	3388.59	1004.73	4199.84	37.24	3310.92
    GPN [2]	28.64	3702.57	58.72	3719.10	77.55	3634.66	50.65	3620.97
    OODGAT [3]	77.99	3369.00	395.88	3390.88	411.44	3851.37	182.11	3291.63
    GRASP	0.05	628.79	0.15	677.26	0.25	1118.02	0.15	644.09

    	squirrel		arxiv-year		snap-patents		wiki
    	time	memory	time	memory	time	memory	time	memory
    GKDE [1]	170.26	3234.38	OOT	-	-	OOM	-	OOM
    GPN [2]	50.70	3650.58	444.84	3808.72	-	OOM	-	OOM
    OODGAT [3]	454.62	3319.99	1214.98	3491.11	-	OOM	-	OOM
    GRASP	0.13	668.07	0.68	768.21	13.63	4279.92	218.67	9824.79

We thank the reviewer for the insightful questions! Below we address each of your comments in detail.

Q1. Experiments on large-scale real world data.

We are glad to share with you that we have conducted experiments on large datasets in paper, i.e. arxiv-year, snap-patents, and wiki, which are three large-scale real world datasets reflecting real-world scenarios. Specifically, Arxiv-year has node and edge counts in the order of hundreds of thousands and millions, respectively. Snap-patents features millions of nodes and tens of millions of edges, while wiki, being a large dense graph, boasts millions of nodes and billions of edges. The detailed statistics of these datasets [1] are provided in the following table. We believe these datasets sufficiently meet the requirements of real-world applications. If the reviewer has an interest in other large datasets, feel free to share with us and we would be more than willing to conduct additional experiments on these datasets to further check the effectiveness of our proposed method.

[1] Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao and Ser-Nam Lim. Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods. NeurIPS 2021.

Q2. The time complexity of GRASP and a thorough accounting of computation/memory demands compared to baselines to account for practical deployment.

Great question! We first present the conclusion and then provide the support from both mathmatical and empirical points.

Takeway: Our method's computational footprint in terms of a single propagation’s runtime and memory usage is:

• Time Complexity: $O(N+|\mathcal{E}|+n)$,
• Memory Complexity: $O(N+|\mathcal{E}|+n)$,

where $N$ is node count of the entire graph $\mathcal{G}$ with $|\mathcal{E}|$ edges and subset $G$ has $n$ nodes. Hence, our algorithm has a linear complexity and this makes our method applicable to large-scale networks.

Justification: While our algorithm introduces the fully connected matrix $E$, we adeptly transform the propagation formula to eliminate direct matrix computation between $E$ and the OOD score vector $\mathbf{g}$, resulting in an efficient linear complexity. This can be confirmed by the computational complexity analysis presented below.

• Computational complexity analysis. As described by Equation (5) in our paper, given a raw OOD scoring vector $\hat{\mathbf{g}} \in \mathbb{R}^{N}$, the propagated scoring vector using augmentated adjacency matrix after propagation for $k$ times is given by:

$

 \mathbf{g} \_{GRASP} &= (\bar{A} \_+)^k \hat{\mathbf{g} } 
 = ({D}^{-1} \_+A \_+)^k \hat{\mathbf{g}} = ({D}^{-1} \_+(A+E))^k \hat{\mathbf{g}} \\
 &= ({D}^{-1} \_+A \_+)^{k-1} \cdot (D \_+^{-1}\boxed{A\hat{\mathbf{g}}}+D \_+^{-1}\boxed{E\hat{\mathbf{g}}})   \\
 &= (\text{run $k-1$ times ...}) \\

$

In the above equation, ($a$) $E\hat{\mathbf{g}}$ can be computed with time/space complexity $O(n)$ by a simple summation operation ($\mathbf{g} \_i$ in $G$ will be replaced by $\sum \_{i\in G} \mathbf{g} \_i$ ) to get rid of the matrix multiplication; ($b$) $A\hat{\mathbf{g}}$ can be computed in $O(|\mathcal{E}|)$ with sparse matrix multiplication; ($c$) $D \_+^{-1}$ is an $O(N)$ operation since it is scaling over all elements in the vector. In all, the time/memory complexity of GRASP is $O(N+|\mathcal{E}|+n)$.

(Connecting to the Q2 above ^ )

Based on the above experimental results, we have:

• In comparison to training-based methods, post-hoc methods exhibit significantly lower runtime and memory consumption.
• Considering that the minimum time and space complexity required to run a graph algorithm is $O(N+|\mathcal{E}|)$, as outlined in our algorithm complexity analysis, our algorithm incurs limited additional time and space costs, specifically $O(n)$. This can be validated by the small extra overhead incurred by our algorithm compared to MSP or Energy (8 times n) from the table.
• Compared with training-based methods, our algorithm demonstrates substantially lower time and space demands on three large-scale datasets. And when compared to post-hoc baselines on these datasets, the overhead of our method is also reasonable. The performance of our method on these three large-scale datasets underscores the strong practicality of our approach.

[1] Xujiang Zhao, Feng Chen, Shu Hu and Jin-Hee Cho. Uncertainty Aware Semi-Supervised Learning on Graph Data. NeurIPS 2020.

[2] Maximilian Stadler, Bertrand Charpentier, Simon Geisler, Daniel Zügner and Stephan Günnemann. Graph Posterior Network: Bayesian Predictive Uncertainty for Node Classification. NeurIPS 2021.

[3] Yu Song and Donglin Wang. Learning on Graphs with Out-of-Distribution Nodes. KDD 2022.

Q3. "Why does the theoretical analysis assume that the edges follow a Bernoulli distribution?"

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 [1,2,3].

[1] Luca Franceschi, Mathias Niepert, Massimiliano Pontil and Xiao He. Learning Discrete Structures for Graph Neural Networks. ICML 2019.

[2] Pantelis Elinas, Edwin V. Bonilla and Louis C. Tiao. Variational Inference for Graph Convolutional Networks in the Absence of Graph Data and Adversarial Settings. NeurIPS 2020.

[3] Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang and Neil Shah. Data Augmentation for Graph Neural Networks. AAAI 2021.

Q4. "The impact of other propagation mechanisms, like higher-order diffusion."

Excellent suggestions! We have conducted an analysis of the hyper-parameter $k$ (order of propagation) and its impact on the AUROC, averaged across all datasets using a GCN backbone. Our findings indicate that OOD detection performance benefits from propagation orders within a reasonable range. However, excessive propagation (greater than 10) may be detrimental.

In addition, we have investigated various classical propagation mechanisms, including Personalized PageRank (PPR) [1], Heat Kernel Diffusion (GraphHeat) [2], Graph Diffusion Convolution (GDC) [3], Mixing Higher-Order Propagation (MixHop) [4], and Generalized PageRank (GPR) [5]. The results (AUROC in percentages) demonstrate that GRASP emerges as the most effective propagation strategy in our study.

[1] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then Propagate: Graph Neural Networks Meet Personalized PageRank. ICLR 2019.

[2] Bingbing Xu , Huawei Shen , Qi Cao , Keting Cen and Xueqi Cheng. Graph Convolutional Networks using Heat Kernel for Semi-supervised Learning. IJCAI 2019.

[3] Johannes Gasteiger, Stefan Weißenberger and Stephan Günnemann. Diffusion Improves Graph Learning. NeurIPS 2019.

[4] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing. ICML 2019.

[5] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. ICLR 2021.

Finally, we would like to express our gratitude for the insightful questions raised by the reviewer. We would be more than grateful if the reviewer would like to champion our paper in the discussion phase. Thanks!

We thank the reviewer for the insightful questions! Below we address each of your comments in detail.

1. "Assumption of the intra-edge domination."

We respectfully point out that the reviewer's interpretation of "The proposed method is developed based on the assumption that intra-edges dominate the graph" is incorrect. The intra-edge-domination assumption is only required for the naive propagation method as proved in Theorem 3.2. One of the primary objectives of our algorithm is to address the hard problem of graph node ood detection in heterophilic scenarios, where intra-edges do not dominate the graph.

For instance, on three particularly challenging heterophily datasets—Chameleon, arXiv-year, and snap-patents, the application of naive propagation method leads to a significant performance decline. In contrast, our approach not only reversed this trend but also demonstrates substantial improvement compared to pre-propagation performance. Refer to the table below for detailed results, where the performance values are evaluated on backbone GCN. From the table we can see that our method yields a maxmium performance increase of up to 32.5 percentage points on these challenging heterophilic datasets (AUROC on arXiv-year for MSP). This robustly underscores the effectiveness of our proposed approach.

2. "How does the proposed method perform when faced with structural manipulation and feature interpolation as addressed in GNNSafe?"

Thanks for raising this point! We adopt the "label leave-out" setting since it aligns closely with practical scenarios where OOD data comes from a different class. The other two settings (structural manipulation and feature interpolation) construct OOD data through manual perturbation, which significantly differs from real-world OOD datas. Even if a method performs well on artificially synthesized OOD data, it does not necessarily reflect its real performance in real-world scenarios. Therefore, we exclusively adopt the "label leave-out" setting.

As the reviewer suggest, we also conduct experiments on the two different types of OOD (structural manipulation and feature interpolation) proposed by GNNSafe, and the results (AUROC) indicate that our method still performs well in these different constructed OOD scenarios.

3. "The proposed method may be ineffective when MSP fails, as observed in dataset Squirrel in Table 2."

We would like to share a differing viewpoint from the reviewer. The effectiveness of our method, GRASP, is evidenced through two key observations:

1. As shown in Table 2, GRASP significantly surpasses MSP by a margin of 6.76 in AUROC on the Squirrel dataset using the GCN model. This improvement underscores the benefits of score propagation augmented by our method. Notably, this enhancement is also observed in scenarios where MSP alone is ineffective.

2. On the other hand, the efficacy of our strategy is primarily measured by the extent to which it enhances Out-of-Distribution (OOD) detection performance beyond the initial OOD scores prior to propagation. Among traditional OOD detection methods, the KNN scores achieved the highest AUROC on the Squirrel dataset. However, when our propagation technique is applied to KNN, there is a notable improvement in its pre-propagation performance, as demonstrated in the table below. Furthermore, across all datasets, applying our method to KNN consistently improves performance in terms of both AUROC and FPR95. This consistently better performance across various metrics highlights the robustness of our approach. It is important to note that this improvement is observed even in cases where MSP underperforms.

   	cora		amazon		coauthor		chameleon		squirrel
   	AUROC	FPR95	AUROC	FPR95	AUROC	FPR95	AUROC	FPR95	AUROC	FPR95
   KNN	81.24	72.29	86.01	60.61	91.34	47.99	62.09	93.43	56.74	94.42
   KNN+GRASP	88.23	33.16	95.30	21.43	97.57	8.86	74.44	62.29	58.57	87.96

We are also more than happy to provide more discussion to address the concerns regarding the "MSP reliance" as follows:

1. As proved in Theorem 4.2, the conditions required for our method to work well are easy to satisfy. The chosen node set G only needs to satisfy the condition $|\mathcal{E} \_{G\leftrightarrow S \_{ID}}|>|\mathcal{E} \_{G \leftrightarrow S \_{OOD}}|$.
2. Our method selectively considers data points at the two ends of the score distribution. This selection minimizes the error in selecting $S \_{ID}$ and $S \_{OOD}$.

4. "Why naive propagration seems to work well in heterophily dataset Chameleon?"

We are happy to provide more clarification here. As illustrated in Table 3, on the Chameleon dataset, both MSP and Energy exhibit degraded performance after naive propagation (evaluated using FPR95, where lower values indicate better results). Notably, our proposed method successfully reverses this trend, significantly improving performance. Table 3 provides a clear demonstration of this enhancement.

5. "Why does the improvement of the proposed method over GNNSafe appear to be marginal in homophily datasets, while the improvement is more significant in the heterophily datasets?"

We respectfully disagree with the reviewer's observation. Firstly, our method's improvement over GNNSafe in homophily datasets is not marginal, which can be verified by the results in the following table (Averaged on the three homophily datasets Cora, Amazon and Coauthor). From the results we can see that our method outperforms GNNSafe by 7.10 and 1.62 on FPR and AUROC respectively. Secondly, the more pronounced improvement on heterophily datasets aligns with our theoretical derivation, since the augmentation strategy aims to improve the ratio of "intra-edges" after propagation. Notably, if inter-edges dominate, traditional propagation methods would lead to performance degradation, while our approach successfully reverses this trend, as evidenced by certain results in Table 3.

6. "Hyperparameter sensitive analysis and how to choose $\alpha$ and $\beta$ when MSP’s performance varies in different datasets"

Great suggestions! We conduct a sensitivity analysis of all the hyper-parameters on all the datasets and the averaged results (AUROC in percentages) on model GCN with Energy are displayed in the following table. The performance comparison in the table for each hyper-parameter is reported by fixing other hyper-parameters. From the results we can see that within the range of chosen hyperparameter values, our proposed method's performance does not vary significantly, which constantly outperforms baselines by a large margin.

Dear Reviewer,

We are eager to receive your feedback and any suggestions you might have. The insights from you would be invaluable in enhancing the quality of this work. If there is any additional information or clarification needed from our end, please feel free to let us know.

Thank you once again for your time and consideration. We look forward to hearing from you soon.

Best,

Authors

Thanks for the response that addresses part of my concerns. In your paper, Theorem 3.2 is as important as a theorem presented before technical details, and it is important to motivate and justify your method. However, after I raised my concern, in your response, you are downplaying the importance of it. This confuses me a lot. Also, on squirrel data, the question of why your method is not good is not well-justified for the heavy dependency on MSP to precompute OOD scores. Although you provided results on different types of OODs, and the results show that your method is better, it remains unclear how this experiment is done, and it is unclear if the results are reproducible, since no code is released to reviewers.

Thank you for your valuable feedback! We are pleased that our response has addressed some of your concerns, and we are more than willing to address the additional issues you have.

In your paper, Theorem 3.2 is as important as a theorem presented before technical details, and it is important to motivate and justify your method. However, after I raised my concern, in your response, you are downplaying the importance of it

We respectfully disagree with the reviewer's perspective. Theorem 3.2 indicates that only when intra-edges dominate, direct propagation on $A$ (naive propagation) can enhance OOD detection performance. However, if intra-edges do not dominate, naive propagation does not guarantee performance improvement. The significance of Theorem 3.2 lies in highlighting the limitation of naive propagation, and our method is designed to address this limitation. The experimental results provided in our previous responses serve as empirical evidence supporting these points. Therefore, we do not agree with the reviewer's statement regarding "downplaying the importance of Theorem 3.2." We hope this clarification addresses the reviewer's concerns.

Also, on squirrel data, the question of why your method is not good is not well-justified for the heavy dependency on MSP to precompute OOD scores.

Regarding this point, we would like to provide further clarifications: The results of our proposed method presented in Table 2 (denoted as GRASP (ours) in the "OOD Detection Method" column) are the performance after propagating on the augmented $A$, using the pre-propagated Energy score. Below, we present the performance of MSP, Energy, and KNN before and after using our method respectively. As shown in the table, there is a significant improvement in performance for all datasets when various scores are propagated using our method. Notably, on the Squirrel dataset, the performance of MSP, after using our method, surpasses that of KNN, even when MSP itself is ineffective before propagation (MSP's AUROC is only 48.17 on Squirrel before propagation). This demonstrates the superiority of our method over all baselines.

We hope our explanations can alleviate the reviewer's concerns.

Thank you for your attention!

We thank the reviewer for the insightful questions! Below we address each of your comments in detail.

Q1. "The base model's OOD prediction scores may lead to potential error propagation"

We are more than happy to provide more discussion to address the concerns as follows:

1. We would like to highlight that our augmentation approach will not incorporate error-edges connecting ID and OOD, since we add edges in the training dataset and the augmentation is performed exclusively on in-distribution (ID) data.
2. As proved in Theorem 4.2, the conditions required for our method to work well are easy to satisfy. The chosen node set G only needs to satisfy the condition $|\mathcal{E} \_{G\leftrightarrow S \_{ID}}|>|\mathcal{E} \_{G \leftrightarrow S \_{OOD}}|$. This condition, compared to directly augmenting edges on the test set, allows for a stronger degree of tolerance to errors.
3. Our method selectively considers data points at the two ends of the Maximum Softmax Probability (MSP) distribution. This selection minimizes the error in selecting $S \_{ID}$ and $S \_{OOD}$.

For reviewer's interest, we are happy to provide comparison with an alternative approach -- augmenting edges directly on the test data. Such strategy would lead to severe error propagation, which is known as "confirmation bias". To validate this point, we conduct experiments comparing the effectiveness of "directly augmenting edges on test data" versus "our proposed method of augmenting edges in the training dataset." From the results, we can see that our method has achieved an improvement of nearly 10 percentage points in AUROC compared to the approach of directly adding edges on test data, which supports our assertion.

(Cells' values represent AUROC in percentages on backbone GCN with Energy Score.)

Q2. "Analysis of two hyper-parameters $\alpha$ and $\beta$ is missing"

Great suggestions! We conduct sensitivity analysis of hyper-parameters $\alpha$ and $\beta$ on all the datasets and the averaged results (AUROC in percentages) on model GCN with Energy are displayed in the following table. The performance comparison in the table for each hyper-parameter is reported by fixing other hyper-parameters. From the results we can see that within the range of chosen hyperparameter values, our proposed method's performance does not vary significantly, which constantly outperforms baselines by a large margin.

Q3. "The respective proportions of intra-edges and inter-edges before and after graph augmentation"

Great suggestions! We provide proportions of intra-edges and inter-edges after two rounds of propagations in each dataset before and after graph augmentation respectively in the following table. From the results we can see that the proportions of intra-edges increase after graph augmentation, which lead to improved ood performance, validating the correctness of our theory.

Finally, we would like to express our gratitude for the insightful questions raised by the reviewer. We would be more than grateful if the reviewer would like to champion our paper in the discussion phase. Thanks!