Answers.Body: <p>These measures are used for evaluating how &quot;good&quot; an embedding of a graph is or how &quot;good&quot; the graph reconstructed from the embedding resembles the original.</p>
  <p>Given the embedding and vertex <span class="math-container">$i$</span>, it seems to be that the rank of the vertices is dependent on the probability of there being a link between vertex <span class="math-container">$i$</span> and vertex <span class="math-container">$j$</span> in the original graph. If there is a higher probability of there being a link between <span class="math-container">$i$</span> and <span class="math-container">$j$</span> in the original graph, <span class="math-container">$j$</span> has a lower rank.</p>
  <p>In other words, <span class="math-container">$precision@k(i)$</span> is the proportion of vertices <span class="math-container">$j$</span> that vertex <span class="math-container">$i$</span> has a link to in the original graph out of the <span class="math-container">$k$</span> vertices for which vertex <span class="math-container">$i$</span> has the highest probability of having a link to, recovered from the embedding.</p>
  <p>This matches up with the common definition of <span class="math-container">$precision@n$</span> used in evaluating information/document retrieval, defined as the proportion of relevant documents out of the <span class="math-container">$n$</span> best retrieved documents.</p>
  <p>The average precision of a vertex, <span class="math-container">$AP(i)$</span>, is the average of <span class="math-container">$precision@j$</span> over all <span class="math-container">$j$</span> such that there is a link between vertex <span class="math-container">$i$</span> and vertex <span class="math-container">$j$</span>. Perhaps a more clear definition would have been <span class="math-container">$$AP(i) = \frac{\sum_{j \in S_i} precision@j(i)}{\left| S_i \right|}$$</span></p>
  <p>where <span class="math-container">$S_i = \{j \, |\,  \Delta_i(j) = 1 \}$</span>, the set of all <span class="math-container">$j$</span> such that there is a link from <span class="math-container">$i$</span> to <span class="math-container">$j$</span>.</p>
  <p><span class="math-container">$MAP$</span> for a query set <span class="math-container">$Q$</span> is then the mean of the average precision (<span class="math-container">$AP$</span>) over all vertices in <span class="math-container">$Q$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-13T11:05:06.660Z
