{"id":"d50b58f9-4a49-4abe-a86f-31c8bcbf15be","arxiv_id":"2411.13888","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.5,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A parameter-light, hierarchy-based graph generator that uses only node and edge counts plus a Poisson degree prior to match real-world graph statistics without training data.","lead":"This paper proposes a two-stage, non-learned graph generator that builds hierarchical star-shaped substructures from just the number of nodes and edges, then fills in remaining edges using a Poisson-based degree mixing rule. It matters because it offers a way to generate realistic graphs without any training data, in contrast to deep generative models that need large datasets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The reported advantage over baselines is not yet established: dmax and k are tuned per dataset without a stated selection rule, and the same method's MMD values differ across tables, so the central comparison lacks a reproducible protocol.","rationale":"The reader's weakest assumption is the Poisson prior with lambda equal to the average degree. That is a reasonable concern because the same statistic also appears in the degree-MMD evaluation, but the paper's distribution ablation (Table 3) directly tests it and still favors the Poisson choice, so the concern is partly addressed. The more consequential gap is the unexplained per-dataset setting of dmax and k, which is not covered by the reader's weakest_assumption. If those thresholds are tuned with access to the evaluation data, then the headline comparison against traditional and deep generative models is not a fair test of a limited-resource generator. The internal discrepancy between Table 1 and Table 5 Ours rows strengthens this concern because it shows that reported MMD values are not stable enough for the reader to verify the claimed margins. I therefore keep the reader's CONDITIONAL verdict: the method is plausible and the direction is promising, but the central empirical claim should not be accepted as stated until the selection rule for dmax and k is specified, the code is released, and variance is reported. The Appendix C.2 proof error is real but secondary; it affects the advertised theoretical guarantees, not directly the empirical tables, so I mention it only as supporting evidence rather than as the primary objection.","tokens_in":26466,"tokens_out":5359,"duration_ms":60564,"concrete_test":"Re-run Table 1 for all 12 datasets with dmax and k chosen by a fixed, pre-registered rule that uses only N and M (for example, dmax = floor(4M/N) and k defined as in Eq. (2)), reporting mean and standard deviation over at least 10 seeds for Ours and for the baselines. If Ours no longer stays in the top two on the majority of datasets, or if the Table 1 Ours values cannot be reproduced within MMD noise, the claimed advantage depends on dataset-specific tuning rather than on the published algorithm.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is empirical: a limited-resource, non-learned generator fits ground truth distributions better than baselines on MMD metrics. The load-bearing part of that claim is the fairness and stability of the MMD comparison, and that part is insecure. Section 5.3 treats dmax and k as tunable parameters and shows that disabling them changes social-network degree MMD from 0.0308 to 0.1901, yet the main results in Table 1 never state how dmax and k are selected for each dataset. If they are chosen by looking at the ground-truth graphs or by optimizing the reported MMD, the limited-resource premise (only N and M known) is violated and the comparison with baselines is not controlled. The problem is compounded by unreported variance: the same method's MMD values differ substantially between Table 1 and Table 5 on identical datasets (e.g., ENZYMES degree MMD is 0.1811 in Table 1 but 0.3274 in Table 5), so the point estimates are not stable. The theoretical appendix does not mitigate this: Appendix C.2, Eq. (2), assumes independence between s_sub and Lent and moves expectation inside the Poisson PMF, which is not valid, so the claimed theoretical underpinning does not constrain the empirical comparison.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a non-learned, hierarchical graph generator for the limited-resource setting in which only the number of nodes N and the number of edges M are known. The first stage samples anchor-node degrees from a Poisson distribution with mean λ = 2M/N and builds star-shaped substructures; the second stage connects substructures and then adds remaining edges by sampling node pairs from a degree-mixing distribution that combines substructure size with the next-degree Poisson probability, subject to thresholds dmax and k. The authors claim theoretical guarantees for the hierarchical process and evaluate the method on 12 datasets from bioinformatics, social networks, and synthetic graphs, reporting MMD scores on average degree, clustering coefficient, and orbit counts and comparing with ER, BA, WS, MMSB, Kronecker, deep generative models, and LLM-based generation.","tokens_in":26696,"tokens_out":5859,"duration_ms":59796,"significance":"If the central empirical claim were established, the paper would make a useful contribution: an interpretable, parameter-light generator for settings where training data are unavailable or sensitive, with explicit algorithmic pseudocode and a broad comparison across several baseline families. The paper also deserves credit for attempting to justify the generator with an expectation calculation and for including distribution ablations. However, the current evidence is not yet reliable: the parameter-selection protocol for dmax and k is unspecified, the same 'Ours' method gives inconsistent MMD values across tables, and the appendix proof contains an invalid independence step. These issues are load-bearing for the main claim that the method fits ground-truth distributions better than existing generators.","major_comments":[{"comment":"","section":"§5.3 and Table 2; main results in Table 1"},{"comment":"","section":"Appendix C.2, Eq. (2)"},{"comment":"","section":"§5.2 Table 1 vs §E.3 Table 5"},{"comment":"","section":"§3, Observation 1 and Eq. (1)"},{"comment":"","section":"Appendix C.1, Algorithm 2, lines 2-7"}],"minor_comments":[{"comment":"","section":"§4.2, after Eq. (2)"},{"comment":"","section":"§5.2, discussion of Table 1"},{"comment":"","section":"Appendix C.1, Algorithm 2, line 21"},{"comment":"","section":"Appendix D.2"}],"recommendation":"major_revision","confidential_remarks":"I would ask the editor to require, as part of the revision, a reproducibility appendix containing code or a precise protocol for dmax/k selection and the MMD evaluation pipeline. The current absence of that protocol, together with the cross-table inconsistencies in the 'Ours' row, makes the headline comparison impossible to verify as written."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Let me cut to it: the method is a sensible combination of known ideas—hierarchical star substructures, a Poisson degree prior with mean set to 2M/N, degree-mixing selection, and two thresholds—and it makes sense as a fallback when you only have N and M. The paper does a decent job of testing it across three graph categories and is honest about the cases where it fails (REDDIT-BINARY, GRID). The threshold ablation and the distribution ablation are genuinely informative, even if the distribution results undercut the claim that Poisson is the uniquely right prior.\n\nThe problem is that the central empirical claim—that the method beats ER, BA, WS, MMSB, Kronecker, and untrained deep models on MMD—is not yet controlled. The stress-test note is on target: dmax and k are treated as tunable in Section 5.3, and the main results never state how they are set per dataset. If they are chosen with knowledge of the target graphs or by optimizing the reported MMD, the limited-resource premise is violated and the comparison is not fair. The point estimates themselves are unstable: the same 'Ours' row differs substantially between Table 1 and Table 5 for several datasets (e.g., ENZYMES degree MMD 0.1811 vs 0.3274; deezer 0.0371 vs 0.1401). Without error bars or a fixed protocol, those numbers don't yet support the 'optimal choice' conclusion. The appendix proof in Eq. (2) is also not valid—expectation does not commute with the Poisson PMF—so the theoretical backing should be read as intuition, not a guarantee.\n\nWhere does that leave the paper? As a proposal, it is worth taking seriously. The recipe is new enough as a combination, the method is simple and cheap, and the problem setting is real—this is for people working on graph generation in data-scarce or privacy-sensitive scenarios. But the current manuscript does not make a reproducible case for superiority. I would send it to peer review, not desk-reject it, because the idea has merit and the experiments can be fixed. The authors need to release code, specify a hyperparameter rule that uses only N and M or a validation split, report variance across generated graphs, and temper the claims accordingly. If those fixes land, I would cite it as a baseline. As it stands, I would not rely on the quantitative claims, but I would be interested to see a revision.","headline":"A sensible non-learned generator recipe, but the headline comparison to baselines is not yet reproducible; the paper needs a fixed hyperparameter rule, released code, and variance estimates before the empirical claims carry weight.","tokens_in":27266,"tokens_out":3972,"would_cite":false,"duration_ms":38957,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C82"],"pacs":[],"model":"deepseek-v4-flash","headline":"A non-learned hierarchical generator using a Poisson degree prior and degree-mixing preferential attachment fits real graph distributions better than classical and untrained deep generators across 12 datasets.","keywords":["graph generation","scale-free","non-learned generator","limited resources","hierarchical generation","Poisson degree distribution","preferential attachment","MMD"],"falsifier":"Run the same two-stage algorithm on a deliberately non-scale-free target, such as a regular lattice or a uniform-degree random graph, and compute the MMD on degree and orbit counts; the paper's own GRID results already suggest the method degrades there, pinpointing the boundary of the claim. Sharper still: replace the Poisson prior with the empirical degree distribution of the target dataset and rerun the generator; if the MMD improves substantially, the Poisson assumption is the bottleneck, whereas little change would show the hierarchy, not the prior, does the work.","tokens_in":26215,"feed_emoji":"🕸️","tokens_out":8892,"duration_ms":76475,"temperature":0.7,"pith_summary":"This paper argues that when training data is unavailable and only the node count N and edge count M are known, graph generation can still be performed well by relying on the scale-free property instead of learned models. The proposed generator works in two stages: it samples anchor-node degrees from a Poisson distribution with mean equal to the average degree $\\bar{D}=2M/N$ and builds star substructures around those anchors, then adds the remaining edges by sampling node pairs with probabilities that combine a substructure-preferential factor with a next-degree Poisson factor. Two thresholds, the maximum degree $d_{\\max}$ and a truncation value $k$, regulate how much deviation from the scale-free ideal the generator tolerates. The paper claims that this non-learned method fits the ground-truth distribution better than classical generators (ER, BA, WS, MMSB, Kronecker) and better than untrained or briefly trained deep generative models, measured by MMD on average degree, clustering coefficient, and orbit counts over 12 datasets. If right, it means useful graph generation does not require learning when the target graphs are approximately scale-free.","feed_headline":"Scale-free hierarchy beats deep graph generators with no training data","feed_subtitle":"Using only node and edge counts, a two-stage Poisson-based algorithm bests classical and deep baselines on 12 datasets.","key_machinery":"The load-bearing object is the two-stage hierarchical construction. In stage one, the algorithm samples a degree sequence for anchor nodes from the Poisson distribution $P(\\bar{D})$ with $\\bar{D}=2M/N$, turns each anchor into a star substructure $G^{(i)}_{\\rm sub}$, and partitions the node set into such substructures. In stage two, it draws the remaining edges by sampling endpoint pairs $u,v$, where each node's selection probability is $\\Pr(v^{(i)}_j)=s^{(i)}_{\\rm sub}\\cdot P(\\mathrm{Lent}[i][j]+1\\mid \\bar{D})$: the substructure's node fraction $s^{(i)}_{\\rm sub}=N^{(i)}_{\\rm sub}/N$ acts as a preferential-attachment weight, and the Poisson term is the probability of moving to the next degree. Two thresholds, the maximum degree $d_{\\max}$ and the truncation $k$ (smallest positive integer with $P(k\\mid\\bar{D})