Negative sampling for graph representation learning

Question

I was watching a lecture about graph representation learning (from here) and got a little bit confusing about how they define the negative samping procedure.

In the presentation J. Leskovec briefly describes the famous trick with the following slide

He refers to the article by Y. Goldberg for details of how this formula is derived. The problem is that formula is a little bit different (with the additional minus sign in the sigmoid):

Moreover, in their famous article Mikolov et al defined negative sampling the same way.

I couldn't find any explaination from Leskovec or anyone about this difference. Would anyone be so kind to explain this to me?

Answer 1

I believe the approximation in the slide isn't quite right in 2 ways:

• The Golberg/Levy & Mikolov papers have the loss function right: as in standard binary classification, the "-" sign is inside the sigmoid ($\sigma$) function, you can't pull it out and put it before the summation (that happens when you consider gradients, but that's another matter).

• Negative sampling (line 2 of your equation) was used to avoid calculating softmax (line 1) when there are many classes, as it gets expensive. However, they are not mathematically equivalent, i.e. the embeddings ($\mathbf{z}$'s) learn different things. That is why in word2vec (and also in comparable graph embedding models) the embeddings end up factorising pointwise mutual information ("PMI", see Goldberg/Levy paper) when using the marginal probability of each word/node as the noise distribution $P_V$.

(Note: Negative sampling is inspired by Noise Contrastive Estimation (NCE). They are not the same thing but often confused, e.g. https://datascience.stackexchange.com/a/93326/116384.)