{"id":"3eeac2d8-d8f5-4e2b-aa7b-d795497e0640","arxiv_id":"2608.04255","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"Introduces incremental private multi-hop aggregation so that edge-level differential privacy cost stays constant across arbitrarily many updates to a dynamic graph, plus an LLM branch that adds utility at no extra privacy cost.","lead":"PriDyG combines a privacy-protected graph neural network with a large language model that reads only public node text, so the text branch costs zero privacy budget. Its incremental aggregation touches each new edge once, keeping total differential-privacy cost constant no matter how often the model updates.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.3's 'any retraining schedule' claim requires the schedule to be independent of private edge data; without this stated assumption, a data-dependent retraining policy can break the constant-budget privacy guarantee.","rationale":"The strongest claim is the schedule-independent constant privacy budget. The proof's decomposition into before/at/after m* is valid under a fixed partition of the edge stream into batches that does not depend on the data. The paper does not state this as an assumption; instead Theorem 3.3 and the abstract assert 'any retraining schedule.' This is the point where the central argument is least secure. If a retraining policy can see the private stream, the number, timing, and contents of batches can all depend on the private data; the same neighboring edge can land in different batches or trigger different release counts, and the transcript alignment used in the proof collapses. This is not merely a wording issue about 'external policy': it is the difference between a theorem that holds and one that is false without a data-independence condition. The empirical protocol uses an independent per-insertion coin flip (p=0.5%), so the experiments fall under the data-independent reading and the practical results are not undermined. Other concerns, including the Lemma 3.1 proof statement that P_fus pairs are excluded from all adjacency matrices (contradicted by Section 3.3's treatment of later P_fus edges) and the missing sigma/M reporting for Proposition 3.7, are real but secondary; they do not attack Theorem 3.3 at its core. Hence I agree with the reader's weakest assumption and keep the conditional verdict.","tokens_in":19636,"tokens_out":7066,"duration_ms":70699,"concrete_test":"Formalize an adaptive policy P: at each edge arrival, if the edge is e*={u,v}, trigger an immediate retrain; otherwise do not retrain until a fixed time T. Let D contain e* and let D' be the neighboring graph without e*. Under D, P produces a release at the arrival time of e*; under D', no release occurs until T. The release count before T is therefore 1 under D and 0 under D' with probability 1, so the deterministic function 'number of releases before T' distinguishes the two neighboring graphs with probability 1. This cannot satisfy (eps, delta)-DP for any finite eps and delta < 1, directly refuting the 'any schedule' claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 3.3: incremental PMA is (eps_PMA, delta)-DP for any number of retrains M and any retraining schedule. The proof fixes the unique retrain m* containing the neighboring edge e* and argues that (Y_0,...,Y_{m*-1}) are identically distributed under neighboring graphs, Y_{m*} is one static PMA, and later outputs are post-processing. This only goes through if the batch partition (B_0,...,B_M), including M itself and the retraining times, is the same under the two neighboring graphs. The paper never states this. Section 3.4.2 says only that retraining is 'issued by any external policy,' while Theorem 3.3 and the abstract claim schedule independence. If the policy can observe the edge stream and react (e.g., retrain immediately when a particular sensitive edge arrives, or retrain more often when many edges arrive), then m*, M, and the batch boundaries are functions of the private data. The transcript under D and D' can then have different lengths or timestamps, so the 'before m* identical' step cannot be applied and the privacy loss is not bounded by a single static PMA. As stated, the schedule-independence claim is unsupported and, for data-dependent schedules, false. The fix is to restrict Theorem 3.3 to schedules chosen independently of the private data (as in the experiments, where retraining is triggered by an independent per-insertion coin flip), or to provide an adaptive-composition argument that accounts for data-dependent stopping times and partitions. This is load-bearing because the abstract's headline advantage--updates at zero additional privacy cost--is exactly the 'any schedule' claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper formulates edge-level differentially private dynamic graph inference (EDG) and proposes PriDyG, a two-branch pipeline in which a DP-GNN performs structural learning through incremental private multi-hop aggregation (PMA) while an LLM supplies semantic predictions from node text alone at zero extra privacy cost. The central theoretical claim is Theorem 3.3: because incremental PMA touches each edge exactly once, parallel composition keeps the total privacy cost equal to one static PMA invocation, independent of the number of retrains and of the retraining schedule. The paper also gives a path-capture analysis (one-hop exact, at least half of two-hop transfers retained), a noise-accumulation analysis (linear rather than exponential), and experiments on four benchmarks for node classification and link prediction.","tokens_in":19848,"tokens_out":7048,"duration_ms":68444,"significance":"If the privacy guarantee is stated under the necessary schedule-independence assumption, the constant-budget incremental aggregation is a valuable and clearly presented contribution to continual private graph inference. The LLM branch is well motivated: under edge-level DP with public node text, semantic reasoning from text is genuinely privacy-free, and the confidence-gated fusion gives the system a stable anchor as GNN noise accumulates. The error analysis (Theorem 3.4, Corollaries 3.5 and 3.6, Proposition 3.7) is a useful characterization of the signal/noise trade-off, and the experiments support the utility claims relative to the geometric-decay baseline. However, the headline claim of schedule independence overreaches as stated: Theorem 3.3 requires the retraining schedule to be independent of the private edge stream, and the proof of Lemma 3.1 contains a false assertion about P_fus edges. These are load-bearing issues, but both appear fixable within the manuscript's scope.","major_comments":[{"comment":"The theorem claims edge-level (epsilon_PMA, delta)-DP for 'any retraining schedule,' and the abstract repeats that privacy cost is independent of the schedule. The proof fixes the batch index m* for the neighboring edge e* and requires the batch partition (B_0,...,B_M), including M itself, to be identical for the two neighboring graphs. This holds only if the retraining schedule is chosen independently of the private edge stream. Section 3.4.2 says only that retraining is 'issued by any external policy,' which does not state independence. If the policy can observe the stream and react to it (e.g., retrain exactly when a sensitive edge arrives), then m*, M, and the batch boundaries become functions of private data; the 'before m*' outputs need not be identically distributed, transcript lengths can differ, and the privacy loss is not bounded by a single static PMA. The experiments use a data-independent per-insertion coin flip, so the empirical results are consistent with the needed assumption, but the theorem and abstract must be restricted to this case unless a new adaptive-composition argument is supplied.","section":"Section 3.5, Theorem 3.3; Section 3.4.2"},{"comment":"The proof of Lemma 3.1 states that when e* lies in P_fus, the PMA transcript is identically distributed under the neighboring graphs because 'the pair is excluded from all adjacency matrices.' This contradicts Section 3.3, which explicitly says that a P_fus pair that becomes an edge at some t>0 is processed by incremental PMA. For such an edge, the randomized-response bit at t=0 is identically distributed (the edge is absent at t=0 in both graphs), but the edge is later touched by incremental PMA, so the PMA transcript is not identically distributed. The claimed max(epsilon_PMA, epsilon_RR) joint guarantee may still be salvageable with a case split on whether e* is present at t=0 or arrives later, but the proof as written has a false assertion and must be corrected.","section":"Appendix A, proof of Lemma 3.1; Section 3.3"}],"minor_comments":[{"comment":"The word 'substaintial' in the second challenge paragraph should be 'substantial.'","section":"Section 1"},{"comment":"The indicator notation uses '⊮' in place of the standard blackboard-bold 1 (\\mathbb{1}); the symbol appears to be a rendering error and should be fixed.","section":"Section 3.3, Eq. (5)"},{"comment":"The sentence 'PriDyG attains utility with non-private baselines' is missing a word; it should read 'attains utility comparable to non-private baselines' or similar.","section":"Conclusion"},{"comment":"The prompt contains the ungrammatical phrase 'are likely to are frequently co-purchased together'; it should be 'are likely to be frequently co-purchased together.'","section":"Appendix B, link prediction prompt for co-purchasing"},{"comment":"The reference format line still contains the placeholder 'Conference acronym ’XX' and the ACM copyright year 2018; these template artifacts should be cleaned before the final version.","section":"Title page and templates"}],"recommendation":"major_revision","confidential_remarks":"The two proof issues identified in the major comments are local and fixable: Theorem 3.3 needs an explicit schedule-independence assumption (matching the experimental protocol), and Lemma 3.1 needs a corrected case split for later-arriving P_fus edges. I do not see grounds for rejection, but the paper should not be accepted while the abstract and theorem claim 'any retraining schedule' and the calibration proof contains a contradiction."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, read PriDyG. The headline: the paper has a genuinely clever idea—incremental PMA—that gives a constant total privacy budget for dynamic GNN retraining under edge-level DP, and the LLM branch is a neat way to add utility at zero budget. But two privacy-accounting issues need fixing before the main claims are solid: the 'any retraining schedule' statement lacks a data-independence assumption, and the Lemma 3.1 proof misstates the P_fus handling, so the joint privacy guarantee for link prediction is not established as written.\n\nWhat's new: the EDG problem formulation, the incremental aggregation that processes each edge once and uses parallel composition, the captured-path analysis showing one-hop exactness and half of two-hop transfers, and the explicit noise-accumulation comparison against geometric decay. That's a real step forward for dynamic graph privacy. The experiments are thorough across four benchmarks and show the LLM helps most when the GNN is weakest.\n\nThe main soft spots. First, Theorem 3.3 claims independence from the retraining schedule, but the proof fixes the batch m* and requires the batch boundaries and M to be identical under neighboring graphs. That holds only if the schedule is independent of private data. The paper says 'issued by any external policy,' which might be read as data-independent, but the theorem and abstract do not state it. A data-dependent policy (retrain when a sensitive edge arrives) would break the argument. The fix is to restrict the claim or prove adaptive composition.\n\nSecond, and I think more serious: the Lemma 3.1 proof says P_fus pairs are 'excluded from all adjacency matrices,' but Section 3.3 explicitly says a P_fus pair that becomes an edge at t>0 is processed by incremental PMA. So such an edge is touched by both randomized response and PMA, and the parallel-composition argument over disjoint partitions doesn't apply. The joint max guarantee is unproven as written. This needs a real fix, either by composing the two interactions or by excluding P_fus pairs from future PMA and accounting for the loss.\n\nThird, the utility analysis: Proposition 3.7 says noise grows sqrt(M+1) but Table 4 shows tiny drops. Without reporting sigma, M, and signal magnitudes, it's hard to tell whether the noise is actually small or the experiments are cherry-picked. Also missing code, seeds, and hyperparameters (alpha, tau, q).\n\nOverall, this is a paper for the privacy-preserving ML community. The main idea deserves refereeing and likely a place at a strong venue after the privacy proofs are corrected. I'd recommend sending to peer review, with a request for major revision and a careful re-check of the composition arguments.","headline":"Clever constant-budget dynamic GNN privacy, but two composition bugs (schedule independence and P_fus double-touching) need fixing before the claims hold; still worth refereeing.","tokens_in":20525,"tokens_out":3350,"would_cite":true,"duration_ms":28339,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"PriDyG claims that repeated retraining of a privacy-preserving graph model can run at a single, constant differential-privacy cost, regardless of how many updates occur.","keywords":["differential privacy","dynamic graphs","edge-level privacy","graph neural networks","incremental aggregation","parallel composition","large language models","link prediction"],"falsifier":"Take a two-edge stream with a policy that retrains immediately whenever a specific sensitive edge appears, and compare the incremental PMA transcript under two neighboring graphs that differ only in that edge; the transcripts have different numbers of released noisy deltas, so a full-transcript privacy audit (for example, computing the hockey-stick divergence over many runs) should exceed the $(\\epsilon_{\\mathrm{PMA}},\\delta)$ predicted by Theorem 3.3 if the schedule-independence assumption is essential.","tokens_in":19299,"feed_emoji":"🔒","tokens_out":4312,"duration_ms":35400,"temperature":0.7,"pith_summary":"The paper tackles a problem in private graph learning: when a graph grows and the model is retrained repeatedly, edge-level differential privacy costs normally add up, making updates expensive. It proposes PriDyG, a pipeline that keeps the total privacy budget constant no matter how many times the model is updated, by buffering new edges, aggregating them once, and adding their contribution to cached private features. A second branch uses an LLM on public node text, which costs no edge-level privacy budget, to compensate for the noise injected into the graph branch. If the central claim is right, frequent model updates on evolving relational data no longer carry a growing privacy price.","feed_headline":"Constant privacy cost across unlimited model updates","feed_subtitle":"Buffered edges processed once let repeated retraining keep edge-level DP loss equal to a single static release.","key_machinery":"The load-bearing object is incremental private multi-hop aggregation (incremental PMA). It caches the noisy per-hop aggregations $\\tilde{Z}^{(k)}$ and normalized features $\\bar{Z}^{(k)}$ of a GAP-style private GNN; at each retrain it builds a delta adjacency $\\Delta A^{(m)}$ from the buffered new edges and updates $\\tilde{Z}^{(k)}_{\\mathrm{new}} = \\tilde{Z}^{(k)}_{\\mathrm{cached}} + \\Delta A^{(m)} \\bar{Z}^{(k-1)}_{\\mathrm{new}} + \\mathcal{N}(0,\\sigma^2 I)$, hop by hop. Because each undirected edge is drained from the buffer exactly once, the mechanism decomposes into disjoint batches, and parallel composition plus the $\\sqrt{2}$ sensitivity of undirected-edge aggregation yield the constant-budget Theorem 3.3. The captured-path analysis (Theorem 3.4) shows the approximation error is structured: a $k$-hop path survives iff its batch indices are non-decreasing in traversal order, so one-hop aggregation is exact and two-hop wedge transfers are at least half retained.","core_discovery":"PriDyG's central claim is that the full output of its incremental private multi-hop aggregation satisfies edge-level $(\\epsilon_{\\mathrm{PMA}},\\delta)$-DP for any number of retrains and any retraining schedule, so the total privacy cost equals that of a single static release (Theorem 3.3). This follows because pre-normalization multi-hop aggregation is linear in the adjacency matrix: each newly arrived edge batch contributes an additive delta to cached noisy aggregations, and since every edge is accessed exactly once, parallel composition bounds the total cost by the maximum, not the sum. The cost is paid in signal: incremental aggregation is signal-exact at one hop, retains at least half of two-hop transfers, and accumulates Gaussian noise variance linearly in the number of retrains, whereas geometrically decaying budget allocation inflates noise exponentially. Experiments on four benchmarks for node classification and link prediction show PriDyG outperforming geometric-decay baselines at the same budget and matching naive per-update retraining while cutting cumulative privacy cost by up to three orders of magnitude.","pith_inferences":["If Theorem 3.3 is read strictly, the constant-budget guarantee depends on the retraining schedule being independent of the private edge stream; an adaptive policy that retrains when a sensitive edge arrives would make batch boundaries data-dependent and could break the parallel-composition argument. The paper does not state this independence assumption explicitly.","A natural testable extension is to stress the claim with an adversarial retraining policy that observes edge arrivals and reacts to them, measuring whether the empirical privacy loss stays at the single-release level.","The same buffered once-only-access idea may extend to edge deletions by treating a deleted edge as a negative delta, though the noise accumulation and path-capture structure would need re-derivation.","The LLM branch's usefulness is predicted to grow as the GNN noise floor rises; a direct experiment would vary the insertion stream length and measure how often the confidence gate routes queries to fusion."],"forward_implications":["The number of retrains $M$ stops multiplying the privacy budget: a model can be refreshed after every edge insertion at the same $(\\epsilon,\\delta)$ as a single static release.","Geometrically decaying budget allocation becomes unnecessary; incremental PMA avoids exponential noise growth while preserving exact one-hop signals and at least half of two-hop information.","LLM predictions from public node text can be fused with private GNN outputs at zero additional edge-level privacy cost, providing a stable semantic anchor as GNN noise accumulates.","Link prediction can stay in post-processing: cosine scoring on privatized representations and randomized-response calibration on a disjoint pair partition keep the end-to-end guarantee at $\\max(\\epsilon_{\\mathrm{PMA}}, \\epsilon_{\\mathrm{RR}})$."],"supporting_citations":[{"why":"Supplies the private multi-hop aggregation (PMA) pipeline and the Rényi accountant that Theorem 3.3 inherits.","marker":"[22]"},{"why":"Parallel composition is the structural tool that bounds total privacy cost by the maximum over disjoint batches.","marker":"[24]"},{"why":"Provides the definition of differential privacy and the composition facts used throughout the analysis.","marker":"[6]"},{"why":"The geometrically decaying budget baseline for continual DP release that incremental PMA is compared against.","marker":"[7]"},{"why":"Rényi differential privacy accountant used to calibrate the Gaussian noise scale to the target epsilon.","marker":"[12]"},{"why":"ProGAP is the stronger static edge-level DP GNN baseline used for comparison in the experiments.","marker":"[21]"},{"why":"Randomized response provides the privatized link-existence labels for fusion calibration in link prediction.","marker":"[30]"}],"fun_headline_variants":["Unlimited retrains, constant edge-DP cost","One privacy bill for endless model updates","Infinite retraining, fixed privacy loss","Buffer edges once, pay privacy once"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The retraining schedule must be independent of the private edge data: the proof fixes the batch in which the neighboring edge appears and requires the batch boundaries to be the same across neighboring graphs, so a policy that reacts to observed edge arrivals is not covered by the theorem as stated.","fun_headline_variants_meta":{"raw":{"variants":["Unlimited retrains, constant edge-DP cost","One privacy bill for endless model updates","Infinite retraining, fixed privacy loss","Buffer edges once, pay privacy once"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000226,"raw_usage":{"total_tokens":1469,"prompt_tokens":950,"completion_tokens":519,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":566,"completion_tokens_details":{"reasoning_tokens":464}},"tokens_in":566,"tokens_out":519,"duration_ms":5089,"temperature":1.0,"reasoning_tokens":464,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T00:09:31.655652+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a two-edge stream with a policy that retrains immediately whenever a specific sensitive edge appears, and compare the incremental PMA transcript under two neighboring graphs that differ only in that edge; the transcripts have different numbers of released noisy deltas, so a full-transcript privacy audit (for example, computing the hockey-stick divergence over many runs) should exceed the $(\\epsilon_{\\mathrm{PMA}},\\delta)$ predicted by Theorem 3.3 if the schedule-independence assumption is essential.","supporting_citations":[{"cited_title":"2023.{GAP}: Differentially private graph neural networks with aggre- gation perturbation","cited_arxiv_id":null,"evidence_quote":"Supplies the private multi-hop aggregation (PMA) pipeline and the Rényi accountant that Theorem 3.3 inherits."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Parallel composition is the structural tool that bounds total privacy cost by the maximum over disjoint batches."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The geometrically decaying budget baseline for continual DP release that incremental PMA is compared against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Rényi differential privacy accountant used to calibrate the Gaussian noise scale to the target epsilon."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"ProGAP is the stronger static edge-level DP GNN baseline used for comparison in the experiments."}],"review_version":1}