Building K-Anonymous User Cohorts with Consecutive Consistent Weighted Sampling (CCWS)

Xinyi Zheng, Weijie Zhao, Xiaoyun Li, Ping Li

Abstract

As the digital advertising industry shifts away from individual tracking toward privacy-preserving cohort-based identity, the challenge of grouping millions of users into tight, similar clusters while maintaining $K$-anonymity has become paramount. Researchers at LinkedIn have introduced Consecutive Consistent Weighted Sampling (CCWS), a scalable hierarchical clustering algorithm. By leveraging advanced hashing techniques, CCWS ensures every cohort meets a minimum size $K$ while significantly outperforming industry standards like SimHash and vanilla Consistent Weighted Sampling (CWS) in targeting accuracy.

Introduction: The Privacy-Utility Trade-off

Driven by privacy initiatives such as Apple’s App Tracking Transparency (ATT) and Google’s Privacy Sandbox, the advertising landscape is moving toward cohort-based identity. The objective is to group users with similar interests into cohorts that are $K$-anonymous, meaning each group must contain at least $K$ users (e.g., $K=20$) to prevent individual identification.

Developing such a system at scale presents two major technical hurdles:

  1. Scalability: With hundreds of millions of users and high-dimensional feature vectors, traditional $O(n^2)$ clustering algorithms are computationally infeasible.
  2. Constraint Satisfaction: Standard clustering methods do not guarantee a minimum cluster size, a hard requirement for privacy compliance.

The CCWS Methodology

CCWS builds upon Consistent Weighted Sampling (CWS), a hashing technique designed to estimate similarity between non-binary, weighted data vectors. Unlike traditional "hash-and-sort" baselines that simply chop sorted users into fixed blocks, CCWS employs a recursive hierarchical splitting logic:

  • Hierarchical Splitting: Starting with a single global cohort, the algorithm applies CWS to generate hash values for every user.
  • Consecutive Logic: It identifies the most frequent hash value. A split is executed only if separating users with that hash into a new group leaves at least $K$ users in both the new and the remaining cohort.
  • Termination: This process repeats until no further splits can be made without violating the $K$-member minimum.

This approach ensures that the resulting cohorts are not only privacy-compliant but also highly cohesive, as the splitting logic prioritizes the preservation of similarity.

Experimental Evaluation

The algorithm was evaluated using a real-world dataset from LinkedIn Ads, comprising over 70 million users. Each user was represented by a weighted feature vector of approximately 200,000 dimensions. Performance was measured by how well the generated cohorts matched the original intended audiences of actual ad campaigns.

Key Results

CCWS was compared against several baselines, including Random Grouping, MinHash, SignRP (SimHash), and a "hash-and-sort" version of CWS.

Performance comparison of CCWS against baseline methods showing significant improvements in recall.

As shown in the table above, CCWS achieved a Macro-Recall of 0.844, outperforming the next best method (CWS hash-and-sort) at 0.721. More impressively, CCWS achieved a Micro-Recall of 0.254, representing a 3x improvement over both vanilla CWS (0.082) and SignRP (0.077).

Cohort Distribution and Privacy

To maximize targeting granularity, it is ideal for cohorts to stay as close to the privacy floor ($K$) as possible. CCWS demonstrates excellent control over cohort size distribution.

Cumulative distribution function (CDF) of cohort sizes, showing that the majority of cohorts are kept small to maximize granularity.

Analysis of the cohort distribution reveals that over 95% of the generated cohorts had sizes between 20 and 40. This indicates that the algorithm effectively creates tight groups that minimize audience dilution while strictly adhering to the $K=20$ privacy constraint.

Insights and Future Work

CCWS demonstrates linear efficiency ($O(Tn)$), making it viable for industrial-scale applications. The researchers found that utilizing weighted features (via CWS) rather than binarized data (via MinHash) is crucial for accuracy. Furthermore, the algorithm proved robust to hyperparameter tuning, specifically regarding the $p$-powered generalized min-max kernel.

While CCWS offers a massive leap in performance, micro-recall remains a challenge for very niche, highly-targeted campaigns where any grouping inevitably dilutes precision. Future work will explore integrating feature importance—such as weighting geographic or professional data more heavily—to further refine cohort quality while respecting the boundaries of $K$-anonymity.

Summary updated

Abstract

To retrieve personalized campaigns and creatives while protecting user privacy, digital advertising is shifting from member-based identity to cohort-based identity. Under such identity regime, an accurate and efficient cohort building algorithm is desired to group users with similar characteristics. In this paper, we propose a scalable $K$-anonymous cohort building algorithm called {\em consecutive consistent weighted sampling} (CCWS). The proposed method combines the spirit of the ($p$-powered) consistent weighted sampling and hierarchical clustering, so that the $K$-anonymity is ensured by enforcing a lower bound on the size of cohorts. Evaluations on a LinkedIn dataset consisting of $>70$M users and ads campaigns demonstrate that CCWS achieves substantial improvements over several hashing-based methods including sign random projections (SignRP), minwise hashing (MinHash), as well as the vanilla CWS.
BibTeX
@inproceedings{zheng2023building,
  author = {Xinyi Zheng and Weijie Zhao and Xiaoyun Li and Ping Li},
  title = {{Building K-Anonymous User Cohorts with Consecutive Consistent Weighted Sampling (CCWS)}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2023},
  doi = {10.1145/3539618.3591857},
}
Figure