A Unified Uncertainty Representation for Graph Neural Networks via Doubly-Spectral Stochastic Expansion

Motivation

• Graph uncertainty depends on both neighborhood structure and node features, while calibration, OOD detection, and shift robustness are facets of when and how confidently a model predicts.Existing approaches often target only one need: sampling-based uncertainty, evidential or intrinsic uncertainty models, energy-based detectors, or robust training.Source: §1 · pp. 1–2

Contributions

• DSS-GNN combines graph-frequency filtering and a scalar Gaussian chaos coordinate to represent uncertainty, then derives task-matched readouts from that shared representation.Its standalone and hybrid modes are evaluated across calibration, OOD detection, and shift robustness.Source: §1 · p. 2
• Under a full-rank feature assumption, a restricted DSS subfamily matches the chaos coefficients of any Gaussian-latent random graph signal, with exponentially decaying truncation error under a growth condition.The theorem establishes representational capacity, not calibration, OOD detection, or robustness; those task-level claims are empirical.Source: §1 · p. 2
• Standalone DSS-GNN has the lowest Brier score among compared uncertainty-aware baselines on all 14 calibration benchmarks, while DSS-Hybrid leads on most node-OOD settings and all 7 concept-shift benchmarks under ERM.The paper also cross-evaluates both modes on all three tasks and provides deployment guidance.Source: §1 · p. 2

Spectral GNNs and uncertainty on graphs

• Spectral GNNs define graph convolutions as polynomial filters of the graph Laplacian, with ChebNet using learned Chebyshev coefficients and a rescaled Laplacian.The rescaling keeps filtering localized and supports low- or high-pass responses under homophily or heterophily.Source: §2 · p. 2

Polynomial chaos and the doubly-spectral expansion

• Polynomial chaos expands a square-integrable random variable in orthonormal Hermite polynomials of a standard Gaussian latent, with truncation at order P.The chaos energy corresponds to variance.Source: §2 · pp. 2–3
• Combining the Laplacian eigenbasis and Hermite basis yields a tensor-product space for random graph signals, with coefficients indexed by graph frequency and chaos order.DSS-GNN learns a truncation and propagation rule on this space; the latent is scalar and each chaos coefficient is a graph signal.Source: §2 · p. 3

3 Method

• DSS-GNN learns coupled propagation of joint graph-frequency and chaos-order coefficients through parameterized graph filters and non-intrusive chaos projection.The network represents each node with P + 1 coefficient vectors; deterministic Gauss–Hermite evaluations handle nonlinearities without Monte Carlo sampling.Source: §3 · p. 3

3.1 DSS layer

• Each DSS layer applies dual low- and high-pass Chebyshev filters along graph frequency and per-order gates along chaos order, then projects activated evaluations back onto the Hermite basis.With S ≥ P + 1, the polynomial filter and gate terms are integrated exactly at the gate orders used in practice; the nonlinearity uses a controlled non-intrusive projection.Source: §3 · p. 3, §3.1 · pp. 3–4

3.2 Uncertainty readout

• The quadrature-averaged predictive distribution supplies both prediction and calibration, while the zeroth-order mean logit supplies the energy-based OOD score.Higher-order coefficients encode structured logit variation; energy retains common-logit shifts that softmax-derived summaries cancel.Source: §3.2 · p. 4, §3.3 · p. 5

3.3 Theoretical properties

• With nonlinearities omitted and sufficient Gauss–Hermite quadrature, the linearized DSS layer acts frequency by frequency, with Chebyshev filters setting graph-frequency response and chaos gates setting chaos-order mixing.At P = 0 and Pg = 0, the layer reduces to a standard polynomial spectral GNN layer, including ChebNet and GCN as special cases.Source: §3.3 · p. 4
• Under full-rank features, a restricted DSS subfamily matches the chaos coefficients of any Gaussian-latent random graph signal through order P; with an entire Gaussian extension of controlled growth, truncation error decays exponentially.The full-rank condition requires din ≥ N; the theorem establishes capacity, not task-level performance guarantees.Source: §3.3 · p. 5
• The quadrature-averaged loss differs from the mean-logit loss at leading order by a curvature-weighted chaos-covariance term, while energy changes under common-logit shifts that leave softmax unchanged.For cross-entropy, the correction is at most one quarter of the chaos energy, which the training objective regularizes; calibration, OOD, and robustness claims remain empirical.Source: §3.3 · p. 5

3.4 Hybrid deployment

• DSS-Hybrid adds DSS-GNN as a residual branch beside a deterministic base encoder, using a shared class readout and a learned residual scale.The chaos-energy regularizer constrains the residual, and the design is an inductive bias rather than a distribution-free guarantee.Source: §3.4 · p. 5

