PaperlayerView exact revision on arXiv

Source-linked AI summary

SHIP: Structured and Hierarchical Insight with Privacy

Kai Chen, Guisi Ni, Albert Cheu, Kassem Fawaz, Yuzheng Hu, Ryan McKenna, Peter Kairouz

arXiv:2610.21048v1cs.CLcs.CRcs.LG

TL;DR

Private insight methods produce varied formats that are difficult to compare, while analytical queries need fine-grained detail and cross-attribute statistics. SHIP maps workloads to attributes, builds hierarchical taxonomies, and releases a DP synthetic table. It improves QA performance over the strongest baseline on WildChat, while some query structures remain challenging.

  • Problem

    Private insight methods produce diverse output formats that complicate utility comparison, while analytical queries can require fine-grained categories and cross-attribute statistics.

    Source: §1 · pp. 1–2

  • Method

    SHIP maps a query workload to attributes, builds a hierarchical hybrid taxonomy, and releases a differentially private synthetic table for analysis.

    Source: §4.1 · p. 4, §4.2 · p. 5

  • Results

    On WildChat, SHIP gains 12.7% points in deterministic QA accuracy and 9.0 points in open-ended QA F1 over the strongest baseline across privacy budgets.

    Source: §1 · p. 2

  • Takeaways & Limitations

    SHIP provides strong query-answering utility for structured insights, while long topic-switching sequences remain challenging for its current representation.

    Source: §6 · p. 8, Limitations · p. 9

    The evaluation focuses primarily on dataset-level statistical and analytical queries and does not establish effectiveness for arbitrary queries or superiority across all aspects of data analysis.

    Source: Limitations · p. 9

Abstract

from arXiv · show

Extracting insights from textual data while protecting user privacy is increasingly important. Existing methods produce private insights in diverse forms for different analytical purposes, making their utility difficult to assess and compare. In this work, we formulate differentially private (DP) insights as reusable representations for answering analytical queries, providing a common basis for utility assessment. Answering these queries, however, requires fine-grained details and cross-attribute statistics that existing representations may omit. To capture this information, we introduce Structured and Hierarchical Insight with Privacy (SHIP), which automatically maps queries to attributes, builds a hierarchical hybrid taxonomy, and releases a DP synthetic table for further analysis. We also develop an evaluation protocol based primarily on QA performance and structured fidelity. Our experiments demonstrate SHIP's strong performance on both measures relative to existing private insight baselines, while identifying queries that remain challenging for structured representations.

1 Introduction

The introduction frames private insight extraction around workload-specific analytical queries, which require both fine-grained attribute detail and cross-attribute statistics. SHIP addresses this need with workload-aware structured insights and a shared evaluation protocol.

1 Introduction

  • Analyzing user text can help organizations understand needs and guide decisions, but such data may contain personal information requiring privacy protection.The introduction notes that generative AI tools are producing large volumes of user-facing textual data.Source: §1 · p. 1
  • Existing evaluations are tailored to methods’ output formats, so the introduction calls for a shared basis to compare analytical utility.The proposed protocol uses a shared offline agent for the same queries and adds structured fidelity assessment.Source: §1 · pp. 1–2
  • Analytical workloads require fine-grained categories and cross-attribute joint distributions, which cluster summaries, keyword statistics, and flat taxonomies may not provide.The introduction motivates a workload-driven DP framework that captures both insight depth and breadth.Source: §1 · pp. 1–2
  • SHIP maps workloads to attributes, builds a hierarchical hybrid taxonomy, and releases a DP synthetic table that preserves cross-attribute correlations.Its taxonomy combines private open-set discovery with taxonomy-model supplementation.Source: §1 · p. 2
  • SHIP gains 12.7% points in deterministic QA accuracy and 9.0 points in open-ended QA F1 on WildChat over the strongest baseline across privacy budgets.The introduction also identifies long topic-switching sequences as challenging for SHIP’s current representation.Source: §1 · p. 2

2 Preliminaries

The preliminaries establish the privacy setting, define workloads and reusable insights, and formalize workload-driven DP insight extraction. The target release must answer workload queries without further access to the private dataset.

2.1 Differential Privacy

  • Differential privacy is defined for neighboring datasets that differ by at most one individual record; the paper tracks privacy loss using zCDP for iterative operations.The supplied definition describes approximate zCDP through Rényi divergence of output distributions.Source: §2.1 · p. 2

2.2 Terminology

  • A query specifies a dataset-level analytical need, a workload collects such queries, and a workload-aware insight is a data structure derived from the dataset to answer them.The paper focuses on dataset-level analysis rather than individual-record retrieval.Source: §2.2 · pp. 2–3

