Abstract

Introduction
User-generated content on social media has led to increased interest in mining actionable patterns from user data (Za- farani, Abbasi, and Liu 2014). This content varies from declaring personal attributes, such as name, gender, and ed- ucation, to sharing ideas, photos, events, and interests. It can be broadly classified into explicit and implicit (Novak and Li 2012). Explicit content is information provided by the user on the social media platform; it can be made publicly avail- able or available to a limited set of users on that platform. In contrast, implicit content is one that the users have cho- sen to withhold from the platform but the platform can infer based on explicit user content and the content in their social networks. Advancements in data mining techniques have led to the development of powerful models that can predict im- plicit user information with good accuracy. Predicting im- plicit user information has many applications, from adver- tising and recommender systems (Ruining He 2018) to un- derstanding health-related behavior (Sun et al. 2019a). While leading to a better and more personalized user ex- perience and improved reach for advertisers, implicit at- tribute prediction has also caused concerns regarding the pri- vacy of users who participate in social networks (Lee Rainie 2018). Multiple studies have shown that it is possible to reli- ably infer sensitive information from publicly available data (Zheleva and Getoor 2009; Lindamood et al. 2009; Kosinski, Stillwell, and Graepel 2013; Garcia 2017), leading to sensi- tive attribute disclosure (Zheleva, Terzi, and Getoor 2012). In the absence of rules and guidelines on how to ethically perform such predictions, or how much of it is even accept- able, individuals, companies and government entities can ap- ply machine learning models on public data for classification and prediction of user behaviour without the explicit per- mission of the users themselves. Solutions such as allowing users to hide their own information have only been success- ful to a limited extent, due to the fact that these models also take into account the data generated by other users in the network. A natural question one can ask is whether users have any power over protecting their own private informa- tion from being predicted accurately. We propose a user-centric solution that can help users have more control over the prediction of their sensitive at- tributes. We take an adversarial learning approach and de- vise an algorithm, Outwit, which can suggest to users what explicit content to change on their social network profiles, in order to mislead predictive algorithms. Unlike a typical ad- versarial scenario in which the adversary is the person trying to mislead the predictive algorithm, we assume that the pre- dictive algorithm itself is the adversary because it is trying to infer a sensitive attribute. We focus on graph data and as- sume that the predictive algorithm uses graph convolutional networks (GCN) for sensitive attribute prediction. Outwit's goal is to mislead the predictive algorithm and help a user protect their privacy. As such, Outwit falls un- der the umbrella of evasion attacks in which contaminated test data is introduced, in Outwit's case the perturbed data of an individual profile. Unlike existing evasion attacks for GCN (Dai et al. 2018b; Wang and Gong 2019) which require the content of multiple profiles to be perturbed, we consider realistic constraints which assume that 1) a user has control over changing their own content only and not the content of other users and 2) that they are willing to change some attributes and relationships but not others.
Table 1: Comparison between Outwit and other adversarial algorithms for node classification. Our main contributions are: ● Framing a new privacy problem of user-centric adversar- ial perturbations with utility constraints. ● Proposing a realistic "grey-box" scenario in which the model type of the predictive algorithm is known and the algorithm parameters can be estimated using publicly available data. ● Developing a new gradient-based algorithm which finds the minimum number of node attribute and edge changes necessary to get the sensitive attribute misclassified while satisfying the utility constraints. ● Showing empirically that our solution leads to 8 – 25% absolute accuracy decrease over a state-of-the-art adver- sarial algorithm with as few as 6 edge deletions.
Related work
Friendship links and group affiliations can leak a surpris- ingly large amount of sensitive data about individuals (Zhel- eva and Getoor 2009; Lindamood et al. 2009; Kosinski, Stillwell, and Graepel 2013) There has been an increas- ing interest in personalized privacy assistants that can help users manage their privacy online (e.g.,  (Fang and LeFevre 2010; Ghazinour, Matwin, and Sokolova 2013; Wisniewski, Knijnenburg, and Lipford 2017)). Meanwhile, the use of graph neural networks has increased in popularity recently (Gori, Monfardini, and Scarselli 2005; Scarselli et al. 2005, 2009a,b; Li et al. 2016), posing threats to personal privacy. However, none of the personalized privacy assistant studies consider user-centric adversarial approaches to combat the predictive power of neural network algorithms, as we do in this work. The goal of adversarial attacks is to mislead machine learning models by either introducing misleading examples during the testing phase (evasion attack)(Dai et al. 2018a; Wang and Gong 2019), contaminating the training data with malicious examples (poisoning attack)(Zügner, Akbarne- jad, and Günnemann 2018; Sun et al. 2019b, 2018; Chang et al. 2019b) or by learning about the model it is trying to mislead as much as possible (exploratory attack) (Big- gio, Fumera, and Roli 2014). Adversarial learning in graphs is fairly new (Zügner, Akbarnejad, and Günnemann 2018; Dai et al. 2018a; Sun et al. 2018). Dai et al. (Dai et al. 2018a) demonstrate a black-box evasion attack assuming GCN (Kipf and Welling 2017) as the node classification model. The model is allowed to add or delete edges from the graph but node features remain unchanged. Dai et al. also propose a gradient-based white-box attack algorithm which is closest to our work and we use as a baseline. In contrast to their greedy combinatorial approach, we use the magni- tude of the gradients along with the degree of the nodes to find optimal perturbations. Zügner et al. (Zügner, Akbarne- jad, and Günnemann 2018) focus on poisoning attacks, also using GCN (Kipf and Welling 2017) as the target model but without preserving its non-linearity. The attacker is allowed to manipulate the graph structure as well as the node fea- tures while preserving important graph characteristics (de- gree distribution and feature co-occurrences). Sun et al. (Sun et al. 2018) present a poisoning attack against unsupervised node embedding methods. The goal is to either change the similarity score of a target node pair, or to affect the link prediction accuracy of a test set by adding or deleting edges. Wang et al. (Wang and Gong 2019) optimizes attack tar- geting Linearized Loopy Belief classifier in order to evade detection via manipulating the graph structure resulting in increase of False Negative Rate. Table 1 summarizes the differences between these approaches and ours. To the best of our knowledge, we are the first ones to consider feature perturbations for evasion attacks and to use graph deriva- tive mapping between node features and class labels for de- termining feature perturbations. While other white box eva- sion models (Dai et al. 2018b) greedily add and delete edges based on the gradient information, we use the gradient infor- mation to first find the dominant nodes in the graph and then make changes to the target node's edges.
Preliminaries
Data model
We represent the social network as an undirected graph. The users in the network are represented by nodes and their profile information is represented by the attributes or fea- tures of the nodes. Relationships, such as friendships or fol- lowing relationships, are represented by edges between the users. Formally, let G = ( A, X ) be an attributed undirected graph where A ∈ {0,1} N×N is the symmetric binary ad- jacency matrix representing the relationships between the users, X  ∈  {0,1} N×D  represents the binary nodes' fea- tures, N represents the number of users and D represents the number of node features. We denote the D-dimensional feature vector of node i as X i ∈ {0,1} P . We assume the node ID to be N = {1,2,...,N} and feature-ids to be {1,2, ..., D}.
Target classifier
We assume that there is a target classifier that is used to predict missing (and potentially sensitive) attributes on user profiles, in order to target users based on hidden character- istics. This classifier can be built by the company behind the social network or third parties with access to the social net- work data. The target classifier performs node classification and it considers a partially labeled graph G L = ( A, X, Y L ), where YL are nodes with explicit labels. If there are C classes, we assume the class labels to be C = {1, 2, ..., C}. Given this partially labelled graph G L , the task of the tar- get classifier is to find an optimal function f : N → C which maps each node i ∈ N to a single class in C in or- der to correctly classify the unlabeled nodes. Since we have the complete A and X , the features and edges of unlabelled nodes (test nodes) in the graph G L are known and are part of the training data hence this corresponds to a transductive learning scenario (Chapelle, Scholkopf, and Zien 2009). Graph Convolutional Networks (GCNs) have achieved state-of-the-art results on node classification tasks hence we assume that the target classifier is based on GCN by Kipf and Welling (2016) (Kipf and Welling 2017). GCNs use spec- tral graph convolutions in which filter parameters are shared over all locations in the graph. A single layer in this model is a non linear function of the form:
where H (0) = X , K is the number of layers and W is train- able weight matrix. The model uses ReLU as the non-linear activation function; the adjacency matrix A is normalized for faster computation. The final model is a 2-layer neural network with the following propagation rule -
where W (0) ∈ RD×H is an input-to-hidden weight matrix for a hidden layer with H feature maps. W(1) ∈ RH×C is a hidden-to-output weight matrix. The softmax activa- tion function, defined as softmax(h i ) =  Hexp(h i ) with Z =  E i exp(h i ), is applied row-wise. To optimize node classification, cross-entropy error is used as loss over all la- beled examples

