Relation Mining Under Local Differential Privacy

Relation Mining Under Local Differential Privacy

Speakers: Kai Dong; Xinwen Fu

Conference: USENIX Security '24

YouTube: https://www.youtube.com/watch?v=xKP797VO9xo

Overview

In an era where centralized institutions amass vast quantities of data, data mining has become an indispensable tool for extracting immense value across diverse sectors, from market analysis and social media optimization to healthcare risk prediction and fraud detection. This process transforms raw datasets into actionable insights, fueling innovation and informing critical decisions. However, the pervasive collection and analysis of sensitive information introduce significant privacy risks, particularly when central servers may not be entirely trustworthy. To address these concerns, Local Differential Privacy (LDP) has emerged as a robust standard for data protection, offering strong mathematical guarantees that ensure individual privacy even against adversaries with extensive background knowledge.

While existing LDP protocols have successfully supported statistical estimation and item-level data mining tasks—such as frequency estimation or identifying popular individual items—a critical gap remains in the ability to mine complex relation-level knowledge under LDP constraints. Insights derived from relations, such as association rules (e.g., identifying products frequently bought together for retail optimization) or temporal dependencies (e.g., predicting product recommendations based on past user behavior), are crucial for unlocking deeper value from data. The absence of a general LDP-compliant approach for this task has hindered the application of privacy-preserving techniques to more sophisticated data mining problems.

This talk, presented by J from Sage University on behalf of Kai Dong and Xinwen Fu, introduces LDPRM (Local Differential Privacy Relation Mining), a groundbreaking framework designed to fill this void. LDPRM is the first LDP-compliant method specifically engineered to discover high-support and high-confidence relations from distributed private data. The core challenge tackled by LDPRM is the "curse of dimensionality," where the noise added by LDP to protect privacy escalates dramatically with the complexity of the data, severely impacting estimation accuracy. By employing innovative dimensionality reduction techniques, including singular value decomposition and low-rank approximation within an iterative scheme, LDPRM offers a practical and effective solution to enable complex relation mining while rigorously preserving user privacy.

Background

▶ Watch: Local Differential Privacy (LDP) introduction and principles (1:08)

The proliferation of data-driven decision-making necessitates robust data mining capabilities. In market analysis, it helps businesses understand consumer behavior and refine marketing strategies. On social platforms, it identifies emerging trends and enhances user experience. In healthcare, it predicts patient risks, optimizes insurance pricing, and detects fraud. The common thread is the conversion of vast datasets into actionable insights. However, this power comes with inherent risks of data leakage throughout the data's lifecycle, especially during the mining phase, as centralized servers responsible for aggregation may be susceptible to breaches or misuse.

To mitigate these privacy risks, Local Differential Privacy (LDP) has become a foundational paradigm. LDP operates on the principle that each user's data is perturbed locally before being sent to an untrusted aggregator, ensuring that the aggregator never receives exact individual data. This provides strong privacy guarantees, even if an adversary possesses full background knowledge, backed by rigorous mathematical proofs. The central tenet of LDP is to make an algorithm's output statistically indistinguishable regardless of minor changes in any single user's input, achieved by adding carefully calibrated noise. This noise level is governed by the privacy budget Epsilon (ε); a smaller Epsilon implies more noise, enhancing privacy but concurrently reducing data utility. An LDP protocol typically involves two algorithms: S, which users apply to perturb their data to ensure ε-LDP compliance, and Fi, which the aggregator uses to analyze the perturbed data and extract meaningful knowledge.

Prior work in LDP has yielded numerous protocols for statistical estimation and item-level data mining. For instance, mean estimation (defining average values) has seen developments like DUI, PM, and HM protocols. Frequency estimation (counting users with a given value) utilizes methods such as GRR (Generalized Randomized Response) and OL. Item mining focuses on identifying high-support items and estimating their frequencies. Despite these advancements, a comprehensive and general approach for mining relations—which involve interactions or co-occurrences between multiple items—under LDP has remained largely elusive.

Relation-level knowledge is distinct from item-level insights and offers profound value. For example, association rule mining is critical for retailers like Walmart to optimize product placement by identifying items frequently purchased together (e.g., "users who buy X also buy Y"). Similarly, understanding temporal relations drives sophisticated product recommendations on platforms like Amazon. The usefulness of a relation is commonly measured by two metrics:

