PaperlayerView exact revision on arXiv

Source-linked AI summary

BetweenCut: Private Heavy-Node Classification with Doubly Logarithmic Error in Tree Height

Ergute Bao, Graham Cormode, Xiaokui Xiao, Ting Yu

arXiv:2610.10075v1cs.CRcs.DS

TL;DR

Private heavy-node classification is difficult because each record affects counts along a tree path, while prior methods incur height-dependent error. BetweenCut combines histogram-based counting with threshold testing and cuts off search after a middle response. It achieves doubly logarithmic height dependence in additive error, simultaneously for all nodes and independently of database size.

  • Problem

    Each record affects counts along a root-to-leaf path, and existing private heavy-node methods incur additive error margins that grow with tree height.

    Source: §1 · p. 1, §5.3 · p. 8

  • Method

    BetweenCut combines histogram-based node counting with threshold testing and uses a middle response to cut off search along affected paths.

    Source: §1 · p. 2, §5.3 · p. 8

  • Results

    Oε,δ(log log h) additive error holds simultaneously for all nodes with probability one and is independent of input database size.

    Source: §6 · p. 8

  • Takeaways & Limitations

    A middle response limits each record to at most one target hit, while balanced level search limits affected queries to O(log h).

    Source: §6 · p. 8

    The hidden constants are sufficiently large that BetweenCut achieves its smallest absolute error only for extremely deep trees.

    Source: §6 · p. 9

Abstract

from arXiv · show

Finding heavy nodes in a tree---those whose counts exceed a given threshold---is a building block for analysis and learning over structured data. Achieving record-level differential privacy (DP) without sacrificing accuracy is challenging because each record contributes to counts along an entire root-to-leaf path, allowing privacy costs to accumulate across levels. Existing methods account for the multiple threshold comparisons for each record incur additive error margins of $\Omega_{\varepsilon,\delta}(\log h)$ or $\Omega_{\varepsilon,\delta}(\sqrt{\log h})$ for tree height $h$. We introduce \textsc{BetweenCut}, an $(\varepsilon,\delta)$-DP algorithm with an additive error margin of $O_{\varepsilon,\delta}(\log\log h)$, improving the existing bounds for deep trees. This error holds simultaneously for all nodes and is independent of the input database size.

1 INTRODUCTION

The paper addresses private heavy-node classification on trees, where each record affects counts along its root-to-leaf path. It combines histogram-based counting with threshold testing and uses a middle response to cut off further search along a path.

1 INTRODUCTION

  • Earlier approaches either reduced the number of queries or controlled positive answers, while retaining privacy costs or error from repeated threshold tests.Lumberjack reduces per-record participation to O(log h) tests; threshold-testing methods retain log h error terms from a union bound over levels.Source: §1 · p. 1
  • The algorithm combines histogram-based node counting with SVT-style threshold testing to classify heavy nodes privately.Its threshold test returns Low, High, or Middle using fresh Laplace noise and two fixed public thresholds around τ.Source: §1 · p. 2
  • A Middle response marks proper ancestors Heavy and the queried node and its descendants Light, terminating search on every path through that node.Thus, any root-to-leaf path can have at most one Middle outcome.Source: §1 · p. 2
  • Low and High outcomes need not trigger separate privacy charges under the analysis, which introduces a one-target, finite-horizon variant of Target-charging.Target-charging generalizes the Sparse Vector Technique and BetweenThresholds.Source: §1 · p. 2
  • The analysis permits reusing a noiseless threshold across queries on disjoint paths, avoiding re-sampling and composition overheads.The authors describe the resulting algorithm and proofs as a clean framework for related private search problems.Source: §1 · p. 2

2 PROBLEM FORMULATION

This section defines the public tree, private records, node counts, and the simultaneous heavy-node classification objective. It then sets out record-level privacy and the SVT and target-charging tools used to reason about repeated threshold queries.

2.1 Heavy Node Classification

  • The public input is a rooted tree of height h and arity k; the private database is a finite multiset of leaf records, each contributing to a leaf count.The tree structure and node ordering are public, and n denotes the database size.Source: §2.1 · p. 2
  • The goal is to label every node Heavy or Light relative to public threshold τ, allowing an additive error margin E around that threshold.The classification guarantee applies simultaneously to every node, except with probability at most β.Source: §2.1 · p. 2
  • The returned Heavy set is ancestor-closed and must include nodes with count at least τ + E while excluding nodes below τ − E.Nodes in the intervening threshold band may receive either label.Source: §2.1 · p. 2

