acceptodds
Under review as a conference paper at ICLR 2027

Discrete Diffusion for Large Graph Generation via Structural Candidate Restriction

Abstract

Synthesizing realistic graphs at scale is vital when the graphs of interest are large and real-world samples are limited or access-sensitive. Diffusion-based generators have recently driven much of the progress, offering high modeling capacity, but most such methods have quadratic computational complexity and are hence restricted to small-scale networks, currently up to 3k nodes. Existing non-quadratic methods remain limited by memorization issues and a trade-off between scalability and generation quality. Our goal is to generate large graphs whose structural statistics — e.g., degree distribution, clustering, and path length — faithfully reflect those of real-world sparse graphs, without resorting to memorizing the training data. We introduce a discrete graph diffusion model that restricts training to a structurally motivated subset of node pairs — observed edges and their wedge non-edges — reducing training complexity below quadratic in the number of nodes. To keep the noisy graph informative throughout both the forward and reverse trajectories, we design a three-class absorbing forward process governed by a degree-aware, floored cosine noise schedule: unlike a structure-blind schedule that adds noise to every pair identically, ours adapts to each node's degree and never fully erases the graph's structure, keeping the noisy graph informative at every step. Experiments across diverse datasets show that our model consistently ranks among the top methods for structural fidelity against existing discrete diffusion baselines in large graph generation. Our code is available at https://anonymous.4open.science/r/Graph-Diffusion-Generative-Model-E52Ehttps://anonymous.4open.science/r/Graph-Diffusion-Generative-Model-E52E.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Scalable graph generation, Large graph synthesis, Graph generative models, Discrete graph diffusion, Absorbing-state diffusion, Degree-aware noise schedule, Candidate pair sampling

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_aehKOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

This manuscript proposes a novel diffusion based method for generating high quality graphs without memorizing the training set. The proposed solution, dubbed SCR, restricts training to edges and wedge non-edges, reducing the training complexity and improving the signal-to-noise ratio. SCR's degree-aware noise schedule ties the introduced noise during the reversing process to a graph's structural attributes, increasing the structural information maintained throughout the process. Compared to prior work, SCR generates graphs with local and global structures that resemble the training set without memorization. Ablations and other extensive experiments thoroughly analyze different aspects of SRC.

Critical strengths
  1. The manuscript is generally well written and well motivated. The claims are substantiated through extensive experiments and ablations.
  2. The methods leading to the improved structural SNR (restricting training to QtQ_t and the noise schedule) are quite insightful and allow SCR to better match the underlying data distribution, specially with the large, single graph datasets.
Critical weaknesses
  1. What is the purpose of the small random coverage set included in QtQ_t? The impact of this inclusion is not discussed or mentioned, yet the small random coverage set itself is mentioned extensively in in Figure 1, several theoretical results, and the loss function.
  2. Experimental results appear to be from a single training run and without any error bars or standard deviations (Table 2 and Table 3).
  3. A major weakness of the manuscript are its figures. Most importantly, Figure 1 is overly complex, confusing, and under explained. I was able to follow the figure by closely reading the text of section 4 several times, but the process was time-consuming and several details remain unclear. As it stands Figure 1 hinders comprehension instead of aiding it. In addition, almost all figures have very small fonts despite having plenty of room for larger fonts (e.g. Figure 2). Some appendix figures do not have subfigure titles specifying their dataset.
Questions for authors

Clarifications that will affect my assessment:

  • I ask the authors to either simplify Figure 1 or include additional information in the text/figure that clarify what the figure is trying to convey. To reiterate, as it stands, Figure 1 hinders comprehension instead of aiding it.
  • Please provide additional clarifications and results to address the weaknesses outlined previously. Standard deviations or error bars should be at least provided for SCR results and all ablations.

Some minor suggestions that could be addressed to improve the readability of the work.

  • The name SCR is never mentioned in the manuscript's text, only tables.
  • The acronym of clustering coefficient (CC) is never defined (line 393).

Additionally, please include an "AI Use Statement". I believe it is required.

6 comments

We thank the reviewer for evaluating our manuscript and for the constructive feedback.

I ask the authors to either simplify Figure 1 or include additional information in the text/figure that clarify what the figure is trying to convey. To reiterate, as it stands, Figure 1 hinders comprehension instead of aiding it.

We thank the reviewer for this comment. As also noted in our response to Reviewer 2MWB, we have revised Figure 1 to improve its readability. In addition, we have added a paragraph in Section 4, where the figure is first referenced, that walks the reader through the figure step by step. Beyond Figure 1, we have enlarged Figure 2 and clarified the dataset names in Figures 9 and 10. We believe these modifications improve the readability and clarity of the presentation of our model.

