{"id":"448e5e0c-828d-48b4-bcdd-e55f9ff66242","arxiv_id":"2501.02354","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":8,"one_line_summary":"PrivDPR generates synthetic graphs under node-level DP by adding Gaussian noise only to the gradient of a node embedding in a deep PageRank model, with depth used to control sensitivity.","lead":"PrivDPR is a method for publishing synthetic graphs under node-level differential privacy, built on a deep PageRank model whose per-edge gradient norms are bounded by spectral normalization. The paper claims that increasing the number of layers makes the required privacy noise easier to tune, and reports utility gains over prior private graph generators.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Privacy proof omits factor of 2 in batch-gradient sensitivity under bounded node DP, so the stated S∇ does not yield the claimed (ε,δ) guarantee.","rationale":"The reader's weakest assumption is the unproven surrogate objective, but the most load-bearing concern is the privacy proof itself: Theorem 5.1's (ε,δ) guarantee depends on the sensitivity bound in Theorem 4.2, which misses a factor of 2 under bounded node DP. This is a concrete, checkable algebraic error, not a debatable modeling choice. The surrogate-objective gap affects utility and is explicitly deferred; the sensitivity error affects the central privacy claim and, if uncorrected, invalidates the headline contribution. The reader's rationale already lists this as reason (1), so the verdict CONDITIONAL remains appropriate: the flaw is fixable by doubling the sensitivity (or adding one layer), and the qualitative claim that depth mitigates sensitivity survives. I recommend keeping the conditional verdict until the authors correct the sensitivity analysis and re-verify the layer-count settings.","tokens_in":22141,"tokens_out":14422,"duration_ms":149645,"concrete_test":"Re-derive Eq. (11) under bounded node DP, accounting for gradients from both neighboring graphs, to replace B·M(1/s)^{L+1} ≤ S∇ with 2B·M(1/s)^{L+1} ≤ S∇ (equivalently B·M(1/s)^{L+1} ≤ S∇/2). Then check Example 4.5: with N=3327, γ=0.85, M≈10464, B=128, S∇=5, s=5, Eq. (12) forces L≥8 instead of L≥7. If the published experiments use L=7 as permitted by the paper's inequality, those settings do not provide the asserted (ε,δ)-DP guarantee; the layer count must be increased or S∇ doubled.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 5.1 claims (ε,δ)-node-level DP by splitting the budget across iterations and adding Gaussian noise calibrated to a sensitivity S∇. In Theorem 4.2, the paper bounds each per-edge gradient in Eq. (7) by ρ = M(1/s)^{L+1} and then sets S∇ ≥ Bρ, asserting that the worst-case sum of B affected gradients has ℓ2-norm at most Bρ (Eq. (11)). Under bounded node DP, two neighboring graphs G and G' both contribute gradients to the difference: for each edge in the batch, the gradient in G and the gradient in G' each have norm at most ρ, so the difference per edge is at most 2ρ, and the sensitivity of the sum over B edges is at most 2Bρ. The proof uses Bρ instead, underestimating sensitivity by exactly a factor of 2. Consequently the noise scale in Theorem 5.1 is too small for the stated privacy budget. This is an internal inconsistency in the proof, not a matter of consensus: even if the batch were fixed, replacing a node changes the gradients, and the triangle inequality forces the 2 factor. The error is fixable (e.g., require Bρ ≤ S∇/2, or increase L by one), but as written the central privacy claim is not established.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"PrivDPR proposes a node-level differentially private synthetic graph publishing method based on a deep PageRank objective. The algorithm learns a node embedding matrix V by adding Gaussian noise to the gradient of V during training, while using weight normalization to bound the per-edge gradient norm by M(1/s)^{L+1}. The paper's central theoretical claims are that increasing the number of network layers can meet any preset sensitivity S∇ and mitigate privacy budget splitting, and that the final synthetic graph satisfies (ε,δ)-node-level DP. The empirical section compares PrivDPR with GAP, DPGGAN, DPGVAE, and a non-private variant on five datasets across eight structural metrics and two downstream tasks.","tokens_in":22382,"tokens_out":26629,"duration_ms":270255,"significance":"If the privacy proof were fully correct, the depth-versus-sensitivity trade-off would be a useful addition to the DP graph synthesis toolbox, and the paper's explicit targeting of node-level DP (rather than the weaker edge-level DP) is valuable. The manuscript is clearly written, the experiments are broad, and the authors provide a public code repository. However, the load-bearing privacy analysis contains a factor-of-2 sensitivity error, the data-dependent random-walk batch construction is not accounted for in the proof, and the absolute utility numbers are modest; the current version therefore does not yet substantiate the claimed privacy guarantee or the abstract's 'high data utility' statement.","major_comments":[{"comment":"The sensitivity of the batch gradient sum is underestimated by a factor of 2. Theorem 4.2 gives ||∂L(vi,vj;Θ)/∂V||_2 ≤ ρ = M(1/s)^{L+1} for each edge, and Eq. (11) sets Bρ ≤ S∇ by claiming that the worst-case norm of the sum over B affected gradients is at most Bρ. Under the bounded node DP adopted in Definition 3, two neighboring graphs both contribute B edges to the batch: for each edge, the gradient in G and the gradient in G′ each have norm at most ρ, so by the triangle inequality the per-edge difference is at most 2ρ and the sensitivity of the sum is at most 2Bρ, not Bρ. Consequently, the Gaussian noise in Theorem 5.1 is scaled too small for the stated (ε,δ)-node-level DP guarantee. The error is fixable by requiring S∇ ≥ 2Bρ (or increasing L by one layer), but as written the central privacy claim is not established.","section":"Sec. 4.3.1, Eq. (11); Sec. 5.1, Theorem 5.1"},{"comment":"The privacy proof does not account for the data-dependent random-walk batch construction. In Algorithm 2, the batch E_B is generated by performing random walks on the input graph (lines 5–7), so the distribution over batches is itself a function of the private graph. Theorem 5.1 only analyzes the Gaussian mechanism for a fixed batch, i.e., it shows that the noisy sum of gradients is DP conditioned on a batch. However, a mixture of DP mechanisms with data-dependent mixture weights is not necessarily DP. To complete the proof, the authors need either to make the batch selection data-independent or to bound the privacy loss of the random-walk sampling itself, for example by a subsampling argument with data-independent probabilities. Without this, the per-iteration DP claim and the composition argument in Theorem 5.1 are not fully justified.","section":"Sec. 5.1, Theorem 5.1; Algorithm 2, lines 4–7"},{"comment":"The approximation ratio of the surrogate objective is left open. The paper minimizes the edge-wise upper bound L(vi,vj) from Lemma 4.1 in place of the PageRank objective in Eq. (3), and it explicitly states that the proof of the approximation ratio is 'currently a subject for future research'. If this upper bound is loose or does not preserve the minimizer structure of PageRank, then the learned embedding V may not reflect the PageRank properties that motivate the method. The DP guarantee is independent of this issue, but the utility claim and the name 'deep PageRank' depend on it. The authors should either provide a bound on the approximation ratio or clearly qualify the theoretical connection to PageRank.","section":"Sec. 4.2, Lemma 4.1 and following paragraph"},{"comment":"The reported utilities appear too low to support the abstract's claim of 'high data utility'. For example, the mean relative error for triangle count is around 0.99 across all datasets in Tables 2 and 3, the KS distance on Cora and Citeseer is around 0.5–0.6, and the link-prediction AUC of PrivDPR is only about 0.50–0.60 in Tables 4 and 5, which is close to random guessing. While PrivDPR often outperforms the baselines, the absolute numbers suggest that the synthetic graphs preserve only weak structural fidelity. The utility claims should be reworded, and the discussion should address why the absolute errors are this large.","section":"Sec. 6, Tables 2–5 and Figure 2"}],"minor_comments":[{"comment":"The sentence 'For a fair comparison, we configure GAP to generate synthetic graphs using the same generation method as PrivDPR' is duplicated in Section 6; please remove the duplicate.","section":"Sec. 6, Baselines"},{"comment":"The phrase 'maximum number of layers' should be 'minimum number of layers', since the inequality provides a lower bound on L for a preset sensitivity S∇.","section":"Theorem 4.2"},{"comment":"The text says 'we evenly divide privacy parameters ε and σ'; this should likely read 'ε and δ', since σ is computed from ε/T and δ/T via the Gaussian mechanism.","section":"Sec. 4.3.2"},{"comment":"The typesetting of Eq. (3) is difficult to parse; please display the PageRank objective with unambiguous parentheses and define all terms, for example the placement of (1−γ)/N inside the outer parentheses.","section":"Eq. (3)"},{"comment":"Algorithm 2 says 'Sample graphs from VV^T to generate score matrix S', but the reconstruction procedure in Appendix A builds a transition count matrix from random walks over the learned embeddings; please reconcile the description so that the reader can reproduce the reconstruction.","section":"Algorithm 2, line 12 and Appendix A"},{"comment":"The batch size is denoted ♭ in Algorithm 2 but B in Eqs. (6)–(7) and Theorem 4.2; please use a consistent symbol.","section":"Notation throughout"},{"comment":"The non-private baseline DPR (No DP) is described in Section 6 but does not appear in the link prediction or node classification tables; please either include it or state why it is omitted.","section":"Sec. 6.3 and Tables 4–5"}],"recommendation":"major_revision","confidential_remarks":"The paper has a promising idea and is generally clearly written, and the authors provide code. However, the central privacy proof has a factor-of-2 sensitivity error and a gap concerning the data-dependent random-walk batch construction. Both need to be fixed before the node-level DP claim can be accepted. The unproven approximation ratio of the surrogate objective and the modest absolute utility numbers should also be addressed in revision. I recommend major revision rather than reject because the issues are potentially fixable within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the core idea is real. Using weight normalization to get a per-edge gradient bound that decays as (1/s)^(L+1), then increasing depth to hit any preset sensitivity, is a genuinely new trick in DP graph synthesis. It lets them avoid advanced composition and get a node-level guarantee without clipping. That is a contribution worth arguing about.\n\nWhat the paper does well: Theorem 4.2 is a real bound, the privacy analysis is written in an auditable way, the experiments cover five datasets and both link prediction and node classification, and the code is public. The paper is honest about the approximation ratio of the surrogate objective, which is more than many papers do.\n\nNow the soft spots. The stress-test is right: under bounded node DP, replacing a node changes gradients in both G and G'. The per-edge bound rho = M(1/s)^(L+1) applies to each gradient separately, so the difference per edge is 2rho, and the batch sensitivity is 2B*rho, not B*rho. Eq. (11) undercounts by exactly a factor of 2. This makes Theorem 5.1's stated (epsilon, delta) guarantee unproven as written. It is fixable—set S∇ >= 2B*rho or add one layer, and the whole architecture still stands—but it is a load-bearing gap.\n\nThe second issue is the surrogate objective. Lemma 4.1 upper-bounds the PageRank loss, and the text says the approximation ratio is future work. That means the method's claim to preserve PageRank structure is currently empirical only. I can live with that if the experiments are strong, but they are not as strong as the prose suggests. Triangle count MRE is about 0.99 on every dataset, which means the synthetic graphs do not preserve triangles at all; 'high utility' is doing too much work. The main utility figures have no error bars, and hyperparameters like s, d, and S∇ are tuned on the same datasets. Those are fixable reporting issues.\n\nWho is this for? People working on DP graph generation and private learning on graphs. It is a worthwhile paper to referee seriously, not a desk reject. I would send it out, with a clear expectation of a corrected sensitivity analysis, a caveat on the objective gap, and a more honest utility summary.","headline":"Interesting and fixable: the depth-sensitivity mechanism is real, but the privacy proof has a factor-of-2 gap and the utility claims outrun the evidence.","tokens_in":22975,"tokens_out":2279,"would_cite":false,"duration_ms":22709,"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":"This paper claims that a deep PageRank network with weight-normalized layers can synthesize graphs under node-level differential privacy by trading network depth for privacy noise.","keywords":["differential privacy","synthetic graph publishing","PageRank","node-level privacy","gradient perturbation","weight normalization","graph synthesis"],"falsifier":"Take a fixed graph, fix $s$ and the batch size, train PrivDPR with $L$ chosen from Eq. (12), and measure the empirical $\\ell_2$ norm of the gradient of the edge-wise loss with respect to $V$ over training; if it does not stay at or below the preset $S_\\nabla$, the sensitivity bound in Theorem 4.2 is false. Alternatively, compute the PageRank vectors of the published graph and of the input graph; if their Spearman correlation is near zero while the training loss has converged, the surrogate objective is not preserving the structure the method claims.","tokens_in":21870,"feed_emoji":"🔐","tokens_out":4718,"duration_ms":46188,"temperature":0.7,"pith_summary":"This paper proposes PrivDPR, a method for publishing synthetic graphs under node-level differential privacy. Instead of clipping and noising every gradient, PrivDPR adds Gaussian noise only to the gradient of the node embedding matrix in a deep PageRank network, and uses weight normalization to bound that gradient. The bounding argument shows the gradient norm falls as $(1/s)^{L+1}$ with the number of layers $L$, so the desired sensitivity can be preset and extra layers absorb the cost of splitting the privacy budget across iterations. The paper proves that the released graph satisfies $(\\varepsilon,\\delta)$-node-level DP and reports experiments where its structural utility stays competitive even at $\\varepsilon = 0.1$.","feed_headline":"Depth lowers DP noise in synthetic graph publishing","feed_subtitle":"PrivDPR proves node-level differential privacy by growing network depth instead of shrinking the privacy budget.","key_machinery":"The central objects are the deep PageRank objective and the Cauchy-Schwarz upper bound $\\mathcal{L}(v_i,v_j;\\Theta)$ from Lemma 4.1, which replaces the non-decomposable PageRank loss with an edge-wise training loss. Weight normalization $W/(\\|sW\\|_2)$ with $s>1$ is the mechanism that makes each layer shrink the gradient bound by a factor $1/s$, so the full bound $M(1/s)^{L+1}$ follows from the chain-rule/Lipschitz estimate of the network. The layer count $L$ is then chosen from the log-inequality $\\log\\left(\\frac{S_\\nabla}{BM}\\right)/\\log\\left(\\frac{1}{s}\\right)-1 \\le L$, turning network depth into the privacy knob.","core_discovery":"At the center of the paper is Theorem 4.2, which bounds the $\\ell_2$ norm of $\\partial \\mathcal{L}(v_i,v_j;\\Theta)/\\partial V$ by $M(1/s)^{L+1}$ for a weight-normalized deep PageRank with normalization $W/\\|sW\\|_2$ and sigmoid activations. Choosing the number of layers according to $\\log\\left(\\frac{S_\\nabla}{BM}\\right)/\\log\\left(\\frac{1}{s}\\right)-1 \\le L$ therefore makes the batch gradient's sensitivity at most the preset value $S_\\nabla$, and the same inequality with $S_\\nabla$ replaced by $S_\\nabla/T$ counters the noise increase from splitting $\\varepsilon$ across $T$ gradient updates. Theorem 5.1 then assembles node-level DP from the per-iteration Gaussian mechanism, sequential composition, and post-processing. The paper's claim is that this depth-for-privacy trade-off, not a stronger composition calculus, is what lets a private deep graph generator work under small privacy budgets.","pith_inferences":["The privacy theorem only guarantees that the released node embedding matrix is close in distribution; whether that embedding captures PageRank structure rests on the unproven approximation ratio of the upper-bound loss, so a natural test is to compare node rankings from the synthetic graph with true PageRank values.","The exponential drop $(1/s)^{L+1}$ suggests the gradient can vanish for large $L$; the method may inherit vanishing-gradient behavior and need residual connections or skip layers, which the paper does not discuss.","One could apply the same weight-normalization-and-depth argument to other random-walk embedding objectives, not just PageRank, to obtain node-level DP for embeddings more generally."],"forward_implications":["Node-level synthetic graph release with $(\\varepsilon,\\delta)$-DP is achievable at privacy budgets as small as $\\varepsilon=0.1$ without moments accountant style composition.","Adding hidden layers lowers the required Gaussian noise, so a user can preset a target sensitivity and size the network accordingly.","Because DP is preserved under post-processing, the published graph can feed arbitrary downstream queries without extra privacy cost.","The training loop runs in time linear in the number of nodes for fixed batch and walk parameters, so the method is claimed to scale to large graphs."],"supporting_citations":[{"why":"Supplies the sequential composition and post-processing theorems used to assemble node-level DP in Theorem 5.1.","marker":"[8]"},{"why":"Supplies the sensitivity definition and Gaussian mechanism used to privatize the gradient of the embedding matrix.","marker":"[7]"},{"why":"Supplies the PageRank random-walk and damping model behind the deep PageRank objective in Eq. (3).","marker":"[28]"},{"why":"Supplies the DP-SGD clipping and noise recipe that PrivDPR modifies, and the moments accountant baseline it avoids.","marker":"[1]"},{"why":"Provides the node-level private GNN baseline (GAP) whose synthetic-graph setup PrivDPR compares against.","marker":"[32]"},{"why":"Provides the DPGGAN and DPGVAE edge-level-DP baselines and the preset sensitivity value $S_\\nabla = 5$ used in PrivDPR.","marker":"[43]"}],"fun_headline_variants":["PrivDPR: deeper PageRank for smaller privacy budgets","Depth beats composition for node-level DP in graphs","Grow layers to cut DP noise in synthetic graphs","PageRank depth as privacy shield: PrivDPR","More depth, less noise: PrivDPR's DP trick"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The training minimizes an upper-bound surrogate for the PageRank objective, and the paper explicitly says the proof that this bound approximates the objective is future work; if that surrogate does not preserve PageRank structure, the synthetic graph's utility claim fails even though the DP guarantee may hold.","fun_headline_variants_meta":{"raw":{"variants":["PrivDPR: deeper PageRank for smaller privacy budgets","Depth beats composition for node-level DP in graphs","Grow layers to cut DP noise in synthetic graphs","PageRank depth as privacy shield: PrivDPR","More depth, less noise: PrivDPR's DP trick"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00067,"raw_usage":{"total_tokens":3056,"prompt_tokens":953,"completion_tokens":2103,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":569,"completion_tokens_details":{"reasoning_tokens":2024}},"tokens_in":569,"tokens_out":2103,"duration_ms":15990,"temperature":1.0,"reasoning_tokens":2024,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:16:30.374951+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a fixed graph, fix $s$ and the batch size, train PrivDPR with $L$ chosen from Eq. (12), and measure the empirical $\\ell_2$ norm of the gradient of the edge-wise loss with respect to $V$ over training; if it does not stay at or below the preset $S_\\nabla$, the sensitivity bound in Theorem 4.2 is false. Alternatively, compute the PageRank vectors of the published graph and of the input graph; if their Spearman correlation is near zero while the training loss has converged, the surrogate objective is not preserving the structure the method claims.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the sequential composition and post-processing theorems used to assemble node-level DP in Theorem 5.1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the sensitivity definition and Gaussian mechanism used to privatize the gradient of the embedding matrix."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the PageRank random-walk and damping model behind the deep PageRank objective in Eq. (3)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the DP-SGD clipping and noise recipe that PrivDPR modifies, and the moments accountant baseline it avoids."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the node-level private GNN baseline (GAP) whose synthetic-graph setup PrivDPR compares against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the DPGGAN and DPGVAE edge-level-DP baselines and the preset sensitivity value $S_\\nabla = 5$ used in PrivDPR."}],"review_version":1}