0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$ – Truong Hoang Aug 13 '20 at 11:05
  • $\begingroup$ $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? $\endgroup$ – Varun Vejalla Aug 13 '20 at 17:00
  • $\begingroup$ I think I am understanding what you wrote. It's more clear for me. Thank you so much! $\endgroup$ – Truong Hoang Aug 13 '20 at 19:33
  • $\begingroup$ No problem. Glad to know I helped! $\endgroup$ – Varun Vejalla Aug 13 '20 at 19:34
  • $\begingroup$ 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 :(( $\endgroup$ – Truong Hoang Aug 16 '20 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.