# Learning Effective Feature Representation against User Privacy Protection on Social Networks
## 4 The Proposed Method
### Community-Cluster Informed NRL (c2n2v)
Assume that the random walk sampling produces a node sequence \(N_{\varphi}(u)=\left\langle n_{1},n_{2},...,n_{l},...n_{l}\right\rangle\), where \(l\) is the size of neighbor list (i.e., the length of random walk path). Because nodes in \(N_{\varphi}(u)\) are what skip-gram aims to predict, to make the embedding learning be aware of either communities or clusters, we add either \(C\) or \(\tilde{C}\) into \(N_{\varphi}(u)\). In detail, take adding the communities into \(N_{\varphi}(u)\) as an example. For \(N_{\varphi}(u)=\left\langle n_{1},n_{2},...,n_{j},...,n_{l}\right\rangle\), we have its corresponding community list \(C_{\varphi}(u)=\left\langle c_{1},c_{2},...,c_{j},...,c_{l}\right\rangle\), where \(c_{j}\in C\). We add each \(c_{j}\in C_{\varphi}(u)\) into the immediate right of its corresponding node, and obtain a new neighbor list \(\hat{N}_{\varphi}(u)=\left\langle n_{1},c_{1},n_{2},c_{2},...,n_{j},c_{j},..., n_{l},c_{l}\right\rangle\). The length of \(\hat{N}_{\varphi}(u)\) is 2\(l\). We can apply the same process to add user clusters into the neighbor list. Note that since each \(n_{i}\) is a node and each \(c_{j}\) is a community, the generation of the new neighbor list \(\hat{N}_{\varphi}(u)\) is simply to interweave \(n_{i}\) and \(c_{j}\) together into a new list. It is not a kind of concatenation operation. In order to make the optimization problem tractable, two typical assumptions referred and justified by an existing work [4] are constructed. One is conditional independence: given the embedding of node \(u\), the likelihood of observing \(u\)'s neighbor list \(\hat{N}_{\varphi}(u)\) is independent of one another. Consequently, \(P(\hat{N}_{\varphi}(u)|f(u))\) can be factorized by the neighboring nodes:  
\[P(\hat{N}_{\varphi}(u)|f(u))=\prod_{y\in\hat{N}_{\varphi}(u)}P(y|f(u)) \tag{5}\]  
The second assumption is feature space symmetry: any pair of neighbors symmetrically affect each other in the space of feature representation. Therefore, for a node \(u\), the conditional likelihood of each neighbor \(y\in N_{\varphi}(u)\) can be implemented by a softmax function ([[https://en.wikipedia.org/wiki/Softmax_function](https://en.wikipedia.org/wiki/Softmax_function)]([https://en.wikipedia.org/wiki/Softmax_function](https://en.wikipedia.org/wiki/Softmax_function))) parameterized by a dot product of their feature representations:  
\[P(y|f(u))=\frac{\exp(f(y)\cdot f(u))}{\sum_{v\in V}\exp(f(v)\cdot f(u))}. \tag{6}\]  
The use of exponential function in Equation (6) comes from the softmax function. The softmax function aims at taking a vector of arbitrary real numbers, and generating a probability distribution with the same number of elements such that larger elements have higher probability values. Hence, the softmax function is required to have two properties: monotonically increasing and giving a non-negative result for any real input. It turns out that the exponential function is a natural choice, since it possesses such two properties. Eventually, the objective function can be simplified as:  
\[\max_{f}\sum_{u\in V}\left(-\log Z_{u}+\sum_{y\in\hat{N}_{\varphi}(u)}f(y) \cdot f(u)\right), \tag{7}\]  
where \(Z_{u}=\sum_{v\in V}\exp(f(u)\cdot f(v))\) can be approximated by negative sampling [5]. In addition, this objective function can be optimized by stochastic gradient descent (SGD) [25]. Each node in the network will be treated as the source of \(r\) random walks. These generated \(r\times|V|\) random walks will be exploited to learn the embedding of each node. Unless we specify otherwise, by default, we set the length of random walks \(l=10\), and the dimension of features \(K=128\). For each node in the graph, 10 random walks (\(r=10\)) are generated. Because we can choose to include either structural community information \(C\) or user cluster information \(\tilde{C}\) in embedding learning, two kinds of embedding vectors will be generated. They are community-informed embedding and cluster-informed embedding for each node \(v\in V\), denoted by \(f^{C}(v)\) and \(f^{\tilde{C}}(v)\), respectively.