AIResearchGraphsUncertainty

A Unified Uncertainty Representation for Graph Neural Networks

DSS-GNN stores each node’s embedding as a short polynomial chaos expansion in one shared Gaussian variable and filters it along two spectral axes, graph frequency and chaos order. Readouts of this one representation, computed in a single deterministic pass, give calibrated predictions, OOD scores and robustness to distribution shift.

Paper Code

A diagram of DSS-GNN: input features on a graph are lifted to chaos coefficients arranged on a graph-frequency axis and a Hermite axis; a DSS layer applies low-pass and high-pass filters, chaos gates and a nonlinearity at quadrature nodes; boxes below show the readouts and the two deployment modes
The DSS-GNN architecture, from the paper. Input features are lifted to chaos coefficients indexed by graph frequency and chaos order; each layer filters every coefficient with two Chebyshev filters, combines them with chaos gates, and applies the nonlinearity at Gauss–Hermite points before projecting back; the final coefficients feed the readouts and either deployment mode.

This post introduces our NeurIPS 2026 paper, “A Unified Uncertainty Representation for Graph Neural Networks via Doubly-Spectral Stochastic Expansion,” written with Thomas Markovich of Block, Florence Regol of Mila and Yizhou Sun of UCLA. A graph neural network that is used for real decisions should do three things besides predicting: give probabilities that match how often it is right, which is calibration; recognize inputs unlike its training data, which is out-of-distribution or OOD detection; and keep its accuracy when the data changes, which is robustness to distribution shift. Existing methods usually address one of these with a dedicated model. DSS-GNN instead stores, for every node, a short polynomial expansion in a single Gaussian random variable rather than one fixed vector, and filters this expansion along two spectral axes, graph frequency and chaos order, so that different readouts of one representation, all computed in a single deterministic forward pass, serve the three tasks. On its own, DSS-GNN has the lowest Brier score among the compared uncertainty-aware methods on all 14 node classification benchmarks; added as a residual branch to a standard GCN, which we call DSS-Hybrid, it has the best OOD AUROC among the compared methods on 6 of 9 node-level settings and, trained with plain empirical risk minimization, the highest accuracy on all 7 GOOD concept-shift benchmarks.

Why a graph neural network should say how sure it is

Many datasets are networks, in which molecules are atoms connected by bonds, a payment platform is accounts connected by transactions, and a road system is intersections connected by roads. Each node has features, such as the words on a web page or an account’s history, while edges say which nodes are related, and a graph neural network, or GNN, predicts something about each node, such as its class, by combining the node’s own features with those of its neighbors. GNNs now appear in drug discovery, fraud detection and traffic forecasting, settings in which a wrong answer given with high confidence is often worse than an answer that says “I am not sure,” and a deployed model should therefore satisfy three requirements.

Three synthetic plots: a reliability curve with a calibrated line along the diagonal and an overconfident line below it; two overlapping score distributions for familiar and unfamiliar inputs; and two accuracy curves that fall as the data shifts, one slowly and one steeply
The three requirements, illustrated with synthetic curves. (a) A calibrated model that reports 90% confidence is right about 90% of the time, while an overconfident model is right less often than it claims. (b) An OOD detector assigns each input a score, and a useful score separates familiar inputs from unfamiliar ones. (c) Under distribution shift, a robust model loses accuracy slowly as the test data moves away from the training data.

We measure them with standard numbers. The Brier score, the average squared difference between the predicted class probabilities and the true answer written as a 0/1 vector, measures calibration and accuracy together, so that a model is penalized both for being wrong and for being more or less confident than it should be, and lower is better. AUROC measures OOD detection as the probability that a randomly chosen OOD node gets a higher “unfamiliar” score than a randomly chosen in-distribution node, so that 50 is chance and 100 is perfect. And shifted accuracy is plain accuracy measured on test data drawn from a different distribution than the training data.

On graphs the three requirements are linked, because how certain a prediction should be depends on the node’s neighborhood as well as on its own features, and all three are versions of one question, when and how confidently the model can predict. Yet most existing methods target only one of them. Sampling methods such as MC-dropout and Deep Ensembles run the model many times; evidential models such as GPN give OOD evidence but not shift-robust classification; energy-based detectors give scores that separate familiar from unfamiliar inputs but not calibrated probabilities; and robust-training methods do not model uncertainty explicitly. Our goal was a single representation of uncertainty inside the GNN, from which each task reads what it needs, and to build it we combine two mathematical tools that are each well established, spectral graph theory and polynomial chaos, which the next four sections introduce.

Signals on a graph and their frequencies

