- 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
-
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?
-
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 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.
-
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.
-
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?
Thank you for the responses and revisions.
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.