Uncertainty Estimation on Graphs with Structure Informed Stochastic Partial Differential Equations
Authors: Fred Xu
Thomas Markovich
Venue: NeurIPS 2025 poster ()
Keywords: Graph Neural Network
Uncertainty estimation
Stochastic Differential Equations
Primary area: general_machine_learning

Abstract: Graph Neural Networks (GNNs) have achieved impressive results across diverse network modeling tasks, but accurately estimating uncertainty on graphs remains difficult—especially under  distributional shifts. Unlike traditional uncertainty estimation, graph-based uncertainty must account for randomness arising from both the graph’s structure and its label distribution, which adds complexity. In this paper, making an analogy between the evolution of a stochastic partial differential equation (SPDE) driven by Mat\'ern Gaussian Process and message passing using GNN layers, we present a principled way to design a novel message passing scheme that incorporates spatial-temporal noises motivated by the Gaussian Process approach to SPDE. Our method simultaneously captures uncertainty across space and time and allows explicit control over the covariance kernel’s smoothness, thereby enhancing uncertainty estimates on graphs with both low and high label informativeness. Our extensive experiments on Out-of-Distribution (OOD) detection on graph datasets with varying label informativeness demonstrate the soundness and superiority of our model to existing approaches.

Uncertainty Estimation on Graphs with Structure Informed Stochastic Partial Differential Equations
Fred Xu Block Inc University of California, Los Angeles fredxu@squareup.. com,
Thomas Markovich
Block Inc tmarxovvictosqqareupp.com com
Abstract
Graph Neural Networks (GNNs) have achieved impressive results across diverse network modeling tasks, but accurately estimating uncertainty graphs remains difficult- especiillly under distributional shifts. Unlike traditional uncertainty estimation, graph-based uncertainty must account for randomness arising from both the graph's 's structure and its label distribution, which adds complexity. In this paper, making analogy between the evolution of stochastic partial differential equation (SPDE) driven by Matérn Gaussian Process and message passing using GNN layers, we present principled way to design novel message passing scheme that incorporates spatial-temporal noises motivated by the Gaussian Process approach to SPDE. Our method simultaneously captures uncertainty across space and time and allows explicit control over the covariance kernel's smoothness, thereby enhancing uncertainty estimates graphs with both low and high label informativeness. Our extensive experiments on Distribbiiitin (OOD) detection on graph datasets with varying label informativeness demonstrate the soundness and superiority of our model to existing approaches.
Introduction
Uncertainty Estimation is crucial to developing reliable machine learning systems, now deployed in safety-critical fields such healthcare [15], medicine (2), and financial modeling [14] This task usually handles uncertainty from the lack of data samples and the inherent randomness in the data generating process [13] and has traditionally been addressed for i.i.d data using energy based models [4]. Bayesian learning framework [6]. or stochastic process to inject random noise into model learning 22 Already a challenging problem, Uncertainty Estimation when applied to graph data, requires even more consideration on the dependency between nodes and even substructures on graph. For graph data, Graph Neural Networks (GNNs) have been the standard model, leading state-of-art performance on many graph related learning tasks. By aggregating information from neighbors, GNNs are able to learn meaningful representations of nodes efficiently 21 [50) Despite their superior performance, GNNs can generate overly confident predictions tasks even when making the wrong predictions [45] Recently many works have attempted to address uncertainty estimation for graph data in the similar manners i.i.d data, using the Bayesian framework [45), energy based model
55) or through injecting noise model training using a stochastic process 26 3]. Despite some
remarkable progresses, these models assume that nodes that are close-by in the graph should share
similar uncertainty, which often connects to the concept of graph homophily [55] 26 However, in cases such as low label informativeness [35), nodes that close to each other often have different labels distribution patterns, resulting in the phenomenon that knowing the neighborhood labels doesn't t decrease uncertainty of center node's 's label. B2] When graphs exhibit low label informativeness, tasks like node classification become more difficult for traditional GNNs, and so is uncertainty
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

F(H)33)
P(PEE)))
= uegggg
K DOCAj
Cousscen labels
Nods Cassss Clss Class 1
o(aret)
6(M())
High Matum cur corrdation
0
(a) Matérn Kernel on a Heterophilic Graph
(b) Structure Informed SPDE
(a) Graph Matérn kernel with varying degrees of smoothness for low v, the Gaussian random field is rough, with higher variance for each node and higher correlation between nodes. Red links are high correlation edges that do not exist in the original graph. (b) Our proposed Structure Informed SPDE (SISPDE) to incorporate spatial correlations between node uncertainty (section 3): Gaussian noises between nodes correlated according to the Matérn Gaussian Random Field.
Figure 1:
estimation: when labels that are close by are uninformative, GNNs that are poorly calibrated either generate incorrect predictions with high certainty or cannot capture the pattern all 36 35)
This potential difficulty has not been addressed by previous works but has been raised by many existing works as future directions (55] 26 12] In this paper, we directly address this challenge by proposing message passing scheme on GNN that explicitly models the dependency between uncertainty of nodes through a correlae stochastic partial differential equation (SPDE) (Figure b)) [6] In particular, we extend the basic framework of Q- Q--Wie process from [26. which uses the graph Laplacian to model spatial correlation, a Matérn Gaussian process on graph [4. With this construction, we can explicitly regulate the smoothness of the spectrum used to represent the Brownian motion on graph, creating covariance structures that can capture long-distame dependencies between uncertainties of nodes. We further provide theoretical analysis for the construction and demonstrate the existence and uniqueness of mild solution the underlying SPDE, We conduct extensive experiments on Out-of-Distribution (OOD) Detection on 8 graph datasets with varying degrees label informativeness to demonstrate our model's effectiveness.
The main contribution of this paper are: (1) we introduce physics-inspired way to perform message correlated noise improve uncertainty estimation, even under low
passing on graph with label- inneliinfommaieeesss.. (2) We extend the Q- Q-Wiener process graph to smoothness soathness--relltteed spatially- correllted noise process and analyze its property and the theoretical implication for the underlying stochastic process on graph. (3) We provide an efficient implementation of this general framework, conduct extensive experiments on standard uncertainty estimation tasks, and provide detailed ablations and visualizations for the properties of designed covariance structure. Empirical results and thorough analyses demonstrate our model's novelty and superiority compared with previous approaches.
2 Background
2.1 Uncertainty Estimation on Graph Data
Let G (V, EV) be graph, where V is the set of vertices and F. the of edges, then semi- supervised node classification problem can be formulated by (1) partitioning the graph nodes: T are the set of nodes with labels and u E l/ are the set of nodes without
V= UUUZ H. where labels, and (2) train GNN model to predict the labels of u E UI using the final node features after rounds of message passing. Denote node features as X and (T) as feature after rounds of message passing, then the classification results depend on P(y HT)). Traditionally, predictive uncertainty be measured by (a) adopting energy- based model perspective [55] [2] the

---

classifier, (b) formulating Bayesian perspective and compute the entropy of the posterior predictive distribution [4)], and (c) formulating the message passing GNN as a stochastic process and compute an expected Shannon entropy H [[[[p( H(T))]] In this paper, we investigate approach (c), which allows for principled design of GNN architecture and explicit modeling of both aleatoric uncertainty and epistemic uncertainty through (TH(T)) and I. ((H(()))) (P(y H(]))]], respectively [2] 26
2.2 Label Informativeness
Traditionally for node classification tasks, graph datasets were divided into homophilic and het- erophilic datasets, where similar nodes are more likely to be connected in the former and less likely to be connected in the later case [31]. While it occurred that classical GNNs perform poorly on heterophilic datasets, it has been recently discovered that fine-tuning can address the issue without relying on heterophilie--peciin methods 31 35 36), leading to design of metrics that better charac- terize node classification difficulty. Among the newly proposed metrics, Label Informativeness (L.) leverages the mutual information framework and better characterizes the structural distribution of graph labels. For two nodes i, E V and their label random variables Vis Mjj LI is defined as:
LI = ()), (v.) = (yx) H(v 95)
(1))
where / is mutual information and H Shannon entropy. Compared with homophily, edge-wise LI can better account for classification difficulty and naturally incorporates multiple types of heterophilic patterns [35]. Using entropy and mutual information, LI provides not just a metrics of classification difficulty, but also of predictive uncertainty: intuitively, when label informativeness is low, predictive uncertainty of center node doesn't 't decrease even after knowing the label of the neighbors, indicating low correlation between the center node's ' predictive uncertainty and the predictive uncertainty of neighbor nodes. This suggests that modeling the spatial correlation between nodes can serve as a prior for graph's label informativeness, and we argue that it is crucial to model not just uncertainty of each node, but also their correlations.
2.3 Graph Stochastic Partial Differential Equation
The analogy between Message Passing Neural Networks and Partial Differential Equations (PDEs) has been widely explored, with pioneering work in PDEGCN [10] and GRAND [5], which systematically defined differential operators on graph. For the node feature X and its corresponding node embedding H on graph, GRAND (S) formulates message passing using the diffusion equation:
@H(t) (iv (VH), Ot
Øx = AGG(X, ()X). In this formulation, G is which closely follows the anisotropic heat equation कt GNN layer while is the continuous index for layers of the GNN, and the entire message passing that updates node features can be written as an integral equation. Later on, to better account for uncertainty, Graph Stochastic Neural Diffusion (GNSD) 266 expanded this formulation into the stochastic diffusion equation, a class of stochastic partial differential equations [
dH (t) f(H(t)) dt + g ((()))W(())) (t),
(3)
where the Brownian motion W (L) is defined using the spectral basis of the graph Laplacian, using the finite dimensional analogy of the KLrv expansion:
VI
W(t) Σ Bet)
(4)
where (A) {ux 1== are the eigenvalues and eigenvectors of the graph Laplacian, and (t)
[V]
l==
are independent zero-mean Brownian motion on each node. In particular, (26) showed that the noise process is a Q- Q-Wiener process, which converges in the asymptotic regime in the L sense, and the process has stationary increment of the form (()) (s)) ~ Ao (I 8) s)Q), where Q is trace class operator and defined to be the graph Laplacian in the finite case. The SPDE in the form of equation 3 suggests a message passing scheme on GNN, where noises are injected independently for each graph nodes, which better accounts for alcatoric uncertainty of the data.
3

---

