acceptodds
Under review as a conference paper at ICLR 2027

Scalable Hierarchical Graph Generation via Soft Community Structure

Abstract

Generating large attributed graphs requires reproducing the topology, generating attributes jointly with the structure, and remaining scalable. Many real-world graphs exist as a single large graph, so a generative model has to generalize from the one graph it is fit on, without independent samples. We present Schema, which recursively decomposes a reference graph into a hierarchy of soft communities, assigning each node a membership distribution. Generation is then split into three stages, each trained independently: (1) synthesizing node attributes conditioned on soft memberships, (2) generating intra-community edges from local structural context, and (3) modeling inter-community connections over bridge nodes whose membership mass is distributed across several communities. No stage forms the full adjacency matrix, and each stage operates on a subgraph bounded by the community size. We also introduce an evaluation protocol that covers structural fidelity, memorization, downstream utility, and scalability. On four real-world attributed graphs, Schema recovers the balance between local and long-range structure more closely than any other model that generates attributes, while reproducing only a small fraction of the reference edges. It retains the downstream accuracy of the reference graph without raising it artificially above that level. Baselines that match its structural fidelity memorize the reference, while those with higher downstream accuracy either exceed the reference accuracy or fail to complete on the larger graphs. We measure scalability on six additional graphs with up to 10 million nodes.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Generation, Hierarchical Graph Models, Soft Community Structure, Attributed Graph Generation, Large-Scale Graph Generation

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_NRPUOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper addresses attributed graph generation from a single large reference graph. SCHEMA first partitions the reference with Leiden into leaf communities, contracts them into supernodes, and recursively applies Leiden to build a cluster tree. Hard labels are relaxed into soft memberships by a parameter-free, row-normalized personalized-propagation scheme (Eq. 1); nodes with substantial mass in a second child cluster are “bridge nodes.” Generation is factorized into three independently trained stages: (1) a per-leaf Transformer generating node features conditioned on soft memberships and a pooled feature row; (2) a VGAE with FiLM degree conditioning and a bilinear decoder generating intra-leaf edges under a per-node degree budget, sampling latents from the prior at generation time; (3) a bilinear scorer plus a parameter-free cluster-affinity term that generates inter-community edges among a bounded candidate pool of bridge nodes. The generated graph preserves the reference node set and labels. Evaluation covers structural fidelity (degree W1, triangle ratio, assortativity, Inter/Intra edge ratio), memorization (edge overlap, self-overlap, neighborhood Jaccard, plus attribute-level leak measures), downstream utility (TSTR/TRTR, TSTS−TRTR, architecture-ranking correlations, with a homophily-rewiring calibration), and scalability on six graphs up to 10M nodes.

Critical strengths

Evaluation design is thoughtful and unusually honest. Treating memorization as a first-class axis (with self-overlap exposing GAE/NetGAN mode collapse, and the Citeseer constrained-node analysis in A.4.3), and decomposing TSTS gains into homophily inflation vs. residual (A.5, Table 14), are genuinely useful contributions to single-graph evaluation. The GraphMaker homophily-inflation finding is a real insight.

Scalability is demonstrated, not just claimed. Generation completes on OGBN-Products (2.4M) and IGB-Medium (10M, with a leaf cap) on one 24 GB GPU; per-stage runtime and memory are reported (Fig. 2, Table 15). The any-size extension (A.7) is practical.

Thorough baselines and transparent deviations. The exact O(M) DC-SBM sampler, alignment classes for memorization, and documented baseline caveats (A.2.3) are careful. Code and generated graphs are released.