Information available to the adversarial algorithm
The goal of our adversarial algorithm is to perturb the graph attributes of a focus node in a way that makes the target clas- sifier predict poorly the node's sensitive attribute. There are two types of information that the adversarial algorithm has access to: 1) information about the target classifier, and 2) user attributes and edges that adversarial algorithm has the power to perturb. Adversarial attacks can be classified into two main groups based on the amount of target classifier information accessi- ble to them: ● White-box attack : The algorithm has access to the tar- get classifier predictions and to its model parameters (Dai et al. 2018a; Sun et al. 2018). ● Black-box attack : The algorithm has access only to the predictions of the target classifier (Chang et al. 2019a; Zügner, Akbarnejad, and Günnemann 2018; Dai et al. 2018a; Bojchevski and Günnemann 2019). Here we introduce a third type of attack which we call Grey-box attack . In a grey-box attack, the adversarial algo- rithm does not have access to the actual target model but has partial access to the training nodes of the target classifier and their true labels. Therefore, it can estimate the param- eters of the target model based on this data and make node label predictions using the estimated model. Grey-box at- tacks are more practical than white box attacks because the adversarial algorithm is unlikely to have access to the target classifier parameters but can estimate them based on pub- licly available data. At the same time, black box attacks are rather limited in their capabilities and are known to perform much worse than white-box attacks (Dai et al. 2018a). Our work assumes a grey-box attack and that the adversar- ial algorithm has access to true class labels for some nodes in the graph to train the estimated classifier. We also make the practical assumption that the only information that the adversarial algorithm can change is the focus node's own attributes and friendship links. This user-centric approach is one of the main distinguishing characteristics of our setup as compared to current adversarial algorithms on graphs which assume that they can perturb multiple nodes' profiles at the same time (Zügner, Akbarnejad, and Günnemann 2018; Dai et al. 2018a; Bojchevski and Günnemann 2019; Chang et al. 2019a; Sun et al. 2018; Zügner and Günnemann 2019; Wang and Gong 2019; Sun et al. 2019b; Chang et al. 2019b).
Privacy protection problem
Adversarial Perturbations
The task of the adversarial algorithm is to modify the profile information and relationships of a target user t in the social network such that the target classifier f cannot predict the true class label of t . Since f 's parameters are unknown, we estimate a classifier f trained on a partially labelled social network graph G L . Let Ã be the graph after the adversar- ial algorithm is applied, X td ∈ {0, 1} and ∑ td ∈ {0, 1} be the values of feature d for target node t before and after the perturbation, A ti  ∈  {0,1} be a binary value representing whether an edge exists between node t and node i , and let the constants γ, δ ∈ Z > 0 represent the maximum number of changes that are allowed to be made to the feature vector and edges respectively for node t . Given the classifier f and (G t , Y t ) where G t is the graph visible to the target node t and Y t is the true class of t , the task of the adversarial algo- rithm g : G → Ğ is to modify the graph G = ( A, X ) to Ğ = (Ã, Ã) such that:
The constraints ensure that the adversarial algorithm does not drastically modify the target node and that the changes it makes are unnoticeable. These perturbations will allow a so- cial network user to change their profile and safeguard their sensitive attributes from machine learning predictions. The computational complexity of training the estimated model and finding the features and nodes that are most help- ful in prediction is O ( EHDC ) (Kipf and Welling 2017) where E = ∑ i=1,j=1 A i,j > 0 is the number of graph edges. The computational complexity to find edge pertur- bations is O ( E t + D ) where E t is the degree of target node and the complexity to find the optimal feature perturbation is O ( D ). Hence the complexity to find both feature and edge perturbations for a target user is O ( E t + D ).
Utility-constrained Perturbations
There is a utility cost associated with hiding or changing attributes on social media. For example, a user may not be willing to declare a different gender from their real gender online or unfriend their spouse, in order to impact the accu- racy of predicting another, sensitive attribute. A user may be more willing to agree to change favorite foods and movies or to "unfriend" an elementary school classmate. Therefore, there is a cost to changing some attribute and our algorithm needs to take this cost into consideration. We define user- specific feature utilities as U = RN×D such that a high util- ity U i d corresponds to user i being less willing to change feature X i d . In order to account for feature utilities in deciding which features to change, we add a utility constraint to our prob- lem. The utility-constrained adversarial algorithm is allowed to change only those attributes whose user utilities are below a certain threshold. The following is the final optimization problem with utility constraints:
where U td is the utility of the feature d for node t , V ij is the utility of the edge between node i and j, η and μ are the thresholds below which the features and edge are allowed to be modified respectively.
Adversarial, user-centric privacy protection
Here, we present Outwit, our algorithm for solving the pri- vacy protection problem through adversarial perturbations, targeting Graph Convolutional Networks. Given a graph G and a target classifier f , our goal is to protect the privacy of a target user t by performing a small number of perturba- tions on their profile leading to the graph Ğ , such that t gets misclassified by f . Outwit has two types of perturbations: feature perturbations and edge perturbations that we de- scribe next. To the best of our knowledge, we are the first ones to consider feature perturbations for evasion attacks and to use graph derivative mapping between node features and class labels for determining feature perturbations. As far as novelty in the edge perturbations, other white box eva- sion models (Dai et al. 2018b) greedily add and delete edges based on the gradient information but we use the gradient information to first find the dominant nodes in the graph and then make changes to the target node's edges.
Feature perturbations
Given the estimated node classifier f , Outwit finds the the node's attributes most likely to cause the change to the pre- diction in the target classifier. In order to do so, it looks at aw(๑) , the gradient of the loss in the final layer with respect to the weights in the first layer:
hence the output of the first layer H (0) is Â X W (0) . Be- cause weight vector W ( 0 ) is being multiplied with X this gradient indicates the importance given to different features in the nodes. There are H spectral filters in the first hid- den layer of our GCN i.e. W(0) = RN×D , hence there are H gradient vectors, each associated with one of the filter parameters. Each of the spectral filters focuses on specific features to pass to the next GCN layer. Outwit makes a list of all such features in decreasing order of the magnitude of their gradients and select the top features. Then it finds the association of these features with one of the class labels. For each node in the labeled set Outwit finds the distribu- tion of class labels with respect to the feature. For all such features in our final list, it finds one class or at most a combi- nation of two classes to have a much higher frequency than the remaining classes.
where X is a particular feature. Then Outwit creates a map- ping for the classes and the features associated with them. Given a target node, the top γ features associated with the true class of this node which are visible to the classifier f are set to 0. Then Outwit uses the list of mappings between features and the classes to select specific features from these mappings that are associated with a class other than the tar- get user's true class. These features are changed to 1 if they were 0 before, until reaching γ perturbations, the upper limit of allowed feature perturbations.
Edge perturbations
Edges between nodes in a graph play a prominent role in node classification. The target GCN model can predict the target node's label with considerable accuracy even when none of the features from the test set are revealed to it (refer to Table 4 in Section 29) by using labels from the neighbour- ing labeled nodes. It is thus important to find these dominant neighboring users in the target user's neighbourhood and re- move the connections to them, in order to decrease the con- fidence of the classifier towards the target node's true class
edges represented by A , the adjacency matrix. Some of the edges have a larger gradient magnitude than others which suggests that these edges provide significant information to their neighbouring node in the aggregation process of graph convolution. Outwit orders all node pairs (edges) in decreas- ing order of their magnitude of gradient. The users repre- sented by nodes with a significantly large frequency of oc- currence are the best classification contributors in the graph, they pass their class label information to their neighbouring nodes. Outwit maintains a mapping of all classes to these dominant nodes. Outwit scans all the edges of the target user in the order of decreasing gradient and connections to the top δ nodes that have the same class as the target node's true class are removed. It is also possible to connect the target node to dominant users in G L , in order to increase the confidence of the node classifier towards the class label of these dominant nodes. Outwit finds the dominant users from the class other than the target user's true class and adds edges between the target node and these dominant nodes until it reaches the constraint of maximum edge perturbations δ . Dependent on the plat- form, edge addition perturbations can be harder to achieve than edge removals. For example, it is a lot easier to add a link to someone when reciprocity of relationship is not re- quired (e.g., follower relationship on Twitter) versus when it is required (e.g., friendship relationship on Facebook).
Utility-constrained Outwit Algorithm
To protect privacy, Outwit perturbs information on user's profile as described in the previous subsections. The input to the Outwit algorithm is a partially labeled graph G L , a target node t and its true class label Y t . The output is Ã such that the target user profile information is perturbed. Before it begins, it trains the GCN classifier f according to Equa- tion 2 to obtain trained weights W ( 0 ) and W ( 1 ) . Algorithm 1 shows the pseudo-code for Outwit which first looks for fea- tures to perturb (Lines 8 – 18). It finds the gradient of loss L of f with respect to W (0) . It looks for the most important feature in every spectral filter h ∈ H and stores them in the f eatures variable (lines 10 – 12). These features represent the most important attributes of the user profile as these help the classifier to identify the node's class. But what is the re- lation between these features and different classes? Which feature combinations help the classifier to predict a certain class? Lines 13 – 15 try to find exactly this. For each of the important features in the variable features , Outwit maps them to a class in feature map variable. Now that Outwit has the most important node features and their relation to the class labels, it changes the feature to decreases the con- fidence of node classifier prediction towards y and increase the confidence towards other classes for our target user node (lines 17 – 18). Then it finds edge perturbation for the target user t (lines 20 – 27), starting by finding the gradient of loss L with respect to A , adjacency matrix. Outwit finds the users which are most dominant in passing their class labels to their neighbours in the GCN aggregation phase (lines 20 – 25). Now that it has the dominant nodes in the graph, Outwit removes the edges to dominant nodes whose class label is same as target node's class y and add edges to dominant nodes from other class in (lines 26 – 27). This, combined with the feature perturbation, will outwit the target classifier Algorithm 1: Outwit Algorithm Input: 1 2 3 4 s 7 Graph G L = (A, X, Y L ) Target node t and it's true class Y t Utility U Output: Perturbed graph Ğ = ( Ã, Ã) 6  Train f on G L to obtain W (0) and W (1)
*/ s  features = [] 9 gradientw = aWill 10  foreach h ∈ H do if U [ t ][d] ≤ η then 11 features ← sort_descending(d, key = 12 gradientw[h][d]) 13  feature_map = [] 14  foreach d do distribution = class_distribution( d ) 15 feature_map ← (d, index(max(distribution)) 16 17 Set top γ features of t to 0 from feature map where class = y 18 Set top γ features of t to 1 from feature map where class ≠ y 19 /* Edge Perturbations */ 20 gradient A = dC 21  edge_grads ← sort_descending(e, key = gradient A ) n node_frequency ← [] 23  foreach (n1,n2) ∈ edge_grads do | node_frequency ← frequency(n1,n2) 24 25 sort(node_frequency) 26  Remove top δ edges from G such that t ∈ ( · , · ) and // Equation 4 the node class = y 27  Add top δ edges to G such that t ∈ ( · , · ) and the node class ≠ y 28 29 Return G
Experiments
Datasets
We consider three citation network datasets, Citeseer (Lu and Getoor 2003), Cora (Lu and Getoor 2003), and Pubmed (Sen et al. 2008), together with one Twitter retweet net- work (Ribeiro et al. 2018). Dataset statistics are summa- rized in Table 2. We treat each scientific paper as a node and the citation links as (undirected) edges between them. The Cora and CiteSeer datasets consists of sparse 0/1-valued bag-of-words feature vectors for each document indicating the absence/presence of the corresponding word in the doc- ument and a list of citation links between them. Each publi- cation in the the Pubmed diabetes dataset is described by a TF/IDF weighted word vector from a dictionary which consists of 500 unique words. The Twitter node features are spaCy's off-the-shelf 300-dimensional GloVe's vector along with few profile attributes and manual annotation whether a user is hateful or not. The features are averaged across all words in a given tweet, and subsequently, across all tweets a user has. Because these features are not binary, we apply only edge perturbations to this dataset and not feature ones.
Table 2: Dataset statistics.
Experimental setup
Our target model for the node classification task is a Graph Convolutional Network from (Kipf and Welling 2017). The model is trained with a 2-layer GCN. The model hyperpa- rameters such as number of epochs, layers and hidden units, learning rate and dropout rate are kept the same as in (Kipf and Welling 2017). We show results of the Outwit algorithm with equal utility and various settings of δ and γ ranging from 6 feature per- turbations, 2 edge perturbations to 20 feature perturbation, 8 edge perturbations. To fairly compare with the baseline al- gorithms, we also run experiments with edge perturbations only with varying amount of δ from 2 to 8. We test our algo- rithm with varying utility distribution with range values for α and β . As we know that the user has no control over the amount of information that is publicly available to train the model, we run experiments with different ratio of training dataset varying the set of labelled nodes in training set from 10% to 100%.
Baselines
We use Dai et al.’s (Dai et al. 2018a) and Wang et al.’s (Wang and Gong 2019) white-box models as baseline models in our experiments and adapt them to the user-centric, grey-box as- sumptions of our privacy protection scenario. Because (Dai et al. 2018a) and (Wang and Gong 2019) don't perturb fea- tures, a fair comparison requires to show results after edge perturbations only. We also consider simple feature pertur- bations as baselines, such as setting all the target node fea- tures to zeros, to ones and random. For simple edge per- turbations we use random edge rewiring to change the links between the nodes. Table 4 shows classification accuracy for the simple perturbations. The row "unperturbed" shows the result for f . As we can see the average accuracy drops very little for both simple feature and edge perturbations which makes Outwit's task very challenging.
Results
Target node perturbation   Figure 2 shows the classifica- tion performance of the target model when perturbing one node at a time. The test nodes are perturbed using the Out- wit algorithm with different settings of γ and δ . There is a significant decrease in classification accuracy with only 4 edge perturbations and 6 feature perturbations. As expected, the average accuracy drops as we allow more perturbations. With a maximum of just 8 edge perturbations and 10 fea- ture perturbations (0.5% of the total information present in the target node) the average accuracy drastically falls more than 50%. Figure 3 shows the comparison of Outwit with the baseline model with only edge perturbations. Different ratios of training data   Since social networks evolve and change over time, the ratio of publicly available and hidden data can change as well. In order to train the tar- get model, we assume that few of the nodes in the graph are labelled. The ratio of this trained data may vary across differ- ent social networks and may also vary over time. So we test the perturbations generated by Outwit algorithm with differ- ent ratios of training data. Table 3 shows the performance of the perturbations with varying ratios of labelled nodes. "Es- timated" column shows the performance of model which is trained on partial training data and "Target" column shows the performance of the company model trained on 100% of training data. It is seen that the perturbations generated by our algorithm work well for all the ratios of training data and as the previous experiments, we are perturbing one test node at a time, and not their neighbors' information. Increasing number of colluding users  One of the as- sumptions of our paper is that perturbations are user-centric and Outwit is not allowed to change the attributes of multi- ple nodes. Here we relax this assumption and show empiri- cally how the average accuracy of the target model is further reduced when a randomly selected group of 10 to 50 users simultaneously use adversarial perturbations from the Out- wit algorithm. Figure 4 shows the performance of the target model when many random users simultaneously use 6 edge perturbations and 8 feature perturbations with utility con- straints with α = β = 0.5. The x-axis represent number of users simultaneously adding adversarial information and y-axis represent the average node classification accuracy of GCN. As the number of users increases, the average classi- fication accuracy of the target model decreases even further because adversarial information is passed on to neighbour- ing nodes in the GCN aggregation phase, causing the target model performance to decrease further.
Table 4: Accuracy for simple feature and edge perturbations Sensitivity of Outwit to node degree Here we analyze the sensitivity of Outwit to the node degree and whether it per- forms poorly for low-degree nodes. Figure 5 shows the re- lation between average accuracy of perturbed nodes to their degree. As expected, Outwit can better perturb the node to preserve privacy with increasing node degree. Nevertheless, Outwit still performs much better than all the baselines as shown earlier. In the real world every user has differ- Varying  Utility ent utility distribution for their profile attributes. In order to replicate the level of mutability of profile attributes we generate U , a utility distribution on top of each dataset. We model the utility values for attributes of a user as ran- dom variables from a Bernoulli distribution. Each feature has a different parameter p for their Bernoulli drawn from a Beta distribution prior α and β . We vary the Beta parameter α = 2,β = 5(i.e., features tend to have mostly high levels of utility) to α = 5,β = 2 (i.e., features tend to have mostly low levels of utility p parameters). This allows us to draw a utility value for each user and attribute pair. Figure 6 shows the average classification accuracy under utility constraints. α and β represent the parameters for the beta distribution used to generate the utility distribution. It is observed that even when utility constraints are applied, the perturbations suggested by algorithm significantly decrease the node clas- sification accuracies when test data is perturbed one node at a time. The accuracies are consistently low for all values of α and β .
Conclusion
In this work, we presented Outwit, an algorithm which helps social network users find small user-centric adversarial per- turbations in their profile which lead to a significant decrease in prediction performance of target classifiers in the form of graph convolutional networks. Outwit is a viable approach by which users can ensure that their sensitive information cannot be reliably used. Our experiments show that only a few perturbations are required to prevent a target classifier from predicting the true label. Even after applying the utility constraints on the perturbations, the algorithm was able to perform well.
Acknowledgments
This material is based on research sponsored in part by the National Science Foundation under Grant No. 1801644.