2.2 Differential Privacy

  • Under add/remove adjacency, neighboring databases differ by one added leaf record, which affects only the counts on that record’s root-to-leaf path.Its contribution to each affected count is exactly 1.Source: §2.2 · p. 2
  • For a counting query f with sensitivity 1 and ε > 0, the mechanism defined as A(D)=f(D)+Z satisfies (ε, 0)-DP.Source: §2.2 · p. 3
  • SVT-style accounting controls privacy through the number of positive answers rather than the total number of threshold queries.The basic AboveThreshold primitive stops at the first positive response.Source: §2.2 · p. 3
  • Target-charging extends SVT-style accounting to general DP mechanisms by associating runs with output targets and tracking target hits.Its privacy cost can be independent of the total number of queries; TCT uses fresh query noise against a public, fixed noiseless threshold.Source: §2.2 · p. 3
  • A q-target decomposition separates a component with DP access to the input from an unrestricted component whose probability contributes to the exceptional probability.The decomposition is primarily an analysis device and need not be implemented by the release mechanism.Source: §2.2 · p. 3

3 HEAVY NODE CLASSIFICATION

Prior approaches to private heavy-node classification use either histogram-based counting or threshold testing. The paper combines these paradigms to reduce the height dependence of the additive error margin.

3 HEAVY NODE CLASSIFICATION

  • A naive full-tree Gaussian histogram release has additive error Oε,δ(h), because a record contributes across the tree’s levels.The histogram publishes node counts at every level and thresholds noisy counts against τ.Source: §3 · p. 3
  • Lumberjack queries middle layers and recurses upward or downward based on noisy counts, with each leaf counted in O(log h) histograms.Its Gaussian-noise error is O(√log h).Source: §3 · p. 3
  • Threshold-testing methods traverse the hierarchy using SVT-like tests, but their errors retain log h terms or depend on a public database-size bound.Ghazi et al. bound positive answers by O(M/τ), where M is an upper bound on total count n.Source: §3 · pp. 3–4
  • The paper unites histogram-based counting and threshold-testing approaches to reduce heavy-node classification error to Oε,δ(log log h).The cited prior threshold-based methods have Ωε,δ(log h) error, while the histogram-based method has Ωε,δ(√log h) error.Source: §3 · pp. 3–4

4 OUR ALGORITHM

BetweenCut uses a three-outcome guarded threshold test and midpoint-first traversal to classify tree nodes with label propagation. A “between” response cuts affected paths, limiting each path to one such response and enabling a finite-horizon privacy analysis.

4.1 Building Blocks

  • The one-hit target-charging building block stops interaction at the first target hit, with at most K calls when no hit occurs sooner.Its finite-horizon analysis bounds overflow after r target misses using the target-hit probability and accounts for exceptional mass.Source: §4.1 · p. 4
  • GuardedBT returns L, H, or B: far-below and far-above counts receive deterministic labels, while counts in the guarded range are tested with fresh Laplace noise.The thresholds are a and b; R sets the guard margin, and λ is the local privacy parameter.Source: §4.1 · p. 4

Label propagation.

  • Label propagation sends L to a node and its descendants, H to a node and its ancestors, and B to light descendants and heavy proper ancestors.The routines are called MarkDown and MarkUp; the B response marks the boundary between the heavy ancestors and light descendants.Source: Label propagation · p. 5

4.2 The BetweenCut Algorithm

  • BetweenCut combines the guarded count query, public traversal, and label propagation to classify every tree node.The algorithm processes unlabelled nodes in the public depth order and propagates labels after each L, H, or B response.Source: §4.2 · p. 5
  • Midpoint-first traversal with label propagation makes at most ⌈log2(h + 1)⌉ guarded queries on each root-to-leaf path.The public depth ordering visits the middle level first, then recursively visits the lower and higher intervals.Source: §4.2 · p. 5, §4.1 · p. 5
  • A B response prevents all later queries on every root-to-leaf path through its node, so each such path has at most one B response.The response resolves the path by propagating heavy labels to ancestors and light labels to descendants.Source: §4.2 · p. 5

