# Multi-View Network Representation Learning Algorithm Research
## 3 Our Method
### Feature Extraction for Different k-Step Networks  
DeepWalk uses Skip-Gram model for big-scale network representation learning, which captures context vertices by random walk algorithm. The objective of the DeepWalk is to maximize the following average log probability:  
\[\frac{1}{L}\sum_{i=1}^{L}\sum_{-t\leq j\leq t,j\
eq 0}\text{log}p(v_{j+i}|v_{i}), \tag{1}\]  
where \(L\) denotes the number of vertices, \(v_{i}\) denotes the current vertex and \(v_{j+i}\) denotes the context vertices of the current vertex \(v_{i}\). \(t\) is the number of context vertices before and after the current vertex \(v_{i}\). \(t\) indicates the context window size to be \(2t+1\). Moreover, the conditional probability \(p(v_{j+i}|v_{i})\) can be defined by \(p(v_{i+j}|v_{i})=\exp(\sigma_{v_{i+j}}^{T}r_{v_{i}})/\sum_{v\in V}\exp(\sigma_ {v}^{T}r_{v_{i}})\), where \(r_{v}\) and \(o_{v}\) is the input and output latent variable, namely, the input and output representation vectors of \(v\). Based on DeepWalk and PageRank, the research achievements from TADW [29] show that DeepWalk aims to factorize the following matrix:  
\[M_{ij}=\log\frac{\left[e_{i}(Pr+Pr^{2}+\cdots+Pr^{t})\right]_{j}}{t}, \tag{2}\]  
where \(Pr_{ij}=1/d_{i}\), if \((i,j)\in E\), and \(Pr_{ij}=0\) otherwise. \(d_{i}\) is the degree value of vertex \(i\). As shown in Equation (3), matrix \(M\) captures the \(t\)-th step neighboring vertices. Node2 vec adopts BFS and DFS to capture higher order neighboring vertices, GraRep captures higher order network feature matrix by the \(k\)-step probability transition matrix \(B^{k}\), and \(B^{k}\) is the multiplication form of multiple \(B\), where \(B=D^{-1}A\), \(A\) is an adjacency matrix, \(D\) is a diagonal matrix. One shortage of GraRep is that the inverse matrix \(D^{-1}\) does not exist when the network is sparse. Based on the Equation (2), TADW [29] presents a simplified target matrix and finds a balance between speed and accuracy. Consequently, matrix \(M\) can be formulated as follows:  
\[M=\frac{Pr+Pr^{2}}{2} \tag{3}\]  
Matrix \(M\) captures the first-order and second-order neighbors for vertices with small computation complexity. GraRep uses the matrix \(\left(D^{-1}A\right)^{k}\) to represent higher order feature matrix. In MVNR, we capture higher order features by defining the adjacency matrix \(A^{(k)}\) as GraRep, but we perform some optimization operations for the matrix \(A^{(k)}\). Unlike GraRep algorithm, \(A^{(k)}\) is the adjacency matrix of \(k\)-step network. In GraRep algorithm, \(\left(D^{-1}A\right)^{k}\) can be regarded as the variation form of \(A^{k}\). \(A^{(k)}\) can be regarded as the reachability matrix within \(k\) steps. Therefore, the optimization operations of \(A^{(k)}\) adopt a similar form as GraRep, but the essence of matrix \(A^{(k)}\) and \(A^{k}\) is very different. Moreover, the structure feature matrix constructions based on \(A^{(k)}\) and \(A^{k}\) are also very different. These differences are the optimization operations of \(A^{(k)}\) in this paper. Here, we first adopt \(A^{(k)}\) to denote the adjacency matrix of \(k\)-step network and \(A^{k}=[a^{k}_{ij}]\). Matrix \(A^{(k)}\) can be formulated as follows:  
\[A^{(k)}=[a^{(k)}_{ij}] \tag{4}\]  
where \(A^{(k)}\) is the adjacency matrix of the \(k\)-step network, \(a^{(k)}_{ij}\) is the matrix elements of matrix \(A^{(k)}\) and adjacency matrix \(A\) consists of 0 and 1, so we set the element value as 0 or 1 in \(A^{(k)}\), thus \(a^{(k)}_{ij}=0\), if \(a^{k}_{ij}=0\), and \(a^{(k)}_{ij}=1\) otherwise, where \(a^{k}_{ij}\) is the matrix elements of matrix \(A^{k}\). The Equation (4) is different from the transition matrix of GraRep, for each \(k\)-step network, we reconstruct the \(k\)-step network based on matrix \(A^{k}\) and \(A^{(k)}\). In fact, \(A^{(k)}\) is the probability of reachability.