3.5 Training and downstream tasks

• Training supervises the mean logit while projection updates couple it to higher chaos orders, and regularization constrains their variation.The mean-logit objective agrees to first order with the quadrature-averaged loss; the measured readout gap remains small where the selected regularization weight is small or zero.Source: §3.5 · p. 6

4.1 Setup

• The evaluation covers 14 node-classification benchmarks, nine node-OOD settings plus two cross-graph settings, and seven GOOD concept-shift settings.Calibration is evaluated over 10 splits; OOD settings use 3 seeds, and GOOD uses standard ERM.Source: §4.1 · p. 6

4.2 Node classification and calibration

• DSS-GNN has the lowest Brier score among compared uncertainty-aware baselines on all 14 datasets without post-hoc calibration, and the best accuracy on 13.The comparison covers homophilous and heterophilous datasets.Source: §4.2 · p. 6, Table 1 · p. 7

4.3 OOD detection

• DSS-Hybrid has the best AUROC on 6 of 9 node-OOD settings and improves over GNNSafe++ on every Twitch metric.On the three remaining node-OOD cells, it is within 0.13 points of the best method; on Arxiv it has the best FPR95 and ID accuracy while remaining within 1.41 AUROC points of GNNSafe++.Source: §4.3 · p. 7, Table 2 · p. 8, Table 3 · p. 8

4.4 Distribution-shifted classification

• DSS-Hybrid achieves the best mean shifted accuracy on all seven GOOD concept-shift settings under standard ERM.Margins range from 0.08 points on GOOD-Cora/word to 9.94 points on GOOD-WebKB/university.Source: Table 4 · p. 9, §4.4 · p. 9

4.5 Standalone versus hybrid: cross-evaluation and deployment guidance

• Across-task evaluation finds standalone stronger for calibration on 13 of 14 datasets and hybrid stronger for OOD detection on 10 of 11 settings.Standalone is above every Table 4 baseline on 5 of 7 GOOD settings and at ERM's level on the other two; hybrid is above every baseline on all seven.Source: Table 5 · p. 9, §4.5 · pp. 9–10
• The authors recommend standalone for calibration-critical single-graph use, particularly under heterophily, and hybrid when a strong conventional encoder exists, for cross-graph transfer, or for sparse-label OOD detection.Standalone requires BatchNorm stabilization in sparse-label regimes; hybrid shares its encoder's failures.Source: §4.5 · p. 10

5 Conclusion and Limitations

• The standalone model has the lowest Brier score among compared uncertainty-aware baselines on all 14 calibration benchmarks; the hybrid has strongest AUROC on most node-OOD settings and strongest shifted accuracy on all 7 concept-shift benchmarks under ERM.Source: §5 · p. 10
• A single shared Gaussian latent limits cross-node logit covariance to rank at most P, so the model does not represent independent per-node noise or joint cross-node uncertainty.The standalone also needs BatchNorm stabilization in sparse-label regimes and does not separate cross-graph OOD inputs on Twitch; the hybrid matches rather than improves on unsuitable small heterophilous encoders.Source: §5 · p. 10

A.1 Background: Wiener chaos and Gauss–Hermite quadrature

• Wiener chaos decomposes Gaussian-latent signals into orthogonal orders, while the graph Fourier basis decomposes graph structure; together their tensor-product basis represents the shared-latent signal domain.The scope is signals measurable with respect to the scalar latent, not signals with independent per-node latents.Source: §A.1 · pp. 16–17
• Gauss–Hermite quadrature exactly integrates polynomials through degree 2S − 1; with gate order Pg ≤ 1, S ≥ P + 1 suffices for the DSS triple products.For general nonlinear activations, non-intrusive projection is approximate, with its error decomposed separately.Source: §A.1 · p. 17

A.2 Supporting technical results

• The technical results separate chaos truncation error from quadrature projection error, which vanishes when the projected integrand is a sufficiently low-degree polynomial.After a general nonlinear activation, the integrand is no longer polynomial, so quadrature error reflects the rule’s approximation quality.Source: §A.2 · pp. 18–19

A.3 Proof of Proposition 1 (Generalization)

• At P = 0 with scalar gates, the DSS layer reduces to a standard polynomial spectral GNN layer, recovering ChebNet, GCN, and related models as special cases.The P = 0 update is a polynomial in the graph Laplacian.Source: §A.3 · p. 19

A.4 Proof of Theorem 1 (Doubly-spectral operator)