2.3 Problem Statement

  • Workload-driven DP insight extraction designs a mechanism that releases an interpretable, reusable representation under (ε, δ)-DP for answering workload queries without further dataset access.The structured representation associates semantic attributes with value domains.Source: §2.3 · p. 3, §2.2 · p. 3

3 Related Work

Related work spans exploratory clustering and structured taxonomies, but existing approaches leave gaps in depth, breadth, and workload adaptation. SHIP is positioned as addressing these capabilities together.

3 Related Work

  • Existing paradigms differ across formal DP, insight depth and breadth, open-set category discovery, and adaptation to an explicit query workload.The paper organizes these capabilities in a comparison spanning clustering and taxonomy-based approaches.Source: §3 · p. 3, Table 1 · p. 3
  • Clustering methods such as Clio and Urania support exploratory analysis, but clustering entangles semantic dimensions and does not expose cross-attribute distributions.Clio lacks formal DP guarantees in the described comparison, while Urania uses DP keyword selection and DP k-means.Source: §3 · p. 3
  • Flat-Open can miss low-frequency categories and does not explicitly address multi-attribute analysis; independent attribute releases also lose joint distributions.Flat-Close captures breadth through tabular synthesis, but its utility depends on taxonomy quality.Source: §3 · pp. 3–4

4 Method

SHIP analyzes a query workload, constructs hierarchical attribute taxonomies, and privately synthesizes a reusable table. Its taxonomy combines data-driven discovery with complementary categories, while its privacy guarantee composes the taxonomy and synthesis budgets.

4.1 DP Taxonomy Building

  • At each taxonomy level, SHIP privately filters model-proposed open-set categories and supplements surviving categories with mutually exclusive complementary proposals.The process continues top-down across levels; surviving categories are attached to their parent and records are assigned to root-to-leaf paths.Source: §4.1 · pp. 4–5

4.2 SHIP

  • SHIP maps workload queries to atomic attributes, builds their taxonomies, and uses AIM to privately synthesize a table preserving low-order marginals and cross-attribute relationships.The released taxonomy and synthetic dataset support downstream analysis without additional privacy cost from post-processing.Source: §4 · p. 4, §4.2 · p. 5

4.3 Privacy Guarantee

  • The privacy theorem states that SHIP satisfies (ε, δ)-DP under the stated unbounded-DP setting when δtax < δ < 1.The theorem defines ρ as the sum of ρtax and ρaim.Source: §4.3 · p. 5

5 Experiments

SHIP is evaluated through deterministic and open-ended query answering and structured-distribution fidelity across conversational, financial, and medical datasets. It performs strongly on the tested workload, while long topic-switching sequences remain difficult for its structured representation.

5 Experiments

  • The evaluation combines deterministic QA accuracy and open-ended QA quality, with Semantic Sinkhorn Divergence additionally measuring structured fidelity.The experiments use WildChat and SynChat for query answering, and WildChat, CFPB, and ChatDoctor for structured insight quality.Source: §5 · pp. 5–6

5.1 Main Experiments

  • SHIP delivers the strongest overall query-answering performance across most tested deterministic settings and the highest open-ended F1 across evaluation settings.The evaluation covers WildChat and SynChat; Figure 2 reports open-ended precision, recall, and F1.Source: §5.1 · pp. 6–7, Figure 2 · p. 7
  • Baseline reports often have high precision but substantially lower recall, whereas SHIP’s WildChat recall ranges from 84.0% to 89.0%.On SynChat at ε = 1.0, Urania has 65.3% precision and 17.7% recall; at ε = 10.0, Flat-Open has 72.2% precision and 37.0% recall.Source: §5.1 · p. 7
  • Hierarchical approaches yield lower distribution divergences than flat baselines, while no single open- or closed-set strategy dominates across datasets and privacy budgets.On CFPB, Hie-Close’s 1-way divergence stays around 0.14 as the privacy budget increases, while SHIP’s falls from 0.13 to 0.11.Source: §5.1 · pp. 7–8, Table 3 · p. 8

5.2 Challenging Queries for SHIP

  • At ε = 10, SHIP’s released SynChat_topic distribution favors shorter topic-switching paths and fails to recover longer sequences.Variable-length paths create a large, sparse categorical domain that is difficult to recover through private discovery; prior-based completion also fits these data-dependent combinations poorly.Source: §5.2 · p. 8, Figure 3 · p. 8

6 Conclusion

The paper studies differentially private insight extraction through query answering, introducing SHIP and a unified evaluation protocol. Experiments show strong query-answering utility for structured insights while identifying queries that current paradigms still find challenging.

