{"id":"99c8267e-1c2b-4c0e-b06a-829c189bbbaf","arxiv_id":"2507.01873","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A polynomial-time differentially private algorithm approximates every cut in a graph within (1+γ) multiplicative and n^{1.25+o(1)} additive error, breaking the previous n^{1.5} barrier.","lead":"This paper gives a polynomial-time differentially private algorithm that approximates all graph cuts with multiplicative error (1+γ) and additive error roughly n^{1.25}, improving on the previous n^{1.5} barrier. The key idea is a new private expander decomposition that splits the graph into dense expanders and sparse leftover edges, each handled by a different privacy mechanism.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The privacy analysis of the recursive expander decomposition relies on an unproven recursion-depth bound from [NS17] and an informal data-dependent composition argument, and if either fails the central DP guarantee collapses.","rationale":"I read the paper in good faith. The main error analysis (Section 3.3) is sound: the expander decomposition's inter-component weight ψ·n^{1+o(1)} and the expander property ψ lower bound correctly balance the EKKL20 and UUA21 errors, yielding n^{1.25+o(1)}. The parameter choices are consistent. The only substantive weakness is the privacy analysis of the recursive expander decomposition: the depth bound from [NS17] is asserted without proof for weighted graphs, and the composition argument is a sketch. I attempted to construct a counterexample to the depth bound (e.g., an edgeless graph) but the second guarantee of Theorem 4.2 forces the oracle to return a large cut when large sparse cuts exist, so the bound appears plausible. The concern is therefore a rigor gap, not a demonstrated falsehood. It is load-bearing because Theorem 1.1 inherits its privacy from Theorem 3.1. The reader's verdict of CONDITIONAL is appropriate; I recommend no change.","tokens_in":16173,"tokens_out":45184,"duration_ms":469964,"concrete_test":"Prove by induction on recursion depth that Algorithm 2 is (D·ε', D·δ')-DP: fix an arbitrary output S of the first A-call, condition on it, and show the two recursive calls are parallel (disjoint vertex sets) and the edge difference lies in at most one child; then re-derive the [NS17] depth bound for weighted graphs, confirming the second guarantee of Theorem 4.2 gives size progress s_{ℓ+1}·c_size^{-1}. As a computational sanity check, run Algorithm 2 with an oracle implementing Theorem 4.2's guarantees (using [LS21] on the clamped private graph) on inputs such as a perfect matching with n/2 isolated vertices; verify the recursion depth never exceeds D. If any run exceeds D, Theorem 3.1's DP claim fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4 proves Theorem 3.1's privacy by asserting (i) Lemma 4.4, that Algorithm 2 has recursion depth at most D = L·c_size·n^σ·log n = n^{o(1)} (credited to [NS17], with the proof not reproduced), and (ii) that an edge difference e affects at most one A-call per recursion level, so the per-call budget ε' = ε/D composes to ε over the affected path. Both steps are load-bearing: if the depth bound is false, the privacy budget is exceeded; if the composition is invalid, the recursion may leak via data-dependent subproblem shapes. The paper does not show how the vertex sets of recursive subproblems, themselves outputs of private cut-finding, are handled in the neighboring-graph coupling, nor how [NS17]'s vertex-count depth argument extends to arbitrary non-negative weights. These are asserted, not proved, in the text immediately before Lemma 4.3. Since Algorithm 1's overall (ε,δ)-DP guarantee composes Theorem 3.1 with two further private mechanisms, any gap in Theorem 3.1's privacy propagates to the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes the first polynomial-time differentially private algorithm for releasing a sparse synthetic graph that approximates all cuts with multiplicative error 1+γ and additive error n^{1.25+o(1)} polylog(1/δ)/(ε γ^{0.5}), breaking the longstanding n^{1.5} additive-error barrier for efficient private cut sparsification. The main technical ingredient is a private expander-decomposition algorithm (Theorem 3.1), obtained by combining a private approximate balanced-cut oracle (Theorem 4.2, built from [UUA21] and [LS21]) with the recursive expander-decomposition framework of [NS17]. The private synthetic graph is then formed by treating inter-component edges and intra-component expanders separately, using [EKKL20] and [UUA21] respectively, and post-processing with a standard non-private cut sparsifier yields the sparse output. The paper also gives applications to private max-cut, max-bisection, max-k-cut, and minimum-bisection with improved additive error.","tokens_in":16396,"tokens_out":7790,"duration_ms":110877,"significance":"If the main theorem holds, this is a substantial advance: it resolves, in a strong sense, the prominent open problem of beating O(n^{1.5}) additive error for polynomial-time private cut sparsification when multiplicative error is allowed. The high-level decomposition into sparse and dense parts is natural and the additive-error accounting in Section 3.3 is clean and correct given the private expander decomposition. The private expander decomposition itself is a potentially reusable primitive. The paper also gives credit where due by building on prior DP algorithms as black boxes. The main weakness is that the privacy proofs for the recursive decomposition are informal at load-bearing points; these need to be made rigorous before the central claim is fully established.","major_comments":[{"comment":"The privacy analysis of Algorithm 1 assumes that the partition V_1,...,V_k produced by Theorem 3.1 is the same for two neighboring graphs. This is not justified: the partition is a randomized, data-dependent output of a private mechanism, and there is no coupling in the text that makes the two partitions coincide. A correct proof needs either an explicit coupling or a composition argument that first releases the partition with its own privacy budget and then argues that, for every fixed partition, the collection of subsequent invocations of Theorem 2.2 is private under parallel composition. As written, the claim that 'at most three invocations' consume privacy budget does not establish (ε,δ)-DP for Algorithm 1, because the adversary observes which subproblems are created and those subproblems depend on the private partition.","section":"Section 3.1"},{"comment":"The argument 'when Algorithm 2 recurses, the edge e affects at most one of the recursive calls' is a statement about a single execution. In a privacy proof, the recursive subproblems A(H,ψ) are themselves outputs of private computations, so the set of subproblems and their vertex sets can differ between neighboring graphs. The text then concludes that Algorithm 2 is (ε,δ)-DP by basic composition over at most D = L·c_size·n^σ·log n affected calls, but all n^{1+o(1)} recursive-call outputs are released. A formal composition theorem for data-dependent recursive partitioning is needed; simply multiplying the per-call privacy budget by the depth bound is not basic composition. Since this is the step that transfers privacy from the per-call oracle to Theorem 3.1, the current proof leaves the central privacy guarantee unsupported.","section":"Section 4, privacy proof of Algorithm 2"},{"comment":"Lemmas 4.3 and 4.4 are imported from [NS17], which is stated for unweighted graphs, and are asserted to extend to arbitrary non-negative weighted graphs 'with little to no change of their proofs'. This is load-bearing: Lemma 4.4 supplies the recursion-depth bound D that sets the privacy budget ε' = ε/(L·c_size·n^σ·log n), and if the weighted version fails then the privacy guarantee collapses. The second bullet of Lemma 4.3 also requires a weighted version of the inter-component edge-count bound. The paper should either prove these extensions in full or give a precise derivation showing exactly which parts of the [NS17] argument carry over to arbitrary non-negative weights; a citation to an unweighted statement is insufficient for the claimed weighted theorem.","section":"Section 4, Lemma 4.4 and Lemma 4.3"}],"minor_comments":[{"comment":"The equality |w_{\\tilde G_i}(C_i)-w_{G_i}(C_i)| - α w_{G_i}(C_i) = |w_{\\tilde G_i}(D_i)-w_{G_i}(D_i)| - α w_{G_i}(D_i) uses the fact that w(C_i)=w(D_i); this should be stated explicitly for clarity.","section":"Section 3.3, Eq. (3)"},{"comment":"The notation for the multiplicative approximation parameter is inconsistent: Table 1 uses α while the theorem statements use γ. Please align the notation.","section":"Table 1 and Theorem 1.1"},{"comment":"The theorem statement refers to parameters cexp and csize before they are defined; define them directly in the statement or immediately before it.","section":"Theorem 4.2"},{"comment":"The runtime claim 'poly(n, log log(1/δ), log(1/ε))' for the Max-k-Cut algorithm appears unrelated to the rest of the paper and is likely a typo; please state the actual polynomial runtime.","section":"Corollary 5.2"},{"comment":"The definition of σ = sqrt(log cexp / log n) is used only in the privacy budget and depth bound; it would help to state explicitly that L = O(1/σ) and to spell out the resulting no(1) bound.","section":"Section 4, Algorithm 2"}],"recommendation":"major_revision","confidential_remarks":"The additive-error analysis is sound and the algorithmic idea is promising, but the privacy proof for the recursive expander decomposition is not yet at the standard required for a theory paper. I would be willing to accept after the authors supply a formal recursive-composition proof and a rigorous weighted extension of the recursion-depth lemma. The paper is likely in scope for the journal and the result, if completed, is a significant contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a genuine advance—the first polynomial-time (eps,delta)-DP cut sparsifier beating the n^1.5 additive error barrier, with n^{1.25+o(1)}, and a private expander decomposition that should be reusable. The core algorithm is smart: privately decompose into expanders, handle inter-component edges with the EKKL20-style mechanism, handle each component with UUA21, then sparsify. The additive error analysis in Section 3.3 is clean; the parameter balance is right and the algebra checks out.\n\nThe soft spots are in the privacy proofs, and they are real but likely patchable. Section 3.1 says 'we assume the partition is the same' across neighboring graphs. That's the wrong way to say it. The right argument is to condition on the partition output of the private decomposition; for any fixed partition, an edge difference affects at most one UUA21 subgraph or the sparse-edge mechanism, so the per-partition budget of eps/3 composes. As written it's a presentation gap, not a mathematical error, but a referee should ask for the conditioning argument spelled out.\n\nSection 4 has a bigger gap. The privacy of Algorithm 2 relies on Lemma 4.4, the recursion-depth bound from [NS17], and the claim that an edge affects at most one recursive call per level. The per-level claim is right: subproblem vertex sets at a level are disjoint. The depth bound, however, is asserted to extend to weighted graphs 'with little to no change' and the proof is not reproduced. Since the whole privacy budget is divided by this depth, a failure there would sink the central DP guarantee. I suspect the extension is straightforward—the [NS17] depth argument is about vertex-count thresholds, not weights—but it needs to be shown, not just asserted. Same for the inter-component weight bound in Lemma 4.3.\n\nThe rest looks solid. The applications in Section 5 are straightforward corollaries. The citation pattern is fine: [LS21] and [NS17] are the right sources, [EKKL20] and [UUA21] are used as black boxes appropriately. Nothing circular.\n\nWho is this for? Anyone working on private graph algorithms or cut sparsification. It breaks a barrier that has been open for a while, and the technique will likely be reused. It deserves a serious referee. My recommendation: send it to review, but ask the authors to add a formal privacy-composition proof for the recursive decomposition and a proof or detailed citation for the weighted version of the [NS17] lemmas. If those are patched, I'd take the result.","headline":"Solid advance breaking the n^1.5 barrier for efficient private cut sparsification via a new private expander decomposition; the main error analysis holds, but the privacy composition for the recursive decomposition needs formal proof before I'd call it fully rigorous.","tokens_in":16965,"tokens_out":11252,"would_cite":true,"duration_ms":122983,"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":"A polynomial-time differentially private algorithm releases a sparse synthetic graph approximating every cut within $1+\\gamma$ multiplicative error and $n^{1.25+o(1)}$ additive error, breaking the $n^{1.5}$ barrier.","keywords":["differential privacy","graph sparsification","cut sparsification","expander decomposition","synthetic graph","cut queries","approximation algorithms","private graph release"],"falsifier":"Run Algorithm 2 on a weighted graph whose edge weights span the allowed $U = O(n^2)$ ratio (for instance, a path with geometrically decreasing weights), on two edge-neighboring inputs, and trace every recursive call whose input graph differs. If a single edge difference ever affects two different recursive calls at the same recursion level, or if the observed recursion depth exceeds $L \\cdot c_{\\mathrm{size}} \\cdot n^\\sigma \\log n = n^{o(1)}$, the claimed $(\\varepsilon,\\delta)$-DP composition bound fails.","tokens_in":15951,"feed_emoji":"🔒","tokens_out":15725,"duration_ms":150981,"temperature":0.7,"pith_summary":"The paper sets out to solve a long-standing gap in differentially private graph release: a polynomial-time algorithm that outputs a sparse synthetic graph approximating all cuts of a large weighted graph, with both a $(1+\\gamma)$ multiplicative factor and as little additive error as possible. Prior polynomial-time algorithms were stuck at $O(n^{1.5})$ additive error on dense graphs, while a near-optimal $O(n \\log n)$ error was reachable only in exponential time. The authors claim to break the $n^{1.5}$ barrier with an $(\\varepsilon,\\delta)$-DP algorithm whose additive error is $n^{1.25+o(1)}$ (up to polylog factors in $1/\\delta$ and $1/\\varepsilon$), while outputting a graph with only $\\widetilde{O}(n/\\gamma^2)$ edges. The strategy is to privately decompose the graph into dense expander components and a sparse remainder, then use a different private release mechanism on each part, exploiting the fact that the dense parts are so well-connected that their per-vertex additive noise is absorbed by the multiplicative error.","feed_headline":"Private sparsifier cuts worst-case error from n^1.5 to n^1.25","feed_subtitle":"First polynomial-time private cut sparsifier: additive error drops from n^1.5 to n^{1.25+o(1)}.","key_machinery":"The load-bearing mechanism is a private expander decomposition (Theorem 3.1). A graph is a $\\psi$-expander if every cut $S$ with $|S| \\le |V\\setminus S|$ has sparsity $\\varphi(S)=w_G(S)/|S|$ at least $\\psi$; the decomposition partitions $V$ into $V_1,\\dots,V_k$ such that each induced subgraph $G[V_i]$ is a $\\psi$-expander and the total weight of edges between different parts is $\\psi \\cdot n^{1+o(1)}$. The algorithm privatizes the recursive expander decomposition of [NS17] by replacing its cut-finding step with a private cut oracle (Theorem 4.2) built from the private graph release of [UUA21] and the deterministic weighted balanced-cut algorithm of [LS21]. Setting $\\psi \\approx n^{0.5+o(1)}$ makes each component dense enough that the $|C|\\sqrt{n}$ additive error of the per-component private release is absorbed into the $\\gamma w_G(S)$ multiplicative slack, so only the sparse inter-component edges contribute the $n^{1.25+o(1)}$ additive error, which is bounded using the $\\sqrt{W n}$ cut-norm algorithm of [EKKL20].","core_discovery":"The paper's central claim is Theorem 1.1: for any $\\gamma \\in (0,1)$, there exists a polynomial-time $(\\varepsilon,\\delta)$-differentially private algorithm that, given any non-negative weighted $n$-node graph $G=(V,E,w)$, outputs a non-negative weighted graph $H$ with $\\widetilde{O}(n/\\gamma^2)$ edges such that, with high probability, every cut $S \\subseteq V$ satisfies $$|w_G(S)-w_H(S)| \\le \\gamma w_G(S) + \\frac{$n^{{1.25+o(1)}}$ \\operatorname{polylog}(1/\\delta)}{\\varepsilon \\$gamma^{{0.5}}$},$$ where $w_G(S)$ is the total weight of edges crossing from $S$ to $V\\setminus S$. This breaks the $O(n^{1.5})$ additive error of the best prior polynomial-time private cut sparsifiers, and it does so while keeping the output sparse; the remaining gap to the exponential-time $O(n \\log n)$ bound is a factor of $n^{0.25+o(1)}$. The proof constructs a private expander decomposition, applies a cut-norm-based private release to the sparse inter-component edges, and applies a per-vertex-noise private release inside each expander component, where the expander's sparsity guarantee makes the additive noise a constant fraction of every nontrivial cut.","pith_inferences":["The same white-box privatization recipe—decompose into dense pieces where crude private release already meets the multiplicative guarantee, privatize the decomposition itself, and handle the sparse remainder separately—could transfer to other non-private decompositions (low-diameter decompositions, dense subgraph covers) for cut-based query release.","The practical payoff of this method is largest when the sparse remainder has total weight near its worst-case $n^{1.5+o(1)}$; on sparser inputs the previous $\\sqrt{mn}$ additive-error algorithms may still dominate, so a hybrid switch between the two could be the best empirical choice.","The privacy proof's reliance on a single-branch-per-level perturbation and on the unproved extension of the recursion-depth lemma to weighted graphs is the part to scrutinize first; a formal coupling argument or an explicit counterexample would settle whether the effective $\\varepsilon$ budget is exactly as claimed.","Because the released synthetic graph preserves all cuts to $n^{1.25+o(1)}$ additive error, it could serve as a private proxy for downstream tasks such as spectral clustering or densest-subgraph discovery, where cut values are the primary query."],"forward_implications":["The additive error for polynomial-time private cut sparsification drops from $O(n^{1.5})$ to $n^{1.25+o(1)}$ (up to polylog factors in $1/\\delta$ and $1/\\varepsilon$) for dense graphs, closing roughly a quarter of the gap to the exponential-time $O(n \\log n)$ bound.","Because the output is a sparse graph with $\\widetilde{O}(n/\\gamma^2)$ edges, it is suitable for memory- and communication-limited settings where the prior dense synthetic graph was prohibitive.","Running standard non-private optimization algorithms on the released synthetic graph yields $(\\varepsilon,\\delta)$-DP algorithms for Max-Cut, Max-Bisection, Max-k-Cut, and Min-Bisection with the same improved $n^{1.25+o(1)}$ additive error, matching the best known multiplicative approximation ratios.","An improved additive-error algorithm for graphs with roughly $n^{1.5}$ edges would, by plugging into this decomposition, automatically improve the bound for all graphs, as the paper notes in its conclusion.","The algorithm works for non-negative weighted graphs under edge-neighboring differential privacy, where a neighboring graph's total edge weight differs by at most 1."],"supporting_citations":[{"why":"Provides the previous best polynomial-time private cut sparsifier with O(n^1.5) additive error, the barrier this paper breaks, and the baseline for the max-cut application.","marker":"[GRU12]"},{"why":"Supplies the sqrt(Wn) cut-norm-based private release used on the sparse inter-component edges, and the exponential-time O(n log n) algorithm that defines the open problem.","marker":"[EKKL20]"},{"why":"Supplies the private per-component release with additive error proportional to |C|sqrt(n/epsilon) for each expander component, whose error is absorbed by the expander's sparsity.","marker":"[UUA21]"},{"why":"Establishes the near-optimal purely additive sqrt(mn) bound and the context for lower bounds that justify allowing multiplicative error.","marker":"[LUZ24]"},{"why":"Provides the non-private expander decomposition recursion and the recursion-depth lemma that the private algorithm inherits and that bounds the privacy composition.","marker":"[NS17]"},{"why":"Provides the deterministic weighted balanced-cut subroutine (used as Theorem 4.1) that lets the decomposition handle weighted graphs with bounded weight ratios.","marker":"[LS21]"},{"why":"The classic cut sparsifier run in post-processing to convert the synthetic graph into a sparse graph with O-tilde(n/gamma^2) edges.","marker":"[BK96]"}],"fun_headline_variants":["Private sparsifier breaks n^1.5 barrier, hits n^1.25 error","Polynomial-time private sparsifier cuts additive error to n^1.25","Expander decomposition yields private sparsifier with n^1.25 error","First efficient private cut sparsifier with sub-1.5 exponent"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that changing a single edge's weight affects at most one recursive call at each level of the private expander decomposition, so the total privacy loss is at most the recursion depth times the per-call privacy budget; the paper asserts this and the needed recursion-depth bound of [NS17] extends to weighted graphs without providing a formal proof.","fun_headline_variants_meta":{"raw":{"variants":["Private sparsifier breaks n^1.5 barrier, hits n^1.25 error","Polynomial-time private sparsifier cuts additive error to n^1.25","Expander decomposition yields private sparsifier with n^1.25 error","First efficient private cut sparsifier with sub-1.5 exponent"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000484,"raw_usage":{"total_tokens":2473,"prompt_tokens":1116,"completion_tokens":1357,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":732,"completion_tokens_details":{"reasoning_tokens":1270}},"tokens_in":732,"tokens_out":1357,"duration_ms":130498,"temperature":1.0,"reasoning_tokens":1270,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:44:52.516204+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 2 on a weighted graph whose edge weights span the allowed $U = O(n^2)$ ratio (for instance, a path with geometrically decreasing weights), on two edge-neighboring inputs, and trace every recursive call whose input graph differs. If a single edge difference ever affects two different recursive calls at the same recursion level, or if the observed recursion depth exceeds $L \\cdot c_{\\mathrm{size}} \\cdot n^\\sigma \\log n = n^{o(1)}$, the claimed $(\\varepsilon,\\delta)$-DP composition bound fails.","supporting_citations":[],"review_version":1}