• In the linearized regime, the DSS layer acts frequency by frequency: Chebyshev filters set graph-frequency response, while chaos gates mix chaos orders.The operator result assumes omitted pointwise nonlinearity and exact Gauss–Hermite integration of the relevant triple products.Source: §A.4 · pp. 20–21

A.5 Proof of Theorem 2 (Representational capacity and truncation)

• Under rank(X) = N, a restricted one-layer DSS-GNN matches any target’s chaos coefficients through order P, and varying P and width yields dense outputs in L2.The construction uses ReLU, width 2d(P + 1), quadrature size S = P + 1, constant gates, and an identity low-pass filter.Source: §A.5 · p. 21
• The constructive capacity result is theoretical rather than a guarantee of calibration, OOD detection, or robustness, and its full-rank assumption requires din ≥ N.The practical model typically has din < N and uses small P and learned filters rather than the construction’s specified settings.Source: §A.5 · p. 23
• When rank(X) < N, the construction matches truncated targets only when their chaos-coefficient columns lie in range(X) and the stated positivity condition holds.Appending a constant feature column can permit matching targets whose coefficient columns lie in range([X, 1]).Source: §A.5 · p. 23

A.6 Proof of the Truncation Bound in Theorem 2

• For targets with an entire extension of controlled Gaussian growth, the omitted chaos tail—and thus the construction’s truncation error—decays exponentially with P.The growth condition requires a uniform bound of the form |Ȳik(z)| ≤ Aik exp(a|z|^2), with a < 1/4.Source: §A.6 · pp. 23–24

A.7 Proof of Proposition 2 (Stochastic and mean-logit readouts)

• With S ≥ P + 1 and the stated loss regularity, the quadrature-averaged loss equals the mean-logit loss plus a leading curvature-weighted chaos-covariance correction.The quadrature average cancels the first-order term; the second-order term uses the loss Hessian and logit covariance.Source: §A.7 · pp. 24–25
• Softmax-derived uncertainty summaries are invariant to a common logit shift, whereas the energy score decreases by exactly that shift.The analogous quadrature-averaged energy expansion has a stochastic correction that vanishes for common-logit variation, while the mean-logit shift is read out linearly.Source: §A.7 · pp. 25–26
• For cross-entropy, the Hessian is positive semidefinite with common-logit offsets as its nullspace, so stochastic variation consisting only of common shifts contributes no correction.The nullspace result holds for finite logits; the correction also vanishes in the fully confident limit.Source: §A.7 · pp. 24–26
• The readout gap is bounded by chaos covariance, and the mean-logit and averaged-prediction argmaxes agree when the top-two probability gap exceeds B tr(Σzi).The bound applies when S ≥ P + 1; because training penalizes tr(Σzi), it explains close agreement in practice.Source: §A.7 · p. 26

B.1 Baseline methods

• Across evaluated benchmarks, DSS has the strongest calibration and GOOD results among compared methods and the best AUROC on 7 of 11 OOD settings; G-∆UQ’s anchor sampling causes OOM in the GNNSafe OOD pipeline.Calibration and GOOD use plain cross-entropy or ERM; DSS-Hybrid uses the same energy-margin objective as GNNSafe++ for OOD.Source: §B.1 · p. 27
• The task-coverage table marks whether methods evaluate calibration, OOD detection, and distribution shift, distinguishing secondary evaluations and OOM cases.The baselines include spectral and intrinsic-uncertainty calibration methods, energy-based OOD methods, stochastic predictors, and distribution-shift methods such as IRM, GroupDRO, VREx, and TAR.Source: Table 6 · p. 27, §B.1 · pp. 27–28

C Dataset Statistics and Licenses

• The dataset section summarizes experimental datasets and their sources; all are publicly available and used in accordance with their respective licenses.Table 7 lists dataset sources and licenses.Source: C Dataset Statistics and Licenses · p. 28, Table 7 · p. 28

C.1 Calibration benchmarks

• The calibration experiments use node-classification datasets, with results reported over 10 splits per dataset; the listed heterophilous-suite datasets come from Platonov et al. [26].The dataset table notes corrected Cornell files and bidirectional edge counts.Source: Table 8 · p. 28

C.2 OOD detection benchmarks

• Node-OOD benchmarks perturb structure, features, or labels on Cora, Amazon-Photo, and Coauthor-CS; cross-graph OOD uses ID and OOD graphs from different domains.The reported dataset statistics are for the in-distribution graph.Source: Table 9 · p. 29

C.3 GOOD distribution-shift benchmarks