Please provide additional clarifications and results to address the weaknesses outlined previously. Standard deviations or error bars should be at least provided for SCR results and all ablations.

We thank the reviewer for this feedback. In the original submission, we omitted standard deviations from some tables because of space constraints. Following the reviewer's suggestion, we have revised the tables throughout the paper to report the mean ±\pm standard deviation over 16 generated samples for the main results and for all ablations. The standard deviations are small relative to the differences between methods and do not change the conclusions drawn from the tables.

Other Modifications

We have also made the following revisions. First, the motivation for the small random coverage set StS_t is now explained in our response to Reviewer 2MWB (Q2) and in the revised method section. Second, we now introduce the name of our model, SCR, at its first mention and use it consistently throughout the manuscript. Third, the metrics and datasets are formally defined in the appendix, as in the original submission; in addition, the main text now states what each metric abbreviation stands for (e.g., CC: clustering coefficient). Fourth, our use of AI was disclosed in a footnote in the original submission; in the revised manuscript, we have moved it to a dedicated AI Use Statement. We believe that these modifications, made in response to the reviewer's constructive feedback, improve the readability and clarity of the manuscript.

AuthorsOpenReview ↗

Summary of Responses to Reviewer aehK

Dear Reviewer aehK,

Thank you again for your constructive feedback. As the discussion period ends soon, we would like to briefly follow up. In short, we have:

  • Revised Figure 1 and added a step-by-step walkthrough in Section 4.
  • Added mean ± std over 16 samples for the main results and all ablations.
  • Clarified the motivation for $ S_t $, used the name SCR consistently, defined the metric abbreviations in the main text, and added an AI Use Statement.

We would be grateful to know whether our response addresses your concerns, and if so, whether this could be reflected in your evaluation. We are happy to clarify anything further.

Best regards,

The Authors

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

This paper addresses scalable generation of large sparse graphs. It proposes structural candidate restriction, a degree-aware absorbing diffusion process, and structural regularization. Experiments on citation, financial, and other graph datasets show improved structural fidelity and low edge overlap compared with baselines. However, sampling remains quadratic.

Critical strengths
  1. The degree-aware noise schedule preserves useful structural information during diffusion, avoiding a completely uninformative noisy graph.
  2. Table 2 shows competitive results for degree-related statistics, path length, and clustering coefficients across six real-world datasets.
Critical weaknesses
  1. During generation, the model uses degree sequences sampled from training graphs (Appendix A). This raises concerns about how much structural fidelity comes from the learned model rather than the provided degree information.
  2. The paper does not fully isolate the effects of candidate restriction, common-neighbor features, and the noise schedule on final generation quality. Their individual contributions remain unclear.
Questions for authors
  1. Equations 15–18 claim an unbiased objective, while Proposition B.4 explicitly proves bias from wedge weighting. How do the authors reconcile these results?
  2. The paper uses edge overlap to argue against memorization. However, low overlap does not rule out copying higher-level structures. Can the authors provide permutation-invariant similarity or community-level evaluations?
3 comments

We thank the reviewer for considering our manuscript.

Q1. Equations 15–18 claim an unbiased objective, while Proposition B.4 explicitly proves bias from wedge weighting. How do the authors reconcile these results?

As stated in the contributions part of the introduction, our objective function is unbiased under a specific condition. We agree that this was not communicated clearly in the section 4; we have therefore revised it to state that, with the 1/λ1/\lambda weighting of the wedge term, our objective has an explicit bias, characterized exactly in Proposition B.4, and that all results are obtained with this weighted version of the objective function.

Q2. The paper uses edge overlap to argue against memorization. However, low overlap does not rule out copying higher-level structures. Can the authors provide permutation-invariant similarity or community-level evaluations?

We thank the reviewer for this suggestion. Beyond edge overlap, we have added two analyses to the revised manuscript.

Degree-source ablation (Appendix C.7). At generation time, we replace the exact per-node degree sequence of the training graph, which is the main channel through which per-node identity could enter generation, with an i.i.d. resample of the same degree distribution, without retraining. No fidelity metric changes by more than one standard error, which indicates that the model does not rely on memorized per-node information.