5 PRIVACY AND UTILITY

BetweenCut targets the privacy cost of repeated threshold tests by focusing on near-threshold inputs, for which a B response stops further queries along affected paths. Its simultaneous deterministic error margin is O(log log h), improving the height dependence of prior heavy-node methods.

5 PRIVACY AND UTILITY

  • Only inputs near threshold τ incur a genuine privacy cost; a B response for such boundary inputs stems further leakage along the path.Counts sufficiently far below or above τ can be revealed without privacy impact, while repeated boundary inputs failing to produce B are bounded.Source: §5 · p. 6

5.1 Privacy Analysis

  • The analysis bounds privacy by considering the affected root-to-leaf path, where at most ⌈log2(h + 1)⌉ queries occur and no further query follows a B response.It applies a finite-horizon one-hit TCT bound to those queries and reconstructs the full algorithm transcript.Source: §5.1 · p. 7

5.3 Discussion and Comparison to Prior Work

  • At fixed privacy parameters, our method achieves O(log log h) error with β = 0, improving on Lumberjack’s O(√log h log log h) error through exponentially better dependence on h.Source: §5.3 · pp. 7–8
  • BetweenCut’s deterministic error guarantee does not require an upper bound on database size n, unlike the stated utility bounds for Ghazi et al. [25] and probabilistic Lumberjack [38].For [25], M affects utility through the number of positive answers; for probabilistic Lumberjack [38], M enters through a union bound over noises.Source: §5.3 · p. 8
  • The ε ≤ 1 restriction simplifies parameter calibration rather than being intrinsic; the authors state that the results extend to ε > 1.Using the larger privacy budget requires additional analysis of the residual-call cutoff.Source: §5.3 · p. 8
  • A geometric-threshold reduction gives α-mRMSE Oα,ε,δ(log log h) for fixed α, improving on the Oα,ε,δ(log h) bound in [25].The passage states this improvement for count estimates with uniformly bounded additive error.Source: §5.3 · p. 8
  • Matching height-dependent lower bounds remain open for approximate-DP heavy-node classification and additive–multiplicative tree counting.The authors leave both lower-bound questions to future work.Source: §5.3 · p. 8

6 CONCLUSION

BetweenCut gives simultaneous, input-size-independent heavy-node classification on public trees with an O_ε,δ(log log h) additive error margin. The analysis notes that large hidden constants mean its smallest absolute error is achieved only for extremely deep trees.

6 CONCLUSION

  • BetweenCut achieves an input-size-independent O_ε,δ(log log h) additive error margin simultaneously for all nodes with probability one.The conclusion identifies this as Theorem 5.6.Source: §6 · p. 8
  • Large hidden constants mean BetweenCut achieves its smallest absolute error only for extremely deep trees.The authors list tightening privacy-parameter dependence and determining optimal height dependence as future directions.Source: §6 · p. 9

AI use statement

  • The authors used generative AI to check proof details, derive constants, and improve writing, but not to design the algorithm.They state that experiments were not applicable and that they reviewed AI-assisted work.Source: AI use statement · p. 9

A.1 Naive Baselines for Differentially Private Heavy Nodes

  • The full-tree baselines independently noise node counts and threshold them; a record contributes across h levels, giving sensitivity h for the levelwise count vectors.Thresholding is post-processing of the differentially private output.Source: §A.1 · p. 11

A.2 Additive Error Guarantee of Ghazi et al.

This appendix translates Ghazi et al.’s relative-tolerance guarantee into an additive margin and reviews related methods and algorithmic properties. It also records the label-propagation routines and structural guarantees used by the algorithm.

A.2 Additive Error Guarantee of Ghazi et al.

  • At a prescribed threshold, Ghazi et al. [25] provide an additive error margin in O(log h).Their result is stated for failure probability 0 < β < 1/2.Source: §A.2 · p. 12

