# Edge-Nodes Representation Neural Machine for Link Prediction
## 3 Edge-Nodes Representation Neural Machine (ENRNN)
### Edge Pattern Encoding  
To acquire the full representation for each link, we need to represent edges and nodes firstly. Traditional edge embedding methods tend to combine the representations of nodes on the two sides of the edge in different manners as link's representation. But recently there are many new methods such as WLNM, it pays attention to get the surrounding environments of the edge. WLNM extracts a subgraph for each edge firstly then transforms the unordered subgraph to an ordered subgraph which can be represented as an adjacency matrix. The edge pattern encoding method is explained in the Algorithm 2, and the detail is elaborated in the following.  
```
0: network \(G\), edge \((x,y)\), integer \(K\)
0: edge's representation \(edgevec(x,y)\)
1:\(V_{K}=\{x,y\}\)
2:\(temp\)= \(\{x,y\}\)
3:while\(|V_{K}|<K\) and \(|temp|>\)0 do
4:\(temp=(\cup_{v\in temp}\Gamma(v))\backslash V_{K}\)
5:\(V_{K}=V_{K}\cup temp\)
6:endwhile
7: calculate \(d(v):=\sqrt{(d(v,x)d(v,y))}\) for all \(v\in V_{K}\)
8: get initial symbols \(c(v)=f(d(v))\) for all \(v\in V_{K}\)
9:while\(c(v)\) not converge do
10: calculate hashing values \(h(v)\) for all \(v\in V_{K}\)
11: update symbols \(c(v)=f(d(v))\)
12:endwhile
13: convert the labeled subgraph to an adjacency matrix
14: joint all the columns of upper triangle of adjacency matrix vertically and record as \(edgevec(x,y)\)
15:return\(edgevec(x,y)\)
```  
**Algorithm 2** Edge pattern encoding  
For each target edge between node \(x\) and node \(y\), we extract a subgraph which can be considered as the edge's surrounding environment and the nodes' amount of the subgraph is K, a number set manually. Then we add node \(x\), node \(y\), \(\Gamma(x)\), \(\Gamma(y)\), \(\Gamma^{1}(x)\), \(\Gamma^{1}(y)\), \(\Gamma^{2}(x)\), \(\Gamma^{2}(y)\dots\) into the subgraph until the nodes' number of the subgraph is more than K or there are no more nodes to add.  
After the subgraph extraction, we need to transform the unordered subgraph to an ordered subgraph by a graph labeling algorithm, then we can represent the subgraph as an adjacency matrix. Each node of the subgraph is given an initial symbol according to the distances to node \(x\) and node \(y\), then we update the symbol iteratively determined by the hash function \(h\) and the mapping function \(f\) which can map a hash value to an integer.  
The hash function is shown as Equation (1) [16]:  
\[h(x)=c(x)+\frac{\sum_{z\subseteq\Gamma(x)}log(p(c(z)))}{\sum_{z^{\prime}\subseteq V _{K}}log(p(c(z^{\prime})))}. \tag{1}\]  
The hashing function is based on the Weisfeiler-Lehman algorithm [26], a color refinement algorithm which transforms an unordered graph to an ordered graph. In the Equation (1), c(x) is the current symbol of node \(x\), \(p(n)\) indicats the \(n\)th prime number, \(p(1)=2\), \(p(2)=3\), \(p(3)=5\), \(p(4)=7\dots\). After getting an ordered subgraph, we can represent the subgraph as an adjacency matrix whose order is decided by the integer symbols. Generally, we often set \(A_{ij}=1/0\) to indicate that there is a link between the corresponding two nodes \(i\) and \(j\) or not. To learn more meaningful patterns, we set \(A_{ij}=function(d((i,j),(x,y)))\), where \(d((i,j),(x,y))\) is the shortest distance between edge \((i,j)\) and edge \((x,y)\). In the end, we splice the upper triangle of the adjacency matrix vertically to a vector as the edge's representation.