• Support: Indicates a relation's popularity, defined as the proportion of users who possess that relation.
• Confidence: Reflects a relation's reliability, calculated as the ratio of the relation's support to the support of its first item.

The objective of relation mining under LDP is two-fold: first, to identify the top-K relations in terms of support; and second, from this set, to find the top-KC relations based on confidence. This task presents significant challenges, primarily hindered by two factors:

1. The Curse of Dimensionality: LDP's noise injection, while crucial for privacy, increases proportionally with the dimensionality of the data. Since the dimensionality of relations is at least the square of the number of individual items (D^2), estimating relation support accurately becomes exceptionally difficult in large item domains, as the noise can easily overwhelm the true signal.
2. Conflict Between Mining High Support and High Confidence Relations: Existing LDP methods often struggle to simultaneously identify both high-support and high-confidence relations. The talk illustrates this with an example involving six items and 75 users, represented by a 6x6 matrix showing item and co-occurrence support. Naive application of existing methods might select incorrect high-support relations, thereby missing the truly important high-confidence relations, which are essential for actionable insights. This conflict underscores the need for a specialized approach that can navigate these intertwined objectives effectively.

Key Findings

▶ Watch: Challenges: curse of dimensionality, support/confidence conflict (4:00)

The central contribution of this research is the introduction of LDPRM (Local Differential Privacy Relation Mining), a novel framework designed to overcome the significant challenges of relation mining under LDP. LDPRM directly addresses the curse of dimensionality and the conflict between high-support and high-confidence relation identification by employing a multi-level strategy focused on reducing LDP noise through strategic dimensionality reduction.

The core findings and contributions of LDPRM can be summarized as follows:

1. Dimensionality Reduction via Pre-estimation: LDPRM introduces a pre-estimation technique where the aggregator first estimates the support of all individual items and identifies a subset of top-K items. By focusing subsequent relation analysis exclusively on relations formed between these top-K items, the dimensionality of the relation domain is drastically reduced from O(D^2) (where D is the total number of items) to a much smaller O(K^2). This targeted approach significantly lowers the amount of LDP noise, thereby improving estimation accuracy.

1. Projection using Singular Value Decomposition (SVD): To further streamline the estimation process, LDPRM organizes support values into a matrix. Each user contributes a KxK matrix indicating their possession of relations among the top-K items. The aggregator then utilizes a variant of Singular Value Decomposition (SVD) on these matrices. This allows for the projection of user data into a local vector of length K, which enables the aggregator to recover the true KxK relation matrix by aggregating these projected vectors. This SVD-based projection effectively transforms a matrix estimation problem into a more manageable vector aggregation task.

1. Low-Rank Approximation for Further Noise Reduction: Building upon the SVD projection, LDPRM applies the best rank R approximation technique. This step further shrinks users' private vectors from length K to an even smaller length R (where R < K). This approximation simplifies the estimation task from a KxK matrix to an R-dimensional vector, leading to a substantial reduction in the LDP noise and enhancing the overall accuracy of relation support estimation.

1. Iterative Scheme for Convergence: LDPRM incorporates an iterative scheme that continuously updates the estimation of the aggregator matrix. This iterative refinement process is designed to automatically converge towards the true relation matrix, progressively improving the accuracy of the support and confidence estimations over time. Experiments confirmed the effectiveness of this iterative approach.

1. Comprehensive LDP Compliance: The proposed LDPRM framework is meticulously designed to satisfy ε-LDP for users, items, and relations across all its operational tasks. This is achieved by ensuring that each sub-protocol employed within LDPRM adheres to established LDP standards, providing robust privacy guarantees throughout the entire relation mining process.

1. Balanced Utility and Computational Efficiency: LDPRM carefully considers the trade-offs between estimation error and bias. While the best rank R approximation introduces some bias, the Eckart-Young-Mirsky theorem guides the selection of R to optimally balance bias and estimation error. Computational overhead analysis identifies Task 2 (high support relation mining) as the primary burden with an O(K^2) bottleneck, which is managed through the dimensionality reduction techniques.

1. Generalizability and Foundation for Future Work: LDPRM demonstrates strong generalizability. It can be enhanced to identify cascading relations involving more than two items and can serve as a foundational frequency oracle (dubbed SVD Foo) for large-scale frequency estimation under LDP. This versatility expands its potential applications in various privacy-preserving data mining scenarios.

