- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper focuses on the problem of discrete graph generation. In this work, the authors argue that the existing reconstruction loss for such models has a flaw. That is, while it promotes proper graph reconstruction for a specific sample, it doesn't necessarily learn the data distribution/manifold well. To enforce this, the authors propose a simple regularization loss that first maps each original and reconstructed graph to a latent space. The distribution is then approximated via a KDE, where the regularization loss then encourages alignment between the original and reconstructed graph spaces. They test their method on multiple datasets, showing encouraging results.
Critical strengths
- The paper is well written with a good and clear motivation.
- The proposed method is very simple and lightweight which is highly useful in practice.
Critical weaknesses
-
I find the design of the experimental results to be a little strange. The SSA loss is model-agnostic. As such, it makes sense to explicitly see if it can improve the results of various backbone models. The authors briefly test this in Table 1 showing small improvements. However, in the rest of the results, they seem to solely adopt the GRuM backbone (please correct me if I'm wrong). I find this odd because the current results seem to mainly show that it can improve results for GRuM, which while nice, does seem to lessen the impact. Because right now, my main focus is on Table 1 which seems to indicate a very minor boost in performance when including SSA across models.
-
The authors argue that for existing approaches may not properly learn the data distribution via just a reconstruction loss (lines 54-57). However, the authors seem to base their argument on a regression loss (Section 3.1). However, many prominent methods used a cross-entropy loss (e.g., DiGress, DeFoG [1], Cometh [2], and Disco [3]). As such, it's unclear if this criticism still holds. Could this be why the performance improvement in Table 1 when applied to DiGress is small?
-
Furthermore, the authors main argument hinges on the fact that MSE loss "does not explicitly constrain whether the collection of predicted samples follows the underlying data manifold" (lines 174-175). However, how true is this in practice? My point being, the authors don't show any empirical evidence that this indeed does happen. They just argue that it could happen. I'd recommend they show evidence that their observations are borne out in reality.
-
The authors don't report the variances for any of the runs. In fact, it seems that they only fit on one seed for each run. The authors seem to justify this in the appendix with results on different seeds for QM9 and Zinc, however, they both exhibit fairly low variances compared to other datasets (see [1]). As such, I do highly recommend including them because for some datasets like Planar and SBM, it's very unclear to me how statistically significant the results are (the same goes for Table 4). At a glance, it does seem that some may not be.
-
Some baseline methods are missing including [2, 3] to name a few. I'd recommend including them for a fair and accurate comparison.
-
The results in Table 4 are missing many strong baselines, e.g., [1, 2, 3], making it hard to compare performance.
[1] "DeFoG: Discrete flow matching for graph generation". ICML 2025.
[2] "Cometh: A continuous-time discrete-state graph diffusion model". TMLR 2025.
[3] Discrete-state Continuous-time Diffusion for Graph Generation". NeurIPS 2024.
Questions for authors
- This is a big ask, but detailing results of Model+SSA across all datasets for multiple methods. E.g., DiGress, GruM, DeFoG. Because to me, this is the real test of SSA, because you want it to be something which people will apply to whatever graph generation model they are using. [Weakness 1]
- Does the loss critique extend to CE loss? [Weakness 2]
- Empirical evidence for distribution misalignment? [Weakness 3]
- Variance on multiple datasets? [Weakness 4]