Skip to content

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

Sep 2026 · arXiv.org · Vol abs/2609.35703 · 0 citations · 38 references
Computer Science

TL;DR

A capacity theorem shows that, under a full-rank feature assumption, a restricted subfamily matches the chaos coefficients of any Gaussian-latent random graph signal, with exponentially decaying truncation error under a growth condition; the task-level claims are established empirically.

Abstract

Reliable deployment of graph neural networks requires calibration, out-of-distribution (OOD) detection, and robustness to distribution shift, yet existing methods address these needs with separate models and objectives. We model uncertain node embeddings as random graph signals: graph Fourier filters capture structural variation, and a scalar orthogonal-polynomial chaos coordinate captures latent stochastic variation. The resulting doubly-spectral stochastic (DSS) expansion supplies task-matched readouts from one representation: the mean coefficient encodes class evidence for the energy-based OOD score, the higher-order coefficients encode structured logit variation, and quadrature averaging over the chaos coordinate defines the single predictive distribution used for prediction and calibration. A capacity theorem shows that, under a full-rank feature assumption, a restricted subfamily matches the chaos coefficients of any Gaussian-latent random graph signal, with exponentially decaying truncation error under a growth condition; the task-level claims are established empirically. DSS-GNN has two deployment modes: standalone, or as a residual branch beside a deterministic encoder (DSS-Hybrid). Standalone DSS-GNN achieves the lowest Brier score among the compared uncertainty-aware baselines on all 14 node classification benchmarks without post-hoc correction; DSS-Hybrid achieves the best AUROC on most node-OOD settings, competitive cross-graph OOD detection, and the strongest shifted accuracy on all 7 GOOD concept-shift benchmarks under standard empirical risk minimization (ERM). Cross-evaluating both modes on all three tasks shows that each remains effective on the other's tasks, with documented exceptions, and yields explicit deployment guidance.

View source

Similar papers

#machine learning Preprint Sep 2026

Spectral Graph Neural Networks with Hermite Polynomials: A Comprehensive Study

The analysis and experiments clarify when Hermite propagation is useful and how calibration and regularization affect its performance, and identify a regime in which plain HermNet outperforms matched polynomial-basis alternatives, including with a jointly trained nonlinear predictor.

Shu-Guang Wu · 0 citations

Stable Filters for Generative Modeling of Graph Signals

This paper derives explicit Wasserstein stability bounds that quantify the effect of relative graph perturbations on the generated distributions and introduces a principled framework for designing stable graph filters that preserve the smoothing behavior of graph heat diffusion, while boosting structural stability.

M. Schmidt, Gonzalo Mateos · 1 citation
#machine learning Preprint Sep 2026

Provable Guarantees for Spectral Structured Prediction

This paper studies binary node label recovery on signed graphs with edge-flip noise via a simple spectral method that decodes node labels from the signs of the principal eigenvector of the noisy signed adjacency matrix and develops graph structure-agnostic theoretical guarantees for approximate inference of node labels...

Violet Zheng, Jean Honorio · 0 citations
Preprint Sep 2026

Multiscale Renormalization of Weighted Networks

A weighted multiscale model whose full probability law, encoding both link creation and weight assignment, has an invariant compound-Poisson form under arbitrary node aggregation is identified, enabling consistent modeling and reconstruction of weighted networks across arbitrary scales.

Mattia Marzi, F. Pijpers, Diego Garlaschelli · 0 citations
Conference Open access Sep 2026

DeepSTE: Deep Spectral Temporal Embeddings for Dynamic Graph Representation Learning

DeepSTE is proposed, a deep spectral temporal embedding framework for dynamic graphs that learns RFF representations via Monte Carlo importance sampling with a tractable proposal distribution and adopts a data-dependent scale parameter to construct the frequency proposal distribution reflecting time–frequency uncertain...

Qiang Huang, Ke Liu, Ren-Jie Gong et al. · 0 citations

Related blog posts

MIT News · Artificial Intelligence Sep 29, 2026

Who we become when we talk to machines

Professor Sherry Turkle’s new book, “Artificial Intimacy,” offers a withering critique of chatbots and the antisocial dynamics she believes they encourage.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.