1. Superior Experimental Performance: Extensive experiments conducted on five public datasets across four scenarios, using three metrics (F1, NCR, V) and five comparison methods, consistently showed that LDPRM significantly outperforms existing methods. This superior performance is particularly evident in large domains and when dealing with the curse of dimensionality, validating LDPRM's effectiveness in accurately identifying high-support and high-confidence relations.

Technical Deep Dive

▶ Watch: LDPRM's three key levels: pre-estimation, projection, iterative scheme (5:20)

The LDPRM framework is meticulously structured into three distinct tasks, designed to optimize privacy budget utilization by dividing users into three separate groups, with each user queried only once per task. This division ensures that the overall privacy budget remains within ε-LDP constraints.

LDPRM Architecture and Tasks

1. Task 1: High Support Item Mining

• Objective: To identify and estimate the support of the top-K items from the entire item domain (D). This initial step is crucial for reducing the dimensionality of the problem space.
• Mechanism: The aggregator interacts with the first group of users (N1 users). It employs the SVSM (Singular Value Sketching for Matrix) protocol, which is an LDP-compliant method for matrix estimation.
• Dimensionality Reduction: By focusing on the top-K items, the item domain is effectively reduced from D to K. Consequently, the potential relation domain, which would otherwise be D^2, is dramatically shrunk to K^2, significantly mitigating the curse of dimensionality.

1. Task 2: High Support Relation Mining

• Objective: To identify the top-KS relations (where KS < K^2) from the reduced KxK relation domain, based on their support. This is the most computationally intensive part, involving an iterative refinement process.
• Mechanism: The aggregator interacts with the second group of users (N2 users) through four iterative stages.
• User-side Processing: Each user, possessing a private set of items, constructs a KxK matrix indicating the presence or absence of relations among the top-K items.
• Projection and Low-Rank Approximation: The aggregator applies a variant of SVD to these user-contributed matrices. This process projects the high-dimensional KxK matrix data into a lower-dimensional representation. Crucially, the best rank R approximation is applied, shrinking each user's private vector from length K to a smaller length R. This step simplifies the estimation task from a matrix to a vector, further reducing LDP noise.
• Aggregation: The R-dimensional vectors from individual users are aggregated. The ASM protocol (likely an LDP-compliant aggregation method for singular vectors, similar to HM for mean estimation) is used here.
• Iterative Refinement: The aggregator continuously updates its estimation of the KxK relation matrix using an iterative scheme. This scheme is designed to automatically converge towards the true matrix, improving accuracy with each iteration. The process involves computing pseudo singular values and updating the matrix based on aggregated data.
• Dimensionality Reduction: This task reduces the relation domain from O(K^2) to O(R), where R is typically much smaller than K.

1. Task 3: High Confidence Relation Mining

• Objective: From the candidate set of top-KS relations identified in Task 2, the aggregator identifies the top-KC relations based on their confidence.
• Mechanism: The aggregator interacts with the third group of users (N3 users). Similar to Task 1, it leverages SVSM protocols or similar LDP-compliant mechanisms to estimate confidence values for the candidate relations.

Privacy Guarantee

LDPRM rigorously satisfies ε-LDP for individual users, their items, and their relations. This guarantee stems from the fact that each of the three tasks, and the specific protocols employed within them (such as SVSM and the underlying mean/singular vector estimation protocols like HM), are themselves designed to meet ε-LDP standards. By dividing users into distinct groups for each task, LDPRM ensures that each user contributes perturbed data only once per task, maintaining the overall privacy budget.

Utility Analysis

The utility of LDPRM's results, primarily measured by the accuracy of relation support and confidence estimations, is influenced by two key factors: estimation error and estimation bias.

• Estimation Error: LDPRM utilizes robust LDP protocols to bound estimation errors. For instance, the HM protocol is employed for mean singular vector estimation, and SVSM is used for relation support, both providing bounded L-infinity errors.
• Estimation Bias: The use of the best rank R approximation in Task 2 introduces a degree of bias when recovering the true KxK relation matrix. However, this is a controlled trade-off. According to the Eckart-Young-Mirsky theorem, selecting an appropriate (smaller) value for R allows for a balance between bias and estimation error. Reducing R generally lowers the estimation error (by simplifying the problem and reducing noise impact) but can increase bias. The research also considered a non-biased variant algorithm (HMM), demonstrating that in the context of LDPRM, this estimation bias has a minimal impact compared to the overall estimation error, suggesting the chosen R approximation is effective.