6 Conclusion

  • The work introduces SHIP for structured insight extraction under differential privacy and a unified protocol for measuring support for common analytical needs.Experiments identify both strong query-answering utility and queries that remain challenging for current insight-generation paradigms.Source: §6 · p. 8

Limitations

The evaluation and utility claims are bounded by the specified analytical workload and by the dimensions the evaluation measures. The authors also identify a possible taxonomy-depth bias in reference-based comparisons that they have not quantified.

Limitations

  • The query evaluation focuses on dataset-level statistical and analytical queries and does not establish effectiveness for arbitrary queries.The covered query types include counting, comparison, aggregation, and multi-attribute analysis.Source: Limitations · p. 9
  • Workload-based QA captures one utility dimension, not superiority across all data analysis; three-level taxonomies in both ground truth and SHIP may favor SHIP, and this potential bias is unquantified.The authors call for assessment across alternative taxonomy depths and reference schemas, and for broader analytical benefits.Source: Limitations · p. 9

Ethical Considerations

The supplementary material describes the paper’s privacy setting, related approaches, implementation choices, baselines, and datasets. It details a hybrid taxonomy pipeline and synthetic datasets with controlled ground truth.

Ethical Considerations

  • The experiments use publicly available and synthetic data without collecting additional private user data; SHIP targets aggregate analysis and releases insights under differential privacy.The work does not release identifiable user records or information.Source: Ethical Considerations · p. 9

A Supplementary Related Work

  • Unlike query-time retrieval or analysis systems, this work releases a reusable private insight representation; DP synthetic-text generation instead targets releases for downstream tasks beyond a predefined analytical workload.The two directions are described as complementary.Source: A Supplementary Related Work · p. 11

B.1 Detailed Implementation of SHIP

  • SHIP’s detailed taxonomy implementation skips “none” and “other” parent categories, filters supplementary categories with τclose = 10, and deduplicates categories across levels.Filtered categories are renamed “other” by default.Source: §B.1 · p. 11

B.2 Detailed Baseline Introduction

  • The baseline descriptions cover Urania, flat structured approaches, and hierarchical variants; Urania uses private keyword histograms and clustering, while Flat-Open releases independent attribute marginals.Hie-Close removes SHIP’s open discovery step, whereas Hie-Open removes its closed supplementary-category generation step.Source: §B.2 · pp. 12–13

B.3 Datasets Information

  • The artificial datasets have known labels by construction: SynChat plants cross-attribute correlations, while SynChat_topic uses controlled topic-transition sequences.The datasets sample ground-truth labels before an LLM renders them into conversations.Source: §B.3 · p. 13

B.4 QA Metric Introduction

The evaluation combines query-answering protocols with a semantic distributional metric, then illustrates how hierarchical and tabular structure handles detailed and cross-attribute queries but fails at extreme joint detail.

B.4 QA Metric Introduction

  • Deterministic QA uses 300 queries per dataset across yes/no, comparative, and numerical types; open-ended QA scores recall and precision against ground truth and averages F1 over five runs.Source: §B.4 · pp. 13–14

B.5 Textual Table Sinkhorn Divergence.

  • Textual Table Sinkhorn Divergence compares semantic category distributions and two-attribute joint distributions using debiased entropic transport; lower scores indicate closer alignment.Source: §B.5 · pp. 14–15

C.1 Examples of Categorization

  • SHIP assigns granular hierarchical paths across four orthogonal dimensions; flat baselines label only STEM, while Urania captures calculus-related detail alongside translation and backend-development content.Source: Table 6 · p. 15, §C.1 · pp. 16–17

B.6 Implementation Details

  • Implementation sets depth d=3, τclose=10, Gemini variants by task, global ε∈{1,5,10}, and δ=1/(n ln(n)).Source: §B.6 · p. 15

C.2 Deterministic QA Results

  • All methods answer macro queries, SHIP alone is relatively accurate on detailed queries, SHIP and Flat-Close answer cross-attribute queries, and all methods fail excessively detailed joint conditions.Source: Table 7 · p. 16, §C.2 · p. 17

C.3 Open-Ended QA Results

Across the appendix evaluations, SHIP is preferred to every baseline, and its open-ended reports capture macro distributions, fine-grained categories, and cross-attribute intersections. The section also examines category contributions, challenging cases, robustness to the QA agent model, and human verification of the evaluation agent.