Take a graph with NN nodes. A graph signal assigns one number to each node, so it is a vector x∈RNx \in \mathbb{R}^N, and a node feature, such as how often the word learning appears on a web page, is a graph signal, as is each coordinate of a GNN’s hidden representation. The set of all graph signals is a vector space, written ℓ2(V)\ell^2(V), with the usual inner product ⟨x,y⟩=∑ixiyi\langle x, y\rangle = \sum_i x_i y_i, which means that we can add signals, scale them, measure their length and, most importantly, write every signal in a basis.

The basis that respects the graph comes from the graph Laplacian, which in its simplest form is L=D−AL = D - A, where AA is the adjacency matrix and DD the diagonal matrix of node degrees. For any signal,

x⊤L x=∑(i,j) ∈ edges(xi−xj)2, x^\top L\, x = \sum_{(i,j)\,\in\,\text{edges}} (x_i - x_j)^2 ,

which is small when connected nodes have similar values and large when they do not. Spectral GNNs usually work with a normalized Laplacian, such as L=I−D−1/2AD−1/2L = I - D^{-1/2} A D^{-1/2}, which has the same interpretation and eigenvalues between 0 and 2.

Because LL is symmetric, its eigenvectors u1,…,uNu_1, \dots, u_N form an orthonormal basis of ℓ2(V)\ell^2(V). Each eigenvector is itself a graph signal, and its eigenvalue λj\lambda_j measures how much that signal changes across edges, so that the eigenvectors play the role that sines and cosines play for sound: a small λ\lambda means a smooth, slowly varying pattern, a low frequency, and a large one a pattern that changes sign across many edges, a high frequency. Any signal can be written as

x=∑j=1Nx^j uj,x^j=uj⊤x, x = \sum_{j=1}^{N} \hat x_j\, u_j, \qquad \hat x_j = u_j^\top x ,

and the coefficients x^j\hat x_j are its graph Fourier transform. Because the basis is orthonormal, the squared length of the signal is the sum of the squared coefficients, ∥x∥2=∑jx^j2\|x\|^2 = \sum_j \hat x_j^2.

Four copies of a small graph colored by Laplacian eigenvectors from smooth to rough, a graph colored by a signal, and a bar chart of that signal’s graph Fourier coefficients, the largest at low frequencies
A small graph with three communities. (a) Four Laplacian eigenvectors (red positive, blue negative): the smoothest separate the communities, and the roughest changes sign across most edges. (b) A signal that mostly follows the communities, plus noise. (c) Its graph Fourier coefficients: most of the signal is in a few low-frequency modes, and the noise is spread evenly over all frequencies, so it accounts for most of the high-frequency coefficients.

Filtering a signal on a graph

On a regular grid, convolution is the same as multiplication in the Fourier domain, and because a graph has no notion of shifting a pattern from one place to another, spectral GNNs turn this property into the definition of convolution on a graph. A spectral filter changes how much of each frequency a signal contains, multiplying the coefficient x^j\hat x_j by a number g(λj)g(\lambda_j) and transforming back, so that in matrix form the output is y=g(L) xy = g(L)\,x. Computing all the eigenvectors of a large graph is expensive, so spectral GNNs choose gg to be a polynomial, which needs only repeated multiplication by LL, and a polynomial of degree KK combines information from neighbors at most KK edges away. ChebNet, a standard spectral GNN, writes the polynomial in the Chebyshev basis,

g(L)=∑k=0Kck Tk(L~),L~=2λmax⁡L−I, \begin{gathered} g(L) = \sum_{k=0}^{K} c_k\, T_k(\tilde L), \\ \tilde L = \tfrac{2}{\lambda_{\max}} L - I , \end{gathered}

where T0(t)=1T_0(t) = 1, T1(t)=tT_1(t) = t and Tk+1(t)=2t Tk(t)−Tk−1(t)T_{k+1}(t) = 2t\,T_k(t) - T_{k-1}(t), and the coefficients ckc_k are learned. The rescaling moves the eigenvalues into [−1,1][-1, 1], where Chebyshev polynomials are well behaved, staying bounded by 1 and giving close to the best polynomial approximation of a given degree, and GCN is the special case of a first-order Chebyshev filter with a single shared coefficient.

Two kinds of filter matter here. A low-pass filter keeps smooth patterns and removes rough ones, which suits graphs where neighbors tend to share labels, a property called homophily that holds for citation networks, while a high-pass filter keeps the differences between neighbors and is useful when neighbors tend to differ, which is heterophily. DSS-GNN applies both a low-pass and a high-pass Chebyshev filter in every layer, so it can learn which frequencies matter on each graph.

Plots of the first four Chebyshev polynomials and of a low-pass and a high-pass filter response across graph frequency, above three copies of a graph showing an input signal and its low-pass and high-pass outputs
(a) The first four Chebyshev polynomials. (b) A low-pass and a high-pass filter response, each a degree-2 polynomial; the tick marks are the eigenvalues of the example graph, the only places where the response is used. (c) An input that mixes the community pattern with a rough pattern. (d) The low-pass output keeps the communities. (e) The high-pass output keeps the rough part.

