A Survey on Interdependent Privacy <s> Statistical Inference <s> Since privacy information can be inferred via social relations, the privacy confidentiality problem becomes increasingly challenging as online social network services are more popular. Using a Bayesian network approach to model the causal relations among people in social networks, we study the impact of prior probability, influence strength, and society openness to the inference accuracy on a real online social network. Our experimental results reveal that personal attributes can be inferred with high accuracy especially when people are connected with strong relationships. Further, even in a society where most people hide their attributes, it is still possible to infer privacy information. <s> BIB001 </s> A Survey on Interdependent Privacy <s> Statistical Inference <s> Most tasks require a person or an automated system to reason -- to reach conclusions based on available information. The framework of probabilistic graphical models, presented in this book, provides a general approach for this task. The approach is model-based, allowing interpretable models to be constructed and then manipulated by reasoning algorithms. These models can also be learned automatically from data, allowing the approach to be used in cases where manually constructing a model is difficult or even impossible. Because uncertainty is an inescapable aspect of most real-world applications, the book focuses on probabilistic models, which make the uncertainty explicit and provide models that are more faithful to reality. Probabilistic Graphical Models discusses a variety of models, spanning Bayesian networks, undirected Markov networks, discrete and continuous models, and extensions to deal with dynamical systems and relational data. For each class of models, the text describes the three fundamental cornerstones: representation, inference, and learning, presenting both basic concepts and advanced techniques. Finally, the book considers the use of the proposed framework for causal reasoning and decision making under uncertainty. The main text in each chapter provides the detailed technical development of the key ideas. Most chapters also include boxes with additional material: skill boxes, which describe techniques; case study boxes, which discuss empirical cases related to the approach described in the text, including applications in computer vision, robotics, natural language understanding, and computational biology; and concept boxes, which present significant concepts drawn from the material in the chapter. Instructors (and readers) can group chapters in various combinations, from core topics to more technically advanced material, to suit their particular needs. <s> BIB002 </s> A Survey on Interdependent Privacy <s> Statistical Inference <s> Social-networking users unknowingly reveal certain kinds of personal information that malicious attackers could profit from to perpetrate significant privacy breaches. This paper quantitatively demonstrates how the simple act of tagging pictures on the social-networking site of Facebook could reveal private user attributes that are extremely sensitive. Our results suggest that photo tags can be used to help predicting some, but not all, of the analyzed attributes. We believe our analysis make users aware of significant breaches of their privacy and could inform the design of new privacy-preserving ways of tagging pictures on social-networking sites. <s> BIB003 </s> A Survey on Interdependent Privacy <s> Statistical Inference <s> Location plays an essential role in our lives, bridging our online and offline worlds. This paper explores the interplay between people's location, interactions, and their social ties within a large real-world dataset. We present and evaluate Flap, a system that solves two intimately related tasks: link and location prediction in online social networks. For link prediction, Flap infers social ties by considering patterns in friendship formation, the content of people's messages, and user location. We show that while each component is a weak predictor of friendship alone, combining them results in a strong model, accurately identifying the majority of friendships. For location prediction, Flap implements a scalable probabilistic model of human mobility, where we treat users with known GPS positions as noisy sensors of the location of their friends. We explore supervised and unsupervised learning scenarios, and focus on the efficiency of both learning and inference. We evaluate Flap on a large sample of highly active users from two distinct geographical areas and show that it (1) reconstructs the entire friendship graph with high accuracy even when no edges are given; and (2) infers people's fine-grained location, even when they keep their data private and we can only access the location of their friends. Our models significantly outperform current comparable approaches to either task. <s> BIB004 </s> A Survey on Interdependent Privacy <s> Statistical Inference <s> In the attribute inference problem, we aim to infer users' private attributes (e.g., locations, sexual orientation, and interests) using their public data in online social networks. State-of-the-art methods leverage a user's both public friends and public behaviors (e.g., page likes on Facebook, apps that the user reviewed on Google Play) to infer the user's private attributes. However, these methods suffer from two key limitations: 1) suppose we aim to infer a certain attribute for a target user using a training dataset, they only leverage the labeled users who have the attribute, while ignoring the label information of users who do not have the attribute; 2) they are inefficient because they infer attributes for target users one by one. As a result, they have limited accuracies and applicability in real-world social networks. ::: ::: In this work, we propose AttriInfer, a new method to infer user attributes in online social networks. AttriInfer can leverage both friends and behaviors, as well as the label information of training users who have an attribute and who do not have the attribute. Specifically, we model a social network as a pairwise Markov Random Field (pMRF). Given a training dataset, which consists of some users who have a certain attribute and some users who do not have a certain attribute, we compute the posterior probability that a target user has the attribute and use the posterior probability to infer attributes. In the basic version of AttriInfer, we use Loopy Belief Propagation (LBP) to compute the posterior probability. However, LBP is not scalable to very large-scale real-world social networks and not guaranteed to converge. Therefore, we further optimize LBP to be scalable and guaranteed to converge. We evaluated our method and compare it with state-of-the-art methods using a real-world Google+ dataset with 5.7M users. Our results demonstrate that our method substantially outperforms state-of-the-art methods in terms of both accuracy and efficiency. <s> BIB005 </s> A Survey on Interdependent Privacy <s> Statistical Inference <s> Co-location information about users is increasingly available online. For instance, mobile users more and more frequently report their co-locations with other users in the messages and in the pictures they post on social networking websites by tagging the names of the friends they are with. The users’ IP addresses also constitute a source of co-location information. Combined with (possibly obfuscated) location information, such co-locations can be used to improve the inference of the users’ locations, thus further threatening their location privacy: As co-location information is taken into account, not only a user's reported locations and mobility patterns can be used to localize her, but also those of her friends (and the friends of their friends and so on). In this paper, we study this problem by quantifying the effect of co-location information on location privacy, considering an adversary such as a social network operator that has access to such information. We formalize the problem and derive an optimal inference algorithm that incorporates such co-location information, yet at the cost of high complexity. We propose some approximate inference algorithms, including a solution that relies on the belief propagation algorithm executed on a general Bayesian network model, and we extensively evaluate their performance. Our experimental results show that, even in the case where the adversary considers co-locations of the targeted user with a single friend, the median location privacy of the user is decreased by up to 62 percent in a typical setting. We also study the effect of the different parameters (e.g., the settings of the location-privacy protection mechanisms) in different scenarios. <s> BIB006
We present an important type of statistical inference methods, Bayesian inference: It is extensively used in interdependent privacy scenarios to update the knowledge (probability) about some attribute(s), typically of the target individual, given the observation of other attributes, typically those of other individuals (see examples below). With Bayesian inference, probabilities are interpreted as the quantification of a belief/knowledge; it relies on the Bayes' theorem that links conditional and marginal probabilities: P (attributes | observations) = P (observations | attributes) · P (attributes) P (observations) , where the marginal probability P (attributes) is called the prior and the conditional probability P (attributes | observations) is called the posterior (i.e., the prior updated after making the observations). To efficiently perform Bayesian inference, researchers have developed probabilistic graphical models (PGMs) BIB002 , graph-based models that enable the clear (graphical) representation of conditional or joint (in)dependencies between various attributes (represented by random variables). Bayesian networks are used to represent directed dependencies, i.e, conditional probability distributions between random variables, whereas Markov random fields are used for undirected dependencies, i.e., joint probability distributions between random variables. Hidden Markov models (HMMs) are a special instance of Bayesian networks. Belief propagation BIB003 ] is a well-known message-passing algorithm for performing Bayesian inference on PGMs. The belief-propagation algorithm can be applied to efficiently compute marginal distributions of unknown variables given a set of observed variables connected to them in the underlying PGM. Belief propagation and PGMs jointly allow to reduce the complexity of marginalization from exponential in the number of random variables down to linear (depending on the underlying PGM structure). Figure 1 depicts two concrete models of Bayesian networks that were used in interdependent privacy settings for performing inference on (a) genomic data and (b) location data. Software libraries implementing Bayesian networks operations include bnt (Matlab), 3 Netica (Java, C, C++, etc.), 4 and pgmpy (Python), 5 to name a few. Application to interdependent privacy. The privacy of an individual is often quantified as the error an adversary makes when inferring the values of some of the individual's private attributes. Therefore, statistical inference techniques are widely used in privacy risk assessment. In particular, in interdependent privacy scenarios where statistical dependencies exist between the target individual's data and that of their contacts (e.g., relatives, friends, co-workers), PGMs are very relevant. Many works on interdependent privacy risks assessment rely on Bayesian inference and/or Bayesian networks or Markov random fields (e.g., BIB001 BIB005 BIB006 BIB004 ) (see Section 4 and more specifically Table 2 on page 23).