What is Precision@K for link prediction in graph embedding meaning?
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 &quot;labels&quot;, 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 &quot;ranking&quot; 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:
&quot;What percentage of reconstructed ties are in the real network?&quot;
Whereas recall would mean.
&quot;What percentage of real ties in the network are found in the reconstruction?&quot;
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 = $&quot;Apple&quot; and $v_j=$&quot;potato&quot;. Obviously, the measure precision@&quot;apple&quot;$(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)&gt;0$.