# Adap-UIL: A Multi-Feature-Aware User Identity Linkage Framework Based on an Adaptive Graph Walk
## 5 Adap-UIL: Multi-Feature-Aware User Identity Linkage Based on Adaptive Graph Walk  
As shown in Figure 4, the UIL framework mainly consists of three parts: graph walk, fusion embedding, and matching. The graph walk includes the intranetwork Adaptive Graph Walk and the internetwork walk; the fusion embedding generates node vectors, respectively, and then concatenates them, and the matching process adopts a multi-layer perceptron (MLP).  
Figure 3: Differences among the Adaptive Graph Walk and other approaches.  
In the process of graph walk, the intranetwork walk adopts the Adaptive Graph Walk method based on the aforementioned RAC, following the transition probabilities of \(m_{i,j}\), and the internetwork walk adopts the cross-network walk.  
The cross-network walk follows the following transition probabilities:  
\[P_{\text{C}}(j\mid i)=\begin{cases}\beta&\text{if }i,j\in\mathcal{L}\\ \frac{1-\beta}{|N(i)|-1}&\text{if }i\in\mathcal{L},\;j\
otin\mathcal{L}\\ \frac{1}{|N(i)|}&\text{if }i\
otin\mathcal{L}\end{cases} \tag{14}\]  
where \(N(i)\) denotes the neighbors of node \(i\), and \(|N(i)|\) denotes the number of neighbors of node \(i\); \(\beta\) denotes the probability of node transfer across the networks.  
\(\mathcal{L}=V^{l},E^{l}\) is a known set of anchor node pairs \(L=V^{l},E^{l}\), where \(V^{l}\) is the set of anchor nodes, and \(E^{l}\) are virtual edges between the anchor nodes from different networks.  
The fusion embedding generates the intranetwork vector representation \(v_{intra}\) and the internetwork vector representation \(v_{inter}\) of each node using word2 vec, respectively, and concatenates the two vectors to form the final vectors. The final representation of the node is:  
\[v=v_{inter}+v_{intra} \tag{15}\]  
In the process of embedding for each network and each walk process, respectively, the user sequences for the given network can be represented as:  
\[v_{1},v_{2},\ldots,v_{M}\in V \tag{16}\]  
Embedding maximizes the log probability by the following formula:  
\[\frac{1}{N}\sum_{t=1}^{N}\sum_{j=-W}^{W}\log\Bigl{(}p\bigl{(}v_{t+j}\mid v_{t} \bigr{)}\Bigr{)}\qquad(j\
eq 0) \tag{17}\]  
where \(N\) is the number of users of the network, and \(W\) is the size of the sliding window. In the formula, the conditional probability \(p(v_{t+j}|v_{t})\) represents the probability of co-occurrence of user \(v_{t}\) and its \(j-hop\) neighbor \(v_{t+j}\):  
\[p(v_{t+j}\mid v_{t})=\frac{\exp\Bigl{(}v_{v_{t+j}}^{T}v_{t}^{\prime}\Bigr{)}} {\sum\limits_{i=1}^{N}\exp\bigl{(}v_{i}^{T}v_{t}^{\prime}\bigr{)}} \tag{18}\]  
Figure 4: Framework of Adap-UIL.  
where \(N\) represents the number of users in the network. In this module, we define the probability of an edge between two nodes \(v_{i},v_{j}\) as  
\[p(v_{i},v_{j})=\sigma(v_{i}^{T}\cdot v_{j})=\frac{1}{1+e^{-v_{i}^{T}\cdot v_{j}}} \tag{19}\]  
where \(\sigma\) represents the sigmoid function.  
We use negative sampling to maximize the target function to improve the training effect.  
\[\log\sigma(v_{i}^{T}\cdot v_{j})+\sum_{k=1}^{K}\mathbb{E}_{v_{k}\in P_{n}(v)} \Big{[}\log\Big{(}1-\sigma(v_{i}^{T}\cdot v_{k})\Big{)}\Big{]} \tag{20}\]  
where the first item is the existing edge modeling and the second item is the negative sampling. \(K\) is the number of negative edges sampled, and the sampling probability of each node is \(P_{n}(v)\sim d_{v}^{3/4}\), where \(d_{v}\) is the degree of the node.  
In the training process, we use stochastic gradient descent to update the node representation.  
After obtaining the network representation, we learn the mapping function F in a supervised manner. For each pair of observed anchor nodes \((v_{s},v_{t})\), an MLP minimizes the cosine similarity between them. The loss function is computed by:  
\[L(v_{s},v_{t})=\min\Big{(}1-\cos\big{(}F(v_{s},v_{t})\big{)}\Big{)} \tag{21}\]  
where the loss ranges from 0 to 2--0 for the same and 2 for exactly the opposite.