What is Precision@K for link prediction in graph embedding meaning?

I am trying to re-implement the SDNE algorithm for graph embedding by PyTorch.

I get stuck at some issues about evaluation metric Precision@K.

precision@k is a metric which gives equal weight to the returned instance. It is defined as follows

$$precision@k(i) = \frac{\left| \, \{ j \, | \, i, j \in V, index(j) \le k, \Delta_i(j) = 1 \} \, \right|}{k}$$

where $$V$$ is the vertex set, $$index(j)$$ is the ranked index of the $$j$$-th vertex and $$\Delta_i(j) = 1$$ indicates that $$v_i$$ and $$v_j$$ have a link.

I don't understand what "ranked index of the $$j$$-th vertex" means.

Beside, I am also confused about the MAP metric in section 4.3. I don't understand how to calculate it.

Mean Average Precision (MAP) is a metric with good discrimination and stability. Compared with precision@k, it is more concerned with the performance of the returned items ranked ahead. It is calculated as follows: $$AP(i) = \frac{\sum_j precision@j(i) \cdot \Delta_i(j)}{\left| \{ \Delta_i(j) = 1 \} \right|}$$ $$MAP = \frac{\sum_{i \in Q} AP(i)}{|Q|}$$ where $$Q$$ is the query set.

If anyone is familiar with these metrics, could you help me to explain them?

These measures are used for evaluating how "good" an embedding of a graph is or how "good" the graph reconstructed from the embedding resembles the original.

Given the embedding and vertex $$i$$, it seems to be that the rank of the vertices is dependent on the probability of there being a link between vertex $$i$$ and vertex $$j$$ in the original graph. If there is a higher probability of there being a link between $$i$$ and $$j$$ in the original graph, $$j$$ has a lower rank.

In other words, $$precision@k(i)$$ is the proportion of vertices $$j$$ that vertex $$i$$ has a link to in the original graph out of the $$k$$ vertices for which vertex $$i$$ has the highest probability of having a link to, recovered from the embedding.

This matches up with the common definition of $$precision@n$$ used in evaluating information/document retrieval, defined as the proportion of relevant documents out of the $$n$$ best retrieved documents.

The average precision of a vertex, $$AP(i)$$, is the average of $$precision@j$$ over all $$j$$ such that there is a link between vertex $$i$$ and vertex $$j$$. Perhaps a more clear definition would have been $$AP(i) = \frac{\sum_{j \in S_i} precision@j(i)}{\left| S_i \right|}$$

where $$S_i = \{j \, |\, \Delta_i(j) = 1 \}$$, the set of all $$j$$ such that there is a link from $$i$$ to $$j$$.

$$MAP$$ for a query set $$Q$$ is then the mean of the average precision ($$AP$$) over all vertices in $$Q$$.

• Thank you very much helping me! However I still don't understand why the $precision@k(i)$ has $index(j) \le k$. Meanwhile, $k$ is just a number indicate the top $k$ probability has link $i$ to $j$ in prediction. Aug 13, 2020 at 11:05
• $index(j) \le k$ basically means that this vertex $j$ is one of the vertices for which vertex $i$ has the $k$-highest probability of having a link to in the original graph. Are you not understanding why this metric is created as is, or how the formula for the metric is? Aug 13, 2020 at 17:00
• I think I am understanding what you wrote. It's more clear for me. Thank you so much! Aug 13, 2020 at 19:33
• No problem. Glad to know I helped! Aug 13, 2020 at 19:34
• Sorry but I still don't understand AP, and MAP. Can you provide some simple code for me? May be for me, code is easier to explain :(( Aug 16, 2020 at 16:36

I understand the confusion and I wanted to refer to this (older post) because the metric really is unclear in the context of the SDNE paper.

Perhaps I can try to explain it for future readers, in hopes that this makes sense. All this is my own interpretation, of course.

SDNE is an autoencoder setup that outputs both node embeddings ($$y_i$$ vector for focal node $$i$$) and a reconstruction of the ties of $$i$$ denoted by $$\hat{x}_i$$ with the original being $$x_i$$. Note that $$y_i$$ is the input to the decoder component, and thus the reconstruction is a function of the embedding. In SDNE, $$x_i$$ are the inputs and the "labels", hence autoencoder.

