Adaptive Anonymity via b-Matching
The adaptive anonymity problem is formalized where each individual shares their data along with an integer value to indicate their personal level of desired privacy. This problem leads to a generalization of k-anonymity to the b-matching setting. Novel algorithms and theory are provided to implement this type of anonymity. The relaxation achieves better utility, admits theoretical privacy guarantees that are as strong, and, most importantly, accommodates a variable level of anonymity for each individual. Empirical results confirm improved utility on benchmark and social data-sets.
'Adaptive Anonymity via b-Matching' addresses the 
      problem of releasing a private dataset such that by censoring measurements 
      individuals in the dataset become indistinguishable. The authors explain 
      the concepts of k-anonymity and the b-matching problem as forming a 
      bipartite graph that describes the compatibility of the original dataset 
      with the released dataset. They provide two algorithms, for the asymmetric 
      and symmetric cases, which are justified as variational approximations of 
      the star (suppression) minimization problem. There is an approximation 
      result for the algorithms. A variety of privacy guarantees are provided 
      for single attacks,and sustained attacks on the k-clique construction, 
      symmetric and asymmetric b-matchings. A brief experimental section is 
      provided with some convincing results. This paper is of high 
      quality, as it comprehensively addresses the b-matching problem and 
      provides strong computationally feasible algorithms that are well 
      justified. It is very well written with a very understandable introduction 
      and exposition. The algorithmic results are strong, as are the privacy 
      guarantees. It is likely to be a significant work, as b-matching is a 
      significant extension of the k-anonymity, while being a reasonable 
      alternative to other notions of privacy. Furthermore, this work is very 
      general, allowing for user specified levels of privacy and addressing both 
      the symmetric and asymmetric cases. The only criticism is that theorem 1 
      is quite weak as an approximation factor of the degree makes it nearly 
      useless. I think that an explanation (at least in the appendix) of how the 
      algorithms are a variational upper bound of the ideal program would be 
      more convincing. Minor comments: 191 - 'a more general' -> 
      'a general' 263 - use `` not '' def 4.1 - this is confusing, how 
      does the matching come in to the symmetry notion 
      here