- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper proposes GraphScale, a model-agnostic framework for controlled generation of large graphs. Given a vector of target structural attributes (e.g., number of nodes and edges, density, average clustering, local bridges, and cliques), an MLP-based attribute splitter recursively predicts the attributes of two child subgraphs until each leaf has at most 50 nodes. An existing small-graph generator then produces each leaf subgraph, and an autoregressive cross-link predictor merges the subgraphs bottom-up, conditioned on the parent attributes. The training hierarchy is built by recursive Kernighan-Lin bisection. The method is evaluated on Ogbn-Arxiv, Enzymes, and SBM with spectral difference (SD) and network similarity distance (NSD), using HiGen and Erdős-Rényi as baselines.
Critical strengths
The idea of splitting global attributes into local constraints and composing the subgraphs with an attribute-conditioned link predictor is simple and practical. It lets existing small conditional generators produce graphs with thousands of nodes. If validated properly, this would be a useful contribution for large-scale controlled graph generation.
Critical weaknesses
I recommend rejection in its current form. There is an interesting idea, but the method lacks formalism, the presentation needs substantial work, and the experiments are not convincing.
-
Lack of formalism. There is no probabilistic model explaining which distribution GraphScale models or approximates, and there is no complexity analysis, even though scalability is the main motivation. The pipeline reads as a combination of heuristic components rather than a principled generative model. For instance, iterative local expansion (Bergmeister et al., 2024) combined with some form of sliding window seems roughly equivalent and much more principled. Some details are missing or incorrect:
- The decoder state at step in Eqn. (1) is never defined (only the initial state is), and it's unclear how the number of cross-links is decided, i.e., when decoding stops.
- The justification of teacher forcing is not correct (Figure 3c and Section 4.4). Teacher forcing doesn't prevent drift. It is used because training on long sequences is otherwise intractable (the gradient would have to be stored through the whole chain), and it actually makes the model worse at correcting its own errors, since it always follows the ground-truth path during training. The training procedure should be detailed.
- The Kernighan–Lin splitting should be explained, at least in the appendix. Also, it doesn't guarantee connected children, contrary to Section 4.1.
- The attribute splitter has no consistency constraints (e.g., the number of nodes of the parent must equal the sum over the two children).
-
Presentation and positioning. Several statements in the introduction and related work are unclear or not accurate:
- The attributes the paper calls "fine-grained" (clustering, cliques, local bridges) are rather global attributes, and global attributes are the ones that are difficult to enforce.
- I don't see how scalability and controllability are "separate" (lines 131–133). Control is usually plugged on top of a generator, biasing the generation toward regions where the constraint is satisfied.
- Hierarchical generation is not motivated only by scalability (line 107). For images, for example, it's not about scale.
The paper also has many typos and broken citations (e.g., "controled", "hirarhcy", "efficienct", "This graph attributes", missing spaces after commas in lines 104–107, and "?" in the appendix related work).
-
Unconvincing experiments. The baselines are dated, and the metrics and datasets are uncommon for graph generation. Most importantly for a controlled generation paper, the error between the target attributes and the attributes of the generated graphs is never reported. Some other concerns:
- The OOM results for SBM are strange, since the listed generators are commonly evaluated on SBM.
- The generated examples in Figures 6 and 7 don't look like the training data. It would be better to show several samples per family, with the targeted properties and the dataset they come from.
- The degree distributions in Figures 4 and 9 are shown on a log scale and don't match well (e.g., the high-degree tail of Ogbn-Arxiv is missing). I wonder whether random graphs with the same density would produce similar-looking plots.
- The runtime analysis (Figure 8) is surprising. If both subgraphs have nodes, the subgraph generator considers about edges, and so does the cross-link predictor, so the claimed low cost of cross-link prediction probably comes from architectural choices.
References
[R1] "Size matters: Large graph generation with HiGGs", arXiv 2023.
Questions for authors
Clarifications:
- What probabilistic model does GraphScale define over graphs, and what is the complexity of the full pipeline (including the cross-link predictor near the root)? How does it compare, conceptually and empirically, with iterative local expansion (Bergmeister et al., 2024) and hierarchical methods such as [R1]?
- What is the error between the target attributes and the attributes of the generated graphs for each attribute and each dataset?
- How is the number of cross-links decided, and how is the decoder state updated at each step?
- How exactly is the train/val/test split done? Since triplets come from the same recursive partition, and Ogbn-Arxiv is a single graph, can test graphs share nodes or subgraphs with training triplets?
- Why does TopoGen have the lowest runtime? If it doesn't use iterative denoising, does it generate edges sequentially?
- Enzymes is a set of 600 small graphs (about 33 nodes on average). How is it used to evaluate large graph generation, and how are the reported 37K nodes obtained?
Minor:
- The HiGen NSD average in Table 1 should be 17.42 (not 19.41), and the text reports an average SD of 0.39 for TOPOGEN on Enzymes and SBM, while Table 1 gives 0.315.
- The density ablation (Figure 5) masks density while keeping node and edge counts fixed, but density is a deterministic function of these two counts.