# Properties of Vector Embeddings in Social Networks
## 4 Approach
### Explaining Embedding Relatedness  
We formulate our approach such that the similarity of two embeddings \(Y_{u}\) and \(Y_{v}\) can be approximated by a weighted sum of network properties:  
\[f(Y_{u},Y_{v})\sim\sum_{i=1}^{k}w_{i}p_{i}(u,v),\]  
where \(p_{i}\) is a function that computes similarity of the pair \((u,v)\) based on network property \(i\), \(k\) is the number of network properties considered, and \(w_{i}\) is the weight of the network property \(i\). To estimate the weights \(w_{i}\) for every property, we cast the problem into a learning to rank problem. Learning to rank is an important problem in web page ranking, information retrieval and many other applications [39]. Given a ranking of items according to some query items, learning to rank obtains a function based on the similarity between the query and its ranked items. Several types of machine learning algorithms have been considered for this problem: pointwise methods, pairwise methods, and listwise methods. Most recent works have applied pairwise methods for learning to rank on graphs [40; 41]. In pairwise ranking, one is given examples of order relationships among objects, and the goal is to learn from these examples, a real-valued ranking function that induces a ranking or ordering over the object space. We consider the problem of learning such a ranking function when the data is represented as a graph, in which nodes correspond to objects and embeddings encode similarities between objects. Among existing approaches for learning to rank, rankSVM [42] is a commonly used method extended from the popular support vector machine (SVM) [43] for data classification. In training an SVM classifier, a weight vector is computed on the training data. This weight vector can be used as an important measure of the centrality to the classifier. These weights can explain what combination of centralities can explain embeddings. In learning to rank, we first sort nodes according to their similarities. More formally, for each node \(u_{i}\), we sort all other nodes \(u_{j}\in U\setminus\{u_{i}\}\) according to the inner product similarity \(Y_{i}\cdot Y_{j}\). Therefore, each pair of nodes has a rank label that we use as ground truth. We denote the ground-truth vector by \(t\in\mathbb{R}^{|z|\times 1}\), \(z=|m|\times|m-1|\). Furthermore, we need to compute the similarity in terms of DC, CC, BC and EC between every pair of nodes \((u_{i},u_{j})\). Given a node \(u_{i}\in U\), we calculate the centrality measures for every node \(v\in N(u_{i})\), where \(N(u_{i})\) defines the neighborhood of node \(u_{i}\). Indeed, in our approach, we consider network properties within a subgraph around a focal node. To compare how properties of two subgraphs are similar, we first calculate the probability distribution of each centrality by histogramming the centrality measures for every node \(v\in N(u_{i})\). We then measure the similarity between two distributions over the same centrality by KL divergence as follows:  
\[sim(u_{i},u_{j})=1-(D_{KL}(P_{u_{i}}\|Q_{u_{j}}))=1-(\sum_{x}P_{u_{i}}(x)\log \frac{P_{u_{i}}(x)}{Q_{u_{j}}(x)}),\]  
where \(P_{u_{i}}\) and \(Q_{u_{j}}\) are probability distributions over the same centrality measure. If \(D_{KL}\) is low, it means the distributions are very similar and vice versa. In order to guarantee a certain stability of our approach, we assume that the KL divergence can be estimated in a reasonably large neighborhood and that the graph is connected. Therefore, for each pair of nodes, we have a feature vector \(x_{i}\in\mathbb{R}^{4},i=1,\ldots,z\). We denote the feature matrix by \(X\in\mathbb{R}^{|z|\times 4}\). The rankSVM [42] model is built by minimizing the objective function  
\[\frac{1}{2}\|w\|^{2}+C\sum_{i,j}\ell(w^{T}x_{i}-w^{T}x_{j}).\]  
\(w=(w_{DC},w_{CC},w_{BC},w_{EC})\) is the centrality vector, where \(w_{DC}\) denotes the weight for degree, \(w_{CC}\) is the weight for closeness, \(w_{BC}\) denotes the weight for betweenness, and \(w_{EC}\) is the weight for eigenvectorcentrality. \(C>0\) is the regularization parameter.