C.3 Open-Ended QA Results

  • SHIP's open-ended reports combine macro distributions, hierarchical subcategories, and cross-attribute intersections, while flat methods lack sub-branches and Urania entangles dimensions.Urania also supplies keyword-level frequencies for technical operations, while Flat-Open's multivariate QA performance depends on attributes not being strongly related.Source: §C.3 · pp. 18–19

C.4 Contributions of Open-Set and Closed-Set Categories

  • At levels L0 and L1, open-set categories cover over 80% of records while closed-set categories cover under 10%; at L2, closed-set coverage rises to 32.1–37.6%.At L2, open-set coverage is 46.7–55.5%, suggesting closed-set supplementation increasingly contributes to record coverage at finer granularity.Source: Table 12 · p. 19, §C.4 · p. 19

C.6 Preference Evaluation Results

  • All pairwise scores exceed neutral 3: SHIP beats every baseline across datasets, privacy budgets, and workload-aware and workload-unaware judgments.The preference gap over Urania is nearly absent on homogeneous CFPB complaints but larger on diverse WildChat and ChatDoctor texts; the flat baselines are stricter comparators.Source: Table 13 · p. 20, §C.6 · p. 20

C.5 Challenging Query Examples

  • In a matched three-topic conversation, SHIP recovers NMR spectroscopy, electronic discovery, and Alexander Hamilton's early political career in the correct order.In a second conversation with five domain switches, it releases only “programming,” leaving four topics unrepresented.Source: §C.5 · p. 20

C.7 Robustness to the QA Agent Model

  • Replacing Gemini with Claude Sonnet changes SynChat deterministic QA scores by at most 0.05 and accuracy by at most 1.0% across three privacy budgets.The comparison retains the same released insights and other evaluation settings.Source: §C.7 · p. 21, Table 14 · p. 21

D Human Verification of Evaluation Agent

  • The example QA trace shows the agent using only SHIP's released table to resolve the population, aggregate categories across taxonomy levels without double counting, and verify its answer.The displayed code and intermediate outputs allow checking category mapping, denominator selection, calculation, and final answer.Source: D Human Verification of Evaluation Agent · p. 21

E Privacy Proof of SHIP

The proof analyzes privacy for SHIP's hybrid taxonomy construction and synthetic-table release under add-or-remove-one-record adjacency. It fixes the workload, dataset description, maximum depth, and models independently of the private corpus, while excluding record-level proposals and assignments from released outputs.

E Privacy Proof of SHIP

The same bounds hold for the histogram under any

  • With prior DP outputs fixed, one record changes the joint histogram by at most one count; Gaussian measurements and thresholding support the closed-stage guarantee.The proof excludes internal record assignments from the guarantee and treats complementary proposals and semantic deduplication as post-processing of DP categories and public information.Source: The same bounds hold for the histogram… · pp. 21–23
  • At each depth, open discovery and closed noisy histograms jointly satisfy δstep-approximate ρstep-zCDP across active parents, without privacy parameters scaling with parent count.Adding or removing one record affects at most one parent–category pair; the open and closed stages are composed adaptively.Source: The same bounds hold for the histogram… · pp. 22–23

F Computational Cost Analysis

SHIP’s hierarchical processing costs more LLM tokens than flat baselines and more record-level processing than Urania, trading added computation for stronger query-answering utility. The appendix also lists prompts used in SHIP and QA scoring, and reports Gemini-family assistance in coding and writing.

F Computational Cost Analysis

  • Under the fixed-depth implementation, SHIP’s record-level token cost ranges from one to two passes over N records per hierarchy level, plus taxonomy operations.The lower bound assumes no re-classification; the upper bound assumes every record needs a second pass at every level.Source: F Computational Cost Analysis · p. 25
  • Flat structured baselines make one record-level classification pass, while Urania makes one facet-and-keyword extraction pass and generates cluster summaries bottom-up.Urania also computes embeddings once and hierarchically clusters records; its non-LLM embedding and clustering costs are reported separately.Source: F Computational Cost Analysis · pp. 25–26
  • SHIP’s higher computational cost is a practical trade-off: its finer-grained representation is associated with substantially stronger utility on targeted and open-ended queries.The cost scales linearly with hierarchy depth.Source: F Computational Cost Analysis · p. 26

G Prompts

  • SHIP’s prompts cover category proposal, re-classification, complementary-category generation, and duplicate-category merging; Figure 8’s prompts score query answers or statements.Duplicate categories are merged after partition selection.Source: G Prompts · p. 26, Figure 8 · p. 28

H Generative AI Usage

  • The authors report using the Gemini family for coding and writing, with authors reviewing and verifying AI-assisted material and taking responsibility for the work.Source: H Generative AI Usage · p. 26
Loading 2610.21048v1…