acceptodds
Under review as a conference paper at ICLR 2027

Sparse GNNs Make Strong Backbones for Discrete Graph Generation

Abstract

Leading discrete graph generators use Graph Transformers or dense message-passing networks as their denoising backbone, processing all node pairs at every layer despite typically sparse output graphs. We present SGen (Sparse-backbone Graph Generation), which restricts intermediate message passing to the current non-null edges and predicts the full adjacency matrix only at the output through a bilinear head. We interpret SGen through conditional link prediction: a Bayes analysis decomposes edge denoising into structural prediction and current-edge information, and further bounds the error when SGen approximates this target. Integrated into DiGress and SimGFM, SGen achieves competitive generation quality on molecular and structural benchmarks, with metric-dependent trade-offs. On Tree and Planar, it delivers approximately – training speedups and – lower peak training memory than the corresponding Graph Transformer backbones. Architecture-matched ablations show that sparse communication itself reduces runtime and memory, with the operator and model size held fixed. Reusing shared representations across terminal output blocks further enables SGen to extend an existing graph generation method to Proteins and Point Clouds with up to 5,037 nodes, without any algorithm specifically designed for large graphs.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Generation, Discrete Diffusion

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_tTf3OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes SGen, a sparse GNN backbone for discrete graph generation. SGen replaces dense intermediate message passing with sparse communication and a bilinear edge decoder. While it achieves some computational savings, it lacks novelty and generation-quality improvements remain questionable.

Critical strengths
  1. The method substantially reduces training time and GPU memory consumption compared to dense Graph Transformer backbones.
  2. Experiments cover molecular, structural, and large-scale graph generation.
  3. The paper provides some theoretical interpretations of the proposed method.
Critical weaknesses
  1. The approach largely combines existing sparse GNN architectures, global pooling, and bilinear link prediction, without introducing substantial technical novelty.
  2. Although SGen improves efficiency to some extent, this comes at the cost of reduced generation quality. More fundamentally, sparse architectures may have limited expressiveness compared with dense backbones.
  3. The theoretical analysis is not very convincing. The Bayesian decomposition mainly follows standard probabilistic identities and does not tightly match the actual algorithm.
  4. Despite the scalability claims, the method still retains quadratic output complexity, so it does not fundamentally resolve the efficiency issue.
Questions for authors

Please see the Weaknesses.

1 comment

We greatly appreciate your careful assessment and detailed feedback. We hope our response below addresses your concerns about novelty, generation quality, theoretical analysis, and scalability.

(W1) Contribution beyond Existing Sparse GNNs and Bilinear Link Prediction

"The approach largely combines existing sparse GNN architectures, global pooling, and bilinear link prediction, without introducing substantial technical novelty."

Our central contribution is to demonstrate that competitive discrete graph generation does not require all-pair communication at every backbone layer. Across DiGress and SimGFM and the evaluated benchmarks, SGen restricts message passing to the non-null edges of the current noisy graph while retaining predictions for every possible node pair. This design achieves competitive generation quality without changing the original training objectives or sampling rules.

Our controlled experiments support this finding. Dense GNN+ and SGen share the same GNN operator, hidden dimensions, conditioning, and bilinear output head, differing only in communication support. The quality comparisons in Table 6 show that sparse communication retains competitive performance, while Table 16 demonstrates 86%–92% lower peak training memory and approximately 2.5–2.6× faster training on the evaluated structural benchmarks. The broader molecular and structural results further validate this design across both generative frameworks.

(W2) Generation-Quality Trade-offs and the Expressiveness of Sparse Backbones

"this comes at the cost of reduced generation quality."

"sparse architectures may have limited expressiveness compared with dense backbones."

Our experiments do not indicate a systematic generation-quality penalty from sparse communication. In particular, integrating SGen into DiGress yields substantial improvements across molecular, structural, and large-graph benchmarks. On GuacaMol, replacing the DiGress graph transformer with SGen raises validity from 85.2% to 95.3% and the FCD score from 68.0 to 77.6 (Table 3). On Planar, V.U.N. rises from 77.5% to 86.0% and Ratio improves from 5.1 to 3.7 (Table 2). On Proteins, Ratio falls from 16.2 to 3.1 (Table 8, lower is better).

The sparse backbone also lets DiGress generate larger graphs. On Point Clouds, DiGress + SGen samples graphs with up to 5,037 nodes while predicting edge types for every node pair at each step. The published benchmark reports that dense DiGress ran out of memory on this dataset (Table 8). Figure 2 in Appendix G.8 shows examples generated by DiGress + SGen on both Proteins and Point Clouds.