Answers.Text: 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.
Answers.UserDisplayName: Truong Hoang
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-13T17:00:26.593Z
Answers.Text: $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?
Answers.UserDisplayName: Varun Vejalla
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-13T19:33:30.907Z
Answers.Text: I think I am understanding what you wrote. It's more clear for me. Thank you so much!
Answers.UserDisplayName: Truong Hoang
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-13T19:34:21.430Z
Answers.Text: No problem. Glad to know I helped!
Answers.UserDisplayName: Varun Vejalla
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-16T16:36:43.903Z
Answers.Text: 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 :((
Answers.UserDisplayName: Truong Hoang
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-17T00:11:49.983Z
Answers.Text: Exactly which part do you not understand? If you are more specific about this, then it would be easier to help you.
Answers.UserDisplayName: Varun Vejalla
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-17T06:55:56.423Z
Answers.Text: I think I understand $precision@k(i)$ which has the $k$-top probability link to vertex $i$. I don't get AP. I think AP should $AP(i) = \frac{ \sum_{i \in S}{precision@k(i)} }{|S|}$
Answers.UserDisplayName: Truong Hoang
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-17T07:19:26.483Z
Answers.Text: I don't know why is $precision@j(i)$? Is $j$ like $k$ in $precision@k(i)$. If as the formula, I need to check all vertex (node) in graph by a for loop?
  And what is exactly $Q$ query? Like `Q = [1,2,10,100]` as value of $k$?
Answers.UserDisplayName: Truong Hoang
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-19T20:48:24.287Z
Answers.Text: @TruongHoang With that definition of $AP$, the argument of the function is being used as the index in the summation (which wouldn't make sense). Regarding $precision@j(i)$, yes - the $j$ is like the $k$ in $precision@k(i)$. For your last question, $Q$ is the set of vertices that you want to find the average precision for (it may be the whole graph).
Answers.UserDisplayName: Varun Vejalla
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-12T22:44:24.137Z
Answers.LastActivityDate: 2020-08-19T20:49:49.320Z
Answers.LastEditDate: 2020-08-19T20:49:49.320Z
Answers.UserDisplayName: Varun Vejalla
Answers.Body: <p>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.</p>
  <p>Perhaps I can try to explain it for future readers, in hopes that this makes sense. All this is my own interpretation, of course.</p>
  <p>SDNE is an autoencoder setup that outputs both node embeddings (<span class="math-container">$y_i$</span> vector for focal node <span class="math-container">$i$</span>) and a reconstruction of the ties of <span class="math-container">$i$</span> denoted by <span class="math-container">$\hat{x}_i$</span> with the original being <span class="math-container">$x_i$</span>. Note that <span class="math-container">$y_i$</span> is the input to the decoder component, and thus the reconstruction is a function of the embedding.
  In SDNE, <span class="math-container">$x_i$</span> are the inputs and the &quot;labels&quot;, hence autoencoder.</p>
  <p>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.</p>
  <p>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:</p>
  <p>&quot;What percentage of reconstructed ties are in the real network?&quot;</p>
  <p>Whereas recall would mean.</p>
  <p>&quot;What percentage of real ties in the network are found in the reconstruction?&quot;</p>
  <p>So we have our reconstruction <span class="math-container">$\hat{x_i}$</span> and our ground truth vector <span class="math-container">$x_i$</span> - typically rows of the adjacency matrix of the network <span class="math-container">$\hat{X}$</span> and <span class="math-container">$X$</span> respectively. Let's denote these networks as <span class="math-container">$\hat{X}$</span> and <span class="math-container">$X$</span> as well as there won't be any confusion (in the paper the authors distinguish the network <span class="math-container">$G$</span>, its adjacency matrix <span class="math-container">$S$</span> and, finally, the inputs and outputs <span class="math-container">$X$</span> as subset of <span class="math-container">$S$</span>.)</p>
  <p>The vectors denote ties between <span class="math-container">$i$</span> and <span class="math-container">$j$</span>. With some abuse of notation, we could write for unweighted networks <span class="math-container">$(i,j) \in X \Leftrightarrow x_{i,j}=1$</span></p>
  <p>Precision would be:
  <span class="math-container">$$\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\}|}$$</span></p>
  <p>and recall would have the denominator with <span class="math-container">$x_{i,j}=1$</span> instead of <span class="math-container">$\hat{x}_{i,j}=1$</span>.</p>
  <p>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.</p>
  <p>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 <span class="math-container">$\hat{x}_i$</span> is akin to a probabilistic prediction across possible neighbors.
  To get the <span class="math-container">$index(j)$</span> we can thus rank the values of <span class="math-container">$\hat{x}_i$</span> from highest to lowest.</p>
  <p>Let the top <span class="math-container">$k$</span> of <span class="math-container">$\hat{x}_i$</span> be above some cutoff value <span class="math-container">$t_i(k)$</span>.
  We can write precision@k as</p>
  <p><span class="math-container">$$\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}$$</span></p>
  <p>If our network were weighted, we could do a similar ranking for <span class="math-container">$x_i$</span>. In any case, this solves the first issue.</p>
  <p>Now, the main problem comes from the description of <span class="math-container">$AP(i)$</span>.</p>
  <p>Both in the paper, and in the previous answer given, there is an obvious mistake: Where precision@k takes an integer <span class="math-container">$k$</span> as parameter, we are to sum over <span class="math-container">$j$</span> in <span class="math-container">$AP(i)$</span>. That is, we are told in the other answer (and in the paper) that</p>
  <p><span class="math-container">$$AP(i) = \frac{\sum_{j \in S_i} \text{precision@}j(i)}{|S_i|}$$</span>
  with <span class="math-container">$S_i=\{j|x_{i,j}=1\}$</span></p>
  <p>This of course makes no sense. <span class="math-container">$j$</span> comes from the node set. Nodes could be numbers, but could also be things like <span class="math-container">$v_i = $</span>&quot;Apple&quot; and <span class="math-container">$v_j=$</span>&quot;potato&quot;. Obviously, the measure precision@&quot;apple&quot;<span class="math-container">$(i)$</span> can not be derived from the above definition.</p>
  <p>So, we need to find an interpretation that works. Note first, that the denominator is the number of neighbors of <span class="math-container">$i$</span> in the network. Thus, the above sum should maximally yield <span class="math-container">$|S_i|$</span>.</p>
  <p>Furthermore, the authors want to sum over neighbors <span class="math-container">$j$</span>, employing some sort of precision measure for each. Consequently, whatever is summed up, should sum up to 1 for each <span class="math-container">$j \in S_i$</span>.</p>
  <p>Let's consider an embedding that predicts everything perfectly.
  Note that then precision@k is <span class="math-container">$1$</span> for every <span class="math-container">$k$</span>. That leaves us with the conclusion that the measure must be</p>
  <p><span class="math-container">$$\frac{1}{|S_i|}\sum_{j \in S_i} \frac{\sum_k \text{precision@}k(i,j)}{|k|}$$</span></p>
  <p>where <span class="math-container">$\text{precision@}k(i,j)$</span> denotes some node wise measure of precision. In any case, the measure collapses to</p>
  <p><span class="math-container">$$\frac{\sum_k \text{precision@}k(i)}{|k|}$$</span>
  for each <span class="math-container">$k$</span> where <span class="math-container">$\text{precision@}k(i)&gt;0$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-16T15:12:35.343Z
