acceptodds
Under review as a conference paper at ICLR 2027

GraphScale: Scaling Controlled Graph Generation through Hierarchical Constraint Composition

Abstract

Controlled graph generation aims to generate graphs that satisfy specified structural constraints, yet existing methods largely trade off controllability and scalability: models that support fine-grained structural conditioning typically operate on small graphs, while scalable generators provide limited control over topology. We study whether global structural attributes can be factorized into local constraints and recovered through hierarchical composition. We introduce GraphScale, a model-agnostic framework that recursively decomposes target graph-level attributes into a hierarchy of subgraph constraints, generates leaf subgraphs independently, and composes them bottom-up using cross-subgraph connectivity conditioned on the remaining global structural attributes. This hierarchical factorization allows the underlying generator to operate only on bounded-size subgraphs while enabling the composed graph to scale to orders of magnitude larger sizes. Across real and synthetic datasets, GraphScale extends existing conditional graph generators to graphs with thousands to tens of thousands of nodes while retaining control over multiple structural properties and preserving global topology. These results demonstrate that compositional structural control offers a promising approach to scalable controlled graph generation.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Scalable Control Graph Generation

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_eNcxOpenReview ↗
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 tt 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 nn nodes, the subgraph generator considers about n2n^2 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.
Reviewer_b4wROpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper proposes GraphScale, a model-agnostic framework for scalable controlled graph generation. Specifically, GraphScale recursively splits a graph using the Kernighan–Lin algorithm until every leaf contains at most 50 nodes. After that, GraphScale applies an existing controlled graph generator to generate leaf graphs. Finally, it employs an autoregressive cross-graph link predictor to compose the generated leaf graphs bottom-up. Empirically, GraphScale is capable of handling graphs with tens of thousands of nodes.

Critical strengths

The proposed approach is intuitive and elegant.

Critical weaknesses
  1. GraphScale aims to generate graphs satisfying the specified attributes, but the paper never evaluates whether these constraints are actually satisfied. In addition to SD and NSD, the paper should measure the distance between the attributes of generated graphs and the requested attribute values.
  2. Multiple details in the evaluation protocol require clarification. L347 says that the train-validation-test split is based on (parent graph, right subgraph, left subgraph) triplets. But how specifically are validation and test triplets used? And since the same subgraph can be a child in one split and a parent in another, how do you ensure there is no train-test leakage? Finally, does Table 1 report end-to-end generation results, or does GraphScale use child subgraphs not available to other methods?

I am ready to substantially increase my score if the points above receive adequate answers. I would keep my score unchanged if the paper still lacks end-to-end generation experiments after revision, or if those experiments show poor results.

Questions for authors

See weaknesses.

Additional comments (no effect on score)

Have you measured how many edges are generated by the leaf models versus the cross-subgraph model? If most edges are generated by the cross-subgraph model (which I would expect at least when the average degree is high enough, though this may also hold for large enough graphs in general), does that mean that the cross-subgraph model does most of the work, while the leaf model has little effect? Since the results in Table 1 are heavily influenced by the leaf model, I would expect this is not the case, but it would be interesting to know why. The authors are not required to answer this question, I am just curious.

Reviewer_Tz6nOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes GraphScale, a model-agnostic framework for scalable controlled graph generation. The framework decomposes global structural attributes into hierarchical subgraph-level constraints, generates small subgraphs using existing graph generators, and recursively combines them through an autoregressive cross-subgraph link predictor. By separating local subgraph generation from global graph construction, GraphScale aims to extend existing conditional graph generators to graphs containing thousands or tens of thousands of nodes. Experiments on real and synthetic datasets demonstrate improvements in structural similarity and scalability compared with selected baselines.

Critical strengths
  1. A scalable framework for controlled graph generation: GraphScale addresses the challenge of generating large graphs while controlling their structural properties. The hierarchical decomposition and composition strategy is a reasonable approach to overcoming the scalability limitations of existing conditional graph generators.

  2. Model-agnostic design: The proposed framework can incorporate different graph generators without modifying their underlying architectures. The experiments demonstrate its applicability to several existing generators, including TOPOGEN, DiGress, GruM, and HGGT.

Critical weaknesses
  1. Insufficient comparison with existing scalable and controlled graph generators: The experimental evaluation lacks comparisons with important existing methods, particularly TrillionG (SIGMOD 2017) and GenCAT (Information Systems 2023). TrillionG supports graph generation at trillion-edge scale using a recursive vector model, while GenCAT enables scalable attributed graph generation with control over relationships between node classes, attributes, and topology. Although these methods differ from GraphScale in their generation mechanisms and supported constraints, they are relevant baselines for evaluating scalability and controllability. Without comparisons against these methods, it is difficult to assess the practical advantages of GraphScale over existing approaches.
  • TrillionG: A trillion-scale synthetic graph generator using a recursive vector model
  • GenCAT: Generating Attributed Graphs with Controlled Relationships between Classes, Attributes, and Topology
  1. Insufficient evaluation of structural controllability and scalability: Although controlled graph generation is the central contribution, the experiments primarily evaluate structural similarity using Spectral Difference (SD) and Network Similarity Distance (NSD), rather than directly measuring how accurately generated graphs satisfy the specified structural constraints. Furthermore, the scalability evaluation is limited, and many existing generators are reported as out-of-memory without detailed computational settings. Consequently, the extent to which GraphScale achieves both controllability and scalability remains unclear.
Questions for authors
  1. Comparison with additional baselines: Could the authors include TrillionG (SIGMOD 2017) and GenCAT (Information Systems 2023) as additional experimental baselines? In particular, comparisons of generation time, memory consumption, scalability, and structural fidelity would help establish the advantages of GraphScale. Since the supported structural constraints differ across these methods, the authors should also clarify which aspects of controllability can be fairly compared.

  2. Evaluation of structural controllability: Could the authors directly evaluate how accurately GraphScale satisfies each specified structural attribute, including density, clustering coefficient, local bridges, and clique counts? In particular, how well does GraphScale satisfy multiple target constraints simultaneously?

  3. Scalability and experimental validity: Could the authors provide a more systematic evaluation of generation time, memory consumption, and structural fidelity as graph size increases? Additionally, since the train-validation-test split is described as being performed over parent–child subgraph triplets, could the authors clarify whether triplets derived from the same original graph are kept within the same split to prevent potential information leakage?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.