Random quantities as functions of a Gaussian

So far everything has been deterministic. To represent uncertainty we want each node’s hidden representation to be a random quantity rather than a fixed vector, and the question is how to store a random quantity with a finite list of numbers. The approach we use, called polynomial chaos, starts from one standard Gaussian variable ω∼N(0,1)\omega \sim \mathcal{N}(0, 1) and writes the random quantity as a function of it, Y=f(ω)Y = f(\omega): Y=μ+σωY = \mu + \sigma\omega, for example, is a Gaussian with mean μ\mu and standard deviation σ\sigma, while Y=e0.5 ωY = e^{0.5\,\omega} is a skewed, always positive random quantity.

There are several ways to give a neural network a random representation, and each has a cost. Sampling methods such as MC-dropout and Deep Ensembles represent uncertainty by many forward passes or many models, which multiplies the cost and adds sampling noise to every estimate; parametric methods give each embedding a mean and a variance, which is cheap but describes only Gaussians, and a nonlinearity such as ReLU destroys the Gaussian form after a single layer; and evidential methods put a distribution on the class probabilities at the output but leave the hidden representation deterministic. Polynomial chaos takes a different route, borrowed from uncertainty quantification in engineering, where since the stochastic finite element methods of Ghanem and Spanos in 1991 it has been the standard way to push random inputs through physical simulations. It represents a random quantity by the coefficients of an orthogonal expansion, much as a Fourier series represents a function, so that the mean and the variance can be read off the coefficients in closed form, non-Gaussian shapes need only a few more coefficients, and every computation, nonlinear ones included, can be carried out deterministically by quadrature rather than by sampling.

The functions ff with finite variance, E[f(ω)2]<∞\mathbb{E}[f(\omega)^2] < \infty, form a vector space written L2(γ)L^2(\gamma), where γ\gamma is the Gaussian distribution. It has an inner product, ⟨f,g⟩=E[f(ω) g(ω)]\langle f, g\rangle = \mathbb{E}[f(\omega)\,g(\omega)], exactly as graph signals do, the difference being that this space is infinite-dimensional, and it too has a natural orthogonal basis, the Hermite polynomials,

He0(ω)=1,    He1(ω)=ω,He2(ω)=ω2−1,    He3(ω)=ω3−3ω, \begin{gathered} \mathrm{He}_0(\omega) = 1, \;\; \mathrm{He}_1(\omega) = \omega, \\ \mathrm{He}_2(\omega) = \omega^2 - 1, \;\; \mathrm{He}_3(\omega) = \omega^3 - 3\omega, \end{gathered}

and so on, generated by the recurrence Hen+1(ω)=ω Hen(ω)−n Hen−1(ω)\mathrm{He}_{n+1}(\omega) = \omega\,\mathrm{He}_n(\omega) - n\,\mathrm{He}_{n-1}(\omega). After normalizing, Ψn=Hen/n!\Psi_n = \mathrm{He}_n / \sqrt{n!}, they satisfy