Critical weaknesses
  1. The learned edge model does not improve on DC-SBM given the same partition. This is the central problem. DC-SBM is handed the same Leiden partition SCHEMA uses as its leaves (A.2.1), and it reaches Inter/Intra of 0.99/0.97/1.13/0.80 with edge overlap 0.05–0.08 — the same regime as SCHEMA (0.98/1.03/1.16/0.95, EO 0.03–0.10). On degree W1, DC-SBM is better on Cora ML (0.47 vs. 1.08), Amazon Photo (2.80 vs. 5.42), and Amazon Computers (2.80 vs. 11.08); on triangle ratio it is comparable or better (0.47/0.38/0.38/0.39 vs. 0.36/0.28/0.29/0.55). A learning-free O(M) Poisson model with the same inputs therefore matches or beats SCHEMA’s structure. The paper’s “among the models that generate attributes” framing hides this. What does the three-stage learned pipeline buy over DC-SBM + a separate attribute generator?

  2. Most of the “generated” graph is copied from the reference. Node identities, labels, the exact Leiden partition, the cluster tree, soft memberships, per-node reference degrees (FiLM conditioning + degree budget), and pooled connectivity Ap(c)A_p^{(c)} are all read from the reference at generation time. Edge overlap measures only whether specific endpoints are copied; it does not capture that the degree sequence, community assignment, and label of every node are reproduced exactly. This undermines the privacy motivation in the introduction and makes the comparison with “memorizing” baselines less clean than presented. The paper should discuss what information leaks through the hierarchy itself.

  3. Attributes and edges are not jointly generated in any meaningful sense. At generation, Stage 2 samples latents from the prior and Stage 3 reads memberships and pooled connectivity, so neither edge stage sees the generated attributes; the “Attribute source: Reference” ablation (Table 18) confirms structure is unchanged when generated features are replaced by real ones. The consequence is visible in Table 13: adjusted homophily drops from 0.67→0.51, 0.75→0.50, 0.79→0.59, and feature-only accuracy drops by 0.16–0.32. The attribute–structure dependence that distinguishes attributed from topology-only generation is largely lost. The claim “attributes and connectivity are tied to the same decomposition” is true only through the reference-derived membership matrix.

  4. The paper’s own ablation contradicts its explanation for low triangle density. Section 4.2 attributes the triangle ratio of ~0.3 to edge independence (Chanpuriya et al.). But Table 18 shows an inner-product Stage-2 decoder reaches triangle ratio 1.04 with edge overlap only 0.071 (vs. 0.038), and an MLP predictor 1.20 at 0.079. Low memorization and near-reference triangle density are simultaneously achievable within the pipeline; the reported configuration appears to have been chosen to minimize overlap at the cost of a 3–4× triangle deficit. This choice needs justification, and the downstream/utility numbers should be reported for the inner-product variant.

Questions for authors

What does SCHEMA’s learned edge model add over DC-SBM with the same Leiden partition? DC-SBM matches Inter/Intra and triangle ratio and has 2–4× lower degree W1 on three of four datasets. Please report DC-SBM + a standalone attribute model (e.g., Stage 1 alone) as a baseline.

The inner-product Stage-2 decoder achieves triangle ratio 1.04 at EO 0.07. Why is the bilinear decoder with triangle ratio 0.28 the reported configuration? What are its downstream and homophily numbers?

Since the generated graph reproduces each node’s label, degree, community, and tree position exactly, how should edge overlap be interpreted as a memorization measure? How much of the reference can be recovered from the hierarchy and degree conditioning alone?

Reviewer_dnuSOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The manuscript proposes Schema: a new method for generating attributed graphs at scale. Rather than following a more classical approach of generation, in which a ML model is trained to generate a graph from an unbiased source (often iid noise), Schema dissects an existing graph into clusters to assign each node a soft community membership. Then, Schema regenerates a new graph structure and node attributes starting from these memberships.

Critical strengths
  1. Scalable model Schema manages to process large graphs with relatively low compute effort and memory.
  2. Attributed graph generation While some early attempts exist, Schema is the first state-of-the-art method for attributed graph generation.
Critical weaknesses
  1. Unclear methodology Part of the methodology is unclear. For instance, the paper does not discuss how the training of Schema components happens (e.g., node feature generator)
  2. "Editing" rather than generation Compared to the more popular graph synthesizers, in which graphs are generated from noise via autoencoder, autoregression, or diffusion model, Schema starts from the clusters of an existing graph and generates the edges within these clusters. In principle, this may introduce some advantages such as lighter training. However, I have some concerns about the capability of Schema to produce novel graphs. For example, I expect Schema to produce a fac-simile of an instance of a citation graph rather than understanding the underlying dynamics of a citation network and generating a new one.
  3. Lack of integration of global features The major bottleneck that prevents graph generation at scale is the hardness of representing global network properties in a compact representation. In this sense, the idea of using clustering to localize the generation process sounds more like avoiding the problem rather than solving it.
  4. Lack of global structural metrics As a follow-up to point 3, the evaluation covers local properties only. I wonder how Schema performs on global metrics like spectral properties.
  5. Low structural quality Even on local structural properties, Schema performs orders of magnitude worse than the structure-only baselines.
  6. On the validity of generated graphs As a consequence of points 2 and 3, I wonder whether Schema can preserve the validity of complex graph properties, like planarity or an underlying geometry. I see this could be a possible hard requirement for some real-word use cases like powergrids.
  7. Lack of baselines in scalability evaluation Schema scalability results look remarkable. However, I suggest comparing it with a couple of baselines to better highlight the performance gain.