(W3) Role of the Bayesian Decomposition and Its Connection to the Algorithm

"The Bayesian decomposition mainly follows standard probabilistic identities and does not tightly match the actual algorithm."

Thank you for highlighting the need to clarify the role of the theoretical analysis. The original Bayesian decomposition was intended to explain the relationship between clean-edge predictions and the denoising posterior under a known corruption process. However, this relationship is general and does not depend on the specific architecture of SGen. The KL term was used only in the analysis and is not computed during training or sampling.

To better focus on our architectural contribution, we have removed Theorem 3.1 and revised Section 3.4 and Algorithm 1 to clarify how SGen integrates with DiGress and SimGFM. During training, SGen predicts clean node and edge categories using the original framework's training objective. During sampling, the predicted probabilities are used in the original sampling updates, after which SGen constructs the sparse communication graph for the next step.

The effectiveness of this architectural design is further supported by our controlled comparisons of generation quality (Table 6) and computational efficiency (Table 16).

(W4) Remaining Quadratic Output Complexity and the Scope of the Scalability Claim

"the method still retains quadratic output complexity, so it does not fundamentally resolve the efficiency issue."

At each generation step, DiGress and SimGFM predict whether an edge exists between each pair of nodes and, if so, what type of edge it is. An undirected graph with NN nodes has N(N−1)/2N(N-1)/2 distinct node pairs, so making an explicit prediction for every pair requires O(N2)O(N^2) work per step.

SGen reduces the cost of producing these predictions. Its intermediate layers pass messages only along the edges of the current noisy graph, and the output layer uses the resulting node embeddings to score all pairs once. Removing this repeated all-pair computation from the backbone makes it practical to apply these generators to much larger graphs, as our experiments with DiGress illustrate.

Reviewer_xuUxOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes SGen. In discrete graph generation, it decouples sparse communication from full node-pair prediction. It achieves performance comparable to discrete diffusion and discrete flow matching. The methods can save much compute and memory resources.

Critical strengths

The paper addresses a concrete inefficiency: predicting every node pair need not require dense communication at every layer. The table 16 shows significant improvements in efficiency.

Critical weaknesses

a. In table 1 QM9H, replacing the SimGFM GT improves Validity from 98.4% to 99.6%, but worsens FCD from 0.04 to 0.89. In table 2 SBM, DiGress’s V.U.N. increases from 60.0% to 80.5%, while Ratio worsens from 1.7 to 3.1. The reason seems not well explained and justified.

b. In table 5, dense GNN+ has better QM9 FCD than SGen (0.41 versus 0.53). The paper seems not establish whether SGen's saved resources can be used to close this gap.

Questions for authors

a. For the large-graph experiments, could you report runtime and peak memory versus graph size and output block size?

1 comment

We greatly appreciate your detailed review and constructive suggestions. We hope our response below addresses your concerns about quality trade-offs, resource allocation, and scalability.

(W1 / Weakness a) Metric-Dependent Trade-offs in Generation Quality

"improves Validity from 98.4% to 99.6%, but worsens FCD from 0.04 to 0.89."

"V.U.N. increases from 60.0% to 80.5%, while Ratio worsens from 1.7 to 3.1."

On QM9H, validity measures the fraction of generated molecules that pass RDKit sanitization, while FCD measures agreement with the reference distribution in ChemNet feature space. A higher fraction of valid molecules therefore does not necessarily imply a closer match to the reference distribution.

To examine how these metrics change during training, we evaluated several checkpoints from one archived SimGFM + SGen run using the same sampling protocol. The GT entry below is the result reported in Table 1; the SGen entries describe the training trajectory of this archived run.

SimGFM backboneEpochValidity ↑FCD ↓
GT (Table 1)—98.4%0.04
SGen5099.6%0.89
SGen30098.7%0.23
SGen65098.2%0.10

Within this run, FCD decreases from 0.89 at epoch 50 to 0.10 at epoch 650, while validity remains above 98%. This shows that distributional fidelity can continue to improve after validity is already high.

SBM. Replacing the DiGress backbone with SGen improves V.U.N. by 20.5 percentage points. Although Ratio worsens, the ranking drops by just one place, from second to third among the 15 model configurations with a reported SBM Ratio in Table 2. Prior work shows that the MMD estimates used to compute Ratio are sensitive to kernel choice [1] and can vary substantially across small samples of SBM graphs [2].

