# Learning Effective Feature Representation against User Privacy Protection on Social Networks
## 4 The Proposed Method
### Structure-Attribute Mutually-Reinforced Representation  
The privacy-protected network \(H\) has the corresponding adjacency matrix \(\tilde{\mathbf{A}}\) and attribute matrix \(\tilde{\mathbf{X}}\). Given that both matrices \(\tilde{\mathbf{A}}\) and \(\tilde{\mathbf{X}}\) are sparse, we aim at mutually using them to reinforce the matrix representation of \(H\), so that their sparsity can be alleviated. Eventually, a structure-attribute enhanced matrix (SAEM) will be generated. The process to construct SAEM consists of four steps. The first step is to pre-process the adjacency matrix \(\tilde{\mathbf{A}}\). We perform column-wise normalization for matrix \(\tilde{\mathbf{A}}\) and obtain a new matrix \(\hat{\mathbf{A}}\), as given by:  
\[\hat{\mathbf{A}}_{ij}= \begin{cases}\dfrac{1}{\sum_{j}\tilde{\mathbf{A}}_{ij}},&(v_{i},v_{j})\in E\\ 0,&\text{otherwise}.\end{cases}  \tag{1}\]  
The second step is to compute the attribute-based similarity between nodes based on cosine score. A similarity matrix \(\mathbf{S}\) can be obtained, as given by: \(\mathbf{S}_{ij}=\frac{\tilde{\mathbf{X}}_{i}\cdot\tilde{\mathbf{X}}_{j}}{\| \tilde{\mathbf{X}}_{i}\|\times\|\tilde{\mathbf{X}}_{j}\|}\). Here, the range of similarity is \(\mathbf{S}_{ij}\in[0,1]\) because the transformed categorial attribute values cannot be negative, implying that the angle between two vectors cannot be greater than 90 degree. Higher \(\mathbf{S}_{ij}\) indicates node \(v_{i}\) and \(v_{j}\) are more similar in terms of their attributes, because their vectors are close to each other in the space of attribute vectors. When \(\mathbf{S}_{ij}=0\), two vectors \(\tilde{\mathbf{X}}_{i}\), and \(\tilde{\mathbf{X}}_{j}\) are orthogonal, meaning that they are apart from each other (i.e., most dissimilar). Subsequently, we create some ghost links to connect node \(v_{i}\) and \(v_{j}\) based on the attribute-based similarity matrix \(\mathbf{S}\) if \(\mathbf{S}_{ij}\
eq 0\). These ghost links will be incorporated with the normalized adjacency matrix \(\tilde{\mathbf{A}}\) so that the sparsity can be alleviated. Nevertheless, matrix \(\mathbf{S}\) can be too dense, because it could be not hard to share common attributes between users. Dense \(\mathbf{S}\) may lead to insignificant ghost links between nodes. To this end, the third step aims to filter out dissimilar ghost links, and keep only significant ones. The idea is to only retain the \(k\) most similar nodes for every node \(v_{i}\), and neglect the remaining ones. This idea is implemented by first retrieving the set of nodes that are top-\(k\) most similar to node \(v_{i}\), denoted by \(T_{i}^{k}\), where \(v_{i}\
otin T_{i}^{k}\) and \(|T_{i}^{k}|=k\). Note that the top-\(k\) similarity search is implemented by locality-sensitive hashing (LSH) [21] to cope with the scalability issue. Subsequently, we use equation Equation (2) to simultaneously rule out insignificant nodes while normalizing the most similar ones, and derive a distilled attribute-based similarity matrix \(\hat{\mathbf{S}}\). \[\hat{\mathbf{S}}_{ij}= \begin{cases}\dfrac{\mathbf{S}_{ij}}{\sum_{j}\mathbf{S }_{ij}},&v_{j}\in T_{i}^{k}\\ 0,&\text{otherwise}.\end{cases}  \tag{2}\]  
Figure 1: Flowchart of the proposed Network representation learning (NRL) model. Note that \(k\) is a hyperparameter of our model, and we set \(k=5\) by default. We will examine how it affects the performance in the evaluation. Also note that we are not to add vertices into the graph. The filter of Equation (2) is also NOT to remove vertices. The purpose of the filter \(S_{ij}\) is to select the pairs of nodes that possess the higher similarity scores in terms of their attributes, and only consider these node pairs to create edges. In other words, we do not want less similar nodes to have edges in the enhanced graph because they will bring noise into the learning of node embeddings. The last step is to generate the structure-attribute enhanced matrix (SAEM).