# NAGNE: Node-to-Attribute Generation Network Embedding for Heterogeneous Network
## 3 Preliminary
### Attributed Random Walks  
Random walks [1] have received much attention in homogeneous networks. However, as nodes in heterogeneous networks are associated with a dominant number of paths, random walks in heterogeneous networks are biased to highly visible types of nodes. Subsequently, the learned node embeddings are also biased to these types in the sense that they mostly preserve the node proximity in these types. In addition, random walks ignore the attributes of nodes and cannot integrate attributes into the node embeddings. Thus, we propose an attributed random walk method in a heterogeneous network. In our attributed random walks, there are two steps to select the next node in a random walk. Consider an attributed random walk that just resides at node \(v_{i}\), and the next node \(v_{i+1}\) is selected via the following steps:  
* Selecting a target attribute type \(t\). Sampling one  
where \(\alpha\in[0,1]\) is an initial probability, which is determined in advance. \(s\) is the number of nodes consecutively visited in the same node type of the current node \(v_{i}\). By sampling the attribute type \(t\) from \(\mathcal{T}_{p}(v_{i})\) with a probability \(\alpha^{s}\), and \(\mathcal{T}_{n}(v_{i})\) otherwise, we adopt an exponential decay function \(\alpha^{s}\) to penalize the case that the walk stays in one node type for too long. After that, we uniformly sample one attribute type \(t\) from \(\mathcal{T}_{t}(v_{i})\). * Sampling the target node \(v_{i+1}\). Sampling one node from the nodes with the selected attribute type \(t\). The corresponding candidate set of nodes is denoted as \(V(v_{i})=\{v|t_{v}=t\}\). After selecting a target attribute type \(t\), we can uniformly sample one node as \(v_{i+1}\) from \(V(v_{i})\) with the following probability: \[P(v_{i+1}|t,v_{i})= \begin{cases}\frac{\pi_{v_{i}\cap v_{i+1}}}{Z},&\text{if }v_{i+1}\in V(v_{i}),\\ 0,&\text{otherwise}.\end{cases} \] (6) where \(\pi_{v_{i}v_{i+1}}\) is the un-normalized transition probability between nodes \(v_{i}\) and \(v_{i+1}\); in unweighted networks, \(\pi_{v_{i}v_{i+1}}=1\), \(Z\) is the normalizing constant. However, intuitively, the nodes in \(V(v_{i})\) that have edges with \(v_{i}\) have more similarities with it, which should make them easier to sample. Figure 2 shows an example of the sampling. In Figure 2, if \(t_{1}\) is the selected attribute type, the two nodes in the red dotted circle should be easier to sample than the others in \(t_{1}\) as they have edges with \(v_{i}\). We use \(V_{p}(v_{i})=\{v_{m}|v_{m}\in V(v_{i}),e_{mi}\in\mathcal{E}\}\) to denote the node sets that have edges with \(v_{i}\), and \(V_{n}(v_{i})=\{v_{m}|v_{m}\in V(v_{i}),e_{mi}\
ot\in\mathcal{E}\}\) otherwise. Then, we define the un-normalized transition probability in networks as the following: \[\pi_{v_{i}v_{i+1}}= \begin{cases}\frac{1}{q}\cdot\frac{1}{|V_{p}(v_{i})|},& \text{if }v_{i+1}\in V_{p}(v_{i}),\\ \frac{1}{|V_{n}(v_{i})|},&\text{if }v_{i+1}\in V_{n}(v_{i}).\end{cases} \] (7) Parameter \(q\) controls the search procedure in the walk. As we hope the nodes in \(V_{p}(v_{i})\) are more likely to be sampled, we set \(0<q<1\). Note that by generating the next node \(v_{i+1}\) based on the attribute type, the attributed random walk samples nodes not only from those connected to \(v_{i}\), but also from the nodes have similar attributes with \(v_{i}\), which allows the random walk to explore both the structural and attribute information of the network. The pseudocode is shown in Algorithm 1. Figure 2: An example of selecting where to jump.