- 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
- The method substantially reduces training time and GPU memory consumption compared to dense Graph Transformer backbones.
- Experiments cover molecular, structural, and large-scale graph generation.
- The paper provides some theoretical interpretations of the proposed method.
Critical weaknesses
- The approach largely combines existing sparse GNN architectures, global pooling, and bilinear link prediction, without introducing substantial technical novelty.
- 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.
- The theoretical analysis is not very convincing. The Bayesian decomposition mainly follows standard probabilistic identities and does not tightly match the actual algorithm.
- 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.
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
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
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
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
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 N nodes has N(N−1)/2 distinct node pairs, so making an explicit prediction for every pair requires O(N2) 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.