Skip-gram with negative sampling (SGNS)

Overview

SGNS trains two embedding tables from observed pairs. For each pair it computes a dot product, gives the observed item a positive target, and gives b items drawn from a noise distribution a negative target. A logistic loss on these scores updates both tables. The pairs and the direction of prediction depend on the variant. In the graph setting, nodes play the role of "words" and the features of nearby nodes play the role of "contexts" 1909.13021 alg. 1. For that skip-gram form, the invariant is that at convergence the dot product of an item and a context approximates the shifted pointwise mutual information of their co-occurrence, log(#(w,c)|D| / (#(w)#(c))) − log b, where b is the number of negatives. This relation is taken from Levy and Goldberg's analysis of SGNS 1909.13021 §4. The sentence-embedding variant uses the same negative sampling loss but predicts each word from its sentence, so the PMI relation is not claimed for it (see Contradictions).

Variants

The first two cards build the pair corpus from first-order random walks on a graph, and pair each walk position with the features of positions a few steps away. The third card keeps the loss and reverses the direction.

Pooled corpus (AE)

All offsets r = 1..t go into one multiset, and a single SGNS model is trained with d dimensions. Walk length, window and negatives are set as in the paper's settings table 1909.13021 tab. 3. The paper shows that this pooled version factorizes the average of the powers P^r of the transition matrix, and that F = I recovers DeepWalk's matrix 1909.13021 §4.2. Card: Multi-scale Attributed Node Embedding.

One model per scale (MUSAE)

Pairs are kept apart by offset r. A separate SGNS model is trained for each offset, and the final embedding concatenates the parts. The theory gives one factorization per offset, log(c P^r F E^{-1}) − log b [arxiv:1909.13021 §4.1, thm. 1]. With F = I this is the Walklets setting 1909.13021 §4.2. The paper states that each part has d/t dimensions, so t must divide d 1909.13021 §3.2. Card: Multi-scale Attributed Node Embedding.

Identity-feature (EGO) variants

Each node also receives a unique feature for itself, which adds the identity matrix to the feature matrix. The paper reports this for both AE and MUSAE, and these variants are not inductive 1909.13021 §4.2, tab. 1. Card: Multi-scale Attributed Node Embedding.

Sentence context, word target (Sent2Vec)

The sentence is the context and each word in it is a target. A sentence vector is the mean of learned unigram and bigram vectors, and each word is predicted from the sentence with that word removed. The objective is therefore C-BOW-style rather than skip-gram, but it keeps SGNS's negative sampling with noise drawn from count^0.5 and 10 negatives 1703.02507 §2.1, eq. 3. Bigrams are hashed into buckets, and the paper drops a fixed number K of bigrams per sentence during training 1703.02507 §2.2, §2.4. Card: Unsupervised Learning of Sentence Embeddings using Compositional n-Gram Features.

When to use which

Only the cited papers' own experiments support the rows below.

Reported accuracy differences are small in several cases. On node classification the paper says multi-scale beats pooled more often than not, and EGO features make little difference 1909.13021 §5.2. On regression MUSAE-EGO has the best score on two of three Wikipedia datasets 1909.13021 tab. 5. For sentences, Sent2Vec uni+bi reports 82.0 average accuracy on six supervised tasks, against 83.8 for SkipThought 1703.02507 tab. 1.

Implementation sketch

The common core is one SGNS step: score a context vector against the observed item and against sampled negatives, then update both. The variants differ in what the context vector is and what the target is.

# Shared SGNS step for one positive pair and b sampled negatives
# [arxiv:1909.13021 alg. 1, line 15] [arxiv:1703.02507 §2.1, eq. 3]
# Input:  ctx_vec (d,), target id, output table U (items, d), lr, b
# Output: U updated in place, gradient for ctx_vec

def sgns_step(ctx_vec, target, U, lr, b, noise):
    grad_ctx = zeros_like(ctx_vec)
    # observed item gets label 1; b sampled items get label 0
    items = [(target, 1.0)] + [(n, 0.0) for n in noise.sample(b, target)]
    for item, label in items:
        score = dot(U[item], ctx_vec)
        g = lr * (label - sigmoid(score))
        grad_ctx += g * U[item]
        U[item] += g * ctx_vec
    return grad_ctx

# Skip-gram on walks: context is one node, target is one feature
# [arxiv:1909.13021 alg. 1, lines 6-10]
def skipgram_pass(walk_pairs, V, U, lr, b, noise):
    for node, feature in walk_pairs:
        V[node] += sgns_step(V[node], feature, U, lr, b, noise)

# Sent2Vec: context is the mean of the sentence's n-gram vectors, target is
# one word, and the word is left out of its own context  [arxiv:1703.02507 §2.1]
def sent2vec_pass(sentence, V, U, lr, b, noise, keep, K):
    for pos, word in enumerate(sentence):
        # target subsampling: skip the word with probability 1 - keep  [§2.1]
        if random_uniform() > keep[word]:
            continue
        # n-grams that do not touch position pos  [arxiv:1703.02507 eq. 3]
        feats = ngram_ids(sentence, skip=pos)
        # drop K bigrams at random; unigrams stay  [arxiv:1703.02507 §2.4]
        feats = drop_bigrams(feats, num_drop=K)
        ctx_vec = mean(V[feats], axis=0)  # sentence vector  [eq. 2]
        grad = sgns_step(ctx_vec, word, U, lr, b, noise)
        # each n-gram gets its share of the averaged gradient  [eq. 2]
        V[feats] += grad / len(feats)

Settings the two cards report differ, so one model's values should not be copied into the other. The graph experiments use 128 dimensions, walk length 80, 5 negatives, 5 epochs, and a learning rate falling from 0.05 to 0.025 1909.13021 tab. 3. The paper does not state the negative-sampling exponent or the frequent-item subsampling threshold. The Sent2Vec settings for the Wikipedia unigram+bigram model are 700 dimensions, a learning rate of 0.2, 10 negatives, 9 epochs, subsampling t = 5e-6 and K = 4 bigrams per sentence 1703.02507 tab. 5.

Contradictions

No two cards give incompatible numbers for the same setting, but they choose different things in three places.

• Negative distribution. Sent2Vec draws negatives with probability proportional to count^0.5 1703.02507 §2.1. The graph paper does not state its exponent 1909.13021 tab. 3; its released code uses 0.75, which is a different choice 1909.13021 tab. 3. Subsampling changes the counts that the factorization theorems rely on 1909.13021 §4.
• Which factorization applies. The PMI relation in the Overview is derived for skip-gram pairs 1909.13021 §4. The Sent2Vec card gives no analogous factorization result 1703.02507 §2, so the relation should not be assumed for sentence vectors.
• Learning rate and negatives. Sent2Vec uses 0.2 and 10 negatives 1703.02507 tab. 5. The graph paper uses 0.05 falling to 0.025 and 5 negatives 1909.13021 tab. 3. These are settings of different models on different data, not a dispute about one result.

The graph paper also differs from its own released code in several training details, listed in its card. The code adds an own-feature component and a different per-component size, and it applies frequent-item subsampling 1909.13021 §3.2, tab. 3. The paper's own configuration (d = 128, t = 3) also cannot follow the d/t rule exactly [arxiv:1909.13021 §3.2, tab. 3].

Papers

• Multi-scale Attributed Node Embedding: applies SGNS to random-walk (node, feature) pairs in two variants (AE and MUSAE), proves the matrices they factorize, and reports results on node classification and regression.
• Unsupervised Learning of Sentence Embeddings using Compositional n-Gram Features (Sent2Vec): sentence vectors as means of learned unigram and bigram vectors, trained by predicting each word from its sentence with negative sampling; reports supervised and unsupervised sentence benchmarks.