# Graph-based Method for App Usage Prediction with Attributed Heterogeneous Network Embedding
## 3 Graph-Based App Usage Prediction
### Link Prediction  
Through the GATNE-I model, we transform App usage records into a latent space to construct a network and obtain embedding of each node with representation learning. We will calculate the similarities of embedding vectors of two nodes using Adjusted Cosine Similarity so that we can infer whether there is a linking between two nodes. If two vectors have a high degree of similarity, then the probability that they will be connected in the future is high. As an example, given a spatial context \(l\) for a specific user \(u\), linking between \(l\) and \(a\) means \(u\) used \(a\) at the location \(l\) and not-linking means the user has not used this App in the past. If a new location \(l^{\prime}\) is given and is similar to \(l\), there is a certain possibility that user \(u\) will use \(a\) at \(l^{\prime}\). In other words, there may be a linking between \(l^{\prime}\) and \(a\). Here, the App prediction problem is reformulated as link prediction problem in the complex network, that is, linking or not between two nodes.  
There are three types of sub-graphs in the new latent space, which contain the relationship between application and time or location or the previous App respectively if only the GATNE-I model is used. On this basis, we can predict the next application in the light of information about time or location or the previous App, but just only one relationship can be made use of per prediction. Nevertheless, there are some works revealing that information about time or location or user profile like the phone in silent mode [6] all have an impact on the next App prediction in the future duration. Hence, for the sake of improvement of accuracy, we need to integrate all the three types of information and decide the importance of three types in the process of fusion.  
Above all, one record \(r\) includes four nodes: time, location, the previous App, and the current App. Through representation learning in Section 3.2, \(v_{r,t},v_{r,l},v_{r,p}\) can be obtained, which indicate embedding of time node, location node, and the previous App node in the \(r-th\) record. In AHNEAP, we adopt a neural network with a single hidden layer to handle integration. In the hidden layer, we choose the sigmoid function as the activation function. We concatenate the three embeddings of time, location, and the previous App nodes together for each record as input:  
\[v_{r}=(v_{r,t},v_{r,l},v_{r,p}) \tag{4}\]  
where \(r\) is a serial number indicating a certain record. Then, take the one-hot value of each application as the output. In that way, the probabilities of all application installed at the context \(v_{r,t}\), \(v_{r,l}\) and \(v_{r,p}\) are:  
\[q_{r}=W^{(2)}\cdot sigmoid(v_{r}\cdot W^{(1)}+b_{1})+b_{2} \tag{5}\]  
where \(q_{r}\) is a probability vector of all applications calculated in the \(r-th\) case, \(W^{(1)}\) and \(W^{(2)}\) are transformation matrices corresponding to layers in the neural network. In addition, we definite \(p_{i}\) as the actual observed distribution, which actually is the one-hot value corresponding to the App user used.  
Before minimizing the distance between the probability distributions and really observed distributions, we define the loss function to calculate divergence:  
\[H=-\sum_{j=1}^{n}p_{r}^{j}log(q_{r}^{j}) \tag{6}\]  
where \(n\) is the number of applications installed, \(p_{r}^{j}\) is the probability of the \(j-th\) application from real distributions, and \(q_{r}^{j}\) is from the result of the output layer.  
The above processes are comprised of representation learning and neural network. The embedding captures both topological structures of App usage interaction from different types of nodes and attributed information, and the neural network integrates all types of relationships. Based on the probability ranking of different App nodes, we can speculate several Apps, one of which will be launched in the future.