• The GOOD distribution-shift experiments use node-level concept-shift settings, with the domain identifying the covariate defining the shift.GOOD-Cora uses the full Cora citation graph (CoraFull), not the 7-class Planetoid subset.Source: Table 10 · p. 29, §C.3 · p. 29

D.1 General training protocol

• All DSS-GNN models use mean-logit cross-entropy with chaos-energy regularization; the quadrature-averaged loss supervises every quadrature node but is used only in the analysis.The regularization strength is selected per dataset on validation Brier, with 0.01 as the default; training uses validation-loss early stopping.Source: §D.1 · p. 29

D.2 Calibration (Table 1)

• Calibration selects architecture variants and chaos order using validation Brier, with shared defaults including P=2 and S=4.The per-dataset search varies propagation, filter symmetry, optimizer, hidden dimension, layer count, and dropout; Table 11 lists architecture variants and overrides.Source: §D.2 · pp. 29–30, Table 11 · p. 30
• DSS-GNN achieves the best mean Brier on all 14 calibration datasets, while P=1 or P=2 is within 0.02 Brier of the best swept order on every dataset.At S=4, the recommended P=1–2 is exact for polynomial filter and gate terms; the S sweep at P=2 changes Brier by at most 0.011 on 12 of 14 datasets.Source: §D.2 · p. 30, Table 12 · p. 31

D.3 OOD detection (Section 4.3)

• OOD DSS-Hybrid uses a warmed-up GCN base with a DSS residual branch and the GNNSafe++ energy-margin regularizer; scoring uses energy propagated over the graph.The standalone OOD and GOOD pipelines add per-chaos-channel BatchNorm in most listed cells, with specified exceptions.Source: §D.3 · pp. 30–31

D.4 Distribution shift (Table 4)

• For distribution shift, DSS-Hybrid uses a warmed-up GCN-plus-DSS residual model trained with standard ERM and no robust objective.Published ERM-through-TAR baseline results are taken from the TAR paper [38], while G-∆UQ is run in the authors’ pipeline.Source: §D.4 · p. 31

D.5 Software, hardware, and compute budget

• Reported experiments total approximately 8 A100 GPU-hours; ablations add approximately 100 GPU-hours, and the project total is approximately 200 A100 GPU-hours.Hyperparameter selection required an additional approximately 25 GPU-hours.Source: §D.5 · p. 32

E.1 Polynomial order P across all datasets

• On every dataset, P=1 or P=2 is within 0.02 Brier of the best swept order; four datasets favor an order above two.The four are PubMed, Squirrel, Amazon-Ratings, and Minesweeper.Source: Figure 3 · p. 32, §E.1 · p. 32

E.2 Chaos order on OOD detection and under distribution shift

• At selected standalone configurations, P=1 adds +1.7, +1.2, and +0.6 shifted-accuracy points over P=0; hybrid energy AUROC stays flat across P on tested OOD settings.The energy score reads the mean logit alone, so chaos order can be selected for calibration without affecting detection in this ablation.Source: §E.2 · pp. 32–33

E.3 Energy-score propagation

• Propagation improves AUROC on 9 of 11 settings, by up to +18.2 points on Twitch; Cora/label is an exception at −6.7 points.Raw and propagated energy scores use identical trained checkpoints, isolating propagation’s effect.Source: Table 16 · p. 33, §E.3 · p. 33

E.4 Chaos energy regularization λreg

• Moderate regularization (λreg=10^-3 or 10^-2) gives the best calibration on most datasets, but λreg=0 is best on Citeseer, Wisconsin, and Roman-Empire.On Texas, Brier changes from 0.366 at λreg=0 to 0.213 at λreg=10^-2.Source: Table 17 · p. 34, §E.4 · p. 34

E.5 Number of quadrature nodes S

• At P=2, Brier varies by at most 0.011 across S=2–8 on 12 of 14 datasets; Wisconsin scores 0.142 at S=2 versus 0.109 at S=3.For P=2 with deterministic gates, S≥3 is the theoretical minimum for exact chaos arithmetic; the Cornell spread is within one standard deviation.Source: Table 18 · p. 34, §E.5 · p. 34

E.6 Contribution decomposition: backbone vs. chaos

• The controlled P=0→P>0 comparison improves calibration on 12 of 14 datasets, with 3.6–27.9% Brier reduction.The comparison holds each dataset’s architecture fixed, isolating the chaos expansion’s contribution from the backbone.Source: Table 19 · p. 35, §E.6 · p. 35

E.7 Computational overhead

• At P=2, epoch overhead is 2.9× on Cora, 1.2× on Amazon-Ratings, and 1.1× on ogbn-arxiv versus P=0.Measured overhead grows linearly with P; each additional order adds one graph-filter evaluation and Gauss–Hermite projection per layer.Source: §E.7 · pp. 35–36, Table 20 · p. 36