Now, the notion of precision comes from information retrieval. However, for networks, the problem setting differs. We do not retrieve documents repeatedly, instead we literally predict an entire adjacency vector (especially if one uses transformer layers and such). For that reason, the "ranking" part needs to be reformulated to make any sense.

Let's take a naive view and see what would make substantive sense. In the context of a reconstructed network, precision should mean the following:

"What percentage of reconstructed ties are in the real network?"

Whereas recall would mean.

"What percentage of real ties in the network are found in the reconstruction?"

So we have our reconstruction $$\hat{x_i}$$ and our ground truth vector $$x_i$$ - typically rows of the adjacency matrix of the network $$\hat{X}$$ and $$X$$ respectively. Let's denote these networks as $$\hat{X}$$ and $$X$$ as well as there won't be any confusion (in the paper the authors distinguish the network $$G$$, its adjacency matrix $$S$$ and, finally, the inputs and outputs $$X$$ as subset of $$S$$.)

The vectors denote ties between $$i$$ and $$j$$. With some abuse of notation, we could write for unweighted networks $$(i,j) \in X \Leftrightarrow x_{i,j}=1$$

Precision would be: $$\frac{|(i,j) \in \hat{X} \cap (i,j) \in X|}{|(i,j) \in \hat{X}|} \Leftrightarrow \frac{|\{j| x_{i,j}=1 \cap \hat{x}_{i,j}=1\}|}{|\{j| \hat{x}_{i,j}=1\}|}$$

and recall would have the denominator with $$x_{i,j}=1$$ instead of $$\hat{x}_{i,j}=1$$.

The only difference to the precision@k metric in the paper comes from the ranking. As mentioned above, it is not immediately apparent from the paper how a reconstruction would yield probabilities that we can use for a rank- especially if ties are binary.

However, SDNE does not predict binary ties, even if these appear in the original graph. Instead, it applies a sigmoid function and thus gets some value that is proportional to the likelihood of a tie between two nodes. Long story short, each element in $$\hat{x}_i$$ is akin to a probabilistic prediction across possible neighbors. To get the $$index(j)$$ we can thus rank the values of $$\hat{x}_i$$ from highest to lowest.

Let the top $$k$$ of $$\hat{x}_i$$ be above some cutoff value $$t_i(k)$$. We can write precision@k as

$$\frac{|\{j| x_{i,j}=1 \cap \hat{x}_{i,j} \geq t_i(k)\}|}{|\{j|\hat{x}_{i,j} \geq t_i(k)\}|}=\frac{|\{j| x_{i,j}=1 \cap \hat{x}_{i,j} \geq t_i(k)\}|}{k}$$

If our network were weighted, we could do a similar ranking for $$x_i$$. In any case, this solves the first issue.

Now, the main problem comes from the description of $$AP(i)$$.

Both in the paper, and in the previous answer given, there is an obvious mistake: Where precision@k takes an integer $$k$$ as parameter, we are to sum over $$j$$ in $$AP(i)$$. That is, we are told in the other answer (and in the paper) that

$$AP(i) = \frac{\sum_{j \in S_i} \text{precision@}j(i)}{|S_i|}$$ with $$S_i=\{j|x_{i,j}=1\}$$

This of course makes no sense. $$j$$ comes from the node set. Nodes could be numbers, but could also be things like $$v_i =$$"Apple" and $$v_j=$$"potato". Obviously, the measure precision@"apple"$$(i)$$ can not be derived from the above definition.

So, we need to find an interpretation that works. Note first, that the denominator is the number of neighbors of $$i$$ in the network. Thus, the above sum should maximally yield $$|S_i|$$.

Furthermore, the authors want to sum over neighbors $$j$$, employing some sort of precision measure for each. Consequently, whatever is summed up, should sum up to 1 for each $$j \in S_i$$.

Let's consider an embedding that predicts everything perfectly. Note that then precision@k is $$1$$ for every $$k$$. That leaves us with the conclusion that the measure must be

$$\frac{1}{|S_i|}\sum_{j \in S_i} \frac{\sum_k \text{precision@}k(i,j)}{|k|}$$

where $$\text{precision@}k(i,j)$$ denotes some node wise measure of precision. In any case, the measure collapses to

$$\frac{\sum_k \text{precision@}k(i)}{|k|}$$ for each $$k$$ where $$\text{precision@}k(i)>0$$.