# Learning Effective Feature Representation against User Privacy Protection on Social Networks
## 3 Problem Statement  
We first describe the notations for our problem. Let \(G=(V,E,\mathbf{A},\mathbf{X})\) denote a social network, in which \(V\) is the node set (\(n=|V|\) is the number of nodes), \(E\) is the edge set, \(A\) is the corresponding adjacency matrix with the symmetric form, in which element \(\mathbf{A}_{ij}=1\) if nodes \(v_{i},v_{j}\in V\) are connected (otherwise, \(\mathbf{A}_{ij}=0\)), and \(\mathbf{X}\in\mathbb{R}^{n\times d}\) is the node-attribute matrix, where \(d\) is the total number of attributes.  
Note that the element in the attribute matrix is binary (not numerical), and all of the used benchmark datasets mentioned in Section 5 have transformed the original categorical attributes into the binary form. For example, if one attribute is gender, then it can have three dimensions depicting all of its attribute values: \"male\", \"female\", and \"do not apply\". The integer value \(d\) is the number of all possible categorical values of all attributes.  
Next, we define the privacy exposure on each user \(v\in V\). The privacy exposure, denoted by \(\epsilon=[0,1]\), is defined by the percentage of reserved information for either edge connections or node attributes. Let \(\epsilon_{c}(v)\) be the connection privacy exposure of node \(v\), which is defined via \(\epsilon_{c}(v)=\frac{|E(v)|}{|E(v)|}\), where \(E(v)\) is the set of edge connections of node \(v\), and \(E(v)\) is the set of connections that user \(v\) exposes to the public. Similarly, let \(\epsilon_{a}(v)\) be the attribute privacy exposure of node \(v\), which is defined via \(\epsilon_{a}(v)=\frac{d(v)}{d}\), where \(d(v)\) is the number of attributes that user \(v\) exposes to the public. Note that in our settings, we assume that the privacy exposure of connections and attributes for all users have the same sensitivity. It is an approximation of the realistic setting. In the experiments in Section 5, we will examine how different sensitivities on users for privacy exposure affect the effectiveness of feature representation learning.  
We define the privacy-protected social network \(H=(V,\bar{E},\bar{\mathbf{A}},\bar{\mathbf{X}})\) to be a subgraph of the original network \(G\). Each user \(v\in V\) has its own connection and attribute privacy exposure, \(\epsilon_{c}(v)\), and \(\epsilon_{a}(v)\), which result in the edge set \(\bar{E}\subseteq E\) the corresponding privacy-protected adjacency matrix \(\bar{\mathbf{A}}\) and node-attribute matrix \(\bar{\mathbf{A}}\).  
**Privacy-Protected Network Representation Learning (PP-NRL).** Given a privacy-protected social network \(H\), PP-NRL is to learn a mapping function \(f:V\rightarrow\mathbb{R}^{K}\) from nodes to low-dimensional embedding vectors, so that nodes sharing more similar graph neighborhood and possessing more similar attributes are as close as possible in the embedding space. Here, \(K\) is a parameter indicating the number of dimensions of feature representations, and \(f\) is a matrix of size \(n\times K\), and \(d\ll|V|\). While the original attribute vector is in \(d\) dimensions, the learned feature representations utilize \(K\) dimensions to encode both graph neighborhood and user attribute information. It is often that \(K<d\), meaning that we can use low-dimensional dense vectors to encode information from high-dimensional sparse vectors in the graph.  
Our goal is to preserve two properties from the privacy-protected network, structural proximity and semantic proximity. The former indicates that nodes with similar structural neighborhood tend to have similar embedding vectors. The latter aims at making nodes sharing similar attributes possess similar embedding vectors. We think such structural and semantic proximities are co-related with one another, and they can be simultaneously exploited to deal with the sparsity of graph topology and user attributes.