{"id":"0ed5e8da-b283-49fc-baad-c1a744564ece","arxiv_id":"1909.00280","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"A differentially private generative model, C-AGM, synthesizes attributed social graphs that preserve community structure, degree distributions, and clustering coefficients better than prior private graph models.","lead":"A new algorithm generates synthetic versions of social networks that keep their community structure while satisfying differential privacy. The authors show it preserves communities better than earlier private graph generators, at some cost in global properties like edge counts.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 5.3's privacy proof for attribute-edge correlations uses Lap(2k/εF) after deriving a 2p sensitivity bound; with k<p in all experiments, the stated ε-DP guarantee does not follow as written.","rationale":"The reader's verdict is REJECT, and I agree that the paper as written does not establish the claimed formal privacy guarantee. The paper has genuine strengths: the community-aware generative model is thoughtfully designed, the non-private CPGM experiments show consistent improvements, and the privacy budget split is clearly stated. However, the weakest link in the central claim is the privacy proof itself. I partially diverge from the reader's formal 'weakest_assumption' field: the m=10,000 assumption in Section 5.1 is explicit, all three datasets satisfy it, and it is better characterized as a stated domain restriction than as an internal error. The k-versus-p mismatch in Section 5.3 is more damaging because it is an unstated inconsistency inside the privacy analysis: the paper's own sensitivity derivation implies a noise scale of 2p/εF, yet the mechanism as written uses 2k/εF, and k<p in every experiment. This makes the claimed ε-DP guarantee unsupported and the 'first community-preserving differentially private method' claim unproven for the version as written. The m=10,000 assumption remains a secondary concern for the general claim, but the k/p error is the concrete false step that should be corrected before any conditional acceptance.","tokens_in":26575,"tokens_out":7682,"duration_ms":77971,"concrete_test":"Re-derive the L1 sensitivity of the Θ_cF release under Definition 2, then instrument the code path for the Petster setting (k=13, p=100, εF=ε/6) and log the actual Laplace scale used. If it is Lap(2k/εF), construct a neighbouring pair by changing one node's attribute vector and compute the exact privacy-loss ratio for a fixed noisy output; a ratio exceeding exp(εF) refutes the paper's DP guarantee. If the scale is Lap(2p/εF), re-run the privacy composition and check whether the experimental entries in Tables 3–5 change materially under the larger noise scale.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that C-AGMDP has a formal differential privacy guarantee (Remark 1). The load-bearing step is the privacy of Θ_cF in Section 5.3. There, the authors state that truncating degrees to p makes the global sensitivity of the attribute-edge correlation counts 2p, but then add Laplace noise with scale 2k/εF instead of 2p/εF. Under Definition 2, neighbouring attributed graphs may differ in the attribute vector of one node v. Changing τ(v) can change the aggregated feature β(τ(v),τ(w)) for each incident edge (v,w); in L1 norm, each such edge contributes at most 2 to the difference of the published count vectors. After degree truncation, the overall sensitivity is therefore ≤2p, not 2k. With p=100 and k=13 (Petster) or k=50 (Facebook/Epinions), the published noise scale is respectively about 7.7 and 2 times too small. A mechanism adding Lap(2k/εF) does not satisfy εF-DP, so the composition in Remark 1 does not certify ε-DP. This is not merely cosmetic: the paper's claim of being the first differentially private community-preserving attributed graph publisher rests on this proof. If the actual implementation uses 2p, the text is a typo, but then the proof and all reported experimental results need to be re-checked against the corrected noise scale. A related internal inconsistency appears in Section 5.4, which calls the triangle-count sensitivity unbounded after stating it is bounded by n−2; the k/p mismatch is the more concrete and consequential false step.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces C-AGM, a community-preserving generative model for attributed graphs, and C-AGMDP, its differentially private variant. The model is designed to preserve community sizes, intra- and inter-community edge densities, per-community attribute distributions, attribute-edge correlations, degree distributions, and clustering coefficients. The authors propose efficient sampling and differentially private parameter estimation, and they evaluate the method on three real-world social networks (Petster, Facebook, Epinions) against two baselines. The central claim is that C-AGMDP is the first differentially private community-preserving method for publishing synthetic attributed graphs with a formal epsilon-DP guarantee.","tokens_in":26833,"tokens_out":18037,"duration_ms":157999,"significance":"If the central claims are upheld after correction, the paper would be a useful contribution to private graph publication: it explicitly targets community structure, which is often destroyed by differential privacy noise, and it demonstrates utility on real social graphs. The modeling and sampling design are thoughtful, and the experimental protocol is generally reasonable. However, the significance is conditional because the load-bearing privacy proof for the attribute-edge correlations contains a substantive error, and the evaluation metric reported as measuring attribute-edge correlations actually measures something different.","major_comments":[{"comment":"The Laplace noise scale for the attribute-edge correlation counts is incompatible with the stated sensitivity bound. In Section 5.3 the authors state that after degree truncation the global sensitivity is 2p, but they add noise drawn from Lap(2k/εF), where k is the number of attributes. Under Definition 2, changing the attribute vector of one node affects each incident edge's aggregated feature, contributing at most 2 to the L1 distance of the published count vectors per edge; with degree at most p the sensitivity is at most 2p, independently of k. With p=100 and k=13 (Petster) or k=50 (Facebook/Epinions), the noise scale used in the text is between 2 and 7.7 times too small. A mechanism adding Lap(2k/εF) does not satisfy εF-differential privacy, so the composition in Remark 1 does not certify ε-DP for C-AGMDP as written. The authors must replace 2k with 2p in the noise scale, or justify a different sensitivity bound, and re-check or re-run the experiments under the corrected scale.","section":"Section 5.3"},{"comment":"The evaluation measure described under the heading 'Distribution of attribute-edge correlations' is not a measure of attribute-edge correlations. The text defines p^C_F and ~p^C_F as distributions of attribute vectors of vertices in community C, with domain W = {0,1}^k, and then sets ρa = maxC H(p^C_F, ~p^C_F). This measures the per-community attribute distribution (property 4 of C-AGM), not the distribution of β(τ(v),τ(w)) over edges (property 5). Consequently, Tables 3-5 and the corresponding discussion in Section 6.3.2 do not actually provide empirical evidence that C-AGMDP preserves attribute-edge correlations. Please correct the definition so that the metric is computed over the aggregated features of edges, or relabel the metric and adjust the claims accordingly.","section":"Section 6.2"},{"comment":"The privacy guarantee for the community partition depends on the assumption that every input graph has at least m = 10,000 edges, which yields ΔQs(C) = 0.0003. This assumption is stated in Section 5.1 but is not carried into the abstract, Remark 1, or the conclusion, where the paper advertises a 'strong formal privacy guarantee.' For input graphs with fewer than 10,000 edges, the true global sensitivity of modularity is larger, and the exponential mechanism as described would not provide εc-differential privacy. Please state this condition prominently wherever the overall guarantee is summarized, or use the worst-case bound with the correspondingly larger noise scale so that the guarantee is unconditional for all graphs.","section":"Section 5.1"}],"minor_comments":[{"comment":"The phrase 'The global sensitivity of each of these sequences is 2(|V|−2), which is unbounded' is self-contradictory: a finite value cannot be unbounded. Presumably the intended meaning is that the sensitivity depends on |V| and can therefore be large; please rephrase.","section":"Section 5.3 and Section 5.4"},{"comment":"The sentence 'Since the global sensitivity of triangle count queries is unbounded' directly contradicts Proposition 3, which just stated the finite bound Δn^{intra}_Δ = maxC(|C|−2). If the sentence refers to the global triangle count (which grows with n), it should be rephrased to avoid the confusion with the intra-community triangle bound.","section":"Section 5.4"},{"comment":"Line 10 of Algorithm 2 reinitializes E' to the empty set after line 3 had assigned E' from SampleEdgeSet, making the initially sampled edge set unused. This appears to be a pseudocode error; either the variable should be renamed or the reset removed.","section":"Algorithm 2"},{"comment":"Line 13 has a missing closing parenthesis in 'E←E∪{ (v1,v 3}' and line 30 lacks a separator between the edge-set update and the subsequent update to μ^{inter}_Δ. Please fix these typos for readability.","section":"Algorithm 4"},{"comment":"There is a duplicated word in the sentence 'where where εF is the privacy budget reserved for this computation'; please remove the second 'where'.","section":"Section 5.3"},{"comment":"The sentence 'we conclude that LSQ(C)(G) ≤ ... and use this value as an upper bound for ΔQ_a(C)' appears to be a typo: the bound is for the combined score Q(C), not for Q_a(C) alone.","section":"Section 5.1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript addresses a relevant problem and the overall modeling framework is sound, but the current version contains a load-bearing error in the privacy proof for attribute-edge correlations and a mismatch between the reported evaluation metric and the claimed property. These issues are fixable within the scope of a major revision: correct the noise scale to 2p/εF, fix the ρa metric definition, and state the m ≥ 10,000 assumption prominently. If the implementation used the incorrect noise scale, the experimental results must be regenerated, which may change the utility conclusions. The novelty claim of being the first such method is plausible and not the reason for the revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real contribution to private attributed graph publishing, but the formal privacy guarantee as written doesn't hold because of an apparent k/p typo in Section 5.3. I'd send it for review, not desk reject — the model is novel and the fix is concrete.\n\nWhat's new and good: C-AGM extends AGM to preserve the number and sizes of communities, intra- and inter-community edge densities, per-community attribute distributions, and attribute-edge correlations, all under a single DP budget. That genuinely fills a gap: Jorgensen et al. preserve clustering but not communities, and DCSBM captures communities but has no DP treatment. The experiments on Petster, Facebook, and Epinions show consistent improvements in Avg-F1 over DCSBM and TriCycle, and the paper is honest about trade-offs in global structural properties. The private modularity-based partition with attribute weighting is a reasonable adaptation of ModDivisive.\n\nWhere it breaks: Section 5.3 states that after truncation the global sensitivity of the attribute-edge correlation counts is 2p, then samples Lap(2k/εF). k is the number of attributes, not the degree bound. In all experiments k < p (13 or 50 vs 100), so the noise is too small by a factor of roughly 2 to 8. As written, the εF-DP claim and therefore the composition in Remark 1 do not follow. I suspect a typo, but it is load-bearing and the text needs correction. If the implementation actually uses 2p, the reported utilities need to be rechecked against the larger noise. Also, the modularity sensitivity relies on assuming m ≥ 10,000; that is an input-domain restriction that should be explicit. Section 5.4 has an odd sentence calling triangle-count sensitivity unbounded right after proving it is bounded by |C|−2; likely wording, but confusing. Minor issues: no error bars, a stray line in Algorithm 2, and some ambiguity in how ρa is computed.\n\nBottom line: the central model is sound in concept and the comparison is useful. I would not accept the current version as a formal DP paper, but I would engage with it — this deserves a real referee, with the main request being a corrected privacy analysis and, if needed, rerun experiments. People working on DP graph synthesis should read it.","headline":"A genuinely new differentially private community-preserving attributed graph model, but the formal privacy claim has a likely load-bearing k/p typo in the noise scale that needs fixing before the paper can be trusted.","tokens_in":27447,"tokens_out":5993,"would_cite":true,"duration_ms":57978,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"C-AGMDP publishes synthetic social graphs under differential privacy while preserving the original community structure.","keywords":["attributed social graphs","differential privacy","synthetic graph generation","community detection","community-preserving graph models","graph generative models","privacy-preserving data publication"],"falsifier":"Generate graphs with fewer than 10,000 edges and a clear community structure, run the private partition mechanism on a graph and on a neighbouring graph that differs by one edge, and compare output distributions: if the probability ratio exceeds $e^{\\varepsilon}$, the assumed sensitivity bound is violated. A simpler calculation check is to compute the true global sensitivity of the modularity score on such graphs and show it is larger than the assumed 0.0003.","tokens_in":1516,"feed_emoji":"🕸️","tokens_out":3568,"duration_ms":125586,"temperature":0.7,"pith_summary":"This paper sets out to establish that a community-preserving synthetic attributed social graph can be published under differential privacy without giving up global graph properties. It claims C-AGMDP is the first such method: it preserves the number and sizes of communities, intra- and inter-community edge densities, per-community attribute distributions, and attribute-edge correlations, while still approximating degree distributions and clustering coefficients. The payoff is that analysts can run community-sensitive tasks on synthetic graphs that carry a formal privacy guarantee.","feed_headline":"Method publishes private social graphs that keep communities intact","feed_subtitle":"Synthetic graphs from C-AGM preserve community sizes, ties, and attributes under one ε-differential-privacy budget.","key_machinery":"The load-bearing object is the C-AGM model, a quintuple $\\langle V, C, \\Theta_M, \\Theta_X, \\Theta_F \\rangle$ that factors graph generation into a community-respecting edge model (CPGM), a per-community attribute-vector model, and a model of attribute-edge correlations. The argument is carried by four mechanisms: a differentially private community partition obtained from a weighted combination of structural modularity and an attribute-similarity graph; sensitivity bounds, set under the paper's assumption that every input graph has at least 10,000 edges, that determine the Laplace noise scales; ladder-function-based private triangle counts; and a post-processing pipeline that restores graphicality and degree order after noise. Together these turn parameter estimation into a sequence of private computations whose outputs are safe to publish.","core_discovery":"The central claim is that C-AGM, a generative model built on an earlier attributed graph model, can capture community structure explicitly: given a community partition, the model records community sizes, edge counts inside and between communities, attribute distributions within each community, and how attribute similarity correlates with edges inside versus across communities. A companion edge generator, CPGM, first samples edges using intra- and inter-community degree products and then edits the edge set to match triangle counts, which carries degree sequences and clustering coefficients along with it. The paper further claims that the whole parameter-estimation pipeline can be made $\\varepsilon$-differentially private by composition, using a modularity-plus-attribute scoring function for the partition, Laplace noise with graphicality post-processing for degree counts, and ladder functions for triangle counts. Experiments on three real social networks support the claim that C-AGMDP synthetic graphs preserve community structure better than earlier private graph models without sacrificing global structural properties.","pith_inferences":["The paper leaves implicit that a natural extension would allow overlapping communities, since the current model assumes a partition and buckets unassigned vertices into a discard community.","The attribute-independence assumption inside each community means correlations among attributes are not modelled; capturing pairwise attribute marginals would be a direct next step, at the price of higher sensitivity and more noise.","The 10,000-edge sensitivity assumption suggests a data-dependent or smooth-sensitivity formulation could extend the guarantee to smaller networks, a route the paper itself opens when it flags the assumption.","If the approach scales, community-preserving private synthetic graphs could serve as a neutral benchmark for comparing community-detection algorithms under a known privacy budget without exposing the original graph."],"forward_implications":["Because the model parameters are estimated once under a fixed privacy budget, any number of synthetic graphs can then be sampled without additional privacy cost.","Analysts can run community-sensitive tasks, such as recommendation or influence studies, on synthetic graphs that carry $\\varepsilon$-differential privacy rather than on the original data.","Published graphs keep the same vertex set, but edges and attribute vectors are freshly sampled, so individual relationships and user features are not reproduced verbatim.","On the three real networks tested, the private model preserves community structure substantially better than the private baselines, while degree distributions and clustering coefficients remain comparable."],"supporting_citations":[{"why":"Introduces the attributed graph generative formalism whose parameterisation C-AGM extends with community-level statistics.","marker":"[11]"},{"why":"Defines the neighbouring-attributed-graph privacy model and the differentially private parameter-estimation strategy that C-AGMDP adapts.","marker":"[12]"},{"why":"Supplies the modularity-based differentially private community partition whose sensitivity bound is reused and extended to an attribute-augmented score.","marker":"[32]"},{"why":"Provides ladder-function mechanisms used to privately count triangles, including the local-sensitivity-at-distance characterisation for intra-community triangles.","marker":"[43]"},{"why":"Gives the post-processing that restores graphicality of noisy degree sequences, a step required for CPGM parameters.","marker":"[16]"},{"why":"Provides the degree-ordering post-processing and degree-distribution estimation used after Laplace perturbation.","marker":"[9]"},{"why":"Introduces restricted sensitivity via degree truncation, which the paper uses to bound the global sensitivity of attribute-edge correlation counts.","marker":"[3]"}],"fun_headline_variants":["Private synthetic graphs that preserve community structure","Differential privacy without sacrificing community ties","Community-preserving synthetic graphs under DP","Publishing private social graphs: communities intact"],"cache_read_input_tokens":29440,"weakest_assumption_plain":"The privacy guarantee rests on the assumption that every input graph has at least 10,000 edges, which sets the modularity score's sensitivity to 0.0003; if a graph has fewer edges, that bound is wrong and the published partition may not meet differential privacy.","fun_headline_variants_meta":{"raw":{"variants":["Private synthetic graphs that preserve community structure","Differential privacy without sacrificing community ties","Community-preserving synthetic graphs under DP","Publishing private social graphs: communities intact"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000566,"raw_usage":{"total_tokens":2638,"prompt_tokens":856,"completion_tokens":1782,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":472,"completion_tokens_details":{"reasoning_tokens":1730}},"tokens_in":472,"tokens_out":1782,"duration_ms":13783,"temperature":1.0,"reasoning_tokens":1730,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:57:42.570525+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Generate graphs with fewer than 10,000 edges and a clear community structure, run the private partition mechanism on a graph and on a neighbouring graph that differs by one edge, and compare output distributions: if the probability ratio exceeds $e^{\\varepsilon}$, the assumed sensitivity bound is violated. A simpler calculation check is to compute the true global sensitivity of the modularity score on such graphs and show it is larger than the assumed 0.0003.","supporting_citations":[{"cited_title":"Pfeiffer III, Sebasti´ an Moreno, Timothy La Fond, Jennifer Neville, and Brian Gallagher","cited_arxiv_id":null,"evidence_quote":"Introduces the attributed graph generative formalism whose parameterisation C-AGM extends with community-level statistics."},{"cited_title":"Publishing attributed social graphs with formal privacy guarantees","cited_arxiv_id":null,"evidence_quote":"Defines the neighbouring-attributed-graph privacy model and the differentially private parameter-estimation strategy that C-AGMDP adapts."},{"cited_title":"Nguyen, Abdessamad Imine, and Micha¨ el Rusinowitch","cited_arxiv_id":null,"evidence_quote":"Supplies the modularity-based differentially private community partition whose sensitivity bound is reused and extended to an attribute-augmented score."},{"cited_title":"Procopiuc, Divesh Srivastava, and Xiaokui Xiao","cited_arxiv_id":null,"evidence_quote":"Provides ladder-function mechanisms used to privately count triangles, including the local-sensitivity-at-distance characterisation for intra-community triangles."},{"cited_title":"Slavkovic","cited_arxiv_id":null,"evidence_quote":"Gives the post-processing that restores graphicality of noisy degree sequences, a step required for CPGM parameters."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the degree-ordering post-processing and degree-distribution estimation used after Laplace perturbation."},{"cited_title":"Differentially private data analysis of social networks via restricted sensitivity","cited_arxiv_id":null,"evidence_quote":"Introduces restricted sensitivity via degree truncation, which the paper uses to bound the global sensitivity of attribute-edge correlation counts."}],"review_version":1}