Questions for authors
  1. Could the authors clarify the training methodology they used for Schema? For instance, what loss function did you use for the node attributes?
  2. Could the authors provide a methodology figure? Since the method differs substantially from other graph generative methods, I believe it could better highlight the new idea brought by Schema.
  3. Do the authors expect Schema to learn the underlying dynamics of the graphs it is trained on?
  4. Could the authors introduce some global structural properties to test the structural quality of the generated graphs?
  5. Do the authors expect Schema to be capable of preserving hard validity requirements posed by datasets? Consider the case of planarity as a possible example, but this could also extend to underlying geometry (either presence or lack of) or molecular stability.
  6. Could the authors compare the runtime and peak memory usage of Schema with a couple of baselines?
  7. Could the authors explain how does Schema take into account the correlation between node features and structure? From what I understood, the node features and edges are generated independently.
Reviewer_ETK5OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

SCHEMA generates attributed graphs from a single reference graph. It constructs a hierarchy based on community partitions, obtains soft community memberships through propagation, and uses bridge nodes to organize the generation of connections between communities. Generation proceeds in three stages: node attributes, intra-community edges, and inter-community edges. Shared models and restrictions on candidate node pairs reduce computational costs. The default setting preserves the reference node identities and generates graphs of the same size; an extension in the appendix adjusts the size through community replication or subsampling. The evaluation covers structural fidelity, memorization and sample diversity, transfer utility for node classification, and computational costs, supported by extensive ablation and diagnostic studies.

Critical strengths

The paper presents a well-motivated hierarchical design, using soft community memberships and bridge-node selection to model connections efficiently. The extensive evaluation covers graph quality, memorization, downstream utility, and computational cost, with ablations and scalability tests that help clarify the method’s strengths and limitations.

Critical weaknesses
  1. The scope of the joint attribute–structure model needs clarification, since attributes and edges are connected through shared memberships rather than the generated attributes themselves. The current evaluation does not directly establish when this shared conditioning is sufficient to capture their dependencies.

  2. The main quality evaluation uses citation and co-purchase networks with binary bag-of-words attributes. Although the additional datasets support scalability, evidence of joint generation quality for other attribute types and domain-specific constraints remains limited.

Questions for authors
  1. How do the generated graphs compare with reference graphs in terms of spectral properties, such as normalized-Laplacian eigenvalue distributions?

  2. What is the joint generative distribution, including the shared conditions and randomness used by each stage? Does it assume conditional independence between attributes and edges given these conditions, and what empirical evidence supports the adequacy of this design?

  3. Can the authors provide a concrete example showing meaningful dependencies between generated attributes and connections, such as atom–bond compatibility or spatial consistency in road networks, if suitable for the method? Could a relevant downstream task also demonstrate the practical value of this joint modeling approach?

1 comment

Thank you for the responses and revisions.

  1. Evaluation protocol (W3/Q3): Including the unreduced computation subgraphs in the full 60-target cohort (Appendix B.2, Table 9) makes the comparison across baselines much fairer. However, I notice that once all 60 targets are included, HypoExplainer's performance on GIN drops noticeably (e.g., F1 = 0.000 and Sparsity = 0.187 on Tree-Cycles because many targets fail to reduce the neighborhood). This fallback behavior should be discussed more clearly in the main text.
  2. Node features and Assumption 6 (W1/Q1): Since no experiments were added for models relying on node features rather than graph topology, the practical validity of Assumption 6 remains a limitation.
  3. Edge dependence (W2/Q2): As the authors note, the Z-test relies on edge independence and dependent-edge settings are left to future work, so the statistical validity on general graphs is still limited.

Overall, I still value the statistical perspective of this work and will keep my score at 3, while taking these remaining limitations into account in the discussion.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.