Reference [1] Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions. ICLR, 2022.

[2] PolyGraph Discrepancy: A Classifier-Based Metric for Graph Generation. ICLR, 2026.

(W2 / Weakness b) Using the Saved Resources to Improve the Quality–Efficiency Trade-off

"dense GNN+ has better QM9 FCD than SGen (0.41 versus 0.53)."

"whether SGen's saved resources can be used to close this gap."

Thank you for this suggestion. On QM9 under SimGFM, we matched SGen’s training budget to that of dense GNN+. SGen’s FCD improved from 0.53 ± 0.01 to 0.32 ± 0.00, bringing its mean FCD below the 0.41 ± 0.03 achieved by dense GNN+. SGen achieved 99.3% ± 0.1% validity under the matched budget.

(Q1 / Question a) Runtime and Peak Memory versus Graph Size and Output Block Size

"For the large-graph experiments, could you report runtime and peak memory versus graph size and output block size?"

We profiled DiGress + SGen on one RTX 3090 at five graph sizes per dataset. At each size, we tested full output, 128-row blocks, and 32-row blocks. The table below reports selected measurements, rounded for readability. Training time is the mean over ten steps on the same graph. Each sampling time covers one 1,000-step run, and both memory columns report peak GPU memory allocated by PyTorch.

DatasetNodesOutput rows at a timeTraining (s/step)Training peak (GiB)Sampling (s/graph)Sampling peak (GiB)
Proteins100Full0.090.8250.13
Proteins500Full0.121.6260.21
Point Clouds5311280.101.3280.17
Point Clouds5,037Full0.7813.33114.5
Point Clouds5,0371280.8612.93304.5
Point Clouds5,037321.1112.94314.5

With the block size fixed at 128 rows, sampling the 531-node Point Clouds graph took 28 s and peaked at 0.17 GiB. Sampling the 5,037-node graph took 330 s and peaked at 4.5 GiB. At 5,037 nodes, smaller blocks increased sampling time while peak sampling memory stayed near 4.5 GiB. During training, 128-row blocks lowered the peak from 13.3 to 12.9 GiB on this graph. We use 128-row blocks during large-graph training and compute the full output at once during sampling. For each training graph, the graph generation algorithm first samples the number of nodes and then the number of edges, so peak GPU memory usage can vary across training steps. Processing the output in blocks limits these memory spikes and helps prevent out-of-memory errors from interrupting training.

Reviewer_AqSwOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes to change the full attention layers in graph generative models to a GNN layer, which enables much higher efficiency. The model reads out with a full attention layer for predicting all node pair interactions. The authors attempt to provide theoretical insights to motivate this proposal. The results of the paper are promising. Certain important baselines are missing however.

Critical strengths

S1. The framework is simple and possible to plug in for existing generative models. The authors validate the effectiveness for discrete diffusion model such as Digress and flow models such as SimGFM. S2. The framework shows strong performance, despite its simplicity. It shows similar or better performance on molecular datasets, different synthetic datasets, and more specifically on large graphs, namely point-cloud, which is commonly known as a challenge.

Critical weaknesses

W1. The largest concern is how the provided theoretical analysis is related to the proposed framework itself. Namely, it is not clear how Theorem 3.1 in Section 3.5 is actually related to the sparse GNN architecture proposed in this paper, since seemingly any graph neural network that can predict edge distributions would fit in this criteria. Moreover, the KL divergence term does not seem to be directly related to either the training or the sampling process. W2. This comment is more related to the presentation. The writing of the paper can be significantly improved. This is not in contradiction with its outstanding experimental performance, but the overall quality of the draft is degraded by difficult-to-read or overly complicated sentences (for example, as can be clearly seen from the opening of the introduction). Some theoretical analysis also seems to be presented in an unnecessarily complicated way, without clearly explaining its relevance to the proposed method. The authors should clearly illustrate the overhead of existing architectures and how the proposed simplifications address it. Theorem 3.2 seems more like a standard complexity analysis than rather than a theoretical contribution. More visualization of generated graphs is also encouraged. W3. Experiments: Table 7 presents one of the most important results, yet the HSpectre baseline is missing, despite being included for the synthetic datasets. Specifically, point-cloud HSpectre has previously achieved some of the best performance on these benchmarks. Important molecular generation benchmarks including GuacaMol and MOSES, are also missing. Moreover, QM9 is already quite saturated and therefore does not provide much additional information.

