- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes GraphVQ, a discrete token-based autoregressive framework for graph generation. The method first employs BFS serialization and VQ-VAE to encode node attributes and local structures into discrete tokens, then uses a GRU to model the token sequence. Finally, token-derived pairwise features are used to guide the generation of the full adjacency matrix, mitigating the limitations of local windows in capturing long-range edges. Experiments on four graph datasets demonstrate the effectiveness of the proposed method.
Critical strengths
-
The two-stage generation framework helps alleviate the limitations of local serialization windows in generating long-range edges, offering practical value.
-
The experiments include multiple baselines and ablation studies, demonstrating competitive generation quality on several datasets.
Critical weaknesses
-
Limited Novelty. The proposed method primarily combines existing techniques, including BFS serialization, VQ-VAE, GRU, and chunk-wise autoregressive generation. The core Pair-wise Conditioning mechanism also relies on conventional feature construction and mean pooling, lacking sufficient methodological novelty. Furthermore, pair-wise features within each chunk are averaged, meaning that the conditioning is not strictly performed at the pair-wise level. This further weakens the claimed novelty of the approach.
-
Insufficient Validation of Core Contributions. The continuous baseline changes both the latent representation type and the prior family, making it difficult to isolate the contribution of VQ. Although the paper includes several conditioning ablations, these experiments primarily demonstrate the effectiveness of conditioning information, without sufficiently establishing the unique advantages of the proposed chunk-pooled decoder over alternative structure-aware edge generation mechanisms.
Questions for authors
-
In Stage B, pair-wise features within the same chunk are mean-pooled, resulting in a shared conditioning representation. How does the model distinguish the edge probabilities of different node pairs under this setting? What specific role do the position-specific readout heads play in this process?
-
The paper reports that unweighted BCE leads to significant under-generation of edges on MUTAG, while positive-class weighting substantially improves connectivity. Do the authors attribute this primarily to graph sparsity, class imbalance, or distribution mismatch between the token prior and the edge decoder?
4 comments
Response to Reviewer q6Uq (2/3)
Weakness 2: What do VQ and pooling each contribute?
We agree the Continuous control in the submission changes the latent type and the prior family together (an autoregressive Gaussian prior instead of the categorical GRU), so it cannot isolate quantization. We therefore ran two matched suites under the revision's MUTAG configuration (density-targeted Stage B, , temperature 1.0, same splits, 10k samples, seeds 0–4):
(a) Code-learning control. The VQ tokenizer is replaced by a same-dimension (32) continuous autoencoder whose latent is discretized post-hoc by k-means into the same code ids, keeping the categorical GRU prior, the Stage-B decoder, and the training budget fixed (continuous_cat). This isolates the code-learning mechanism — joint VQ training vs. post-hoc clustering — while holding the discrete interface itself fixed.
| MUTAG (density-targeted, 5 seeds) | degree | clustering | orbit | spectral | comp. size | conn. |
|---|---|---|---|---|---|---|
| GraphVQ (VQ + pooled) | 0.135±0.012 | 0.845±0.026 | 0.359±0.053 | 0.092±0.009 | 0.085±0.032 | 0.653 |
| continuous_cat | 0.139±0.015 | 0.844±0.005 | 0.393±0.026 | 0.086±0.010 | 0.061±0.024 | 0.703 |
| continuous | 0.180±0.040 | 0.898±0.012 | 0.521±0.117 | 0.104±0.006 | 0.002±0.002 | 0.821 |
| Raw | 0.138±0.012 | 0.851±0.009 | 0.392±0.050 | 0.101±0.019 | 0.075±0.020 | 0.704 |
On MUTAG, no significant difference was detected between joint VQ training and post-hoc clustering on any metric (orbit , degree ; paired , 5 seeds); this does not establish equivalence. The three discrete-interface variants have similar observed degree MMDs (0.135–0.139); the continuous-prior control is nominally worse on orbit (0.521 vs. 0.359/0.393; paired ). The one-stage, condition, and mask ablations separately support the contributions of token-derived conditioning and the Stage-B decoder. The matched code-learning comparison is limited to MUTAG and holds the discrete interface fixed; it does not isolate discretization vs. no discretization, since the continuous control also changes the prior family.
(b) Decoder comparison. Three alternative structure-aware decoders sharing the tokenizer, prior, candidate order, chunk width, and budget (density-targeted on MUTAG; unweighted tables for all four datasets are in the revision's Appendix C):
| MUTAG (density-targeted, 5 seeds) | degree | orbit | conn. | params | sample s/1k |
|---|---|---|---|---|---|
| Pooled (ours) | 0.135 | 0.359 | 0.653 | 20.7K | 17.1 |
| Per-pair | 0.158 | 0.291 | 0.454 | 20.5K | 18.8 |
| Within-chunk AR | 0.168 | 0.330 | 0.493 | 26.9K | 42.7 |
| GraphRNN-style | 0.147 | 0.329 | 0.732 | 33.6K | 8.8 |
On MUTAG, no significant advantage over pooled was detected on orbit or degree (paired on orbit: for per-pair/within-AR/GraphRNN-style). Pooled has the lowest observed degree MMD and sampling cost among the pair-conditioned heads; alternatives improve clustering/spectral, per-pair has lower observed orbit MMD ( vs. , ), and GraphRNN-style has higher connectivity ( vs. ). Pooled also has the lowest orbit MMD on the two largest benchmarks (PROTEINS vs. –; SYN-COMM vs. –). These quality–cost trade-offs motivate our choice; the full metric-level table is in Appendix C. (Training batch size 32 for all arms on MUTAG; the within-AR arm uses batch size 1 only for the largest PROTEINS graphs, which the revision states explicitly.)
Response to Reviewer q6Uq (3/3)
Response to Reviewer q6Uq (3/3)
Q2: Is MUTAG under-generation sparsity, class imbalance, or prior–decoder mismatch?
Three facts, without a claimed causal ordering among them:
- Class imbalance is structural. Positive bits are of all edge bits (384/3171); under true conditions the positive/negative conditional NLL is vs. nats/bit — the positive class has an observed higher NLL. These values come from a single-checkpoint, unweighted diagnostic, not five-seed statistics or a calibration assessment.
- Density targeting is the principled response. With positive-class weight , the weighted-BCE optimum is : shifts the per-bit target for a edge to , raising the sampled edge rate. The measured effect matches the intent: mean degree of generated MUTAG graphs rises to vs. in the training reference. The weight was selected in the diagnostic phase from by training-reference structural metrics (Table C.3), not on test metrics. This is a design choice for imbalanced edge prediction: the revised main table uses it on MUTAG (connectivity , orbit MMD , mean rank , five seeds), and the probability-oriented unweighted variant with validation temperature calibration is reported alongside in Appendix C.
- The decoder tracks its conditions; size is set by the prior. The oracle → reconstructed → generated NLL gap on MUTAG is (unweighted diagnostic run, seed 0): the observed average gap is small. The condition-dependence diagnostic (Fig. B.1) confirms the condition is used (+13.6% positive-edge NLL under global shuffle). Separately, generated graphs average nodes against a resampled target of because the token prior emits EOS earlier than the empirical length distribution; on MUTAG (max 28 nodes, below the generation cap of 64) the size gap therefore comes from the prior's EOS behavior, not from the edge decoder (Algorithm 1 now states that the sampled is an upper bound), and the revision reports this decomposition explicitly. (The NLL decomposition and the position-head diagnostic were computed under the unweighted diagnostic configuration; their findings are limited to that configuration.)
Thanks for the author's reply. The newly added control experiments provided valuable evidence for understanding the contribution of VQ. But I still have concerns about the novalty of the method. I maintain my score.
Response to Reviewer q6Uq (1/3)
We thank the reviewer for the two precise questions — they target exactly the two places where the implementation and the narrative needed to be pinned down, and the matched controls below answer them.
Q1: How does the model distinguish edge probabilities within a chunk?
Equation (9) computes a masked mean of the projected pair features rij over the valid positions of chunk q; the GRU combines this chunk summary with the previous chunk's bits and its hidden state into a shared chunk state sq. Equation (10) then applies a position-specific readout vector wb to sq: the B candidate slots of the chunk receive logits wb⊤sq and are sampled independently. The design is deliberately a chunk-level shared condition with position-wise Bernoulli outputs.
Two diagnostics confirm this reading:
The revision uses the term chunk-pooled pair features throughout and adds an algorithm box for the Stage-B decoder.