Community-level evaluation (Appendix C.8). Using Louvain community detection, we compare generated and training graphs at two levels. First, at the partition level, we use permutation-invariant statistics: modularity, number of communities, and the Wasserstein-1 distance between community-size distributions. Second, at the node level, we measure whether a generated graph groups the same specific nodes together as the training graph, using the adjusted Rand index (ARI) and normalized mutual information (NMI); for both, higher values indicate greater agreement and thus a higher risk of memorization. To ensure that these scores can detect real agreement, we use Louvain's agreement with itself across random seeds on the training graph as a reference (ARI of 0.60–0.96).

The node-level agreement between generated and training graphs is at chance level on all six datasets (ARI between -0.0020.002 and 0.0050.005), far below this reference, and the result is the same under both conditions of the degree-source ablation. Hence, the generated graphs do not reproduce the community assignment of the training graph. At the same time, the partition-level statistics are partially preserved, which shows that the generated graphs are not structurally featureless. Together with the low edge overlap, these results provide evidence against memorization at both the edge level and the community level.

AuthorsOpenReview ↗

Summary of Responses to Reviewer qqRs

Dear Reviewer,

Thank you again for your review. As the discussion period ends soon, we would like to briefly follow up. In short, we have:

  • Revised Section 4 to state the bias of the weighted objective explicitly (Prop. B.4) (Q1).
  • Added a degree-source ablation (App. C.7) and a community-level evaluation (App. C.8), showing no memorization beyond edge overlap (Q2).

We would be grateful to know whether our response addresses your concerns, and if so, whether this could be reflected in your evaluation. We are happy to clarify anything further in the remaining time.

Best regards,

The Authors

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

The paper proposes a diffusion based generative model for large graphs, addressing one gap in the literature where generative models are quite limited in terms of complexity (generally quadratic), hence in terms of target size for the graphs they can generate. This paper proposes to addresses the training complexity problem by restricting training to a well chosen subset of node pairs (instead of all of them), and by a new degree-aware noise schedule. The proposed framework is well described, generally properly motivated, and validated with experiments targeting the generation of large unweighted graphs with relatively convincing performance.

Critical strengths

S1. The paper addresses a timely problem and important gap in the literature towards the generation of large graphs S2. The (distant) inspiration from network science models (e.g. ERGM) is interesting and novel in this type of works S3. The objective of reducing training complexity is clearly achieved. S4. The presentation is generally clear and results relatively convincing (wrt to the chosen performance metrics)

Critical weaknesses

W1. The text and definitions should be clarified, and more formal at places. For example, i) the proposed framework applies to unweighted graphs, not any graphs; ii) 'structurally meaningful subset of node pairs' should come with a clear definition of the target structural properties; iii) structural properties of the class of generated samples should be clear also, ideally in the problem statement; iv) choice of performance metrics should be well explained (incl. their properties and limitations) - this is not a criticism of the choice of metrics, as good metrics are still lacking in that space, but rather a need to be clearer in the text about actual properties of the proposed framework; v) complexity is essentially reduced in training, not in the sampling phase (this is mentioned at the end of the paper, but the first part is less clear on that respect); vi) the proposal targets the generation of sparse graphs, and not any graphs - sparse graphs are the most interesting graphs of course, but the language can be made more precise in the description of the framework. W2. The generalisation properties of the proposed framework is not studied in details. In particular, the choice of the subset of node pairs used for training, must influence the properties of the class of generated samples. This is not much discussed, unfortunately. W3. Experimental settings are not optimal: most of the dataset (listed in Table 1) seem to contains only one (large) graph (?). How is that compatible with the proposed generative framework? how do the authors go around that potential mismatch? W4. The loss function (15) seems overly complex - while its elements are generally properly motivated, would there by any more straightforward loss, maybe with a more consistent prior term adapted to the actual target properties of the generated graphs (which is actually not fully described, formally, in the problem statement)

Questions for authors

Q1. The literature on generative models based on diffusion, is quite complete. Any reason with the flow matching literature seems to be omitted? Q2. The choice of separating W(G) and S_t in the training process could be more clearly motivated: why these different sets of edges should be treated differently? Q3. Is the choice of edges Q(G) fixed over training? and across samples of the training set? Q4. Is there any global structural properties that are guaranteed in the generated large graphs? or mostly local (structural) properties? Q5. How are training, and eventually evaluation performed on the multiple datasets that seem to contain only one graph? Q6. Why the class-mass SNR is relevant? how does it connect to the overall generative objective? Q7. Performance evaluation does not include basic models like ERGM - would it be relevant to show the advantage of more complex models like the one proposed here, wrt to network science ones?

Minor comments:

Q8 . Figure 1 is too small and barely readable

13 comments

We sincerely thank the reviewer for the time and effort devoted to evaluating our manuscript, and for the constructive feedback. We address each comment below and have revised the manuscript accordingly.