Questions for authors

Q1. How to explain more clearly the relation between the theoretical analysis to the proposed GNN network? Q2. Can the authors provide the required results and baselines in W3? Q3. When is this local information propagation sufficient, and when will there be any failure cases? Q4. Can the authors separate the contribution (in terms of memory and training/sampling speed) from GNN design, the output head design, and the sampling in blocks? Specifically, how does the new sampling algorithm change the sampling speed?

2 comments
AuthorsOpenReview ↗

Response to Reviewer AqSw (Part 1)

We greatly appreciate your thoughtful and constructive feedback. We hope our response below clarifies the theoretical interpretation, baseline comparisons, and sources of efficiency gains.

(W1 & Q1) Connection between the Theoretical Analysis and the Sparse GNN Architecture

"it is not clear how Theorem 3.1 in Section 3.5 is actually related to the sparse GNN architecture proposed in this paper"

"the KL divergence term does not seem to be directly related to either the training or the sampling process."

Thank you for asking us to clarify the connection between Theorem 3.1 and SGen. We included the theorem to explain how, under a known corruption process, observing a noisy edge changes the predicted distribution of its clean edge type. This relationship applies to any model that predicts edge distributions, including SGen and a dense graph transformer. The KL term appeared only in the analysis. In the implementation, SGen learns clean-edge logits using the original generator’s loss, and the sampler uses the resulting probabilities to update the graph.

The architectural question is how much communication is needed to make these predictions. SGen passes messages along the non-null edges of the noisy graph, then uses a bilinear head to score every node pair, including pairs with no current edge. We test this choice by holding the GNN layers and output head fixed and varying only which pairs exchange messages. Tables 6 and 16 of the revised manuscript report the effects on generation quality and computational cost, respectively. To bring this contribution into focus, we removed Theorem 3.1 and revised Section 3.4 and Algorithm 1 to show how SGen supplies predictions to DiGress and SimGFM during training and sampling.

(W2a) Presentation and Complexity Analysis

"The authors should clearly illustrate the overhead of existing architectures and how the proposed simplifications address it."

"Theorem 3.2 seems more like a standard complexity analysis than rather than a theoretical contribution."

We have revised the introduction to clarify the main source of computational overhead in existing graph generators. Dense backbones repeatedly compute and maintain hidden representations for all node pairs at every layer, even when most pairs have no edge. SGen avoids this repeated computation by restricting intermediate message passing to non-null edges, while retaining full node-pair prediction through a single bilinear output head.

We replaced Theorem 3.2 with a direct complexity analysis in Section 3.5.

(W2b) Generated-Graph Visualizations

"More visualization of generated graphs is also encouraged."

Thank you for this suggestion. We have added six graphs generated by DiGress + SGen in Figure 2 of Appendix G.8. These include three Proteins graphs with 269, 468, and 498 nodes and three Point Clouds graphs with 545, 986, and 990 nodes. These visualizations illustrate the generated graph structures at different sizes and complement our quantitative evaluation on large-graph benchmarks.

(W3a & Q2a) HSpectre Baseline on Large-Graph and Point-Cloud Benchmarks

"Table 7 presents one of the most important results, yet the HSpectre baseline is missing"

"point-cloud HSpectre has previously achieved some of the best performance on these benchmarks."

Table 7 of our original submission listed HSpectre as ESGG, following Table 2 of AutoGraph. In Table 8 of the revised manuscript, we label the row HSpectre (ESGG) so it is easier to find.

On Proteins, DiGress + SGen achieves a lower Ratio than HSpectre (3.1 ± 0.5 versus 4.7). On Point Clouds, HSpectre achieves a lower Ratio (6.8 versus 22.8 ± 2.8). We report both comparisons to provide a complete evaluation against this baseline.

(W3b & Q2b) GuacaMol, MOSES, and Evaluation beyond Saturated QM9

"Important molecular generation benchmarks including GuacaMol and MOSES, are also missing."

"QM9 is already quite saturated and therefore does not provide much additional information."

GuacaMol and MOSES were already included in our original submission, with experiments conducted under both DiGress and SimGFM. These benchmarks extend our evaluation beyond QM9 to larger and more diverse molecular datasets.

