Sparse relation tables arise when users contribute sets of user–item, learner–concept, or user location pairs. We study population relation-matrix estimation under personalized local differential privacy with heterogeneous budgets and Byzantine report replacement. The target is globally sparse, without low-rank assumptions. We propose a joint personalized relation sketch (JPRS), a set-level mechanism mapping each capped relation set to one personalized bit through a public pair-safe signed score. Its decoder combines channel amplitude weighting with sparse capped-simplex projection. Two budget functionals distinguish honest channel information from adversarial leverage. Under strong privacy, we establish a contamination-trimmed minimax lower bound over all local channels and an upper bound for JPRS against adaptive valid-output attacks from a precommitted corrupted identity set. The bounds match up to support-search logarithms on regular budget classes. In homogeneous settings, recovery requires the effective private sample size to dominate the structural scale and contamination to vanish relative to epsilon. Experiments on six synthetic scenarios and three processed public datasets show that JPRS achieves the lowest private loss and reduces endpoint loss by 23% relative to the best non-JPRS private comparator. These results characterize how personalized privacy, sparsity, and Byzantine contamination jointly determine recoverability.

We study estimation of globally sparse relation probability matrices from capped binary relation sets under personalized user-level local differential privacy and Byzantine response replacement. A cardinality-calibrated joint personalized relation sketch (JPRS) releases one bit per user. The decoder combines public channel-amplitude weighting with exact sparse feasible projection. We distinguish trimmed honest information, adversarial leverage, and a response-contamination indistinguishability radius. An explicit capped binary block construction yields a sampling lower bound with an explicit low-information truncation. A separate contamination construction gives a finite-sample error floor. For precommitted corrupted identities, the global decoder admits a uniform bound against adaptive valid-output attacks. In the strong-privacy, sufficiently informative regime, sampling and contamination bounds match up to logarithms on bounded-ratio budget classes, subject to the stated sample regularity and corruption-count conditions. The theory uses global sparsity rather than low-rank structure. Across six synthetic families, the global decoder has lower mean loss than the three tested private global baselines, but improves on zero only in the Zipf setting. Three public-data benchmarks further show that low aggregate error can be driven by a merged tail category. These results delimit practical utility; finite-budget attack searches do not certify worst-case performance.