Answers.LastActivityDate: 2021-05-16T15:12:35.343Z
Answers.UserDisplayName: IMA
Body: <p>I am trying to re-implement the <a href="https://www.kdd.org/kdd2016/papers/files/rfp0191-wangAemb.pdf" rel="nofollow noreferrer">SDNE algorithm</a> for graph embedding by PyTorch.</p>
  <p>I get stuck at some issues about evaluation metric <strong>Precision@K</strong>.</p>
  <blockquote>
  <p><em>precision@k</em> is a metric which gives equal weight to the returned instance. It is defined as follows</p>
  <p><span class="math-container">$$precision@k(i) = \frac{\left| \, \{ j \, | \, i, j \in V, index(j) \le k, \Delta_i(j) = 1 \} \, \right|}{k}$$</span></p>
  <p>where <span class="math-container">$V$</span> is the vertex set, <span class="math-container">$index(j)$</span> is the ranked index of the <span class="math-container">$j$</span>-th vertex and <span class="math-container">$\Delta_i(j) = 1$</span> indicates that <span class="math-container">$v_i$</span> and <span class="math-container">$v_j$</span> have a link.</p>
  </blockquote>
  <p>I don't understand what &quot;ranked index of the <span class="math-container">$j$</span>-th vertex&quot; means.</p>
  <p>Beside, I am also confused about the <strong>MAP</strong> metric in <strong>section 4.3</strong>. I don't understand how to calculate it.</p>
  <blockquote>
  <p><em>Mean Average Precision (MAP)</em> is a metric with good discrimination and stability. Compared with <em>precision@k</em>, it is
  more concerned with the performance of the returned items ranked ahead. It is calculated as follows:
  <span class="math-container">$$AP(i) = \frac{\sum_j precision@j(i) \cdot \Delta_i(j)}{\left| \{ \Delta_i(j) = 1 \} \right|}$$</span>
  <span class="math-container">$$MAP = \frac{\sum_{i \in Q} AP(i)}{|Q|}$$</span>
  where <span class="math-container">$Q$</span> is the query set.</p>
  </blockquote>
  <p>If anyone is familiar with these metrics, could you help me to explain them?</p>
  
Tags: <deep-learning><graphs><precision>
Title: What is Precision@K for link prediction in graph embedding meaning?
UserDisplayName: Truong Hoang
ThreadText: # What is Precision@K for link prediction in graph embedding meaning?
  
  (Asked by: username_0 on 2020-08-12)
  
  I am trying to re-implement the [SDNE algorithm](https://www.kdd.org/kdd2016/papers/files/rfp0191-wangAemb.pdf) 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?
  
  **Tags:** deep-learning, graphs, precision
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2020-08-12. Score: 1 | Accepted answer
  
  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$.
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_1**: $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?  
  > **username_0**: I think I am understanding what you wrote. It's more clear for me. Thank you so much!  
  > **username_1**: No problem. Glad to know I helped!  
  > **username_0**: 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 :((  
  > **username_1**: Exactly which part do you not understand? If you are more specific about this, then it would be easier to help you.  
  > **username_0**: I think I understand $precision@k(i)$ which has the $k$-top probability link to vertex $i$. I don't get AP. I think AP should $AP(i) = \frac{ \sum_{i \in S}{precision@k(i)} }{|S|}$  
  > **username_0**: I don't know why is $precision@j(i)$? Is $j$ like $k$ in $precision@k(i)$. If as the formula, I need to check all vertex (node) in graph by a for loop? And what is exactly $Q$ query? Like `Q = [1,2,10,100]` as value of $k$?  
  > **username_1**: @TruongHoang With that definition of $AP$, the argument of the function is being used as the index in the summation (which wouldn't make sense). Regarding $precision@j(i)$, yes - the $j$ is like the $k$ in $precision@k(i)$. For your last question, $Q$ is the set of vertices that you want to find the average precision for (it may be the whole graph).  
  
  ---
  
  ### Answer by username_2 on 2021-05-16. Score: 1
  
  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$.
  
  
  ---
  
  