E[Ψm(ω) Ψn(ω)]={1m=n0m≠n. \mathbb{E}\big[\Psi_m(\omega)\,\Psi_n(\omega)\big] = \begin{cases} 1 & m = n \\ 0 & m \ne n. \end{cases}

The parallel with the graph is closer than it might look. The Laplacian eigenvectors are sorted by eigenvalue, and the jj-th one on a path graph changes sign j−1j-1 times, while the Hermite polynomials are sorted by order nn, and Ψn\Psi_n has nn zeros. Both families are eigenvectors of a symmetric operator, L uj=λjujL\,u_j = \lambda_j u_j on the graph and −L Ψn=n Ψn-\mathcal{L}\,\Psi_n = n\,\Psi_n for the Ornstein–Uhlenbeck operator Lf=f′′−ωf′\mathcal{L}f = f'' - \omega f' on L2(γ)L^2(\gamma), so the chaos order nn plays the role of a frequency for randomness. The Gaussian is not the only possible base variable, since generalized polynomial chaos pairs other distributions with their own orthogonal polynomials, Legendre polynomials for a uniform variable for instance, but the Gaussian and its Hermite polynomials are the classical choice, the one Wiener introduced, and the one whose quadrature rule we will use.

Two line plots: Laplacian eigenvectors of a path graph with zero to three sign changes, and normalized Hermite polynomials of orders zero to three over the Gaussian variable, with the Gaussian density shaded beneath
Two orthonormal bases, both ordered by how often they oscillate. (a) Laplacian eigenvectors of a path graph, sorted by eigenvalue. (b) Normalized Hermite polynomials, sorted by order; they are orthonormal when weighted by the Gaussian density (gray), which is small where the polynomials grow large.

The polynomial chaos expansion

Because the Hermite polynomials form a complete orthonormal basis, a classical result of Wiener and of Cameron and Martin, every finite-variance function of ω\omega can be written as

Y(ω)=∑n=0∞Yn Ψn(ω),Yn=E[Y(ω) Ψn(ω)]. \begin{gathered} Y(\omega) = \sum_{n=0}^{\infty} Y_n\, \Psi_n(\omega), \\ Y_n = \mathbb{E}\big[Y(\omega)\,\Psi_n(\omega)\big]. \end{gathered}

This is the polynomial chaos expansion, where “chaos” is Wiener’s historical name and has nothing to do with chaotic dynamics. Two facts make it useful for uncertainty: the mean is the first coefficient, E[Y]=Y0\mathbb{E}[Y] = Y_0, because Ψ0=1\Psi_0 = 1 and every other Ψn\Psi_n has mean zero, and the variance is the sum of the squared remaining coefficients, Var[Y]=∑n≥1Yn2\mathrm{Var}[Y] = \sum_{n\ge1} Y_n^2, a quantity we call the chaos energy.

In practice we keep only the terms up to order PP. With P=1P = 1, Y≈Y0+Y1ωY \approx Y_0 + Y_1\omega, which is exactly a Gaussian, while with P≥2P \ge 2 the expansion can also describe skewed or otherwise non-Gaussian quantities. For sufficiently regular functions the coefficients shrink quickly with nn, exponentially fast under the smoothness condition of the paper’s Theorem 2, so a small PP is often enough.

Three panels: truncations of order 1, 2 and 3 of an exponential function of a Gaussian variable; the corresponding distributions, order 1 symmetric and order 3 skewed like the true one; and a log-scale bar chart of coefficients shrinking with order
The expansion of Y=e0.5ωY = e^{0.5\omega}, whose coefficients are Yn=e1/8 0.5n/n!Y_n = e^{1/8}\,0.5^n/\sqrt{n!}. (a) As functions of ω\omega, the order-2 and order-3 truncations follow the true curve closely, while order 1 is a straight line. (b) As distributions, order 1 is a symmetric Gaussian, while order 3 reproduces the skew of the true distribution. (c) The coefficients shrink faster than exponentially; the first is the mean, and the others set the spread and shape.

Two axes at once: the doubly-spectral expansion

Now we combine the two ideas. A random graph signal assigns a random quantity to each node, and in DSS-GNN all the randomness comes from one shared Gaussian variable ω\omega, so that every node’s value is a function of the same ω\omega. This is a deliberate simplification: a single variable keeps every average over the randomness one-dimensional, so that a handful of quadrature points computes it exactly, and it makes the variations of neighboring nodes move together, a limitation we return to at the end. Such signals are the elements of the product space ℓ2(V)⊗L2(γ)\ell^2(V) \otimes L^2(\gamma), and the products uj Ψn(ω)u_j\,\Psi_n(\omega) of a graph eigenvector and a Hermite polynomial form a complete orthonormal basis of it, so that every such signal has a doubly-spectral stochastic expansion,

Y(ω)=∑n=0∞∑j=1Nuj Y^n,j Ψn(ω). Y(\omega) = \sum_{n=0}^{\infty} \sum_{j=1}^{N} u_j\, \hat Y_{n,j}\, \Psi_n(\omega).

Each coefficient Y^n,j\hat Y_{n,j} has two indices, a graph frequency jj, which says how smooth the pattern is across the graph, and a chaos order nn, which says how the pattern varies with ω\omega. This is where the name DSS, for doubly-spectral stochastic, comes from, since both factors of the basis are eigenvectors of a symmetric operator.

Three copies of a graph colored by a random signal at three values of the Gaussian variable; the mean and standard deviation of each node on the same graph; and a heat map of coefficient size over graph frequency and chaos order
A random graph signal built for illustration. (a) Its values for three values of ω\omega; all nodes change together because they depend on the same ω\omega. (b) The order-0 coefficient is the mean of each node. (c) The higher-order coefficients give each node’s standard deviation. (d) The size of each coefficient on the two axes: here the mean is smooth across the graph (order 0, low frequencies), the order-1 variation is at middle frequencies, and the order-2 variation at high frequencies.

An ordinary, deterministic GNN representation is the special case in which only the n=0n = 0 coefficients are nonzero. DSS-GNN keeps the first P+1P+1 orders and learns how to update them.

The DSS layer

A DSS layer stores, for every node, P+1P + 1 coefficient vectors H0,H1,…,HPH_0, H_1, \dots, H_P, one per chaos order, instead of one hidden vector, and the represented embedding is H(ω)=∑n=0PHn Ψn(ω)H(\omega) = \sum_{n=0}^{P} H_n\,\Psi_n(\omega). The input features are first mapped to these coefficients by P+1P+1 learned linear maps, and each layer then updates them along both axes. On the graph axis, every coefficient HnH_n goes through the low-pass and the high-pass Chebyshev filter, giving Glp(L) HnG_{\mathrm{lp}}(L)\,H_n and Ghp(L) HnG_{\mathrm{hp}}(L)\,H_n, and on the chaos axis, per-order chaos gates αn(ω)\alpha_n(\omega) and βn(ω)\beta_n(\omega), which are learned constants or themselves low-order expansions in ω\omega, weight and combine the two filter outputs.

A neural network also needs a nonlinearity such as ReLU, but the ReLU of a polynomial is not a polynomial, so it mixes the chaos orders and has no closed form. DSS-GNN computes this step by evaluating, applying and projecting back: it evaluates the embedding at SS fixed values ω1,…,ωS\omega_1, \dots, \omega_S, applies the linear map and the ReLU at each of them, and computes the new coefficients with weights μs\mu_s,

Hmnew=∑s=1Sμs ReLU(H~(ωs)) Ψm(ωs),m=0,…,P. \begin{gathered} H_m^{\text{new}} = \sum_{s=1}^{S} \mu_s\, \mathrm{ReLU}\big(\tilde H(\omega_s)\big)\, \Psi_m(\omega_s), \\ m = 0, \dots, P. \end{gathered}

The points ωs\omega_s and weights μs\mu_s are a Gauss–Hermite quadrature rule, and the SS-point rule computes the Gaussian average of any polynomial of degree up to 2S−12S - 1 exactly. The experiments use S=4S = 4, which computes the filter and gate terms exactly for P≤3P \le 3, covering the recommended P=1P = 1 to 2, while at larger PP these terms are integrated approximately; the ReLU step is always an approximation, and the paper analyzes its error.

Three panels: four Gauss–Hermite nodes and weights under the Gaussian density; the error of Gauss–Hermite quadrature falling much faster than that of random sampling as evaluations increase; and a ReLU curve with an order-3 polynomial rebuilt from its values at the four nodes
(a) The four Gauss–Hermite points and their weights. (b) Estimating the Gaussian average of a smooth function of ω\omega: the error of Gauss–Hermite drops much faster with the number of evaluations than the error of random sampling. (c) Applying ReLU at the four points and projecting back gives an order-3 polynomial close to the true function over the range where the Gaussian has most of its mass.

An important consequence is that ω\omega is never sampled. The network is deterministic from input to output, with no Monte Carlo sampling and no sampling noise in training or at test time, and with P=0P = 0, a single coefficient and constant gates, the DSS layer reduces to an ordinary polynomial spectral GNN layer, of which ChebNet and GCN are special cases, so DSS-GNN extends a standard architecture rather than replacing it. The paper’s implementation also offers two variants of the graph-filtering step, described in its appendix, and the variant is selected per dataset on validation data. The cover figure at the top of this post shows the whole architecture.

Reading out uncertainty

After the last layer, a linear map gives each node ii one logit vector per chaos order, Zi,0,Zi,1,…,Zi,PZ_{i,0}, Z_{i,1}, \dots, Z_{i,P}, with one entry per class, and evaluating the expansion at the quadrature points gives logits zi(s)=∑nZi,n Ψn(ωs)z_i^{(s)} = \sum_n Z_{i,n}\,\Psi_n(\omega_s). Three quantities are read from these coefficients. The first is the predictive distribution, used for prediction and calibration,

pˉi=∑s=1Sμs softmax(zi(s)), \bar p_i = \sum_{s=1}^{S} \mu_s\, \mathrm{softmax}\big(z_i^{(s)}\big),

which is the class probability averaged over ω\omega; the predicted class is the one with the largest pˉi\bar p_i, so the prediction and its reported confidence come from the same distribution. The second is the chaos energy, Ei=∑n≥1∥Zi,n∥2\mathcal{E}_i = \sum_{n\ge1} \|Z_{i,n}\|^2, the total variance of the node’s logits, and training minimizes the cross-entropy of the mean logit Zi,0Z_{i,0} plus λreg\lambda_{\mathrm{reg}} times the average chaos energy, with λreg\lambda_{\mathrm{reg}} chosen per dataset on validation data and zero on three of the 14 datasets. The third, used for OOD detection, is the energy score, computed from the mean logit alone,

senergy(i)=−log⁡∑cexp⁡(Zi,0,c), s_{\mathrm{energy}}(i) = -\log \sum_{c} \exp\big(Z_{i,0,c}\big),

where lower energy means more confident. The score comes from energy-based models, in which a classifier’s logits define an unnormalized density over inputs, ∑ceZi,0,c\sum_c e^{Z_{i,0,c}}, whose negative logarithm is the energy, so that inputs unlike the training data, to which the model gives little density, receive high energy. It was proposed for OOD detection on images and adapted to graphs by GNNSafe, which also averages the scores over each node’s neighborhood, a step called score propagation that we follow.

The paper’s Proposition 2 gives two reasons for these choices. The first concerns calibration: when S≥P+1S \ge P + 1 and the loss is smooth, averaging the loss over ω\omega equals the loss at the mean logit plus a correction, to second order,

ℓˉi≈ℓ(Zi,0,yi)+12 tr(Hi Σzi), \bar\ell_i \approx \ell(Z_{i,0}, y_i) + \tfrac{1}{2}\,\mathrm{tr}\big(\mathcal{H}_i\,\Sigma_{z_i}\big),

where Σzi\Sigma_{z_i} is the covariance of the node’s logits, built from the higher-order coefficients, and Hi\mathcal{H}_i is the curvature of the loss. The correction is large only where the logits vary and the loss is curved, which is near a decision boundary, and for cross-entropy it is at most a quarter of the chaos energy, the quantity that the training objective penalizes; on the Minesweeper dataset it concentrates on the hardest nodes. The second concerns OOD detection: if an input lowers every class logit by the same amount, the softmax probabilities do not change, so no score computed from them, such as predictive entropy, can detect the change, while the energy score changes by exactly that amount, and the mean logit therefore keeps information that a softmax discards.

Three panels: a cross-entropy curve with two nodes’ logit spreads, the average loss rising well above the loss at the mean only for the node near the decision boundary; identical softmax bars for two nodes; and energy bars for the same two nodes differing by exactly 3
(a) Two nodes whose logits vary by the same amount over ω\omega (colored curves at the bottom): for the node near the decision boundary the average loss is clearly above the loss at the mean, while for the confident node the two are nearly equal. (b, c) Node B has the logits of node A minus 3, so the softmax probabilities are identical, but the energy is higher by exactly 3.
A scatter of nodes by loss curvature and chaos energy, colored by the size of the second-order correction, beside bar charts of accuracy and Brier score for nodes grouped by correction size
The second-order correction on the Minesweeper dataset, from the paper. (a) Each node, placed by loss curvature and chaos energy and colored by the size of the correction. (b) Nodes grouped by correction size: the group with the largest correction has the lowest accuracy and the highest Brier score.

Two further points are needed to state this correctly. The calibration effect comes through training, not through a correction applied at test time: after training, the predictive distribution pˉi\bar p_i and the plain softmax of the mean logit agree closely, their predicted classes differing on at most 0.21% of test nodes, and on none at all for 10 of the 14 datasets, and their accuracy and Brier score by at most 0.04 points and 0.003. This holds on the datasets where λreg\lambda_{\mathrm{reg}} is zero as well, and no temperature scaling or other post-hoc calibration is used. And because the energy score reads only the mean logit, the design predicts that OOD detection should not depend on the chaos order, which the experiments confirm, since varying only PP from 0 to 3 leaves the energy AUROC on Cora-structure flat, at 91.0, 91.2, 90.9 and 90.8, in a separate set of runs at one fixed configuration whose level differs from the main results. What the DSS representation adds shows up when everything else is held fixed: on the three Cora settings, with the same energy readout, score propagation and training objective, it separates in-distribution from OOD nodes more widely than the GCN encoder alone does.

Two ways to deploy it

DSS-GNN can be used in two modes, which share the same representation and the same readouts, as the bottom right of the cover figure shows. In the standalone mode the whole network is made of DSS layers. In DSS-Hybrid, a DSS-GNN branch is added next to a conventional encoder, a two-layer GCN in our experiments to match the baselines, and the logits are combined as zhyb=zbase+γres Z0z^{\mathrm{hyb}} = z^{\mathrm{base}} + \gamma_{\mathrm{res}}\, Z_0 with a learned scale γres\gamma_{\mathrm{res}}, the GCN being warmed up for a few epochs before the DSS branch is activated. The chaos-energy penalty keeps the branch from fitting noise in the training distribution, while its two filters can adjust which graph frequencies the model relies on when the distribution changes, a design choice that the experiments support rather than a guarantee.

What the theory says, and what it does not

The paper proves four results. Proposition 1 says that P=0P = 0 recovers standard spectral GNNs, Proposition 2 explains the readouts, as above, and two theorems describe the layer itself. Theorem 1 concerns its operator structure: without the ReLU, and with a quadrature rule fine enough to be exact, a DSS layer is a linear operator on the joint domain of graph frequency and chaos order, acting frequency by frequency, with the Chebyshev filters setting the response to each graph frequency and the chaos gates setting how the orders mix.

Theorem 2 concerns capacity. If the node features have full rank, which requires at least as many features as nodes, a restricted one-layer DSS-GNN can match the chaos coefficients of any random graph signal driven by a Gaussian variable, up to any chosen order PP; as PP and the width grow, these outputs can approximate any such signal, and for targets that meet a strong smoothness condition, an extension to an entire function, analytic on the whole complex plane, with controlled growth, the truncation error shrinks exponentially in PP. For the common case of fewer features than nodes, as on Cora with 1,433 features for 2,708 nodes, the same construction matches, through order PP, every target whose chaos-coefficient columns lie in the span of the features, under one additional positivity condition that can be met by adding a constant feature.

These are statements about what the layer can represent, and they do not by themselves guarantee good calibration, OOD detection or robustness, claims that rest on the experiments below. The exponential truncation bound is consistent with what we observe, since low orders, PP = 1 or 2, already capture most of the benefit.

Results

We evaluated the standalone model on calibration and DSS-Hybrid on OOD detection and distribution shift, and then cross-evaluated both modes on all three tasks. Calibration was measured on 14 node classification benchmarks, citation, co-purchase, co-authorship, web-page and heterophilous graphs, with 10 splits each, against the uncertainty-aware GNNs TFE-GNN and G-Δ\DeltaUQ, and with no post-hoc calibration. OOD detection used the GNNSafe benchmark, whose nine node-level settings perturb the graph structure, perturb the features or hold out classes on Cora, Amazon-Photo and Coauthor-CS, and whose two cross-graph settings train on one graph and test on others: on Twitch the German network against the Spanish, French and Russian ones, and on Arxiv papers up to 2015 against papers from 2018 to 2020. The baselines were GNNSafe, GNNSafe++, GPN, Graph-EBM, MC-dropout with 20 passes and Deep Ensembles of 5 models, and DSS-Hybrid follows the GNNSafe++ protocol, with the same GCN configuration, the same energy-margin training objective and the same score propagation, so that the two differ only in the DSS branch. Distribution shift was measured on 7 concept-shift settings of the GOOD benchmark against 13 baselines, most of them designed for distribution shift, such as IRM, VREx, GroupDRO and TAR, while DSS-Hybrid is trained with plain empirical risk minimization.

Three horizontal bar charts of DSS-GNN’s or DSS-Hybrid’s margin over the strongest competitor on each dataset, for Brier score, OOD AUROC and shifted accuracy, nearly all bars positive
The margin of DSS-GNN or DSS-Hybrid over the strongest competitor on each dataset (named in parentheses); orange means our model is better. Numbers are means from the paper’s tables, where the standard deviations can be found. (a) Brier score, standalone DSS-GNN. (b) OOD AUROC, DSS-Hybrid. (c) Shifted accuracy on GOOD concept shift, DSS-Hybrid.

Standalone DSS-GNN has the lowest Brier score among the compared uncertainty-aware methods on all 14 datasets and the best accuracy on 13, the exception being Squirrel, where TFE-GNN is more accurate, at 71.56% against 68.06%. The margins vary, large on Wisconsin, Minesweeper, Citeseer and Roman-Empire and 0.003 or less on Squirrel, Amazon-Ratings and Questions, and the gains are not an accuracy effect, since standard GNNs such as GCN and GAT match or exceed DSS-GNN’s accuracy on Cora and Citeseer but are less calibrated. With P=0P = 0, that is, with no chaos terms, DSS-GNN is still a competitive two-filter spectral GNN, so the comparison across PP isolates what the chaos expansion adds.

A bar chart of the Brier-score reduction from the best chaos order above zero for each dataset, beside line plots of relative Brier score against chaos order for seven datasets, lowest around orders 1 and 2
From the paper. (a) The percentage reduction in Brier score from the best chaos order P>0P > 0 compared with P=0P = 0, per dataset. (b) Brier score relative to P=0P = 0 as the order grows, for seven datasets.

Raising PP above 0 improves the Brier score on 12 of the 14 datasets, and on every dataset P=1P = 1 or P=2P = 2 is within 0.02 of the best order tried, so we recommend P=1P = 1 to 2 as the default. P=1P = 1 is exactly a Gaussian representation, and the higher orders add non-Gaussian structure that matters on some datasets: on Citeseer, going from P=1P = 1 to P=2P = 2 lowers the Brier score from 0.346 to 0.308.

For OOD detection, DSS-Hybrid has the best AUROC on 6 of the 9 node-level settings, including all three Cora settings, at 94.32, 97.60 and 94.11 against 90.62, 95.56 and 92.75 for GNNSafe++, and on the other three it is within 0.13 points of the best method, where both it and GNNSafe++ are above 99.6. On Twitch it improves on GNNSafe++ in every metric, with an AUROC of 95.75 against 95.36 and a false positive rate at 95% recall of 22.40 against 33.57, while on Arxiv it is 1.41 AUROC points behind GNNSafe++, at 73.36 against 74.77, though it has the best false positive rate and in-distribution accuracy. Against MC-dropout and Deep Ensembles, which receive the same score propagation, DSS-Hybrid has the higher AUROC on all 11 settings, in one forward pass against their 20 passes and 5 models, and score propagation itself contributes up to 18.2 AUROC points, on Twitch.

Eight density plots of the energy score for in-distribution and OOD nodes, for four methods on Cora and on Twitch
The distribution of the energy score for in-distribution nodes (blue) and OOD nodes (red) on Cora-structure (top) and Twitch (bottom), from the paper. Lower energy means more confident, and DSS-Hybrid separates the two groups on both datasets.

Under distribution shift, DSS-Hybrid trained with plain empirical risk minimization has the highest mean shifted accuracy on all 7 GOOD concept-shift settings, by margins from 0.08 points on GOOD-Cora/word to 9.94 points on GOOD-WebKB/university. The chaos terms contribute here too, since in the standalone model P=1P = 1 improves shifted accuracy over P=0P = 0 on GOOD-Cora/word by 1.7 points, on GOOD-Cora/degree by 1.2 and on GOOD-Arxiv/time by 0.6.

We also ran each mode on the other’s tasks. On calibration, the standalone model has the best Brier score on all 14 datasets and is stronger than the hybrid on 13 of them, Tolokers being the exception, while the hybrid is never worse than its own GCN base beyond noise and gains a great deal where the GCN is weak, as on Roman-Empire, with 27.7 points more accuracy and a Brier score lower by 0.33. On OOD detection, the standalone model is effective on 10 of the 11 settings, its energy score failing to separate the groups only on Twitch, and the hybrid is stronger than the standalone on 10 of the 11. On concept shift, the standalone model is above every published baseline on 5 of the 7 settings and at the level of plain empirical risk minimization on the other 2, while the hybrid is highest on all 7. This gives practical guidance: the standalone model is the choice when calibration on a single graph matters most, especially when neighbors tend to differ, and the hybrid is the choice when a strong conventional encoder already exists, for transfer across graphs, and for OOD detection with few labels.

The cost is moderate. Graph filtering and coefficient memory grow with the number of chaos orders P+1P + 1, and the nonlinearity step with the number of quadrature points SS, but no eigendecomposition is ever computed, and the measured training time per epoch at P=2P = 2 is 2.9 times that of P=0P = 0 on Cora, 1.2 times on Amazon-Ratings and 1.1 times on ogbn-arxiv, where each additional order adds about 4%, while memory grows linearly with P+1P + 1.

Limitations

The two modes share a representation and readouts but are not interchangeable everywhere. The standalone model needs BatchNorm to train stably when labels are scarce, as every baseline encoder in the OOD benchmark does, and its energy score fails on Twitch, while the hybrid inherits the limits of its encoder, so that on small heterophilous graphs, where a GCN is a poor fit, it matches its GCN base but does not improve on it. All variation comes from a single Gaussian ω\omega shared by every node, so variations at different nodes are perfectly dependent and the model cannot represent independent noise at each node; this is enough for per-node calibration and OOD scores, and it is what makes single-pass quadrature possible, but joint uncertainty across nodes is not modeled, and with qq latent variables a full quadrature grid would need SqS^q points, a cost that sparse grids can reduce and that we leave to future work. The expansion also adds the compute overhead reported above, and the theorems describe what the layer can represent, while the benefits at the level of tasks are established empirically, on the benchmarks we tested.

Takeaways

Uncertainty can be part of the representation itself: writing each node’s embedding as a polynomial in one Gaussian variable gives every node a mean, in order 0, and a description of its variation, in the higher orders, which the network learns directly. Graph frequency describes how a pattern varies across the network and chaos order how it varies with the random variable, both coming from orthonormal eigenbases, and the DSS layer filters along both. Gauss–Hermite quadrature replaces random draws, so one deterministic forward pass gives all the uncertainty readouts, and one representation serves several tasks through matched readouts, the averaged predictive distribution serving prediction and calibration, the mean-logit energy serving OOD detection, and a regularized DSS branch beside a standard encoder helping under distribution shift. If you work with graphs where decisions depend on knowing how much to trust a prediction, we hope DSS-GNN is useful to you, and the code is on GitHub.

This work was partially supported by NSF 2303037, NSF 2312501, NSF 2531008, NSF 2553619, SRC JUMP 2.0 Center, CDSC Industry Partners, Amazon Research Awards, Snapchat, and Google Gifts. Part of this work was done while Fred Xu was an intern at Block, Inc., and we thank Block, Inc. for its support. The cover figure and the figures of the second-order correction, the chaos order and the energy densities are from the paper; the other figures were made for this post, with synthetic examples except for the results chart, which uses the numbers in the paper’s tables.