Q1. The literature on diffusion-based generative models is quite complete. Is there any reason why the flow matching literature seems to be omitted?

We thank the reviewer for this question. As indicated by the title, our method belongs to the diffusion-based generative paradigm and targets large sparse graphs. Accordingly, our literature review focuses on diffusion-based graph generative models and scalable graph generation. To the best of our knowledge, no existing flow matching model for graph generation has been shown to scale beyond 1,000 nodes per graph, whereas our largest dataset contains graphs with more than 19,000 nodes. For this reason, and given the page limit of the ICLR template, we did not include flow matching models in the related work. We consider extending flow matching models to large-scale graph generation a promising direction for our future work.

Q2. The choice of separating W(G)W(G) and StS_t in the training process could be more clearly motivated: why should these different sets of edges be treated differently?

We thank the reviewer for this question. The two sets play complementary roles.

Role of W(G). W(G) is determined by the structure of each training graph and is fixed during training. It is the local structure on which our denoiser can rely: restricting the noising and denoising processes to E∪W(G)E \cup W(G) allows the model to learn the statistics of the observed edges and of the wedge pairs, i.e., the non-edges that are structurally closest to becoming edges.

Role of S_t. The set Eˉ∖W(G)\bar{E} \setminus W(G) of remaining non-edges contains Θ(N2)\Theta(N^2) pairs, but a loss computed only over E∪W(G)E \cup W(G) never sees them. Rescaling the wedge term does not resolve this either: the rescaled loss would represent all non-edges only if the average wedge loss happened to equal the average loss over all non-edges. StS_t is a uniformly sampled subset of Eˉ∖W(G)\bar{E} \setminus W(G), and reweighting its term by 1/λS1/\lambda_S makes the coverage term an unbiased estimator, with respect to the sampling of StS_t, of the loss over Eˉ∖W(G)\bar{E} \setminus W(G). Consequently, without additional weighting of the wedge term, the full objective is an unbiased estimator of the loss over all (N2)\binom{N}{2} node pairs (Proposition B.3).

Weighting of the wedge term. When the wedge term is additionally weighted by 1/λ1/\lambda, Proposition B.4 shows that the expected objective equals the full-graph loss plus a bias term. Since this bias term is nonnegative and its coefficient is fixed by the graph structure, the weighted objective corresponds to the full-graph loss with an explicit, exactly quantified additional emphasis on wedge pairs, rather than an uncontrolled approximation.

In summary, W(G)W(G) concentrates training on the structurally informative pairs, while StS_t ensures that every node pair contributes to the objective. This is why we treat the two sets separately. To address this concern, we have also revised the model overview in Section 4.

Q3. Is the choice of edges Q(G)Q(G) fixed over training? And across samples of the training set?

We thank the reviewer for this question. Q(G)=E∪W(G)Q(G) = E \cup W(G) is a deterministic function of each training graph dataset. Hence, it is fixed throughout training for a given graph, but it differs across graphs in the training set, since each graph has its own edge set EE and wedge set W(G)W(G). During training, the set of node pairs that can be noised in the forward process is Qt(G)=Q(G)∪StQ_t(G) = Q(G) \cup S_t, while the noise schedule governs the dynamics of the forward process on this set.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Rebuttal and Revisions

Dear Area Chair,

Our paper scales discrete diffusion models to large, sparse graphs by restricting the diffusion process to observed edges and wedge pairs (non-edges with at least one common neighbor), complemented by a small random coverage set. We briefly summarize the main concerns raised during the review and how we addressed them:

  • Classical baselines: Added four non-learned network models, ER, Chung–Lu, SBM, and ERGM, fitted directly to the observed graph. SCR outperforms all four in 8 of 12 comparisons, while EDGE, the strongest learning-based baseline for large graphs, does so in none.
  • Memorization and role of degree information: Added a community-level evaluation (App. C.8) and a degree-source ablation (App. C.7).
  • Objective design: Clarified the bias of the objective (Prop. B.3, B.4) and added an ablation showing that the coverage set StS_t and the SNR reweighting each contribute (App. C.9), complementing the ablations of the prior distribution and the regularizers in the original submission.
  • Clarity and presentation: Stated the scope (sparse, unweighted, undirected graphs) and definitions precisely, added error bars to all results, revised Figure 1, and added the evaluation protocol (App. D.1).

We believe that, with these revisions informed by the reviewers' constructive feedback, the paper makes a clear contribution to diffusion-based generative models for large, sparse graphs. We thank you and the reviewers for the constructive discussion.

Best regards,

The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.