Data published on social networks profiles can be mined for inferring sensitive information about users. For instance it was shown in [10] how musical tastes allow one to predict educational level. To increase user awareness about these privacy threats we have designed a tool, SONSAI, for Facebook users to audit their profiles.The system crawls the network around the user and predicts its sensitive attributes values using a machine learning engine. The results provided by SONSAI, also shows the public attributes of the user that have oriented the learning algorithm towards a particular sensitive attribute value. The user can therefore modify these public attributes to prevent inference.
For the approach to be feasible several problems have to be solved: First, data collection by crawling is limited both by the social network and by country regulations. Hence the crawler exploration strategy has to focus only on meaningful representative network nodes. Since attributes are numerous, for the learning program to scale one has to select only the most relevant ones for inferring sensitive attribute values. Hence the second problem is to find an attribute relevance measure that is both accurate and easy to compute. Note that we cannot rely on semantic proximity since we notice that a user that hides a sensitive attribute probably will hide semantically related ones, too. Moreover for fully anonymised datasets the attributes semantics is hard to recover. Therefore we follow an alternative approach by modelling attributes as bipartite graphs and measuring relevance of attributes by comparing their bipartite graph structures.
For specific attributes such as gender and relationship status, the sets of values are much smaller than for other attributes like music and movie. Consequently, the graphs that model these attributes have higher connectivity than the other graphs. For instance, the density of the graph that models gender (as most users publish their gender) is close to 0.5. In order to infer hidden links in such graphs we need to learn from highly connected graphs. However most of the available learning graphs are sparse. To cope with this last problem, we derive new graphs by merging several learning graphs.
All the proposed methods have been implemented for Facebook, however they can be applied to many other social networks. The system has been tested by several volunteer users for auditing their Facebook profiles. In each case a dataset was built from real profiles collected in the user neighborood network.
Related works. In [15] the authors propose algorithms to detect whether a sensitive attribute value can be infered from the neighborhood of a target user in a social network. Heatherly et al. [12] infer attribute values in social network with bayesian classification techniques. For the same purpose Estivill-Castro et al. [7] employ decision-tree learning algorithms. In these works learning is performed off-line on large datasets. In order to perform attribute inference from sparser datasets collected in short time by our tool user in his ego-network, we rather use randow walk-based learning. The random walk technique has been applied to social representations in [14] and [11] where the authors analysed friendships and used a skip-gram model. In these works, user profiles that have similar friends will be mapped to similar representations. This model helps to detect communities and can predict a set of potential friends for a given user profile. Skip-gram model has also been applied recently to infer social relationship from mobility data [5]. Our work uses a more adapted Continuous Bag of Words (CBOW) model to predict the most likely values for a user sensitive attribute. In our setting friends are considered as an attribute among others. Moreover we first determine automatically a relevant subset of the social network for optimizing random walks. In [3] the relevance of attributes is computed by Bayesian optimisation which is much less efficient than the graph comparison approach adopted here. In particular [3] does not succeed in reasonable time (on standard PC) with attributes like gender and relationship status. Let us note that (unlike [1]) our approach does not need any ontology to perform semantic correlation between attributes. Finally we notice that the proposed system SONSAI is close under some aspects to a recommendation system: an item suggestion can be viewed as an attribute value prediction [4]. However unlike recommendation systems SONSAI also provides explanations for the predicted values, namely an ordered list of attributes that have played a significant role in the computation. For enforcing privacy, our final goal will be to reduce the "recommendation accuracy" by acting on this list of attributes. The architecture of SONSAI is overviewed in Figure 1. The Facebook crawler (about 5k lines of Java 8) drives a Firefox 58.0b4 navigator through a Selenium 3.5.3 server 1 . Collected information from each profile, group and page are stored in separated XML files. The Anonymizer, Cleanser, Random walker and Ranker components are written in Python 2.7 (about 2.5k lines of code). The Anonymizer component parses all the XML files, generates anonymized graphs and stores them as TSV files. Then, the Cleanser selects the most relevant graphs and stores them as adjacency lists. The Random walker component browses the adjacency lists and stores the resulting walks in a text document. We use the Python gensim 2 implementation of Word2Vec to parse the text document and compute a vectorial representation of social network nodes encountered in the walk. Finally, the Ranker component classifies the sensitive nodes according to their similarity to the target user profile.
We have designed a crawler that explores the social network around a user (to some distance given as a parameter) and collects public information from the visited web pages (i.e. friends, liked pages . . . ) in order to build a representative subnetwork. We distinguish two types of Facebook nodes: user profiles (u) and pages (p) and two types of links: like-ships between user profiles and pages, and friendships between user profiles. Given a node π, π.π denotes the set of nodes that are linked to π. A discovered node is a node whose URL is known by the crawler. For instance, if the crawler retrieves a user profile and collects its public friends list, then all the friends of that particular user profile are discovered. Algorithm 1 crawls at most ππ nodes at distance β€ π from the target node π’π‘. Each iteration of the outer loop samples a node, crawls it and update the sets of discovered and crawled nodes. The sampling is done by random walks of length β€ π with a transition probability π designed to crawl with higher priority closer nodes and to favour neighbour nodes according to their type. Function sinks(π) returns the set of sinks, i.e. crawled nodes such that all discovered nodes at distance β€ π are also crawled. Sinks are avoided by the random walks to guarantee that the final node has not been crawled yet.
Modelling friendship relations. Since friendship on Facebook is symmetric, we model friendship between user profiles by an undirected graph (π, πΉ ) where π is a set of users' profiles and πΉ is a set of friendship links between them.
Modelling page like-ship. We model like-ship between user profiles and pages by several bipartite graphs (π, π, πΏ) where π is a set of users profiles, π is a set of pages (a type) and πΏ is a set of like-ship links between them. Figure 2 shows an example of page like-ship modelled by two graphs 3 . Graph (π) models liked pages of music type and Graph (π) models liked pages of book type. We note that user profiles can like several pages of the same type. Anonymizing the social network graphs. For ethical and regulation reasons Facebook identifiers are replaced by fresh identifiers. Each node in the network is then identified by a unique integer ID replacing its Facebook ID. The anonymized IDs are sorted according to the node types. Anonymized graphs are saved under the tab-separated value (TSV) format, one of the most general delimiterseparated values format (DSV). TSV is widely used in graph exchange. In contrast to the dataset released by Netflix 4 where only user IDs are anonymised (but not movies title, rating, date of rating), all attribute values are anonymised in our datasets.
In the following a sensitive graph is a graph that models an attribute that is considered sensitive by the user (i.e. the user does not want its value to be predictable). The learning graphs are attribute graphs available for the learning module in order to predict hidden links in the sensitive graph.
The task of predicting a sensitive attribute from the other ones is made difficult by the size of datasets. Therefore, we suggest to apply the inference process only on a subset of most relevant attributes for the task. Our relevance notion does not rely on semantic proximity since we noticed that i) a user that hides a sensitive attribute will probably hide other semantically-related attributes, and moreover ii) for fully anonymised datasets the attributes semantics is hard to recover. On the contrary we will rely on comparing attributes graph structures. In the following we assume a fixed sensitive graph π .
Step 1: Computing the learning and the confidence rates of learning graphs. In order to compare the structure of a given learning graph to the structure of the sensitive graph, we first split each graph in two parts. The first part contains user profiles that hide their links in the sensitive graph. The ratio of user profiles that publish their links in the first part of the learning graph represents the learning rate ππ. The second part contains user profiles that publish their links in the sensitive graph. The ratio of user profiles that publish their links in the second part of the learning graph represents the confidence rate ππ.
The function connected_profiles_in() returns the set of user profiles that publish their links in the graph given as argument. Given π, π respectively a learning graph and a sensitive graph and π the set of user profiles in all graphs, we define:
depicts an example of splitting two graphs for comparison. The graph that models the link-ship between user profiles and pages of politicians is the sensitive graph. And the graph that models the link-ship between user profiles and pages of musics is the learning graph. The learning rate ππ for this example is equal to 50%. And the confidence rate ππ is equal to 75%.
Step 2: Computing the distance between a learning graph and the sensitive graph. In this step, we discard user profiles that have a null degree in the learning graph or in the sensitive graph. The Jaccard index between two user nodes 4 https://www.kaggle.com/netflix-inc/netflix-prize-data π’1 and π’2 in a given graph π΄ is computed as follows, where the function πππππ π΄(π’π) returns the set of nodes to which user node π’π is connected in the graph π΄.
The Hamming distance π» between graphs π and π is defined by:
In order to compare learning graphs with different sets of common connected profiles π π β© π π , we normalize this distance by the maximal Hamming distance that can be obtained on such a set. Hence we define the Hamming rate:
Step 3: Selecting most relevant graphs for learning sensitive attribute values. We first discard the learning graphs that have a learning rate ππ lower than threshold π ππ since they do not convey enough information. We then discard the graphs that have a confidence rate ππ lower than πππ since they are considered as unreliable. Finally, from the remaining graphs we only select graphs that have a Hamming rate βπ higher than π βπ since they are the most similar to the sensitive graph.
For some sensitive attributes such as gender, age and relationship status, user profiles are linked to at most one value. Moreover the sets of values for these particular attributes are much smaller than for other attributes. Consequently, the graphs that model these attributes are denser than the other ones. In this case, for improving the random-walk based learning process (see Section 6) we need to merge several learning graphs in order to obtain a denser one. We explain the method with a simple example of gender prediction: we select attribute graphs with high ππ, ππ rates but with also a good rate of discrimination between genders, that is the gender of connected users in the graph is unbalanced between male and female. For instance we can select jewelry and fast-food graphs. We merge these graphs by grouping all fast-foods in a unique node and similarly for jewelries as shown in Figure 4 to obtain a new learning graph.
Representation generation. We plan to translate latent information from the selected graphs (in previous section) to a document. The resulting document holds information about paths in the graphs and their frequencies that can be exploited for infering proximity of a user node to some sensitive attribute value node. Following [14], paths in the social graph are sampled by random walks. In our case, the walks are executed only in the subset of selected graphs.
Let πΊ1, πΊ2, . . . πΊπ be the list of selected learning graphs.Let π be the set of users in all graphs. We assume that the friendship graph is selected and πΊ1 = (π, πΉ ) (otherwise we can simply adapt the computation below). The other graphs are bipartite and we pose πΊπ = (π, ππ, πΏπ) for π > 1.
We introduce quotas to quantify the importance of each graph πΊπ for inferring secret values of the target sensitive attribute. Each selected graph πΊπ is assigned a 3 dimensional vector
The quota of πΊπ is given by its Mahalanobis distance to the null vector [0,0,0]. It is computed as follows:
ππΊ π with Ξ£ the 3 Γ 3 covariance matrix over the set of selected graph vectors.
To specify the random walk transitions we first define the probability ππ’,π¦ that being in node π’ the next node in the random walk is in a selected graph πΊπ¦:
where ππππ₯(π’) is the degree of user π’ in graph πΊπ₯. A value node π£ is followed by a user node chosen uniformly at random from the ones connected to π£. Assuming the node following user node π’ is in πΊπ¦, then it will be chosen uniformly at random from the nodes in πΊπ¦ that are connected to π’. Therefore, the transition probabilities are (πΊ1 is the friendship graph): As illustrated in Figure 5 the document is constructed by connecting all graphs through random jumps between their nodes (see also [14]). At each step the walker state changes and a new word is written in the text document. One step amounts to select a graph where the current node occurs with non null degree, and then to select a node that is connected to the current node in the selected graph. The selected node then becomes the new current node.
In this example we aim to predict liked pages of politicians masked by user profile π’3. The sensitive graph is Graph 2 and the learning graphs are Graph 1 and Graph 3. Since the values of the sensitive attributes (the pages of politicians) are labelled (each value belongs to a unique cluster), they are represented by the label of their clusters in the final document. We use a greedy clustering algorithm [3] to define size similar clusters. Pages of politicians that share many common "likers" end up in the same cluster. For instance the first walk depicted by Figure 5 is [π’1, π’4, π£2,3, π’4]. But for efficiency the walk [π’1, π’4, π2,2, π’4] is stored instead in the document since the value π£2,3 belongs to the cluster π2,2.
Applying word2vec to compute node representations. We have performed multi-graph random walks in the social network and generated a text document. Walks in the document can be interpreted as sentences, where the words are network nodes. Hence, inferring a link between a user node and an attribute value node is similar to the problem of estimating the likelihood of words co-occurrence in a corpus. We use word2vec [9,13] to map one-hot encoded vectors that represent words in a high-dimensional vocabulary space to low-dimensional vectors (see [6]). Word2vec is employed with the Continuous Bag of Words (CBOW) model for predicting a word given its context defined by the π β 1 words surrounding it (π is the window size of the context). Inputs of the model in our case are users and published attribute value. Since there is no order between the attribute values CBOW model is more adequate than Skipgram. The output of the CBOW model is a vector of size π£ representing a probability distribution of co-occurrence between all the words of the context and each word from the vocabulary within a window of size π.
Ranking sensitive attribute values. We measure semantic similarity between two nodes by the cosine of the angle formed by the vectors representing the nodes. Cosine similarity is known to take greater account of context information. We rank all the sensitive values by their cosine similarity to the target user profile. The values that have the lowest rank are most likely the sensitive attribute secret values of the target user profile, where secret values are actually the true values of the target user but are not published by him on the social network.
The Figure 6 depicts an example of 2-dimensional vectors that encode 8 nodes: 3 user profiles (π’1, π’2 and π’3), 2 pages of musics (π£3,1 and π£3,2) and 3 clusters of pages of politicians (π2,1, π2,2 and π2,3). The clusters of the pages of politicians are the sensitive values and their vectors are red. The node π’1 is the target user profile and its vector is blue. The clusters of pages of politicians will be ranked according to their distances to π’1. And the inference algorithm will infer as most probable pages of politicians to be liked by π’1, the pages of politicians of the cluster that has the smallest rank (the closest cluster to π’1).
In [16] Schakel et al. show that word2vec unsupervised learning algorithm encodes word semantics by affecting vectors in the same direction for co-occurrent words during training. Besides, the magnitude of a vector reflects both the frequency of appearance of related words in the corpus and the homogeneity of contexts. Where a context is a set of words that have high co-occurrence probability in the corpus.
In fact, the words that appear in the same contexts have small angular distances between them. The less overlapping the contexts are, the larger the angular distances between their different words are. However, words that appear in many contexts are represented by vectors that average vectors pointing in many contexts directions. Hence, the vectors magnitude generally decreases with respect to the number of contexts. Moreover, the higher the word frequency is, the higher the chance that it is used in different contexts is. Consequently, the vector magnitude also decreases with respect to frequency. From these remarks, we conclude that the euclidean distance is not a good measure for our inference purpose. Actually, words that appear in many contexts have low magnitude. As a result, their euclidean distances will be small and, using this criteria, they would be considered close even if they do not appear in any common context. For instance, the euclidean distance between the cluster of pages of the most popular politicians will be small even if they are rivals. In the example depicted by Figure 6 the politicians of the clusters π2,1 and π2,2 are rivals. The angular distance between those two clusters is big. However, the euclidean distance is small. Moreover, the euclidean distance between a user that has many friends, for instance the user π’1 in the Figure 6, and a popular music like "despacito", for instance the page of music π£2,1 in the Figure 6, will be small. But popular users do not necessarily like popular musics.
To build datasets we have crawled Facebook profiles of people that live in North-East France and in Γle-de-France (Paris). Table 1
From each node π we perform a random-walk of 800 steps. The dimension of the node representation is taken to be 512. The dimension is usually taken between 100 and 300 for natural languages. However the size of the vocabulary in social networks (equal to the number of nodes) is much higher than in natural languages.
In Dataset 1 the sensitive graph represents the links between 2554 user profiles and 4589 politician pages. For each experiment we generate a new social graph from the dataset by selecting the user profiles that publish their preferences concerning the sensitive attribute (pages of politicians) and at least another attribute. Then we remove all the links in the sensitive graph of 10% of the selected user profiles. The algorithm makes sure that all the nodes in the resulting social graph remain connected. The experiments have consisted then in inferring the hidden links based on information from the learning graphs.
Among the 1928 learning graphs, we selected the ones with learning rate greater than π ππ = 20%, confidence rate greater than πππ = 60% and Hamming rate lower than
Table 2 We note that the communities graph has the second greatest learning rate ππ = 44.97%, which means that it holds much latent information about users who hide their likes in the sensitive graph. It also has the maximal confidence rate ππ = 98.47 and the fifth lowest Hamming rate (βπ = 1.75%) among the 23 selected relevant graphs, which means that its structure is very similar to the structure of the politicians graph. The friendship graph (Users) has the maximal learning rate ππ = 88.37% and a high confidence rate ππ = 83.98% since 87.62% of users are connected to this graph. However, this graph has a Hamming rate βπ = 2.08% greater than the average βπ of selected graphs which means that learned information from this graph is less reliable than learned information from the communities graph.
We use the area under the ROC curve (AUC) as defined in [8] to measure the accuracy of the inferred links. For the defined thresholds (π ππ = 20%, πππ = 60%, π βπ = 4%) the precision is equal to 0.79. However, the inference accuracy when the 23 relevant graphs are selected randomly is only 0.41. We conducted more tests by selecting manually 3 graphs that are semantically close to politics as follows. Graph πΊ1 models the links between 1246 user profiles and 2357 political organizations, πΊ2 models the links between 1120 user profiles and 1758 political parties and πΊ3 models the links between 39 user profiles and 41 political ideologies. Although the selected graphs seem promising, the inference accuracy is only 0.46. This can be explained by the fact that the selected graphs are very sparse and users are vigilant when publishing their preferences about those attributes. Consequently, the algorithm cannot learn well from them.
We note that the musicians/bands graph was automatically selected by our relevance-based selection method confirming that music and politics are correlated as it was empirically discovered in previous studies [17],
Table 3 summarizes the results of the conducted experiments.
To produce a text document from the social graph, we perform random-walks of 80 steps. Each random walk starts from a different node. The dimension of the node vectorial representation is taken to be 128 since in that case the number of sensitive values is smaller. Moreover learning graphs are obtained by grouping several attribute values in the merging operation (see Section 5). For the experiments, we have generated a new social graph from the dataset by randomly selecting 10% of user profiles that publish the value of their sensitive attribute and we have masked it. Then SONSAI has tried to infer the masked values of the sensitive attribute for each user based on the selected attributes by the cleanser module.
Relationship status. The sensitive graph models the relationship status of user profiles. To simplify the presentation we define two meta-relationship status as follows: π 1= {ππππππ, π·ππ£πππππ, πππππππ‘ππ, π ππππ€ππ, πΆππππππππ‘ππ} π 2= {π·ππππ π‘ππ ππππ‘ππππ βππ, π ππππππ, πΈππππππ, π ππππ‘ππππ βππ, πΆππ£ππ π’ππππ, ππππ πππππ‘πππ}
We aim to infer the meta-relationship status of users. Table 4 gives more details about the selected attributes from dataset D2.
We notice that discriminant attributes toward π 1 are focused around educations and leisures. On the other hand, discriminant attributes toward π 2 are focused around business. The accuracy in AUC of inferring the metarelationship status is higher than 0.7 in both datasets D1 and D2 as soon as the target publishes values concerning at least 4 selected attributes by the cleanser.
Gender. The sensitive graph models the gender of user profiles. We notice that discriminant attributes toward male are focused around sports, games and software. On the other hand, discriminant attributes toward female are focused around health, home and luxury. The accuracy in AUC of inferring the gender is higher than 0.83 in dataset D1 and higher than 0.67 in dataset D2 as soon as the target publishes values concerning at least 2 selected attributes by the cleanser. Ranking task has to compute cosine similarity between a few vectors that represent the sensitive values and the target user vector. Cleansing task selects most important attributes and reduces the vocabulary. Consequently, this process accelerates the inference tasks (relying on Random walk and Word2Vec). Moreover, Cleansing increases accuracy by discarding irrelevant information.
Let us investigate the impact of the cleansing parameters ππ, ππ and βπ. All experiments detailed in this section are conducted on dataset D1 to infer users' political orientation.
Table 7 shows that only 3 graphs among the 1928 available graphs have a learning rate ππ higher than 30%. Based on those graphs, inference accuracy can be very low. For instance, inference accuracy based on gender attribute is only 0.36. Based only on the users (i.e. friendship) graph accuracy is getting better to 0.64. The communities graph gives high accuracy of 0.74 for inferring political views. However, we notice that the best accuracy is obtained when selecting graphs with learning rate between 10% and 40%. Table 7 shows that the learning rate parameter ππ is important to select the best graphs for inference. However, accuracy does not depend only on this parameter since some graphs such as gender graph that have high learning rate may lead to very low accuracy results.
Table 8 shows that when the Hamming rate βπ decreases, accuracy increases. However, most graphs have a low Hamming rate because only a small part of them can be compared to the sensitive graph, as few users publish their preferences in both graphs. Hence, their structure is not fairly comparable to the politicians' graph structure. To cope with this problem we compute a third parameter, the confidence rate ππ, that indicates how reliable the structure comparison is.
Table 9 shows that the confidence rate, ππ, does not give information about the best graph to select when it is considered isolately but it must be coupled with other parameters. For instance, if a given graph π has a high confidence rate but a low Hamming rate, that means that it is a good graph for inference. However, if a given graph π has a high confidence rate and high Hamming distance rate that means that π is probably a bad graph for infering the sensitive attribute. But a given graph π could be interesting for inference if it has low ππ and high βπ.
SONSAI application enables users to predict their sensitive links in social networks from relatively small amount of data and computing resources. Indeed, sensitive data inferences are fast and accurate on typical personal attributes. It should be noted that the friendship graph was not selected among important ones to deduce both the gender and the relationship status of users. This probably means that alternative techniques based solely on homophily would be inaccurate in this context. Moreover, we have observed that the privacy of users is threatened as soon as they start publishing at least three important attributes. These ones are automatically brought to light by SONSAI, regardless their semantics and only through a structural analysis of the social network graph. As future work, we plan to incorporate countermeasures into our tool to protect users against posts that might compromise their privacy. We also plan to enhance SONSAI prediction engine with a tool that permits one to disclose hidden friendship links using adequate combinations of queries provided by the social network [2].
Acknowledgments. This work is supported by MAIF Foundation 5 .