Organizations: Dept. of Electrical and Systems Eng., University of Pennsylvania, Philadelphia, PA 19104 USA · Department of Signal Processing and Communications, King Juan Carlos University, Madrid, Spain
Sampling stochastic signals supported on a graph underlies many graph machine learning tasks, including recommender systems, forecasting in financial markets, and wireless network optimization. In these settings, the target signals are realizations of unknown conditional distributions. However, prevailing approaches rely mostly on intricate, application-tailored designs that often regress to a conditional mean instead of sampling from the conditional law. This paper unifies such problems as conditional graph signal generative modeling and tackles them with a single denoising diffusion framework. We learn a reverse diffusion process, parametrized by graph neural networks (GNNs), that draws graph signals conditioned directly on the graph topology and on node-feature side information. The reverse process is realized by a novel architecture, the U-Graph Neural Network (U-GNN), which generalizes the image-convolutional U-Net to graph-structured signals. The U-GNN performs multi-resolution encoder--decoder processing in which pooling and unpooling reduce to a learned node selection, expressed by nested selection matrices, and a zero-padded lifting of coarse signals back to the full node set. The graph convolutions are carried out on the original graph, with a stride that sets their hop reach, so the U-GNN bypasses explicit graph coarsening at every resolution. We demonstrate our method on two generative tasks: stock price forecasting and optimal wireless resource allocation, with extensive numerical results in both domains.
Discrete graph generation has emerged as a powerful paradigm for modeling graph-structured data, yet state of the art models often rely on Graph Transformers or higher order architectures. We revisit this design assumption by introducing GenGNN, a modular message passing backbone for graph generation. GenGNN enables powerful generation by persisting edge fields through latent refinement of coupled node edge graph states, all without requiring global attention. Diffusion models integrating GenGNN achieve over 90 percent validity on standard benchmark datasets, performing within margins of Graph Transformer backbones and achieving up to 2x or even 5x faster inference. Systematic ablations isolate how GenGNN is resilient to oversmoothing during generative denoising, indicating each GenGNN component is necessary for downstream generation quality. Finally, representation-space analysis suggests GenGNN learns functionally similar representations to more theoretically-expressive architectures; even at deeper layers. As such, GenGNN uplifts local message-passing to challenge prevailing assumptions that performant discrete graph generation requires global attention or higher-order representations. Source Code Available Here
Conditional generative models, particularly diffusion-based methods, have recently been applied to graph prediction by modeling the target as a conditional distribution given the input graph, yielding competitive results compared to deterministic predictor. However, existing diffusion-based prediction methods typically require expensive iterative denoising at inference and often suffer from unstable sampling, which motivates recent efforts to reduce inference denoising steps and enable stable sampling via techniques such as consistency training. Despite this progress, we find that existing consistency training methods for graph prediction could potentially fall into a shortcut solution: the model may attempt to satisfy the self-consistency constraint by ignoring the noisy target (i.e., assigning it negligible weight), ultimately collapsing into a purely deterministic predictor. To mitigate such shortcut solution, we propose GCCM, a graph contrastive consistency model that goes beyond isolated pairwise matching between the same target at different noise levels by introducing negative pairs into a contrastive consistency objective. This adds an additional separation requirement, making the shortcut solution no longer trivially sufficient to satisfy the proposed objective. Moreover, we apply feature perturbation to the input node/edge features to break identical conditioning on the input graph, so that the shortcut no longer yields the same predictions across noise levels and becomes less attractive. Extensive experiments on benchmark datasets demonstrate that GCCM mitigates the shortcut solution and yields consistent performance improvements in graph prediction compared to deterministic predictors.
Generating signals on graphs requires permutation-equivariant models that exhibit stability with respect to relative structural perturbations. While favorable stability properties of Graph Neural Networks (GNNs) have been well documented, it is unclear how structural errors propagate through the dynamics of continuous generative flow models that are gaining traction for graph signal generation. In this paper, we analyze continuous normalized flow models parameterized by GNNs and show that permutation equivariance is preserved for both the resulting continuous-time ordinary differential equations and their discrete numerical approximations used as graph signal samplers. Our primary contribution is to derive explicit stability bounds on the generated probability distributions, which quantify how relative graph perturbations affect the final sampled signals. Motivated by these theoretical bounds, we introduce a stability-promoting regularized flow matching strategy that actively penalizes the spatial Lipschitz constant of the vector field during model training. Experiments using synthetic smooth signals on stochastic block model graphs and real-world fMRI signals on brain connectomes demonstrate that this bound-oriented approach yields generative models that are more robust to structural noise, without sacrificing output quality.