Lost in the Crowd: k-unmatchability in Anonymized Knowledge Graphs

This paper introduces and investigates k-unmatchability, a counterpart of k-anonymity for knowledge graphs. Like k-anonimity, k-unmatchability enhances privacy by ensuring that any individual in any external source can always be matched to either none or at least k different anonymized individuals. The tradeoff between privacy protection and information loss can be controlled with parameter k. We analyze the data complexity of k-unmatchability under different notions of anonymization.