Random Walk Negative Sampling Seeded

Problem

Sample k non-edges uniformly from an undirected graph with n nodes as negative examples.

All pairs i < j that are not edges are candidates. Call random.seed(seed) first so results are reproducible, sample without replacement, and return the chosen pairs sorted. When fewer candidates than k exist, return all of them.

Hint

Negative sampling supplies the contrastive pairs that make link prediction trainable.

Test cases

case 1

in: [5,[[0,1],[1,2],[2,3]],3,42]

expected: [[0,2],[2,4],[3,4]]

case 2

in: [4,[[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]],2,7]

expected: []

case 3

in: [3,[[0,1],[1,2]],5,1]

expected: [[0,2]]

Starter codePython

import random
def negative_sampling(n, edges, k, seed):
    # Your code here
    pass

3 test cases · run your code against them in the editor