E.8 Summary of component evidence

• The component comparisons associate chaos expansion with calibration, spectral filtering and the residual with accuracy under heterophily and shift, and propagated energy scoring with OOD detection.Each task’s readout uses a different part of the same representation.Source: §E.8 · p. 36, Table 21 · p. 36

Comparison protocol

• The standard GCN and GAT baselines use two layers, 64 hidden units, Adam, and the same 10 splits as DSS-GNN.The stochastic-baseline comparison uses 20 MC-dropout passes or five independently trained ensemble models, with probabilities averaged.Source: F Comparison with Standard GNN Baselines · p. 37

Stochastic baselines under the same protocol

• DSS-GNN’s Brier score is lower on all 14 datasets than either MC-dropout or Deep Ensembles under the same 10-split protocol.Ensembling improves GCN Brier by at most 0.008 on any dataset; MC-dropout sometimes worsens it.Source: Table 22 · p. 37, F Comparison with Standard GNN Baselines · p. 37

Comparison with standard GNN baselines

• On Cora, GCN and GAT are more accurate than DSS-GNN (87.5% and 87.8% vs. 86.6%) but have worse Brier scores (0.213 and 0.222 vs. 0.207).On Citeseer, GAT matches DSS-GNN in accuracy (80.6% vs. 80.2%) but has a higher Brier score (0.353 vs. 0.308).Source: F Comparison with Standard GNN Baselines · p. 37, Table 23 · p. 38

G.1 Protocols

• Calibration uses matched hybrid/base budgets; standalone OOD and GOOD runs follow their respective pipelines with validation-selected configurations.Source: §G.1 · p. 39

G.2 Calibration: standalone, hybrid, and the hybrid’s GCN base

• The hybrid matches or exceeds its GCN base in accuracy on 11/14 datasets, while standalone is preferred on small heterophilous graphs.Source: Table 24 · p. 39, §G.2 · pp. 39–40

G.3 OOD detection: standalone versus hybrid

• Hybrid leads on 10/11 OOD settings; standalone reaches 73.73 AUROC versus the hybrid’s 73.36 on Arxiv, while hybrid is preferred for Twitch at 95.75.Source: Table 25 · p. 40, §G.3 · p. 40

G Cross-Evaluation of the Two Deployment Modes

• Across tasks, DSS-Hybrid is stronger on 10/11 OOD settings and beats every baseline on all 7 concept-shift settings; standalone remains effective with task-specific exceptions.Source: §G.3 · p. 40, §G.4 · p. 40

G.4 Distribution shift: standalone versus hybrid

• Under GOOD concept shift, hybrid exceeds every baseline on all 7 settings; standalone exceeds every baseline on 5 and matches ERM on the other two.Source: Table 26 · p. 40, §G.4 · p. 40

G.5 Readout coincidence

• Hybrid’s quadrature and mean-logit readouts agree on all 14 datasets (disagreement 0.0000), with accuracy differing by at most 0.04 points.Source: Table 27 · p. 41, §G.5 · p. 41

G.6 BatchNorm under the calibration protocol

• BatchNorm leaves Cora and Roman-Empire unchanged within noise and Wisconsin within one SD, but Citeseer accuracy drops 13.2 points; it stabilizes the sparse-label OOD pipeline.Source: §G.6 · p. 41, Table 28 · p. 41

G.7 Covariate shift on GOOD

• DSS-Hybrid exceeds ERM GCN on 6/7 GOOD covariate shifts; the Cora/degree loss is within 1.8 points, while Arxiv baselines did not converge.Source: §G.7 · p. 41, Table 29 · p. 42

• DSS coefficients are indexed by graph Fourier modes and Hermite polynomials of a scalar Gaussian latent, with dual Chebyshev filters along the graph axis.Source: Figure 4 · p. 43, H Architecture Overview and Notation · p. 43
• Each DSS layer filters every chaos channel, couples filter branches with per-order gates, applies a shared map and ReLU at quadrature nodes, then projects back.Source: H Architecture Overview and Notation · pp. 43–44
• The mean-logit energy score serves OOD detection, while the quadrature-averaged predictive distribution serves class prediction and calibration; chaos energy is a regularizer and uncertainty scalar.Source: H Architecture Overview and Notation · p. 43
• Standalone DSS-GNN and DSS-Hybrid use the same readouts; the hybrid adds a scaled DSS residual branch to a warmed-up GCN base.Source: H Architecture Overview and Notation · p. 43