- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2(+1)
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper introduces a novel transformer-based graph-level variational autoencoder that encodes an entire graph into a single latent representation instead of a node-level latent representation, as in existing methods. The encoder creates a global latent representation, which is thus invariant to input graph ordering. The central paper claim is that when training data is provided with consistent node ordering, the authors can compare predictions directly to targets in that ordering without sorting to solve graph matching problems. By doing so, the authors can avoid cubic complexity in the matching step. The authors mainly tested their method on molecular graph editing, property optimization, and molecular graph generation tasks.
Critical strengths
The authors raised an interesting question on latent graph generative modeling. Indeed, there is a bottleneck when we model graphs with a global latent representation, which requires solving a graph matching problem when computing reconstruction losses. In addition, the authors showed some promising results on different molecular tasks from their learned latent graph representations.
Critical weaknesses
-
One of the main weaknesses of the paper is the lack of related work. The prior work, GLAD [1], explicitly discussed different approaches to modeling graphs in latent space, from latent nodes to latent graphs, and both discrete and continuous representations. Especially, the authors in GLAD showed that their global latent representation did not work well in latent-node cases in the context of graph generation. In addition, they also discussed graph matching problems of global graph latent representations. Thus, I would suggest the authors put analysis compared to GLAD, since I feel this is the most related work to this paper.
-
Related to the GLAD paper, it's not very clear how the proposed method can avoid the latent node collapsing problem in GLAD. In Section 3, when decoding from graph-level to node-level representation, the authors simply duplicate the graph-level latent representation, which contributes to the latent node collapsing problem, where different local neighborhood node encodings share a similar latent representation. This causes difficulty when reconstructing original graphs.
-
The authors claim that their model is scalable. I think they make such a claim because they can avoid solving the cubic graph matching problem. However, latent-node representations can also avoid this problem by keeping node ordering information from encoder input to decoder output. Thus, I would suggest that the authors revise this claim. Especially, the claim remains very generic, given that their graph transformer has quadratic complexity in the number of nodes compared to less expensive standard message-passing graph neural networks.
-
Another claim on relaxed permutation invariance remains ambiguous. I still can not fully understand how the authors reconstruct original graphs while the node ordering information is collapsed/destroyed by their global latent node representation without sorting graph matching problems. There is no such clear analysis of relaxed permutation invariance in their main methodology section (Section 3). In addition, latent graph modeling has been a well-studied subject for a long time; the main contribution here remains quite trivial.
-
The authors emphasized the necessity of predicting graph size, but there is no ablation study to show that if the prediction helps or we simply samples from empirical graph size distributions.
-
On the graph generation task, even though the authors acknowledge that this is not the main focus of their study. However, I would think this is an utmost important task; through this, we can assert how well the model can capture data distributions. There are many state-of-the-art baselines on this task [1,3,4]; I would recommend that the authors compare with them to make their model look stronger and more promising.
Questions for authors
-
How does the model compare to GraphVAE [2], which also uses a global latent graph representation?
-
How does the model overcome the latent-node collapsing problem in GLAD, where all latent nodes share the same representation? Because broadcasting from the latent graph representation to all latent node ones create the same latent representation for all nodes, while it should not be.
-
How does the model handle different node input orderings? Since, for the current model, each node ordering causes a different loss objective, which imposes instability in training and model generalization.
-
What does it mean the stable node ordering is available (in the Conclusion)?
-
How do the authors sample the number of nodes for the generation task? Is the number of nodes predicted by the model as shown in Section 3? In this case, how would the model performance compare to the scenario when we simply sample the number of nodes from empirical distributions?
References:
[1] GLAD: Improving Latent Graph Generative Modeling with Simple Quantization, AAAI 2025. Nguyen et al.
[2] GraphVAE: Towards generation of small graphs using variational autoencoders, arXiv:1802.03480v1. Simonovsky et al.
[3] DiGress: Discrete Denoising diffusion for graph generation, ICLR 2023. Vignac et al.
[4] Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations, ICML 2022. Jo et al.
9 comments
Rebuttal: Reviewer m1si - II
W2 / Q2
Related to the GLAD paper, it's not very clear how the proposed method can avoid the latent node collapsing problem in GLAD. In Section 3, when decoding from graph-level to node-level representation, the authors simply duplicate the graph-level latent representation, which contributes to the latent node collapsing problem, where different local neighborhood node encodings share a similar latent representation. This causes difficulty when reconstructing original graphs.
How does the model overcome the latent-node collapsing problem in GLAD, where all latent nodes share the same representation? Because broadcasting from the latent graph representation to all latent node ones create the same latent representation for all nodes, while it should not be.
We thank the reviewer for this question. We agree that broadcasting a single vector to nodes would yield identical node inputs if nothing else were added. We explain below why that collapse would not be a failure mode for our model, and why the broadcast does not lead to such a collapse.
Where collapse arises. Latent-node collapse is a failure mode of node-level latents: each node latent must encode its own local neighborhood, and several latents can converge to similar vectors, preventing reconstruction of diverse local structures, because the node-level latents are then propagated through permutation-equivariant layers (so identical rows in the input lead to identical rows in the output). In our model, the latent is a single graph-level vector encoding the whole molecule. High-level node-level representations appear only at two intermediate points (Fig. 1):
-
Encoder side: (between blocks (A) and (B) in Figure 1). Rows of (one per node) could in principle become similar, for example through oversmoothing in the graph updates of block (A). However, is not a latent, and it is never propagated through a permutation-equivariant layer directly. Its only role is to be pooled by the permutation-invariant readout into the global graph representation , and the encoder is trained end-to-end with the reconstruction loss (meaning that, unlike in GLAD, no node-level latent has to encode its own neighborhood and collapse is only penalized if it discards graph-level information). Therefore, a collapse at the level is not incompatible with a good graph-level representation; if reconstruction performance remains high (as we observe with GraViti), it simply indicates that the graph-update part of the encoder is powerful enough to summarize the entire graph into a rank-one matrix before readout while conserving all information relevant for reconstruction. We provide an ablation study where we replace the transformer pooling by a simple sum pooling (see the updated Table 4). Reconstruction accuracy drops from 99.5% to 99.4%, showing that remains informative (but saying nothing about collapse). To further investigate whether this phenomenon occurs, we compare the average cosine similarity between node representations belonging to the same graph with the average cosine similarity across all node pairs. Across 1024 randomly sampled molecules from PubChem16, we obtain an average within-graph cosine similarity of 0.044, compared to 0.057 across all node pairs. This suggests that node representations within individual graphs are, if anything, slightly more diverse than the overall population of node representations. In particular, we find no evidence that nodes belonging to the same graph systematically converge to similar representations. While this analysis cannot rule out all forms of representation collapse, it provides no indication of within-graph collapse in .
-
Decoder side: duplication of . We duplicate times ( being the predicted size) and combine it with size information and a sinusoidal positional encoding . The node inputs thus share the same content, coming from , and differ only by position. This is deliberate. Because the training targets and reconstruction loss use a canonical node ordering (see W1), position always refers to the -th node in that order, so the decoder can learn to produce node-specific outputs from the shared content and the position. Without all node inputs would be identical and reconstruction would fail.
Summary. The graph-level design removes the need for node latents to encode local neighborhoods, which is the source of collapse in GLAD. The broadcast is made safe by together with the canonical ordering, and the high reconstruction accuracy in Table 1 indicates that nodes are well distinguished in practice.
Rebuttal: Reviewer m1si - III
W3
The authors claim that their model is scalable. I think they make such a claim because they can avoid solving the cubic graph matching problem. However, latent-node representations can also avoid this problem by keeping node ordering information from encoder input to decoder output. Thus, I would suggest that the authors revise this claim. Especially, the claim remains very generic, given that their graph transformer has quadratic complexity in the number of nodes compared to less expensive standard message-passing graph neural networks.
We thank the reviewer for this remark and agree that the claim should be made more precise. Our scalability claim has two parts, and neither is meant as a claim of efficiency relative to message-passing GNNs or node-level models:
- Computational scalability relative to matching-based graph-level models. As the reviewer points out, this advantage stems from avoiding the costly (cubic) matching step. It holds only against graph-level models, whose standard is to use a matching step: node-level models need no matching, since each node latent stays tied to its input node and output node by construction. We therefore claim no scalability advantage over node-level VAEs. We make the trade-off (scalability vs. graph-level expressivity) explicit at the end of Section 2; and we compare in Appendix A against a node-level variant of our architecture (identical except for the absence of the readout/readin). That variant expectedly reconstructs better, but at the cost of losing the graph-level representation. We made it explicit in the revised version that our scalability claim holds with regards to matching-based graph-level methods, which is the core claim of our paper.
- Reconstruction quality as graphs grow. Still at the graph level, our canonical-ordering approach reaches better reconstruction than matching-based approaches. Matching thus acts as a performance bottleneck that becomes harder to train as graphs grow. GLAD makes the same observation in Section 2: "Graph-matching scales poorly and is inaccurate for large graphs."
To support this claim, we report intermediate results for two models of the same size (35M parameters, both autoencoder and using aromatic form of PubChem32, our largest dataset) trained for 5 epochs on the same computational architecture: GraViti reaches 73.5% after a single epoch (40.5 h), which GRALE only matches after five (73.3% at 229.8 h), about 5.7× less training time for the same accuracy. Then, our model keeps improving to reach 97.5% in five epochs. We will add these results in the revised paper. This strongly support our claim that our approach alleviates the computational and performance bottleneck induced by the matching step by leveraging our aligned loss.
Table: Accuracy vs. cumulative training time (GraViti vs. GRALE), AEs (35M parameters), PubChem32.
| Epoch | GraViti Acc. | GraViti Time (h) | GRALE Acc. | GRALE Time (h) | Δ Acc. (pts) |
|---|---|---|---|---|---|
| 1 | 73.5% | 40.5 | 48.8% | 56.0 | +24.7 |
| 2 | 86.8% | 76.3 | 61.2% | 98.7 | +25.6 |
| 3 | 92.7% | 113.7 | 67.9% | 143.5 | +24.8 |
| 4 | 96.2% | 149.4 | 71.1% | 185.4 | +25.1 |
| 5 | 97.5% | 186.5 | 73.3% | 229.8 | +24.2 |
Table: Compute-matched comparison.
| GraViti | GRALE | |
|---|---|---|
| Avg. time per epoch | 37.3 h | 46.0 h |
| Time to reach ~73% accuracy | 40.5 h (epoch 1) | 229.8 h (epoch 5) |
| Accuracy at ~186 h | 97.5% (epoch 5) | 71.1% (epoch 4) |
On the quadratic cost of the transformer. We agree that self-attention is in the number of nodes, whereas standard message-passing GNNs are , roughly linear for molecular graphs. Our scalability claim concerns the matching step, which costs and comes on top of the backbone. While using message passing GNNs is tempting, it suffers from two drawbacks:
- an MPNN-based encoder degrades the performance of the model in a significant manner (the ablation results are shown in Table 3);
- the decoder still has to predict the full adjacency matrix, which is already , so attention does not change its asymptotic cost. Neither MPNNs nor node-level autoencoders alleviate this issue, since the bottleneck is predicting the adjacency matrix, which they all need to do.
In the revised paper we have (i) replaced the generic "scalable" with more detailed statements, (ii) added the supporting GLAD citation, (iii) clarified that our method is quadratic through the use of attention and the need to reconstruct the entire adjacency matrix and (iv) will enrich the training time table with more complete values.
Rebuttal: Reviewer m1si
We thank the reviewer for their thorough and extensive review. We answer below the different weaknesses and questions that arise throughout the review, and hope that our answer and results will clarify several of the points raised.
W1
We thank the reviewer for pointing us to GLAD [1], which we agree is related to the domain of graph autoencoding, and which we will discuss explicitly in the revision.
Different latent spaces. GLAD operates in a node-level latent space: its encoder produces a set of node embeddings Zraw={zi}i=1N, each quantized independently. The latent is therefore size-dependent and permutation-equivariant. Ours is a graph-level, permutation-invariant latent.
Why GLAD avoids graph-level latents. The GLAD authors motivate their choice by noting that graph-level latents require solving a graph-matching problem in the reconstruction loss, and that "this extra step adds more computational complexity and is inaccurate for large graphs" ([1], Sec. 2, "Continuous-graph latent space"). This matches our findings in Table 1, where the reconstruction quality of matching-based graph-level models degrades as graph size grows. Our approach is designed to avoid the matching step: we use a canonical node ordering for the training targets and the reconstruction loss. As a result, our AE reaches on PubChem32 (molecules of size 32) a reconstruction accuracy of 98%, compared to 73.3% for GRALE, the state-of-the-art matching-based model, a gap of 24.7 points.
GLAD's graph-level baseline. GLAD includes a graph-level model as a baseline, described only as a "vanilla VAE on a global structure, pooled latent nodes, to get a continuous-latent representation" [1]. Neither the paper nor the released code details its architecture or training, but we suppose that it was trained using matching (as stated in Section 2). That model is also simply evoked in an experiment but never thourouhly analyzed by the authors.
Planned revisions. We will cite GLAD in the introduction and related work (node-level latent models) and when motivating our matching-free design.