Computational Overhead

The computational burden of LDPRM is distributed across its three tasks and user groups:

• Task 1 & 3: These tasks primarily rely on SVSM protocols.
• User-side overhead: O(log D) for Task 1 and O(log KS) for Task 3, reflecting the complexity of perturbing data for item or candidate relation sets.
• Aggregator-side overhead: O(N1 log D) for Task 1 and O(N3 log KS) for Task 3, involving aggregation and estimation over the respective domains.
• Task 2: This task, with its iterative nature and matrix operations, represents the primary computational burden.
• Per-user overhead: Each of the N2 users computes pseudo singular values, incurring an overhead of O(K^2). Additionally, there's an O(log R) overhead associated with the ASM protocol for singular vector estimation. The total per-user overhead is O(K^2 + log R).
• Aggregator-side overhead: The aggregator performs SVD and matrix updates across T iterations (where T is the number of subgroups). This adds an overhead of O(T * K^2).
• Bottleneck: The O(K^2) operations in Task 2 represent the primary computational bottleneck of LDPRM. While SVSM and PCV (another potential protocol) are constrained by the perturbation overhead related to domain size KS, and COM (another comparison method) by the length of its edge table, LDPRM's K^2 complexity is managed by reducing K itself.

Enhancements and Generalizations

LDPRM's foundational principles allow for significant enhancements and generalizations:

• Cascading Relations: The framework can be modified to identify cascading relations involving more than two items. In a modified Task 2, after identifying top-K items, the aggregator can estimate relation support by multiplying item supports. If a relation's support surpasses that of an individual item in the candidate set, it replaces that item. The candidate set is then updated with the top-K items or relations, allowing for discovery of more complex, multi-item dependencies.
• SVD Foo (Frequency Oracle): LDPRM can serve as a foundational frequency oracle for large-scale frequency estimation under LDP, named SVD Foo. This involves encoding a unidimensional item domain into a b-dimensional one and then using LDPRM to estimate the resulting matrix, demonstrating the framework's versatility beyond just relation mining.

Demo / Proof of Concept

▶ Watch: LDPRM's three-task framework: item, support, confidence mining (7:00)

While the talk did not feature a live, interactive demonstration of the LDPRM system or a specific proof-of-concept tool, the speakers presented extensive experimental validation to substantiate the framework's effectiveness. These experiments served as the primary evidence of LDPRM's capabilities.

The research team conducted experiments on five public datasets across four distinct scenarios, employing three key metrics (F1 score, NCR, and V) and comparing LDPRM against five existing methods. For mining relations between items, two datasets, FTTT and Movie, were used. The first experiment investigated the impact of the privacy budget Epsilon (ε) and the number of top-K items (KS) on accuracy. Results consistently showed that as Epsilon or KS decreased (implying stronger privacy or less dimensionality reduction), F1 and NCR increased, while V decreased, indicating improved accuracy. LDPRM consistently outperformed all other methods in these scenarios.

A second experiment, using a modified FTTT dataset, focused on mining relations among multiple items. Here, methods like SVSM and COM were excluded due to their ineffectiveness in large domains. LDPRM again demonstrated superior performance, followed by HMM, while other methods struggled significantly, primarily due to the curse of dimensionality. The third experiment verified LDPRM's effectiveness in mining association rules using the retail dataset. Initially, SVSM performed well when high-support relations aligned with high-support items. However, when the dataset was modified to exclude the top eight items, SVSM's accuracy dropped drastically, whereas LDPRM's accuracy remained stable, highlighting its robustness.

Finally, two ablation experiments were performed. The first confirmed the effectiveness of LDPRM's iterative process compared to non-iterative algorithms. The second compared private and non-private algorithms, also revealing that simply increasing the number of iterations (T) is not always beneficial, as it can decrease the number of users per iteration and thus increase estimation error. These experiments also quantitatively showed that the estimation bias, as measured by the bias bound Theta, had a minimal impact compared to the estimation error, further validating LDPRM's design choices.

Defensive Implications

▶ Watch: Computational overhead and primary burden of LDPRM (9:00)

The introduction of LDPRM carries significant implications for organizations and defenders operating in environments where sensitive data must be analyzed while upholding stringent privacy standards. This research provides a robust, LDP-compliant methodology for extracting complex relational insights that were previously inaccessible or highly inaccurate under existing privacy-preserving frameworks.

