Are Expressive Encoders Necessary for Discrete Graph Generation? DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper
Jay Revolinsky, Harry Shomer, Jiliang Tang · 2026
Read Are Expressive Encoders Necessary for Discrete Graph Generation? DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper by Jay Revolinsky, Harry Shomer, Jiliang Tang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-08825.txt.
Introduction
Jay Revolinsky and colleagues build discrete graphs with local message passing alone, no global attention. Their GenGNN backbone keeps edge fields alive while refining coupled node-edge states in latent space. Diffusion models built on it clear a 90 percent pass rate on standard tests, run up to five times faster than transformer rivals, and resist over-smoothing while cleaning up.
Catalog record
| CREATOR | Jay Revolinsky, Harry Shomer, Jiliang Tang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56631 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.08825
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Are Expressive Encoders Necessary for Discrete Graph Generation? DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper Jay Revolinsky, Harry Shomer, Jiliang Tang Abstract . Discrete graph generation has emerged as a powerful paradigm for modeling graph data, often relying on highly expressive neural backbones such as transformers or higher-order architectures. We revisit this design choice by introducing GenGNN, a modular message-passing framework for graph generation. Diffusion models with GenGNN achieve more than 90% validity on Tree and Planar datasets, within margins of graph transformers, at 2-5x faster inference speed. For molecule generation, DiGress with a GenGNN backbone achieves 99.49% Validity. A systematic ablation study shows the benefit provided by each GenGNN component, indicating the need for residual connections to mitigate oversmoothing on complicated graph-structure. Through scaling analyses, we apply a principled metric-space view to investigate learned diffusion representations and uncover whether GNNs can be expressive neural backbones for discrete diffusion. 1. Introduction Graph generation exists as a burgeoning subfield of graph representation learning, with applications extending from drug discovery ( 57 ) to code modeling ( 6 ) . Subsequently, models which leverage discrete graph diffusion demonstrate impressive performance for molecule generation ( 15 ; 51 ) . Recent work integrates continuous-time modeling into discrete diffusion via flow matching ( 45 ; 58 ) , where further decoupling of training and sampling results in near-perfect performance on some benchmark datasets ( 39 ) . In order for discrete diffusion models to achieve best-in-class results, the current landscape for graph generative models (GGMs) rely on specialized graph encoder backbones. This includes variants of either the transformer architecture ( 50 ; 40 ; 35 ) or maximally-expressive graph networks ( 32 ; 34 ) . The need for integrating expressive neural backbones into GGMs relies on observations from prior work and is distilled into a simple two-part intuition. One , message-passing within less-expressive graph networks fail to distinguish simple isomorphic substructures ( 55 ) . Two , graph neural networks (GNNs) suffer from over-smoothing, which translates to failure when scaling on long-range tasks ( 2 ) . This lack of expressivity implies that simple GNNs fail to accurately denoise complicated graph-structure across the many diffusion timesteps required for successful sampling, as demonstrated in Figure 1(a) with a simple GNN backbone on the Planar dataset versus a graph transformer backbone in Figure 1(b) . (a) simple GNN (b) Graph Transformer Figure 1 . Planar graphs generated via DeFoG with a simple GNN and Graph Transformer backbone. We can see that the GNN fails to properly sample planar structure, instead producing several clustered communities. However, a conflicting story is apparent within the node- and graph-classification tasks, where recent work shows simpler GNNs (with modifications) achieving comparable performance to graph transformers (GTs) ( 25 ; 27 ; 28 ) . This is noteworthy, as simple GNNs are more efficient than expressive models reliant on tupled-based representations ( 32 ; 34 ; 40 ; 35 ) , therefore translating to inference speed improvements ( 28 ) . Any kind of speed improvement is important for discrete graph diffusion, which currently struggles with scalability from the quadratic time-complexity required for graph reconstruction ( 51 ; 39 ) . This leads us to the ask the question of, are expressive encoders really necessary for discrete graph diffusion? Despite any efficiency boost promised by a simpler baseline, repeated empirical observations indicate their failure to re-create their training data within generated graphs. Therefore, a balance must be achieved between expressivity and time efficiency. To answer this, we first design GenGNN, a neural framework created to address the shortcomings of simpler GNNs as neural backbones for discrete graph diffusion. Unlike graph transformers, GenGNN relies solely on message-passing to denoise latent representations, which is further integrated into a modular framework for effective sampling of generated graphs. The message-passing restriction of GenGNN is intentional, enabling analysis to focus on the threshold at which expressiveness matters for discrete graph diffusion . Initial benchmarking indicates GenGNN achieves performance competitive with SOTA models, 99.35% validity and over 2.5x inference speed-up relative to theoretically-expressive architectures on the QM9 dataset ( 54 ) . This inference speedup is comprehensively illustrated with 1.7-5x improvements and competitive performance across common benchmarks including: Tree, Planar, SBM, ZINC, Guacamol, and MOSES ( 4 ; 33 ; 47 ; 38 ; 7 ) . Furthermore, ablation studies on the proposed GenGNN framework demonstrate the necessity of each proposed component within GenGNN. Scaling analysis across increasing number of layers for these ablated components indicates GenGNN learn latent representations ( 26 ) comparable to more-expressive architectures. We further derive theoretical relationships to how these latent representations correlate to improved downstream generation within multivariate-systems, formalizing the intuition of how decoupled frameworks allow bypassing of standard expressivity hierarchies. The contribution of our work is as follows: • We introduce GenGNN, a modular neural message-passing framework enabling less-expressive model backbones to achieve competitive graph generation performance with 1.7-5x inference speedup. • We detail a theoretical underpinning as to why GenGNN enhances standard message-passing for discrete graph diffusion. • We conduct detailed analysis ablating components of the GenGNN framework and further scaling framework layers to demonstrate the connection between downstream performance and latent representations 1 1 1 Source Code Available Here: GitHub . 2. Background 2.1. Preliminary Within this work, we represent a graph G=\{\mathbf{X},\mathbf{E}\} by node features \mathbf{X}\in\mathbb{R}^{N\times d_{x}} , edge features \mathbf{E}\in\mathbb{R}^{N\times N\times d_{e}} , and a global conditioning vector with a timestep embedding as \mathbf{y}\in\mathbb{R}^{d_{y}} . The adjacency matrix for a target graph is illustrated by {A}^{N\times N} , where a point of interest is shown by a_{ij} . We denote the hidden representations at layer \ell by \mathbf{X}^{(\ell)} , \mathbf{E}^{(\ell)} , and \mathbf{y}^{(\ell)} . A continuous flow-matching rate matrix is represented by {R}^{N\times N} . Discrete probabilities computed across an adjacency matrix are shown as {P}^{N\times N} . The transition matrix is detailed with M^{N\times N} , which is distinct from a message ( \mathcal{M}_{\theta} ) or \mathbf{m}_{i} . The diagonal matrix is shown as D^{N\times N}=diag(a_{1},a_{2},...,a_{n}) and the identity matrix I^{N\times N}=\mathbf{1} . A learnable weights matrix, W^{N\times N} . Hidden representations are represented generally as \mathbf{h} . 2.2. Discrete Graph Diffusion Discrete-state diffusion alters continuous denoising ( 46 ) by transitioning between noisy and denoised states as marginal probabilities across categorical distributions, adding noise to form G_{t}=(X_{t},E_{t}) , where t is the t -th diffusion timestep. This amounts to sampling each node and edge type from a categorical distribution, as defined by ( 51 ) : (1) \displaystyle\begin{split}q(M_{t}\mid M_{t-1})&=\bigl(X_{t-1}M_{t}^{X},\;E_{t-1}M_{t}^{E}\bigr),\\ q(M_{t}\mid M)&=\bigl(X\bar{M}_{t}^{X},\;E\bar{M}_{t}^{E}\bigr),\end{split} where \bar{M} is a transition matrix that defines the forward diffusion process. In practice, Eq. ( 1 ) enables the denoising backbone to be trained via cross-entropy loss on node and edge features for strong graph generation performance. Recent work integrated continuous flow-modeling into the