As reported in Table 3 of the revised manuscript, replacing the original Graph Transformer with SGen improves the GuacaMol FCD similarity score and reduces the MOSES FCD distance in both frameworks. For example, under SimGFM, the GuacaMol FCD score increases from 80.8 to 84.4, while the MOSES FCD distance decreases from 1.08 to 0.96.

To further strengthen these evaluations, Tables 13 and 14 provide uncertainty estimates and comparisons with additional molecular generation baselines. HSpectre results on these two benchmarks were not reported by Bergmeister et al.

AuthorsOpenReview ↗

Response to Reviewer AqSw (Part 2)

(Q3) When Sparse Local Propagation Is Sufficient and When It Fails

"When is this local information propagation sufficient, and when will there be any failure cases?"

Sparse local propagation is effective when edge predictions can be made from locally aggregated node representations together with graph-level context. SGen combines these two sources of information through sparse message passing and global pooling, allowing its bilinear head to predict edges between any node pair, including disconnected nodes.

The main limitation arises when accurate predictions require pair-specific long-range interactions that cannot be adequately represented by the node embeddings and pooled global context. The controlled comparison in Table 6 of the revised manuscript isolates the effect of restricting message passing. Table 5 shows that freezing the pooled global state increases QM9 FCD in both DiGress and SimGFM. These results support the effectiveness of sparse propagation on the evaluated benchmarks, while clarifying the conditions under which additional pairwise communication may be beneficial.

(Q4a) Separating Backbone, Output-Head, and Blockwise Efficiency Contributions

"Can the authors separate the contribution (in terms of memory and training/sampling speed) from GNN design, the output head design, and the sampling in blocks?"

Thank you for requesting an explicit attribution of the efficiency gains. Table 16 compares the original graph transformer (GT), a GNN that passes messages between all node pairs (dense GNN+), and SGen. On Tree, sampling 40 graphs takes 207.02 s with GT and 96.83 s with dense GNN+, while peak training memory is similar (18.1 and 18.4 GB).

The comparison between dense GNN+ and SGen isolates the contribution of sparse communication. Both use the same GNN layers, hidden widths, conditioning, and bilinear head. The only difference is which pairs exchange messages: dense GNN+ uses all node pairs, while SGen uses the non-null edges of the current noisy graph.

Dataset (dense GNN+ → SGen)Training time (s/epoch)Training peak (GB)Sampling time (s/40 graphs)Sampling peak (GB)
Tree0.86 → 0.3318.4 → 1.596.83 → 36.731.3 → 0.2
Planar0.86 → 0.3419.2 → 2.693.90 → 64.251.3 → 0.3

The bilinear head lets both GNNs score every possible edge from the final node embeddings, including pairs with no current edge. The GT-to-dense-GNN+ comparison measures the combined effect of changing the message-passing layers and the readout. Comparing dense GNN+ with SGen isolates the effect of sparse communication. In Q4b below, we compare full and blockwise evaluation of the same SGen output head.

(Q4b) Effect of Blockwise Output Processing on Sampling Speed and Semantics

"Specifically, how does the new sampling algorithm change the sampling speed?"

On a 5,037-node Point Clouds graph, 1,000 DiGress sampling steps on one RTX 3090 took approximately 311 s with full output, 330 s with 128-row blocks, and 431 s with 32-row blocks. Peak GPU memory allocated by PyTorch was approximately 4.5 GiB in all three runs. We therefore use full output for large-graph sampling. All blocks are evaluated from the same noisy graph before the sampler advances to the next step. Under the conditions in Appendix E.1, this preserves the original transition distribution in exact arithmetic.

During training, we use 128-row blocks to limit memory spikes when a sampled graph is unusually large or has many non-null edges. For a graph with NN nodes, processing bb rows at a time keeps O(bN)O(bN) output scores in memory. The dense graph state still requires O(N2)O(N^2) storage.

On Proteins, switching from full output to 128-row blocks reduced peak training memory from 16.45 to 16.05 GiB and increased mean epoch time from 9.08 to 10.22 s. On Point Clouds, peak memory fell from 14.91 to 13.76 GiB and mean epoch time fell from 9.69 to 5.50 s. Epoch times are averages over 20 epochs after warm-up.

We use 128-row blocks during large-graph training and compute the full output at once during sampling. For each training graph, the graph generation algorithm first samples the number of nodes and then the number of edges, so peak GPU memory usage can vary across training steps. Processing the output in blocks limits these memory spikes and helps prevent out-of-memory errors from interrupting training.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.