A.3 Other Related Works

  • PrivTree [47] uses a depth-dependent threshold bias of O(d), so it does not automatically provide a bounded error margin comparable to BetweenCut.The appendix also notes that its guarantee is not comparable with BetweenCut’s method.Source: §A.3 · p. 12
  • The threshold-release reduction discussed by Ghazi et al. [25] has input-size-dependent error, unlike BetweenCut’s size-independent margin.The cited reduction’s error includes a (log n)^2.5 factor.Source: §A.3 · p. 12

B.1 Label Propagation

  • The label-propagation routines inspect only the public tree and current labels, making no additional count queries.Source: §B.1 · p. 12

B.2 Algorithm Properties

  • Algorithm 3 maintains ancestor-closed Heavy and descendant-closed Light sets that stay disjoint, and labels each node permanently.It terminates with every node labeled Heavy or Light.Source: §B.2 · pp. 12–13
  • For a fixed database, Lemma B.2 bounds the number of positive-count queries made by Algorithm 3.Source: §B.2 · p. 13

B.2.1 Dense implementation cost

The dense implementation’s cost is linear in the number of records and tree nodes, with linear auxiliary space under the stated computational conventions.

B.2.1 Dense implementation cost

  • Total marking work is O(N), assuming count and label access, edge traversal, arithmetic, comparisons, and Laplace sampling take constant time.Source: §B.2.1 · p. 13
  • The dense implementation runs in O(n + N) time and uses O(N) auxiliary space.Here n is the database size and N is the number of tree nodes.Source: §B.2.1 · p. 13
  • It makes at most N GuardedBT calls and performs exactly N marking assignments after initialization.The inner node loop considers each node exactly once.Source: §B.2.1 · p. 13

B.3 Proofs of Algorithmic Properties

The proofs establish that label propagation preserves consistent, permanent classifications and that midpoint-first depth search bounds queries along each path. The TCT analysis uses a tunable parameter to trade between the ε and δ components of its privacy guarantee.

B.3 Proofs of Algorithmic Properties

  • The algorithm preserves disjoint, ancestor-closed Heavy and descendant-closed Light sets; every node is eventually labeled, and its label does not change.Source: §B.3 · pp. 13–14
  • Each root-to-leaf path has at most ⌈log2(h + 1)⌉ queried nodes under midpoint-first depth search.After processing the middle level, closure and permanent labels leave queries on a path in at most one remaining subinterval.Source: §B.3 · p. 14
  • A Between response permanently labels the queried node’s ancestors Heavy and its node and descendants Light, preventing later queries on paths through it.Consequently, each root-to-leaf path contains at most one Between response.Source: §B.3 · p. 14
  • Marking work is O(N): each tree edge is scanned at most once during downward marking, without requiring bounded arity.Source: §B.3 · p. 15

C.1 Proof for the Bespoke Analysis for TCT

  • In the TCT analysis, increasing the tunable parameter r weakens the ε component and strengthens the δ component of the privacy guarantee.Source: §C.1 · p. 17

C.2 Proofs for Privacy

The privacy proofs decompose each query’s output into shared and residual probability mass, then control privacy along the affected record path. Composing those guarantees yields transcript privacy and, by post-processing, privacy for the released Heavy set.

Target decomposition

  • The target decomposition writes each output law as a common component plus residual laws that are λ-indistinguishable and retain sufficient Middle probability.The proof establishes this for neighboring counts, including guarded cases with exceptional mass at most δ0.Source: §C.2 · pp. 17, 20, 21

Guarded target decomposition

  • Guarded outputs with identical laws need no residual privacy cost, while crossing a guard is handled with an exceptional mass bounded by δ0.The proof treats identical guarded laws and the remaining neighboring-count cases separately.Source: §C.2 · pp. 20–21

Transcript privacy

  • For a finite public rooted tree of height h ≥ 1, Algorithm 3 with stated thresholds and fresh independent GuardedBT noise produces (rλ, δr)-indistinguishable transcripts for neighboring datasets and every integer 1 ≤ r ≤ L.This holds for public parameters τ ≥ 0, 0 < λ ≤ 1, and R ≥ 1.Source: §C.2 · p. 21
  • For fixed off-path answers, the affected-query transcript is private; replaying the full traversal then transfers that guarantee to the complete transcript.The released Heavy set is a deterministic function of the transcript, so post-processing preserves the guarantee.Source: §C.2 · p. 22