2.4 Graph Matérn Gaussian Process and SPDE
Generally, stochastic partial differential equation (SPDE) describes a spatial-temporal stochastic process driven by spacetime noise process (x,, 4). When time is fixed, the object W ((x) is Random Field, whereas if fixed, we obtain classical stochastic process [16]. Under regularity conditions, Gaussian process can be formulated as the mild solution to SPDE system [4]. with its covariance structure derived from the underlying Brownian motion. In particular, when the spatial domain is a graph, [4] showed that Gaussian process can be defined over the graph nodes, using the spectrum of the graph Laplacian matrix to form the covariance kernel. Specifically, given the spectral decomposition of the Laplacian matrix A UAU
define matrix function Φ: | - IR | (A) := U (T)(AAU" can be used to define a fractional diffusion operator, where ((A) diag((o())). ... , }) scalar transforms the eigenvalues with scalar function 6. When driven by standard Gaussian W ~ (O, I), the diffusion equation generates spatially correlated Gaussian process. Using the general result from [54] that formulates the Matérn Gaussian process as the mild solution of class of diffusion type static SPDEs, 4 proposed the family of Matérn kernel and the associated Matérn Gaussian process on graph:
2v x2
V/2
. f~N E~N(0,
( (0.(" 2v (0.0 R2
(A) =
+
(5)
where v4 >> 0 are spatial scaling parameters and f V + R' can be seen random field defined on the graph domain. This formulation provides a framework to model the smoothness of spatial correlation structure for noise on graph. When is large, the noise process is smooth, with low covariance overall, whereas if v small, the noise process is rough, resulting in long distance dependencies. A visualization of Matérn kernel on a synthetic graph can be found in Figure Ta))
Method
In this section, we first design general spacetime noise process on graph using Gaussian Random Field and Brownian motion. Based on this general design, we propose spectral formulation of the noise process and discuss the design of the spatial covariance kernel. We formalize the findings in four theorems and provide the detailed proof' in Appendices. We then provide an efficient graph neural ODE implementation and a learning framework to handle uncertainty estimation.
3.1 W-Wiener Process on Graph
In GNSD[26), the authors adopted spectral perspective and proposed to represent the spacetime white noise using the graph Laplacian. Although the construction is a valid Q- Q-Wiener process, lacks rich spatial structure: the noise process defined in GNSD corresponds to Gaussian Random Field whose spatial covariance kernel is the Laplacian Matrix.
Let G = (V, E) be a graph and j,j E V, then the Q-Wiener process defined in Equation 4 results in spatial covariance structure of Cov(W, (,()) = Aiyl.
Proposition 1.
While this result provides some degrees of spatial correlation between noise on graph nodes, doesn't 't provide mechanism control for kernel smoothness, important prior when dealing with label distributions, limiting the kind of uncertainty that may be encoded in the graph structure and potentially harming the performance of uncertainty estimation on graph. To overcome this issue, we propose a more flexible way to encode graph structure by directly modeling the spatial correlation pattern covariance kernel. To facilitate this construction, we propose the following definition:
Definition 1. (Graph Gaussian Random Field) Let G EV,E) be undirected graph and A its graph Laplacian, then Graph Gaussian Random Field is multivariate Gaussian random variable with its positive definite covariance matrix K (A(AUUZ where A UAUT is the spectral decomposition of the graph Laplacian, and & represents a matrix-valued function that applies scalar function to each element of the diagonal matrix A.
This is Gaussian random variable that directly models the correlation structure between graph nodes. In 4. when & equals the transformation in equation 5 a Matérn Gaussian process can be obtained. Denote & the matrix functional form of é, which corresponds to element-wise transform of matrix

---

element using o, we propose the following definition for apatially-correlate Wiener process on graph induced by the function Φ:
Definition 2. (+- Wieeer process on graph). Lei G = EV, be undirected graph and A its graph Laplacian. Let {ur J é b:R: IR + IR be a scalar function with & its matrix functional form, then Φ --Wiener process is defined by the (truncated) Karhunen-Loeye expansion:
VVI fe be its eigenvectors and eigenvalues, respectively, and let
MV]
W(t) = E v (x
(6)
where {B<(0)}kr are independent Brownian motions on each graph node.
Compared with the construction in 266 (Equation 4. we explicitly introduce a covariance structure between nodes using the function c. This construction has the following property:
Theorem 1. Let G = E),, and A its graph Laplacian with A = UA then for the construction
in definition 2 the matrix K ( is positive definite, then the spatial-tepprra covariance
of noise process on two nodes j. k can be written as Cov(W,(t) (t), Ws(s) = (t A Kss, where
(t A s) = min(t, s), and (t) W (s) NO, (t K) for t >
Sketch Proof. The result follows from the orthogonality of the eigenvectors of the graph Laplacian and the fact that Wiener processes are cero-centered with correlation structure of Cou Cou(W (t). W W(s)) min(t, s) and (t) (s) ~ NN t s) for t 8.
In the asymptotic regime where [V + oc, the process generalizes to be a space-time time noise process with the following property (proof in Appendix A.5):
Theorem 2.
Let H be a separable Hilbert space and (D, P)) a filtered probubility space. Let Q' be trace-class operator in H and & function operator that scalar-trant transforms the eigenvalues ((;)
< OC, the induced 4 --Wiener process is Q- D-Wiener process with the trace class operator Q = (QQ). Moreover, the transformation for Matérn kernel induces a Q- R-Wiener process when v > d for a random field taking value in compact C Rd.
{&e of Q', then E /
The covariance structure derived in theorem implies that the - g-Wiener process constructed in this way more expressive than the Q-Wiener process constructed in [26., and the condition outlined in theorem provides the framework to reason about the solution of SPDE driven by such a noise process, which we highlight in theorem in the section below.
3.2 Structure Informed Graph SPDE
Aside from the theoretical construction, we propose that the design of function T should depend on the underlying graph structure and label informativeness. In the context of graph node classification, various previous works [55] 26] assumed that nodes that are connected to each other should have similar uncertainty. However, for graphs with low label informativeness, knowing the labels of neighbors does not decrease of entropy for the center node [1]. This suggests that far-apart nodes can exhibit similar uncertainty patterss, while the magnitude of noise between neighboring nodes can vary greatly. In the language of Graph Gaussian Random Field[]] this means a slowly decaying covariance between two nodes that are far apart. To incorporate this insight, we propose to carefully design ó using the Matérn Kernel in Equation 5 In this case, the choice of y is crucial, for high values of v indicate smooth and hence short-range dependency, whereas low values of D a rough and hence long range dependency. The SPDE driven by the Gaussian process with the Matérn kernel message passing scheme to address the distribution of uncertainty in both cases.
can then be used We summarize the theoretical property of this SPDE in the following theorem:
Theorem 3. Let H be a separable Hilbert space, and Ft, be a filtered probability space and W(x,t) t) be a Fr-adapted space-time stochastic process whose spatial covariance kernel is given by the Matérn kernel square-inteed square-integrable and Fo re-maasura,le, the SPDE of the form:
closed and bounded domain D c Rd, then if > d and H(O) is
dH(I)= (CH(I) + F(H())) + ((H()))W())
5

---

admits unique mild solution:
H(t = =xp((())(O) + J. exp((t-s)))
J: expl(t - ()) (s), (8)
where C is bounded linear operator generating a semigroup exp(tC) and F, G are global Lipschitz functions.
This theorem holds generally even when the noise process dW, is not a Q-Wiener process [Chapter in [16) [41]]. In section provide empirical results for the choice of v. In the section below, provide an alternative formulation using the mollifier proposed in 41 and present our neural architecture incorporating the structure aware graph SPDE.
Remark 1. (Expressiveness)) Our proposed Structure Informed Graph SPDE is more expressive than the PDE formulation in GRAND [5] because of the additional noise term. It is also more expressive than GNSD (26], which corresponds to the special case where & is the identity transformation. 7 which uses deterministic forcing, our model uses stochastic forcasiiicoorcing
Compared to GREAD
3.3 Practical Implementation: Graph ODE with Random Forcing
For the SPDE of the form 7 its solution can be written with a mollifier W = 1f * W, where & is a
smooth test function and the convolution operator [1] 41 20). The solution then can be written as randomly forced PDE:
(t)) = exp(t())(()) + I. exp ((t (D=s)c) ((H(()) (F)((((())))) + G(H(s)),.)
where & W is noise process that serves as mollification the underlying Wiener process. From the classical theory of Wong-Zakai approximation [49], this construction ensures that for SDEs, the sequence of random ODEs driven by the mollification of Brownian motion converges in probability to limiting process independent from the mollifier. In [4]), it is defined colored noise when We is a Q- process and white noise W, is a cylindrical Wiener process. The corresponding neural architecture consists of modeling the semigroup exp(t.) using convolution kernel, as done in [41] which in our case is Graph Neural Network (24). and the functions F, G are MLPs. The first step therefore performs graph convolution and the resulting architecture is Graph Neural ODE 37 with a spatially correlated, temporally stationary Gaussian process injected at each time step:
(t) ODESolve(GNN, Ve,e, (0,
(10)
where the integrand has the form:
V (H())) GNNO GG (H(()))
(11)
& ~ N 0,
(0
2v + A)
(12)
We simulate the Multivariate Gaussian distribution & using the Cholesky decomposition on the Matérn covariance matrix graph [4]. For graphs with large number of nodes, performing an eigendecomposition on the Laplacian matrix is prohibitively expensive (O(IV))), so we adopt Chebyshev polynomial approximation of the Matérn kernel 88. in which case we avoid Cholesky decomposition and directly use the following expansion to approximate the kernel matrix:
Approximating the Matérn Kernel:
2v x +
(2)
(13)
where ) are Chebyshev polynomials up to degree m and {cr {m are Chebyshev coefficients determined by d(x)= = (2v/k² + xr-",, and Â is the rescaled graph Laplacian, resulting in O(m E)) complexity. We summarize the theoretical property of this approximation in the theorem below:
Theorem 4 (Chebyshev Approximation of Matérn kernel). Let G = (V, E) be graph, and let the Matérn kernel on graph be defined in equation
5 then the Chebyshev approximation in equation my
where m is the degree of the Chebyshev polynomial and dmow is the maximum degree of the graph.
13 results an error bound of O
((
kidd 16 (
x² xddmar

---

We provide the technical proof for this theorem in Appendix B. Intuitively, for large v. which indicates smoother covariance structure, the error rate decays exponentially with respect to the degree of the polynomials. For model training. we adopt the distributional uncertainty loss used in (26), which relies on the predictive distribution of the final state H(T):
Lyy 9) (P(HT)))(CCC
X, G). H()))
(14)
where H is the Shannon entropy. In the experiment section, we investigate the choice of parameters v, which controls the roughness of the Gaussian Random Field.
4 Experiments
In this section, we conduct extensive experiments to demonstrate the capacity of our model: in section 4.1, we demonstrate model performance on -fist--distribution (OOD) detection on semi-supervised node classification task under the influence of label, feature, and structure shifts, on both low LI and high LI datasets. In section 4.2, we examine the impact of kernel smoothness parameter v on model performance with respect to label informativeness. In section 4.3, we provide graph rewiring perspective on stochastic message passing. We provide comprehensive comparisons with previous works, especially with GNSD for OOD detection tasks. Additional experiment details for hyperparameter search, visualizations, and results can be found in Appendix C.
4.1 OOD Detection
We evaluate our model's capacity to model uncertainty for graph data using the task of Out-of- Distribution Detection (OOD) for node classification. This task involves training the models using node classification task, while reporting the OOD Detection performance at test time. To highlight the effectiveness of modeling the spatial patterns of noise, we experiment on graph datasets with varying label informativeness. This includes heterophilous / low LI datasets [36] (Roman Empire, Amazon- Ratings, Minesweeper, Tolokers, and Questions) and high LI datasets (Cora [30] Citeseer 43], and Pubmed (34] ). Details of dataset LIs can be found in Appendix C. For each dataset, we perform following three types of distribution shifts, similar to previous works 26 55
Label-Leave-out: We treat a subset of class labels as OOD and leave them out of training. For the common benchmarks, we follow the approach in [26] and leave the class with partial labels as the OOD class. For the heterophilous datasets, we use the last class label as the OOD class for Minesweeper, Tolokers, and Questions, and more labels for Roman Empire and Amazon Ratings for more balanced distribution. We list the detailed label assignments for each dataset in Appendix C.
we follow [55] by using original graph as in-distribution data and applying stochastic block model to randomly generate a graph for OOD data.
Structural Perturbation:
Feature Perturbation: we follow 26 55 and use the original graph as in-distribution data
while perturbing subset of nodes' features with Gaussian noise generate OOD samples.
Baseline Models: we compare our model with non-graph models specifically designed for OOD
detection (ODIN 25 MSP 17,. Mahalanobis (3 (E(8), GNN-based OOD models (GCN2I)
GNNSafe 55) GOLD 52
GEBM [2),, and stochastic message passing based model (GNSD 26) ).
We also add a special case of SISPDE-RBI to compare the Matérn kernel agains the smooth RBF kernel. We focus on the case where the OOD labels are not available during training, making our approach more general than the scenarios in (55] 45). which rely on existing OOD labels to help with the OOD detection task. In this OOD scenario, the model sees the normal and learns what the normal looks like at training time and detect the abnormal at test time from normal and abnormal samples. Some previous works have explored the case of OOD samples exposure during training time, which allows them to further the gap between IND and OOD sample's 's entropy or energy function, but in case we choose to handle the more general scenario of no OOD exposures during training. For more recent datasets that previous works have never been run on, we conduct hyperparameter search for some of the more recent baseline models using the search space provided by them.
Evaluation Metrics: In order to study the capacity of the model to detect OOD samples, we formulate the problem binary classification task and quantify the performance using detection accuracy
7

---

(DET ACC), AUC, and FPR95, where larger values for DET ACC and AUC means better OOD detection performance, whereas smaller value FPR95 indicates better OOD detection performance. In Table D we report the results of baseline models on all the datasets, with each metrics reported as mean std over runs with different seeds. We use green and orange signify the best performance and the runner-up performance.
Model Rankings by Metric
DET-ACC
FPR95
Average
SISPDE
GNSD
GNNSafe
GRBM
91SPOR-ROR RaP
GOLD
MSP
Mahalanoble
GCW
Odin
Model
(a) Average Rank of Model for each metrics
Average best by Dataset
18.33
Low High LI
Average best V
14.67
15
9.33
1.30
0.97
0.57
citeseer
cora
pubmed
roman empire
minesweeper
amazon ratings
tolokers
questions
(b) Best value of v for each dataset
Figure 2: (a) Average rank of metrics for model on all graph datasets in Table [ (b) Comparison of smoothness parameter on each dataset. Here plot the average over the three cases (label, structure, feature) for each dataset.
Summary of Results:
The results of the experiments be found in Table 1 Of the 72 results, model (SISPDE) achieves the best result or the second best 71 cases (98.6% of all experiments). In particular, it performs the best in 50 cases (69.4% of all) and the second best in 21 cases (29.2% of all), demonstrating our model's consistent and superior performance not just on homophilic datasets with high label informativeness (Cora, Pubmed, Citeseer) but also on heterophilic datasets that have low label informativeness (Roman Empire, Minesweeper, Questions, Tolokers, Amazon Ratings). Compared to GNSD, which assumes smooth covariance kernel, our model achieves better performance in 26 of the 27 cases (96.2% of all) for data sets with high LI and 45 of the 45 (100% of all) for datasets with low LI, demonstrating the validity of our assumption on the importance of modeling spatial correlation. We present the average rank of each model in Figure 2a). datasets and metrics, our model's average rank the best, which holds true also for Tow datasets, demonstrated in Figure
a). Across all

---

4.2 Kernel Smoothness and Label Informativeness
In this section we examine the impact of the kernel smoothness parameter in the Matérn kernel on OOD Detection on graphs with varying label informativeness. Here we state our observations:
Lower kernel smoothness ben- efits learning under low lahel informativeness: In Figure (b), we demonstrate the best v for low label informative datasets to be significantly smaller than datasets with high label informa- tiveness. We reason that smooth spatial covari- ance structure (large z/) results in short-range un- certainty dependencies whereas a rough covari- ance structure (small 1) results in long-range uncertainty dependency, which should benefit the case for low informative labels. We also pro- vide the case where -> oo, where the Matérn kernel turns into the RBF kernel 4 In table [ The results demonstrate that general, flexible choice of kernel smoothness outperforms the smooth behavior provided by the RBF kernel: the RBF kernel results consistently perform poorly the low LI datasets.
Ohservation 1:
Model Rankings Metric Datasets)
Frens
Figure 3: Average rank for low LI datasets. Some baselines perform better than GNN models.
Observation 2: Traditional models without graph structure can perform better on low LI datasets: In Figure 3 we provide the average rank for all the models on low label informative datasets and observe that models without using graph structure (OF, ODIN) can perform better than previous state-of-art graph models (GNNSafe, GNSD) when the graph model does not particularly consider the problem of low label informativeness. Our SISPDE instead consistently outperforms all the baselines by explicitly modeling the spatial correlation of uncertainty.
4.3 Covariance Kernel as Implicit Dynamic Rewiring
In this section we provide an alternative insight on why covariance kernel design helps with learning on low LI graphs by performing the following experiment: for graph and its Matérn covariance kernel, we set threshold value based on percentile of covariance distribution, then prune the low correlation edges and insert new edges that have high correlations. After rewiring, the label informativeness of roman empire increases by a factor of 2.21, tolokers by 2.94, minesweeper by 2.90, and Questions by 1.84. We then use these rewired graphs as the new input to the simple GCN model and compare the performances. Comparison scenario can be found in Table 2 where GCN's OOD detection performance improves significantly after rewiring. This suggests that spatial covariance structures can effectively serve as a prior for label informativeness.
OOD detection results on label leave out
5 Conclusion and Future Work
In this paper, we proposed a novel, systematic, and rigorous framework to perform message passing on graph motivated by stochastic partial differential equations driven by spatially correlated Gaussian process. We demonstrate the soundness and superiority of the framework on uncertainty estimation task for graph datasets with varying label informativeness and provide insights on the mechanism by analyzing kernel smoothness and graph rewiring. There are a number of promising and intriguing directions work on: (a) Adapt a systematic Bayesian perspective and use the spatially-correlate SDE as a prior to extend the current framework for uncertainty estimation. (b) Explore the more general case of nonlinear dependency between uncertainty (such mutual information). (c) Exploring covariance structures for graph substructures rather than nodes. (d) Further explore a larger class of SPDE models, such as those with both deterministic and stochastic forcing term or with fractional brownian motions. (e) Improve the scalability of the current approach on larger graphs. (f) Explore application to other tasks such as modeling stochastic
dynamical systems.

---

Mldd
Stractu
Feauee DETAACC
DER-ACC
ADC
DEET-DC
F19ess
AUC
TEROS
Odir
17.61
90.40 0.225
95.33 0:55
80 1.45
69.59 0.20
10:79
1.67
01:93
1.50
58.6 4.06
91.84 1:550
Malabansos
T4.57 8: 1.45
60.83 6: 1.45
64.95 = 9.56
58.50=22.00
64.7= 0.50
56.94
0.52
18.00
9.57
=0.0700.51
02.41
2.0.6
GNNNSi
90.77 8 0.48
65.32 1:30
46.85
4.19
58.84
0.33
53.10
-0.21
61:36
0 3.50
89.50 09
1.00
66.45 0.45
79.34
11:73
Cara
GNSD
03.75 3: 0.31
54.54 0.00
86 4:
10.70 0 0.55
36.15-
01.08 03
860 02
0007
26.23 2: 465
54.25
07. 0.83
55.40
00.40
78.13=0.5
7.06
0..47
2.35
OE
0.64
GOLD
10.
85.54
36.88
0.44
58.53 4.57
10:
16.72 3.51
0.034
12:02 4.3.5
GEBM
90.00
11.20
70.50
4 10.15
50.50
15.75
78.00 9.96
77.50 0 8.51
51.00 0 9.29
76.00 7.81
78,23 2.78
61.00
2.70
SISSTIE-RI RIBB
15.22
6- 0.54
88 90 9.775
23.07 0 0.00
63.55
- 9.20
77 13 2.61
67.63
- 6.95
18 3.94
65-39 1:15
61.57
SISPDE
96.95
3: 0.08
B1:45
35 0.13
10:87
3.006
00.05 21 1:336
66.06 0.774
18.94
22 0..5
07.89 25 00220
B4::8 0.55
6.17 2: 00.03
96-17
0.54
0:77
56.73
07.02
1.50
Matalanohrs
72.01 3.43
15.45 0.0.
4.90
0.37
55.03
0.20
70.14
2:31
55.35 0.30
75.15 8.50
GNINSOR
76.31 8- 2:33
081 9 2.18
72:33 0: 5.55
S7 0.77
64.15
1.76
14.15- 02 1.30
2.05
83
53.38
GINSD
70.91 3: 5.00
T3.09 5.65
68.02 0.30
07.60
04.42
0.29
0.82
06.57
04.06
5.76 1.87
71:15 0.06
06.
72.99 3.15
73.91
68:32 00000
50
K3-20 0.76
75.11
70.08
0.74
0.00
GOLD
02
50.46
2.26
GERM
19.50
2.96
64.60 3 0.79
7.06
94 20
91.40 1:21
12.20
3.26
94:30
2.08
00.30 2.06
14.00
9.06
SISPDE RBF
79.16 + 5.82
T4.29 4 4.022
12.92
56 19 1.91
50.50 = 1.70
21.17 +: 50.22
10:57 + 2,77
65.03
0.64
51.30
= 12 25.55
SISPDE
51.50
3: 2.74
75.81 3: 1:52
56.96
07:20 08
941.6
0.77
5:30
0.57
09.
32 0.22
96.04
0:43
2:55 3 1:37
55
50.95
50.49 1.52
50.76
2.00
58 2.38
0.36
Malahaooss
05.61
5.5
56
56.74 0.76
04.40
0.50
33.56 0.00
GNNNSaf
78.53 3 0.89
T1.68
0.50
75
60.98 0.62
62.55
0.70
12.22
0.70
70.1 0.45
97.51
0.25
Chomeer
GNSD
82.41 3: 0.62
78.86
3: 0.26
55.35
82.25
70.35 1.00
08.70
51.
0.700
66.01
55, 20.20-3
MSP
79.94 0.68
T3.35
55
01 0:36
54
T7:76
0.00
7003-000 0.26
20.15 2.2
OE
1.04
68.55
57 0.70
01:65
83.07 2.1.4
76:5 0.12
10-31
GEBM
5.00
2.60
1.30
SISPDE RBF
80,51
01 2.81
70.55 6 2,50
62.05 0.55
73.04 2.74
69.75 1.91
59.30 0 5,16
$1.45 3.07
77.65 0.30
50.35 =
SISPDE
83-43
3: 0.80
7W:17
3: 0.07
53.75
2.70
1.00
79.58
2:22
10.00
5.55
$2.05
2:85
65.98 2:23
25.25
GCN
51.15 0:33
N119
92
0.71
00 0.28
18 0.20
16 70
51.77 0.00
50.0
0.34
91.47 0.14
07.81
06.22 6
95.95
50.18
61.40
04.48
Malslanokss
0.10
50.0
Wommnn Drrpe
(INNSaG
GISD
00.85 0.000
16.40=11.77
50.68 0.71
18.10 9.57
90.09
86
71.26
72.16 1.58
45.10 : 0.54
62. 1 0.40
53.50 1.58
56
20:00 0.47
85.15
91.21 0.25
4.12
MIS
66.69 32 0.40
62.41 3:
66.35
6188 0.90
50 00.50.1
0.25
91.98 0.27
OE
53.00 0.54
58:22
68 0.20
51:55 0.23
29.00 1.63
7777
GEBM
SISPDE-RU
51.76
51
56
57.80 0.55
51.53
0.95
0.15 01:35
51
SISPDE
60:49
0.30
05.05
1:00
1:58
96.12 18 3.36
90.72
13:43 1: 9/44
05.4 1: 0.51
0.89
90.05 + 2.85
GCN
51.97 4: 3.22
54.20 + 2.50
92:90 2.60
50.91 1.55
57.72
3.56
5o 10113:22 8.30
04.88
1.04
57.64 0.54
95.05
1:25
N1.00 2.2
51.11 3
96.3
50.25
$1.41
66:30 7.14
61
1.11
56.15
0.30
98.00
0.26
01
50:40
10:90
0.51
1.54
GINNSafe
May 5oepper
GNSD
65.20 2: 0.05
64.37 2 0.52
92.15 0 0.65
58 1.50
58.06 0.18
06.92 =2 0.71
19.61 2 5.90
50.45 1.20
94.64
1.40
MBS
07.02 0 0.61
16.35 0.57
66
1.39
57 1.00
47 0.35
58 63 5.30
00 16 0.005
65
0.06
91.37
8.9.31
OE
60.45
0.40
01.55 0.55
85.23 0.08
53.80 8.06
71.71 6.62
01.70 2: 19.03
70.26
5.61
56.10 7.51
52.95
13.04
GOLD
50:36 0.00
40:33
95.14 0.50
06 9.01
50.15
14: 0.55
64.74
2.04
51-12 1.55
96.70 1.33
SISPDE
64.00
54.70
92
52
56.55
10.92
3.34
56.00=222
2.23
SISPDE
3.00
02.08 3: 1:10
4.20
966855
5.08 1
79:51
50.99
GXN
04.13 0.74
50.71 0.21
91 0.30
16- 19-19- 0.00
50.00 0.10
100.001 1 0.00
50-56 0.00
50 0.00
91.87 0.0
03.76 1 0.80
58.50
1-68
8.91
69.30 4.26
10.32 0.03
55.75
00.48
0.41
53.35
0.04
Malalanobs
00:71
57.08
62.40
2:11
78.04
3.11 52.23
56.54 1.54
01.70
Questions
GNSD
52.50 2.90
54.25 0.55
43.85
54
te 20 0.33
5364- 0.50
13.00
0..00
MSP
41.82 0: 1.80
50.50 0.350
1.60
48.45 0.66
0.55
100.00 0.00
50.61 0.06
50.9 1.10
94.84 2: 0.00
OE
61.50 31 0.89
57 09.39-2 0.052
85.25
1:200
14.20 11
70.74 1: 7:14
RL.88 2: 11:30
50.00 0.00
5001 0.01
94.71
8.000
GOLD
05.74 1: 1.16
20.06 0..85
91.53 - 1.30
54:55-110 1.00
75.45 = 1.66
14 0.00
50.07
9.1.6
5003-0.00 0.00
97.10
1.00
GEBM
07.90
0.00 0.00
50.00 0.00
100.00 0.00
00.20 0.72
60.70-6.3 0.71
0.30
0.14
SISPDE
2:45
58.68 1.445
79.16
56.34
GUN
05, 73 5.10
51.55 6 2.14
90.32 8: 1.15
75.
6.30
75.95 = 3.30
te
: 0.30
55.8 4 9,80
63 3.63
53.51 3.352
Olix
60,00 2: 1.82
66.00 0.66
68.82 = 0.20
20 84 4.04
50,8 = 1.0
100000 2: 0.00
65.70 1.85
60:35 1.14
94.00
0.35
Manalunohes
53.18
13 9-9.9 9/
1:26
N6 3:40
54.99 0.77
50.4
7:30
53.54 1:03
0.00
1.60
06.58
GNSD
10.50
51644
96.05
2.54
0.00
42.58
8.22
55,00 0.40
MAR
15.51 1.60
40.09 0.00
96
ST 9.38
85.35 3.58
25.25: 57 40
50.20
1.27
5M 0.30
93.00
1.50
OE
71.02 4: 0.70
00.15 + 0.68
85.20 22 0.85
70.64:33..0 9.00
$1.92 0.50
63.58 2 55.71
01.33
62
0:50
92.51 2.00
GOLD
60,68-22 2.17
00.00 0.04
94 = 1.20
61.30 4000
76.17
4: 22
00:00 49.00
47 (1 2 16 06.96
93,13
1.45
GEBM
59.60 1
5300 0.55
96 0:38
1.50 1 0.90
50.90 0.11
06
0.50
1.44
50.0- 0.10
0.29
SISPDE
00.01
92:35
3.50 50.99
10
T5, 13.02
T4.52
50
76
OZ
OCN
50.55 2: 0.04
22.32
+ 9.01
94 = 0.50
55.95
= 1.31
77.24 =z 0.30
56.88 : 5.96
20.56 2 3.00
50.14 0.00
15.21 0.04
$1.25 2 0.42
52 00 3 3.40
96.05
- 0.15
56 0.61
53.81 2 0.64
10:90- 0.01
51.37 0.62
$1.28 0.18
93.00
9.11
Manalanobi
51.25 2: 0.42
51.02
2 0-112
53.31
= 0.40
57 0.00
64.10 0.041
10:31
56. 06.28-1
1.85
68.71 1.0.5
87. 01 8.00
CINNSafe
51.18 2 0.94
51.88
95.74 0.06
0.10
51
A7 0.00
50.58 0.50
50.5 0.22
0.36
MSP
50.72 00:5-0000
59.14
91.77 0:20
56
75.00 2.18
50
50.00 3.00
54 0.00
94.74
OE
R2.24 2:
$2.00 2 0,00
96.45 32 0.12
88.05 15 1.91
70.61 = 3.42
40.78 1 5.30
10.56 0.12
50.45 0.08
94,00 0.07
GOLD
19 00 0 0.0.7
10.41 4 0.32
05.25 - 0.36
$4.95
8.10
$3.92
-3.92-9915
9:45
76.79
37 15
36:15 0.07
11 0.00
95.15
9-:1
GEBM
67.30 2:30
02.00 =: 1.01
55.00 -1 1.66
36.90 0.29
61
= 3.21
78.30 6.64
51.20 4.00
2.51
24.00 4:30
SISPDE
12
95.51
0.07
0.330
50.55
0,51
91.01
0.21
Table Out- Oft-of- Distribution detection accuracy (DET-ACC) (1), (T) and FPR95 (L) (best and
runner-up) on graph datasets. Our model consistently outperforms baseline models on all datasets and on different OOD types.
Dataset
Minesweeper 53.97 /53.20/92..000 80 59.64/57.15/ 15/.//
Tolokers
Questions
Roman Empire
Result Without Rewiring
48.73/51 1011159///0 395.32 61.99/61.92/886.22
44.43/50.71 /94.33
53.15/53. 12/92.49
Result With Rewiring
06..6/500.4//95
19.33
64.53/ 55.
Table 2: GCN Performance with and without rewiring on low LI datasets (AUC/DET- -CCCDEER-ACC/FRR5)
10

---

References
[1] Sami Abu-EI-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, 2019.
[2] Anna Okula Basile, Alexandre Yahi, and Nicholas P. Tatonetti. Artificial intelligence for drug toxicity and safety. Trends in pharmacological sciences, 2019.
[3] Richard Bergna, Felix Opolka, Pietro Liò, and Jose Miguel Hernandez-LLobtto. Graph neural stochastic differential equations, 2023.
[4] Viacheslav Borovitskiy, Iskander Azangulov. Alexander Terenin, Peter Mostowsky, Marc Peter Deisenroth, and Nicolas Durrande. Matérn gaussian processes on graphs, 2021.
[5] Benjamin Paul Chamberlain, James Rowbottom, Maria Gorinova, Stefan Webb, Emanuele Rossi, and Michael M. Bronstein. Grand: Graph neural diffusion, 2021.
[6] Bertrand Charpentier, Daniel Zügner, and Stephan Günnemann. Posterior network: Uncertainty estimation without ood samples via density-based pseudo-counts, 2020.
[7] Jeongwhan Choi, Seoyoung Hong. Noseong Park, and Sung-Bae Cho. Gread: Graph neural reaction-diffusion networks, 2023.
[8] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering, 2017.
[9] Laurent Demanet. On chebyshev interpolation of analytic functions. 2010.
[10] Moshe Eliasof, Eldad Haber, and Eran Treister. Pde-gen: Novel architectures for graph neural networks motivated by partial differential equations, 2021.
[11] Peter Friz and Martin Hairer. A course on rough paths. Universitext, 2020.
[12] Dominik Fuchsgruber, Tom Wollschläger, and Stephan Günnemann. Energy-based epistemic uncertainty for graph neural networks, 2024.
[13] Yarin Gal. Uncertainty in deep learning. 2016.
[14] Paolo Giudici and Emanuela Raffinetti. Safe artificial intelligence in finance. SSRN Electronic Journal, 2023.
[15] Ibrahim Habli, Tom Lawton, and Zoe Porter. Artificial intelligence in health care: accountability and safety. Bulletin of the World Health Organization, 98:251 256, 2020.
[16] Martin Hairer. An introduction to stochastic pdes, 2023.
[17] Dan Hendrycks and Kevin Gimpel. A baseline for detecting misclassified and out-of-distribution examples neural networks. ArXiv, abs/1610.00136, 2016.
[18] Dan Hendrycks, Mantas Mazeika, and Thomas Dietterich. Deep anomaly detection with outlier exposure, 2019.
[19] Victor Ivrii. 100 years of weyl's law. Bulletin of Mathematical Sciences, 6(3):379-452, August 2016.
[20] Patrick Kidger, James Morrill, James Foster, and Terry Lyons. Neural controlled differential equations for irregular time series, 2020.
[21] Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ArXiv, Abs/1609.029000 2016.
[22] Lingkai Kong, Jimeng Sun, and Chao Zhang. Sde-net: Equipping deep neural networks with uncertainty estimates, 2020.

---

[23] Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin. A simple unified framework for detecting out-of-distribution samples and adversarial attacks. ArXiv, abs/1807 807.03888, 2018.
[24] Zong-Yi Yi Li, Nikola B. Kovachki, Kamyar Azizzadenesheli, Burigede Liu, Kaushik Bhattacharya, Andrew M. Stuart, and Anima Anandkumar. Neural operator: Graph kernel network for partial differential equations. ArXiv, 02//2003.034485 2020.
[25] Shiyu Liang, Yixuan Li, and Rayadurgam Srikant. Enhancing the reliability of out-of- distribution image detection in neural networks. arXiv: Learning, 2017.
[26] Xixun Lin, Wenxiao Zhang, Fengzhao Shi, Chuan Zhou, Lixin Zou, Xiangyu Zhao, Dawei Yin, Shirui Pan, and Yanan Cao. Graph neural stochastic diffusion for estimating uncertainty in node classification. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 30457-30478, PMLR, 21-27 Jul 2024.
[27] Finn Lindgren, David Bolin, and Havard Rue. The spde approach for gaussian and non- non-gaussian fields: 10 years and still running. Spatial Statistics, 50: 100599, August 2022.
[28] Finn Lindgren, Johan Lindström, and Håvard Rue. Norges aakriss-naturviiennsaaliiii uni- versitet an explicit link between gaussian fields and gaussian markov random fields: the spde approach an explicit link between gaussian fields and gaussian markov random fields: the spde approach.
[29] Weitang Liu, Xiaoyun Wang, John D. Owens, and Yixuan Li. Energy- based -iittriiittiiutionn detection, 2021.
[30] Qing Lu and Lise Getoor. Link-based classification. In Encyclopedia of Machine Learning and Data Mining, 2003.
[31] Sitao Luan, Chenqing Hua, Qincheng Lu, Liheng Ma, Lirong Wu, Xinyu Wang, Minkai Xu, Xiao-Wen Wen Chang, Doina Precup, Rex Ying, Stan Z. Li, Jian Tang, Guy Wolf, and Stefanie Jegelka. The heterophilic graph learning handbook: Benchmarks, models, theoretical analysis. applications and challenges, 2024.
[32] Sitao Luan, Qincheng Lu, Chenqing Hua, Xinyu Wang, Jiaqi Zhu, Xiao-Wen Chang, Guy Wolf, and Jian Tang. Are heterophily-speccfic gnns and homophily metrics really effective? evaluation pitfalls and new benchmarks, 2024.
[33] Thomas Markovich. Qde: Quantum diffusion convolution kernels on graphs, 2023.
[34] Galileo Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven active surveying for collective classification, 2012.
[35] Oleg Platonov, Denis Kuznedelev, Artem Babenko, and Liudmila Prokhorenkova. Character- izing graph datasets for node classification: Homophily-hettrrphily dichotomy and beyond, 2024.
[36] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of gnns under heterophily: Are we really making progress?, 2024.
[37] Michael Poli, Stefano Massaroli, Junyoung Park, Atsushi Yamashita, Hajime Asama, and Jinkyoo Park. Graph neural ordinary differential equations, 2021.
[38] Giuseppe Da Prato and Jerzy Zabezyk. Stochastic equations in infinite dimensions. 2008
[39] Yifan Qu, Oliver Krzysik, Hans De Sterck, and Omer Ege Kara. First-order pdes for graph neural networks: Advection and burgers equation models, 2024.
[40] Carl E. Rasmussen. Gaussian processes in machine learning. Advanced Lectures on Machine Learning, 2003,
12

---

[41] Cristopher Salvi, Maud Lemercier, and Andris Gerasimovics. Neural stochastic pdes: Resolution-invariint learning of continuous spatiotemporal dynamics, 2022.
[42] Simo Särkkä. Linear operators and stochastic partial differential equations in gaussian process regression. In International Conference on Artificial Neural Networks, 2011.
[43] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi- Rad. Collective classification in network data. In The Al Magazine, 2008.
[44] Yang Song and Diederik P. Kingma. How to train your energy-based models, 2021.
[45] Maximilian Stadler, Bertrand Charpentier, Simon Geisler, Daniel Zügner, and Stephan Gün- nemann. Graph posterior network: Bayesian predictive uncertainty for node classification, 2021.
[46] Eitan Tadmor. The exponential accuracy of fourier and chebyshev differencing methods. SIAM Journal on Numerical Analysis, 23:1-10, 1986.
[47] Jayaraman Thiagarajan, Rushil Anirudh, Vivek Narayanaswamy, and Peer-Timo Bremer. Single model uncertainty estimation via stochastic data centering, 2022.
[48] Matthew Thorpe, Tan Minh Nguyen, Hedi Xia, Thomas Strohmer, A. Bertozzi, Stanley J. Osher, and Bao Wang. Grand++: Graph neural diffusion with a source term. In International Conference on Learning Representations, 2022.
[49] Krystyna Twardowska. Wong-zakin upproximations for stochastic differential equations. Acta Applicandae Mathematica, 43:317-359, 1996.
[50] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio', and Yoshua Bengio. Graph attention networks. ArXiv, abs/1710. 10903, 2017.
[51] John B. Walsh. An introduction to stochastic partial differential equations. 1986.
[52] Danny Wang, Ruihong Qiu, Guangdong Bai, and Zi Huang. Gold: Graph out-of-distribution detection via implicit adversarial latent generation, 2025.
[53] Yuelin Wang, Kai Yi, Xinliang Liu, Yu Guang Wang, and Shi Jin. Aemp: Allen-cahn message passing for graph neural networks with particle phase transition, 2023.
[54] P. Whittle. Stochastic processes in several dimensions. Bulletin of the International Statistical Institute, 40:974-994, 1963.
[55] Qitian Wu, Yiting Chen, Chenxiao Yang, and Junchi Yan. Energy-based out-of-distribution detection for graph neural networks, 2023.
[56] Xiaodong Zhang. The laplacian eigenvalues of graphs: survey. arXiv: Combinatorics, 2011.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Please refer abstract and Introduction section.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We provide the limitations in the future work section, where talk about extensions to the current work. We also provide the performance profiling results in the Appendix section and discuss possible further improvements.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: For each of the theorems in section 3 and 4, we provide detailed proofs in the Appendix; in each theorem clearly state the required mathematical assumptions.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We clearly provide the list of datasets and the list of baseline models in section 4. Moreover, we provide the details on dataset split and hyperparameter search range in the Appendix section. We also provide anonymous version of the code as part of paper submission. Datasets used in the paper have already been open sourced, and all the codes will be open sourced as well.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibilitty In the case of closed-source models, it may be that access to the model is limited in
15

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We will release the open sourced code to GitHub after the paper is accepted.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide the detailed experimental set ups, including dataset split and hyperparameter search range, in the appendix section of the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
In section 4, we provide the tta over runs over 5 different seed values for each datasets and for each metries. We also provide clear barplots that show average rank for all the models included in the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
16

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide details about the computational resource used in appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://///.aaaaae.cc////////ttaa
Answer: [Yes]
Justification:
We acknowledge that we follow the code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Throughout the paper we are addressing the problem of uncertainty estimation; while the approach theoretical, this topic has implications for safety-critical areas, as highlighted in the Introduction section.
17

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considcrations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning conrectly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work doesn't pose such risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
All the datasets used in the paper were licensed by CC through the package PyTorch Geometrie; moreover, all the baseline models' code were released under the CC
Justification:
license on GitHub.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
18

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the palaaets.ppperssttt paperssii thcode. com con/datases package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We don't 't have any new assets to release beyond the source code and the paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
There is no crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: our work does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
19

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLM usage is not important for our research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy httto:///merrrppecc////offeerrre for what should or should not be described.
20

---

A Construction of Spacetime Noise on Graph
In this section, we provide the detailed formulation for defining the d-Wiener process in the main paper and its associated stochastic partial differential equation (SPDE) on graph. We introduce the mathematical tools of differential operators on graph, the formulation of a PDE on graph, and the definition of noise process on graph. For each subsection, we provide the proofs for theorem I to 3 in the main paper.
A.1 Graph Message Passing PDE
The analogy between Message Passing Neural Networks and Partial Differential Equations has been widely explored, with pioneering work in [TO]. which systematically defined differential operators on graph. In particular, the graph incidence matrix G' used to model divergence and the gradient operator, while GG L, the graph Laplacian matrix, is used to model the Laplace operator. Multiple existing works such as GRAND [5] and GREAD 7 formulate MPNNs as discretization of partial differential equations convolution operation as a heat diffusion kernel. This formulation allows them to use an ODE-solver to perform message passing, making the MPNN continuous in depth. In the most basic case, for the node feature r on graph, we have the GRAND-basee message passing as:
the graph domain, with the special formulation of the graph
dx(t) 0L
divlG ((te)
which follows the heat equation Ø4 Az. For graph data, Vx defined as a matrix whose entries are the difference between two node feature: (Vær)ij Xi Ij and the divergence operator is the aggregation of signals over the neighborhood of a node. In the GRAND formulation, G is a GNN layer while f. is the continuous index for layers of the GNN, and the entire message passing that updates node features can be written as an integral equation. For GRAND, the vector field written as 0x 0tt (Ar - f)x, random walk operation. The full forward pass also incorporates an encoder and decoder network (ø, eh) to project the individual node features into a latent space, which results in the following update rule:
( ((x)
f
T a
J'd (AH(t) ())(t)
H (())
at H())dt H10)+ +
x (T) = ((H(T))
This formulation aligns with the neural model known as latent graph ODE, which also uses a GNN as the parametric function for the vector field, while first projecting the input feature into latent space. The author argued that this formulation can help alleviate over-smoothing and provides principled way design GNN message passing schemes, despite the challenge of model training and hyperparameter-tuniin
Beyond the heat equation formulation, various other PDE-based message passing schemes have been proposed, such as -iftriooniffuiion equation 77]. transport equation [39] and the Schrödinger equation 33 In [26), the author motivated the case of stochastic heat equation, which appends Q-Wiener process after the heat equation, and was implemented in the form similar to a latent graph Stochastic Differential Equation
A.2
Q- Q-Wiener process and Cylindrical Wiener process
We provide the mathematical definition two types of space time noise process crucial for the construction of stochastic PDEs.
Definition 3 (Brownian Motion), A standard Brownian motion (also called Wiener process) is a stochastic process (8(t))r2o defined filtered probability space (S, with the following properties:
1. ((0) O.
2. t + W, is continuous in t, almost surely.
21

---

3. The process has independent increment: 40 < 1 I t2 .... S Ins the increments (t (() B(t,,) B(t, (((tn-2):: 2). ,3(t2) ((t) are independent random variables.
4. Vs 2 0, 0, B(t) N0 s).
For the theory of SPDE, the crucial concept is random variable Hilbert space, which gives rise to the notion of trace-class operators and Q- Q-Wiener process.
Definition 4 (Trace-Class Operators). Let H be a separable Hilbert space with a complete or- thonormal eigenfiantion basis {1h1 KEN and Q H H a linear operator, then Q is trace-class if:
Tr(Q) = = (QUi. wha) < 00
k=1
Definition 5 (Karhunen-Loove Expansion). Let X be zemo-maa and square-integrable stochastic process defined on (S2, F, Ft,P)) and indexed over a closed and bounded (a. b) with covariance function K x (8, t), then if Ky x is Mercer kernel, and let ek be an orthonormal basis of the Hilbert- Schmidt operator on L L2)a, , b] with eigenvalues Ale then Xe admits the expansion:
X₁ Zzen(t).
where } are pairwise orthogonal random variables with zero mean and variance Xu. and the series converges to X, uniformly in mean square.
Definition 6 (Q-Wiener process). Let Q : H H be trace-class operator that's 's symmetric and non-negative, then a -valuudd stochastic process (W(1) 2 0} on the filtered probability space (2, F,, PP) is Q- W-eeer process if:
1. W (0) = almost surely.
2. W (t::w) a continuous sample trajectory H for each E S2
3. (tt) is F--adapted and has independent increments (t) (S) <t.
4. W(t) (ss) ~O,0 (t (t=)) for all 0 st
Using the Karhunen-Loève expansion, one can establish that W(t) is Q-Wiener process if and only if Vt 2 0:
W(I) = Σ (
1=1
where (t(t) is i.i.d. Brownian motions, v/s orthonormal eigenfunctions of the Hilbert space, and the series converge in (2, H) 411
When
then Q no longer trace class in H, so othe series above does not converge in (Ω2, H). In this case we have the Cylindrical Wiener process:
Definition 7 (Cylindrical Wiener Process). Let H be separable Hilbert space. Cylindrical Wiener process (spacetime white noise) is H-valued stochastic process (W(I) 2 0} defined by:
W(1) = (1)
which is simply the case for Q I.
Note that in our construction of the d- Wiener process on graph (Definition 2), we have the analogous Hilbert space formulation of:
W(() Σ (01)0,8,(1))
22

---

and the convergence depends heavily on the behavior of the cigenvalues A of the Hilbert space. If the operator ((A) I, then we recover Cylindrical Brownian motion, and if the infinite series converge in (H, 22), we have Q-Wiener process. If it diverges, we have a general class of spacetime white noise.
A.3 Q-Wiener process on Graph
The notion of a Q-Wiener process on graph was introduced in 26 where spectral formulation of the noise is adapted using the spectrum of the graph Laplacian matrix L UAU where U = [u1, and A = diag( A ; are the Laplacian eigenvalues. Constructing the Q-Wiener process follows the classical Karhunen-Loève expansion, which projects standard i.i.d Gaussian noises onto the spectral basis:
uv)) is the orthogonal matrix whose column vectors are the Laplacian eigenvectors
M W(1) = Σ (W()) u
Σ
3z
k=1
This construction has the following properties:
1. W(1) - (s) ~ ~O (t-aa L)
2. the process (t)) is trace class and Q-Wiener process.
3. (t) (s) AA2 (t)t) ((s), ug)
Proof of Proposition in the main paper:
Proposition 1: Let G (V.E) be graph, then the Q-Wiener process defined in Equation results in spatial covariance structure of each independent Brownian motion i.
W,(t), = Ligt, where i, E V, and (t),), By (t) are
Proof.
(o, (t) EW((OW,(0) ([W(
A (1)
Au (t) un
+E Ax33
t
A (1) = [UAU*] List
As can seen, the Q-iiener process defined by (26] can be seen as stochastic process with spatial covariance structure determined by the graph Laplacian.
A.4 Gaussian Random Field and Graph Gaussian Process
To imbue the noise process with more structure, the usual approach is to examine the covariance of the Gaussian process. A space time noise process in its essence a process with two parameters: ((x,t) t) where usually takes the value from compact set in a space like Rdd. The approach that studies space-time time white noise from the perspective of compact sets in space and time is pioneered by Whittle 54 and Walsh [5I). particular, if we freeze time and study the spatial component, we obtain a Random Field W(x), where takes value from a compact set U E Rd If the joint distribution of any finite subset of spatial noises admit multivariate Gaussian, then the random field
is known Gaussian Random Field (GRF). The study of random field as solution of SPDE
23

---

can be found in [54 27 where it is known that the GRF with the Matérn Covariance kernel can be
obtained by solving the following SPDE:
2V
274
S-W W
A2
where W is the Gaussian white noise re-normalized by certain constants 4 On the graph domain,
a truncated version the SPDE above can be formualted by replacing W ~ ~W, I) and with equation:
2/ f f= W -
2v R22
the Gaussian process result of this equation can be represented using the spectral decomposition, similar to the Karhunen-Léoo expansion approach. This was solved in [4] as:
(0,
2u + +
~~N
where the covariance kernel is known as the Matérn kernel (M), which admits spectral representation of:
22v 122 2
1/2
M = U.AAU +(A)=
x2
The parameter controls the smoothenss of the spectrum, with v corresponding to the heat kernel exp(-
- A) and small values of // resulting in a rough spectrum and the resulting Karhunen- Loève expansion not converging in (IR,, ,2).
A.5 Ø-Wiener process Graph
Motivated by the limitation of the Q-Wiener process on graph and the covariance structure based approach in Gaussian Random Field, we proposed the Ø-Wiener process, which performs the spectrum transformation on the eigenvalues induced by a predefined covariance kernel function.
Siinition(&-Winnee process graph). Let G EV, be undirected graph and A its graph Laplacian. Let { {xx
be its eigenvectors and eigenvalues, respectively, and let IR - R be scalar function with & its matrix functional form, then d-Wiener process is defined by the (truncated) Karhunen-Lock expansion:
M w(t) = Σ Bx
(15)
In the experimental part of the paper, we in particular studied the case when á corresponds to the Matérn kernel, while the construction can be applied to any positive semidefinite kernel matrix (or the kernel function in the Hilbet space). Here we present the proof for Theorem 2 in the main paper:
Proof for Theorem 1 in the main paper:
Theorem 1: Let = (V, F), and A graph Laplacian with spectral decomposition A UAUT,
then for the construction in definition 2 if the matrix K = -UT(A)UT is positive definite, then (tt) (s) ~ (O, (t - 8) K) for s and the spatial-temporal covariance of noise process on two nodes j, k can be written Cov(W.()) Ws(s)) = (t s) where (t A s) min(t,
Proof. The result that ((I) - (s) A/ (L K) follows since the truncated KI. expansion equivalently embedding on the matrix K = (A)UTT and the form follows from the definition of Q- WWeiner process in Appendix A.3, As for the covariance structure, obtain the result by

---

adjusting the proof for proposition 1:
Cov(W W (IW,(() [Ww.,//w[6))-RR////W//WW
(Ax) mp (1),x(())
[ ((
M
R
(0) uz)
+E Σ (00))008800000000000
V ([)
Φ (As))s = ] [U = ( (t)
(U(A)U))
Notice that with the specific choice of é in our paper, the covariance structure the spatial domain should correspond to the Matérn kernel.
As theoretical interest, we can analogously look at the general Hilbert space construction of the h- Wiener process, by looking at the full KL expansion:
W(I) = Σ ((Aa)
where (Ax, 4hx In are now the orthonormal eigenbasis a separable Hilbert space H. We stated the property of this stochastic process in Theorem 2 of the main paper. Here we restate the theorem and provide a proof.
Proof of Theorem in the main paper:
Theorem 2: Let H. be separable Hilbert space and (L,F,Fi,P) a filtered probability space. Let Q' be a trace-class operator in H and a function operator that scalar- soalar-tranforms the eigenvalues {Ai) Q' then if Ei= ((;)) < oc, the induced h-Wiener process is a Q- Q-Wiener process with (QQ'). Moreover, the transformation for Matérn kernel induces Q-Wiener process when v > d for a random field taking value in Compact U C Rd.
the trace class operator
Proof. The first part of the theorem simply states that the operator induced by (Q')) is trace class, then the resulting Wiener process is Q-Wiener process with Q ((Q'). This is true by definition. The main proof concerns the case for the Matérn kernel, which we aim to prove here.
Let A be the Laplace-Beltrami Beltrami operator, which is the Hilbert space analogy of the Laplacian matrix, then we need to show that the Matérn kernel's induced spectral decomposition results trace-class operator. This is equivalent to proving that the following infinite series converge:
Am
8
1=1
Where the additional term with d comes from the Whittle SPDE for Rd
3+1
2v
+
S-W
which ensures regularity and existence of solution. Proving the convergence of the series requires analyzing the asymptotic behavior of the Laplacian eigenvalues {Am Assume that the boundary condition Neumann, then the Laplace problem can be written in spectral form as:
Auu = Agu lau= 0
with the eigenvalues satisfying:
0 < \ 5 522 < ...
0
25

---

Let the eigenvalue counting function (A) be:
[(A) = #IKEN: A S A}
then (An)) = n2. Now the classical Weyl's law 19 says that:
((A) vol O(44/3)
where vU)(U) < oo is the Lebesgue measure of U, which finite since U is compact. We hence arrive at the following relationship:
((1 An O(ni/d)
Now with the asymptotic behavior of d clear, refer back the original infinite series, whose convergence is controlled by:
n 2/d
20
n=1
==1
which converges and only if:
2v
B Stochastic PDE with @-Wiener process on Graph
In this section we analyze the conditions for SPDE to have unique mild solution. In particular, we analyze the case when the SPDE is driven by the 4-Wiener process defined in the section above, and provide a proof for theorem in the main paper. the end, we also provide the derivation of the graph ODE implementation of the SPDE using the Wong-Zakai approximation theorem.
B.1 Existence and Uniqueness of Solution to SPDE
In this section we provide the technical details about the existence and uniqueness of the solution to a stochastic PDE system driven by Q-Wiener process and then justify the SPDE system driven by h- Biener process our case by proving Theorem 3 in the main paper:
Theorem 3: Let H be separable Hilbert space, and (Ω, F.F,PF be a filtered probability space and W(x, 1) a Fr-udapted space-time stochastic process whose spatial covariance kernel is given by the Matérn kernel on a closed and bounded domain D Rd, then if d and H(0) is square-intgrabble and Fo-measurable, the SPDE of the form:
dH(()
F(H()))) dt + G(H(t))dW(I)
admits unique mild solution:
H(1) = exp(1C)H(() + 1 (x)(((=))C)P(H()))) + exxx((())))))(eee ()S(()-))))C(H))))WV
Where L is a bounded linear operator generating a semigroup exp(tC) and F, G are global Lipschitz functions.
Proof. The condition that v > d ensures that the Space time noise with Matérn kernel in our case is Q- Q-iiener measure (from Theorem 2 This is applicable since a closed and bounded domain D C I is a compact set. The theorem then becomes the classical result existence and uniqueness of mild solution of semilinear SPDE driven by Q-Wiener process. The technical details of the proof
can be found in [16] Theorem 6.4. Since the whole proof requires a series of technical build ups, we refer the readers to the monograph by Hairer [16].
26

---

B.2 Chebyshev Approximation of Matérn Kernel
For the practical implementation in section 3.3, we propose to use the Chebyshev polynomial to approximate the matrix function o ()) when cigendecomposition becomes too expensive for the graph Laplacian A. Here we provide the theoretical justification for the approximation bound derived in Theorem 4
Theorem 4: Let G (V, be graph, and let the Matérn kernel on graph be defined in equation (
then the Chebyshev approximation in equation 13 results in error bound O
x² ddd
m
160+x=dma.
where m is the degree of the Chebyshev polynomial and dmax is the maximum degree of the graph.
Proof. Equation Dintiioaniidditetesss that the function approximate is:
2v
S(A)
+ +
generally analytical except at the singularity of X = - However, since the eigenvalues are non-negative for the graph Laplacian and 2 0, the function is analytical in the entire domain of X. In practice, however, we scale À to the range [-1,1] 1] for the graph Laplacian before the Chebyshev approximation. Hence without loss of generality, suppose
which is
2A (Amaz Amin I
Amaz
-Amin
Then analysis concerns f(X) the interval [-1,1]. Since f(X) is analytic this interval, use result in 46): Let E,p be the Bernstein Ellipsis over which f(A) analytic. Let p >> 1, then a Chebyshev polynomial of degree K has approximation error of:
(g(x) (x(xx) S CM((P)
M(p) p-p p-p-1P < <C- M(())
p p-1
where (p) maa [(A) is the bound for f()) over the Bernstein Ellipsis, defined in the complex XE E.
plane as:
E = (2 S:eC::z (pe + - (0,24))
The singularity of the function ff f(A) is at 24 which should lie outside of the rescaled eigenvalue range [-1, 1]. Let H, be the point of singularity, then:
2A (Amaz + Amin))
2( 2v Amar
4v
F.
Amaz
Aminn
Amaz
Ammax
For { the eigenvalues the graph Laplacian, following the conclusion in [56). have that
Amaz I Aman where dmaz is the maximum degree of the graph. Let a es d'aaa
8y
then:
8y
-a
222
and p being the distance from the spectrum of A to the nearest singularity, is computed as:
1
- -12 V 1)2
p p= p= x.l
2 2a + 1
hence we have:
16v
p> 2a
d2d
In the end, the approximation bound in 9 again:
(g(x) (x00)g)(())----)) 0() ((
>)=
K
((1
K
K²² dmaa
16p
16v + x2 dd
Note that tighter bounds are possible, depending on bound of choice for Amaz and M M but we leave that for future discussion. This bound nevertheless provides the insight that if larger values of results in faster convergence, which naturally follows due a smoother spectrum of the Laplacian.
27

---

B.3 Discussion on Node Variance
Throughout the paper we have focused on the correlation of uncertainty between different nodes due to graph topology and label distribution. Now we briefly discuss on the behavior of node- level uncertainty, characterized by variance the accumulated noise. For the Matérn kernel U + A)-"?² the variance of each node can be computed as:
22 +
Ki
-U
(16)
This variance depends the graph topology the above equation is function of Laplacian cigenvalues and cigen-vectors, and is not directly clear whether they are small or large by just looking v. However, what we can tell is that, fixing all the other terms constant and set 2v/ x 1, then since graph Laplacian eigenvalues are non-negative, the larger the value of v, the more it seems to penalize the variance term (hence the terminology of smooth kernel). In addition, if y large, the distribution of variance is more even for neighbors or connected components (if one node has large variance, neighbors also do), whereas if is small, we can have two distant nodes sensitive the variance change of each other. Ultimately the kernel function controls covariance while variance has more to do with graph topology itself, due to the direct link with the spectrum A, U.
Hence, in our model, the more direct answer to how variance is controlled for each node individually is the integration time in the graph Neural ODE in section 3.3, since longer integration time leads to accumulation of more variance, hence more uncertainty. Analyzing variance is therefore an interesting direction to explore, since know that more layers of GNN (corresponding more integration steps) usually lead to over-smoothing of graph signals, but the noise accumulation can seem to introduce variance. Since these two dynamics can interact with each other in intricate ways, it may even be possible that longer integration time doesn't 't necessarily lead to exploding variance. In our empirical studies, we concluded that learning converges with loss function converging, but it would indeed be interesting to study how the variance of each individual nodes (or sub-regions, since the graphs are usually very large) evolve. We believe that this topic itself can be an interest of extensive future studies.
C Experiment details
In this section we provide additional details on the configurations for experiments, including dataset description, baseline description, evaluation metrics, hyperparameter selection ranges, and additional empirical results.
C.1 Experiment Environment
The experiments are conducted on the Mosaic ML platform with 8 H100 GPUs, and the cluster docker image is the latest AWS image with Ubuntu 20.04. We implement our pipeline using Python 3. 3.12 and PyTorch version 2.5.1 with CUDA 12.4 support.
C.2 Dataset Description
Cora, Pubmed, Coauthor-CSS are three citation graph datasets. Each graph is directed, and nodes are documents, edges are citations. The features are bag-of-words representations. In particular, Cora contains 2, 708 nodes, 5. 429 edges, 1, 1,433 features and 7 classes. Pubmed has 19, 717 nodes, 88, 648 edges, 500 features and 3 classes. Coauthor-CS contains 18, 333 nodes, 163, 788 edges, 6, 805 features, and 15 labels. The train-validation-ted splits of these three datasets follow the standard practice previous works. These datasets are considered to be of Moderate to high label informativenesss with the particular LI values found in table 3 which is originally [35]. Coauthor-CS has edge LI to 0.65, Cora has edge LI to be 0.59, and Pubmed has edge LI to be 0.41.
Roman-Empail Tolokers, Minesweeper, Questions, Amazon-Ratings are so-called heterophilic datasets (36) that also have low label informativeness, which poses challenge for traditional GNNs. In particular, roman-empire has 22, 662 nodes, 32, 927 edges, 300
28

---

Table 3: Dataset characteristics, more homophilous datasets above the line. In the paper focus on Lledges representing edge label informativeness. The table is obtained from 35
Dataset
[
C
hedge
Bannde
Belosa
Badj
Li
LInade
2708
5278
7
0.81
0.83
0.77
0.77
0.59
0.61
citeseer
3327
4552
0.74
0.72
0.63
0.67
0.45
0.45
pubmed
19717
44324
0.80
0.79
0.69
0.41
0.40
coauthor-cs
18333
81894
15
0.81
0.83
0.75
0.78
0.65
0.68
coauthor-physies
34493
247962
5
0.93
0.92
0.85
0.87
0.72
0.76
umazon-computerr
13752
245861
10
0.78
0.80
0.70
0.68
0.53
0.62
amazon- amazon-photo photo
7650
119081
0.83
0.85
0.77
0.79
0.67
0.72
lastfm-asia
7624
27806
0.87
0.83
0.77
0.86
0.74
0.68
facebook
22470
170823
4
0.89
0.88
0.82
0.82
0.62
0.74
github
37700
289003
2
0.85
0.80
0.38
0.38
0.13
0.15
twitter-hate
2700
11934
2
0.78
0.67
0.50
0.55
0.23
0.51
ogbn-arxiv
169343
1157799
0.65
0.64
0.42
0.59
0.45
0.53
ogbn-products
2449029
61859012
47
0.81
0.83
0.46
0.79
0.68
0.72
actor
7600
26659
0.22
0.22
0.01
0.00
0.00
0.00
flickr
89250
449878
7
0.32
0.32
0.07
0.09
0.01
0.01
deczer-curope
28281
92752
2
0.53
0.53
0.03
0.03
0.00
0.00
twitch-de
9498
153138
0.63
0.60
0.14
0.14
0.02
0.03
twitch-pt
31299
0.57
0.59
0.12
0.11
0.01
0.02
twitch-gamers
168114
6797557
2
0.55
0.56
0.09
0.09
0.01
0.02
genius
421961
922868
2
0.59
0.51
0.02
-0.05
0.00
0.17
arxiv-year
169343
1157799
5
0.22
0.29
0.07
0.01
0.04
0.12
snap-patents
2923922
13972547
0.22
0.21
0.04
0.00
0.02
0.00
wiki
1770981
242605360
0.38
0.28
0.17
0.15
0.06
0.04
roman-empire
22662
32927
18
0.05
0.05
0.02
-0.05
0.11
0.11
amazon-ratings
24492
93050
5
0.38
0.38
0.13
0.14
0.04
0.04
minesweeper
10000
39402
2
0.68
0.68
0.01
0.01
0.00
0.00
workers
11758
519000
0.59
0.01
0.02
questions 48921
153540
2
0.84
0.90
0.08
0.02
0.00
0.01
features, and 10 classes. Amazon-ratings has 24, 492 nodes, 93, 050 edges, 300 features, and classes. Minesweeper has 10, 000 nodes, 39, 402 edges, features, and 2 classes. Tolokers has 11, 758 nodes, 519, 000 edges, 10 features, and 2 classes. Questions has 48, 921 nodes, 153, 530 edges, 301 features, and classes. These datasets' LI in table 3 with rooann-emiie LI to be 0.11, amazon-ratings LI to be 0.04, minesweeper 0.00, and questions 0.00.
Overall we can observe significant gap of label informativeness between the homophillic datasets and the heterophilic datasets.
C.3 Label Leave out Details
For the experiment of label leave out, we follow the common practices for the homophilous datasets; for heterophilous datasets, either choose the last label more labels to alleviate class imbalance. Below we present the OOD label choice for all datasets:
Cora: class labels 4, 5, 6 as IND while class labels 0, 1, 1, as OOD samples.
Pubmed: class label 1, 2 as IND samples while class labels as OOD samples.
Citeseer: class labels 3, 4, IND while class labels 0, 2, OOD samples.
Tolokers: class as IND while class 1 as OOD samples.
Roman Empire class labels 0-8 as IND samples while class labels 9-17 as OOD samples.
Amazon Ratings: class labels 0, 2, 2 IND samples while class labels 3, 4, 5 as OOD samples.
Minesweeper: class 0 as IND while class OOD samples.
Questions: class 0 IND while class 1 as OOD samples.

---

C.4 Baseline Description
GCN 2 is fundamental GNN architecture that performs spatial graph convolution.
ODIN 25 uses a temperature scaled softmax activation and uses small perturbations to
inputs to augment the gap between in-distribution and -otoof-distribution data.
MSP 17 uses the density derived from the softmax function to perform OOD detection, with the OOD data have overall lower density values.
Mahalanobis(23] uses a confidence score based on Mahalanobis distance. They use this score to obtain the class conditional Gaussian distributions with respect to (low- and upper- level) features and to determine IND vs OOD samples.
OE 18] proposes to improve deep anomaly detection by training an anomaly detectors against an auxiliary dataset of outliers and to use the detector later on to detect OOD samples.
GNNSafe (55] proposes to treat the classifier-induced logit as score for an energy based model and use label propagation scheme to propagate energy, such that the OOD samples get higher energy and IND samples get lower energy. The model was proposed with or without OOD sample exposure, and we use it for the later case for a fair comparison.
GNSD is an earlier stochastic message passing framework that motivates a stochastic diffusion equation formulation of GNN message passing. It assumes a spatially independent noise and uses aleatoric uncertainty of each node as score for OOD detection.
C,5 Evaluation Metries
The evaluation metrics we choose were also used by previous works 55 26 22
DET-ACC: OOD detection accuracy is the ratio between the test samples that are cor- rectly detected OOD samples and all test samples. Higher DET-ACC indicates better performance.
FPR95 is False Positive Rate at 95% true positive rate. is the probability that an OOD sample is misclassified when the true positive rate is 95%. Smaller FPR95 indicates better performance.
AUC the Area Under the Curve for the ROC curve. With varying thresholds, it is able to evaluate how the model is able to distinguish between OOD and IND samples. Higher AUC indicates better performance.
C.6 Hyperparameter Search
For hyperparameter search, we perform grid search on the following parameters:
kernel smoothness μ: (0.1, 0.3, 0.5, 1.0, 4.0, 10.0, 20.0, 50.0).
latent dimension: [64, 128, 256, 512, 1024).
learning rate: [1e_1 1e-
weight decay:[1e 1e 1e 12]
dropout: (0.0,
Chebyshev polynomial order: {30, 40, 50, 60, 80, 100)
training sample times: (1, 5,
C.7 Runtime Analysis
In this part we provide the result of rumning single forward pass for the models on each datasets. As can be seen from Figure 4 except for two datasets (Pubmed, Questions), our SISPDE's runtime comparable to other models. We suspect that the reason lies the matrix multiplication when applying the Cholesky factor / Matérn kernel to the Gaussian noise and the process can be made more efficient by exploring sparse matrix methods, as was also pointed out ( This suggests that our code can be further optimized for more efficient matrix multiplication.
30

---

Time for one forward
1.2
gen
goneade
gnod
mahalanob
map
Time (seconis)
0.8
oriin
0.6
0.2
amazon, ratiego
citesee
cora
mineswerper
pubmed
questions
reman empire
talokero
Dataset
Figure 4: Runtime for one forward pass in seconds for all the models across all the datasets.
D Details on Related Works
In the paper we went over related works in the introduction and the background parts. However, due to the page limit, we choose to put detailed related works in the appendix section.
Uncertainty Estimation on Graph. Uncertainty Estimation is a booming subject in machine learning, and in the context of graph learning, the community has so far extensively focused on node-level tasks, such as node classification, in which case Dut-of-Distribution (OOD) Detection has been one of the main downstream evaluation tasks. For this task, earlier works focus on adding simulated OOD samples, such as OE and MSP [7], or use distribution density based estimates such as Mahalanobis distance 22 and perturbation based methods that aim modify the distribution of the softmax activation, such as ODIN [25]. Later on, deep generative models were used to directly model the predictive uncertainty of the classification model. Energy based models [55] 29 has been widely adapted, with GNNSafe (55) to explicit model energy propagation on graph to separate the IND samples and OOD samples when these labels are available. However, when the labels are not available during training, models that rely on simulating stochastic processes on graph, such as GNSD (26.. usually perform better. Our SISPDE can seen as an extension and generalization of the GNSD framework, in that we better incorporated the distribution of labels without incorporating explicit label information and our model mathematically more expressive.
Physics--nspired Message Passing Network. The first paper that draws an analogy between a Message Passing Neural Network (MPNN) and Partial Differential Equation (PDE) PDE-GCN [10]. which systematically defined differential operators on graph. The continuous integral equation formulation of message passing was later expanded by GRAND [.) which motivates message passing as diffusion process and therefore discretizes the heat equation. Later works such as ACMP GREAD 77, and GRAND++ 48 further expanded the paradigm by introducing more powerful equations, which explored the message passing
class of PDEs such classes of reaction-diffusie mechanism using special properties of these PDE systems. Most recently there has been growing interests to use tools from stochastic analysis, Stochastic Partial Differential Equations, to further expand the class of PDEs. GNSD [26] motivates to use the cigenspace of the graph Laplacian to define Wiener process graph, following the approach of SPDE in (38) Our SISPDE also explores the adaptation of SPDE to message passing. However, we follow more closely to the random field formulation of SPDE in [54] and propose richer family of space time noise process to drive the message passing process.
Label Informativeness and Heterophily. For the task of node classification, there has been a long
line research on the dichotomy of homophilous and heterophilous graphs [31 32 35 36), where
it has been observed early that traditional GNNs usually perform poorly on heterophilous graphs. However, it was later discovered that for the datasets proposed be used for the evaluation task, graph
GNN after sufficient hyperparameter search yields results competitive
31

---

models, resulting in some questions on the evaluation benchmarks [36]. This discovery motivates the concept of Label Informativeness (LI), which provides label distribution-bast view on the phenomenon of heterophily, with strong correlation between GNN's performance on the dataset and the magnitude of I.I [31 (6). Instead of relying on the homophily vs. heterophily dichotomy, therefore more reliable to divide the graph datasets according to label informativeness [35].
Gaussian Process on Graph. Gaussian Process models 440] has been wide applications in various fields of machine learning. Although traditionally operating only on Euclidean space, it has been proposed early in 28 27 that it can be extended different geometric domains by treating it as solution to certain types of SPDE [54]. On geometric domains, these processes are also known as Gaussian Random Fields [54] (2],, and on graph, was proposed by [4] that Gaussian process can be defined using the graph Laplacian as the discrete representation of the Laplace operator, drawing also connection between the PDE perspective on message passing. The specific kernel this case the Matérn Kernel, which allows control of smoothness of the covariance structure. Alternative kernel choices are the symmetric normalized graph Laplacian 4 In this work we focus on the Matérn kernel since need a mechanism to explicitly control for kernel smoothness.
32


Reviews:
[{"review_id": "BxTb2aQc4G", "reviewer": "Reviewer_Ewp5", "summary": "This paper proposes a new method of uncertainty estimation on graphs by making an analogy between the evolution of SPDE and message passing. Through introducing the noise process, the proposed method enables GNNs to quantify uncertainty and to achieve detection tasks on graphs. The core innovation is proposing a new noise form based on graph Gaussian Process to learn the spatial-temporal covariance of noise. Experimental results demonstrate the effectiveness of the proposed methods.", "questions": "1. The paper mentions uncertainty estimation but does not explain how the two types of uncertainty are accurately learned after formulating the modeling equation. Therefore, how are epistemic uncertainty and aleatoric uncertainty actually learned?\n\n2. Besides OOD detection, does uncertainty estimation serve any other purposes?", "limitations": "NA", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. Exploring the integration of SPDEs with GNNs is a highly interesting and promising direction. The authors propose a novel form of SPDE and provide a theoretical analysis of it.\n2. The authors provide a detailed descriptions of graph SPDE and related works, which clarifies the logical flow of the paper and enhances its readability.\n\nWeaknesses\n1. The novelty of the proposed model appears to be limited. The combination of SPDEs and GNNs has already been explored in prior works [1,2], and this paper mainly makes adjustments to the noise term. Moreover, the dependence of the noise can also be learned through the stochastic forcing term, rather than simply adding independent noise. Therefore, the authors need to place greater emphasis on this aspect.\n2. The computation of graph Gaussian processes is typically very complex. Therefore, the authors should clarify the computational complexity of the proposed model and compare its efficiency with that of other methods.\n3. The connection between label informativeness and the proposed method in this paper is not clearly emphasized. It is necessary to further highlight the relationship between label informativeness and the proposed approach.\n\n[1] Graph Neural Stochastic Diffusion for Estimating Uncertainty in Node Classification. Xixun Lin et al. ICML 2024.\n\n[2] Uncertainty Modeling in Graph Neural Networks via Stochastic Differential Equations. Richard Bergna et al. ICLR 2025.", "was_revised": true, "final_justification": "Most of the concerns have been addressed, but I still have some reservations regarding the novelty. As a result, I have increased the score by just one point, from 3 to 4.", "rebuttal": "We thank the reviewer for the suggestions and the here we attempt to address your concerns: \n\n__W1. The novelty of the proposed model appears to be limited. The combination of SPDEs and GNNs has already been explored in prior works [1,2], and this paper mainly makes adjustments to the noise term. Moreover, the dependence of the noise can also be learned through the stochastic forcing term, rather than simply adding independent noise. Therefore, the authors need to place greater emphasis on this aspect.__ \n\nWe respectfully disagree that our novelty is limited. First, to clarify, despite some limited degrees of similarity in the  model implementation, our work is fundamentally different from [2], where a latent graph SODE is used with the learning framework formulated using variational inference, similar to the same authors' work in [4], which the latent SODE was used for time series data. Our model focuses on studying message passing on graph data with explicit spatially-correlated noise structures, hence SPDE-motivated, and we are not concerned with sequential or time series modeling, although we think this task is an interesting one to extend our model to. Also from section 3.3, we implement the model as a randomly forced ODE, which is principally motivated by semigroup theory and  Wong-Zakai approximation of SPDE used in [3], rather than proposing a latent SDE model, as was done in [2] and [4]. Therefore, we have provided a much more natural and principled approach compared to [2]. We will add the clarification with the added reference to [2] in our section 2.1 in the camera-ready version. We thank the reviewer for raising the concern.  \n\n[3]. Cristopher Salvi, Maud Lemercier, Andris Gerasimovics: Neural Stochastic PDEs: Resolution-Invariant Learning of Continuous Spatiotemporal Dynamics. NeurIPS 2022. \n\n[4]. Richard Bergna, Felix L. Opolka, Pietro Liò, José Miguel Hernández-Lobato: Graph Neural Stochastic Differential Equations. CoRR abs/2308.12316 (2023). \n\nSecond, for the GNSD model: While prior work such as GNSD [1] did explore the SPDE-GNN connection, our contributions are fundamentally different in three ways.\n\n1. Spatial correlation modeling, which we believe is not just a simple adjustment to the noise term. We model spatially correlated noise through the use of a Matérn gaussian process, which explicitly gives us control of strength of correlation between uncertainty at each node. In [1], the Wiener process was not directly transformed but the heavy lifting was done using an additional diffusion network $G$ without any inductive bias. We don't want to claim that learning $G$ would be impossible, but we suspect that the learning task would be significantly more difficult (our empirical results support that, since we tuned the hyperparameters of both models). \n\n2. Our framework's derivation as randomly forced graph ODE, rather than a latent SDE like in [1], is more principled, using the semigroup and Wong-Zakai approximation of SPDE, instead of simply proposing a neural SDE model as the actual implementation, as was done in [1]. In the camera-ready version, we will add the clarification as part of section 2.1, talking about the latent graph SDE model in the context of sequence data modeling and how our model differs from it.  \n\n3. We provide both a theoretical motivation and empirical validation showing the connection between kernel smoothness, $\\nu$, and the label informativeness. Such a connection moves beyond the traditional homophilic/heterophilic paradigm and was not addressed before in [1]. Specifically, we find significant variations in the required $\\nu$ parameter among the heterophilic/low LI  datasets (roman-empire, minesweeper, amazon ratings, tolokers, questions) and a significant gap between the optimal $\\nu$ values for low LI and high LI datasets. Further, we observe that low $\\nu$ is required to capture long-range uncertainty that traditional methods cannot capture. We believe that drawing and strengthening this connection is a novel synthesis and contributes meaningfully to the work.\n\n4. We introduce the $\\Phi$-Wiener process that generalizes the $Q$-Wiener process. This process generalizes the $Q$-Wiener process through a spectral transformation, and goes beyond merely ``adjusting the noise term'' but instead allows us to develop a principled mathematical framework. We believe that the natural extension as seem by the reviewer is an artifact of the elegance of mathematics, rather than a limit on novelty. \n\nCompared to our work, the relationship between [1] and [2] is closer in the sense that the implementation of [1] closely follows [2], a latent SDE, despite the motivation of using SPDE in [1]. Our work correctly motivates the neural implementation based on the work from [3] using sound mathematical principles, which [1] failed to do, and our implementation differs from [1] because of that. \n\n__W2. The computation of graph Gaussian processes is typically very complex. Therefore, the authors should clarify the computational complexity of the proposed model and compare its efficiency with that of other methods.__\n\nWe address the computational complexity through the Chebyshev approximation (Theorem 4). This reduces the $O(|V|^3)$ eigen decomposition to $O(m |E|)$ operations, where $m$ is the polynomial degree. The error bound shows exponential convergence for smooth kernels. Further, we present a comparison of runtimes in Figure 4 in the appendix. In Figure 4 we see that aside from pubmed and questions, our model is similar in computational cost to the other baselines.\n\n__W3. The connection between label informativeness and the proposed method in this paper is not clearly emphasized. It is necessary to further highlight the relationship between label informativeness and the proposed approach.__\n\nWe agree that the connection between label informativeness is both motivating (line 86-91) and empirical, but lacks theoretical rigor. We do empirically confirm these results in Figure 2(b). Further, we validate this empirical evidence in Table 1 by showing that our method out-performs the benchmarks. We believe that this evidence is enough to justify the connection between LI and SISPDE. In terms of writing, we will surely highlight the relationship further in our camera-ready version. We thank the reviewer for the constructive feedback.\n\n__Q1. The paper mentions uncertainty estimation but does not explain how the two types of uncertainty are accurately learned after formulating the modeling equation. Therefore, how are epistemic uncertainty and aleatoric uncertainty actually learned?__\n\nOur method estimates both types of uncertainty, but we opted to not decompose the uncertainty into epistemic and aleatoric uncertainty since we noticed differing definitions in the literature and a lack of consensus. That being said, one sensible way to understand this is that Aleatoric uncertainty is captured through the stochastic noise term which represents the inherent randomness in the data. The epistemic uncertainty could be quantified through the distribution of final states and measured through the entropy. Here too, we note that spatially correlated noise better captures the true Aleatoric uncertainty, especially for low-LI graphs where neighboring nodes may have different uncertainty patterns.\n\n__Q2. Besides OOD detection, does uncertainty estimation serve any other purposes?__\n\nOur uncertainty framework naturally extends to other applications, including:\n- Active learning for node labeling. Here we would pick the most uncertain vertices to send out for additional labeling\n- Confidence aware predictions\n- Robust predictions in the presence of distributional shifts, either in the graph structure or in the feature distributions.\nWe mentioned some of these directions in future work, such as extending the approach to model stochastic spatial dynamical systems, and are excited about their prospect. We ultimately decided to not include those applications in this work because we believed that this work was self contained with the theoretical developments and the OOD application. In the camera-ready version, we will add the above applications in the last part of section 5. \n\nWe again thank the reviewer for their insightful feedbacks and questions. We believe that by addressing the above weaknesses, the work will be presented more clearly. Please let us know if we have not fully addressed your concerns."}, {"review_id": "zPj5tNFG6H", "reviewer": "Reviewer_9pWG", "summary": "This paper proposes a novel Structure Informed Stochastic Partial Differential Equation (SISPDE) framework for uncertainty estimation on graphs. The key innovation lies in modeling spatially correlated noise via a Matérn-Gaussian-Process-driven SPDE, which generalizes prior Q-Wiener processes by explicitly controlling covariance smoothness through parameter ν. This enables superior uncertainty quantification under both high and low label informativeness (LI) scenarios. Theoretical contributions include proofs for the Φ-Wiener process properties (Theorems 1–2), existence/uniqueness of SPDE solutions (Theorem 3), and Chebyshev approximation bounds (Theorem 4). Experiments on 8 graph datasets demonstrate state-of-the-art OOD detection, especially on low-LI graphs where traditional GNNs struggle.", "questions": "1)​​Kernel Generalization:​​ Why not explore non-Matérn kernels (e.g., RBF)? If ν is pivotal for LI adaptation (Fig 2b), does this limit applicability to non-Matérn covariances?\n\n​​2)Smoothness vs. LI:​​ Can you establish a quantitative relationship between optimal ν and dataset LI (e.g., via regression)? Fig 2b implies heuristic tuning.\n\n​​3)Scalability:​​ For large graphs (e.g., >10^6 nodes), does Chebyshev approximation (Theorem 4) suffice? Have you tested scalability vs. graph size?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Quality \n\n​​Strength:​​ Rigorous theoretical grounding with 4 theorems and appendices. Extensive experiments (8 datasets, 3 OOD types, 5 seeds) validate claims.\n\n​​Strength:​​ Matérn kernel’s ν adapts to LI – low ν captures long-range dependencies in heterophilic graphs (Figure 2b), addressing a critical gap.\n​​\n\nWeakness:​​ Computational cost of Cholesky decomposition for Matérn kernel not deeply analyzed (runtime in Fig 4 but scalability limits unclear).\n\n​​Clarity \n\n\n​​Strength:​​ Well-structured with clear analogies between SPDEs and GNN message passing (Section 2.3–2.4).\n​\n\n​Weakness:​​ Appendix-heavy proofs may disrupt flow; some notation (e.g., Φ-Wiener process in Def 2) requires multiple reads.\n\n\nSignificance \n\n\n​​Strength:​​ Unifies stochastic processes (GNSD), graph kernels (Matérn GP), and PDE-based GNNs (GRAND) into a flexible framework.\n​​\n\nStrength:​​ Achieves SOTA on low-LI graphs (Table 1), where uncertainty estimation is most challenging (Section 4.2).\n\n\n\nOriginality \n\n\n​​Strength:​​ First to integrate SPDE-driven spatially correlated noise with tunable smoothness for graph uncertainty. The physics-inspired approach (Figure 1b) is novel.", "was_revised": true, "final_justification": "I stand with my rating.", "rebuttal": "We thank the reviewer for the valuable feedbacks and questions. Here we attempt to address your questions and concerns below:\n\n__W1: Appendix-heavy proofs may disrupt flow.__ \n\n Due to page limit, we chose to put the proofs in the Appendix section. In the camera-ready version, we will add sketch proof in the paper. For example, for Theorem 1, we will add the following below the theorem, at line 170:\n\n__Sketch Proof__: the result follows from the orthogonality of the eigenvectors of the graph Laplacian and the fact that Wiener processes are zero-centered with correlation structure of $ Cov(W(t),W(s)) = min(t, s)$  and $W(t)-W(s) \\sim \\mathcal{N}(0,t-s)$ for $t>s$.\n\n__W2: Some notation (e.g., $\\Phi$-Wiener process in Def 2) requires multiple reads.__ \n\nIn the camera-ready version, we will add a short clarification part for the relationship between $\\phi$ and $\\Phi$, a function and its matrix functional form, which we believe could be where the reviewer find to be unclear. In particular, we will add the notation of $\\Phi(\\Delta) =  \\text{diag}([\\phi(\\lambda_1), \\cdots,\\phi(\\lambda_n)])$ for diagonal $\\Delta$ and $\\Phi(X) = U \\Phi(\\Lambda)U^T$ for $X=U\\Lambda U^T$ in section 2.4, at line 125 of the manuscript. \n\n__Q1: kernel Generalization: Why not explore non-Matérn kernels (e.g., RBF)? If $\\nu$ is pivotal for LI adaptation (Fig 2b), does this limit applicability to non-Matérn covariances?__\n\nThe RBF kernel can be seen as a special case of theMatérn kernel, that is, when $\\nu \\rightarrow \\infty$. So the RBF kernel does serve as an extreme case for studying the smoothness parameter $\\nu$, for which we provide the additional results in the following table that explicitly uses the RBF kernel. We report the mean and standard deviation over 5 runs for the same set of experiments as other baseline models in the paper, and will add it in the camera-ready version as part of the discussion of the parameter $\\nu$. In the camera ready version, in section 4.2 below line 320, we will add further observation of the result from a smooth kernel (RBF) and state the superiority of the more general Matérn kernel, which gives us control of the smoothness explicitly. \n\n| Dataset | **LABEL OOD** | | | **FEATURE OOD** | | | **STRUCTURE OOD** | | | \n|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|\n| | __AUC__ | __DET-ACC__ | __FPR95__ | __AUC__ | __DET-ACC__ | __FPR95__ | __AUC__ | __DET-ACC__ | __FPR95__ | \n| **cora** | 95.220 ± 0.536 | 88.899 ± 0.752 | 23.671 ± 5.615 | 91.375 ± 0.835 | 85.302 ± 1.150 | 61.573 ± 8.031 | 83.546 ± 2.241 | 77.928 ± 2.609 | 77.629 ± 6.857 | \n| **pubmed** | 79.157 ± 5.815 | 73.594 ± 4.623 | 62.915 ± 12.068 | 90.972 ± 5.786 | 85.612 ± 5.642 | 51.302 ± 32.345 | 95.185 ± 1.907 | 89.559 ± 1.757 | 23.168 ± 20.215 | \n| **citeseer** | 80.259 ± 2.308 | 73.828 ± 2.520 | 62.951 ± 5.878 | 83.453 ± 3.574 | 77.554 ± 3.257 | 80.331 ± 12.477 | 73.641 ± 2.736 | 69.775 ± 1.911 | 88.500 ± 8.154 | \n| **roman_empire** | 51.757 ± 0.565 | 51.630 ± 0.290 | 93.240 ± 0.285 | 51.500 ± 0.259 | 51.340 ± 0.151 | 94.129 ± 0.080 | 56.582 ± 0.677 | 57.800 ± 0.551 | 81.935 ± 0.921 | \n| **minesweeper** | 53.998 ± 3.206 | 53.695 ± 2.160 | 92.580 ± 0.952 | 55.168 ± 3.243 | 56.600 ± 2.221 | 96.014 ± 2.212 | 52.967 ± 1.654 | 56.845 ± 1.412 | 95.924 ± 1.189 | \n| **tolokers** | 60.632 ± 8.902 | 59.263 ± 6.164 | 92.362 ± 7.944 | 76.620 ± 13.619 | 74.516 ± 12.588 | 76.503 ± 33.647 | 93.115 ± 1.226 | 93.986 ± 3.898 | 99.980 ± 0.041 | \n| **questions** | 54.297 ± 0.968 | 54.446 ± 1.383 | 94.466 ± 0.430 | 50.377 ± 0.040 | 50.483 ± 0.059 | 94.614 ± 0.135 | 53.908 ± 0.718 | 61.400 ± 0.391 | 99.534 ± 0.022 | \n| **amazon_ratings** | 52.616 ± 0.489 | 52.310 ± 0.464 | 93.513 ± 0.508 | 51.658 ± 0.320 | 51.367 ± 0.307 | 94.010 ± 0.409 | 88.123 ± 0.071 | 87.262 ± 0.359 | 89.534 ± 0.342 |\n\nTo summarize the results above, the RBF kernel performs decently (ranked 3rd generally) for the high LI datasets, but performed poorly on the low LI datasets, which agrees with the current conclusions we draw from $\\nu$ value and LI. \n\nMoreover, our construction in section 3.1 and 3.2 indicates that as long as the kernel function for the Gaussian process is trace class, the SPDE should have weak solution, which means we can indeed extend it to Kernels that are non-Matérn. Parameter $\\nu$ is an artifact of the Matérn kernel, so other kernel functions may have their own specific parameters. \n\n\n__Q2. Smoothness vs. LI: Can you establish a quantitative relationship between optimal $\\nu$ and dataset LI (e.g., via regression)? Fig 2b implies heuristic tuning.__ \n\nDue to the constraint of NeurIPS rebuttal, we cannot provide a regression figure. However, we choose to provide the data points used for a scatter plot, which should clearly indicates a positive correlation between LI and optimal $\\nu$ values overall. Here are the two lists: LI = [0.590, 0.409, 0.451, 0.110, 0.007, 0.000, 0.001, 0.040] and $\\nu$ = [14.67, 9.33, 18.33, 1.30, 0.57, 0.97, 0.23, 0.90]. They have a Pearson correlation of 0.939 with a p-value of 0.00055, indicating strong linear correlation. \n\n__Scalability: For large graphs (e.g., $>10^6$ nodes), does Chebyshev approximation (Theorem 4) suffice? Have you tested scalability vs. graph size?__\n\nThe Chebyshev approximation has the runtime complexity of $\\mathcal{O}(m|E|)$ where $m$ is the degree of the polynomial and $|E|$ is the number of edges. In our camera ready version, we will add this previously known result at line 237. In our Appendix section C.7 and figure 4, we have provided a runtime analysis for the purpose of studying scalability w.r.t the other baselines, and we found that indeed the performance of the Chebyshev approximation lags when the graph is dense. Since in general  $O(K|E|) < O(|V|^3)$, the performance is bounded by the number of edges and much less expensive than directly computing the eigendecomposition of the graph Laplacian. \n\n\nWe again thank the reviewer for their insightful feedbacks and questions. We believe that by addressing the above weaknesses, the work will be presented more clearly. Please let us know if we have not fully addressed your concerns."}, {"review_id": "mBNs7bGOLY", "reviewer": "Reviewer_TK1Y", "summary": "The authors propose to model message passing in a graph as a stochastic partial differential equation (SPDE) with the flexible covariance structure of the Brownian noise (here realized by a Matérn kernel). This allows for better control over defining the spatial correlation pattern that suits the graph structure, improving the uncertainty estimation and OOD detection performance.", "questions": "- High correlation between nodes (low $\\nu$) comes with high node variance. In such case, what is the strategy to balance those? And how careful should we be to choose the OOD uncertainty threshold in cases with low $\\nu$ ?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength:**\n- The idea is well-motivated and theoretically sound.\n- Proposed method outperforms state-of-the-art uncertainty estimation baselines in graphs.\n\n**Weakness:**\n- No significant weakness\n- To better gain insights in the results presented in Figure 2(b), it would be useful to see the some kind of LI distribution of nodes in the graphs having high LI (e.g Citeseer), medium LI (Pubmed) and low LI(Questions).", "was_revised": true, "final_justification": "This is a good paper. I had minor clarification concern regarding how the variance of nodes would be effected by $ \\nu $, which the reviewers have duly addressed.", "rebuttal": "We thank the reviewer for the positive remarks and for the questions raised. Here we attempt to address the concerns and questions: \n\n__To better gain insights in the results presented in Figure 2(b), it would be useful to see the some kind of LI distribution of nodes in the graphs having high LI (e.g Citeseer), medium LI (Pubmed) and low LI(Questions).__\n\nIn our case, Label Informativeness (LI) is a graph-level metrics since its computation depends on random sampling of the edges of graph, hence it is not directly defined for each node, unlike the traditional but limited homophily and heterophily metrics. To fulfill the reviewer's request, we can randomly sample edges, compute edge LI, and marginalize to obtain node LI, but this would not be the same metrics used in the paper. \n\n__High correlation between nodes (low $\\nu$) comes with high node variance. In such case, what is the strategy to balance those? And how careful should we be to choose the OOD uncertainty threshold in cases with low $\\nu$ ?__\n\n Low $\\nu$ in our case corresponds to low edge LI, and the covariance structure of the Mat\\'ern kernel is able to handle the situation automatically due to the roughness of the kernel. As for the threshold for calculating detection accuracy, we first take the range of scores of IND and OOD samples generated by the models, then take the detection accuracy as the average across 10 equally sized threshold values in between. For each threshold we calculate the accuracy and take the \\textit{minimum} accuracy to report. Otherwise, we use AUC to make the reporting independent of threshold choice. In other words, the evaluation method is not $\\nu$ dependent and is consistent for all the models in comparison.  \n\n\nWe again thank the reviewer for the helpful comments and questions.  We believe that by addressing the above weaknesses, the work will be presented more clearly. Please let us know if we have not fully addressed your concerns."}, {"review_id": "Pc4A33cFvK", "reviewer": "Reviewer_iXcv", "summary": "The paper uses a Graph Stochastic Partial Differential Equation to model uncertainty for node classification. The model can represent uncertainty through the stochasticity of a Wiener Process component guided by a Matern Graph Gaussian Process. It consistently outperforms previous models both on homophilic and heterophilic graphs in terms of out-of-distribution detection.", "questions": "1. Is $\\nu$ a learnable parameter? If not, how is it tuned?\n2. Why is a $\\nu$ needed to capture \"long-range\" interactions if the pointwise transformation of the graph's spectrum is already enabled through $\\Psi$?\n3. Is the term \"long-range\" interaction justified? From my understanding, what happens is that the kernel promotes high frequency signals (in terms of the graph spectrum), which need not be long-range per se. Would \"high-frequency\" patterns be a more suitable term?\n4. For the leave-out-class setting, the authors also consider some datasets with only two classes. Did the authors train the model only in one class in this setting? I find it very surprising that the model learns anything sensible in this case, as just predicting this one class for any input should minimize the training loss.\n5. How is the LI computed? Eq. 1 suggests that one needs access to $p(y_i | y_j)$, but this distribution is unknown as the data-generating process is unknown. Is this distribution estimated as MLE from the entire graph?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "## Strenghts\n1. The approach is clearly motivated as the GSDN [1] model it builds upon assumes homophily also in the uncertainty by using Laplacian-based propagation to guide the uncertainty. Since heterophilic graphs violate this assumption, a learnable diffusion process is needed.\n2. The empirical evaluation of the paper is thorough and methodically sound and shows a clear and consistent improvement over previous work.\n3. The paper provides an insightful intuition for the learned covariance that can be interpreted as similar to rewiring the graph to connect nodes with high mutual information in their label distribution.\n\n## Weaknesses\n### Major\n1. While well-motivated, the approach in this paper is very similar to GSDN. As far as I understand, it only extends on GSDN by introducing pointwise learnable transformations of the eigenvalues of the Graph Laplacian.\n2. The paper is sometimes a bit difficult to follow, especially if the reader is not super familiar with Partial Stochastic Differential Equations. My understanding of the paper's flow is: 1) It motivates a spatial kernel different from the Laplacian due to possible high frequencies in the epistemic uncertainty. 2) It introduces pointwise transformations to the graph spectrum and shows that the resulting process is a Wiener process. 2b) This also holds when applying a Matern kernel using the transformed Laplacian. 3) The proposed model is the solution to the resulting GSPDE, realized through forcing. \n- I found it difficult to follow the red thread that clearly motivates each of these components. For example, in Theorem 3, where exactly does the pointwise transformation of $\\Delta$'s spectrum manifest? What is different from a version where no Matern Kernel (with transformed spectrum?) is used?\n- Later on (Eq. 11-13), it seems to me that there is no pointwise transformation of the graph's spectrum anymore and only the Matern kernel (i.e. where is $\\Phi$?). Can the authors clarify that?\n- Figure 1 shows the Matern kernel (which is used in this work but not a novel contribution) on a synthetic heterophilic graph. What is the takeaway from this figure in terms of the proposed model? Is this to motivate a different diffusion kernel than just the standard Laplacian? If so, how does this motivate the learnable transformation of the graph's spectrum?\n\n### Minor\n1. There are some grammatical errors and inconsistencies in the paper (e.g. whether references to equations, figures, etc. are capitalized). I recommend using a grammar-checking tool to fix those.\n2. The most recent baseline for UQ in node classification, GEBM [2], is cited but not compared against. Can the authors extend their evaluation to this baseline?\n3. Notation like the gradient $\\nabla$ and its adjoint $div$ could be briefly introduced for the graph domain.\n\n## References:\n\n[1]: Lin, Xixun, et al. \"Graph neural stochastic diffusion for estimating uncertainty in node classification.\" Forty-first International Conference on Machine Learning. 2024.\n[2]: Fuchsgruber, Dominik, Tom Wollschläger, and Stephan Günnemann. \"Energy-based Epistemic Uncertainty for Graph Neural Networks.\" The Thirty-eighth Annual Conference on Neural Information Processing Systems.", "was_revised": true, "final_justification": "The authors resolved all minor concerns and answered questions. Since I still maintain some reservations regarding novelty and clarity of the paper, I raise my score by only one point.", "rebuttal": "We thank the reviewer for the comprehensive set of feedbacks and questions, and here we attempt to address your questions and concerns. We refer to reviewers' raised weaknesses by __W1-W8__ and questions as __Q1-Q4__. \n\n__W1 (novelty)__: While building on GNSD's foundation, our contributions are substantial. GNSD uses a fixed graph Laplacian with limited insights on noise propagation on graph. By embedding a noise process with covariance structure through the $\\Phi$ transformation, our approach differs from GNSD with inductive bias and explicitly models the correlation structure of uncertainty. It is a fundamental change in the noise process that enables us to model heterophilic (low LI) uncertainty patterns that GNSD cannot capture, and its implementation in section 3.3 is derived from the theory of semilinear SPDEs in stochastic analysis, which allows a random graph ODE approximation using the semigroup and Wong-Zakai theorem, rather than a simple latent graph SDE in GNSD, which lacks a clear connection with the SPDE representation itself. \n\n__W2 (background)__: we acknowledge that the paper does require some additional backgrounds for Stochastic Partial Differential Equations, and due to the page limit, we put extensive background materials in Appendix A. In the camera-ready version, we will modify line 51-59 of the manuscript to add a description of the method developed in the paper. Here is the content: \n\n_The flow of the paper goes like the following: we first motivate a noise process with a spatial kernel structure that can capture the smoothness of correlation between uncertainty of graph nodes, then we principally derive an end-to-end message passing scheme on graph that utilizes this noise process using the theory of SPDE._\n\nThe reviewer's understanding of the flow is mainly correct, with the caveats that we refrain from talking about aleatoric and epistemic uncertainty explicitly, which we find to be defined differently across existing literature. The intuition of frequency in terms of Laplacian eigenvalues is also relevant, in the sense that the Matérn kernel magnifies graph signal's smoothness for large $\\nu$ and produces rough dependencies with smaller $\\nu$.  The spectral approach for SPDE and Wiener process connects more directly with the Hilbert space theory (the Karhunen-Loeve expansion in definition 2) for representing stochastic processes rather than frequency domain analysis of signals, and we motivate it in the paper from the former perspective. However, the reviewers comment from the signal processing perspective is a promising direction to look at the current framework.\n\n__W3,4 ($\\Phi$ and Matérn kernel)__: Thanks for the question. In section 3.1 we are motivating a general theory of $\\Phi$-Wiener process, which uses a general transformation $\\Phi$, and the Matérn kernel is a special case of the transformation. We touched upon this connection in section 2.4, and in the rest of the paper, we confine ourselves to use only the Matérn kernel. The reason why we want to develop a general framework for $\\Phi$ is to motivate further studies using different kernel functions that can also lead to meaningful solution of SPDEs, which can be left for further work. Nevertheless, the condition of $\\Phi(\\Delta)$ being trace-class allows us to develop the current framework, and the Matérn kernel satisfies the condition and is known solution of SPDE, with relevant backgrounds mentioned in section 2.4 of the paper.\n\n__W5 (Figure 1)__:  Figure 1 is intended to show the need for a flexible spectral transformation. The same heterophilic graph requires fundamentally different uncertainty correlation patterns depending on the underlying label structure. Traditional methods are locked into topology-based correlations, while our $\\Phi$-wiener framework with tunable $\\nu$ allows adaptation to the appropriate correlation structure. The red edges in the small-$\\nu$ limit show correlations that would be impossible with the fixed Laplacian but may be exactly what's needed for heterophilic uncertainty patterns. This is also connected to the observation made in section 4.3, which views the covariance structure as dynamic graph rewiring.\n\n__W6 (Grammar)__: We thank the reviewer for pointing these out. We will review the paper thoroughly for grammatical errors and other notational inconsistencies.\n\n__W7 (GEBM baseline)__: Thanks for the valuable suggestion. With some major efforts, we have now successfully added GEBM to the list of baseline models. We use the hyper-parameter set up in Appendix B.2 of the GEBM paper with the multiscale energy functions described in the paper. We ran the experiments on each dataset 5 times with different seed values, under the 3 types of OOD shifts. Here are the results of this model on the proposed datasets, which differ from the datasets settings used in GEBM. We will include this model's results in the camera-ready version of our paper, in section 4. To summarize the results, our model outperforms GEBM on all datasets except Citeseer, and we found that GEBM gives pathological behavior on the questions dataset for the structural perturbation case, where it produces higher energy score for IND samples than OOD samples. \n\n| Dataset | Label OOD | | | Feature OOD | | | Structure OOD | | |\n|---------|-------------------|---|---|---------------|---|---|-----------|---|---|\n|         | **AUROC** | **Acc** | **FPR95** | **AUROC** | **Acc** | **FPR95** | **AUROC** | **Acc** | **FPR95** |\n| **cora** | 90.50±11.23 | 79.90±10.15 | 30.80±13.73 | 75.00±7.81 | 73.20±2.73 | 61.00±2.79 | 78.50±9.95 | 77.70±5.51 | 51.00±8.29 |\n| **pubmed** | 79.50±2.36 | 64.60±0.79 | 64.30±7.16 | 94.20±2.48 | 90.30±2.48 | 14.90±9.06 | 94.70±1.70 | 91.40±1.21 | 12.70±3.28 |\n| **citeseer** | 94.20±4.52 | 88.60±5.32 | 26.90±13.26 | 82.80±2.55 | 75.40±1.39 | 57.30±4.21 | 80.80±8.00 | 75.90±5.66 | 77.40±3.08 |\n| **roman_empire** | 57.80±2.90 | 54.60±2.33 | 89.60±0.35 | 60.80±1.08 | 57.90±0.82 | 87.90±0.98 | 49.60±0.38 | 53.70±0.21 | 99.90±0.04 |\n| **tolokers** | 56.80±0.72 | 53.00±0.32 | 96.60±0.26 | 5.00±1.44 | 50.50±0.16 | 97.50±0.79 | 1.80±0.30 | 50.90±0.17 | 98.20±0.30 |\n| **minesweeper** | 59.00±3.76 | 54.60±2.18 | 92.20±0.64 | 51.60±13.96 | 58.80±3.44 | 80.10±7.83 | 42.60±16.22 | 64.90±6.27 | 66.20±13.76 |\n| **questions** | 51.60±0.15 | 50.40±0.00 | 97.90±0.13 | 67.20±0.72 | 66.70±0.71 | 91.20±0.30 | 0.00±0.00 | 50.00±0.00 | 100.00±0.00 |\n| **amazon_ratings** | 57.20±2.30 | 52.60±1.01 | 85.90±1.66 | 51.20±4.00 | 61.10±2.31 | 74.90±4.37 | 35.90±6.29 | 61.10±3.21 | 73.50±6.64 |\n\n__W8 (introducing $\\nabla$ on graph)__:  Due to the limited space, we formalized the notations in Appendix A.1. We will add these definitions more systematically in the Appendix and reference them appropriately to make the paper more self contained.\n\n__Q1 ($\\nu$ tuning)__: The $\\nu$ parameter is tuned as indicated in Appendix C.6.\n\n__Q2 ($\\nu$ interpretation)__: The $\\Phi$ function provides the general framework for the spectral transformation of the noise process while $\\nu$ controls the smoothness of the specific functional form of our noise process, the Matérn kernel. In a sense, they serve complementary roles because $\\Phi$ enables the mathematical framework, while $\\nu$ specifies the smoothness needed for LI-related adaptations. _Long-range_ refers to noise correlations between topologically distant nodes on the graph, which is appropriate since low $\\nu$ enables correlations between nodes that are far apart in graph structure. The intuition of frequency in terms of Laplacian eigenvalues is also relevant, as the Matérn kernel magnifies graph signal's smoothness for large $\\nu$ and produces rough dependencies with smaller $\\nu$.  The spectral approach for SPDE and Wiener process connects more directly with the Hilbert space theory (Karhunen-Loeve expansion in definition 2) for representing stochastic processes, rather than frequency domain analysis of signals, and we motivate it in the paper from the former perspective. However, the reviewer's comment is a promising direction to look at the current framework. \n\n__Q3 (two class scenario)__: Thanks for the insightful question. This question illustrates the difference between the task of node classification and OOD detection. On the high level, the question/concern is valid if we are working with a node classification task, which uses the largest logit value to indicate label prediction. Instead, we use the overall entropy of the class distribution to distinguish between IND and OOD samples at test time. If a deterministic node classification model only sees one class at training, it will simply overfit to that one class using cross entropy loss, but our probabilistic model can handle the existence of the other class at test time, precisely because of the uncertainty it induces, since the OOD samples' predicted class probabilities can have a lot higher entropy. In short, for OOD detection, the model sees the _normal_ and learns what the normal looks like at training time and detect the _abnormal_ at test time from normal and abnormal samples. Some previous works have explored the case of OOD samples exposure during training time, which allows them to further the gap between IND and OOD sample's entropy or energy function, but in our case we choose to handle the more general scenario of no OOD exposures during training. This point was touched upon briefly in Appendix C.4, but we will move it to the experimental section and make it more clear. \n\n__Q4 (LI calculation)__: LI is computed using empirical label distributions estimated from the training portion of each dataset. This follows the methodology of [5]. We will rework section 2.2 to make this point more clear.\n\nWe again thank the reviewer for their comprehensive feedbacks and questions. We believe that by addressing the above weaknesses, the work will be presented more clearly. Please let us know if we have not fully addressed your concerns."}]

Author rebuttal:

Meta-review: Summary of the paper:

The paper proposes a novel Structure Informed Stochastic Partial Differential Equation (SISPDE) framework for uncertainty estimation on graphs. The key innovation lies in modeling spatially correlated noise via a Matérn-Gaussian-Process-driven SPDE, which generalizes prior Q-Wiener processes by explicitly controlling covariance smoothness through parameter. This enables superior uncertainty quantification under both high and low label informativeness (LI) scenarios. Theoretical contributions include several proofs for properties, existence/uniqueness of SPDE solutions, and Chebyshev approximation bounds. Experiments on 8 graph datasets demonstrate state-of-the-art OOD detection, especially on low-LI graphs where traditional GNNs struggle.

Summary of the discussion:

All the reviewers agree on acceptance. Two reviewers still have concerns regarding the novelty. One still has concerns regarding the clarity of the paper. One of the reviewers had minor clarification concern regarding how the variance of nodes would be effected by the model's parameter. This was successfully addressed by the authors.

Recommendation:

All reviewers vote for acceptance. I, therefore, recommend acceptance and encourage the authors to use the feedback provided to improve the paper for its final version, especially, to address the remaining concerns of the reviewers.
Decision: Accept (poster)