For organizations leveraging LDP for distributed data collection and analysis, LDPRM offers a practical pathway to:

• Unlock Deeper Insights: By enabling the discovery of high-support and high-confidence association rules, co-occurrence patterns, and even cascading relations, LDPRM allows for a much richer understanding of user behavior, market dynamics, and system interactions. This translates into more sophisticated business intelligence, highly personalized recommendation systems, more accurate fraud detection, and enhanced anomaly detection capabilities, all without compromising individual user privacy.
• Build Robust Privacy-Preserving Systems: Defenders and system architects can now consider adopting or building privacy-preserving data mining systems that incorporate LDPRM's principles. The methodology's multi-level approach to dimensionality reduction (top-K item selection, SVD-based projection, low-rank approximation) and iterative refinement provides a blueprint for constructing LDP systems that effectively balance the critical trade-off between privacy guarantees and data utility, particularly for high-dimensional and complex analytical tasks.
• Optimize LDP Deployments: Understanding the interplay between the privacy budget (Epsilon), the dimensionality reduction parameters (K for top items, R for low-rank approximation), and the number of iterations (T) is crucial. Defenders should carefully tune these parameters based on their specific use case, data characteristics, and required privacy-utility balance. LDPRM's analysis of these trade-offs provides valuable guidance for informed decision-making in LDP system design.
• Address Complex Data Challenges: The ability to identify cascading relations is particularly valuable for analyzing complex sequences or multi-stage interactions, such as supply chain dependencies, sophisticated cyberattack kill chains, or intricate user journeys. This capability allows for the detection of more nuanced patterns that are often missed by simpler item-level analyses.
• Foundational for General LDP Tasks: The concept of SVD Foo, where LDPRM serves as a foundational frequency oracle, demonstrates its broader applicability. This suggests that LDPRM's core techniques can be adapted for a wider array of privacy-preserving tasks requiring large-scale frequency estimation, which is a common building block in many privacy-enhancing technologies.
• Mitigate the Curse of Dimensionality: LDPRM provides a concrete, experimentally validated solution to the "curse of dimensionality" in LDP settings. This is a critical defensive measure, as unmitigated high dimensionality can render LDP-protected data useless for analysis due to excessive noise. By effectively reducing the problem space, LDPRM ensures that valuable signals can still be extracted even from highly complex, distributed datasets.

In essence, LDPRM empowers organizations to move beyond basic statistical estimations under LDP, enabling them to derive complex relational insights while maintaining strong privacy guarantees. This advancement is vital for fostering innovation in data-driven fields without sacrificing user trust and data security.

Key Takeaways

• Addressing a Critical Gap: LDPRM is the first LDP-compliant method specifically designed for relation mining, a crucial but previously challenging task for complex data analysis on private distributed data due to the "curse of dimensionality."
• Novel Dimensionality Reduction Strategy: The framework effectively mitigates LDP noise by employing a multi-level dimensionality reduction approach, including pre-estimation of top-K items, SVD-based projection, and low-rank approximation (reducing KxK matrices to R-length vectors).
• Iterative and LDP-Compliant Design: LDPRM utilizes an iterative scheme for estimation refinement and convergence, ensuring that the entire process rigorously satisfies ε-LDP across all tasks by partitioning users and using LDP-compliant sub-protocols.
• Superior Accuracy and Robustness: Extensive experimental validation demonstrates LDPRM's consistent outperformance of existing methods in terms of accuracy (F1, NCR, V metrics), particularly in large domains and when dealing with high-dimensional relational data.
• Balanced Privacy and Utility: The framework carefully balances estimation error and bias, showing that the introduced bias from low-rank approximation has minimal impact compared to estimation error, indicating an optimal trade-off for practical utility.
• Versatile and Generalizable: LDPRM can be enhanced to identify complex cascading relations among more than two items and serves as a foundational frequency oracle (SVD Foo), broadening its applicability across various privacy-preserving data mining scenarios.

About the Speaker(s)

The talk was presented by J from Sage University, on behalf of Kai Dong and Xinwen Fu. Kai Dong is identified as the first author and is affiliated with Sage University. Xinwen Fu is a colleague, and the research represents a joint work conducted by Southeast University and "L" (likely an associated lab or institution). Their collective work focuses on advancing privacy-preserving data mining techniques, particularly under the challenging constraints of Local Differential Privacy.