Explicit privacy parameters

  • Theorem 5.5 calibrates the parameters to obtain (ε, δ)-DP for Algorithm 3.When r = L, the additional term vanishes, giving (ε, δ/2)-DP before the remaining additive privacy parameter is bounded by δ.Source: §C.2 · p. 22

C.3 Proofs for Utility

The utility proof establishes a simultaneous deterministic classification margin for Algorithm 3. Combining that margin with its privacy guarantee yields the stated utility guarantees.

Exact deterministic margin

  • With probability one, Algorithm 3 has simultaneous deterministic margin E = w + R around threshold τ.The theorem’s bounds place nodes outside the Heavy set below τ + E and nodes inside it above τ − E.Source: §C.3 · p. 22

Utility guarantee

  • Combining the privacy and utility theorems gives the utility guarantees stated in Theorem 5.6.Termination ensures every node receives one of the two labels.Source: §C.3 · pp. 22–23

Proof of the deterministic margin

  • The margin follows from the deterministic guards: Heavy labels have queried witnesses above the lower guard, while Light labels have witnesses below the upper guard.Ancestor and descendant count monotonicity transfers those witness bounds to classified nodes.Source: §C.3 · pp. 22–23

D SPARSE IMPLEMENTATION

The appendix gives a sparse implementation of BetweenCut and extends classification to numerical tree counting through repeated threshold calls. The counting construction uses increasing thresholds and decreasing privacy budgets.

D SPARSE IMPLEMENTATION

  • Under τ ≥ E, the sparse implementation matches the dense algorithm’s Heavy-set distribution and preserves its (ε, δ)-DP guarantee and deterministic margin E.It omits zero-count queries, treating omitted nodes as Light.Source: D SPARSE IMPLEMENTATION · p. 23

E.1 Tree Counting through Classification

  • BetweenCut supports numerical estimates by assigning each node an estimate when it first becomes Light, using nearby Heavy and Light thresholds as count bounds.Nodes Light in the first round are estimated by zero; the resulting error is Oα,ε,δ(log log h), an exponential improvement over Oα,ε,δ(log h) in [25].Source: §E.1 · p. 25

E.2 Construction

  • The construction uses a uniform margin bound across calls, keeping each call’s margin at most a fraction γ of its threshold.These bounds provide the lower and upper count bounds used by the reduction.Source: §E.2 · p. 25
  • The counting construction runs BetweenCut on the original tree at increasing thresholds and stops when the root becomes Light.It assigns decreasing privacy budgets so the executed calls’ total budgets do not exceed ε and δ, even when their number is not fixed in advance.Source: §E.2 · p. 26

E.3 Guarantee and proof

Theorem E.1 establishes private numerical estimates with a simultaneous accuracy guarantee. Its error scale is Oα,ε,δ(log log h), independent of database size, and the proof uses increasing thresholds to accommodate the classification margins.

Guarantee

  • Theorem E.1 gives an (ε, δ)-DP estimator whose nonnegative estimates satisfy the stated accuracy bound simultaneously with probability one.The theorem applies to finite public rooted trees of height h ≥ 3.Source: §E.3 · p. 26

Comparison with Ghazi et al.

  • Compared with the Oα,ε,δ(log h) error in [25], the paper describes the Oα,ε,δ(log log h) bound as an exponential improvement in h.The stated utility guarantee also uses a threshold-based form without requiring node-specific thresholds.Source: §E.3 · pp. 26, 28

Proof of accuracy

  • Each node is estimated at its first Light round; if it was Heavy in the preceding round, those two classifications bracket its count.If it is Light in the first round, its error is bounded by B; combining the cases proves the bound simultaneously for all nodes.Source: §E.3 · pp. 27–28

Guarantee

  • B = Oα,ε,δ(log log h), with no database-size dependence.For fixed α, ε, and δ, the constants defining the scale are independent of both h and the database D.Source: §E.3 · p. 28

Increasing thresholds

  • The reduction’s increasing thresholds let it classify the original tree repeatedly without an upper bound on database size or lighter-subtree refinement.BetweenCut’s classification margin does not depend on a root-count bound, unlike the cited classifier [25].Source: §E.3 · p. 28
Loading 2610.10075v1…