TL;DR
This paper introduces a method to compare recommendation systems even when privacy controls prevent linking specific users to their purchases. By treating aggregate item-level purchase counts as constraints in a transportation-style linear programming problem, the authors can calculate sharp bounds on performance metrics like NDCG, proving one ranker is better than another without ever seeing individual-level data.
What Problem Does This Paper Address?
In the "golden age" of data, evaluators assumed they could always link a user’s recommendation slate to their eventual purchase. However, modern privacy regulations (like GDPR) and platform-level changes (like Apple’s App Tracking Transparency) have made "unlinked" data the new reality. When a user opts out of tracking, the evaluator knows what recommendations they saw, but not what they bought.
Standard workarounds are flawed:
- Complete-case evaluation: Simply ignoring unlinked users. This introduces massive bias if the people who opt out of tracking behave differently than those who don't.
- Worst-case bounds: Assuming the unlinked users bought the "best" or "worst" possible items. These bounds are usually so wide they are useless for decision-making.
The authors ask: Can we use aggregate sales data to narrow these bounds? Even if we don't know who bought Item X, we know exactly how many of Item X were sold to the cohort.
Methods
The core idea is to treat the evaluation as a transportation problem.
Imagine a bipartite graph: on one side are unlinked users, and on the other are items in the catalog. We know each user bought exactly one item (following the standard "leave-one-out" evaluation protocol), and we know the total count for each item.
- Linear Programming (LP): The authors formulate an LP where the objective is to maximize (or minimize) the difference in a metric (like NDCG@k) between two rankers. The constraints are the aggregate item counts. Because the constraint matrix is "totally unimodular," the LP naturally finds integer solutions—meaning it identifies a valid assignment of items to users that is consistent with the observed sales.
- Reduced Network: Solving this for a catalog of 100,000 items is computationally expensive. The authors developed a "reduced network" that merges items not present on any user's recommendation list into a "pool," drastically speeding up the math without losing accuracy.
- Differential Privacy (DP): To further protect privacy, the merchant might release noisy counts (using the Laplace mechanism). The authors provide a way to build a "simultaneous confidence box" around these noisy counts, ensuring the resulting performance bounds remain valid with a high degree of certainty (e.g., 95%).
Datasets
The authors evaluated their approach on two major e-commerce benchmarks:
- Beibei: 20,623 users and 7,977 items.
- Tmall: 103,507 users and 10,000 items.
They simulated various "linkage masks" to mimic real-world scenarios, such as users opting out randomly, based on their activity level, or based on their purchase outcomes.
Key Insights and Ideas
- Coupling is the "Aha!" Moment: Aggregate counts are powerful because they couple users. If only three unlinked users bought Item J, you can't "credit" Item J to 100 different users to make a specific ranker look better. This constraint significantly shrinks the uncertainty interval.
- Popularity is Easier to Prove: Rankers that favor popular items (like a "Most Popular" baseline) are much easier to evaluate with this method. Because many users see the same popular items, the aggregate counts for those items provide very tight constraints.
- The Information Ladder: The paper demonstrates a clear trade-off. Finer data (e.g., counts broken down by user age groups) leads to tighter performance bounds but increases the risk of leaking information about individual purchases.
- Tiered Releases for DP: For differentially private releases, the authors found that releasing exact counts for the most popular items and grouping the "long tail" of unpopular items into bins provides the best balance of utility and privacy.
Key Results
- Narrowing the Gap: On the Beibei dataset, using exact item counts reduced the width of the uncertainty interval to just 30% of the width of bounds that ignored the counts.
- Settling the Score: In the smaller Beibei cohort, exact counts were able to "settle" (prove a winner) in 25% of the tested scenarios where standard bounds would have abstained.
- Privacy Resilience: Even with Differential Privacy ($\epsilon=1$), the method retained significant utility, especially in the larger Tmall cohort.
- Speed: The reduced network formulation allowed the system to solve problems in seconds that would otherwise involve hundreds of millions of variables.
Limitations and Future Work
- Personalized Rankers are Tough: While the method works great for rankers that favor popular items, it struggles to distinguish between two highly personalized rankers where every user sees a unique list. In these cases, the aggregate counts are less restrictive.
- The "One Item" Assumption: The current model assumes each user bought exactly one item during the test period. While the authors discuss extensions for multiple purchases, the math becomes more complex.
- Under-reporting: If the merchant's counts are incomplete (e.g., missing some sales), the bounds become one-sided. The authors suggest that complete cohort-restricted reports are essential for the best results.
For more details, you can find the full paper under the title "What Unlinked Aggregates Still Prove: Ranker Comparisons from Exact and Differentially Private Item Counts" (arXiv:2611.20388v1).
Summary updated